一句話解釋ID3\C4.5算法

ID3\C4.5算法

ID3算法

ID3算法，ID的意思是 Iteritive Dichotomiser(疊代二分類器)。

它的基本原理是對所有特征求資訊增益，選出資訊增益最大的特征，按照該特征對資料進行分組 D 1 , D 2 D_1, D_2 D1​,D2​（二分類，是以分了兩組），然後，如果每組中所有的樣本都屬于同一類，則建立該節點為葉子節點；否則，遞歸上面的步驟，一直到所有節點都為葉子節點結束遞歸。

C4.5算法

C4.5(Classifier4.5) 算法是對 ID3 算法的改進，就是将 ID3中的資訊增益改為求資訊增益比。

名詞解釋

資訊增益：

特征 A 對訓練資料集D的資訊增益g(D,A)，定位集合D的經驗熵H(D)與特征A給定條件下D的經驗條件熵H(D|A)之差，即：

g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A) = H(D) - H(D | A) g(D,A)=H(D)−H(D∣A)

資訊增益比：

特征A對訓練資料集D的資訊增益比 g R ( D , A ) g_R(D, A) gR​(D,A) 定義為其資訊增益 g(D, A) 與訓練資料集 D關于特征A的值的熵 H A ( D ) H_A(D) HA​(D)之比，即：

g R ( D , A ) = g ( D , A ) H A ( D ) g_R(D, A) = \frac{g(D, A)}{H_A(D)} gR​(D,A)=HA​(D)g(D,A)​

其中， H A ( D ) = − ∑ i = 1 n ∣ D i ∣ ∣ D ∣ l o g 2 ∣ D i ∣ D H_A(D) = -\sum_{i=1}^n \frac{|D_i|}{|D|}log_2 \frac{|D_i|}{D} HA​(D)=−∑i=1n​∣D∣∣Di​∣​log2​D∣Di​∣​，n是特征A取值的個數。