數(shù)據(jù)挖掘十大經(jīng)典算法如下：

簡介

C4.5是決策樹算法的一種。決策樹算法作為一種分類算法，目標(biāo)就是將具有p維特征的n個(gè)樣本分到c個(gè)類別中去。常見的決策樹算法有ID3,C4.5,CART。

基本思想

下面以一個(gè)例子來詳細(xì)說明C4.5的基本思想

上述數(shù)據(jù)集有四個(gè)屬性，屬性集合A={ 天氣，溫度，濕度，風(fēng)速}， 類別標(biāo)簽有兩個(gè)，類別集合L={進(jìn)行，取消}。

1. 計(jì)算類別信息熵

類別信息熵表示的是所有樣本中各種類別出現(xiàn)的不確定性之和。根據(jù)熵的概念，熵越大，不確定性就越大，把事情搞清楚所需要的信息量就越多。

2. 計(jì)算每個(gè)屬性的信息熵

每個(gè)屬性的信息熵相當(dāng)于一種條件熵。他表示的是在某種屬性的條件下，各種類別出現(xiàn)的不確定性之和。屬性的信息熵越大，表示這個(gè)屬性中擁有的樣本類別越不“純”。

3. 計(jì)算信息增益

信息增益的 = 熵 - 條件熵，在這里就是 類別信息熵 - 屬性信息熵，它表示的是信息不確定性減少的程度。如果一個(gè)屬性的信息增益越大，就表示用這個(gè)屬性進(jìn)行樣本劃分可以更好的減少劃分后樣本的不確定性，當(dāng)然，選擇該屬性就可以更快更好地完成我們的分類目標(biāo)。

信息增益就是ID3算法的特征選擇指標(biāo)。

但是我們假設(shè)這樣的情況，每個(gè)屬性中每種類別都只有一個(gè)樣本，那這樣屬性信息熵就等于零，根據(jù)信息增益就無法選擇出有效分類特征。所以，C4.5選擇使用信息增益率對ID3進(jìn)行改進(jìn)。

4.計(jì)算屬性分裂信息度量

用分裂信息度量來考慮某種屬性進(jìn)行分裂時(shí)分支的數(shù)量信息和尺寸信息，我們把這些信息稱為屬性的內(nèi)在信息(instrisic information)。信息增益率用信息增益 / 內(nèi)在信息，會(huì)導(dǎo)致屬性的重要性隨著內(nèi)在信息的增大而減小(也就是說，如果這個(gè)屬性本身不確定性就很大，那我就越不傾向于選取它)，這樣算是對單純用信息增益有所補(bǔ)償。

5. 計(jì)算信息增益率

(下面寫錯(cuò)了。。應(yīng)該是IGR = Gain / H )

天氣的信息增益率最高，選擇天氣為分裂屬性。發(fā)現(xiàn)分裂了之后，天氣是“陰”的條件下，類別是”純“的，所以把它定義為葉子節(jié)點(diǎn)，選擇不“純”的結(jié)點(diǎn)繼續(xù)分裂。

在子結(jié)點(diǎn)當(dāng)中重復(fù)過程1~5。

至此，這個(gè)數(shù)據(jù)集上C4.5的計(jì)算過程就算完成了，一棵樹也構(gòu)建出來了。

總結(jié)算法流程為：

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)

產(chǎn)生的分類規(guī)則易于理解，準(zhǔn)確率較高。

缺點(diǎn)

在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效。

代碼

代碼已在github上實(shí)現(xiàn)，這里也貼出來

測試數(shù)據(jù)集為MNIST數(shù)據(jù)集，獲取地址為train.csv

運(yùn)行結(jié)果