決策樹資料匯總

2012年8月26日

決策樹（Decision tree）

決策樹是以實例為基礎的歸納學習算法。

它從一組無次序、無規則的元組中推理出決策樹表示形式的分類規則。它采用自頂向下的遞歸方式，在決策樹的內部結點進行屬性值的比較，并根據不同的屬性值從該結點向下分支，葉結點是要學習劃分的類。從根到葉結點的一條路徑就對應著一條合取規則，整個決策樹就對應著一組析取表達式規則。1986年Quinlan提出了著名的ID3算法。在ID3算法的基礎上，1993年Quinlan又提出了C4.5算法。為了適應處理大規模數據集的需要，后來又提出了若干改進的算法，其中SLIQ(super-vised learning in quest)和SPRINT (scalable parallelizableinduction of decision trees)是比較有代表性的兩個算法。

　　ID3算法是由Quinlan首先提出的。該算法是以信息論為基礎，以信息熵和信息增益度為衡量標準，從而實現對數據的歸納分類。以下是一些信息論的基本概念：

　　定義1：若存在n個相同概率的消息，則每個消息的概率p是1/n，一個消息傳遞的信息量為Log2(n)

　　定義2：若有n個消息，其給定概率分布為P=(p1,p2…pn)，則由該分布傳遞的信息量稱為P的熵，記為

　　I(p)=-(i=1 to n求和)piLog2(pi)。

　　定義3：若一個記錄集合T根據類別屬性的值被分成互相獨立的類C1C2..Ck，則識別T的一個元素所屬哪個類所需要的信息量為Info(T)=I(p)，其中P為C1C2…Ck的概率分布，即P=(|C1|/|T|,…..|Ck|/|T|)

　　定義4：若我們先根據非類別屬性X的值將T分成集合T1,T2…Tn，則確定T中一個元素類的信息量可通過確定Ti的加權平均值來得到，即Info(Ti)的加權平均值為：

　　Info(X, T)=(i=1 to n 求和)((|Ti|/|T|)Info(Ti))

　　定義5：信息增益度是兩個信息量之間的差值，其中一個信息量是需確定T的一個元素的信息量，另一個信息量是在已得到的屬性X的值后需確定的T一個元素的信息量，信息增益度公式為：

　　Gain(X, T)=Info(T)-Info(X, T)

　　ID3算法計算每個屬性的信息增益，并選取具有最高增益的屬性作為給定集合的測試屬性。對被選取的測試屬性創建一個節點，并以該節點的屬性標記，對該屬性的每個值創建一個分支據此劃分樣本.

決策樹的構造

這個數據集來自Mitchell的機器學習，叫做是否去打網球play-tennis,以下數據仍然是從帶逗號分割的文本文件，復制到紀事本，把后綴直接改為.csv就可以拿Excel打開：

*play-tennis data，其中6個變量依次為：編號、天氣{Sunny、Overcast、Rain}、溫度{熱、冷、適中}、濕度{高、正常}、風力{強、弱}以及最后是否去玩的決策{是、否}。一個建議是把這些數據導入Excel后，另復制一份去掉變量的數據到另外一個工作簿，即只保留14個觀測值。這樣可以方便地使用Excel的排序功能，隨時查看每個變量的取值到底有多少。*/

NO. , Outlook , Temperature , Humidity , Wind , Play

1 , Sunny , Hot , High , Weak , No

2 , Sunny , Hot , High , Strong , No

3 , Overcast , Hot , High , Weak , Yes

4 , Rain , Mild , High , Weak , Yes

5 , Rain , Cool , Normal , Weak , Yes

6 , Rain , Cool , Normal , Strong , No

7 , Overcast , Cool , Normal , Strong , Yes

8 , Sunny , Mild , High , Weak , No

9 , Sunny , Cool , Normal , Weak , Yes

10 , Rain , Mild , Normal , Weak , Yes

11 , Sunny , Mild , Normal , Strong , Yes

12 , Overcast , Mild , High , Strong , Yes

13 , Overcast , Hot , Normal , Weak , Yes

14 , Rain , Mild , High , Strong , No

這里我們先不討論算法（這里用的是ID3/C4.5），把一棵決策樹建立起來再說。我們要建立的決策樹的形式類似于“如果天氣怎么樣，去玩；否則，怎么著怎么著”的樹形分叉。那么問題是用哪個屬性（即變量，如天氣、溫度、濕度和風力）最適合充當這顆樹的根節點，在它上面沒有其他節點，其他的屬性都是它的后續節點。借用信息論的概念，我們用一個統計量，“信息增益”（Information Gain）來衡量一個屬性區分以上數據樣本的能力。信息增益量越大，這個屬性作為一棵樹的根節點就能使這棵樹更簡潔，比如說一棵樹可以這么讀成，如果風力弱，就去玩；風力強，再按天氣、溫度等分情況討論，此時用風力作為這棵樹的根節點就很有價值。如果說，風力弱，再又天氣晴朗，就去玩；如果風力強，再又怎么怎么分情況討論，這棵樹相比就不夠簡潔了。計算信息增益的公式需要用到“熵”（Entropy）。名詞越來越多，讓我們通過手工計算記住它們的計算方法，把Excel打開：

1 計算熵

我們檢查的屬性是是否出去玩。用Excel對上面數據的play變量的各個取值排個序（這個工作簿里把“play”這個詞去掉），一共是14條記錄，你能數出取值為yes的記錄有9個，取值為no的有5個，我們說這個樣本里有9個正例，5 個負例，記為S(9+,5-)，S是樣本的意思(Sample)。這里熵記為Entropy(S),計算公式為：

Entropy(S)= -(9/14)*log(9/14)-(5/14)*log(5/14)

解釋一下，9/14是正例的個數與總記錄之比，同樣5/14是負例占總記錄的比例。log(.)是以2為底的對數（我們知道以e為底的對數稱為自然對數，記為ln(.),lg(.)表示以10為底的對數）。在Excel里我們可以隨便找一個空白的單元格，鍵入以下公式即得0.940：

=-(9/14)*LOG(9/14,2)-(5/14)*LOG(5/14,2)

這里LOG(9/14,2)中的“2”表示以2為底。類似地，如果你習慣用Matlab做數學運算本，公式為

-(9/14)*log2(9/14)-(5/14)*log2(5/14)

其中“2”的含義與上同。

總結：在這個例子中，我們的輸出屬性（我們要檢查的屬性）“play”只有兩個取值，同樣地，如果輸出屬性的取值大于2，公式是對成的，一樣的形式，連加就是，找到各個取值的個數，求出各自的比例。如果樣本具有二元輸出屬性，其熵的公式為

Entropy(S) =-(p+)*log(p+)-(p-)*log(p-)

其中，p+、p-分別為正例和負例占總記錄的比例。輸出屬性取值大于2的情況，公式是對稱的。

2 分別以Wind、Humidity、Outlook和Temperature作為根節點，計算其信息增益

可以數得，屬性Wind中取值為Weak的記錄有Normal的記錄有8條，其中正例6個，負例2個；同樣，取值為Strong的記錄6個，正例負例個3個。我們可以計算相應的熵為：

Entropy(Weak)=-(6/8)*log(6/8)-(2/8)*log(2/8)=0.811

Entropy(Strong)=-(3/6)*log(3/6)-(3/6)*log(3/6)=1.0

現在就可以計算出相應的信息增益了：

Gain(Wind)=Entropy(S)-(8/14)*Entropy(Weak)-(6/14)*Entropy(Strong)=0.940-(8/14)*0.811-(6/14)*1.0=0.048

這個公式的奧秘在于，8/14是屬性Wind取值為Weak的個數占總記錄的比例，同樣6/14是其取值為Strong的記錄個數與總記錄數之比。

同理，如果以Humidity作為根節點：

Entropy(High)=0.985 ; Entropy(Normal)=0.592

Gain(Humidity)=0.940-(7/14)*Entropy(High)-(7/14)*Entropy(Normal)=0.151

以Outlook作為根節點：

Entropy(Sunny)=0.971 ; Entropy(Overcast)=0.0 ; Entropy(Rain)=0.971

Gain(Outlook)=0.940-(5/14)*Entropy(Sunny)-(4/14)*Entropy(Overcast)-(5/14)*Entropy(Rain)=0.247

以Temperature作為根節點：

Entropy(Cool)=0.811 ; Entropy(Hot)=1.0 ; Entropy(Mild)=0.918

Gain(Temperature)=0.940-(4/14)*Entropy(Cool)-(4/14)*Entropy(Hot)-(6/14)*Entropy(Mild)=0.029

這樣我們就得到了以上四個屬性相應的信息增益值：

Gain(Wind)=0.048 ；Gain(Humidity)=0.151 ； Gain(Outlook)=0.247 ；Gain(Temperature)=0.029

最后按照信息增益最大的原則選Outlook為根節點。子節點重復上面的步驟。這顆樹可以是這樣的，它讀起來就跟你認為的那樣：

參考資料：

1.王厚峰，“機器學習‘課程講義，2007年春季學期，北京大學軟件與微電子學院

2.Mitchell,《機器學習》，曾華軍等譯，北京：機械工業出版社，2003

(2) C4.5算法

C4.5算法繼承了ID3算法的優點，并在以下幾方面對ID3算法進行了改進：

1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足；

2) 在樹構造過程中進行剪枝；

3) 能夠完成對連續屬性的離散化處理；

4) 能夠對不完整數據進行處理。

C4.5算法與其它分類算法如統計方法、神經網絡等比較起來有如下優點：產生的分類規則易于理解，準確率較高。其缺點是：在構造樹的過程中，需要對數據集進行多次的順序掃描和排序，因而導致算法的低效。此外，C4.5只適合于能夠駐留于內存的數據集，當訓練集大得無法在內存容納時程序無法運行。

(3) SLIQ算法

SLIQ算法對C4.5決策樹分類算法的實現方法進行了改進，在決策樹的構造過程中采用了“預排序”和“廣度優先策略”兩種技術。

1)預排序。對于連續屬性在每個內部結點尋找其最優分裂標準時，都需要對訓練集按照該屬性的取值進行排序，而排序是很浪費時間的操作。為此，SLIQ算法采用了預排序技術。所謂預排序，就是針對每個屬性的取值，把所有的記錄按照從小到大的順序進行排序，以消除在決策樹的每個結點對數據集進行的排序。具體實現時，需要為訓練數據集的每個屬性創建一個屬性列表，為類別屬性創建一個類別列表。

2)廣度優先策略。在C4.5算法中，樹的構造是按照深度優先策略完成的，需要對每個屬性列表在每個結點處都進行一遍掃描，費時很多，為此，SLIQ采用廣度優先策略構造決策樹，即在決策樹的每一層只需對每個屬性列表掃描一次，就可以為當前決策樹中每個葉子結點找到最優分裂標準。

SLIQ算法由于采用了上述兩種技術，使得該算法能夠處理比C4.5大得多的訓練集，在一定范圍內具有良好的隨記錄個數和屬性個數增長的可伸縮性。

然而它仍然存在如下缺點：

1)由于需要將類別列表存放于內存,而類別列表的元組數與訓練集的元組數是相同的,這就一定程度上限制了可以處理的數據集的大小。

2)由于采用了預排序技術，而排序算法的復雜度本身并不是與記錄個數成線性關系，因此，使得SLIQ算法不可能達到隨記錄數目增長的線性可伸縮性。

(4)SPRINT算法

為了減少駐留于內存的數據量，SPRINT算法進一步改進了決策樹算法的數據結構，去掉了在SLIQ中需要駐留于內存的類別列表，將它的類別列合并到每個屬性列表中。這樣，在遍歷每個屬性列表尋找當前結點的最優分裂標準時，不必參照其他信息，將對結點的分裂表現在對屬性列表的分裂，即將每個屬性列表分成兩個，分別存放屬于各個結點的記錄。

SPRINT算法的優點是在尋找每個結點的最優分裂標準時變得更簡單。其缺點是對非分裂屬性的屬性列表進行分裂變得很困難。解決的辦法是對分裂屬性進行分裂時用哈希表記錄下每個記錄屬于哪個孩子結點，若內存能夠容納下整個哈希表，其他屬性列表的分裂只需參照該哈希表即可。由于哈希表的大小與訓練集的大小成正比，當訓練集很大時，哈希表可能無法在內存容納，此時分裂只能分批執行，這使得SPRINT算法的可伸縮性仍然不是很好。

其他資料：

本文是《Mitchell機器學習》《JiaweiHan數據挖掘概念與技術》的學習筆記

概覽一

1 決策樹就是實例屬性值約束的合取的析取式。從樹根到樹葉的每一條路徑對應一組屬性測試的合取，樹本身對應這些合取的析取。

2 決策樹建立時，使用統計測試來確定每一個實例屬性單獨分類訓練樣例的能力，在每個結點選取能最好地分類樣例的屬性，且從不回溯重新考慮以前的選擇。因此，決策樹學習是一個自頂向下的貪婪搜索算法。

3 每一步都使用統計測試使決策樹學習對錯誤有很好的健壯性。

4 決策樹學習的假設空間包含所有的決策樹，它是關于現有屬性的有限離散值函數的一個完整空間。每個有限離散值函數都可被表示為某個決策樹。因此，決策樹學習(ID3)的歸納偏置來自它的搜索策略，即較短的樹比較長的樹優先，信息增益高的屬性更靠近根結點的樹優先。這種類型的偏置稱為優選偏置或搜索偏置。而候選消除算法的歸納偏置來自它對搜索空間的定義，被稱為限定偏置或語言偏置。

5 奧坎姆剃刀：優先選擇擬合數據的最簡單假設。

一個解釋：

找到一個短的但同時與訓練數據擬合的假設的可能性較小，不太可能是統計巧合。

兩個難題：

I． ? ? ? ? ? ? ? 根據什么相信短描述的決策樹組成的小假設集合比其它眾多可定義的小假設集合更適當？

II． ? ? ? ? ? ?假設的大小由學習器內部使用的特定表示決定。不同的內部表示方式，據奧坎姆剃刀產生兩個不同的假設。

6 處理不同代價屬性

使屬性代價參與屬性選擇度量，如將信息增益除以屬性代價。這在考慮獲取屬性的不同代價的現實條件時是很有用處的。

概覽二

1 在決策樹歸納分類之前，假設數據是預處理過的。不可忽略地，這其中包括數據清理，相關分析，數據變換與歸約。具體實現及方法另述。

2 (離散)分類和（數值）預測是預測問題的兩種主要類型，決策樹一般用于分類。

3 歸納決策樹時對于樹的每一層都需要掃描一遍D中的元組，因此算法的計算復雜度為O(n*|D|*log|D|)。

4 決策樹歸納的scalability

（1）SLIQ使用若干駐留磁盤的屬性列表和單個駐留內存的類列表

（2）SPRINT使用另一種屬性列表，易于并行，消除了所有內存限制，但需要正比于訓練集的散列樹。

（3）RainForest對每個屬性維護一個AVC（屬性-值-類）集，可以選擇任何屬性度量。

（4）BOAT使用稱作bootstrap的統計學技術，從子集構造多棵樹后合并構造接近于真實樹的新樹。可使用二元分裂的屬性選擇度量，如Gini指標。只需掃描訓練集兩次，可以增量更新。

綜述

1 屬性選擇度量：信息增益（ID3使用）

I 熵(entropy)刻畫了任意樣例集的純度，熵值越大表示越不純，識別其中元組分類所需要的平均信息量就越大。公式如下：

熵的最大可能為logc。信息論中熵的一種解釋是，確定要編碼集合S中任意成員的分類所需要的最少二進制位數。所以底數都是2。

II 信息增益Gain(S,A)有幾種解釋：

由于知道屬性A的值而導致的期望熵減少；

原來的信息需求與新的需求的差，即信息需求的期望減少。

公式如下，第二項描述的是每個子集的熵的加權和：

2 屬性選擇度量：增益率（C4.5使用）

I 信息增益度量存在一個內在偏置，它偏袒具有較多值的屬性。

II 分裂信息：S關于屬性A的各值的熵，用來衡量屬性分裂數據的廣度和均勻性，懲罰可取較多值的屬性。公式如下：

III 增益率：

IV 增益率存在的問題：當Si約等于S時，分裂信息趨向于0，GainRatio變得不穩定。可以先計算每個屬性的增益，僅對增益高過平均值的屬性應用增益比率測試。

3 屬性選擇度量：Gini指標（CART使用）

I Gini指標度量數據劃分或訓練元組集D的不純度，如下，其中pi=|C(i,D)|/|D|：

II 只考慮屬性的二元劃分。因此對于有v個值的屬性A，存在2^v-2中劃分。從中選擇該屬性產生最小Gini指標的子集作為分裂子集。

III 對連續值屬性，考慮每對（排序的）相鄰值之間的中點取作可能的分裂點。可以證明，產生最大信息增益的分裂點必定位于這樣的邊界中。

4 樹剪枝

(1) 當數據中有噪聲或訓練樣例的數量太少時，決策樹歸納算法會出現過度擬合。另外決策樹可能很大，很復雜，難以理解。因此需要修剪決策樹。

(2) 兩種常用的剪枝方法：先剪枝(即提前停止樹增長)，后剪枝。對于前者，精確地估計何時停止樹增長非常困難，一般進行統計測試來估計擴展一個特定的節點是否可能改善質量，如用卡方測試統計顯著性，另外可以使用信息增益，Gini指標及預定義的閾值。后剪枝更常用。

(3) 代價復雜度后剪枝(CART使用)。代價復雜度是樹葉結點個數與錯誤率的函數，使用與訓練和測試集合完全不同的修剪驗證集合來評估。

(4) 悲觀剪枝（C4.5使用）。不需要剪枝集，使用訓練集評估錯誤率，但是假定此估計精度為二項分布，計算標準差，對于一個給定的置信區間，采用下界來估計錯誤率。雖然這種啟發式方法不是統計有效的，但是它在實踐中是有效的。

(5) 規則后修剪。將決策樹轉化為等價的IF-THEN規則，如何提取另述，并嘗試修剪每個規則的每個前件(preconditions)。這樣的好處是使對于決策樹上不同的路徑，關于一個屬性測試的修剪決策可以不同。另外避免了修剪根結點后如何組織其子節點的問題。

(6) 以明確的標準來衡量訓練樣例和決策樹的復雜度，如最小描述長度準則（MDL），而不是根據估計的錯誤率。

問題：

1 關于奧坎姆剃刀的第II個難題，進化產生的內部表示使得學習算法的歸納偏置成為seft-fulfilling prophecy。只因為它改變內部表示比改變學習算法更容易。推理中盡是假設？進化何以成立？

2 證明決策樹學習的時間復雜度為O（n*|D|*log|D|）？

3 信息論中的熵？

4 為什么Gini指標只能用作二元劃分？

5 證明產生最大信息增益的分裂點必定位于相鄰值之間的中點中？

6 MDL準則如何用于樹剪枝？

http://www.cnblogs.com/zhaoqian/archive/2011/01/25/1944717.html

http://www.docin.com/p-113903819.html

決策樹構造法ID

如果學習的任務是對一個大的例子集作分類概念的歸納定義，而這些例子又都是用一些無結構的屬性值對來表示，則可以采用示例學習方法的一個變種──決策樹學習，其代表性的算法是昆蘭（J.R.Quinlan，1986）提出的ID3。

ID3的輸入是描述各種已知類別實例的列表。例子由預先定義的屬性值對來表示。歸納推理產生的結果不是以往討論的那種合取表達式，而是一棵決策樹（也稱判別樹，并可轉而表示為決策規則的一個集合），用它可正確地區分所有給定例子的類屬。

樹中的每一非葉節點對應一個需測試的屬性，每個分叉就是該屬性可能的取值；樹的葉節點則指示一個例子事物的類別。ID3的顯著優點是歸納學習花費的時間和所給任務的困難度（取決于例子個數，用來描述對象的屬性數，所學習概念的復雜度即決策樹的節點數等）僅成線性增長關系。當然，ID3只能處理用屬性-值對表示的例子。

在ID3中, 每一個例子用相同的一組屬性來表示，每一個屬性又有自身的屬性值集，如"顏色"屬性可取值是{紅、綠、蘭}等。構造決策樹的目的是為了對事物作出正確的分類。決策樹形式的分類規則適用于任何的對象集Ｃ。如Ｃ是空的，那么它無需分類，對應的決策樹也為空；如Ｃ中的對象是同一類的，那么決策樹就一個葉節點，即該類名；如果Ｃ集中的對象屬于二個不同的類別，那未我們可以選取一個對象的屬性，隨后按其可能值把Ｃ劃分成一些不相交的子集C1，C2，…，Cn，其中Ci是含有所選屬性的第ｉ個值的那些對象集。對每一個這樣的子集又可以用同樣的策略處理，最后的結果是一棵樹。

下面給出一個關于人分類的例子（對象）集，并預先定義了指定的一組屬性及其可取值：高度{高，矮}，發色{黑色, 紅色，金色}和眼睛{蘭色，棕色}。這里，將人分為兩類，分別以＋、－來指示。

高度　　　　發色　　　眼睛　　　　　類別

───────────────────────────

矮　　　　　黑色　　　蘭色　　　　　　－

高　　　　　黑色　　　蘭色　　　　　　－

矮　　　　　金色　　　蘭色　　　　　　＋

高　　　　　金色　　　棕色　　　　　　－

高　　　　　黑色　　　棕色　　　　　　－

矮　　　　　金色　　　棕色　　　　　　－

高　　　　　金色　　　蘭色　　　　　　＋

高　　　　　紅色　　　蘭色　　　　　　＋

如我們首先選取"發色"為樹的根節點，即可獲得圖6.11所示的決策樹。

相應于"黑色"，"紅色"和"金色"三值都有一個對象子集。隨后我們再測試"金色"這一分支，又按屬性"眼睛"把其所含的對象集劃分成蘭色和棕色二類。至此，所有葉結點相應的對象子集只含同一類的對象，我們就可以用相應的類別名（本例中的+ 和 -）來取代各子集，得到一決策樹，如圖6.12所示。

一個對象所屬類的判別從決策樹的根開始，首先依據根節點指示的屬性（發色），選擇與該對象屬性值相應的分支；然后，以同樣的方式進行下去, 一直到達葉節點。有時判別一個對象的類別，由于從根到葉節點的路徑較短，只要測試少量的屬性。如上例中，若"發色"的值是"黑色"或"紅色"，則對象就可以直接歸屬相應的類別，而不必再去判定其它屬性的取值；若為"金色"，則再測試一次"眼睛"的值（而不必考慮"高度"）就可以進行判別。

若不存在這樣的二個對象:它們在每個屬性上都具有相同的值，卻屬于不同的類別，那么這種生成決策樹的過程是可行的。產生這種歸納學習方法的關鍵在于如何選擇一系列有用的屬性來測試一個對象集，以使生成的決策樹是最小的。ID3采用了香農（Shannon）信息論中的方法以使分類時期望（平均）的測試次數最小。

一個決策樹可看成一個信息源，即給定一個對象，可從決策樹產生一個該對象所屬類別的消息(比如類別"+"或"-")。決策樹的復雜程度與借助這個消息所傳遞的信息量密切相關。若決策樹傳遞的不同類別消息的概率用P+ (對應于"+"類)和P-表示(對應于"-"類)，那么這個消息的期望信息量為:

- P+log2P+ - P-log2P-

對給定的物體集C，我們可以把這概率近似地表示為相對頻率, 此時P+和P-分別等于C中類別為"+"和"-"的對象所占的比例。

從C集對應的決策樹中得到消息的期望信息量記為M(C)，并定義M({})=0。

對于上述例子，C集有八個例子，三個為"+"，五為"-"，則

M(C) = -（3/8）log2（3/8）-（5/8）log2（5/8）= 0.954 bits

圖6.13是一個局部決策樹，A為構造決策樹時下一個可能選取的屬性，Ai為屬性A的值且是互斥的。屬性A將集合C劃分為若干個子集合{C1，C2，...，Cn}。設M(Ci)是值為Ai的子集Ci所對應決策樹的期望信息量，則確定以屬性A作為樹根的決策樹的期望信息量B(C, A)可通過權值平均而得到:

B(C, A)＝∑(A值為Ai的概率) * M(Ci)

同樣我們把Ai的概率用相對比例來代替，即在所有對象中具有Ai值所占的相對比例。

我們希望待選的測試屬性能使決策樹獲得最大的信息增益即M(C)-B(C, A)為最大值。因為M(C)為判別一個對象的類屬所要求的總的期望信息量，B(C,A)為按屬性A構造局部決策樹后還需要的期望信息量。二者的差越大，說明測試這個屬性所能傳遞的信息量越大,則判別的速度也就越快。

例如，圖6.14中，我們選取的屬性為"高度"，對高度值為"高"的分支的所需期望信息量為：