決策樹
優點：計算複雜度不高，輸出結果易於理解，對中間值的缺失不敏感，可以處理不相關特徵數據。 缺點：可能會產生過度匹配問題。 適用數據類型：數值型和標稱型。
本節將一步步地構造決策樹，並會涉及許多有趣的細節。首先我們討論數學上如何使用信息論劃分數據集，然後編寫代碼將理論應用到具體的數據集上，最後編寫代碼構建決策樹。
在構造決策樹時，我們需要解決的第一個問題就是，當前數據集上哪個特徵在劃分數據分類時起決定性作用。為了找到決定性的特徵，劃分出最好的結果，我們必須評估每個特徵。完成測試之後，原始數據集就被劃分為幾個數據子集。這些數據子集會分佈在第一個決策點的所有分支上。如果某個分支下的數據屬於同一類型，則當前無需閱讀的垃圾郵件已經正確地劃分數據分類，無需進一步對數據集進行分割。如果數據子集內的數據不屬於同一類型，則需要重複劃分數據子集的過程。如何劃分數據子集的算法和劃分原始數據集的方法相同，直到所有具有相同類型的數據均在一個數據子集內。
創建分支的偽代碼函數createBranch如下所示：
檢測數據集中的每個子項是否屬於同一分類：
If so return 類標籤；
Else
尋找劃分數據集的最好特徵
劃分數據集
創建分支節點
for 每個劃分的子集
調用函數createBranch並增加返回結果到分支節點中
return 分支節點
上面的偽代碼createBranch是一個遞歸函數，在倒數第二行直接調用了它自己。後面我們將把上面的偽代碼轉換為Python代碼，這裡我們需要進一步瞭解算法是如何劃分數據集的。
決策樹的一般流程
- 收集數據：可以使用任何方法。
- 準備數據：樹構造算法只適用於標稱型數據，因此數值型數據必須離散化。
- 分析數據：可以使用任何方法，構造樹完成之後，我們應該檢查圖形是否符合預期。
- 訓練算法：構造樹的數據結構。
- 測試算法：使用經驗樹計算錯誤率。
- 使用算法：此步驟可以適用於任何監督學習算法，而使用決策樹可以更好地理解數據的內在含義。
一些決策樹算法採用二分法劃分數據，本書並不採用這種方法。如果依據某個屬性劃分數據將會產生4個可能的值，我們將把數據劃分成四塊，並創建四個不同的分支。本書將使用ID3算法劃分數據集，該算法處理如何劃分數據集，何時停止劃分數據集（進一步的信息可以參見http://en.wikipedia.org/wiki/ID3_algorithm）。每次劃分數據集時我們只選取一個特徵屬性，如果訓練集中存在20個特徵，第一次我們選擇哪個特徵作為劃分的參考屬性呢？
表3-1的數據包含5個海洋動物，特徵包括：不浮出水面是否可以生存，以及是否有腳蹼。我們可以將這些動物分成兩類：魚類和非魚類。現在我們想要決定依據第一個特徵還是第二個特徵劃分數據。在回答這個問題之前，我們必須採用量化的方法判斷如何劃分數據。下一小節將詳細討論這個問題。
表3-1 海洋生物數據
不浮出水面是否可以生存 是否有腳蹼 屬於魚類 1 是 是 是 2 是 是 是 3 是 否 否 4 否 是 否 5 否 是 否3.1.1 信息增益
劃分數據集的大原則是：將無序的數據變得更加有序。我們可以使用多種方法劃分數據集，但是每種方法都有各自的優缺點。組織雜亂無章數據的一種方法就是使用信息論度量信息，信息論是量化處理信息的分支科學。我們可以在劃分數據前後使用信息論量化度量信息的內容。
在劃分數據集之前之後信息發生的變化稱為信息增益，知道如何計算信息增益，我們就可以計算每個特徵值劃分數據集獲得的信息增益，獲得信息增益最高的特徵就是最好的選擇。
在可以評測哪種數據劃分方式是最好的數據劃分之前，我們必須學習如何計算信息增益。集合信息的度量方式稱為香農熵或者簡稱為熵，這個名字來源於信息論之父克勞德·香農。
克勞德·香農
克勞德·香農被公認為是二十世紀最聰明的人之一，威廉·龐德斯通在其2005年出版的《財富公式》一書中是這樣描寫克勞德·香農的：
「貝爾實驗室和MIT有很多人將香農和愛因斯坦相提並論，而其他人則認為這種對比是不公平的——對香農是不公平的。」1
1. 威廉·龐德斯通的《財富公式：擊敗賭場和華爾街的不為人知的科學投注系統》(Fortune's Formula: The Untold Story of the Scientific Betting System that Beat the Casi- nos and Wall Street)[Hill and Wang，2005]第15頁
如果看不明白什麼是信息增益（information gain）和熵（entropy），請不要著急——它們自誕生的那一天起，就注定會令世人十分費解。克勞德·香農寫完信息論之後，約翰·馮·諾依曼建議使用「熵」這個術語，因為大家都不知道它是什麼意思。
熵定義為信息的期望值，在明晰這個概念之前，我們必須知道信息的定義。如果待分類的事務可能劃分在多個分類之中，則符號xi 的信息定義為
其中p(xi)是選擇該分類的概率。
為了計算熵，我們需要計算所有類別所有可能值包含的信息期望值，通過下面的公式得到：
其中n是分類的數目。
下面我們將學習如何使用Python計算信息熵，創建名為trees.py的文件，將程序清單3-1的代碼內容錄入到trees.py文件中，此代碼的功能是計算給定數據集的熵。
程序清單3-1 計算給定數據集的香農熵
from math import log
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
#❶ （以下五行）為所有可能分類創建字典
for featVec in dataSet:
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys:
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
#❷ 以2為底求對數
shannonEnt -= prob * log(prob,2)
return shannonEnt
程序清單3-1的代碼非常簡單。首先，計算數據集中實例的總數。我們也可以在需要時再計算這個值，但是由於代碼中多次用到這個值，為了提高代碼效率，我們顯式地聲明一個變量保存實例總數。然後，創建一個數據字典，它的鍵值是最後一列的數值❶。如果當前鍵值不存在，則擴展字典並將當前鍵值加入字典。每個鍵值都記錄了當前類別出現的次數。最後，使用所有類標籤的發生頻率計算類別出現的概率。我們將用這個概率計算香農熵❷，統計所有類標籤發生的次數。下面我們看看如何使用熵劃分數據集。
在trees.py文件中，我們可以利用createDataSet函數得到表3-1所示的簡單魚鑒定數據集，你可以輸入自己的createDataSet函數：
def createDataSet:
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
labels = ['no surfacing','flippers']
return dataSet, labels
在Python命令提示符下輸入下列命令：
>>> reload(trees.py)
>>> myDat,labels=trees.createDataSet
>>> myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.calcShannonEnt(myDat)
0.97095059445466858
熵越高，則混合的數據也越多，我們可以在數據集中添加更多的分類，觀察熵是如何變化的。這裡我們增加第三個名為maybe的分類，測試熵的變化：
>>> myDat[0][-1]='maybe'
>>> myDat
[[1, 1, 'maybe'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.calcShannonEnt(myDat)
1.3709505944546687
得到熵之後，我們就可以按照獲取最大信息增益的方法劃分數據集，下一節我們將具體學習如何劃分數據集以及如何度量信息增益。
另一個度量集合無序程度的方法是基尼不純度2 （Gini impurity），簡單地說就是從一個數據集中隨機選取子項，度量其被錯誤分類到其他分組裡的概率。本書不採用基尼不純度方法，這裡就不再做進一步的介紹。下面我們將學習如何劃分數據集，並創建決策樹。
2. 要瞭解更多信息，請參考 Pan-Ning Tan, Vipin Kumar and Michael Steinbach , Introduction to Data Mining. Pearson Education (Addison-Wesley, 2005), 158.
3.1.2 劃分數據集
上節我們學習了如何度量數據集的無序程度，分類算法除了需要測量信息熵，還需要劃分數據集，度量劃分數據集的熵，以便判斷當前是否正確地劃分了數據集。我們將對每個特徵劃分數據集的結果計算一次信息熵，然後判斷按照哪個特徵劃分數據集是最好的劃分方式。想像一個分佈在二維空間的數據散點圖，需要在數據之間劃條線，將它們分成兩部分，我們應該按照x軸還是y軸劃線呢？答案就是本節講述的內容。
要劃分數據集，打開文本編輯器，在trees.py文件中輸入下列的代碼：
程序清單3-2 按照給定特徵劃分數據集
def splitDataSet(dataSet, axis, value):
#❶ 創建新的list對像
retDataSet =
for featVec in dataSet:
if featVec[axis] == value:
#❷ （以下三行）抽取
reducedFeatVec = featVec[:axis]
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
程序清單3-2的代碼使用了三個輸入參數：待劃分的數據集、劃分數據集的特徵、需要返回的特徵的值。需要注意的是，Python語言不用考慮內存分配問題。Python語言在函數中傳遞的是列表的引用，在函數內部對列表對象的修改，將會影響該列表對象的整個生存週期。為了消除這個不良影響，我們需要在函數的開始聲明一個新列表對象。因為該函數代碼在同一數據集上被調用多次，為了不修改原始數據集，創建一個新的列表對像❶。數據集這個列表中的各個元素也是列表，我們要遍歷數據集中的每個元素，一旦發現符合要求的值，則將其添加到新創建的列表中。在if語句中，程序將符合特徵的數據抽取出來❷。後面講述得更簡單，這裡我們可以這樣理解這段代碼：當我們按照某個特徵劃分數據集時，就需要將所有符合要求的元素抽取出來。代碼中使用了Python語言list類型自帶的extend和append方法。這兩個方法功能類似，但是在處理多個列表時，這兩個方法的處理結果是完全不同的。
假定存在兩個列表，a和b：
>>> a=[1,2,3]
>>> b=[4,5,6]
>>> a.append(b)
>>> a
[1, 2, 3, [4, 5, 6]]
如果執行a.append(b)，則列表得到了第四個元素，而且第四個元素也是一個列表。然而如果使用extend方法：
>>> a=[1,2,3]
>>> a.extend(b)
>>> a
[1, 2, 3, 4, 5, 6]
則得到一個包含a和b所有元素的列表。
我們可以在前面的簡單樣本數據上測試函數splitDataSet。首先還是要將程序清單3.2的代碼增加到trees.py文件中，然後在Python命令提示符內輸入下述命令：
>>> reload(trees)
<module 'trees' from 'trees.pyc'>
>>> myDat,labels=trees.createDataSet
>>> myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.splitDataSet(myDat,0,1) [[1, 'yes'], [1, 'yes'], [0, 'no']]
>>> trees.splitDataSet(myDat,0,0) [[1, 'no'], [1, 'no']]
接下來我們將遍歷整個數據集，循環計算香農熵和splitDataSet函數，找到最好的特徵劃分方式。熵計算將會告訴我們如何劃分數據集是最好的數據組織方式。
打開文本編輯器，在trees.py文件中輸入下面的程序代碼。
程序清單3-3 選擇最好的數據集劃分方式
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0; bestFeature = -1
for i in range(numFeatures):
#❶ （以下兩行）創建唯一的分類標籤列表
featList = [example[i] for example in dataSet]
uniqueVals = set(featList)
newEntropy = 0.0
#❷ （以下五行）計算每種劃分方式的信息熵
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
infoGain = baseEntropy - newEntropy
if (infoGain > bestInfoGain):
#❸ 計算最好的信息增益
bestInfoGain = infoGain
bestFeature = i
return bestFeature
程序清單3-3給出了函數chooseBestFeatureToSplit的完整代碼，該函數實現選取特徵，劃分數據集，計算得出最好的劃分數據集的特徵。函數chooseBestFeatureToSplit使用了程序清單3-1和3-2中的函數。在函數中調用的數據需要滿足一定的要求：第一個要求是，數據必須是一種由列表元素組成的列表，而且所有的列表元素都要具有相同的數據長度；第二個要求是，數據的最後一列或者每個實例的最後一個元素是當前實例的類別標籤。數據集一旦滿足上述要求，我們就可以在函數的第一行判定當前數據集包含多少特徵屬性。我們無需限定list中的數據類型，它們既可以是數字也可以是字符串，並不影響實際計算。
在開始劃分數據集之前，程序清單3-3的第3行代碼計算了整個數據集的原始香農熵，我們保存最初的無序度量值，用於與劃分完之後的數據集計算的熵值進行比較。第1個for循環遍歷數據集中的所有特徵。使用列表推導（List Comprehension）來創建新的列表，將數據集中所有第i個特徵值或者所有可能存在的值寫入這個新列表中❶。然後使用Python語言原生的集合（set）數據類型。集合數據類型與列表類型相似，不同之處僅在於集合類型中的每個值互不相同。從列表中創建集合是Python語言得到列表中唯一元素值的最快方法。
遍歷當前特徵中的所有唯一屬性值，對每個特徵劃分一次數據集❷，然後計算數據集的新熵值，並對所有唯一特徵值得到的熵求和。信息增益是熵的減少或者是數據無序度的減少，大家肯定對於將熵用於度量數據無序度的減少更容易理解。最後，比較所有特徵中的信息增益，返回最好特徵劃分的索引值❸。
現在我們可以測試上面代碼的實際輸出結果，首先將程序清單3-3的內容輸入到文件trees.py中，然後在Python命令提示符下輸入下列命令：
>>> reload(trees)
<module 'trees' from 'trees.py'>
>>> myDat,labels=trees.createDataSet
>>> trees.chooseBestFeatureToSplit(myDat)
0
>>> myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
代碼運行結果告訴我們，第0個特徵是最好的用於劃分數據集的特徵。結果是否正確呢？這個結果又有什麼實際意義呢？數據集中的數據來源於表3-1，讓我們回頭再看一下表1-1或者變量myDat中的數據。如果我們按照第一個特徵屬性劃分數據，也就是說第一個特徵是1的放在一個組，第一個特徵是0的放在另一個組，數據一致性如何？按照上述的方法劃分數據集，第一個特徵為1的海洋生物分組將有兩個屬於魚類，一個屬於非魚類；另一個分組則全部屬於非魚類。如果按照第二個特徵分組，結果又是怎麼樣呢？第一個海洋動物分組將有兩個屬於魚類，兩個屬於非魚類；另一個分組則只有一個非魚類。第一種劃分很好地處理了相關數據。如果不相信目測結果，讀者可以使用程序清單3-1的calcShannonEntropy函數測試不同特徵分組的輸出結果。
本節我們學習了如何度量數據集的信息熵，如何有效地劃分數據集，下一節我們將介紹如何將這些函數功能放在一起，構建決策樹。
3.1.3 遞歸構建決策樹
目前我們已經學習了從數據集構造決策樹算法所需要的子功能模塊，其工作原理如下：得到原始數據集，然後基於最好的屬性值劃分數據集，由於特徵值可能多於兩個，因此可能存在大於兩個分支的數據集劃分。第一次劃分之後，數據將被向下傳遞到樹分支的下一個節點，在這個節點上，我們可以再次劃分數據。因此我們可以採用遞歸的原則處理數據集。
遞歸結束的條件是：程序遍歷完所有劃分數據集的屬性，或者每個分支下的所有實例都具有相同的分類。如果所有實例具有相同的分類，則得到一個葉子節點或者終止塊。任何到達葉子節點的數據必然屬於葉子節點的分類，參見圖3-2所示。
圖3-2 劃分數據集時的數據路徑
第一個結束條件使得算法可以終止，我們甚至可以設置算法可以劃分的最大分組數目。後續章節還會介紹其他決策樹算法，如C4.5和CART，這些算法在運行時並不總是在每次劃分分組時都會消耗特徵。由於特徵數目並不是在每次劃分數據分組時都減少，因此這些算法在實際使用時可能引起一定的問題。目前我們並不需要考慮這個問題，只需要在算法開始運行前計算列的數目，查看算法是否使用了所有屬性即可。如果數據集已經處理了所有屬性，但是類標籤依然不是唯一的，此時我們需要決定如何定義該葉子節點，在這種情況下，我們通常會採用多數表決的方法決定該葉子節點的分類。
打開文本編輯器，在增加下面的函數之前，在trees.py文件頂部增加一行代碼：import operator，然後添加下面的代碼到trees.py文件中：
def majorityCnt(classList):
classCount={}
for vote in classList:
if vote not in classCount.keys: classCount[vote] = 0
classCount[vote] += 1
sortedClassCount=sorted(classCount.iteritems,
key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
上面的代碼與第2章classify0部分的投票表決代碼非常類似，該函數使用分類名稱的列表，然後創建鍵值為classList中唯一值的數據字典，字典對像存儲了classList中每個類標籤出現的頻率，最後利用operator操作鍵值排序字典，並返回出現次數最多的分類名稱。
在文本編輯器中打開trees.py文件，添加下面的程序代碼。
程序清單3-4 創建樹的函數代碼
def createTree(dataSet,labels):
classList = [example[-1] for example in dataSet]
#❶ （以下兩行）類別完全相同則停止繼續劃分
if classList.count(classList[0]) == len(classList):
return classList[0]
#❷ （以下兩行）遍歷完所有特徵時返回出現次數最多的
if len(dataSet[0]) == 1:
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel:{}}
#❸ 得到列表包含的所胡屬性值
del(labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:]
myTree[bestFeatLabel][value] = createTree(splitDataSet
(dataSet, bestFeat, value),subLabels)
return myTree
程序清單3-4的代碼使用兩個輸入參數：數據集和標籤列表。標籤列表包含了數據集中所有特徵的標籤，算法本身並不需要這個變量，但是為了給出數據明確的含義，我們將它作為一個輸入參數提供。此外，前面提到的對數據集的要求這裡依然需要滿足。上述代碼首先創建了名為classList的列表變量，其中包含了數據集的所有類標籤。遞歸函數的第一個停止條件是所有的類標籤完全相同，則直接返回該類標籤❶。遞歸函數的第二個停止條件是使用完了所有特徵，仍然不能將數據集劃分成僅包含唯一類別的分組❷。由於第二個條件無法簡單地返回唯一的類標籤，這裡使用程序清單3-3的函數挑選出現次數最多的類別作為返回值。
下一步程序開始創建樹，這裡使用Python語言的字典類型存儲樹的信息，當然也可以聲明特殊的數據類型存儲樹，但是這裡完全沒有必要。字典變量myTree存儲了樹的所有信息，這對於其後繪製樹形圖非常重要。當前數據集選取的最好特徵存儲在變量bestFeat中，得到列表包含的所有屬性值❸。這部分代碼與程序清單3-3中的部分代碼類似，這裡就不再進一步解釋了。
最後代碼遍歷當前選擇特徵包含的所有屬性值，在每個數據集劃分上遞歸調用函數createTree，得到的返回值將被插入到字典變量myTree中，因此函數終止執行時，字典中將會嵌套很多代表葉子節點信息的字典數據。在解釋這個嵌套數據之前，我們先看一下循環的第一行subLabels = labels[:]，這行代碼複製了類標籤，並將其存儲在新列表變量subLabels中。之所以這樣做，是因為在Python語言中函數參數是列表類型時，參數是按照引用方式傳遞的。為了保證每次調用函數createTree時不改變原始列表的內容，使用新變量subLabels代替原始列表。
現在我們可以測試上面代碼的實際輸出結果，首先將程序清單3-4的內容輸入到文件trees.py中，然後在Python命令提示符下輸入下列命令：
>>> reload(trees)
<module 'trees' from 'trees.pyc'>
>>> myDat,labels=trees.createDataSet
>>> myTree = trees.createTree(myDat,labels)
>>> myTree
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
變量myTree包含了很多代表樹結構信息的嵌套字典，從左邊開始，第一個關鍵字no surfacing是第一個劃分數據集的特徵名稱，該關鍵字的值也是另一個數據字典。第二個關鍵字是no surfacing特徵劃分的數據集，這些關鍵字的值是no surfacing節點的子節點。這些值可能是類標籤，也可能是另一個數據字典。如果值是類標籤，則該子節點是葉子節點；如果值是另一個數據字典，則子節點是一個判斷節點，這種格式結構不斷重複就構成了整棵樹。本節的例子中，這棵樹包含了3個葉子節點以及2個判斷節點。
本節講述了如何正確地構造樹，下一節將介紹如何繪製圖形，方便我們正確理解數據信息的內在含義。