這一篇文章中撤防，討論一種被廣泛使用的分類算法——決策樹（decision tree）耸序。決策樹的優(yōu)勢在于構造過程不需要任何領域知識或參數(shù)設置愚墓，因此在實際應用中决左，對于探測式的知識發(fā)現(xiàn)琅豆，決策樹更加適用朱浴。

決策樹案例

通俗來說七蜘，決策樹分類的思想類似于找對象∥执郑現(xiàn)想象一個女孩的母親要給這個女孩介紹男朋友柄粹，于是有了下面的對話：

女兒：多大年紀了喘鸟？

母親：26。

女兒：長的帥不帥驻右？

母親：挺帥的什黑。

女兒：收入高不？

母親：不算很高堪夭，中等情況愕把。

女兒：是公務員不拣凹？

母親：是，在稅務局上班呢恨豁。

女兒：那好嚣镜，我去見見。

這個女孩的決策過程就是典型的分類樹決策橘蜜。相當于通過年齡菊匿、長相、收入和是否公務員對將男人分為兩個類別：見和不見计福。假設這個女孩對男人的要求是：30歲以下跌捆、長相中等以上并且是高收入者或中等以上收入的公務員，那么這個可以用下圖表示女孩的決策邏輯象颖。

上圖完整表達了這個女孩決定是否見一個約會對象的策略佩厚，其中綠色節(jié)點表示判斷條件，橙色節(jié)點表示決策結果力麸，箭頭表示在一個判斷條件在不同情況下的決策路徑可款，圖中紅色箭頭表示了上面例子中女孩的決策過程。

這幅圖基本可以算是一顆決策樹克蚂，說它“基本可以算”是因為圖中的判定條件沒有量化，如收入高中低等等筋讨，還不能算是嚴格意義上的決策樹埃叭，如果將所有條件量化，則就變成真正的決策樹了悉罕。

有了上面直觀的認識赤屋，我們可以正式定義決策樹了：

決策樹（decision tree）是一個樹結構（可以是二叉樹或非二叉樹）。其每個非葉節(jié)點表示一個特征屬性上的測試壁袄，每個分支代表這個特征屬性在某個值域上的輸出类早，而每個葉節(jié)點存放一個類別。使用決策樹進行決策的過程就是從根節(jié)點開始嗜逻，測試待分類項中相應的特征屬性涩僻，并按照其值選擇輸出分支，直到到達葉子節(jié)點栈顷，將葉子節(jié)點存放的類別作為決策結果逆日。

可以看到，決策樹的決策過程非常直觀萄凤，容易被人理解室抽。目前決策樹已經成功運用于醫(yī)學、制造產業(yè)靡努、天文學坪圾、分支生物學以及商業(yè)等諸多領域晓折。知道了決策樹的定義以及其應用方法，下面介紹決策樹的構造算法兽泄。

決策樹的構造

不同于貝葉斯算法已维，決策樹的構造過程不依賴領域知識，它使用屬性選擇度量來選擇將元組最好地劃分成不同的類的屬性已日。所謂決策樹的構造就是進行屬性選擇度量確定各個特征屬性之間的拓撲結構垛耳。

構造決策樹的關鍵步驟是分裂屬性。所謂分裂屬性就是在某個節(jié)點處按照某一特征屬性的不同劃分構造不同的分支飘千，其目標是讓各個分裂子集盡可能地“純”堂鲜。盡可能“純”就是盡量讓一個分裂子集中待分類項屬于同一類別。分裂屬性分為三種不同的情況：

1护奈、屬性是離散值且不要求生成二叉決策樹缔莲。此時用屬性的每一個劃分作為一個分支。

2霉旗、屬性是離散值且要求生成二叉決策樹痴奏。此時使用屬性劃分的一個子集進行測試，按照“屬于此子集”和“不屬于此子集”分成兩個分支厌秒。

3读拆、屬性是連續(xù)值。此時確定一個值作為分裂點split_point鸵闪，按照>split_point和<=split_point生成兩個分支檐晕。

構造決策樹的關鍵性內容是進行屬性選擇度量，屬性選擇度量是一種選擇分裂準則蚌讼，是將給定的類標記的訓練集合的數(shù)據(jù)劃分D“最好”地分成個體類的啟發(fā)式方法辟灰，它決定了拓撲結構及分裂點split_point的選擇。

屬性選擇度量算法有很多篡石，一般使用自頂向下遞歸分治法芥喇，并采用不回溯的貪心策略。這里介紹ID3和c4.5兩種常用算法凰萨。

ID3算法

從信息論知識中我們直到继控，期望信息越小，信息增益越大沟蔑，從而純度越高湿诊。所以ID3算法的核心思想就是以信息增益度量屬性選擇，選擇分裂后信息增益最大的屬性進行分裂瘦材。下面先定義幾個要用到的概念厅须。

設D為用類別對訓練元組進行的劃分，則D的熵表示為：

其中pi表示第i個類別在整個訓練元組中出現(xiàn)的概率食棕，可以用屬于此類別元素的數(shù)量除以訓練元組元素總數(shù)量作為估計朗和。熵的實際意義表示是D中元組的類標號所需要的平均信息量错沽。

現(xiàn)在我們假設將訓練元組D按屬性A進行劃分，則A對D劃分的期望信息為：

而信息增益即為兩者的差值：

ID3算法就是在每次需要分裂時眶拉，計算每個屬性的增益率千埃，然后選擇增益率最大的屬性進行分裂。下面我們繼續(xù)用SNS社區(qū)中不真實賬號檢測的例子說明如何使用ID3算法構造決策樹忆植。為了簡單起見放可，我們假設訓練集合包含10個元素：

其中s、m和l分別表示小朝刊、中和大耀里。

設L、F拾氓、H和R表示日志密度冯挎、好友密度、是否使用真實頭像和賬號是否真實咙鞍，下面計算各屬性的信息增益房官。

因此日志密度的信息增益是0.276。

用同樣方法得到H和F的信息增益分別為0.033和0.553续滋。

因為F具有最大的信息增益翰守，所以第一次分裂選擇F為分裂屬性，分裂后的結果如下圖表示：

在上圖的基礎上吃粒，再遞歸使用這個方法計算子節(jié)點的分裂屬性潦俺，最終就可以得到整個決策樹。

上面為了簡便徐勃，將特征屬性離散化了，其實日志密度和好友密度都是連續(xù)的屬性早像。對于特征屬性為連續(xù)值僻肖，可以如此使用ID3算法：先將D中元素按照特征屬性排序，則每兩個相鄰元素的中間點可以看做潛在分裂點卢鹦，從第一個潛在分裂點開始臀脏，分裂D并計算兩個集合的期望信息，具有最小期望信息的點稱為這個屬性的最佳分裂點冀自，其信息期望作為此屬性的信息期望揉稚。

C4.5算法

ID3算法存在一個問題，就是偏向于多值屬性熬粗，例如搀玖，如果存在唯一標識屬性ID，則ID3會選擇它作為分裂屬性驻呐，這樣雖然使得劃分充分純凈灌诅，但這種劃分對分類幾乎毫無用處芳来。ID3的后繼算法C4.5使用增益率的信息增益擴充，試圖克服這個偏倚猜拾。

C4.5算法首先定義了“分裂信息”即舌，其定義可以表示成：

其中各符號意義與ID3算法相同，然后挎袜，增益率被定義為：

C4.5選擇具有最大增益率的屬性作為分裂屬性顽聂，其具體應用與ID3類似，不再贅述盯仪。

如果屬性用完了怎么辦

在決策樹構造過程中可能會出現(xiàn)這種情況：所有屬性都作為分裂屬性用光了紊搪，但有的子集還不是純凈集，即集合內的元素不屬于同一類別磨总。在這種情況下嗦明，由于沒有更多信息可以使用了，一般對這些子集進行“多數(shù)表決”蚪燕，即使用此子集中出現(xiàn)次數(shù)最多的類別作為此節(jié)點類別娶牌，然后將此節(jié)點作為葉子節(jié)點。

關于剪枝

在實際構造決策樹時馆纳，通常要進行剪枝诗良，這時為了處理由于數(shù)據(jù)中的噪聲和離群點導致的過分擬合問題。剪枝有兩種：

先剪枝——在構造過程中鲁驶，當某個節(jié)點滿足剪枝條件鉴裹，則直接停止此分支的構造。

后剪枝——先構造完成完整的決策樹径荔，再通過某些條件遍歷樹進行剪枝脆霎。

流程圖形式的決策樹

上圖流程圖就是一個假想的郵件分類系統(tǒng)決策樹，正方形代表判斷模塊睛蛛，橢圓形代表終止模塊鹦马，表示已經得出結論忆肾，可以終止運行。判斷模塊引出的左右箭頭稱為分支客冈，它可以到達另一個判斷模塊或者終止模塊旭从。決策樹的主要優(yōu)勢在于數(shù)據(jù)形式非常容易理解。

優(yōu)點

計算復雜度不高遇绞，對中間值的缺失不敏感，可以處理不相干特征數(shù)據(jù)摹闽，輸出結果易于理解。

缺點

可能會產生過度匹配問題澜汤。

適用數(shù)據(jù)類型

數(shù)值型跟標稱型

ID3算法python2實現(xiàn)

from math import log

import operator

#def createDataSet():自己創(chuàng)建的數(shù)據(jù)舵匾，可作實驗用

#dataSet = [[1, 1, 'yes'],

# [1, 1, 'yes'],

# [1, 0, 'no'],

# [0, 1, 'no'],

# [0, 1, 'no']]

# labels = ['no surfacing','flippers']

#print dataSet

#change to discrete values

#return dataSet, labels

def loadDataSet(fileName): #general function to parse tab -delimited floats

dataMat = [] #assume last column is target value

fr = open(fileName)

for line in fr.readlines():

curLine = line.strip().split(',')

fltLine = list(curLine) #map all elements to float()

dataMat.append(fltLine)

return dataMat

#def createDataSet():

#dataSet = [[1, 1, 'yes'],

#[1, 1, 'yes'],

#[1, 0, 'no'],

#[0, 1, 'no'],

#[0, 1, 'no']]

#labels = ['no surfacing','flippers']

#print dataSet

#change to discrete values

#return dataSet, labels

def calcShannonEnt(dataSet):#計算給定數(shù)據(jù)集的香農熵

numEntries = len(dataSet)#計算數(shù)據(jù)集中實例的總數(shù)

#print numEntries

labelCounts = {}#創(chuàng)建一個數(shù)據(jù)字典

for featVec in dataSet: #the the number of unique elements and their occurance

currentLabel = featVec[-1]#鍵值是最后一列數(shù)值

#print currentLabel

if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0#如果鍵值不存在坐梯，則擴展字典并將當前鍵值加入字典

labelCounts[currentLabel] += 1#當前鍵值加入字典

#print labelCounts

shannonEnt = 0.0

for key in labelCounts:

prob = float(labelCounts[key])/numEntries# 使用所有類標簽的發(fā)生概率計算類別出現(xiàn)的概率

#print prob

shannonEnt -= prob * log(prob,2) #log base 2 用這個概率計算香農熵

#print shannonEnt

return shannonEnt

def splitDataSet(dataSet, axis, value):#劃分數(shù)據(jù)集，dataSet為待劃分的數(shù)據(jù)集谎替，axis為劃分數(shù)據(jù)集的特征蹋辅，value為特征的返回值

retDataSet = []#創(chuàng)建新的list對象

for featVec in dataSet:

#print featVec

if featVec[axis] == value:#將符合特征的數(shù)據(jù)抽取出來

reducedFeatVec = featVec[:axis] #chop out axis used for splitting

#print reducedFeatVec

reducedFeatVec.extend(featVec[axis+1:])#extend()函數(shù)只接受一個列表作為參數(shù)侦另，并將該參數(shù)的每個元素都添加到原有的列表中

#print reducedFeatVec

retDataSet.append(reducedFeatVec)#append()向列表的尾部添加一個元素，任意弃锐，可以是tuple

return retDataSet

def chooseBestFeatureToSplit(dataSet):#遍歷整個數(shù)據(jù)集殿托，循環(huán)計算香農熵和splitDataSet（）函數(shù)，找到最好的劃分方式

numFeatures = len(dataSet[0]) - 1 #the last column is used for the labels判斷當前數(shù)據(jù)集包含多少特征屬性

baseEntropy = calcShannonEnt(dataSet)#計算整個數(shù)據(jù)集的原始香農熵，保存最初的無序度量值唾戚，用于與劃分完之后的數(shù)據(jù)集計算的熵值進行比較

bestInfoGain = 0.0; bestFeature = -1

for i in range(numFeatures): #iterate over all the features 遍歷數(shù)據(jù)集中的所有特征

featList = [example[i] for example in dataSet]#create a list of all the examples of this feature使用列表推導創(chuàng)建新的列表

uniqueVals = set(featList) #get a set of unique values將數(shù)據(jù)集中所有可能存在的值寫入featlist中待诅，并從列表中創(chuàng)建集合

newEntropy = 0.0

for value in uniqueVals:#遍歷當前特征值中的所有唯一屬性值，

subDataSet = splitDataSet(dataSet, i, value)#對每個特征劃分一次數(shù)據(jù)集

prob = len(subDataSet)/float(len(dataSet))

newEntropy += prob * calcShannonEnt(subDataSet) #計算數(shù)據(jù)集的新熵值募书，并對所有唯一特征值得到的熵求和

infoGain = baseEntropy - newEntropy #calculate the info gain; ie reduction in entropy#信息增益

if (infoGain > bestInfoGain): #compare this to the best gain so far#比較所有特征中的信息增益

bestInfoGain = infoGain #if better than current best, set to best

bestFeature = i#返回最好特征劃分的索引值

return bestFeature #returns an integer

def majorityCnt(classList):

classCount={}#創(chuàng)建鍵值為classList中唯一值的數(shù)據(jù)字典莹捡，字典對象存儲了classList中每個類標簽現(xiàn)的頻率

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)#利用operator操作鍵值排序字典

return sortedClassCount[0][0]#返回出現(xiàn)次數(shù)最多的分類名稱

def createTree(dataSet,labels):#創(chuàng)建樹的函數(shù)代碼

classList = [example[-1] for example in dataSet]#創(chuàng)建了名為classList的列表變量，包含所有類標簽

if classList.count(classList[0]) == len(classList): #

return classList[0]#stop splitting when all of the classes are equal

if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet

return majorityCnt(classList)

bestFeat = chooseBestFeatureToSplit(dataSet)

bestFeatLabel = labels[bestFeat]

myTree = {bestFeatLabel:{}}#存儲了樹的所有信息

del(labels[bestFeat])#當前數(shù)據(jù)集選取的最好特征存儲在變量bestFeat中齿椅，

featValues = [example[bestFeat] for example in dataSet]#得到列表包含的所有屬性值

uniqueVals = set(featValues)

for value in uniqueVals:#遍歷當前選擇特征包含的所有屬性值

subLabels = labels[:] #copy all of labels, so trees don't mess up existing labels為了保證每次調用函數(shù)createtree()時不改變原始列表的內容启泣，使用新變量subLabels代替原始列表

myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)#遞歸調用函數(shù)cteatetree()得到的返回值插入到字典變量mytree中

return myTree

def classify(inputTree,featLabels,testVec):#遞歸函數(shù)寥茫，

firstStr = inputTree.keys()[0]

secondDict = inputTree[firstStr]

featIndex = featLabels.index(firstStr)#使用index查找當前列表中第一個匹配firstStr變量的元素

key = testVec[featIndex]

valueOfFeat = secondDict[key]

if isinstance(valueOfFeat, dict): #如果到達葉子節(jié)點

classLabel = classify(valueOfFeat, featLabels, testVec)#返回當前節(jié)點的分類標簽

else: classLabel = valueOfFeat

return classLabel

def storeTree(inputTree,filename):#決策樹分類器的存儲

import pickle#pickle序列化對象可以在磁盤上保存對象，并在需要時讀出來

fw = open(filename,'w')

pickle.dump(inputTree,fw)

fw.close()

def grabTree(filename):

import pickle

fr = open(filename)

return pickle.load(fr)

import matplotlib.pyplot as plt

decisionNode = dict(boxstyle="sawtooth", fc="0.8")

leafNode = dict(boxstyle="round4", fc="0.8")

arrow_args = dict(arrowstyle="<-")

def getNumLeafs(myTree):#遍歷整顆樹芭梯，累計葉子節(jié)點的個數(shù)膝迎，并返回數(shù)值

numLeafs = 0

firstStr = myTree.keys()[0]#第一個關鍵字是以第一次劃分數(shù)據(jù)集的類別標簽

secondDict = myTree[firstStr]#表示子節(jié)點的數(shù)值

for key in secondDict.keys():#遍歷整顆樹的所有子節(jié)點

if type(secondDict[key]).__name__=='dict':#test to see if the nodes are dictonaires, if not they are leaf nodes type()函數(shù)判斷子節(jié)點是否為字典類型限次，如果子節(jié)點是字典類型

numLeafs += getNumLeafs(secondDict[key])#則該節(jié)點是一個判斷節(jié)點，遞歸調用getNumLeafs()函數(shù)

else: numLeafs +=1

return numLeafs

def getTreeDepth(myTree):#遍歷過程中遇到判斷節(jié)點的個數(shù)

maxDepth = 0

firstStr = myTree.keys()[0]

secondDict = myTree[firstStr]

for key in secondDict.keys():

if type(secondDict[key]).__name__=='dict':#test to see if the nodes are dictonaires, if not they are leaf nodes

thisDepth = 1 + getTreeDepth(secondDict[key])

else: thisDepth = 1

if thisDepth > maxDepth: maxDepth = thisDepth

return maxDepth

def plotNode(nodeTxt, centerPt, parentPt, nodeType):#執(zhí)行實際的繪圖功能

createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',

xytext=centerPt, textcoords='axes fraction',

va="center", ha="center", bbox=nodeType, arrowprops=arrow_args )#全局繪圖區(qū)

def plotMidText(cntrPt, parentPt, txtString):#計算子節(jié)點與父節(jié)點的中間位置费尽，在父節(jié)點間填充文本信息

xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]

yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]

createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)

def plotTree(myTree, parentPt, nodeTxt):#if the first key tells you what feat was split on計算寬與高

numLeafs = getNumLeafs(myTree) #this determines the x width of this tree計算樹的寬

depth = getTreeDepth(myTree)#計算樹的高

firstStr = myTree.keys()[0] #the text label for this node should be this

cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)

plotMidText(cntrPt, parentPt, nodeTxt)#標記子節(jié)點屬性值

plotNode(firstStr, cntrPt, parentPt, decisionNode)

secondDict = myTree[firstStr]

plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD

for key in secondDict.keys():

if type(secondDict[key]).__name__=='dict':#test to see if the nodes are dictonaires, if not they are leaf nodes

plotTree(secondDict[key],cntrPt,str(key)) #recursion

else: #it's a leaf node print the leaf node

plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW

plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)

plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))

plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD

#if you do get a dictonary you know it's a tree, and the first element will be another dict

def createPlot(inTree):#第一個版本的函數(shù)

fig = plt.figure(1, facecolor='white')

fig.clf()

axprops = dict(xticks=[], yticks=[])

createPlot.ax1 = plt.subplot(111, frameon=False, **axprops) #no ticks

createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses

plotTree.totalW = float(getNumLeafs(inTree))#全局變量plotTree.totalW存儲樹的寬度

plotTree.totalD = float(getTreeDepth(inTree))#全局變量plotTree.totalD存儲樹的深度

plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;#使用plotTree.totalW，plotTree.totalD計算樹節(jié)點的擺放位置柏卤，這樣可以將樹繪制在水平方向和垂直方向的中心位置

plotTree(inTree, (0.5,1.0), '')

plt.show()

#def createPlot():

#fig = plt.figure(1, facecolor='white')

#fig.clf()

#createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses

#plotNode('a decision node', (0.5, 0.1), (0.1, 0.5), decisionNode)

#plotNode('a leaf node', (0.8, 0.1), (0.3, 0.8), leafNode)

#plt.show()

def retrieveTree(i):#輸出預先存儲的樹信息匀油，避免每次測試都要從數(shù)據(jù)集中創(chuàng)建樹的麻煩,該函數(shù)主要用于測試，返回預定義的樹結構

listOfTrees =[{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}},

{'no surfacing': {0: 'no', 1: {'flippers': {0: {'head': {0: 'no', 1: 'yes'}}, 1: 'no'}}}}

]

return listOfTrees[i]

if __name__ == "__main__":

myMat=loadDataSet('C:\Users\HZF\Desktop\credit.txt')

labels=['A1','A2','A3','A4','A5','A6','A7','A8','A9','A10','A11','A12','A13','A14','A15']

myTree=createTree(myMat,labels)

print myTree

#numLeafs=getNumLeafs(myTree)

maxDepth=getTreeDepth(myTree)

print maxDepth

createPlot(myTree)

#classLabel=classify(myTree,labels,[1,1])

#labels=['age','prescript','astigmatic','tearRate']

#storeTree(myTree,'C:/Users/HZF/Desktop/machinelearninginaction/Ch03/classifierStorage.txt')

#pickle.load(fr)=grabTree('C:/Users/HZF/Desktop/machinelearninginaction/Ch03/classifierStorage.txt')

#print pickle.load(fr)

#print numLeafs

#print maxDepth

#print classLabel

#myMat,labels=createDataSet()

#myMat[0][-1]='maybe'

#print myMat

#shannonEnt=calcShannonEnt(myMat)

#print shannonEnt

#retDataSet=splitDataSet(myMat, 0, 0)

#print retDataSet

#bestFeature=chooseBestFeatureToSplit(myMat)

#print bestFeature

#myTree=createTree(myMat,labels)

#classify(inputTree,featLabels,testVec)

#print myTree

上篇就寫這么多了，中下篇會盡快更新哦！

參考文獻

1蒲每、《機器學習實戰(zhàn)》（書）

2喻括、算法雜貨鋪——分類算法之決策樹（博客）

3双妨、其他網(wǎng)站資料（略）