簡(jiǎn)述

本章構(gòu)造的決策樹(shù)算法能夠讀取數(shù)據(jù)集合夸浅，構(gòu)建類(lèi)似于圖3-1的決策樹(shù)。決策樹(shù)很多任務(wù)都 是為了數(shù)據(jù)中所蘊(yùn)含的知識(shí)信息尖昏，因此決策樹(shù)可以使用不熟悉的數(shù)據(jù)集合，并從中提取出一系列規(guī)則赖歌，機(jī)器學(xué)習(xí)算法最終將使用這些機(jī)器從數(shù)據(jù)集中創(chuàng)造的規(guī)則。專(zhuān)家系統(tǒng)中經(jīng)常使用決策樹(shù)蹂楣，而且決策樹(shù)給出結(jié)果往往可以匹敵在當(dāng)前領(lǐng)域具有幾十年工作經(jīng)驗(yàn)的人類(lèi)專(zhuān)家俏站。

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：計(jì)算復(fù)雜度不高，輸出結(jié)果易于理解痊土，對(duì)中間值的缺失不敏感肄扎，可以處理不相關(guān)特征數(shù)據(jù)。
缺點(diǎn)：可能會(huì)產(chǎn)生過(guò)度匹配問(wèn)題赁酝。我們可以裁剪決策樹(shù)犯祠，去掉一些不
必要的葉子節(jié)點(diǎn)。如果葉子節(jié)點(diǎn)只能增加少許信息酌呆，則可以刪除該節(jié)點(diǎn)衡载，將它并人到其他葉子節(jié) 點(diǎn)中。第9章將進(jìn)一步討論這個(gè)問(wèn)題隙袁。
適用數(shù)據(jù)類(lèi)型：數(shù)值型和標(biāo)稱(chēng)型

數(shù)據(jù)集

lenses.txt 預(yù)測(cè)隱形眼鏡類(lèi)型

構(gòu)建步驟

1.我們需要解決的第一個(gè)問(wèn)題就是痰娱，當(dāng)前數(shù)據(jù)集上哪個(gè)特征在劃分?jǐn)?shù)據(jù)分類(lèi)
時(shí)起決定性作用。一 些決策樹(shù)算法采用二分法劃分?jǐn)?shù)據(jù)菩收，本書(shū)并不采用這種方法梨睁。如果依某個(gè)屬性劃分?jǐn)?shù)據(jù)將會(huì)產(chǎn)生4個(gè)可能的值，我們數(shù)據(jù)劃分成四塊娜饵，并創(chuàng)建四個(gè)不的分支坡贺。本書(shū)將使用ID3算法劃分?jǐn)?shù)據(jù)集。
1.1在劃分?jǐn)?shù)據(jù)集之前之后信息發(fā)生的變化稱(chēng)為信息增益箱舞，知道如何計(jì)算信息增益遍坟，我們就可以計(jì)算每個(gè)特征值劃分?jǐn)?shù)據(jù)集獲得的信息增益，獲得信息增益最高的特征就是最好的選擇晴股。如何度量數(shù)據(jù)集的無(wú)序程度的方式是計(jì)算信息熵愿伴。
2.分類(lèi)算法除了需要測(cè)量信息熵，還需要?jiǎng)澐謹(jǐn)?shù)據(jù)集队魏，度量花費(fèi)數(shù)據(jù)集的熵公般，以便判斷當(dāng)前是否正確地劃分了數(shù)據(jù)集。我們將對(duì)每個(gè)特征劃分?jǐn)?shù)據(jù)集的結(jié)果計(jì)算一次信息熵胡桨，然后判斷按照哪個(gè)特征劃分?jǐn)?shù)據(jù)集是最好的劃分方式官帘。
3.由于特征值可能多于兩個(gè)，因此可能存在大于兩個(gè)分支的數(shù)據(jù)集劃分昧谊。第一次劃分之后刽虹，數(shù)據(jù)將被向下傳遞到樹(shù)分支的下一個(gè)節(jié)點(diǎn)，在這個(gè)節(jié)點(diǎn)上呢诬，我們可以再次劃分?jǐn)?shù)據(jù)涌哲。因此我們可以采用遞歸的原則處理數(shù)據(jù)集胖缤。 遞歸結(jié)束的條件是：程序遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性，或者每個(gè)分支下的所有實(shí)例都具有相同的分類(lèi)阀圾。
4.哪廓。如果數(shù)據(jù)集已經(jīng)處理了所有屬性，但是類(lèi)標(biāo)簽依然不是唯一的初烘，此時(shí)我們需要決定如何定義該葉子節(jié)點(diǎn)涡真，在這種情況下，我們通常會(huì)采用多數(shù)表決的方法決 定該葉子節(jié)點(diǎn)的分類(lèi)肾筐。
5,遞歸構(gòu)建決策樹(shù)
6.構(gòu)造注解樹(shù)
繪制一棵完整的樹(shù)需要一些技巧哆料。我們雖然有x,y坐標(biāo)，但是如何放置所有的樹(shù)節(jié)點(diǎn)卻是個(gè)問(wèn) 題吗铐。我們必須知道有多少個(gè)葉節(jié)點(diǎn)东亦，以便可以正確確x 軸的長(zhǎng)度；我們還需要知道樹(shù)有多少層唬渗，以便可以正確確定y軸的高度
7.通 過(guò)計(jì)算樹(shù)包含的所有葉子節(jié)點(diǎn)數(shù)典阵，劃分圖形的寬度，從而計(jì)算得到當(dāng)前節(jié)點(diǎn)中心位置镊逝，也就是 說(shuō) , 我們按照葉子節(jié)點(diǎn)的數(shù)目將x軸劃分為若干部分萄喳。
8.依靠訓(xùn)練數(shù)據(jù)構(gòu)造了決策樹(shù)之后，我們可以將它用于實(shí)際數(shù)據(jù)的分類(lèi)蹋半。在執(zhí)行數(shù)據(jù)分類(lèi)時(shí)，需要決策樹(shù)以及用于構(gòu)造樹(shù)的標(biāo)簽向量充坑。然后减江，程序比較測(cè)試數(shù)據(jù)與決策樹(shù)上的數(shù)值，遞歸執(zhí)行 該過(guò)程直到進(jìn)人葉子節(jié)點(diǎn)捻爷；最后將測(cè)試數(shù)據(jù)定義為葉子節(jié)點(diǎn)所屬的類(lèi)型
9.為了節(jié)省計(jì)算時(shí)間辈灼，最好能夠在每次執(zhí)行分類(lèi)時(shí)調(diào)用巳經(jīng)構(gòu)造好的決策樹(shù),為 了解決這個(gè)問(wèn)題，需要使用python莫塊pickle序列化對(duì)象.

語(yǔ)法

1.python語(yǔ)言在函數(shù)中傳遞的是列表的引用也榄，在函數(shù)內(nèi)部對(duì)列表對(duì)象的修改巡莹，將會(huì)影響該列表對(duì)象的整個(gè)生存周期。為了消除這個(gè)不良影響甜紫，我們需要在函數(shù)的開(kāi)始聲明一個(gè)新列表對(duì)象降宅。因?yàn)樵摵瘮?shù)代碼在同一數(shù)據(jù)集上被調(diào)用多次，為了不修改原始數(shù)據(jù)集囚霸，創(chuàng)建一個(gè)新的列表對(duì)象腰根。
2.extend() 函數(shù)用于在列表末尾一次性追加另一個(gè)序列中的多個(gè)值（用新列表擴(kuò)展原來(lái)的列表）。和append()有區(qū)別：

假定存在兩個(gè)列表拓型，a和b:
>>> a= [1,2,3]
>>> b = [4 , 5 , 6]
>>> a .append(b)
>>> a
[1, 2, 3, [4, 5, 6]]
如果執(zhí)行a .append(b)則列表得到了第四個(gè)元素额嘿，而且第四個(gè)元素也是一個(gè)列表瘸恼。然而
如果使用extend方法：
>>> a = [ 1 , 2,3]
>>> a .extend(b)
[1, 2, 3, 4, 5, 6]
則得到一個(gè)包含a和b所有元素的列表。

3.list索引值,featVec[:a]指第0個(gè)元素到第a-1個(gè)元素册养，[b:]指

featVec=[1, 0, 1, 'no']
reducedFeatVec = featVec[:2]
>>>reducedFeatVec =[1, 0]
reducedFeatVec.extend(featVec[3:])
>>>reducedFeatVec =[1, 0, 'no']

4.用python語(yǔ)言原生的集合set數(shù)據(jù)類(lèi)型东帅。集合數(shù)據(jù)類(lèi)型與列表類(lèi)型似，不同之處僅在于集合類(lèi)型中的每個(gè)值互不相同球拦。從列表中創(chuàng)建集合是python語(yǔ)言得到列表中唯一元素值的最快方法
5.Python 字典(Dictionary) items() 函數(shù)以列表返回可遍歷的(鍵, 值) 元組數(shù)組靠闭。
eg

lrt = {'a':1, 'b':2, 'c':3 }
rgj = lrt.items()
print(rgj)
>>>dict_items([('a', 1), ('b', 2), ('c', 3)])

6.operator模塊提供的itemgetter函數(shù)用于獲取對(duì)象的哪些維的數(shù)據(jù)，參數(shù)為一些序號(hào)（即需要獲取的數(shù)據(jù)在對(duì)象中的序號(hào)）

a = [1,2,3] 
>>> b=operator.itemgetter(1)      //定義函數(shù)b刘莹，獲取對(duì)象的第1個(gè)域的值
>>> b(a) 
>>> b=operator.itemgetter(1,0)  //定義函數(shù)b阎毅，獲取對(duì)象的第1個(gè)域和第0個(gè)的值
>>> b(a) 
(2, 1)
要注意，operator.itemgetter函數(shù)獲取的不是值点弯，而是定義了一個(gè)函數(shù)扇调，通過(guò)該函數(shù)作用到對(duì)象上才能獲取值。

7.sorted函數(shù)
Python內(nèi)置的排序函數(shù)sorted可以對(duì)list或者iterator進(jìn)行排序抢肛，官網(wǎng)文檔見(jiàn)：http://docs.python.org/2/library/functions.html?highlight=sorted#sorted狼钮，該函數(shù)原型為：
sorted(iterable, cmp=None, key=None, reverse=False)
參數(shù)解釋?zhuān)?br> iterable：是可迭代類(lèi)型;
cmp：用于比較的函數(shù)，比較什么由key決定;
key：用列表元素的某個(gè)屬性或函數(shù)進(jìn)行作為關(guān)鍵字捡絮，有默認(rèn)值熬芜，迭代集合中的一項(xiàng);
reverse：排序規(guī)則. reverse = True 降序 或者 reverse = False 升序，有默認(rèn)值福稳。
返回值：是一個(gè)經(jīng)過(guò)排序的可迭代類(lèi)型涎拉，與iterable一樣。

參數(shù)說(shuō)明：
(1) cmp參數(shù)
cmp接受一個(gè)函數(shù)的圆，拿整形舉例鼓拧，形式為:
def f(a,b):
return a-b
如果排序的元素是其他類(lèi)型的，如果a邏輯小于b越妈，函數(shù)返回負(fù)數(shù)季俩；a邏輯等于b，函數(shù)返回0梅掠；a邏輯大于b酌住，函數(shù)返回正數(shù)就行了

(2) key參數(shù)
key也是接受一個(gè)函數(shù)，不同的是阎抒，這個(gè)函數(shù)只接受一個(gè)元素,形式如下
def f(a):
return len(a)
key接受的函數(shù)返回值酪我，表示此元素的權(quán)值，sort將按照權(quán)值大小進(jìn)行排序

(3) reverse參數(shù)
接受False 或者True 表示是否逆序

例子：
(1)按照元素長(zhǎng)度排序
L = [{1:5,3:4},{1:3,6:3},{1:1,2:4,5:6},{1:9}]
def f(x):
    return len(x)
sort(key=f) 
print L
 
輸出:
[{1: 9}, {1: 5, 3: 4}, {1: 3, 6: 3}, {1: 1, 2: 4, 5: 6}]

對(duì)于本決策樹(shù)中用到的sort（）
（1）iterable指定要排序的list或者iterable
（2）cmp為函數(shù)且叁，指定排序時(shí)進(jìn)行比較的函數(shù)祭示，可以指定一個(gè)函數(shù)或者lambda函數(shù)，如：
students為類(lèi)對(duì)象的list，沒(méi)個(gè)成員有三個(gè)域质涛，用sorted進(jìn)行比較時(shí)可以自己定cmp函數(shù)稠歉，例如這里要通過(guò)比較第三個(gè)數(shù)據(jù)成員來(lái)排序，代碼可以這樣寫(xiě)：

      students = [('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]
      sorted(students, key=lambda student : student[2])

（3）key為函數(shù)汇陆，指定取待排序元素的哪一項(xiàng)進(jìn)行排序怒炸，函數(shù)用上面的例子來(lái)說(shuō)明，代碼如下：

      sorted(students, key=lambda student : student[2])

key指定的lambda函數(shù)功能是去元素student的第三個(gè)域（即：student[2]）毡代，因此sorted排序時(shí)阅羹，會(huì)以students所有元素的第三個(gè)域來(lái)進(jìn)行排序。
有了上面的operator.itemgetter函數(shù)教寂，也可以用該函數(shù)來(lái)實(shí)現(xiàn)捏鱼，例如要通過(guò)student的第三個(gè)域排序，可以這么寫(xiě)：

sorted(students, key=operator.itemgetter(2)) 

sorted函數(shù)也可以進(jìn)行多級(jí)排序酪耕，例如要根據(jù)第二個(gè)域和第三個(gè)域進(jìn)行排序导梆，可以這么寫(xiě)：

sorted(students, key=operator.itemgetter(1,2))

即先根據(jù)第二個(gè)域排序，再根據(jù)第三個(gè)域排序迂烁。
（4）reverse參數(shù)就不用多說(shuō)了看尼，是一個(gè)bool變量，表示升序還是降序排列盟步，默認(rèn)為false（升序排列）藏斩，定義為T(mén)rue時(shí)將按降序排列。
8.Python count() 方法用于統(tǒng)計(jì)字符串里某個(gè)字符出現(xiàn)的次數(shù)却盘≌颍可選參數(shù)為在字符串搜索的開(kāi)始與結(jié)束位置。
count()方法語(yǔ)法：

str.count(sub, start= 0,end=len(string))
sub -- 搜索的子字符串
start -- 字符串開(kāi)始搜索的位置黄橘。默認(rèn)為第一個(gè)字符,第一個(gè)字符索引值為0北专。
end -- 字符串中結(jié)束搜索的位置。字符中第一個(gè)字符的索引為 0旬陡。默認(rèn)為字符串的最后一個(gè)位置。

9.python中的del用法比較特殊语婴，新手學(xué)習(xí)往往產(chǎn)生誤解描孟，弄清del的用法，可以幫助深入理解python的內(nèi)存方面的問(wèn)題砰左。
python的del不同于C的free和C++的delete匿醒。
由于python都是引用，而python有GC機(jī)制缠导，所以廉羔，del語(yǔ)句作用在變量上，而不是數(shù)據(jù)對(duì)象上僻造。

if __name__=='__main__':  
    a=1       # 對(duì)象 1 被 變量a引用憋他，對(duì)象1的引用計(jì)數(shù)器為1  
    b=a       # 對(duì)象1 被變量b引用孩饼，對(duì)象1的引用計(jì)數(shù)器加1  
    c=a       #1對(duì)象1 被變量c引用，對(duì)象1的引用計(jì)數(shù)器加1  
    del a     #刪除變量a竹挡，解除a對(duì)1的引用  
    del b     #刪除變量b镀娶，解除b對(duì)1的引用  
    print(c)  #最終變量c仍然引用1  

del刪除的是變量，而不是數(shù)據(jù)揪罕。

另外梯码。關(guān)于list。

if __name__=='__main__':  
    li=[1,2,3,4,5]  #列表本身不包含數(shù)據(jù)1,2,3,4,5好啰，而是包含變量：li[0] li[1] li[2] li[3] li[4]   
    first=li[0]     #拷貝列表轩娶，也不會(huì)有數(shù)據(jù)對(duì)象的復(fù)制，而是創(chuàng)建新的變量引用  
    del li[0]  
    print(li)      #輸出[2, 3, 4, 5]  
    print(first)   #輸出 1  

10." python提供了一個(gè)注解工具annotations 框往，非常有用鳄抒，它可以在數(shù)據(jù)圖形上添加文本注釋。在使用annotate()時(shí)搅窿，要考慮兩個(gè)點(diǎn)的坐標(biāo)：被注釋的地方xy(x, y)和插入文本的地方xytext(x, y)嘁酿。
11.matplotlib.pyplot模塊中的字典類(lèi)型

# 定義決策樹(shù)決策結(jié)果的屬性，用字典來(lái)定義  
# 下面的字典定義也可寫(xiě)作 decisionNode={boxstyle:'sawtooth',fc:'0.8'}  
# boxstyle為文本框的類(lèi)型男应，sawtooth是鋸齒形闹司，fc是邊框線粗細(xì)  
decisionNode = dict(boxstyle="sawtooth",fc="0.8")  
# 定義決策樹(shù)的葉子結(jié)點(diǎn)的描述屬性  
leafNode = dict(boxstyle="round4",fc="0.8")  
# 定義決策樹(shù)的箭頭屬性  
arrow_args = dict(arrowstyle="<-")  

12.matplotlib.pyplot模塊中,axis()命令可以方便的獲取和設(shè)置XY軸的一些屬性。
13.Python 字典(Dictionary) keys() 函數(shù)以列表返回一個(gè)字典所有的鍵沐飘。
keys()方法語(yǔ)法：
dict.keys()
以下實(shí)例展示了 keys()函數(shù)的使用方法：

#!/usr/bin/python

dict = {'Name': 'Zara', 'Age': 7}

print "Value : %s" %  dict.keys()

以上實(shí)例輸出結(jié)果為：

Value : ['Age', 'Name']

代碼

from math import log
import operator
# import sys
# sys.path.append('C:/Users/LRT/PycharmProjects/M_learn/treeplotter.py')
# from treeplotter import *
# if __name__ == "__main__":

#另一個(gè)文件的內(nèi)容
import  matplotlib.pyplot as plt




#使用文本注解繪制樹(shù)節(jié)點(diǎn)
decisionNode = dict(boxstyle = "sawtooth", fc = "0.8")   #定義文本框和箭頭格式
#  定義決策樹(shù)決策結(jié)果的屬性游桩，用字典來(lái)定義  
# 下面的字典定義也可寫(xiě)作 decisionNode={boxstyle:'sawtooth',fc:'0.8'}  
# boxstyle為文本框的類(lèi)型，sawtooth是鋸齒形耐朴，fc是邊框線粗細(xì) 
leafNode = dict(boxstyle = "round4", fc = "0.8")  # 定義決策樹(shù)的葉子結(jié)點(diǎn)的描述屬性  
arrow_args = dict(arrowstyle = "<-")   # 定義決策樹(shù)的箭頭屬性


# def createPlot():   #第一個(gè)版本的createPlot()函數(shù)
#    fig = plt.figure(1, facecolor='white')  #先創(chuàng)建了一個(gè)新圖形并清空繪圖區(qū)   # 類(lèi)似于Matlab的figure借卧，定義一個(gè)畫(huà)布(暫且這么稱(chēng)呼吧)，背景為白色 
#    #  把畫(huà)布清空
#    fig.clf()
#  #  createPlot.ax1為全局變量筛峭，繪制圖像的句柄铐刘，subplot為定義了一個(gè)繪圖，111表示figure中的圖有1行1列影晓，即1個(gè)镰吵，最后的1代表第一個(gè)圖 
# #  frameon表示是否繪制坐標(biāo)軸矩形
#    createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses
#   #  繪制結(jié)點(diǎn) 
#    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 plotNode(nodeTxt, centerPt, parentPt, nodeType):   #繪制帶箭頭的注解，繪制節(jié)點(diǎn)
   # axis()命令可以方便的獲取和設(shè)置XY軸的一些屬性挂签。
   #  nodeTxt為要顯示的文本疤祭，centerPt為文本的中心點(diǎn)，箭頭所在的點(diǎn)饵婆，parentPt為指向文本的點(diǎn)  
   createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
                           xytext=centerPt, textcoords='axes fraction',
                           va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)


# createPlot()

def getNumLeafs(myTree):  #獲取葉節(jié)點(diǎn)數(shù)目
    numLeafs = 0
    a =  list(myTree.keys())
    firstStr = a[0]   # keys() 函數(shù)以列表返回一個(gè)字典所有的鍵勺馆。
    secondDict = myTree[firstStr]
    for key in secondDict.keys():   #。如果子節(jié)點(diǎn)是字典類(lèi)型，則 該節(jié)點(diǎn)也是一個(gè)判斷節(jié)點(diǎn)草穆，需要遞歸調(diào)用getNmnLeafs()函數(shù)
        if type(secondDict[key]).__name__=='dict':#test to see if the nodes are dictonaires, if not they are leaf nodes
            numLeafs += getNumLeafs(secondDict[key])
        else:   numLeafs +=1
    return numLeafs

def getTreeDepth(myTree):  #獲取樹(shù)的層數(shù)
    maxDepth = 0    #計(jì)算遍歷過(guò)程中遇到判 斷節(jié)點(diǎn)的個(gè)數(shù)灌灾。該函數(shù)的終止條件是葉子節(jié)點(diǎn)，一旦到達(dá)葉子節(jié)點(diǎn)续挟，則從遞歸調(diào)用中返回紧卒，并將 計(jì)算樹(shù)深度的變量加一
    a =list (myTree.keys())
    firstStr = a[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 retrieveTree(i):   #e輸出預(yù)先存儲(chǔ)的樹(shù)信息，避免了每次測(cè)試代碼時(shí)都要從數(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]


# mytree = retrieveTree(0)
# print(getNumLeafs(mytree))
# print(getTreeDepth(mytree))

def plotMidText(cntrPt, parentPt, txtString):   #在父子節(jié)點(diǎn)中填充文本信息
   xMid = (parentPt[0] - cntrPt[0]) / 2.0 + cntrPt[0] # 求中間點(diǎn)的橫坐標(biāo) 
   yMid = (parentPt[1] - cntrPt[1]) / 2.0 + cntrPt[1]  # 求中間點(diǎn)的縱坐標(biāo) 
   createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)  #繪制樹(shù)結(jié)點(diǎn) 

#繪制決策樹(shù)    >也是個(gè)遞歸函數(shù)诗祸。樹(shù)的寬度用于計(jì)算放置判斷節(jié)點(diǎn)的 位置跑芳，主要的計(jì)算原則是將它放在所有葉子節(jié)點(diǎn)的中間，而不僅僅是它子節(jié)點(diǎn)的中間
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)
   a = list(myTree.keys() ) # the text label for this node should be this
   firstStr = a[0]  #得到第一個(gè)特征    用兩個(gè)全局變量plotTree.xOff和plotTree.yOff追蹤已經(jīng)繪制的節(jié)點(diǎn)位置直颅，
   cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.yOff)  #計(jì)算坐標(biāo)博个，x坐標(biāo)為當(dāng)前樹(shù)的葉子結(jié)點(diǎn)數(shù)目除以整個(gè)樹(shù)的葉子結(jié)點(diǎn)數(shù)再除以2，y為起點(diǎn)
   plotMidText(cntrPt, parentPt, nodeTxt)   #計(jì)算父節(jié)點(diǎn)和子節(jié)點(diǎn)的中間位置功偿，并在此處添加簡(jiǎn)單的文本標(biāo)簽信息0
   plotNode(firstStr, cntrPt, parentPt, decisionNode)
   secondDict = myTree[firstStr]
   plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD   #盆佣，按比例減少全局變量  plotTree.yOff，并標(biāo)注此處將要繪制子節(jié)點(diǎn)
   #因?yàn)槲覀兪亲皂斚蛳吕L制圖形械荷， 因此需要依次遞減_y坐標(biāo)值共耍，而不是遞增^y坐標(biāo)值。
   for key in secondDict.keys():
      if type(secondDict[     #如果不是葉子節(jié)點(diǎn)則遞歸調(diào)用 plotTree函數(shù),吨瞎。
                 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   痹兜，如果節(jié)點(diǎn)是葉子節(jié)點(diǎn)則在圖形上畫(huà)出葉子節(jié)點(diǎn)，
         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   #在繪制了所有子節(jié)點(diǎn)之后颤诀，增加全局變量y的偏移


#繪制圖形的x軸有效范圍是0.0到1.0, y軸有效范 圍也是0.0?1.0
def createPlot(inTree):
    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.totalD = float(getTreeDepth(inTree))
    plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;  #將樹(shù)繪制在水平方向和垂直方向的中心位置
    plotTree(inTree, (0.5,1.0), '')
    plt.show()
#
# mytree = retrieveTree(0)
# createPlot(mytree)
# mytree['no surfacing'][3] = 'maby'
# createPlot(mytree)









#本文件內(nèi)容
def calcShannonEnt(dataSet): #計(jì)算給定數(shù)據(jù)集的熵折剃。
    numEntries = len(dataSet)
    labelCounts = {}#創(chuàng)建一個(gè)數(shù)據(jù)字典温亲，他的鍵值是最后一列的數(shù)值
    for featVec in dataSet:#為所有可能分類(lèi)創(chuàng)建字典
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0#為當(dāng)前沒(méi)有出現(xiàn)的類(lèi)別創(chuàng)建鍵值并加入字典
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob, 2) #計(jì)算熵的公式
    return shannonEnt

def createDataSet():
    # dataSet = [[1, 2, 3, 'yes'], [1, 3, 2, 'yes'], [1, 0, 1, 'no'], [0, 1, 0, 'no'], [0, 0, 1, 'no'] ]
    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()  #測(cè)試熵的計(jì)算
# print(calcShannonEnt(mydat))

def spliDataSet(dataSet, axis, value):#按照給定特征劃分?jǐn)?shù)據(jù)集  參數(shù)：待劃分的數(shù)據(jù)集鸠珠、劃分?jǐn)?shù)據(jù)集的特征变泄、特征的返回值

    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:   #將所有符合要求的元素抽取出來(lái)。
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])#extend() 函數(shù)用于在列表末尾一次性追加另一個(gè)序列中的多個(gè)值（用新列表擴(kuò)展原來(lái)的列表）心傀。
            retDataSet.append(reducedFeatVec)
    return retDataSet

# mydat, labels = createDataSet()  #測(cè)試
# print(spliDataSet(mydat, 2, 1))
# print(spliDataSet(mydat, 0, 0))

def chooseBestFeatureToSplit(dataSet):     #遍歷整個(gè)數(shù)據(jù)集屈暗， 計(jì)算香農(nóng)熵和spliDataSet()函數(shù)，找到最好的特征劃分方式脂男。
#在函數(shù)中調(diào)用的數(shù)據(jù)需要滿(mǎn)足一定的要求：第一個(gè)要 求是养叛，數(shù)據(jù)必須是一種由列表元素組成的列表，而且所有的列表元素都要具有相同的數(shù)據(jù)長(zhǎng)度疆液；
#  第二個(gè)要求是，數(shù)據(jù)的最后一列或者每個(gè)實(shí)例的最后一個(gè)元素是當(dāng)前實(shí)例的類(lèi)別標(biāo)簽陕贮。
    numFeatures = len(dataSet[0]) - 1   #行判定當(dāng)前數(shù)據(jù)集包含多少特征屬性堕油。
    baseEntropy = calcShannonEnt(dataSet)   #計(jì)算了整個(gè)數(shù)據(jù)集的原始香農(nóng)熵
    bestInfoGain = 0.0
    bestFeatures = -1
    for i in range(numFeatures):  #。第1個(gè)for循環(huán)遍歷數(shù)據(jù)集中的所有特征
        featList = [example[i] for example in dataSet]  #遍歷第i個(gè)特征
        uniqueVals = set(featList)  #set類(lèi)型：集合數(shù)據(jù)類(lèi)型與列表類(lèi)型相似，不同之處僅在于集合類(lèi)型中的每個(gè)值互不相同
        newEntropy = 0.0
        for value in uniqueVals:    #按各個(gè)特征來(lái)計(jì)算的香農(nóng)熵
            subDataSet = spliDataSet(dataSet, i, value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob *calcShannonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
        if(infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeatures = i
    return bestFeatures

# mydat, labels = createDataSet()
# print(chooseBestFeatureToSplit(mydat))

def majorityCnt(classList):   #參數(shù)：分類(lèi)名稱(chēng)的列表掉缺，返回出現(xiàn)次數(shù)最多的分類(lèi)名稱(chēng)
    classCount = {}
    for vote in classList:   #創(chuàng)建鍵值為classList中唯一值的數(shù)據(jù)字典
        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]


# lrt = {'a':1, 'b':2, 'c':3 }
# rgj = lrt.items()
# print(rgj)

def createTree(dataSat, labels):   #創(chuàng)建樹(shù)的函數(shù)代碼    輸人參數(shù)：數(shù)據(jù)集和特征標(biāo)簽列表卜录。
    classList = [example[-1] for example in dataSat]   #包含了數(shù)據(jù)集的所有類(lèi)標(biāo)簽。
    if classList.count(classList[0]) == len(classList):  #遞歸函數(shù)的第一個(gè)停止條件是所有的 類(lèi)標(biāo)簽完全相同眶明，則直接返回該類(lèi)標(biāo)簽0
        return classList[0]
    if len(dataSat[0]) == 1:   #遞歸函數(shù)的第二個(gè)停止條件是使用完了所有特征艰毒，仍然不能將數(shù)據(jù)集劃分成僅包含唯一類(lèi)別的分組?。
        return majorityCnt(classList)  #搜囱。由于第二個(gè)條件無(wú)法簡(jiǎn)單地返回唯一的類(lèi)標(biāo) 簽 丑瞧，這里使用majorityCnt函數(shù)挑選出現(xiàn)次數(shù)最多的類(lèi)別作為返回值。
    bestFeat = chooseBestFeatureToSplit(dataSat)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSat]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(spliDataSet(dataSat, bestFeat,value), subLabels)#遞歸調(diào)用
    return myTree

# mydat, labels = createDataSet()
# myTree = createTree(mydat, labels)
# print(myTree)


def classify(inputTree,featLabels,testVec):    # 使用決策樹(shù)的分類(lèi)函數(shù)
    a = list(inputTree.keys())
    firstStr = a[0]
    secondDict = inputTree[firstStr]
    featl = list(featLabels)
    featIndex = featl.index(firstStr)  #使用index方法查找當(dāng)前列表中第一個(gè)匹配firstStr變量的元素0蜀肘，確定當(dāng)前用來(lái)判斷的特征值
    key = testVec[featIndex]    #獲取當(dāng)前輸入的特征值
    valueOfFeat = secondDict[key]    #根據(jù)獲取的特征值進(jìn)入決策樹(shù)的下一層
    if isinstance(valueOfFeat, dict):
        classLabel = classify(valueOfFeat, featLabels, testVec)
    else: classLabel = valueOfFeat
    return classLabel

# mydat, labels = createDataSet()
# myTree = retrieveTree(0)
# print(classify(myTree, labels, [1, 0]))
# print(classify(myTree, labels, [1, 1]))

# 使用pickle塊存儲(chǔ)決策樹(shù)
def storeTree(inputTree, filename):
    import pickle
    fw = open(filename, 'wb+')
    #決策樹(shù)序列化
    pickle.dump(inputTree, fw)   #序列化對(duì)象可以在磁 盤(pán)上保存對(duì)象绊汹，并在需要的時(shí)候讀取出來(lái)。任何對(duì)象都可以執(zhí)行序列化操作扮宠，字典對(duì)象也不例外
    fw.close()

def grabTree(filename):
    import pickle
    fr = open(filename, 'rb')
    # 返回讀到的樹(shù)
    return pickle.load(fr)

# mydat, labels = createDataSet()    小測(cè)試
# myTree = retrieveTree(0)
# storeTree(myTree, 'classifierStorage1.txt')
# print(grabTree('classifierStorage1.txt'))

fr = open('lenses.txt', 'r')
lenses = [inst.strip().split('\t') for inst in fr.readlines()]
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
lensesTree = createTree(lenses, lensesLabels)
createPlot(lensesTree)

結(jié)果

image.png