小白從0學習推薦系統 ---04 機器學習模型介紹

文章目錄

• • 監督學習
  • • 回歸模型
    • 分類模型
    • • K近鄰（KNN）
      • 邏輯斯蒂回歸
      • 決策樹
  • 無監督學習
  • • 聚類
    • • K-均值

監督學習

回歸模型

• 線性回歸模型
  • 線性回歸(Linear Regression)是一種線性模型，它假設輸入變量x和單個輸出變量y之間存線上性關系
  • 具體來說，利用線性回歸模型，可以從一組輸入變量x的線性組合中，計算輸出變量y
    • y=ax+b
    • f ( x ) = w 1 x 1 + w 2 x 2 + . . . + w d x d + b f(x)=w_{1}x_{1}+w_{2}x_{2}+...+w_{d}x_{d}+b f(x)=w1​x1​+w2​x2​+...+wd​xd​+b
    • 給定有d個屬性（特征）描述的示例 x=(x1;x2;…;xd)，其中xi是x在第i個屬性（特征）上的取值，線性模型（linear model）試圖學得一個通過屬性（特征）的線性組合來進行預測的函數，即:
      • f ( x ) = w 1 x 1 + w 2 x 2 + . . . + w d x d + b f(x)=w_{1}x_{1}+w_{2}x_{2}+...+w_{d}x_{d}+b f(x)=w1​x1​+w2​x2​+...+wd​xd​+b
    • 一般用向量形式寫成： f ( x ) = w T x + b f(x)=w^{T}x+b f(x)=wTx+b ( 其中w=( w 1 ; w 2 ; . . . ; w d w_{1};w_{2};...;w_{d} w1​;w2​;...;wd​) )
    • 假設特征和結果都滿足線性，即不大于一次方
  • 一進制線性回歸
  • 多元線性回歸
    • 如果有兩個或者兩個以上的自變量，這樣的線性回歸分析就稱為多元線性回歸
    • 實際問題中，一個現象往往受多個因素的影響，是以多元線性回歸通常比一進制線性回歸的實際應用更廣
• 非線性回歸 模型
• 最小二乘法
  • 基于均方誤差最小化來進行模型求解的方法稱為 最小二乘法（least square method）
  • 其主要思想是 選擇未知參數，使得理論值與觀測值之差的平方和達到最小
  • 我們假設輸入屬性（特征）的數目隻有一個：
    • f ( x i ) = w x i + b , 使 得 f ( x i ≃ y i ) f(x_{i})=wx_{i}+b,使得f(x_{i}\simeq y_{i}) f(xi​)=wxi​+b,使得f(xi​≃yi​)
  • 線上性回歸中，最小二乘法就是試圖 找到一條直線，使所有樣本到直線上的歐氏距離之和最小

    • 

• 求解線性回歸
  • 線性回歸模型的“最小二乘參數估計”：求解w和b,使得 E ( w , b ) = ∑ i = 1 m ( y i − w x i − b ) 2 E_{(w,b)}=\sum_{i=1}^{m}(y_{i}-wx_{i}-b)^{2} E(w,b)​=∑i=1m​(yi​−wxi​−b)2最小化的過程
  • 将 E ( w , b ) E_{(w,b)} E(w,b)​分别對w和b求導,可以得到
    • ∂ E ( w , b ) ∂ w = 2 ( w ∑ i = 1 m x i 2 − ∑ i = 1 m ( y i − b ) x i ) \frac{∂E_{(w,b)}}{∂w}=2(w\sum_{i=1}^{m}x_{i}^2-\sum_{i=1}^{m}(y_{i}-b)x_{i}) ∂w∂E(w,b)​​=2(w∑i=1m​xi2​−∑i=1m​(yi​−b)xi​)
    • ∂ E ( w , b ) ∂ b = 2 ( m b − ∑ i = 1 m ( y i − w x i ) ) \frac{∂E_{(w,b)}}{∂b}=2(mb-\sum_{i=1}^{m}(y_{i}-wx_{i})) ∂b∂E(w,b)​​=2(mb−∑i=1m​(yi​−wxi​))
  • 另偏導數都為0，可以得到

    • 

    • 其中 x ˉ = 1 m x i \bar{x}=\frac{1}{m}x_{i} xˉ=m1​xi​
• 使用梯度下降法來求解線性回歸

  

  • 使用梯度下降法來求解一進制線性回歸

    

• 梯度下降法和最小二乘法
• 相同點
  • 本質和目标相同：兩種方法都是經典的學習算法，在給定已知資料的前提下利用求導算出一個模型（函數），使得損失函數最小，然後對給定的新資料進行估算預測。
• 不同點
  • 損失函數：梯度下降可以選取其它損失函數，而最小二乘法一定是平方損失函數
  • 實作方法：最小二乘法是直接求導找出全局最小，而梯度下降是一種疊代法
  • 效果：最小二乘找到的一定是全局最小，但計算繁瑣，且複雜情況下未必有解；梯度下降疊代計算簡單，但找到的一般都是局部最小，隻有在目标函數是凸函數時才是全局最小；到最小點附近時收斂速度會變慢，且對初始點的選擇極為敏感。

分類模型

K近鄰（KNN）

• 最簡單最初級的分類器，就是将全部的訓練資料所對應的類别都記錄下來，當測試對象的屬性和某個訓練對象的屬性完全比對時，便可以對其進行分類
• K近鄰（K-nearest neighbour,KNN）是一種基本分類方法，通過測量不同特征值之間的距離進行分類。它的思路是：如果一個樣本在特征空間中的k個最相似（即特征空間中最鄰近）的樣本中的大多數屬于某一個類别，則該樣本也屬于這個類别，其中K通常是不大于20的整數
• KNN算法中，所選取的鄰居都是已經正确分類的對象
• KNN算法的結果很大程度取決于K的選擇
• KNN的距離計算
  • KNN中，通過計算對象間距離來作為各個對象之間的非相似性名額，避免了對象之間的比對問題，在這裡距離一般使用歐氏距離或曼哈頓距離

  • 歐式距離：d(x,y)= ∑ k = 1 n ( x k − y k ) 2 \sqrt{\sum_{k=1}^{n}(x_{k}-y_{k})^2} ∑k=1n​(xk​−yk​)2

    ​

  • 曼哈頓距離：d(x,y)= ∑ k = 1 n ∣ x k − y k ∣ \sqrt{\sum_{k=1}^{n}|x_{k}-y_{k}|} ∑k=1n​∣xk​−yk​∣

    ​

• 在訓練集中資料和标簽已知的情況下，輸入測試資料，将測試資料的特征與測試集中對應的特征進行互相比較，找到訓練集中與之最為相似的前k個資料，則該測試資料對應的類别就是k個資料中出現次數最多的那個分類，其算法的描述為：
  • a) 計算測試資料與各個訓練資料之間的距離；
  • b) 按照距離的遞增關系進行排序；
  • c) 選取距離最小的K個點；
  • d) 确定前K個點所在類别的出現機率；
  • e) 傳回前K個點中出現頻率最高的類别作為測試資料的預測分類。

邏輯斯蒂回歸

• 邏輯斯蒂回歸 能夠解決分類問題

  

• Sigmoid函數（壓縮函數）
  • g(z)= 1 1 + e − z \frac{1}{1+e^{-z}} 1+e−z1​

  • 

  • sigmoid函數中， e − z e^{-z} e−z中z的正負決定了g(z)的值最後是大于0.5還是小于0.5；即z大于0時，g(z)大于0.5，z小于0時，g(z)小于0.5
  • 當z對應的表達式為分類邊界時，恰好有分類邊界兩側對應z正負不同，也就使得分類邊界兩邊分别對應g(z)>0.5和g(z)<0.5，是以根據g(z)與0.5的大小關系，就可以實作分類
• 損失函數

  • 

  • 

• 損失函數求解步驟

  • 

  • 

  • 這樣我們就能獲得一個 凸函數
  • 梯度下降法求解

    • 

決策樹

• 決策樹是一種簡單高效并且具有強解釋性的模型，廣泛應用于資料分析領域。其本質是一顆自上向下的由多個判斷節點組成的樹
• 決策樹與if-then規則
  • 決策樹可以看作是一個 if-then 規則的集合
  • 由決策樹的根節點到葉節點的每一條路徑，建構一條規則：路徑上内部節點的特征對應着規則的條件（condition）,葉節點對應規則的結論
  • 決策樹的if-then規則集合有一個重要性質：互斥并且完備。也就是說，每個執行個體都被一條規則（一條路徑）所覆寫，并且隻被這一條規則覆寫
  • 決策樹中的判斷條件 的确定過程就是 特征選擇 的過程
• 決策樹的目标
  • 決策樹學習的本質，是從訓練資料集中歸納出一組 if-then分類規則
  • 與訓練集不相沖突的決策樹，可能有很多個，也可能一個都沒有；是以我們需要選擇一個與訓練資料集沖突較小的決策樹
  • 另一角度，我們可以把決策樹砍成一個條件機率模型，我們的目标是将執行個體配置設定到條件機率更大的那一類中去
  • 從所有可能的情況中選擇最優決策樹，是一個np完全問題，是以我們通常采用啟發式算法求解決策樹，得到一個次最優解
  • 采用的算法通常是遞歸地進行以下過程：選擇最優特征，并根據該特征對訓練資料進行分割，使得各個子資料集都有一個最好的分類
• 特征選擇
  • 特征選擇就是決定用哪個特征來劃分特征空間
• 随機變量
  • 随機變量（random variable）的本質是一個函數，是從樣本空間的子集到實數的映射，将事件轉換成一個數值
  • 根據樣本空間中的元素不同（即不同的實驗結果），随機變量的值也将随機産生。可以說，随機變量是“數值化”的實驗結果
  • 在現實生活中，實驗結果是描述性的詞彙，比如“硬币的正反面”，而在數學家的角度，這些文字化的描述太過繁瑣，可以用數字來0、1來替代它們。
• 熵
  • 熵(entropy)用來衡量随機變量的不确定性
  • 變量的不确定性越大，熵也就越大,也就是變量的不确定性與熵成正相關關系
  • 設X是一個取有限個值的離散随機變量，其機率分布為： P ( X = x i ) = p i , i = 1 , 2 , . . , n P(X=x_{i})=p_{i},i=1,2,..,n P(X=xi​)=pi​,i=1,2,..,n，則随機變量x的熵定義為： H ( X ) = − ∑ i = 1 n p i l o g P i H(X)=-\sum_{{i=1}}^{n}p_{i}logP_{i} H(X)=−∑i=1n​pi​logPi​，通常，上式中的對數以2為底或者以e為底（自然對數），這時熵的機關分别稱為比特(bit)或納特(nat)

  • 當随機變量隻取兩個值，例如1,0時，則X的分布為：P（X=1）=p，P(x=0)=1-p, 0 ⩽ p ⩽ 1 0\leqslant p \leqslant1 0⩽p⩽1

    此時 熵為： H ( p ) = − p l o g 2 p − ( 1 − p ) l o g 2 ( 1 − p ) H(p)=-plog _{2}p-(1-p)log _{2}(1-p) H(p)=−plog2​p−(1−p)log2​(1−p)

    這個熵H§随機率p變化的曲線如圖所示：

    

  • 熵的示例 （給三個小球分類）
    • 1.将紅球獨自一組，黑球一組 ，此時熵：E=-1/3log(1/3)-2/3log(2/3)=0.918

      

    • 2.一個紅球和一個黑球一組，另外一個黑球自己一組，此時熵:E=-1/2log(1/2)-1/2log(1/2)-1*log(1)=1

      

    • 3.将紅球自己一組，剩下兩個黑球一組，此時熵：E=-1log(1)-1log(1)=0

      

• 決策樹的目标
  • 我們使用決策樹模型的最終目的是利用決策樹模型進行分類預測，預測我們給出的一組資料最終屬于哪一種類别，這是一個由不确定到确定的過程
  • 最終理想的分類是，每一組資料，都能确定性地按照決策樹分支找到對應的類别
  • 是以我們就選擇使資料資訊熵下降最快的特征作為分類節點，使得決策樹盡快地趨于确定
• 條件熵 （conditional entropy）
  • 條件熵H(Y|X)表示在已知随機變量X的條件下随機變量Y的不确定性： H ( Y ∣ X ) = ∑ i = 1 n p i H ( Y ∣ X = x i ) H(Y|X)=\sum_{i=1}^{n}p_{i}H(Y|X=x_{i}) H(Y∣X)=∑i=1n​pi​H(Y∣X=xi​),其中， p i = P ( X = x i ) p_{i}=P(X=x_{i}) pi​=P(X=xi​)
  • 熵H(D)表示對資料集D進行分類的不确定性
  • 條件熵H(D|A)指在給定特征A的條件下資料集分類的不确定性
  • 當熵和條件熵的機率由資料估計得到時，所對應的熵與條件熵分别稱為經驗熵（empirial entropy）和經驗條件熵(empirical conditional entropy)
• 資訊增益
  • 特征A對訓練資料集D的資訊增益g(D,A),定義為集合D的**經驗熵H(D)與特征A給定條件下D的條件熵H(D|A)**之差，即 g(D,A)=H(D)-H(D|A)
  • 決策樹學習應用 資訊增益準則 選擇特征
  • 經驗熵H(D)表示對資料集D進行分類的不确定性。而經驗條件熵H(D|A)表示在特征A給定的條件下對資料集D進行分類的不确定性。那麼它們的差，即資訊增益，就表示由于特征A而使得對資料集D的分類的不确定性減少的程度
  • 對于資料集D而言，資訊增益依賴于特征，不同的特征往往具有不同的資訊增益
  • 資訊增益大的特征具有更強的分類能力
• 決策樹的生成算法
  • ID3
    • 決策樹（ID3） 的訓練過程就是找到資訊增益最大的特征，然後按照此特征進行分類，然後再找到各類型子集中的資訊增益最大的特征，然後再按照此特征進行分類，最終得到符合要求的模型
  • C4.5
    • C4.5算法在ID3的基礎上做了改進，用資訊增益比來選擇特征
  • 分類與回歸樹（CART）
    • 由特征選擇、樹的生成和剪枝三部分組成，既可以用于分類也可以用于回歸

無監督學習

• 聚類
  • K均值
  • 基于密度的聚類
  • 最大期望聚類
• 降維
  • 潛語義分析（LSA）
  • 主成分分析（PCA）
  • 奇異值分解（SVD）

聚類

K-均值

• K均值（K-means）是聚類算法中最為簡單、高效的，屬于無監督學習算法
• 核心思想：由使用者指定的K個初始質心（initial centroids）,以作為聚類的類别（cluster）,重複疊代直至算法收斂
• 基本算法流程：
  • 選取k個初始質心（作為初始cluster）
  • repeat:
    • 對每個樣本點，計算得到距其最近的質心，将其類别标記為該質心所對應的cluster;
    • 重新計算K個cluster對應的質心
  • until 質心不再發生變化或疊代達到上限

    

• 關注「一個熱愛學習的計算機小白」公衆号 ，對作者的小小鼓勵，後續更多資源敬請關注。

•