？女兒:妳多大了？
？母親:26。
？女兒:妳帥嗎？
？母親:很帥。
？女兒:收入高嗎？
？母親:不是很高，但是中等。
？女兒:是公務員嗎？
？母親:是的，我在稅務局工作。
？女兒:好的，我去見見他。
？這個女生的決策過程是典型的分類樹決策。相當於把男人按照年齡、長相、收入、是否是公務員分為兩類:見與不見。假設女生對男性的要求是:30歲以下，相貌中等以上，高收入或中等收入以上的公務員。圖1是女生的決策邏輯。
如果妳是女生，妳會優先考慮哪個條件:長相？收入？還是年齡。在考慮年齡條件時，以25歲為分界點，或者以35歲為分界點。條件那麽多，先用哪個條件特征做if，後用哪個條件特征做if？以及如何確定特征中的哪個值作為劃分的標準。這是決策樹機器學習算法的關鍵。
首先，我們需要熟悉信息論中熵的概念。熵衡量事物的不確定性。事物越不確定，其熵就越大。具體地，隨機變量x的熵的表達式如下:
如果扔硬幣是壹個事件，，，
擲骰子作為壹個事件，
顯然，擲骰子的不確定性高於擲硬幣。？
熟悉單個變量的熵，很容易推廣到多個變量的聯合熵。這裏給出兩個變量X和Y的聯合熵表達式:
有了聯合熵，我們就可以得到條件熵的表達式H(X|Y ),類似於條件概率，它度量的是我們知道Y之後X剩余的不確定性，表達式:
我們剛剛提到了測量的不確定性，條件熵測量的是我們知道它之後剩余的不確定性。那又怎麽樣？它衡量的是知道後不確定性降低的程度。這個測度在信息論中稱為互信息，記為。
信息熵、聯合熵、條件熵和互信息之間的關系如圖2所示:
在決策樹的ID3算法中，互信息稱為信息增益。ID3算法是利用信息增益來判斷當前節點應該使用什麽特征來構建決策樹。信息增益越大，越適合分類。
下面，我們以SNS社區的虛假賬號檢測為例，來說明如何使用ID3算法構建決策樹。為簡單起見，我們假設訓練集包含10個元素:
設L，F，H，D代表日誌密度，好友密度，是否使用真實頭像，賬號是否真實。計算每個屬性的信息增益，如下所示:
因此對數密度的信息增益為0.276。用同樣的方法得到的H和F的信息增益分別為0.033和0.553。因為F具有最大的信息增益，所以第壹個破壞性選擇F被拆分，拆分結果如圖3所示:
在上圖的基礎上，遞歸地使用該方法計算子節點的分裂屬性，最終可以得到整個決策樹。
但是ID3算法仍然存在壹些缺點:
1.ID3不考慮連續的特征，比如長度和密度都是連續的值，所以不能用在ID3中。這大大限制了ID3的使用。
2.ID3首先采用信息增益大的特征建立決策樹的節點。人們很快發現，在相同的條件下，值多的要素比值少的要素獲得更多的信息。例如，壹個變量有兩個值，每個值都是0，另壹個變量有三個值，每個值都是0。其實都是完全不確定的變量，只是取三個值的信息增益大於取兩個值。(給定條件後信息增益所反映的不確定性降低的程度壹定是數據集越細，信息增益越大。)河流修正呢？為了解決這些問題，我們有了壹個C4.5算法。
對於第壹個問題，我們無法處理連續的特征，C4.5的思路是將連續的特征離散化。比如有m個樣本的m個連續特征A，從小到大排列。然後C4.5取相鄰兩個樣本值的平均值，壹個* * *得到m-1個劃分點，其中第I個劃分點表示為:對於這m-1個點，分別計算該點作為二元分類點時的信息增益。選擇信息增益最大的點作為連續特征的二元離散分類點。比如增益最大的點是，大於類別1，小於類別2。這樣，我們可以將連續的特征離散化。
對於第二個問題，信息增益作為壹個標準，往往偏向於值多的特征。C4.5提出了信息增益比:
即特征對數據集的信息增益與特征信息熵的比值，信息增益比越大，分類效果越好。壹個特征中的值種類越多，對應於該特征的特征熵就越大。作為分母，它可以糾正信息增益帶來的問題。
回到上面的例子:
？
也有:？, 。
因為F的信息增益比最大，所以第壹個破壞性選擇F被拆分，拆分結果如圖3所示。
然後遞歸地使用這種方法計算子節點的分裂屬性，最後可以得到整個決策樹。
看了上面的材料，我們知道在ID3算法中，我們使用信息增益來選擇特征，優先選擇信息增益大的特征。在C4.5算法中，使用信息增益比來選擇特征，以減少信息增益容易選擇多種特征值的特征的問題。但是ID3和C4.5都是基於信息論的熵模型，會涉及大量的對數運算。我們能否在不完全喪失熵模型優勢的情況下簡化模型？是啊！CART分類樹算法用基尼系數代替信息增益率。基尼系數代表模型的雜質。基尼系數越小，雜質越低，特征越好。這是信息增益的反義詞。
在分類問題中，假設有類別，第壹類的概率為，基尼系數為:
對於給定的樣本，假設有類別，且第壹類的數量為，則該樣本的基尼系數為:
特別是對於樣本D，如果按照特征A的某個值A將D劃分為D1和D2，那麽在特征A的條件下，D的基尼系數為:
回到上面的例子:
同理:，
因為L的基尼系數最小，所以第壹個破壞性選擇L是分裂的。
然後遞歸地使用這種方法計算子節點的分裂屬性，最後可以得到整個決策樹。
朋友們，如果覺得文章還可以，請點贊！！同時，妳能評論壹下文章有什麽問題嗎？謝謝大家！