決策樹是如何工作的

摘要: 決策樹演算法屬於監督學習演算法系列。與其他監督學習演算法不同，決策樹演算法也可用於求解關於回歸和分類問題。

作者：Rahul Saxena

譯者：java達人

來源：http://dataaspirant.com/2017/01/30/how-decision-tree-algorithm-works/

決策樹演算法屬於監督學習演算法系列。與其他監督學習演算法不同，決策樹演算法也可用於求解關於回歸和分類問題。

使用決策樹的目的通常是創建一個訓練模型，可以通過學習根據先驗數據（訓練數據）推導的決策規則，來預測目標變數的類別或數值。

與其他分類演算法相比，決策樹演算法是非常容易的。決策樹演算法嘗試通過使用樹表示來解決問題。樹的每個內部節點對應一個屬性，每個葉節點對應一個類標籤。

決策樹演算法偽碼

1. 將數據集的最優屬性放在樹的根節點。

2. 將訓練集分為子集。子集應以這樣一種方式組織：每個子集包含相同屬性值的數據。

3. 在每個子集上重複步驟1和步驟2，直到在樹的所有分支中都有葉節點。

在決策樹中，為了預測從根節點開始的記錄的類標籤。我們將根屬性的值與記錄的屬性值進行比較。在比較的基礎上，我們選擇與該值對應的分支，並跳轉到下一個節點。

我們繼續將我們的記錄的屬性值與樹的其他內部節點進行比較，直到我們到達預測類型值的葉節點。我們知道如何使用模型決策樹來預測目標類別或數值，現在讓我們了解如何創建決策樹模型。

創建決策樹時的假設

下面是我們使用決策樹時所做的一些假設：

一開始，整個訓練集被視為根節點。

特徵值更傾向於分類。如果這些值是連續的，那麼在構建模型之前，它們將被離散化。

記錄根據屬性值遞歸分布。

將屬性作為樹的根或內部節點的順序是通過使用統計方法完成的。

決策樹遵循Sum of Product（SOP）表述形式。對於上面的圖片，你可以看到我們如何通過從根節點到葉節點的遍歷預測我們是否接受新的工作機會或者是否每天使用電腦。

這就是Sum of Product。Sum of Product（SOP）也稱為析取範式(Disjunctive Normal Form)。對於一個類，從樹根到具有相同類的葉節點的每個分支都是值的合取(Product)，在該類中結束的不同分支構成了析取(Sum)。

決策樹實現中的主要挑戰是確定哪些屬性作為根節點以及每個級別的節點。處理這些需要知道屬性選擇。我們有不同的屬性選擇方法來識別這些屬性。

普遍的屬性選擇方法：

信息增益

基尼指數

屬性選擇

如果數據集由「n」個屬性組成，則決定在樹的根節點或不同級別放置哪個屬性作為內部節點是一個複雜的步驟。通過隨機選擇任意節點作為根，無法解決問題。如果我們遵循隨機的方法，它可能會給我們帶來準確性很低的結果。

為了解決這個屬性選擇問題，研究人員制定了一些解決方案。他們建議使用一些標準，如信息增益，基尼指數等。這些標準將計算每個屬性的值。值會被排序，並且按照順序將屬性放置在樹中，即大數值的屬性（在信息增益的情況下）被放置在根的位置。

當信息增益作為標準時，我們假設屬性是分類的，對於基尼係數，則假設屬性是連續的。

信息增益

當信息增益作為標準，我們嘗試估計每個屬性所包含的信息。我們使用信息理論中的一些知識點。

隨機變數X的隨機性或不確定性由熵定義。

對於二分類問題，只有兩個類，正負類。

如果所有的例子都是正的或全部是負的，則熵為0，也就是低。

如果一半的記錄是正，一半是負類，那麼熵是1，也就是高。

通過計算每個屬性的熵測度，我們可以計算其信息增益。信息增益計算了由於屬性排序而產生的熵的預期減少值。信息增益可以被計算出來。

為了清楚地了解信息增益和熵的計算，我們嘗試在樣本數據上作操作。

示例：以「信息增益」為標準構建決策樹

我們嘗試以信息增益為標準，使用這些數據樣本。在這裡，我們有5列數據，其中4列是連續數據，第5列由類標籤組成。

A，B，C，D屬性當作是預測變數，E列類標籤當作是目標變數。為了根據這些數據構建決策樹，我們必須將連續數據轉換為分類數據。

我們選擇了一些隨機值來對每個屬性進行分類：

1. 計算目標熵。計算每個屬性的信息增益有兩個步驟：

2. 需要計算每個屬性A，B，C，D的熵。使用信息增益公式，我們將從目標熵減去該熵，其結果就是信息增益。

目標熵：我們有8個負類型的記錄和8個正類型的記錄。所以我們可以直接估計目標熵為1。

使用公式計算熵：

E(8,8) = -1*( (p(+ve)*log( p(+ve)) + (p(-ve)*log( p(-ve)) )

= -1*( (8/16)*log2(8/16)) + (8/16) * log2(8/16) )

= 1

Var A的信息增益

Var A的16個記錄中，有12個記錄值>=5, 4個記錄的值

Var A >= 5 & class == positive: 5/12

Var A >= 5 & class == negative: 7/12

Entropy(5,7) = -1 * ( (5/12)*log2(5/12) + (7/12)*log2(7/12)) = 0.9799

Var A

Var A

Entropy(3,1) = -1 * ( (3/4)*log2(3/4) + (1/4)*log2(1/4)) = 0.81128

Entropy(Target, A) = P(>=5) * E(5,7) + P(

= (12/16) * 0.9799 + (4/16) * 0.81128 = 0.937745

Var B的信息增益

Var B16個記錄中,12個記錄的值> = 3，4個記錄值

Var B >= 3 & class == positive: 8/12

Var B >= 3 & class == negative: 4/12

Entropy(8,4) = -1 * ( (8/12)*log2(8/12) + (4/12)*log2(4/12)) = 0.39054

VarB

Var B

Entropy(0,4) = -1 * ( (0/4)*log2(0/4) + (4/4)*log2(4/4)) = 0

Entropy(Target, B) = P(>=3) * E(8,4) + P(

= (12/16) * 0.39054 + (4/16) * 0 = 0.292905

Var C的信息增益

Var C 16個記錄中的6個記錄值 = 4.2。

Var C >= 4.2 & class == positive: 0/6

Var C >= 4.2 & class == negative: 6/6

Entropy(0,6) = 0

VarC < 4.2 & class == positive: 8/10

Var C < 4.2 & class == negative: 2/10

Entropy(8,2) = 0.72193

Entropy(Target, C) = P(>=4.2) * E(0,6) + P(< 4.2) * E(8,2)

= (6/16) * 0 + (10/16) * 0.72193 = 0.4512

Var D的信息增益

Var D 16個記錄中的5個記錄值 = 1.4。

Var D >= 1.4 & class == positive: 0/5

Var D >= 1.4 & class == negative: 5/5

Entropy(0,5) = 0

Var D < 1.4 & class == positive: 8/11

Var D < 14 & class == negative: 3/11

Entropy(8,3) = -1 * ( (8/11)*log2(8/11) + (3/11)*log2(3/11)) = 0.84532

Entropy(Target, D) = P(>=1.4) * E(0,5) + P(< 1.4) * E(8,3)

= 5/16 * 0 + (11/16) * 0.84532 = 0.5811575

具有更高值的屬性應該作為根，並且熵0的分支應該被轉換為葉節點。熵大於0的分支需要進一步分解。根據上述信息增益計算，我們可以構建一個決策樹。我們應根據它們的值將屬性放在樹上。

基尼指數

基尼係數是衡量隨機選擇元素被錯誤識別的頻率的度量標準。這意味著應該優選具有較低gini指數的屬性。

示例：使用「gini index」作為標準構造決策樹

我們將使用與信息增益示例相同的數據樣本。我們試著用基尼係數作為標準。在這裡，我們有5列，其中4列具有連續數據，第5列由類標籤組成。

A，B，C，D屬性可以被認為是預測變數，E列類標籤可以被認為是目標變數。為了從這些數據構建決策樹，我們必須將連續數據轉換為分類數據。

我們選擇了一些隨機值來對每個屬性進行分類：

Var A的基尼指數

Var A16個記錄中的12個記錄值 = 5。

Var A >= 5 & class == positive: 5/12

Var A >= 5 & class == negative: 7/12

gini(5,7) = 1- ( (5/12)2 + (7/12)2 ) = 0.4860

Var A

Var A

gini(3,1) = 1- ( (3/4)2 + (1/4)2 ) = 0.375

將基尼指數加權匯總:

Var B的基尼指數

Var B16個記錄中的12個記錄值> = 3，4個記錄值

Var B >= 3 & class == positive: 8/12

Var B >= 3 & class == negative: 4/12

gini(8,4) = 1- ( (8/12)2 + (4/12)2 ) = 0.446

Var B

Var B

gin(0,4) = 1- ( (0/4)2 + (4/4)2 ) = 0

Var C的基尼指數

Var C16個記錄中的6個記錄值 = 4.2。

Var C >= 4.2 & class == positive: 0/6

Var C >= 4.2 & class == negative: 6/6

gini(0,6) = 1- ( (0/8)2 + (6/6)2 ) = 0

Var C < 4.2& class == positive: 8/10

Var C < 4.2 & class == negative: 2/10

gin(8,2) = 1- ( (8/10)2 + (2/10)2 ) = 0.32

Var D的基尼指數

Var D16個記錄中的5個記錄值 = 1.4。

Var D >= 1.4 & class == positive: 0/5

Var D >= 1.4 & class == negative: 5/5

gini(0,5) = 1- ( (0/5)2 + (5/5)2 ) = 0

Var D < 1.4 & class == positive: 8/11

Var D < 1.4 & class == negative: 3/11

gin(8,3) = 1- ( (8/11)2 + (3/11)2 ) = 0.397

過擬合

構建決策樹模型時，過擬合是一個實際問題。當演算法越來越深入以減少訓練集誤差時，測試集誤差卻會增加，我們的模型的預測精度會下降。它通常發生於由於異常值和數據不規則而構建多個分支的時候。

我們可以使用兩種方法來避免過擬合：

預修剪

後修剪

預先剪枝

預先剪枝，提前結束樹的構建。如果分裂節點的良好度低於閾值，則傾向於不分裂節點。但是要選擇一個合適的閥值是不容易的。

後剪枝

後剪枝中，先逐步構建一棵完整的樹。如果樹顯示了過擬合的問題，那麼剪枝是作為一個後剪枝步驟完成的。我們使用交叉驗證數據來檢查修剪的效果。通過使用交叉驗證數據，測試擴展節點是否會帶來改進。如果顯示會帶來改進，那麼我們可以繼續擴展該節點。但是，如果精度降低，則不應該擴展，節點應該轉換為葉節點。

決策樹演算法優點和缺點

優點：

決策樹很容易解釋。它產生一組規則。

它遵循的方法與人類平時做出決策時的方法相同的。

複雜決策樹模型的解釋可以通過可視化來簡化。即使門外漢也能夠理解其邏輯。

要調整的超參數的數量幾乎為零。

缺點：

決策樹中過擬合的概率很高。

相比於其他機器學習演算法，它對數據集預測精度較低。

帶有分類變數的決策樹對具有較大編號的類別得出的信息增益具有偏差。

當有很多類標籤時，計算可能變得複雜。

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！