樸素貝葉斯

參考[1]

事件A和B同時發生的機率為在A發生的情況下發生B或者在B發生的情況下發生A

P(A∩B)=P(A)∗P(B|A)=P(B)∗P(A|B)P(A∩B)=P(A)∗P(B|A)=P(B)∗P(A|B)

是以有：

P(A|B)=P(B|A)∗P(A)P(B)P(A|B)=P(B|A)∗P(A)P(B)

對于給出的待分類項，求解在此項出現的條件下各個目标類别出現的機率，哪個最大，就認為此待分類項屬于哪個類别

工作原理

假設現在有樣本x=(a1,a2,a3,…an)x=(a1,a2,a3,…an)這個待分類項(并認為xx裡面的特征獨立)

再假設現在有分類目标Y={y1,y2,y3,y4..yn}Y={y1,y2,y3,y4..yn}

那麼max(P(y1|x),P(y2|x),P(y3|x)..P(yn|x))max(P(y1|x),P(y2|x),P(y3|x)..P(yn|x))就是最終的分類類别

而P(yi|x)=p(x|yi)∗P(yi)P(x)P(yi|x)=p(x|yi)∗P(yi)P(x)

因為xx對于每個分類目标來說都一樣，是以就是求max(P(x|yi)∗p(yi))max(P(x|yi)∗p(yi))

P(x|yi)∗p(yi)=p(yi)∗∏i(P(ai|yi))P(x|yi)∗p(yi)=p(yi)∗∏i(P(ai|yi))

而具體的p(ai|yi)p(ai|yi)和p(yi)p(yi)都是能從訓練樣本中統計出來

p(ai|yi)p(ai|yi)表示該類别下該特征出現的機率

p(yi)p(yi)表示全部類别中這個這個類别出現的機率

好的，就是這麼工作的^_^

工作流程

準備階段

确定特征屬性，并對每個特征屬性進行适當劃分，然後由人工對一部分待分類項進行分類，形成訓練樣本。

訓練階段

計算每個類别在訓練樣本中的出現頻率及每個特征屬性劃分對每個類别的條件機率估計

應用階段

使用分類器進行分類，輸入是分類器和待分類樣本，輸出是樣本屬于的分類類别

屬性特征

特征為離散值時直接統計即可（表示統計機率）

特征為連續值的時候假定特征符合高斯分布:g(x,n,u)g(x,n,u)

那麼p(ak|yi)=g(xk,ni,ui)p(ak|yi)=g(xk,ni,ui)

Laplace校準(拉普拉斯校驗)

當某個類别下某個特征劃分沒有出現時，會有P(a|y)=0P(a|y)=0，就是導緻分類器品質降低，是以此時引入Laplace校驗，就是對每個類别下所有劃分的計數加1。

遇到特征之間不獨立問題

參考改進的貝葉斯網絡，使用DAG來進行機率圖的描述

優缺點

樸素貝葉斯的優點：

對小規模的資料表現很好，适合多分類任務，适合增量式訓練。

缺點：

對輸入資料的表達形式很敏感（離散、連續，值極大極小之類的）。

邏輯回歸和線性回歸

參考[2,3,4]

LR回歸是一個線性的二分類模型，主要是計算在某個樣本特征下事件發生的機率，比如根據使用者的浏覽購買情況作為特征來計算它是否會購買這個商品，抑或是它是否會點選這個商品。然後LR的最終值是根據一個線性和函數再通過一個sigmod函數來求得，這個線性和函數權重與特征值的累加以及加上偏置求出來的，是以在訓練LR時也就是在訓練線性和函數的各個權重值w。

hw(x)=11+e−(wTx+b)hw(x)=11+e−(wTx+b)

關于這個權重值w一般使用最大似然法來估計,假設現在有樣本 {xi,yi}{xi,yi},其中 xixi表示樣本的特征， yi∈{0,1}yi∈{0,1}表示樣本的分類真實值， yi=1yi=1的機率是 pipi,則 yi=0yi=0的機率是 1−pi1−pi，那麼觀測機率為:

p(yi)=pyii∗(1−pi)1−yip(yi)=piyi∗(1−pi)1−yi

則最大似然函數為:

∏(hw(xi)yi∗(1−hw(xi))1−yi)∏(hw(xi)yi∗(1−hw(xi))1−yi)

對這個似然函數取對數之後就會得到的表達式

L(w)=∑i(yi∗loghw(xi)−(1−yi)∗log(1−hw(xi)))=∑i(yi∗(wTxi)−log(1+ewTxi))L(w)=∑i(yi∗loghw(xi)−(1−yi)∗log(1−hw(xi)))=∑i(yi∗(wTxi)−log(1+ewTxi))

估計這個 L(w)L(w)的極大值就可以得到 ww的估計值。

實際操作中一般會加個負号改為求最小

是以求解問題就變成了這個最大似然函數的最優化問題，這裡通常會采樣随機梯度下降法和拟牛頓疊代法來進行優化

梯度下降法

LR的損失函數為:

J(w)=−1N∑i=1N(yi∗log(hw(xi))+(1−yi)∗log(1−hw(xi)))J(w)=−1N∑i=1N(yi∗log(hw(xi))+(1−yi)∗log(1−hw(xi)))

這樣就變成了求 min(J(w))min(J(w))

其更新w的過程為

w:=w−α∗▽J(w)w:=w−α∗1N∗∑i=1N(hw(xi)−yi)∗xi)w:=w−α∗▽J(w)w:=w−α∗1N∗∑i=1N(hw(xi)−yi)∗xi)

其中 α為步長α為步長,直到 J(w)J(w)不能再小時停止

梯度下降法的最大問題就是會陷入局部最優，并且每次在對目前樣本計算cost的時候都需要去周遊全部樣本才能得到cost值，這樣計算速度就會慢很多（雖然在計算的時候可以轉為矩陣乘法去更新整個w值）

是以現在好多架構（mahout）中一般使用随機梯度下降法，它在計算cost的時候隻計算目前的代價，最終cost是在全部樣本疊代一遍之求和得出，還有他在更新目前的參數w的時候并不是依次周遊樣本，而是從所有的樣本中随機選擇一條進行計算，它方法收斂速度快（一般是使用最大疊代次數），并且還可以避免局部最優，并且還很容易并行（使用參數伺服器的方式進行并行）

w:=w−α∗(hw(xj)−yj)∗xi);j∈1 Nandrandomlyw:=w−α∗(hw(xj)−yj)∗xi);j∈1 Nandrandomly

這裡SGD可以改進的地方就是使用動态的步長

α=0.04∗(1.0+n+i)+rα=0.04∗(1.0+n+i)+r

其他優化方法

拟牛頓法（記得是需要使用Hessian矩陣和cholesky分解）

BFGS

L-BFGS

優缺點：無需選擇學習率α，更快，但是更複雜

關于LR的過拟合問題

如果我們有很多的特性，在訓練集上拟合得很好，但是在預測集上卻達不到這種效果

1. 減少feature個數（人工定義留多少個feature、算法選取這些feature）

2. 正則化（為了友善求解，L2使用較多）

添加正則化之後的損失函數為:

J(w)=−1N∑i=1N(yi∗log(hw(xi))+(1−yi)∗log(1−hw(xi)))+λ||w||2J(w)=−1N∑i=1N(yi∗log(hw(xi))+(1−yi)∗log(1−hw(xi)))+λ||w||2

同時w的更新變為 w:=w−α∗(hw(xj)−yj)∗xi)−2α∗wjw:=w−α∗(hw(xj)−yj)∗xi)−2α∗wj

注意：這裡的 w0w0不受正則化影響

關于LR的多分類：softmax

假設離散型随機變量Y的取值集合是{1,2,..,k},則多分類的LR為

P(Y=a|x)=ewa∗x∑ki=1ewi∗xP(Y=a|x)=ewa∗x∑i=1kewi∗x

這裡會輸出目前樣本下屬于哪一類的機率，并且滿足全部機率加起來=1

關于softmax和k個LR的選擇

如果類别之間是否互斥（比如音樂隻能屬于古典音樂、鄉村音樂、搖滾月的一種）就用softmax

否則類别之前有聯系（比如一首歌曲可能有影視原聲，也可能包含人聲，或者是舞曲），這個時候使用k個LR更為合适

優缺點

Logistic回歸優點：

實作簡單；

分類時計算量非常小，速度很快，存儲資源低；

缺點：

容易欠拟合，一般準确度不太高

隻能處理兩分類問題（在此基礎上衍生出來的softmax可以用于多分類），且必須線性可分；

ps 另外LR還可以參考這篇以及多分類可以看這篇

KNN算法

給一個訓練資料集和一個新的執行個體，在訓練資料集中找出與這個新執行個體最近的k個訓練執行個體，然後統計最近的k個訓練執行個體中所屬類别計數最多的那個類，就是新執行個體的類

三要素

k值的選擇
距離的度量（常見的距離度量有歐式距離，馬氏距離等）
分類決策規則（多數表決規則）

k值的選擇

k值越小表明模型越複雜，更加容易過拟合
但是k值越大，模型越簡單，如果k=N的時候就表明無論什麼點都是訓練集中類别最多的那個類

是以一般k會取一個較小的值，然後用交叉驗證來确定

這裡所謂的交叉驗證就是将樣本劃分一部分出來為預測樣本，比如95%訓練，5%預測，然後k分别取1，2，3，4，5之類的，進行預測，計算最後的分類誤差，選擇誤差最小的k

KNN的回歸

在找到最近的k個執行個體之後，可以計算這k個執行個體的平均值作為預測值。或者還可以給這k個執行個體添加一個權重再求平均值，這個權重與度量距離成反比（越近權重越大）。

優缺點：

KNN算法的優點：

1. 思想簡單，理論成熟，既可以用來做分類也可以用來做回歸；

2. 可用于非線性分類；

3. 訓練時間複雜度為O(n)；

4. 準确度高，對資料沒有假設，對outlier不敏感；

缺點：

1. 計算量大；

2. 樣本不平衡問題（即有些類别的樣本數量很多，而其它樣本的數量很少）；

3. 需要大量的記憶體；

KD樹

KD樹是一個二叉樹，表示對K維空間的一個劃分，可以進行快速檢索（那KNN計算的時候不需要對全樣本進行距離的計算了）

構造KD樹

在k維的空間上循環找子區域的中位數進行劃分的過程。

假設現在有K維空間的資料集T={x1,x2,x3,…xn}T={x1,x2,x3,…xn},xi={a1,a2,a3..ak}xi={a1,a2,a3..ak}

1. 首先構造根節點，以坐标a1a1的中位數b為切分點，将根結點對應的矩形局域劃分為兩個區域，區域1中a1<ba1<b,區域2中a1>ba1>b

2. 構造葉子節點，分别以上面兩個區域中a2a2的中位數作為切分點，再次将他們兩兩劃分，作為深度1的葉子節點，（如果a2=中位數，則a2的執行個體落在切分面）

3. 不斷重複2的操作，深度為j的葉子節點劃分的時候，索取的aiai 的i=j%k+1i=j%k+1，直到兩個子區域沒有執行個體時停止

KD樹的搜尋

首先從根節點開始遞歸往下找到包含x的葉子節點，每一層都是找對應的xi
将這個葉子節點認為是目前的“近似最近點”
遞歸向上回退，如果以x圓心，以“近似最近點”為半徑的球與根節點的另一半子區域邊界相交，則說明另一半子區域中存在與x更近的點，則進入另一個子區域中查找該點并且更新”近似最近點“
重複3的步驟，直到另一子區域與球體不相交或者退回根節點
最後更新的”近似最近點“與x真正的最近點

KD樹進行KNN查找

通過KD樹的搜尋找到與搜尋目标最近的點，這樣KNN的搜尋就可以被限制在空間的局部區域上了，可以大大增加效率。

KD樹搜尋的複雜度

當執行個體随機分布的時候，搜尋的複雜度為log(N)，N為執行個體的個數，KD樹更加适用于執行個體數量遠大于空間次元的KNN搜尋，如果執行個體的空間次元與執行個體個數差不多時，它的效率基于等于線性掃描。

後來自己有實作過KD樹，可以看KNN算法中KD樹的應用

SVM、SMO

對于樣本點(xi,yi)(xi,yi)以及svm的超平面：wTxi+b=0wTxi+b=0

- 函數間隔：yi(wTxi+b)yi(wTxi+b)

- 幾何間隔：yi(wTxi+b)||w||yi(wTxi+b)||w||,其中||w||||w||為ww的L2範數，幾何間隔不會因為參數比例的改變而改變

svm的基本想法就是求解能正确劃分訓練樣本并且其幾何間隔最大化的超平面。

線性SVM問題

先來看svm的問題:

argmaxw,bγst.yi(wTxi+b)||w||≥γargmaxw,bγst.yi(wTxi+b)||w||≥γ

那麼假設 γ^=γ∗||w||γ^=γ∗||w||

則将問題轉為：

argmaxw,bγ^||w||st.yi(wTxi+b)≥1argmaxw,bγ^||w||st.yi(wTxi+b)≥1

由于 γ^γ^的成比例增減不會影響實際間距，是以這裡的取 γ^=1γ^=1，又因為 max(1||w||)=min(12∗||w||2)max(1||w||)=min(12∗||w||2)

是以最終的問題就變為了

argminw,b12∗||w||2st.yi(wTxi+b)≥1argminw,b12∗||w||2st.yi(wTxi+b)≥1

這樣就變成了一個凸的二次規劃化，可以将其轉換為拉格朗日函數，然後使用對偶算法來求解

對偶求解

引進拉格朗日乘子α={α1,α2..αn}α={α1,α2..αn},定義拉格朗日函數：

L(w,b,a)=12∗||w||2−∑i=1N(αi∗yi(wTxi+b))+∑(αi)L(w,b,a)=12∗||w||2−∑i=1N(αi∗yi(wTxi+b))+∑(αi)

根據對偶性質原始問題就是求對偶問題的極大極小

maxαminw,bL(w,b,α)maxαminw,bL(w,b,α)

先求L對 w,bw,b的極小，再求對 αα的極大。

求 minw,bL(w,b,α)minw,bL(w,b,α)，也就是相當于對 w,bw,b求偏導并且另其等于0

▽wL(w,b,α)=w−∑i=1N(αiyixi)=0▽bL(w,b,α)=∑i=1N(aiyi)=0▽wL(w,b,α)=w−∑i=1N(αiyixi)=0▽bL(w,b,α)=∑i=1N(aiyi)=0

代入後可得

minw,bL(w,b,α)=−12∗∑i=1N∑j=1N(αiαjyiyj(xi⋅xj))+∑i=1Nαiminw,bL(w,b,α)=−12∗∑i=1N∑j=1N(αiαjyiyj(xi⋅xj))+∑i=1Nαi

求 minw,bL(w,b,α)minw,bL(w,b,α)對 αα的極大，即是對偶問題:

maxα−12∗∑i=1N∑j=1N(αiαjyiyj(xi⋅xj))+∑i=1Nαist.∑i=1N(aiyi)=0α≥0,i=1,2,3…Nmaxα−12∗∑i=1N∑j=1N(αiαjyiyj(xi⋅xj))+∑i=1Nαist.∑i=1N(aiyi)=0α≥0,i=1,2,3…N

将求最大轉為求最小，得到等價的式子為：

minα12∗∑i=1N∑j=1N(αiαjyiyj(xi⋅xj))−∑i=1Nαist.∑i=1N(aiyi)=0α≥0,i=1,2,3…Nminα12∗∑i=1N∑j=1N(αiαjyiyj(xi⋅xj))−∑i=1Nαist.∑i=1N(aiyi)=0α≥0,i=1,2,3…N

假如求解出來的 αα為 α∗=(α∗1,α∗2,…α∗n)α∗=(α1∗,α2∗,…αn∗)

則得到最優的 w,bw,b分别為

w∗=∑i=1N(α∗iyixi)b∗=yj−∑i=1N(α∗iyi(xi⋅xj))w∗=∑i=1N(αi∗yixi)b∗=yj−∑i=1N(αi∗yi(xi⋅xj))

是以，最終的決策分類面為

f(x)=sign(∑i=1N(α∗iyi(x⋅xi)+b∗)f(x)=sign(∑i=1N(αi∗yi(x⋅xi)+b∗)

也就是說，分類決策函數隻依賴于輸入 xx與訓練樣本的輸入的内積

ps：上面介紹的是SVM的硬間距最大化，還有一種是軟間距最大化，引用了松弛變量 ζζ，則次svm問題變為:

\underset{w,b}{argmin} \quad \frac{1}{2}*||w||^2 + C \sum_{i=1}^{N} \zeta_i \\ st. \quad y_i(w^Tx_i+b) \geq 1-\zeta_i \\ \zeta_i \geq 0,i=1,2…N argminw,b12∗||w||2+C∑i=1Nζist.yi(wTxi+b)≥1−ζiζi≥0,i=1,2…Nargminw,b12∗||w||2+C∑i=1Nζist.yi(wTxi+b)≥1−ζiζi≥0,i=1,2…N

其餘解決是與硬間距的一緻~

還有：與分離超平面最近的樣本點稱為支援向量

損失函數

損失函數為（優化目标）:

∑i=1N[1−yi(wTxi+b)]++λ||w||2∑i=1N[1−yi(wTxi+b)]++λ||w||2

其中 [1−yi(wTxi+b)]+[1−yi(wTxi+b)]+稱為折頁損失函數，因為:

[1−yi(wTxi+b)]+={01−yi(wTxi+b)if1−yi(wTxi+b)≤0otherwise[1−yi(wTxi+b)]+={0if1−yi(wTxi+b)≤01−yi(wTxi+b)otherwise

為什麼要引入對偶算法

對偶問題往往更加容易求解(結合拉格朗日和kkt條件)

可以很自然的引用核函數（拉格朗日表達式裡面有内積，而核函數也是通過内積進行映射的）

核函數

将輸入特征x（線性不可分）映射到高維特征R空間，可以在R空間上讓SVM進行線性可以變，這就是核函數的作用

多項式核函數:K(x,z)=(x∗z+1)pK(x,z)=(x∗z+1)p

高斯核函數:K(x,z)=exp(−(x−z)2σ2)K(x,z)=exp(−(x−z)2σ2)

字元串核函數：貌似用于字元串處理等

SVM優缺點

優點：

1. 使用核函數可以向高維空間進行映射

2. 使用核函數可以解決非線性的分類

3. 分類思想很簡單，就是将樣本與決策面的間隔最大化

4. 分類效果較好

缺點：

1. 對大規模資料訓練比較困難

2. 無法直接支援多分類，但是可以使用間接的方法來做

SMO

SMO是用于快速求解SVM的

它選擇凸二次規劃的兩個變量，其他的變量保持不變，然後根據這兩個變量建構一個二次規劃問題，這個二次規劃關于這兩個變量解會更加的接近原始二次規劃的解，通過這樣的子問題劃分可以大大增加整個算法的計算速度，關于這兩個變量：

1. 其中一個是嚴重違反KKT條件的一個變量

2. 另一個變量是根據自由限制确定，好像是求剩餘變量的最大化來确定的。

SVM多分類問題

直接法

直接在目标函數上進行修改，将多個分類面的參數求解合并到一個最優化問題中，通過求解該優化就可以實作多分類（計算複雜度很高，實作起來較為困難）
間接法
1. 一對多
  
  其中某個類為一類，其餘n-1個類為另一個類，比如A,B,C,D四個類，第一次A為一個類，{B,C,D}為一個類訓練一個分類器，第二次B為一個類,{A,C,D}為另一個類,按這方式共需要訓練4個分類器，最後在測試的時候将測試樣本經過這4個分類器f1(x)f1(x),f2(x)f2(x),f3(x)f3(x)和f4(x)f4(x),取其最大值為分類器(這種方式由于是1對M分類，會存在偏置，很不實用)
2. 一對一(libsvm實作的方式)
  
  任意兩個類都訓練一個分類器，那麼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

首先是針對目前的集合，計算每個特征的資訊增益
然後選擇資訊增益最大的特征作為目前節點的決策決策特征
根據特征不同的類别劃分到不同的子節點（比如年齡特征有青年，中年，老年，則劃分到3顆子樹）
然後繼續對子節點進行遞歸，直到所有特征都被劃分

S(C,ai)=−∑i(pi∗log(pi))S(C,ai)=−∑i(pi∗log(pi))

一個屬性中某個類别的熵 pi=P(yi|ai)pi=P(yi|ai), pipi表示aiai情況下發生yiyi的機率，也即是統計機率。

S(C,A)=∑i(P(A=ai)∗S(ai))S(C,A)=∑i(P(A=ai)∗S(ai)) 整個屬性的熵，為各個類别的比例與各自熵的權重求和。

Gain(C,A)=S(C)−S(C,A)Gain(C,A)=S(C)−S(C,A) 增益表示分類目标的熵減去目前屬性的熵，增益越大，分類能力越強

(這裡前者叫做經驗熵，表示資料集分類C的不确定性，後者就是經驗條件熵，表示在給定A的條件下對資料集分類C的不确定性，兩者相減叫做互資訊，決策樹的增益等價于互資訊)。

比如說目前屬性是是否擁有房産，分類是是否能償還債務

現在：

- 有用房産為7個，4個能償還債務，3個無法償還債務

- 然後無房産為3個，其中1個能償還債務，2個無法償還債務

然後

有房子的熵： S(have_house)=−(47∗log47+37∗log37)S(have_house)=−(47∗log47+37∗log37)

無房子的熵： S(no_house)=−(13∗log13+23∗log23)S(no_house)=−(13∗log13+23∗log23)

分類的熵： S(classifier)=−(510∗log510+510∗log510)S(classifier)=−(510∗log510+510∗log510)

最終的增益= S(classifier)−(710∗S(have_house)+310∗S(no_house))S(classifier)−(710∗S(have_house)+310∗S(no_house)) 最大越好

關于損失函數

設樹的葉子節點個數為TT，tt為其中一個葉子節點，該葉子節點有NtNt個樣本，其中kk類的樣本有NtkNtk個，H(t)H(t)為葉子節點上的經驗熵，則損失函數定義為

Ct(T)=∑(Nt∗H(t))+λ|T|Ct(T)=∑(Nt∗H(t))+λ|T|

其中

H(t)=∑(NtkNt∗log(NtkNt))H(t)=∑(NtkNt∗log(NtkNt))

代入可以得到

Ct(T)=∑(∑(Ntk∗log(Ntk/Nt)))+λ|T|Ct(T)=∑(∑(Ntk∗log(Ntk/Nt)))+λ|T|

λ|T|λ|T|為正則化項， λλ是用于調節比率

決策樹的生成隻考慮了資訊增益

C4.5

它是ID3的一個改進算法，使用資訊增益率來進行屬性的選擇

splitInformation(S,A)=−∑i(|Si||S|∗log2(|Si||S|))GainRatio(S,A)=Gain(S,A)splitInformation(S,A)splitInformation(S,A)=−∑i(|Si||S|∗log2(|Si||S|))GainRatio(S,A)=Gain(S,A)splitInformation(S,A)

優缺點：

準确率高，但是子構造樹的過程中需要進行多次的掃描和排序，是以它的運算效率較低

Cart

分類回歸樹(Classification And Regression Tree)是一個決策二叉樹，在通過遞歸的方式建立，每個節點在分裂的時候都是希望通過最好的方式将剩餘的樣本劃分成兩類，這裡的分類名額：

1. 分類樹：基尼指數最小化(gini_index)

2. 回歸樹：平方誤差最小化

分類樹：

1. 首先是根據目前特征計算他們的基尼增益

2. 選擇基尼增益最小的特征作為劃分特征

3. 從該特征中查找基尼指數最小的分類類别作為最優劃分點

4. 将目前樣本劃分成兩類，一類是劃分特征的類别等于最優劃分點，另一類就是不等于

5. 針對這兩類遞歸進行上述的劃分工作，直達所有葉子指向同一樣本目标或者葉子個數小于一定的門檻值

gini用來度量分布不均勻性（或者說不純），總體的類别越雜亂，GINI指數就越大（跟熵的概念很相似）

gini(ai)=1−∑i(p2i)gini(ai)=1−∑i(pi2) pipi目前資料集中第i類樣本的比例

gini越小，表示樣本分布越均勻（0的時候就表示隻有一類了），越大越不均勻

基尼增益 gini_gain=∑i(NiN∗gini(ai))gini_gain=∑i(NiN∗gini(ai)) 表示目前屬性的一個混亂 NiNNiN表示目前類别占所有類别的機率

最終Cart選擇GiniGain最小的特征作為劃分特征

以ID3中的貸款的那棵樹為樣例：

基尼指數有房産: gini(have_house)=1−((37)2+(47)2)gini(have_house)=1−((37)2+(47)2)

基尼指數無房産: gini(no_house)=1−((13)2+(23)2)gini(no_house)=1−((13)2+(23)2)

基尼增益為: gini_gain=710∗gini(have_house)+310∗gini(no_house)gini_gain=710∗gini(have_house)+310∗gini(no_house)

回歸樹

回歸樹是以平方誤差最小化的準則劃分為兩塊區域

周遊特征計算最優的劃分點s，

使其最小化的平方誤差是：

min{min(R1.sigma((yi−c1)2))+min(R2.sigma((yi−c2)2))}min{min(R1.sigma((yi−c1)2))+min(R2.sigma((yi−c2)2))}

計算根據s劃分到左側和右側子樹的目标值與預測值之差的平方和最小，這裡的預測值是兩個子樹上輸入xi樣本對應yiyi的均值
找到最小的劃分特征j以及其最優的劃分點s,根據特征j以及劃分點s将現有的樣本劃分為兩個區域，一個是在特征j上小于等于s，另一個在在特征j上大于s

R1(j)={x|x(j)≤s}R2(j)={x|x(j)>s}R1(j)={x|x(j)≤s}R2(j)={x|x(j)>s}
進入兩個子區域按上述方法繼續劃分，直到到達停止條件
這裡面的最小化我記得可以使用最小二乘法來求
關于剪枝：用獨立的驗證資料集對訓練集生長的樹進行剪枝（事後剪枝）。

停止條件

直到每個葉子節點都隻有一種類型的記錄時停止，（這種方式很容易過拟合）
另一種時當葉子節點的記錄樹小于一定的門檻值或者節點的資訊增益小于一定的門檻值時停止

關于特征與目标值

特征離散目标值離散：可以使用ID3，cart
特征連續目标值離散：将連續的特征離散化可以使用ID3，cart
特征離散目标值連續

決策樹的分類與回歸

分類樹

輸出葉子節點中所屬類别最多的那一類
回歸樹

輸出葉子節點中各個樣本值的平均值

理想的決策樹

葉子節點數盡量少

葉子節點的深度盡量小(太深可能會過拟合)

解決決策樹的過拟合

剪枝
1. 前置剪枝：在分裂節點的時候設計比較苛刻的條件，如不滿足則直接停止分裂（這樣幹決策樹無法到最優，也無法得到比較好的效果）
2. 後置剪枝：在樹建立完之後，用單個節點代替子樹，節點的分類采用子樹中主要的分類（這種方法比較浪費前面的建立過程）
交叉驗證
随機森林

優缺點

優點：

1. 計算量簡單，可解釋性強，比較适合處理有缺失屬性值的樣本，能夠處理不相關的特征；

缺點：

1. 單顆決策樹分類能力弱，并且對連續值變量難以處理；

2. 容易過拟合（後續出現了随機森林，減小了過拟合現象）；

随機森林RF

随機森林是有很多随機得決策樹構成，它們之間沒有關聯。得到RF以後，在預測時分别對每一個決策樹進行判斷，最後使用Bagging的思想進行結果的輸出（也就是投票的思想）

學習過程

現在有N個訓練樣本，每個樣本的特征為M個，需要建K顆樹
從N個訓練樣本中有放回的取N個樣本作為一組訓練集（其餘未取到的樣本作為預測分類，評估其誤差）
從M個特征中取m個特征左右子集特征(m<
對采樣的資料使用完全分裂的方式來建立決策樹，這樣的決策樹每個節點要麼無法分裂，要麼所有的樣本都指向同一個分類
重複2的過程K次，即可建立森林

預測過程

将預測樣本輸入到K顆樹分别進行預測
如果是分類問題，直接使用投票的方式選擇分類頻次最高的類别
如果是回歸問題，使用分類之後的均值作為結果

參數問題

這裡的一般取m=sqrt(M)
關于樹的個數K，一般都需要成百上千，但是也有具體的樣本有關（比如特征數量）
樹的最大深度，（太深可能可能導緻過拟合？？）
節點上的最小樣本數、最小資訊增益

泛化誤差估計

使用oob（out-of-bag）進行泛化誤差的估計，将各個樹的未采樣樣本作為預測樣本（大約有36.8%），使用已經建立好的森林對各個預測樣本進行預測，預測完之後最後統計誤分得個數占總預測樣本的比率作為RF的oob誤分率。

學習算法

ID3算法：處理離散值的量
C45算法：處理連續值的量
Cart算法：離散和連續兩者都合适？

關于CART

Cart可以通過特征的選擇疊代建立一顆分類樹，使得每次的分類平面能最好的将剩餘資料分為兩類

gini=1−∑(p2i)gini=1−∑(pi2)，表示每個類别出現的機率和與1的內插補點，

分類問題：argmax(Gini−GiniLeft−GiniRight)argmax(Gini−GiniLeft−GiniRight)

回歸問題：argmax(Var−VarLeft−VarRight)argmax(Var−VarLeft−VarRight)

查找最佳特征f已經最佳屬性門檻值th 小于th的在左邊，大于th的在右邊子樹

優缺點

能夠處理大量特征的分類，并且還不用做特征選擇
在訓練完成之後能給出哪些feature的比較重要
訓練速度很快
很容易并行
實作相對來說較為簡單

GBDT

GBDT的精髓在于訓練的時候都是以上一顆樹的殘差為目标，這個殘差就是上一個樹的預測值與真實值的內插補點。

比如，目前樣本年齡是18歲，那麼第一顆會去按18歲來訓練，但是訓練完之後預測的年齡為12歲，內插補點為6，是以第二顆樹的會以6歲來進行訓練，假如訓練完之後預測出來的結果為6，那麼兩棵樹累加起來就是真實年齡了，但是假如第二顆樹預測出來的結果是5，那麼剩餘的殘差1就會交給第三個樹去訓練。

Boosting的好處就是每一步的參加就是變相了增加了分錯instance的權重，而對已經對的instance趨向于0，這樣後面的樹就可以更加關注錯分的instance的訓練了

Shrinkage

Shrinkage認為，每次走一小步逐漸逼近的結果要比每次邁一大步逼近結果更加容易避免過拟合。

y(1∼i)=y(1∼i−1)+step∗yiy(1∼i)=y(1∼i−1)+step∗yi

就像我們做網際網路，總是先解決60%使用者的需求湊合着，再解決35%使用者的需求，最後才關注那5%人的需求，這樣就能逐漸把産品做好.

調參

樹的個數 100~10000
葉子的深度 3~8
學習速率 0.01~1
葉子上最大節點樹 20
訓練采樣比例 0.5~1
訓練特征采樣比例 sqrt(num)

優缺點：

優點：

1. 精度高

2. 能處理非線性資料

3. 能處理多特征類型

4. 适合低維稠密資料

缺點：

1. 并行麻煩（因為上下兩顆樹有聯系）

2. 多分類的時候複雜度很大

BP

最小二乘法

最小二乘法是一種數學的優化技術，通過求最小化平方誤差來尋找最佳的函數比對

假設現在有二維的觀測資料(x1,y1),(x2,y2)…(xn,yn)(x1,y1),(x2,y2)…(xn,yn)，求y=a+bxy=a+bx的拟合。

現設yi=a+b∗xi+kiyi=a+b∗xi+ki 如果有a,ba,b能得到∑Ni=1(|ki|)∑i=1N(|ki|)最小，則該線比較理想

是以先變為求min(∑Ni=1(ki))min(∑i=1N(ki)) ，這個與min(∑Ni=1(k2i))min(∑i=1N(ki2))等價

而ki=yi−(a+b∗xi)ki=yi−(a+b∗xi)

那麼現設f=∑i=1N((yi−(a+b∗xi))2)f=∑i=1N((yi−(a+b∗xi))2)求其最小即可

上述就是最小二乘原則，估計a,ba,b的方法稱為最小二乘法

先求ff對a,ba,b的偏導：

▽af=−2∗∑i=1N(yi−(a+b∗xi))=0▽af=−2∗∑i=1N(yi−(a+b∗xi))=0

▽bf=−2∗xi∗∑i=1N(yi−(a+b∗xi))=0▽bf=−2∗xi∗∑i=1N(yi−(a+b∗xi))=0

現設：

X=∑Ni=1xiNY=∑Ni=1yiNX=∑i=1NxiNY=∑i=1NyiN

則代入上述偏導：

a∗N+b∗N∗X=N∗Ya∗N∗X+b∗∑i=1N(x2i)=∑i=1N(xi∗yi)a∗N+b∗N∗X=N∗Ya∗N∗X+b∗∑i=1N(xi2)=∑i=1N(xi∗yi)

求該行列式:

∣∣∣NN∗XN∗X∑Ni=1x2i∣∣∣=N∗∑i=1N((xi−X))!=0|NN∗XN∗X∑i=1Nxi2|=N∗∑i=1N((xi−X))!=0

是以有唯一解

最後記：

l(xx)=∑i=1N(xi−X)2l(yy)=∑i=1N(yi−Y)2l(xy)=∑i=1N((xi−X)(yi−Y))l(xx)=∑i=1N(xi−X)2l(yy)=∑i=1N(yi−Y)2l(xy)=∑i=1N((xi−X)(yi−Y))

則

b=l(xy)l(xx)a=Y−b∗Xb=l(xy)l(xx)a=Y−b∗X

EM

EM用于隐含變量的機率模型的極大似然估計，它一般分為兩步：第一步求期望(E),第二步求極大(M)，

如果機率模型的變量都是觀測變量，那麼給定資料之後就可以直接使用極大似然法或者貝葉斯估計模型參數。

但是當模型含有隐含變量的時候就不能簡單的用這些方法來估計，EM就是一種含有隐含變量的機率模型參數的極大似然估計法。

應用到的地方：混合高斯模型、混合樸素貝葉斯模型、因子分析模型

Bagging

從N樣本中有放回的采樣N個樣本
對這N個樣本在全屬性上建立分類器(CART,SVM)
重複上面的步驟，建立m個分類器
預測的時候使用投票的方法得到結果

Boosting

boosting在訓練的時候會給樣本加一個權重，然後使loss function盡量去考慮那些分錯類的樣本（比如給分錯類的樣本的權重值加大）

凸優化

在機器學習中往往是最終要求解某個函數的最優值，但是一般情況下，任意一個函數的最優值求解比較困難，但是對于凸函數來說就可以有效的求解出全局最優值。

凸集

一個集合C是，目前僅當任意x,y屬于C且0≤Θ≤10≤Θ≤1，都有Θ∗x+(1−Θ)∗yΘ∗x+(1−Θ)∗y屬于C

用通俗的話來說C集合線段上的任意兩點也在C集合中

凸函數

一個函數f其定義域(D(f))是凸集，并且對任意x,y屬于D(f)和0≤Θ≤10≤Θ≤1都有

f(Θ∗x+(1−Θ)∗y)≤Θ∗f(x)+(1−Θ)∗f(y)f(Θ∗x+(1−Θ)∗y)≤Θ∗f(x)+(1−Θ)∗f(y)

用通俗的話來說就是曲線上任意兩點的割線都在曲線的上方

常見的凸函數有：

指數函數 f(x)=ax;a>1f(x)=ax;a>1

負對數函數 −logax;a>1,x>0−logax;a>1,x>0

開口向上的二次函數等

凸函數的判定：

如果f是一階可導，對于任意資料域内的x,y滿足 f(y)≥f(x)+f′(x)(y−x)f(y)≥f(x)+f′(x)(y−x)

如果f是二階可導，

凸優化應用舉例

SVM：其中由max|w|max|w| 轉向min(12∗|w|2)min(12∗|w|2)

最小二乘法？

LR的損失函數∑(yi∗log(hw(xi))+(1−yi)∗(log(1−hw(xi))))∑(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]. 《統計學習方法》.李航

AI算法統計與彙總樸素貝葉斯邏輯回歸和線性回歸KNN算法SVM、SMO決策樹随機森林RFGBDTBP最小二乘法EMBaggingBoosting凸優化參考

樸素貝葉斯

工作原理

工作流程

準備階段

訓練階段

應用階段

屬性特征

遇到特征之間不獨立問題

優缺點

邏輯回歸和線性回歸

梯度下降法

其他優化方法

關于LR的過拟合問題

關于LR的多分類：softmax

關于softmax和k個LR的選擇

優缺點

KNN算法

三要素

k值的選擇

KNN的回歸

優缺點：

KD樹

構造KD樹

KD樹的搜尋

KD樹進行KNN查找

KD樹搜尋的複雜度

SVM、SMO

線性SVM問題

對偶求解

損失函數

為什麼要引入對偶算法

核函數

SVM優缺點

SMO

SVM多分類問題

決策樹

ID3

關于損失函數

C4.5

Cart

回歸樹

停止條件

關于特征與目标值

決策樹的分類與回歸

理想的決策樹

解決決策樹的過拟合

優缺點

随機森林RF

學習過程

預測過程

參數問題

泛化誤差估計

學習算法

關于CART

優缺點

GBDT

Shrinkage

調參

優缺點：

BP

最小二乘法

EM

Bagging

Boosting

凸優化

凸集

凸函數

凸優化應用舉例

參考

繼續閱讀