机器学习常见算法个人总结（面试用）
樸素貝葉斯
參考[1]
事件A和B同時發生的概率為在A發生的情況下發生B或者在B發生的情況下發生A
所以有：
[Math Processing Error]P(A|B)=P(B|A)?P(A)P(B)
對于給出的待分類項，求解在此項出現的條件下各個目標類別出現的概率，哪個最大，就認為此待分類項屬于哪個類別
工作原理
[Math Processing Error]p(ai|yi)表示該類別下該特征出現的概率
[Math Processing Error]p(yi)表示全部類別中這個這個類別出現的概率
工作流程
確定特征屬性，并對每個特征屬性進行適當劃分，然后由人工對一部分待分類項進行分類，形成訓練樣本。
計算每個類別在訓練樣本中的出現頻率及每個特征屬性劃分對每個類別的條件概率估計
使用分類器進行分類，輸入是分類器和待分類樣本，輸出是樣本屬于的分類類別
屬性特征
那么[Math Processing Error]p(ak|yi)=g(xk,ni,ui)
Laplace校準(拉普拉斯校驗)
當某個類別下某個特征劃分沒有出現時，會有[Math Processing Error]P(a|y)=0，就是導致分類器質量降低，所以此時引入Laplace校驗，就是對沒類別下所有劃分的計數加1。
遇到特征之間不獨立問題
參考改進的貝葉斯網絡，使用DAG來進行概率圖的描述
優缺點
樸素貝葉斯的優點：
缺點：
邏輯回歸和線性回歸
參考[2,3,4]
LR回歸是一個線性的二分類模型，主要是計算在某個樣本特征下事件發生的概率，比如根據用戶的瀏覽購買情況作為特征來計算它是否會購買這個商品，抑或是它是否會點擊這個商品。然后LR的最終值是根據一個線性和函數再通過一個sigmod函數來求得，這個線性和函數權重與特征值的累加以及加上偏置求出來的，所以在訓練LR時也就是在訓練線性和函數的各個權重值w。
[Math Processing Error]hw(x)=11+e?(wTx+b)
關于這個權重值w一般使用最大似然法來估計,假設現在有樣本[Math Processing Error]{xi,yi},其中[Math Processing Error]xi表示樣本的特征，[Math Processing Error]yi∈{0,1}表示樣本的分類真實值，[Math Processing Error]yi=1的概率是[Math Processing Error]pi,則[Math Processing Error]yi=0的概率是[Math Processing Error]1?pi，那么觀測概率為:
則最大似然函數為:
[Math Processing Error]∏(hw(xi)yi?(1?hw(xi))1?yi)
對這個似然函數取對數之后就會得到的表達式
估計這個 [Math Processing Error]L(w)的極大值就可以得到 [Math Processing Error]w的估計值。
實際操作中一般會加個負號 改為求最小
所以求解問題就變成了這個最大似然函數的最優化問題，這里通常會采樣隨機梯度下降法和擬牛頓迭代法來進行優化
梯度下降法
LR的損失函數為:
這樣就變成了求 [Math Processing Error]min(J(w))
其更新w的過程為
[Math Processing Error]w:=w?α?▽J(w)w:=w?α?1N?∑i=1N(hw(xi)?yi)?xi)
其中 [Math Processing Error]α為步長,直到 [Math Processing Error]J(w)不能再小時停止
梯度下降法的最大問題就是會陷入局部最優，并且每次在對當前樣本計算cost的時候都需要去遍歷全部樣本才能得到cost值，這樣計算速度就會慢很多（雖然在計算的時候可以轉為矩陣乘法去更新整個w值）
所以現在好多框架（mahout）中一般使用隨機梯度下降法，它在計算cost的時候只計算當前的代價，最終cost是在全部樣本迭代一遍之求和得出，還有他在更新當前的參數w的時候并不是依次遍歷樣本，而是從所有的樣本中隨機選擇一條進行計算，它方法收斂速度快（一般是使用最大迭代次數），并且還可以避免局部最優，并且還很容易并行（使用參數服務器的方式進行并行）
這里SGD可以改進的地方就是使用動態的步長
其他優化方法
- 擬牛頓法（記得是需要使用Hessian矩陣和cholesky分解）
- BFGS
- L-BFGS
優缺點：無需選擇學習率α，更快，但是更復雜
關于LR的過擬合問題：
如果我們有很多的特性，在訓練集上擬合得很好，但是在預測集上卻達不到這種效果
添加正則化之后的損失函數為:?[Math Processing Error]J(w)=?1N∑i=1N(yi?log(hw(xi))+(1?yi)?log(1?hw(xi)))+λ||w||2
同時w的更新變為[Math Processing Error]w:=w?α?(hw(xj)?yj)?xi)?2α?wj
注意：這里的[Math Processing Error]w0不受正則化影響
關于LR的多分類：softmax
假設離散型隨機變量Y的取值集合是{1,2,..,k},則多分類的LR為
這里會輸出當前樣本下屬于哪一類的概率，并且滿足全部概率加起來=1
關于softmax和k個LR的選擇
如果類別之間是否互斥（比如音樂只能屬于古典音樂、鄉村音樂、搖滾月的一種）就用softmax
否則類別之前有聯系（比如一首歌曲可能有影視原聲，也可能包含人聲，或者是舞曲），這個時候使用k個LR更為合適
優缺點：
Logistic回歸優點：
缺點：
ps 另外LR還可以參考這篇以及多分類可以看這篇
KNN算法
給一個訓練數據集和一個新的實例，在訓練數據集中找出與這個新實例最近的k個訓練實例，然后統計最近的k個訓練實例中所屬類別計數最多的那個類，就是新實例的類
三要素：
k值的選擇
所以一般k會取一個較小的值，然后用過交叉驗證來確定
這里所謂的交叉驗證就是將樣本劃分一部分出來為預測樣本，比如95%訓練，5%預測，然后k分別取1，2，3，4，5之類的，進行預測，計算最后的分類誤差，選擇誤差最小的k
KNN的回歸
在找到最近的k個實例之后，可以計算這k個實例的平均值作為預測值。或者還可以給這k個實例添加一個權重再求平均值，這個權重與度量距離成反比（越近權重越大）。
優缺點：
KNN算法的優點：
缺點：
KD樹
KD樹是一個二叉樹，表示對K維空間的一個劃分，可以進行快速檢索（那KNN計算的時候不需要對全樣本進行距離的計算了）
構造KD樹
在k維的空間上循環找子區域的中位數進行劃分的過程。
假設現在有K維空間的數據集[Math Processing Error]T={x1,x2,x3,…xn},[Math Processing Error]xi={a1,a2,a3..ak}
KD樹的搜索
KD樹進行KNN查找
通過KD樹的搜索找到與搜索目標最近的點，這樣KNN的搜索就可以被限制在空間的局部區域上了，可以大大增加效率。
KD樹搜索的復雜度
當實例隨機分布的時候，搜索的復雜度為log(N)，N為實例的個數，KD樹更加適用于實例數量遠大于空間維度的KNN搜索，如果實例的空間維度與實例個數差不多時，它的效率基于等于線性掃描。
后來自己有實現過KD樹，可以看KNN算法中KD樹的應用
SVM、SMO
對于樣本點[Math Processing Error](xi,yi)以及svm的超平面：[Math Processing Error]wTxi+b=0
- 函數間隔：[Math Processing Error]yi(wTxi+b)
- 幾何間隔：[Math Processing Error]yi(wTxi+b)||w||,其中[Math Processing Error]||w||為[Math Processing Error]w的L2范數，幾何間隔不會因為參數比例的改變而改變
svm的基本想法就是求解能正確劃分訓練樣本并且其幾何間隔最大化的超平面。
線性SVM問題
先來看svm的問題:
那么假設[Math Processing Error]γ^=γ?||w||
則將問題轉為：
[Math Processing Error]argmaxw,bγ^||w||st.yi(wTxi+b)≥1
由于[Math Processing Error]γ^的成比例增減不會影響實際間距，所以這里的取[Math Processing Error]γ^=1，又因為[Math Processing Error]max(1||w||)=min(12?||w||2)
所以最終的問題就變為了
這樣就變成了一個凸的二次規劃化，可以將其轉換為拉格朗日函數，然后使用對偶算法來求解
對偶求解
引進拉格朗日乘子[Math Processing Error]α={α1,α2..αn},定義拉格朗日函數：
根據對偶性質 原始問題就是求對偶問題的極大極小
先求L對 [Math Processing Error]w,b的極小，再求對 [Math Processing Error]α的極大。
求 [Math Processing Error]minw,bL(w,b,α)，也就是相當于對 [Math Processing Error]w,b求偏導并且另其等于0
[Math Processing Error]▽wL(w,b,α)=w?∑i=1N(αiyixi)=0▽bL(w,b,α)=∑i=1N(aiyi)=0
代入后可得
[Math Processing Error]minw,bL(w,b,α)=?12?∑i=1N∑j=1N(αiαjyiyj(xi?xj))+∑i=1Nαi
求 [Math Processing Error]minw,bL(w,b,α)對 [Math Processing Error]α的極大，即是對偶問題:
[Math Processing Error]maxα?12?∑i=1N∑j=1N(αiαjyiyj(xi?xj))+∑i=1Nαist.∑i=1N(aiyi)=0α≥0,i=1,2,3…N
將求最大轉為求最小，得到等價的式子為：
[Math Processing Error]minα12?∑i=1N∑j=1N(αiαjyiyj(xi?xj))?∑i=1Nαist.∑i=1N(aiyi)=0α≥0,i=1,2,3…N
假如求解出來的[Math Processing Error]α為[Math Processing Error]α?=(α1?,α2?,…αn?)
則得到最優的[Math Processing Error]w,b分別為
所以，最終的決策分類面為
[Math Processing Error]f(x)=sign(∑i=1N(αi?yi(x?xi)+b?)
也就是說，分類決策函數只依賴于輸入 [Math Processing Error]x與訓練樣本的輸入的內積
ps：上面介紹的是SVM的硬間距最大化，還有一種是軟間距最大化，引用了松弛變量[Math Processing Error]ζ，則次svm問題變為:
其余解決是與硬間距的一致~
還有：與分離超平面最近的樣本點稱為支持向量
損失函數
損失函數為（優化目標）:
其中 [Math Processing Error][1?yi(wTxi+b)]+稱為折頁損失函數，因為:
[Math Processing Error][1?yi(wTxi+b)]+={0if1?yi(wTxi+b)≤01?yi(wTxi+b)otherwise
為什么要引入對偶算法
核函數
將輸入特征x（線性不可分）映射到高維特征R空間，可以在R空間上讓SVM進行線性可以變，這就是核函數的作用
- 多項式核函數:[Math Processing Error]K(x,z)=(x?z+1)p
- 高斯核函數:[Math Processing Error]K(x,z)=exp(?(x?z)2σ2)
- 字符串核函數：貌似用于字符串處理等
SVM優缺點
優點：
缺點：
SMO
SMO是用于快速求解SVM的
它選擇凸二次規劃的兩個變量，其他的變量保持不變，然后根據這兩個變量構建一個二次規劃問題，這個二次規劃關于這兩個變量解會更加的接近原始二次規劃的解，通過這樣的子問題劃分可以大大增加整個算法的計算速度，關于這兩個變量：
SVM多分類問題
直接在目標函數上進行修改，將多個分類面的參數求解合并到一個最優化問題中，通過求解該優化就可以實現多分類（計算復雜度很高，實現起來較為困難）
其中某個類為一類，其余n-1個類為另一個類，比如A,B,C,D四個類，第一次A為一個類，{B,C,D}為一個類訓練一個分類器，第二次B為一個類,{A,C,D}為另一個類,按這方式共需要訓練4個分類器，最后在測試的時候將測試樣本經過這4個分類器[Math Processing Error]f1(x),[Math Processing Error]f2(x),[Math Processing Error]f3(x)和[Math Processing Error]f4(x),取其最大值為分類器(這種方式由于是1對M分類，會存在偏置，很不實用)
任意兩個類都訓練一個分類器，那么n個類就需要n*(n-1)/2個svm分類器。
還是以A,B,C,D為例,那么需要{A,B},{A,C},{A,D},{B,C},{B,D},{C,D}為目標共6個分類器，然后在預測的將測試樣本通過這6個分類器之后進行投票選擇最終結果。（這種方法雖好，但是需要n*(n-1)/2個分類器代價太大，不過有好像使用循環圖來進行改進）
決策樹
決策樹是一顆依托決策而建立起來的樹。
ID3
[Math Processing Error]S(C,ai)=?∑i(pi?log(pi))一個屬性中某個類別的熵? [Math Processing Error]pi=P(yi|ai),? [Math Processing Error]pi表示 [Math Processing Error]ai情況下發生 [Math Processing Error]yi的概率，也即是統計概率。
[Math Processing Error]S(C,A)=∑i(P(A=ai)?S(ai))?整個屬性的熵，為各個類別的比例與各自熵的加權求和。
[Math Processing Error]Gain(C,A)=S(C)?S(C,A)?增益表示分類目標的熵減去當前屬性的熵，增益越大，分類能力越強
(這里前者叫做經驗熵，表示數據集分類C的不確定性，后者就是經驗條件熵，表示在給定A的條件下對數據集分類C的不確定性，兩者相減叫做互信息，決策樹的增益等價于互信息)。
比如說當前屬性是是否擁有房產，分類是是否能償還債務
現在：
- 有用房產為7個，4個能償還債務，3個無法償還債務
- 然后無房產為3個，其中1個能償還債務，2個無法償還債務
然后
有房子的熵：[Math Processing Error]S(have_house)=?(47?log47+37?log37)
無房子的熵：[Math Processing Error]S(no_house)=?(13?log13+23?log23)
分類的熵：[Math Processing Error]S(classifier)=?(510?log510+510?log510)
最終的增益=[Math Processing Error]S(classifier)?(710?S(have_house)+310?S(no_house))?最大越好
關于損失函數
設樹的葉子節點個數為[Math Processing Error]T，[Math Processing Error]t為其中一個葉子節點，該葉子節點有[Math Processing Error]Nt個樣本，其中[Math Processing Error]k類的樣本有[Math Processing Error]Ntk個，[Math Processing Error]H(t)為葉子節點上的經驗熵，則損失函數定義為
其中
[Math Processing Error]H(t)=∑(NtkNt?log(NtkNt))
代入可以得到
[Math Processing Error]Ct(T)=∑(∑(Ntk?log(Ntk/Nt)))+λ|T|
[Math Processing Error]λ|T|為正則化項，[Math Processing Error]λ是用于調節比率
決策樹的生成只考慮了信息增益
C4.5
它是ID3的一個改進算法，使用信息增益率來進行屬性的選擇
優缺點：
準確率高，但是子構造樹的過程中需要進行多次的掃描和排序，所以它的運算效率較低
Cart
分類回歸樹(Classification And Regression Tree)是一個決策二叉樹，在通過遞歸的方式建立，每個節點在分裂的時候都是希望通過最好的方式將剩余的樣本劃分成兩類，這里的分類指標：
分類樹：
gini用來度量分布不均勻性（或者說不純），總體的類別越雜亂，GINI指數就越大（跟熵的概念很相似）
gini越小，表示樣本分布越均勻（0的時候就表示只有一類了），越大越不均勻
基尼增益 [Math Processing Error]gini_gain=∑i(NiN?gini(ai))?表示當前屬性的一個混亂? [Math Processing Error]NiN表示當前類別占所有類別的概率
最終Cart選擇GiniGain最小的特征作為劃分特征
以ID3中的貸款的那棵樹為樣例：
基尼指數有房產:[Math Processing Error]gini(have_house)=1?((37)2+(47)2)
基尼指數無房產:[Math Processing Error]gini(no_house)=1?((13)2+(23)2)
基尼增益為:[Math Processing Error]gini_gain=710?gini(have_house)+310?gini(no_house)
回歸樹：
回歸樹是以平方誤差最小化的準則劃分為兩塊區域
使其最小化的平方誤差是：[Math Processing Error]min{min(R1.sigma((yi?c1)2))+min(R2.sigma((yi?c2)2))}
計算根據s劃分到左側和右側子樹的目標值與預測值之差的平方和最小，這里的預測值是兩個子樹上輸入xi樣本對應[Math Processing Error]yi的均值
[Math Processing Error]R1(j)={x|x(j)≤s}R2(j)={x|x(j)>s}
這里面的最小化我記得可以使用最小二乘法來求
關于剪枝：用獨立的驗證數據集對訓練集生長的樹進行剪枝（事后剪枝）。
停止條件
關于特征與目標值
決策樹的分類與回歸
- 分類樹
輸出葉子節點中所屬類別最多的那一類 - 回歸樹
輸出葉子節點中各個樣本值的平均值
理想的決策樹
解決決策樹的過擬合
優缺點
優點：
缺點：
隨機森林RF
隨機森林是有很多隨機得決策樹構成，它們之間沒有關聯。得到RF以后，在預測時分別對每一個決策樹進行判斷，最后使用Bagging的思想進行結果的輸出（也就是投票的思想）
學習過程
預測過程
參數問題
泛化誤差估計
使用oob（out-of-bag）進行泛化誤差的估計，將各個樹的未采樣樣本作為預測樣本（大約有36.8%），使用已經建立好的森林對各個預測樣本進行預測，預測完之后最后統計誤分得個數占總預測樣本的比率作為RF的oob誤分率。
學習算法
關于CART
Cart可以通過特征的選擇迭代建立一顆分類樹，使得每次的分類平面能最好的將剩余數據分為兩類
[Math Processing Error]gini=1?∑(pi2)，表示每個類別出現的概率和與1的差值，
分類問題：[Math Processing Error]argmax(Gini?GiniLeft?GiniRight)
回歸問題：[Math Processing Error]argmax(Var?VarLeft?VarRight)
查找最佳特征f已經最佳屬性閾值th 小于th的在左邊，大于th的在右邊子樹
優缺點
GBDT
GBDT的精髓在于訓練的時候都是以上一顆樹的殘差為目標，這個殘差就是上一個樹的預測值與真實值的差值。
比如，當前樣本年齡是18歲，那么第一顆會去按18歲來訓練，但是訓練完之后預測的年齡為12歲，差值為6， 所以第二顆樹的會以6歲來進行訓練，假如訓練完之后預測出來的結果為6，那么兩棵樹累加起來就是真實年齡了， 但是假如第二顆樹預測出來的結果是5，那么剩余的殘差1就會交給第三個樹去訓練。Boosting的好處就是每一步的參加就是變相了增加了分錯instance的權重，而對已經對的instance趨向于0，這樣后面的樹就可以更加關注錯分的instance的訓練了
Shrinkage
Shrinkage認為，每次走一小步逐步逼近的結果要比每次邁一大步逼近結果更加容易避免過擬合。
就像我們做互聯網，總是先解決60%用戶的需求湊合著，再解決35%用戶的需求，最后才關注那5%人的需求，這樣就能逐漸把產品做好.
調參
優缺點：
優點：
缺點：
BP
最小二乘法
最小二乘法是一種數學的優化技術，通過求最小化平方誤差來尋找最佳的函數匹配
假設現在有二維的觀測數據[Math Processing Error](x1,y1),(x2,y2)…(xn,yn)，求[Math Processing Error]y=a+bx的擬合。
現設[Math Processing Error]yi=a+b?xi+ki?如果有[Math Processing Error]a,b能得到[Math Processing Error]∑i=1N(|ki|)最小，則該線比較理想
所以先變為求[Math Processing Error]min(∑i=1N(ki))?，這個與[Math Processing Error]min(∑i=1N(ki2))等價
而[Math Processing Error]ki=yi?(a+b?xi)
那么現設[Math Processing Error]f=∑i=1N((yi?(a+b?xi))2)求其最小即可
上述就是最小二乘原則，估計[Math Processing Error]a,b的方法稱為最小二乘法
先求[Math Processing Error]f對[Math Processing Error]a,b的偏導：
[Math Processing Error]▽bf=?2?xi?∑i=1N(yi?(a+b?xi))=0
現設：
[Math Processing Error]X=∑i=1NxiNY=∑i=1NyiN
則代入上述偏導：
[Math Processing Error]a?N+b?N?X=N?Ya?N?X+b?∑i=1N(xi2)=∑i=1N(xi?yi)
求該行列式:
[Math Processing Error]|NN?XN?X∑i=1Nxi2|=N?∑i=1N((xi?X))!=0
所以有唯一解
最后記：
則
[Math Processing Error]b=l(xy)l(xx)a=Y?b?X
百度文庫-最小二乘法
EM
EM用于隱含變量的概率模型的極大似然估計，它一般分為兩步：第一步求期望(E),第二步求極大(M)，
如果概率模型的變量都是觀測變量，那么給定數據之后就可以直接使用極大似然法或者貝葉斯估計模型參數。
但是當模型含有隱含變量的時候就不能簡單的用這些方法來估計，EM就是一種含有隱含變量的概率模型參數的極大似然估計法。
應用到的地方：混合高斯模型、混合樸素貝葉斯模型、因子分析模型
Bagging
Boosting
boosting在訓練的時候會給樣本加一個權重，然后使loss function盡量去考慮那些分錯類的樣本（比如給分錯類的樣本的權重值加大）
凸優化
在機器學習中往往是最終要求解某個函數的最優值，但是一般情況下，任意一個函數的最優值求解比較困難，但是對于凸函數來說就可以有效的求解出全局最優值。
凸集
一個集合C是，當前僅當任意x,y屬于C且[Math Processing Error]0≤Θ≤1，都有[Math Processing Error]Θ?x+(1?Θ)?y屬于C
用通俗的話來說C集合線段上的任意兩點也在C集合中
凸函數
一個函數f其定義域(D(f))是凸集，并且對任意x,y屬于D(f)和[Math Processing Error]0≤Θ≤1都有
用通俗的話來說就是曲線上任意兩點的割線都在曲線的上方
常見的凸函數有：
- 指數函數[Math Processing Error]f(x)=ax;a>1
- 負對數函數[Math Processing Error]?logax;a>1,x>0
- 開口向上的二次函數等
凸函數的判定：
凸優化應用舉例
- SVM：其中由[Math Processing Error]max|w|?轉向[Math Processing Error]min(12?|w|2)
- 最小二乘法？
- LR的損失函數[Math Processing Error]∑(yi?log(hw(xi))+(1?yi)?(log(1?hw(xi))))
參考
[1].?http://www.cnblogs.com/leoo2sk/archive/2010/09/17/naive-bayesian-classifier.html
[2].?http://www.cnblogs.com/biyeymyhjob/archive/2012/07/18/2595410.html
[3].?http://blog.csdn.net/abcjennifer/article/details/7716281
[4].?http://ufldl.stanford.edu/wiki/index.php/Softmax%E5%9B%9E%E5%BD%92
[5]. 《統計學習方法》.李航
備注
資料主要來源于網絡或者《統計學習方法》，還有自己一小部分的總結，如果錯誤之處敬請指出
from:?http://kubicode.me/2015/08/16/Machine%20Learning/Algorithm-Summary-for-Interview/#優缺點：
總結
以上是生活随笔為你收集整理的机器学习常见算法个人总结（面试用）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： matlab连接字符串
- 下一篇： Uniform Grid Quadtre