簡(jiǎn)介
C4.5是決策樹(shù)算法的一種。決策樹(shù)算法作為一種分類(lèi)算法，目標就是將具有p維特征的n個(gè)樣本分到c個(gè)類(lèi)別中去。常見(jiàn)的決策樹(shù)算法有ID3,C4.5,CART。
基本思想
下面以一個(gè)例子來(lái)詳細說(shuō)明C4.5的基本思想
上述數據集有四個(gè)屬性，屬性集合A={ 天氣，溫度，濕度，風(fēng)速}， 類(lèi)別標簽有兩個(gè)，類(lèi)別集合L={進(jìn)行，取消}。
1. 計算類(lèi)別信息熵
類(lèi)別信息熵表示的是所有樣本中各種類(lèi)別出現的不確定性之和。根據熵的概念，熵越大，不確定性就越大，把事情搞清楚所需要的信息量就越多。
2. 計算每個(gè)屬性的信息熵
每個(gè)屬性的信息熵相當于一種條件熵。他表示的是在某種屬性的條件下，各種類(lèi)別出現的不確定性之和。屬性的信息熵越大，表示這個(gè)屬性中擁有的樣本類(lèi)別越不“純”。
3. 計算信息增益
信息增益的 = 熵 - 條件熵，在這里就是 類(lèi)別信息熵 - 屬性信息熵，它表示的是信息不確定性減少的程度。如果一個(gè)屬性的信息增益越大，就表示用這個(gè)屬性進(jìn)行樣本劃分可以更好的減少劃分后樣本的不確定性，當然，選擇該屬性就可以更快更好地完成我們的分類(lèi)目標。
信息增益就是ID3算法的特征選擇指標。
但是我們假設這樣的情況，每個(gè)屬性中每種類(lèi)別都只有一個(gè)樣本，那這樣屬性信息熵就等于零，根據信息增益就無(wú)法選擇出有效分類(lèi)特征。所以，C4.5選擇使用信息增益率對ID3進(jìn)行改進(jìn)。
4.計算屬性分裂信息度量
用分裂信息度量來(lái)考慮某種屬性進(jìn)行分裂時(shí)分支的數量信息和尺寸信息，我們把這些信息稱(chēng)為屬性的內在信息(instrisic information)。信息增益率用信息增益 / 內在信息，會(huì )導致屬性的重要性隨著(zhù)內在信息的增大而減小(也就是說(shuō)，如果這個(gè)屬性本身不確定性就很大，那我就越不傾向于選取它)，這樣算是對單純用信息增益有所補償。
5. 計算信息增益率
(下面寫(xiě)錯了。。應該是IGR = Gain / H )
天氣的信息增益率最高，選擇天氣為分裂屬性。發(fā)現分裂了之后，天氣是“陰”的條件下，類(lèi)別是”純“的，所以把它定義為葉子節點(diǎn)，選擇不“純”的結點(diǎn)繼續分裂。
在子結點(diǎn)當中重復過(guò)程1~5。
至此，這個(gè)數據集上C4.5的計算過(guò)程就算完成了，一棵樹(shù)也構建出來(lái)了。
總結算法流程為：
優(yōu)缺點(diǎn)
優(yōu)點(diǎn)
產(chǎn)生的分類(lèi)規則易于理解，準確率較高。
缺點(diǎn)
在構造樹(shù)的過(guò)程中，需要對數據集進(jìn)行多次的順序掃描和排序，因而導致算法的低效。
代碼
代碼已在github上實(shí)現，這里也貼出來(lái)
測試數據集為MNIST數據集，獲取地址為train.csv
運行結果
