機器學習方法簡介（2）--決策樹、随機森林、樸素貝葉斯

1.決策樹

決策樹是一種用于對執行個體進行分類的樹形結構。

Hunt算法是一種采用局部最優政策的決策樹建構算法，它同時也是許多決策樹算法的基礎，包括ID3、C4.5和CART等。

Hunt算法的遞歸定義如下： 

(1) 如果 

中所有記錄都屬于同一個類，則 t 是葉結點，用 

标記。 

(2) 如果 

中包含屬于多個類的記錄，則選擇一個屬性測試條件（attribute test condition），将記錄劃分成較小的子集。對于測試條件的每個輸出，建立一個子女結點，并根據測試結果将 

中的記錄分布到子女結點中。然後，對于每個子女結點，遞歸地調用該算法。

需要附加的條件來處理以下的情況：

1. 算法的第二步所建立的子女結點可能為空，即不存在與這些結點相關聯的記錄。如果沒有一個訓練記錄包含與這樣的結點相關聯的屬性值組合，這種情形就可能發生。這時，該結點成為葉結點，類标号為其父結點上訓練記錄中的多數類。
2. 在第二步，如果與

   

   相關聯的所有記錄都具有相同的屬性值（目标屬性除外），則不可能進一步劃分這些記錄。在這種情況下，該結點為葉結點，其标号為與該結點相關聯的訓練記錄中的多數類。

在決策過程中，對于特征的選擇還是比較重要的。随機選擇顯然是不好的，是以，我們定義了資訊增益和資訊增益比兩個名額來指導特征選擇。

資訊熵的定義：

資訊增益的定義：

資訊增益率定義：

ID3算法應用了資訊增益來選擇特征 。

C4.5算法與上邊的ID3算法非常相似，唯一的不同是，ID3算法是用資訊增益來選擇特征，而C4.5算法使用資訊增益率來選擇特征。在使用資訊增益作為訓練資料集特征時會偏向于取值較多的特征，而用資訊增益率則避免了這一問題。

CART生成算法與C4.5算法相類似，它與C4.5算法的主要差別是使用基尼系數進行屬性選擇。

剪枝

作為決策樹中一種防止Overfitting過拟合的手段，分為預剪枝和後剪枝兩種。

預剪枝：當決策樹在生成時當達到該名額時就停止生長，比如小于一定的資訊擷取量或是一定的深度，就停止生長。

後剪枝：當決策樹生成完後，再進行剪枝操作。優點是克服了“視界局限”效應，但是計算量代價較大。

決策樹優點：

直覺，便于了解，在相對短的時間内能夠對大型資料源做出可行且效果良好的結果，能夠同時處理資料型和正常型屬性。

決策樹缺點：

可規模性一般，連續變量需要劃分成離散變量，容易過拟合。

2.随機森林（RF）

随機森林就是通過內建學習的思想将多棵樹內建的一種算法，它的基本單元是決策樹，而它的本質屬于機器學習的一大分支——內建學習（Ensemble Learning）方法。

随機森林中的每個決策樹獨立預測，然後對所有決策樹的預測結果進行投票，将若幹個弱分類器的分類結果進行投票選擇，進而組成一個強分類器，這就是随機森林bagging的思想。

特點：

1）在目前所有算法中，具有極好的準确率。

2）能夠有效地運作在大資料集上。

3）能夠處理具有高維特征的輸入樣本，而且不需要降維。

4）能夠評估各個特征在分類問題上的重要性。

5）在生成過程中，能夠擷取到内部生成誤差的一種無偏估計。

6）對于預設值問題也能夠獲得很好得結果。

每棵樹的按照如下規則生成：

1）如果訓練集大小為N，對于每棵樹而言，随機且有放回地從訓練集中的抽取N個訓練樣本（這種采樣方式稱為bootstrap sample方法），作為該樹的訓練集；

2）如果每個樣本的特征次元為M，指定一個常數m<<M，随機地從M個特征中選取m個特征子集，每次樹進行分裂時，從這m個特征中選擇最優的；

3）每棵樹都盡最大程度的生長，并且沒有剪枝過程。

随機森林分類效果（錯誤率）與兩個因素有關：

• 森林中任意兩棵樹的相關性：相關性越大，錯誤率越大；
• 森林中每棵樹的分類能力：每棵樹的分類能力越強，整個森林的錯誤率越低。

　　減小特征選擇個數m，樹的相關性和分類能力也會相應的降低；增大m，兩者也會随之增大。是以關鍵問題是如何選擇最優的m（或者是範圍），這也是随機森林唯一的一個參數。

3.樸素貝葉斯

基于機率論的分類算法，通過考慮特征機率來預測分類。

貝葉斯法則

假如我們有c0和c1兩個類，給定一個資料，它的特征為x1,x2,x3，我們求這個資料屬于哪個類。

首先我們需要求p（c0|x1,x2,x3）和p（c1|x1,x2,x3）哪個更大，如果p（c0|x1,x2,x3）更大，則該資料屬于c0類，反之屬于c1類。

但是p（c0|x1,x2,x3）不好求解，是以我們利用貝葉斯法則将其轉化為求解陪p（x1,x2,x3|c0）、p（c0）、p（x1,x2,x3）的問題。

引用《決策樹簡述》

引用《資料挖掘十大算法之決策樹詳解（1）》

引用《決策樹 (Decision Tree) 原理簡述及相關算法(ID3,C4.5)》

引用《随機森林（Random Forest）》

引用《帶你搞懂樸素貝葉斯分類算法》