C4.5決策樹

? (2011-10-20 23:22:19) 轉(zhuǎn)載▼

標簽：? 分類樹 ? 決策樹 ? c4.5 ? 機器學習 ? 數(shù)據(jù)挖掘 ?

分類：?數(shù)據(jù)挖掘

1. 算法背景介紹

分類樹（決策樹）是一種十分常用的分類方法。他是一種監(jiān)管學習，所謂監(jiān)管學習說白了很簡單，就是給定一堆樣本，每個樣本都有一組屬性和一個類別，這些類別是事先確定的，那么通過學習得到一個分類器，這個分類器能夠?qū)π鲁霈F(xiàn)的對象給出正確的分類。這樣的機器學習就被稱之為監(jiān)督學習。分類本質(zhì)上就是一個map的過程。C4.5分類樹就是決策樹算法中最流行的一種。下面給出一個數(shù)據(jù)集作為算法例子的基礎，比如有這么一個數(shù)據(jù)集，如下：

這個Golf數(shù)據(jù)集就是我們這篇博客討論的基礎。我們分類的目的就是根據(jù)某一天的天氣狀態(tài)，如天氣，溫度，濕度，是否刮風，來判斷這一天是否適合打高爾夫球。

2. 算法描述

確切的說，C4.5不是單個的算法，而是一套算法，C4.5有許多的功能，每個功能都對應著一個算法，這些功能組合起來就形成了一套算法就是C4.5。C4.5分類樹構造算法框架如下圖：

Figure 1

該算法的框架表述還是比較清晰的，從根節(jié)點開始不斷得分治，遞歸，生長，直至得到最后的結果。根節(jié)點代表整個訓練樣本集,通過在每個節(jié)點對某個屬性的測試驗證,算法遞歸得將數(shù)據(jù)集分成更小的數(shù)據(jù)集.某一節(jié)點對應的子樹對應著原數(shù)據(jù)集中滿足某一屬性測試的部分數(shù)據(jù)集.這個遞歸過程一直進行下去,直到某一節(jié)點對應的子樹對應的數(shù)據(jù)集都屬于同一個類為止.Golf數(shù)據(jù)集對應得到的決策樹如下:

Figure 1給出了C4.5分類樹構造算法的框架，一些細節(jié)并沒有闡述。下面就來具體分析一下里面可能面對的問題：

分類樹中的測試是怎樣的？

分類樹中的測試是針對某一個樣本屬性進行的測試。我們知道，樣本的屬性有兩種，一種是離散變量，一種是連續(xù)變量。對于離散變量，這很簡單，離散變量對應著多個值，每個值就對應著測試的一個分支，測試就是驗證樣本對應的屬性值對應哪個分支。這樣數(shù)據(jù)集就會被分成幾個小組。對于連續(xù)變量，所有連續(xù)變量的測試分支都是2條，其測試分支分別對應著，對應著分支閾值，后面我們來討論這個分支閾值如何選擇。

如何選擇測試？

分類樹中每個節(jié)點對應著測試，但是這些測試是如何來選擇呢？C4.5根據(jù)信息論標準來選擇測試，比如增益（在信息論中，熵對應著某一分布的信息量，其值同時也對應著要完全無損表示該分布所需要的最小的比特數(shù)，本質(zhì)上熵對應著不確定性，可能的變化的豐富程度。所謂增益，就是指在應用了某一測試之后，其對應的可能性豐富程度下降，不確定性減小，這個減小的幅度就是增益，其實質(zhì)上對應著分類帶來的好處）或者增益比（這個指標實際上就等于增益/熵，之所以采用這個指標是為了克服采用增益作為衡量標準的缺點，采用增益作為衡量標準會導致分類樹傾向于優(yōu)先選擇那些具有比較多的分支的測試，這種傾向需要被抑制）。算法在進行Tree-Growth時，總是“貪婪得”選擇那些信息論標準最高的那些測試。

如何選擇連續(xù)變量的閾值？

在《分類樹中的測試是怎樣的？》中提到連續(xù)變量的分支的閾值點為，這閾值如何確定呢？很簡單，把需要處理的樣本（對應根節(jié)點）或樣本子集（對應子樹）按照連續(xù)變量的大小從小到大進行排序，假設該屬性對應的不同的屬性值一共有N個，那么總共有N-1個可能的候選分割閾值點，每個候選的分割閾值點的值為上述排序后的屬性值鏈表中兩兩前后連續(xù)元素的中點，那么我們的任務就是從這個N-1個候選分割閾值點中選出一個，使得前面提到的信息論標準最大。舉個例子，對于Golf數(shù)據(jù)集，我們來處理溫度屬性，來選擇合適的閾值。首先按照溫度大小對對應樣本進行排序如下

那么可以看到有13個可能的候選閾值點，比如middle[64,65], middle[65,68]….,middle[83,85]。那么最優(yōu)的閾值該選多少呢？應該是middle[71,72]，如上圖中紅線所示。為什么呢？如下計算：

通過上述計算方式，0.939是最大的，因此測試的增益是最小的。（測試的增益和測試后的熵是成反比的，這個從后面的公式可以很清楚的看到）。根據(jù)上面的描述，我們需要對每個候選分割閾值進行增益或熵的計算才能得到最優(yōu)的閾值，我們需要算N-1次增益或熵（對應溫度這個變量而言就是13次計算）。能否有所改進呢？少算幾次，加快速度。答案是可以該進，如下圖

該圖中的綠線代表可能的最優(yōu)分割閾值點，根據(jù)信息論知識，像middle[72,75]（紅線所示）這個分割點，72,75屬于同一個類，這樣的分割點是不可能有信息增益的。（把同一個類分成了不同的類，這樣的閾值點顯然不會有信息增益，因為這樣的分類沒能幫上忙，減少可能性）

Tree-Growth如何終止?

前面提到Tree-Growth實際上是一個遞歸過程,那么這個遞歸什么時候到達終止條件退出遞歸呢?有兩種方式,第一種方式是如果某一節(jié)點的分支所覆蓋的樣本都屬于同一類的時候,那么遞歸就可以終止,該分支就會產(chǎn)生一個葉子節(jié)點.還有一種方式就是，如果某一分支覆蓋的樣本的個數(shù)如果小于一個閾值，那么也可產(chǎn)生葉子節(jié)點，從而終止Tree-Growth。

如何確定葉子節(jié)點的類？

前面提到Tree-Growth終止的方式有2種，對于第一種方式，葉子節(jié)點覆蓋的樣本都屬于同一類，那么這種情況下葉子節(jié)點的類自然不必多言。對于第二種方式，葉子節(jié)點覆蓋的樣本未必屬于同一類，直接一點的方法就是，該葉子節(jié)點所覆蓋的樣本哪個類占大多數(shù)，那么該葉子節(jié)點的類別就是那個占大多數(shù)的類。

前面《如何選擇測試？》提到測試的選擇是依據(jù)信息論標準，信息論標準有兩種，一種是增益，一種是增益比。首先來看看增益Gain的計算。假設隨機變量x，它可能屬于c個類中的任何一個，通過樣本的統(tǒng)計，它分別屬于各個類的概率分別為，那么要想把某一樣本進行歸類所需要的熵就為

公式1

對于Golf數(shù)據(jù)集，{PlayGolf？}的熵根據(jù)上述公式，就是

上述公式的值為0.940。它的信息論含義就是我要想把PlayGolf？這個信息傳遞給別人話，平均來講我至少需要0.940個bit來傳遞這個信息。C4.5的目標就是經(jīng)過分類來減小這個熵。那么我們來依次考慮各個屬性測試，通過某一屬性測試我們將樣本分成了幾個子集，這使得樣本逐漸變得有序，那么熵肯定變小了。這個熵的減小量就是我們選擇屬性測試的依據(jù)。還是以Golf數(shù)據(jù)集為例，Outlook的增益Gain(Outlook),其公式如下：

它的實質(zhì)是把數(shù)據(jù)集D根據(jù)某一屬性測試分成v個子集，這使得數(shù)據(jù)集D變得有序，使得數(shù)據(jù)集D的熵變小了。分組后的熵其實就是各個子集的熵的權重和。通過計算我們得到Gain(Outlook)=0.940-0.694=0.246，Gain(Windy)=0.940-0.892=0.048….

可以得到第一個測試屬性是Outlook。需要注意的是，屬性測試是從數(shù)據(jù)集中包含的所有屬性組成的候選屬性中選擇出來的。對于所在節(jié)點到根節(jié)點的路徑上所包含的屬性（我們稱之為繼承屬性），其實根據(jù)公式很容易得到他們的熵增益是0，因此這些繼承屬性完全不必考慮，可以從候選屬性中剔除這些屬性。

到這里似乎一切都很完美，增益這個指標非常得make sense，但是其實增益這個指標有一個缺點。我們來考慮Golf數(shù)據(jù)集中的Day這個屬性（我們假設它是一個真屬性，實際上很可能大家不會把他當做屬性），Day有14個不同的值，那么Day的屬性測試節(jié)點就會有14個分支，很顯然每個分支其實都覆蓋了一個“純”數(shù)據(jù)集（所謂“純”，指的就是所覆蓋的數(shù)據(jù)集都屬于同一個類），那么其熵增益顯然就是最大的，那么Day就默認得作為第一個屬性。之所以出現(xiàn)這樣的情況，是因為增益這個指標天然得偏向于選擇那些分支比較多的屬性，也就是那些具有的值比較多的那些屬性。這種偏向性使我們希望克服的，我們希望公正地評價所有的屬性。因此又一個指標被提出來了Gain Ratio-增益比。某一屬性A的增益比計算公式如下：

Gain(A)就是前面計算的增益，而SplitInfo(A)計算如下：

公式2

與公式1進行比較，你會發(fā)現(xiàn)，SplitInfo(A)實際上就是屬性A的熵，只不過這個熵有所不同，他不是樣本最終分類{PlayGolf？}的熵，而是對應屬性分組{A?}的熵，它反映的是屬性A本身的信息量。通過計算我們很容易得到GainRatio(Outlook)=0.246/1.577=0.156。增益比實際上就是對增益進行了歸一化，這樣就避免了指標偏向分支多的屬性的傾向。

通過上述方法得到了決策樹，這一切看起來都很完美，但是這還不夠。決策樹能夠幫助我們對新出現(xiàn)的樣本進行分類，但還有一些問題它不能很好得解決。比如我們想知道對于最終的分類，哪個屬性的貢獻更大？能否用一種比較簡潔的規(guī)則來區(qū)分樣本屬于哪個類？等等。為了解決這些問題，基于產(chǎn)生的決策樹，各位大牛們又提出了一些新的方法。

3. C4.5的功能

3.1 決策樹的剪枝

決策樹為什么要剪枝？原因就是避免決策樹“過擬合”樣本。前面的算法生成的決策樹非常的詳細而龐大，每個屬性都被詳細地加以考慮，決策樹的樹葉節(jié)點所覆蓋的訓練樣本都是“純”的。因此用這個決策樹來對訓練樣本進行分類的話，你會發(fā)現(xiàn)對于訓練樣本而言，這個樹表現(xiàn)堪稱完美，它可以100%完美正確得對訓練樣本集中的樣本進行分類（因為決策樹本身就是100%完美擬合訓練樣本的產(chǎn)物）。但是，這會帶來一個問題，如果訓練樣本中包含了一些錯誤，按照前面的算法，這些錯誤也會100%一點不留得被決策樹學習了，這就是“過擬合”。C4.5的締造者昆蘭教授很早就發(fā)現(xiàn)了這個問題，他作過一個試驗，在某一個數(shù)據(jù)集中，過擬合的決策樹的錯誤率比一個經(jīng)過簡化了的決策樹的錯誤率要高。那么現(xiàn)在的問題就來了，如何在原生的過擬合決策樹的基礎上，通過剪枝生成一個簡化了的決策樹？

第一種方法，也是最簡單的方法，稱之為基于誤判的剪枝。這個思路很直接，完全的決策樹不是過度擬合么，我再搞一個測試數(shù)據(jù)集來糾正它。對于完全決策樹中的每一個非葉子節(jié)點的子樹，我們嘗試著把它替換成一個葉子節(jié)點，該葉子節(jié)點的類別我們用子樹所覆蓋訓練樣本中存在最多的那個類來代替，這樣就產(chǎn)生了一個簡化決策樹，然后比較這兩個決策樹在測試數(shù)據(jù)集中的表現(xiàn)，如果簡化決策樹在測試數(shù)據(jù)集中的錯誤比較少，并且該子樹里面沒有包含另外一個具有類似特性的子樹（所謂類似的特性，指的就是把子樹替換成葉子節(jié)點后，其測試數(shù)據(jù)集誤判率降低的特性），那么該子樹就可以替換成葉子節(jié)點。該算法以bottom-up的方式遍歷所有的子樹，直至沒有任何子樹可以替換使得測試數(shù)據(jù)集的表現(xiàn)得以改進時，算法就可以終止。

第一種方法很直接，但是需要一個額外的測試數(shù)據(jù)集，能不能不要這個額外的數(shù)據(jù)集呢？為了解決這個問題，于是就提出了悲觀剪枝。該方法剪枝的依據(jù)是訓練樣本集中的樣本誤判率。我們知道一顆分類樹的每個節(jié)點都覆蓋了一個樣本集，根據(jù)算法這些被覆蓋的樣本集往往都有一定的誤判率，因為如果節(jié)點覆蓋的樣本集的個數(shù)小于一定的閾值，那么這個節(jié)點就會變成葉子節(jié)點，所以葉子節(jié)點會有一定的誤判率。而每個節(jié)點都會包含至少一個的葉子節(jié)點，所以每個節(jié)點也都會有一定的誤判率。悲觀剪枝就是遞歸得估算每個內(nèi)部節(jié)點所覆蓋樣本節(jié)點的誤判率。剪枝后該內(nèi)部節(jié)點會變成一個葉子節(jié)點，該葉子節(jié)點的類別為原內(nèi)部節(jié)點的最優(yōu)葉子節(jié)點所決定。然后比較剪枝前后該節(jié)點的錯誤率來決定是否進行剪枝。該方法和前面提到的第一種方法思路是一致的，不同之處在于如何估計剪枝前分類樹內(nèi)部節(jié)點的錯誤率。

悲觀剪枝的思路非常巧妙。把一顆子樹（具有多個葉子節(jié)點）的分類用一個葉子節(jié)點來替代的話，誤判率肯定是上升的（這是很顯然的，同樣的樣本子集，如果用子樹分類可以分成多個類，而用單顆葉子節(jié)點來分的話只能分成一個類，多個類肯定要準確一些）。于是我們需要把子樹的誤判計算加上一個經(jīng)驗性的懲罰因子。對于一顆葉子節(jié)點，它覆蓋了N個樣本，其中有E個錯誤，那么該葉子節(jié)點的錯誤率為（E+0.5）/N。這個0.5就是懲罰因子，那么一顆子樹，它有L個葉子節(jié)點，那么該子樹的誤判率估計為。這樣的話，我們可以看到一顆子樹雖然具有多個子節(jié)點，但由于加上了懲罰因子，所以子樹的誤判率計算未必占到便宜。剪枝后內(nèi)部節(jié)點變成了葉子節(jié)點，其誤判個數(shù)J也需要加上一個懲罰因子，變成J+0.5。那么子樹是否可以被剪枝就取決于剪枝后的錯誤J+0.5在的標準誤差內(nèi)。

對于樣本的誤差率e，我們可以根據(jù)經(jīng)驗把它估計成各種各樣的分布模型，比如是二項式分布，比如是正態(tài)分布。我們以二項式分布為例，啰嗦幾句來分析一下。什么是二項分布，在n次獨立重復試驗中，設事件A發(fā)生的次數(shù)為X，如果每次試驗中中事件A發(fā)生的概率是p，那么在n次獨立重復試驗中，事件A恰好發(fā)生k次的概率是

其概率期望值為np，方差為np(1-p)。比如投骰子就是典型的二項分布，投骰子10次，擲得4點的次數(shù)就服從n=10，p=1/6的二項分布。

如果二項分布中n=1時，也就是只統(tǒng)計一次，事件A只可能有兩種取值1或0，那么事件A的值所代表的分布就是伯努利分布。B(1,p)~f(1;1,p)就是伯努利分布，伯努利分布式是二項分布的一種特殊形式。比如投硬幣，正面值為1，負面值為0，那么硬幣為正面的概率為p=0.5，該硬幣值就服從概率為0.5的伯努利分布。

當n趨于無限大時，二項式分布就正態(tài)分布，如下圖。

那么一棵樹錯誤分類一個樣本值為1，正確分類一個樣本值為0，該樹錯誤分類的概率（誤判率）為e（e為分布的固有屬性,可以通過統(tǒng)計出來），那么樹的誤判次數(shù)就是伯努利分布，我們可以估計出該樹的誤判次數(shù)均值和方差：

把子樹替換成葉子節(jié)點后，該葉子的誤判次數(shù)也是一個伯努利分布，其概率誤判率e為(E+0.5)/N，因此葉子節(jié)點的誤判次數(shù)均值為

那么，如果子樹可以被葉子節(jié)點替代，它必須滿足下面的條件：

這個條件就是剪枝的標準。根據(jù)置信區(qū)間，我們設定一定的顯著性因子，我們可以估算出誤判次數(shù)的上下界。

誤判次數(shù)也可以被估計成一個正態(tài)分布，有興趣大家可以推導一下。

3.2 連續(xù)值屬性的改進

相對于那些離散值屬性，分類樹算法傾向于選擇那些連續(xù)值屬性，因為連續(xù)值屬性會有更多的分支，熵增益也最大。算法需要克服這種傾向。還記得前面講得如何克服分類樹算法傾向于離散值較多的離散屬性么？對了，我們利用增益率來克服這種傾向。增益率也可以用來克服連續(xù)值屬性傾向。增益率作為選擇屬性的依據(jù)克服連續(xù)值屬性傾向，這是沒有問題的。但是如果利用增益率來選擇連續(xù)值屬性的分界點，會導致一些副作用。分界點將樣本分成兩個部分，這兩個部分的樣本個數(shù)之比也會影響增益率。根據(jù)增益率公式，我們可以發(fā)現(xiàn)，當分界點能夠把樣本分成數(shù)量相等的兩個子集時（我們稱此時的分界點為等分分界點），增益率的抑制會被最大化，因此等分分界點被過分抑制了。子集樣本個數(shù)能夠影響分界點，顯然不合理。因此在決定分界點是還是采用增益這個指標，而選擇屬性的時候才使用增益率這個指標。這個改進能夠很好得抑制連續(xù)值屬性的傾向。當然還有其它方法也可以抑制這種傾向，比如MDL，有興趣的讀者可以自己閱讀相關文章。

3.3 處理缺失屬性

如果有些訓練樣本或者待分類樣本缺失了一些屬性值，那么該如何處理？要解決這個問題，需要考慮3個問題：i)當開始決定選擇哪個屬性用來進行分支時，如果有些訓練樣本缺失了某些屬性值時該怎么辦？ii)一個屬性已被選擇，那么在決定分支的時候如果有些樣本缺失了該屬性該如何處理？iii)當決策樹已經(jīng)生成，但待分類的樣本缺失了某些屬性，這些屬性該如何處理？針對這三個問題，昆蘭提出了一系列解決的思路和方法。

對于問題i),計算屬性a的增益或者增益率時，如果有些樣本沒有屬性a，那么可以有這么幾種處理方式：(I)忽略這些缺失屬性a的樣本。(C)給缺失屬性a的樣本賦予屬性a一個均值或者最常用的的值。(R)計算增益或者增益率時根據(jù)缺失屬性樣本個數(shù)所占的比率對增益/增益率進行相應的“打折”。(S)根據(jù)其他未知的屬性想辦法把這些樣本缺失的屬性補全。

對于問題ii)，當屬性a已經(jīng)被選擇，該對樣本進行分支的時候，如果有些樣本缺失了屬性a,那么：(I)忽略這些樣本。(C)把這些樣本的屬性a賦予一個均值或者最常出現(xiàn)的值，然后再對他們進行處理。(R)把這些屬性缺失樣本，按照具有屬性a的樣本被劃分成的子集樣本個數(shù)的相對比率，分配到各個子集中去。至于哪些缺失的樣本被劃分到子集1，哪些被劃分到子集2，這個沒有一定的準則，可以隨機而動。(A)把屬性缺失樣本分配給所有的子集，也就是說每個子集都有這些屬性缺失樣本。(U)單獨為屬性缺失的樣本劃分一個分支子集。(S)對于缺失屬性a的樣本，嘗試著根據(jù)其他屬性給他分配一個屬性a的值，然后繼續(xù)處理將其劃分到相應的子集。

對于問題iii)，對于一個缺失屬性a的待分類樣本，有這么幾種選擇：(U)如果有單獨的確實分支，依據(jù)此分支。(c)把待分類的樣本的屬性a值分配一個最常出現(xiàn)的a的屬性值，然后進行分支預測。(S)根據(jù)其他屬性為該待分類樣本填充一個屬性a值，然后進行分支處理。(F)在決策樹中屬性a節(jié)點的分支上，遍歷屬性a節(jié)點的所有分支，探索可能所有的分類結果，然后把這些分類結果結合起來一起考慮，按照概率決定一個分類。(H)待分類樣本在到達屬性a節(jié)點時就終止分類，然后根據(jù)此時a節(jié)點所覆蓋的葉子節(jié)點類別狀況為其分配一個發(fā)生概率最高的類。

3.4 推理規(guī)則

C4.5決策樹能夠根據(jù)決策樹生成一系列規(guī)則集,我們可以把一顆決策樹看成一系列規(guī)則的組合。一個規(guī)則對應著從根節(jié)點到葉子節(jié)點的路徑，該規(guī)則的條件是路徑上的條件，結果是葉子節(jié)點的類別。C4.5首先根據(jù)決策樹的每個葉子節(jié)點生成一個規(guī)則集，對于規(guī)則集中的每條規(guī)則，算法利用“爬山”搜索來嘗試是否有條件可以移除，由于移除一個條件和剪枝一個內(nèi)部節(jié)點本質(zhì)上是一樣的，因此前面提到的悲觀剪枝算法也被用在這里進行規(guī)則簡化。MDL準則在這里也可以用來衡量對規(guī)則進行編碼的信息量和對潛在的規(guī)則進行排序。簡化后的規(guī)則數(shù)目要遠遠小于決策樹的葉子節(jié)點數(shù)。根據(jù)簡化后的規(guī)則集是無法重構原來的決策樹的。規(guī)則集相比決策樹而言更具有可操作性，因此在很多情況下我們需要從決策樹中推理出規(guī)則集。C4.5有個缺點就是如果數(shù)據(jù)集增大了一點，那么學習時間會有一個迅速地增長。

4 可用的C4.5軟件包

C4.5決策樹算法如此

C4.5的原始實現(xiàn)可以從昆蘭教授的個人網(wǎng)頁http://www.rulequest.com/Personal/中得到，但這是c語言版本，而且這個版本不是免費的，你必須遵循他的商業(yè)許可證要求。開源的MLC++和Weka都有對C4.5的實現(xiàn)，你可以參考。另外也有一些商業(yè)版本的實現(xiàn)可供使用，比如ODBCMINE。

C4.5是一種早期的機器學習算法，在工業(yè)界也被廣泛使用。

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的C4.5决策树 此博文包含图片(2011-10-20 23:22:19)转载▼ 标签： 分类树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。