數據挖掘學習筆記--決策樹C4.5
在網上和教材上也看了有很多數據挖掘方面的很多知識，自己也學習很多，就準備把自己學習和別人分享的結合去總結下，以備以后自己回頭看，看別人總還是比不上自己寫點，及時有些不懂或者是沒有必要。
定義：分類樹（決策樹）是一種十分常用的分類方法。他是一種監管學習，所謂監管學習說白了很簡單，就是給定一堆樣本，每個樣本都有一組屬性和一個類別，這些類別是事先確定的，那么通過學習得到一個分類器，這個分類器能夠對新出現的對象給出正確的分類。這樣的機器學習就被稱之為監督學習。分類本質上就是一個map的過程。C4.5分類樹就是決策樹算法中最流行的一種。
算法簡介：
Function C4.5(R:包含連續屬性的無類別屬性集合,C:類別屬性,S:訓練集) /*返回一棵決策樹*/ Begin If S為空,返回一個值為Failure的單個節點; If S是由相同類別屬性值的記錄組成, 返回一個帶有該值的單個節點; If R為空,則返回一個單節點,其值為在S的記錄中找出的頻率最高的類別屬性值; [注意未出現錯誤則意味著是不適合分類的記錄]； For 所有的屬性R(Ri) Do If 屬性Ri為連續屬性，則 Begin 將Ri的最小值賦給A1： 將Rm的最大值賦給Am；/*m值手工設置*/ For j From 2 To m-1 Do Aj=A1+j*(A1Am)/m; 將Ri點的基于{< =Aj,>Aj}的最大信息增益屬性(Ri,S)賦給A； End； 將R中屬性之間具有最大信息增益的屬性(D,S)賦給D; 將屬性D的值賦給{dj/j=1,2...m}； 將分別由對應于D的值為dj的記錄組成的S的子集賦給{sj/j=1,2...m}; 返回一棵樹，其根標記為D;樹枝標記為d1,d2...dm; 再分別構造以下樹: C4.5(R-{D},C,S1),C4.5(R-{D},C,S2)...C4.5(R-{D},C,Sm); End C4.5
該算法的框架表述還是比較清晰的，從根節點開始不斷得分治，遞歸，生長，直至得到最后的結果。根節點代表整個訓練樣本集,通過在每個節點對某個屬性的測試驗證,算法遞歸得將數據集分成更小的數據集.某一節點對應的子樹對應著原數據集中滿足某一屬性測試的部分數據集.這個遞歸過程一直進行下去,直到某一節點對應的子樹對應的數據集都屬于同一個類為止，例如數據集對應得到的決策樹如下:
分類樹中的測試是怎樣的？
分類樹中的測試是針對某一個樣本屬性進行的測試。樣本的屬性有兩種，一種是離散變量，一種是連續變量。對于離散變量，這很簡單，離散變量對應著多個值，每個值就對應著測試的一個分支，測試就是驗證樣本對應的屬性值對應哪個分支。這樣數據集就會被分成幾個小組。對于連續變量，所有連續變量的測試分支都是2條，其測試分支分別對應著{<=A?,>a?}(a就是對應的閥值)。
如何選擇測試？
分類樹中每個節點對應著測試，但是這些測試是如何來選擇呢？C4.5根據信息論標準來選擇測試，比如增益（在信息論中，熵對應著某一分布的信息量，其值同時也對應著要完全無損表示該分布所需要的最小的比特數，本質上熵對應著不確定性，可能的變化的豐富程度。所謂增益，就是指在應用了某一測試之后，其對應的可能性豐富程度下降，不確定性減小，這個減小的幅度就是增益，其實質上對應著分類帶來的好處）或者增益比（這個指標實際上就等于增益/熵，之所以采用這個指標是為了克服采用增益作為衡量標準的缺點，采用增益作為衡量標準會導致分類樹傾向于優先選擇那些具有比較多的分支的測試，這種傾向需要被抑制）。算法在進行Tree-Growth時，總是“貪婪得”選擇那些信息論標準最高的那些測試。
如何選擇連續變量的閾值？
在《分類樹中的測試是怎樣的？》中提到連續變量的分支的閾值點為a，這閾值如何確定呢？很簡單，把需要處理的樣本（對應根節點）或樣本子集（對應子樹）按照連續變量的大小從小到大進行排序，假設該屬性對應的不同的屬性值一共有N個，那么總共有N-1個可能的候選分割閾值點，每個候選的分割閾值點的值為上述排序后的屬性值鏈表中兩兩前后連續元素的中點，那么我們的任務就是從這個N-1個候選分割閾值點中選出一個，使得前面提到的信息論標準最大。舉個例子，對play數據集，我們來處理溫度屬性，來選擇合適的閾值。首先按照溫度大小對對應樣本進行排序如下：
那么可以看到有13個可能的候選閾值點，比如middle[64,65], middle[65,68]….,middle[83,85]。那么最優的閾值該選多少呢？應該是middle[71,72]，如上圖中紅線所示。為什么呢？如下計算：
通過上述計算方式，0.939是最大的，因此測試的增益是最小的。（測試的增益和測試后的熵是成反比的，這個從后面的公式可以很清楚的看到）。根據上面的描述，我們需要對每個候選分割閾值進行增益或熵的計算才能得到最優的閾值，我們需要算N-1次增益或熵（對應溫度這個變量而言就是13次計算）。能否有所改進呢？少算幾次，加快速度。答案是可以該進，如下圖：
該圖中的綠線代表可能的最優分割閾值點，根據信息論知識，像middle[72,75]（紅線所示）這個分割點，72,75屬于同一個類，這樣的分割點是不可能有信息增益的。（把同一個類分成了不同的類，這樣的閾值點顯然不會有信息增益，因為這樣的分類沒能幫上忙，減少可能性）
哪個屬性是最佳的分類屬性？
信息論標準有兩種，一種是增益，一種是增益比。
首先來看看增益Gain的計算
為了精確地定義信息增益，我們先定義信息論中廣泛使用的一個度量標準，稱為熵（entropy），它刻畫了任意樣例集的純度（purity）。給定包含關于某個目標概念的正反樣例的樣例集S，那么S相對這個布爾型分類的熵為：
上述公式中，p+代表正樣例，比如在本文開頭第二個例子中p+則意味著去打羽毛球，而p-則代表反樣例，不去打球。
舉例來說，假設S是一個關于布爾概念的有14個樣例的集合，它包括9個正例和5個反例（我們采用記號[9+，5-]來概括這樣的數據樣例），那么S相對于這個布爾樣例的熵為：
Entropy（[9+，5-]）=-（9/14）log2（9/14）-（5/14）log2（5/14）=0.940。
上述公式的值為0.940。它的信息論含義就是我要想把Play？這個信息傳遞給別人話，平均來講我至少需要0.940個bit來傳遞這個信息。C4.5的目標就是經過分類來減小這個熵。那么我們來依次考慮各個屬性測試，通過某一屬性測試我們將樣本分成了幾個子集，這使得樣本逐漸變得有序，那么熵肯定變小了。這個熵的減小量就是我們選擇屬性測試的依據。
信息增益Gain(S,A)定義
已經有了熵作為衡量訓練樣例集合純度的標準，現在可以定義屬性分類訓練數據的效力的度量標準。這個標準被稱為“信息增益（information gain）”。簡單的說，一個屬性的信息增益就是由于使用這個屬性分割樣例而導致的期望熵降低(或者說，樣本按照某屬性劃分時造成熵減少的期望)。更精確地講，一個屬性A相對樣例集合S的信息增益Gain(S,A)被定義為：
其中 Values(A)是屬性A所有可能值的集合，是S中屬性A的值為v的子集。換句話來講，Gain(S,A)是由于給定屬性A的值而得到的關于目標函數值的信息。當對S的一個任意成員的目標值編碼時，Gain(S,A)的值是在知道屬性A的值后可以節省的二進制位數。
它的實質是把數據集D根據某一屬性測試分成v個子集，這使得數據集S變得有序，使得數據集S的熵變小了。分組后的熵其實就是各個子集的熵的權重和。通過計算我們得到Gain(Outlook)=0.940-0.694=0.246，Gain(Windy)=0.940-0.892=0.048….
可以得到第一個測試屬性是Outlook。需要注意的是，屬性測試是從數據集中包含的所有屬性組成的候選屬性中選擇出來的。對于所在節點到根節點的路徑上所包含的屬性（我們稱之為繼承屬性），其實根據公式很容易得到他們的熵增益是0，因此這些繼承屬性完全不必考慮，可以從候選屬性中剔除這些屬性。
到這里似乎一切都很完美，增益這個指標非常好，但是其實增益這個指標有一個缺點。我們來考慮play數據集中的Day這個屬性（我們假設它是一個真屬性，實際上很可能大家不會把他當做屬性），Day有14個不同的值，那么Day的屬性測試節點就會有14個分支，很顯然每個分支其實都覆蓋了一個“純”數據集（所謂“純”，指的就是所覆蓋的數據集都屬于同一個類），那么其熵增益顯然就是最大的，那么Day就默認得作為第一個屬性。之所以出現這樣的情況，是因為增益這個指標天然得偏向于選擇那些分支比較多的屬性，也就是那些具有的值比較多的那些屬性。這種偏向性使我們希望克服的，我們希望公正地評價所有的屬性。因此又一個指標被提出來了Gain Ratio-增益比。
C4.5算法之信息增益率
增益比率度量是用前面的增益度量Gain(S，A)和分裂信息度量SplitInformation(S，A)來共同定義的，如下所示：
其中，分裂信息度量被定義為(分裂信息用來衡量屬性分裂數據的廣度和均勻)：
其中S1到Sc是c個值的屬性A分割S而形成的c個樣例子集。分裂信息實際上就是S關于屬性A的各值的熵。這與我們前面對熵的使用不同，在那里我們只考慮S關于學習到的樹要預測的目標屬性的值的熵。
通過計算我們很容易得到GainRatio(Outlook)=0.246/1.577=0.156。增益比實際上就是對增益進行了歸一化，這樣就避免了指標偏向分支多的屬性的傾向。
決策樹能夠幫助我們對新出現的樣本進行分類，但還有一些問題它不能很好得解決。比如我們想知道對于最終的分類，哪個屬性的貢獻更大？能否用一種比較簡潔的規則來區分樣本屬于哪個類？等等。
C4.5算法的改進：
用信息增益率來選擇屬性。
在樹構造過程中進行剪枝，在構造決策樹的時候，那些掛著幾個元素的節點，不考慮最好，不然容易導致overfitting。
對非離散數據也能處理。
能夠對不完整數據進行處理。
決策樹的剪枝
決策樹為什么要剪枝？原因就是避免決策樹“過擬合”樣本。前面的算法生成的決策樹非常的詳細而龐大，每個屬性都被詳細地加以考慮，決策樹的樹葉節點所覆蓋的訓練樣本都是“純”的。因此用這個決策樹來對訓練樣本進行分類的話，你會發現對于訓練樣本而言，這個樹表現堪稱完美，它可以100%完美正確得對訓練樣本集中的樣本進行分類（因為決策樹本身就是100%完美擬合訓練樣本的產物）。但是，這會帶來一個問題，如果訓練樣本中包含了一些錯誤，按照前面的算法，這些錯誤也會100%一點不留得被決策樹學習了，這就是“過擬合”。C4.5的締造者昆蘭教授很早就發現了這個問題，他作過一個試驗，在某一個數據集中，過擬合的決策樹的錯誤率比一個經過簡化了的決策樹的錯誤率要高。那么現在的問題就來了，如何在原生的過擬合決策樹的基礎上，通過剪枝生成一個簡化了的決策樹？
1、第一種方法，也是最簡單的方法，稱之為基于誤判的剪枝。這個思路很直接，完全的決策樹不是過度擬合么，我再搞一個測試數據集來糾正它。對于完全決策樹中的每一個非葉子節點的子樹，我們嘗試著把它替換成一個葉子節點，該葉子節點的類別我們用子樹所覆蓋訓練樣本中存在最多的那個類來代替，這樣就產生了一個簡化決策樹，然后比較這兩個決策樹在測試數據集中的表現，如果簡化決策樹在測試數據集中的錯誤比較少，并且該子樹里面沒有包含另外一個具有類似特性的子樹（所謂類似的特性，指的就是把子樹替換成葉子節點后，其測試數據集誤判率降低的特性），那么該子樹就可以替換成葉子節點。該算法以bottom-up的方式遍歷所有的子樹，直至沒有任何子樹可以替換使得測試數據集的表現得以改進時，算法就可以終止。
2、第一種方法很直接，但是需要一個額外的測試數據集，能不能不要這個額外的數據集呢？為了解決這個問題，于是就提出了悲觀剪枝。該方法剪枝的依據是訓練樣本集中的樣本誤判率。我們知道一顆分類樹的每個節點都覆蓋了一個樣本集，根據算法這些被覆蓋的樣本集往往都有一定的誤判率，因為如果節點覆蓋的樣本集的個數小于一定的閾值，那么這個節點就會變成葉子節點，所以葉子節點會有一定的誤判率。而每個節點都會包含至少一個的葉子節點，所以每個節點也都會有一定的誤判率。悲觀剪枝就是遞歸得估算每個內部節點所覆蓋樣本節點的誤判率。剪枝后該內部節點會變成一個葉子節點，該葉子節點的類別為原內部節點的最優葉子節點所決定。然后比較剪枝前后該節點的錯誤率來決定是否進行剪枝。該方法和前面提到的第一種方法思路是一致的，不同之處在于如何估計剪枝前分類樹內部節點的錯誤率。
連續值屬性的改進
相對于那些離散值屬性，分類樹算法傾向于選擇那些連續值屬性，因為連續值屬性會有更多的分支，熵增益也最大。算法需要克服這種傾向，我們利用增益率來克服這種傾向。增益率也可以用來克服連續值屬性傾向。增益率作為選擇屬性的依據克服連續值屬性傾向，這是沒有問題的。但是如果利用增益率來選擇連續值屬性的分界點，會導致一些副作用。分界點將樣本分成兩個部分，這兩個部分的樣本個數之比也會影響增益率。根據增益率公式，我們可以發現，當分界點能夠把樣本分成數量相等的兩個子集時（我們稱此時的分界點為等分分界點），增益率的抑制會被最大化，因此等分分界點被過分抑制了。子集樣本個數能夠影響分界點，顯然不合理。因此在決定分界點是還是采用增益這個指標，而選擇屬性的時候才使用增益率這個指標。這個改進能夠很好得抑制連續值屬性的傾向。當然還有其它方法也可以抑制這種傾向，比如MDL。
處理缺失屬性
如果有些訓練樣本或者待分類樣本缺失了一些屬性值，那么該如何處理？要解決這個問題，需要考慮3個問題：
i)當開始決定選擇哪個屬性用來進行分支時，如果有些訓練樣本缺失了某些屬性值時該怎么辦？
ii)一個屬性已被選擇，那么在決定分支的時候如果有些樣本缺失了該屬性該如何處理？
iii)當決策樹已經生成，但待分類的樣本缺失了某些屬性，這些屬性該如何處理？針對這三個問題，昆蘭提出了一系列解決的思路和方法。
對于問題i),計算屬性a的增益或者增益率時，如果有些樣本沒有屬性a，那么可以有這么幾種處理方式：
(1)忽略這些缺失屬性a的樣本。
(2)給缺失屬性a的樣本賦予屬性a一個均值或者最常用的的值。
(3)計算增益或者增益率時根據缺失屬性樣本個數所占的比率對增益/增益率進行相應的“打折”。
(4)根據其他未知的屬性想辦法把這些樣本缺失的屬性補全。
對于問題ii)，當屬性a已經被選擇，該對樣本進行分支的時候，如果有些樣本缺失了屬性a,那么：
(1)忽略這些樣本。
(2)把這些樣本的屬性a賦予一個均值或者最常出現的值，然后再對他們進行處理。
(3)把這些屬性缺失樣本，按照具有屬性a的樣本被劃分成的子集樣本個數的相對比率，分配到各個子集中去。至于哪些缺失的樣本被劃分到子集1，哪些被劃分到子集2，這個沒有一定的準則，可以隨機而動。(A)把屬性缺失樣本分配給所有的子集，也就是說每個子集都有這些屬性缺失樣本。
(3)單獨為屬性缺失的樣本劃分一個分支子集。
(4)對于缺失屬性a的樣本，嘗試著根據其他屬性給他分配一個屬性a的值，然后繼續處理將其劃分到相應的子集。
對于問題iii)，對于一個缺失屬性a的待分類樣本，有這么幾種選擇：
(1)如果有單獨的確實分支，依據此分支。
(2)把待分類的樣本的屬性a值分配一個最常出現的a的屬性值，然后進行分支預測。
(3)根據其他屬性為該待分類樣本填充一個屬性a值，然后進行分支處理。
(4)在決策樹中屬性a節點的分支上，遍歷屬性a節點的所有分支，探索可能所有的分類結果，然后把這些分類結果結合起來一起考慮，按照概率決定一個分類。
(5)待分類樣本在到達屬性a節點時就終止分類，然后根據此時a節點所覆蓋的葉子節點類別狀況為其分配一個發生概率最高的類。
推理規則
C4.5決策樹能夠根據決策樹生成一系列規則集,我們可以把一顆決策樹看成一系列規則的組合。一個規則對應著從根節點到葉子節點的路徑，該規則的條件是路徑上的條件，結果是葉子節點的類別。C4.5首先根據決策樹的每個葉子節點生成一個規則集，對于規則集中的每條規則，算法利用“爬山”搜索來嘗試是否有條件可以移除，由于移除一個條件和剪枝一個內部節點本質上是一樣的，因此前面提到的悲觀剪枝算法也被用在這里進行規則簡化。MDL準則在這里也可以用來衡量對規則進行編碼的信息量和對潛在的規則進行排序。簡化后的規則數目要遠遠小于決策樹的葉子節點數。根據簡化后的規則集是無法重構原來的決策樹的。規則集相比決策樹而言更具有可操作性，因此在很多情況下我們需要從決策樹中推理出規則集。C4.5有個缺點就是如果數據集增大了一點，那么學習時間會有一個迅速地增長。
來自： http://blog.csdn.net//u011067360/article/details/21861989