決策樹是一種常見的機器學習方法，也稱作“判定樹”。決策樹是根據樹結構來進行決策的，決策過程中提出的每一個判定都是對某個屬性的“測試”，每個測試的結果或是導出最終結論，或者導出進一步的判定問題，在測評那種資料劃分方式是做好的資料劃分的時候，有多種測量方法，其中有一種計算資訊增益的方法，叫作香農熵。“資訊熵”是用來度量兩種機率分布的差異，假設目前樣本的集合D中第k類樣本所占的比例為pk（k=1,2，...，|y|），則D的資訊熵為：
下面是計算給定資料集的香農熵：
from math import log
def calcShannonEnt(dataSet):
numEntries=len(dataSet) #numEntries得到的是資料集的大小，儲存執行個體總數
labelCounts={}
for featVec in dataSet: #為了所有資料建立一個字典，友善後面的求每種類的機率
currentLabel=featVec[-1] #建立一個資料字典，健值是最後一列的值，取該資料的特征标簽
if currentLabel not in labelCounts.keys(): #如果該特征标簽不存在
labelCounts[currentLabels]=0 #則擴充字典并将目前标簽加入字典
labelCounts[currentLabels]+=1 #記錄每個類别出現的次數
shannonEnt=0.0
for key in labelCounts:
prob=float(labelCounts[key])/numEntries #每個類别除以總數，是該類别的機率，也就是上面式子中的pk
shannonEnt-=prob*log(prob,2) *這一行就是上述pk乘以以2為底的對數
return shannonEnt
測試上面的代碼的結果為：
下面開始劃分資料集：
這個函數的作用是将第axis列中等于value的資料集劃分出來
def splitDataSet(dataSet,axis,value): #可以看到這個函數有三個輸入參數：待劃分的資料集，劃分資料集的特征以及需要傳回的特征的值
retDataSet=[] #因為該函數在同一個資料集上調用了很多次，是以定義一個新的清單對象
for featVec in dataSet: #周遊資料集中的每個元素的特征
if featVec[axis]==value: #如果該資料的這個特征的值符合要求
reducedFeatVec=featVec[:axis] #axis前幾行
reducedFeatVec.extend(featVec[axis+1:]) #跳過axis，添加之後的之後的
retDataSet.append(reducedFeatVec)
return retDataSet
下面是選擇最好的資料集劃分方式的代碼：
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) # 這裡的set是一個無序不重複的集合
newEntropy=0.0
for value in uniqueVals:
subDataSet=splitDataSet(dataSet,i,value) #用這個value值進行劃分的資料集
prob=len(subDataSet)/float(len(dataSet)) #傳回這個在所有中的比例
newEntropy+=prob*calcShannonEnt(subDataSet)
infoGain=baseEntropy-newEntropy #這幾行代碼是在計算資訊增益
if(infoGain>bestInfoGain): #如果這樣的劃分比之前最好的劃分方式得到的資訊增益多，則替換劃分方法為目前劃分方法
bestInfoGain=infoGain
bestFeature=i
return bestFeature #傳回最終的特征
傳回出現次數最多的分類名稱：
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]
遞歸建構決策樹的代碼：
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
下面是一個使用文本注解繪制樹節點：
import matplotlib.pyplot as plt
decisionNode=dict(boxstyle="sawtooth",fc="0.8")
leafNode=dict(boxstyle="round4",fc="0.8")
arrow_args=dict(arrowstyle="<-")
def plotNode(nodeTxt,conterPt,parentPt,nodeType):
createPlot.ax1.annotate(nodeTxt,xy=parentPt,\
xycoords='axes fraction',\
xytext=conterPt,textcoords='axes fraction',\
va="center",ha="center",bbox=nodeType,arrowprops=arrow_args)
def createPlot():
fig=plt.figure(1,facecolor='white')
fig.clf()
createPlot.ax1=plt.subplot(111,frameon=False)
plotNode(U'a',(0.5,0.1),(0.1,0.5),decisionNode)
plotNode(U'a',(0.8,0.1),(0.3,0.8),leafNode)
plt.show()
産生的效果如下;