圖片.png
決策樹的主要算法有ID3，C4.5，CART
ID3使用信息增益來選擇特征
C4.5使用信息增益率來選擇特征
CART使用基尼系數(shù)來選擇特征
本文主要介紹ID3抑片，相關(guān)的理論知識請參考下面的博文
http://blog.csdn.net/acdreamers/article/details/44661149
'''構(gòu)建算法'''
def calcShannonEnt(dataSet):#定義求熵函數(shù)
numEntries = len(dataSet)#總共有多少條數(shù)據(jù)
labelCounts = {}#建立一個字典阅懦，收集結(jié)果中的分類
for i in dataSet:
currentLabel = i[-1] #注意數(shù)據(jù)集的分類要在最后一列
if currentLabel not in labelCounts.keys():#統(tǒng)計(jì)各分類數(shù)量
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0
for key in labelCounts:#計(jì)算系統(tǒng)的信息熵
prob = float(labelCounts[key])/numEntries #計(jì)算每種類別的概率
shannonEnt -= prob*log(prob,2) #計(jì)算所有信息期望值的和即為信息熵
#這一句可理解成這樣shannonEnt += -prob*log(prob,2)
return shannonEnt
def createDataSet():#定義創(chuàng)建數(shù)據(jù)集函數(shù)，測試用
dataSet = [[1,1,'yes'],
[1,1,'yes'],
[1,0,'no'],
[0,1,'no'],
[0,1,'no']]
labels = ['no surfacing','flippers']
return dataSet,labels
#myDat,labels = createDataSet()
#print(calcShannonEnt(myDat)) #目前結(jié)果有兩類踢俄，可得出信息熵是0.97咪橙，我們增加一個分類
#myDat[0][-1] = 'maybe'
#print(calcShannonEnt(myDat)) #可以看到信息熵增加了，也就是說果善，數(shù)據(jù)越無序(即越不可預(yù)測)诊笤，熵越大
'''以上定義求信息熵函數(shù)，下面我們依據(jù)信息熵來選擇最優(yōu)特征'''
def splitDataSet(dataSet,axis,value):#按照給定特征劃分?jǐn)?shù)據(jù)集
#axis為dataSet列方向的索引(某個特征)巾陕，value為該列(特征)所包含的值(類別)
#這個函數(shù)的目的是將dataSet按照某列的某值進(jìn)行分類
retDataSet = []
for i in dataSet:
if i[axis] == value:
reducedFeatvec = i[:axis]
reducedFeatvec.extend(i[axis+1:])
retDataSet.append(reducedFeatvec)
return retDataSet
def chooseBestFeatureToSplit(dataSet):
#該函數(shù)的目的是選擇最好的數(shù)據(jù)集劃分特征
numFeatures = len(dataSet[0])-1 #獲得數(shù)據(jù)集中的特征個數(shù)
#選出一個元素讨跟，-1是因?yàn)樽詈笠涣惺菢?biāo)簽，不是特征
baseEntropy = calcShannonEnt(dataSet) #計(jì)算最初的熵
bestInfoGain = 0
bestFeature = -1
for i in range(numFeatures):#按特征的個數(shù)進(jìn)行循環(huán)
featList = [example[i] for example in dataSet] #獲取索引為i的特征列表
uniqueVals = set(featList) #獲取特征所包含的唯一值
newEntropy = 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
'''以上晾匠，先通過chooseBestFeatureToSplit函數(shù)選擇信息增益最大的特征，
而后使用splitDataSet函數(shù)通過該特征對數(shù)據(jù)集進(jìn)行分類'''
def majorityCnt(classList):
#該函數(shù)的作用是梯刚，當(dāng)所有的特征都處理完了以后凉馆，標(biāo)簽仍然不存在唯一值，這個時候我們
#人為選擇出現(xiàn)標(biāo)簽出現(xiàn)最多的那個
classCount = {} #定義標(biāo)簽字典
for vote in classList:
if vote not in classCount.keys():
classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),
reverse = True)
return sortedClassCount[0][0]
def createTree(dataSet,labels):#創(chuàng)建樹函數(shù)
classList = [example[-1] for example in dataSet] #將所有的標(biāo)簽提取出來亡资，組成一個列表
if classList.count(classList[0]) == len(classList):#判斷標(biāo)簽列表時不是唯一值
return classList[0]
# if set(classList) == 1:
# return classList[0]
if len(dataSet[0]) == 1:#如果標(biāo)簽不唯一澜共，但dataSet的長度已經(jīng)為1了，即所有的特征已經(jīng)
#處理完了锥腻，這個時候嗦董，認(rèn)為選擇標(biāo)簽出現(xiàn)最多的那一個
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)#獲取最大信息熵的特征索引
bestFeatLabel = labels[bestFeat]#獲取對應(yīng)的標(biāo)簽
myTree = {bestFeatLabel:{}} #建立樹的字典
del labels[bestFeat] #從標(biāo)簽列表中刪除已經(jīng)處理過的特征標(biāo)簽
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) #遞歸使用cerateTree函數(shù)，直到標(biāo)簽值唯一或者所有特征處理完為止
#每一次遞歸都會將篩選出的擁有最大信息熵的特征傳遞給myTree字典旷太，以構(gòu)建樹
return myTree
'''createTree為遞歸創(chuàng)建樹函數(shù)展懈，每次調(diào)用都先判斷標(biāo)簽是否一致，
如果一致說明此特征已分類完成供璧，
如果標(biāo)簽不一致存崖，那就判斷還有沒有特征集，
有睡毒，就繼續(xù)尋找最優(yōu)特征来惧，進(jìn)行分類，
沒有演顾，就調(diào)用majorityCnt選擇當(dāng)前結(jié)果中標(biāo)簽出現(xiàn)最多的那個'''
myDat,labels = createDataSet()
myTree = createTree(myDat,labels)
#輸出結(jié)果為{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
#解釋如下供搀，首先通過最大信息熵選擇第一個特征，即‘no surfacing’钠至，它下面有兩個值葛虐，
#分別是0，1棉钧。0分支下面所有的標(biāo)簽都是no屿脐，即類標(biāo)簽，那么該節(jié)點(diǎn)判斷完畢，為葉子結(jié)點(diǎn)
#1分支下面還含有其他特征的诵，繼續(xù)通過最大信息熵進(jìn)行選擇万栅，這次選擇的是特征是'flippers'，
#它下面有兩個值西疤，0和1烦粒，每個值下面都是類標(biāo)簽，所以該節(jié)點(diǎn)判斷完畢代赁，為葉子節(jié)點(diǎn)
def classify(inputtree,featLabels,testvec):#定義測試決策樹函數(shù)
#后兩個參數(shù)代表的是指定標(biāo)簽以及對應(yīng)標(biāo)簽的值
firstStr = list(inputtree.keys())[0]
secondDict = inputtree[firstStr]
featIndex = featLabels.index(firstStr)
for key in secondDict.keys():
if testvec[featIndex] == key:
if type(secondDict[key]) == dict:
classLabel = classify(secondDict[key],featLabels,testvec)
else:
classLabel = secondDict[key]
return classLabel
print(classify(myTree,['no surfacing','flippers'],[1,0])
#可以看到扰她，當(dāng)特征no surfacing為1，特征flippers為0時管跺，輸出結(jié)果是no义黎，可數(shù)據(jù)集中的一致
def storeTree(inputtree,filename):#定義一個函數(shù)，保存決策樹結(jié)果
import pickle
f = open(filename,'wb')
pickle.dump(inputtree,f)
f.close()
def grabTree(filename):#定義一個函數(shù)豁跑，讀取決策樹結(jié)果
import pickle
with open(filename,'rb') as f:
return pickle.load(f)
'''
下面定義幾個函數(shù)將決策樹畫出來
'''
#畫圖的時候要確定圖所需大概空間廉涕，通過以下函數(shù)來定義相關(guān)屬性
def getNumLeafs(myTree):#定義一個獲取樹葉節(jié)點(diǎn)數(shù)目的函數(shù)
numLeafs = 0
firstStr = list(myTree.keys())[0] #第一層肯定只有一個特征
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]) == dict:
numLeafs += getNumLeafs(secondDict[key])
else:
numLeafs += 1
return numLeafs
def getTreeDepth(myTree): #定義一個獲取樹層數(shù)的函數(shù)
maxDepth = 0
firstStr = list(myTree.keys())[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]) == dict:
maxDepth = 1 + getTreeDepth(secondDict[key])
else:
maxDepth = 1 #這里不是+=1，是因?yàn)檫@里是在節(jié)點(diǎn)的循環(huán)里艇拍，層數(shù)與節(jié)點(diǎn)數(shù)無關(guān)
return maxDepth
def plotMidText(cntrpt,parentpt,txtString):#該函數(shù)的作用是在兩個節(jié)點(diǎn)之間添加文本
xMid = (parentpt[0]-cntrpt[0])/2 + cntrpt[0]
yMid = (parentpt[1]-cntrpt[1])/2 + cntrpt[1]
axes.text(xMid,yMid,txtString)#text是在指定的位置添加文本
decisionNode = dict(boxstyle='sawtooth',fc='0.8')#設(shè)置文本外框樣式
leafNode = {'boxstyle':'round4','fc':'0.8'}#設(shè)置文本外框樣式
arrow_args={'arrowstyle':'<-'} #注意這里是反箭頭
def plotNode(nodeTxt,centerpt,parentpt,nodeType): #畫節(jié)點(diǎn)及連接線
axes.annotate(nodeTxt,xy=parentpt,xycoords='axes fraction',
xytext=centerpt,textcoords='axes fraction',va='center',
ha='center',bbox=nodeType,arrowprops=arrow_args)
#str=nodeTxt設(shè)置要插入的文本狐蜕，xytext為文本及箭頭起始，xy為箭頭終止位置卸夕，因?yàn)橥ㄟ^
#arrowprops設(shè)置箭頭類型為反方向的层释，因此箭頭實(shí)際指向起始點(diǎn)即文本的位置
#xycoords及textcoords是設(shè)置坐標(biāo)系標(biāo)準(zhǔn)的，'axes fraction'代表
# 0,0 是軸域左下角快集，1,1 是右上角贡羔，bbox中的boxstyle屬性為設(shè)置文本外框樣式
#annotate的詳解請參考matplotlib文檔或者以下博文
#http://blog.csdn.net/wizardforcel/article/details/54782628
def plotTree(myTree,parentpt,nodeTxt): #畫圖主程序
global xoff,yoff #引入全局變量
numLeafs = getNumLeafs(myTree) #因?yàn)檫@個函數(shù)要迭代，
#所以這里重新定義一個獲取葉子節(jié)點(diǎn)個數(shù)的變量
firstStr = list(myTree.keys())[0]
cntrpt = (xoff+(1+float(numLeafs))/(2*totalW),yoff)
#這里首先要理解一個前提个初，就是為了確定整體圖形比較對稱乖寒，當(dāng)前節(jié)點(diǎn)所在的位置，
#是由他擁有的葉子節(jié)點(diǎn)數(shù)來決定的院溺。比如該節(jié)點(diǎn)下面共有葉子節(jié)點(diǎn)m個楣嘁，那么這m個葉子節(jié)點(diǎn)
#所占x軸的長度就是m*(1/n)，當(dāng)前節(jié)點(diǎn)要居中珍逸，那長度就是(1/2)*(m*(1/n))逐虚，
#(葉子結(jié)點(diǎn)的位置需要進(jìn)行偏移，但節(jié)點(diǎn)不需要)所以最初有個偏移所以要加回來谆膳，
#即(1/2)*(m*(1/n))+(1/2)*(1/n)叭爱，合并后即為(1+m)/(2*n),此時的位置為相對位置
#最后再加上根據(jù)已畫葉子節(jié)點(diǎn)產(chǎn)生的偏移量xoff，就是當(dāng)前節(jié)點(diǎn)最終在x軸上的位置
plotMidText(cntrpt,parentpt,nodeTxt)
plotNode(firstStr,cntrpt,parentpt,decisionNode)#畫當(dāng)前節(jié)點(diǎn)和上層節(jié)點(diǎn)的連接線
secondDict = myTree[firstStr]
yoff = yoff - 1/totalD #y軸的位置漱病，依據(jù)深度進(jìn)行遞減
for key in secondDict.keys():
if type(secondDict[key]) == dict:
plotTree(secondDict[key],cntrpt,str(key))
else:
xoff = xoff + 1/totalW #每畫一個葉子節(jié)點(diǎn)涤伐，偏移量就要加上對應(yīng)的長度
plotNode(secondDict[key],(xoff,yoff),cntrpt,leafNode)
plotMidText((xoff,yoff),cntrpt,str(key))
yoff = yoff + 1/totalD #注意這里馒胆，因?yàn)樯厦娴膄or循環(huán)中是隸屬于某個節(jié)點(diǎn)的，比如同層
#有節(jié)點(diǎn)A和節(jié)點(diǎn)B凝果，首先在節(jié)點(diǎn)A里面進(jìn)行迭代畫圖，每次迭代yoff都會減1/totalD,因此睦尽，當(dāng)
#A節(jié)點(diǎn)結(jié)束要處理B節(jié)點(diǎn)的時候器净，yoff的值要相應(yīng)加回來
'''以下代碼定義了幾個其他函數(shù)會用到的全局變量，因此沒有寫入到函數(shù)里面当凡，
你也可以寫到函數(shù)里山害，然后再通過調(diào)用其他函數(shù)時傳遞進(jìn)去'''
fig=plt.figure(1,facecolor='white')
fig.clf()
axprops = dict(xticks=[],yticks=[])#這兩個參數(shù)設(shè)置xy軸不顯示
axes = plt.subplot(111,frameon=False,**axprops)
totalW = float(getNumLeafs(inTree)) #獲取總的葉子結(jié)點(diǎn)個數(shù)
totalD = float(getTreeDepth(inTree)) #獲取總的深度
xoff = -1/(2*totalW) #設(shè)定x軸上的偏移量，假定樹一共有n個葉子節(jié)點(diǎn)沿量，將x軸等分為n個段浪慌，
#每段的長度就是1/n，為了對稱畫圖朴则，每個葉子節(jié)點(diǎn)在每段的中間位置权纤，所以要整體往左偏移
#即減去(1/2)*(1/n)，最初偏移量就是-1/(2*n)乌妒，那么第i個節(jié)點(diǎn)的x的位置就是i*(1/n)-1/(2*n)
#即xoff + i*(1/n)汹想，xoff這個變量后面會根據(jù)已畫的葉子節(jié)點(diǎn)數(shù)變化
yoff = 1
'''用些測試數(shù)據(jù)查看畫圖效果'''
def retrieveTree(i):
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]
inTree = retrieveTree(0)
plotTree(inTree,(0.5,1),'')#這里設(shè)定0.5，1是因?yàn)閜lotTree函數(shù)里面有兩個功能撤蚊，畫當(dāng)前節(jié)點(diǎn)
#以及和上層節(jié)點(diǎn)的連接線古掏，第一層節(jié)點(diǎn)沒有上一層，所以設(shè)定這個值侦啸，使得當(dāng)前節(jié)點(diǎn)和上層節(jié)點(diǎn)畫在一起
plt.show()
下面將以上構(gòu)建樹及畫圖的函數(shù)應(yīng)用到預(yù)測隱形眼鏡類型上
data = pd.read_table('lense.txt',sep='\t',header=None)
datalist = data.as_matrix().tolist() #將數(shù)據(jù)加載進(jìn)來后槽唾，先轉(zhuǎn)化為矩陣格式，而后轉(zhuǎn)為列表
labelslist = ['age','prescript','astigmatic','tearRate'] #數(shù)據(jù)集里共有四列光涂，設(shè)置每列名稱
lenseTree = createTree(datalist,labelslist)
plotTree(inTree,(0.5,1),'')
plt.show()
