數據挖掘十大算法之決策樹詳解(1)

從分類問題開始

分類（Classification）任務就是確定對象屬于哪個預定義的目標類。分類問題不僅是一個普遍存在的問題，而且是其他更加復雜的決策問題的基礎，更是機器學習和數據挖掘技術中最龐大的一類算法家族。我們前面介紹過的很多算法（例如SVM，樸素貝葉斯等）都可以用來解決分類問題。作為本文的開始，我們首先來簡單回顧一下什么是分類。

假設我們現在有如下表所示的一個屬性集（feature set），它收集了幾個病患的癥狀和對應的病癥。癥狀包括頭疼的程度、咳嗽的程度、體溫以及咽喉是否腫痛，這些癥狀（feature）的組合就對應一個病癥的分類（Cold 還是 Flu）。

分類問題的本質就是當給定這樣一個數據集后，要求我們訓練出（或建立）一個模型f。當出現一組新的特征向量時，要求我們預測（或判斷）擁有這樣一組特征向量的對象應當屬于哪個類別。就我們現在給出的例子而言，假設你是一名醫生，現在收治了一位新的病患，然后你通過問診得知他的一些癥狀（包括頭疼的程度、咳嗽的程度、體溫以及咽喉是否腫痛），然后你就要根據你已經建立好的模型來判斷該病人得的到底是Cold（普通感冒）還是Flu（流行性感冒）。

分類問題的類別數目可以是兩類也可以是多類。二分類問題是最簡單的分類問題，而多分類問題模型可以在二分類模型的基礎上進行構建。我們在前面文章中一直使用的鳶尾花數據集就是一個典型的多分類問題，問題的最終目標是判斷給定一朵花，它應該屬于setosa、versicolor和virginica中的哪一類。

決策樹基礎

決策樹是一種用于對實例進行分類的樹形結構。決策樹由節點（node）和有向邊（directed edge）組成。節點的類型有兩種：內部節點和葉子節點。其中，內部節點表示一個特征或屬性的測試條件（用于分開具有不同特性的記錄），葉子節點表示一個分類。

一旦我們構造了一個決策樹模型，以它為基礎來進行分類將是非常容易的。具體做法是，從根節點開始，地實例的某一特征進行測試，根據測試結構將實例分配到其子節點（也就是選擇適當的分支）；沿著該分支可能達到葉子節點或者到達另一個內部節點時，那么就使用新的測試條件遞歸執行下去，直到抵達一個葉子節點。當到達葉子節點時，我們便得到了最終的分類結果。

下圖是一個決策樹的示例（注意我們僅用了兩個feature就對數據集中的5個記錄實現了準確的分類）： 

Hunt算法是一種采用局部最優策略的決策樹構建算法，它同時也是許多決策樹算法的基礎，包括ID3、C4.5和CART等。該算法的具體執行步驟如下：

在Hunt算法中，通過將訓練記錄相繼劃分成較純的子集，以遞歸方式建立決策樹。設 Dt 是與結點 t 相關聯的訓練記錄集，而y={y1,y2,?,yc}是類標號，Hunt算法的遞歸定義如下： 
(1) 如果 Dt 中所有記錄都屬于同一個類，則 t 是葉結點，用 yt 標記。 
(2) 如果 Dt 中包含屬于多個類的記錄，則選擇一個屬性測試條件（attribute test condition），將記錄劃分成較小的子集。對于測試條件的每個輸出，創建一個子女結點，并根據測試結果將 Dt 中的記錄分布到子女結點中。然后，對于每個子女結點，遞歸地調用該算法。

為了演示這方法，我們選用文獻【2】中的一個例子來加以說明：預測貸款申請者是會按時歸還貸款，還是會拖欠貸款。對于這個問題，訓練數據集可以通過考察以前貸款者的貸款記錄來構造。在下圖所示的例子中，每條記錄都包含貸款者的個人信息，以及貸款者是否拖欠貸款的類標號。

該分類問題的初始決策樹只有一個結點，類標號為“拖欠貨款者＝否”（見圖a），意味大多數貸款者都按時歸還貸款。然而，該樹需要進一步的細化，因為根結點包含兩個類的記錄。根據“有房者”測試條件，這些記錄被劃分為較小的子集，如圖b所示。接下來，對根結點的每個子女遞歸地調用Hunt算法。從下圖給出的訓練數據集可以看出，有房的貸款者都按時償還了貸款，因此，根結點的左子女為葉結點，標記為“拖欠貨款者二否”（見圖b)。對于右子女，我們需要繼續遞歸調用Hunt算法，直到所有的記錄都屬于同一個類為止。每次遞歸調用所形成的決策樹顯示在圖c和圖d中。

如果屬性值的每種組合都在訓練數據中出現，并且每種組合都具有唯一的類標號，則Hunt 算法是有效的。但是對于大多數實際情況，這些假設太苛刻了，因此，需要附加的條件來處理以下的情況：

算法的第二步所創建的子女結點可能為空，即不存在與這些結點相關聯的記錄。如果沒有一個訓練記錄包含與這樣的結點相關聯的屬性值組合，這種情形就可能發生。這時，該結點成為葉結點，類標號為其父結點上訓練記錄中的多數類。

在第二步，如果與 Dt 相關聯的所有記錄都具有相同的屬性值（目標屬性除外），則不可能進一步劃分這些記錄。在這種情況下，該結點為葉結點，其標號為與該結點相關聯的訓練記錄中的多數類。

此外，在上面這個算法過程中，你可能會疑惑：我們是依據什么原則來選取屬性測試條件的，例如為什第一次選擇“有房者”來作為測試條件。事實上，如果我們選擇的屬性測試條件不同，那么對于同一數據集來說所建立的決策樹可能相差很大。如下圖所示為基于前面預測病人是患了Cold還是Flu的數據集所構建出來的另外兩種情況的決策樹：

事實上，在構建決策樹時我們需要關心的問題包括：

How to build optimal Decision Tree?

How to choose attribute values at each decision point (node)?

How to choose number of branches at each node and attribute values for partitioning the data?

When to stop the growth of the tree?

我會在接下來的部分回答上述這些問題。

構建決策樹進階：Gini測度與劃分

構建一棵最優的決策樹是一個NP難問題！所以我們只能采用一些啟發式策略來解決：

Choose an attribute to partition the data at the node such that each partition is as homogeneous (least impure) as possible. This means we would like to see most of the instances in each partition belonging to as few classes as possible and each partition should be as large as possible.

We can stop the growth of the tree if all the leaf nodes are largely dominated by a single class (that is the leaf nodes are nearly pure).

現在新的問題來了：如何評估節點的Impurity？通?？梢允褂玫闹笜擞腥缦氯齻€（實際應用時，只要選其中一個即可）：

Gini Index

Entropy

Misclassification error

第一個可以用來評估節點Impurity的指標是Gini系數。對于一個給定的節點 t，它的Gini系數計算公式如下： 

其中，p(j | t) is the relative frequency of class j at node t（即表示給定節點 t 中屬于類 j 的記錄所占的比例）。通過這個計算公式你可以看出：

Maximum value of Gini index = (1 - 1/nc) when records are equally distributed among all classes, implying least interesting information or most impure.

Minimum is (0.0) when all records belong to one class, implying most interesting information or most pure or most homogeneous.

說到這里，我們插一句題外話（如果你對這部分Background無感可以跳過）。你在生活中有沒有聽過基尼系數這個名詞？是的，基尼系數本來是經濟學里的一個概念?；嵯禂凳?943年美國經濟學家阿爾伯特·赫希曼根據勞倫茨曲線所定義的判斷收入分配公平程度的指標?；嵯禂凳潜壤龜抵?，在0和1之間，是國際上用來綜合考察居民內部收入分配差異狀況的一個重要分析指標。其具體含義是指，在全部居民收入中，用于進行不平均分配的那部分收入所占的比例?；嵯禂底畲鬄椤?”，最小等于“0”。前者表示居民之間的收入分配絕對不平均，即100%的收入被一個單位的人全部占有了；而后者則表示居民之間的收入分配絕對平均，即人與人之間收入完全平等，沒有任何差異。但這兩種情況只是在理論上的絕對化形式，在實際生活中一般不會出現。因此，基尼系數的實際數值只能介于0～1之間，基尼系數越小收入分配越平均，基尼系數越大收入分配越不平均。國際上通常把0.4作為貧富差距的警戒線，大于這一數值容易出現社會動蕩。

選擇最佳劃分的度量通常是根據劃分后子女結點不純性的程度。不純的程度越低，類分布就越傾斜。例如，類分布為 (0, 1)的結點具有零不純性，而均衡分布(0.5, 0.5)的結點具有最高的不純性?，F在我們回過頭來看一個具體的計算例子?，F在我們一共有6個records，以二元分類問題不純性度量值的比較為例，下圖的意思表示有四個節點，然后分別計算了每一個節點的GINI系數值（注意決策樹中每一個內節點都表示一種分支判斷，也就可以將6個records分成幾類，我們這里討論的是二元分類所以是分成兩個子類）： 

從上面的例子可以看出，第一個結點，具有最低的不純性度量值，接下來節點的不純度度量值依次遞增。為了確定測試條件的效果，我們需要比較父結點（劃分前）的不純程度和子女結點（劃分后） 的不純程度，它們的差越大，測試條件的效果就越好。增益Δ是一種可以用來確定劃分效果的標準： 

其中，I(.) 是給定結點的不純性度量，N是父結點上的記錄總數，k是屬性值的個數，N(vj)是與子女結點 vj 相關聯的記錄個數。決策樹構建算法通常選擇最大化增益Δ的測試條件，因為對所有的測試條件來說，I(parent)是一個不變的值，所以最大化增益等價于最小化子女結點的不純性度量的加權平均值。

考慮下面這個劃分的例子。假設有兩種方法將數據劃分成較小的子集。劃分前，Gini系數等于0.5，因為屬于兩個類（C0和C1）的記錄個數相等。如果選擇屬性A來劃分數據，節點N1的Gini系數為1?(4/7)2?(3/7)2=0.4898，而N2的Gini系數為1?(2/5)2?(3/5)2=0.48，派生節點的Gini系數的加權平均為(7/12)×0.4898+(5/12)×0.48=0.486。同理，我們還可以計算屬性B的Gini系數的加權平均為(7/12)×0.408+(5/12)×0.32=0.371。因為屬性B具有更小的Gini系數，所以它比屬性A更可取。

考慮多分類的情況

標稱屬性可以產生二元劃分也可以產生多路劃分，如下圖所示。二元劃分的Gini系數的計算與二元屬性類似。對于車型屬性第一種二元分類，{運動，豪華}的Gini系數是0.4922，而{家用}的Gini系數是0.375。這個劃分的Gini系數加權平均是： 

類似地，對第二種二元劃分{運動}和{家用，豪華}，Gini系數加權平均是0.167。第二種劃分的Gini系數相對更低，因為其對應的子集的純度更高。對于多路劃分，需要計算每個屬性值的Gini系數。Gini({家用})=0.375，Gini({運動})=0，Gini({豪華})=0.219，所以多路劃分的Gini系數加權平均值為： 

多路劃分的Gini系數比兩個二元劃分都小。這是因為二元劃分實際上合并了多路劃分的某些輸出，自然降低了子集的純度。 

考慮特征值連續的情況

考慮下圖所示的例子，其中測試條件“年收入≤v”用來劃分拖欠貸款分類問題的訓練記錄。用窮舉方法確定 v 的值，將N個記錄中所有的屬性值都作為候選劃分點。對每個候選v，都要掃描一次數據集，統計年收入大于和小于v的記錄數，然后計算每個候迭的Gini系數，并從中選擇具有最小值的候選劃分點。這種方法的計算代價顯然是高昂的，因為對每個候選劃分點計算 Gini系數需要O(N)次操作，由于有N個候選，總的計算復雜度為O(N2)。為了降低計算復雜度， 按照年收入將訓練記錄排序，所需要的時間為O(NlogN)，從兩個相鄰的排過序的屬性值中選擇中間值作為候選劃分點，得到候選劃分點55, 65, 72等。無論如何，與窮舉方法不同，在計算候選劃分點的Gini指標時，不需考察所有N個記錄。

對第一個候選v=55，沒有年收入小于$55K的記錄，所以年收入＜$55K的派生結點的Gini系數是0；另一方面，年收入≥$55K的樣本記錄數目分別為3（類Yes）和7（類No)。如此一來，該結點的Gini系數是0.420。該候選劃分的Gini系數的加權平均就等于0×0+1×0.42=0.42。

對第二個候選v=65，通過更新上一個候選的類分布，就可以得到該候選的類分布。更具體地說，新的分布通過考察具有最低年收入（即$60K）的記錄的類標號得到。因為該記錄的類標號是No所以類No的計數從0增加到1（對于年收入≤$65K），和從7降到6（對于年收入> $65K），類Yes的分布保持不變。新的候選劃分點的加權平均Gini系數為0.4。

重復這樣的計算，直到算出所有候選的Gini系數值。最佳的劃分點對應于產生最小Gini系數值的點，即v=97。該過程代價相對較低，因為更新每個候選劃分點的類分布所需的時間是一個常數。該過程還可以進一步優化：僅考慮位于具有不同類標號的兩個相鄰記錄之間的候選劃分點。例如，因為前三個排序后的記錄（分別具有年收入$60K、 $70K和$75K)具有相同的類標號，所以最佳劃分點肯定不會在$60K和$75K之間，因此，候選劃分點 v = $55K、 $65K、 $72K、 $87K、 $92K、 $110K、 $122K、 $172K 和 $230K都將被忽略，因為它們都位于具有相同類標號的相鄰記錄之間。該方法使得候選劃分點的個數從11個降到2個。

其他純度測量指標暨劃分標準

正如我們前面已經提到的，評估節點的Impurity可以是三個標準中的任何一個。而且我們已經介紹了Gini系數。

信息熵與信息增益

下面來談談另外一個可選的標準：信息熵（entropy）。在信息論中，熵是表示隨機變量不確定性的度量。熵的取值越大，隨機變量的不確定性也越大。

設X是一個取有限個值的離散隨機變量，其概率分布為 

則隨機變量X的熵定義為 

在上式中，如果pi=0，則定義0log0=0。通常，上式中的對數以2為底或以e為底，這時熵的單位分別是比特（bit）或納特（nat）。由定義可知，熵只依賴于 X 的分布，而與 X 的取值無關，所以也可以將X 的熵記作 H(p)，即 

就我們當前所面對的問題而言，如果給定一個節點 t，它的（條件）熵計算公式如下：

其中，p(j | t) is the relative frequency of class j at node t（即表示給定節點 t 中屬于類 j 的記錄所占的比例）。通過這個計算公式你可以看出：

Maximum (lognc) when records are equally distributed among all classes implying least information

Minimum (0.0) when all records belong to one class, implying most information

還是來看一個具體的計算例子，如下圖所示（基本情況與前面介紹Gini系數時的例子類似，我們不再贅述）： 

以此為基礎，我們要來定義信息增益（Information Gain）如下： 

其中，Parent Node, p is split into k partitions; ni is number of records in partition i. 
與之前的情況相同，決策樹構建算法通常選擇最大化信息增益的測試條件來對節點進行劃分。

使用信息增益的一個缺點在于：信息增益的大小是相對于訓練數據集而言的。在分類問題困難時，即訓練數據集的經驗熵比較大時，信息增益會偏大。反之，信息增益會偏小。使用信息增益比（Information gain ratio）可以對這一問題進行校正。 

于是，Higher entropy partitioning (large number of small partitions) is penalized!

分類誤差

給定一個節點t，它的分類誤差定義為： 

由此公式可知：

Maximum (1?1/nc) when records are equally distributed among all classes, implying least interesting information

Minimum (0.0) when all records belong to one class, implying most interesting information

話不多說，還是一個簡單的算例： 

下圖給出了二分類模型中，熵、Gini系數、分類誤差的比較情況。如果我們采用二分之一熵12H(p)的時候，你會發現它與Gini系數將會相當接近。

我們最后再來看一個Gini系數和分類誤差對比的例子： 

來計算一下加權平均的Gini系數： 

再來計算一下分類誤差： 

可見在這個例子中，Gini improves ! However，Missclassification unchanged! 我們會在下一篇文章中繼續介紹關于ID3、C4.5和CART算法的內容，其中會更加具體地用到本文所介紹的各種純度評判標準。