簡述

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

優(yōu)缺點

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

數(shù)據(jù)集

lenses.txt 預(yù)測隱形眼鏡類型

構(gòu)建步驟

1.我們需要解決的第一個問題就是，當(dāng)前數(shù)據(jù)集上哪個特征在劃分?jǐn)?shù)據(jù)分類
時起決定性作用。一 些決策樹算法采用二分法劃分?jǐn)?shù)據(jù)，本書并不采用這種方法。如果依某個屬性劃分?jǐn)?shù)據(jù)將會產(chǎn)生4個可能的值，我們數(shù)據(jù)劃分成四塊，并創(chuàng)建四個不的分支。本書將使用ID3算法劃分?jǐn)?shù)據(jù)集。
1.1在劃分?jǐn)?shù)據(jù)集之前之后信息發(fā)生的變化稱為信息增益，知道如何計算信息增益，我們就可以計算每個特征值劃分?jǐn)?shù)據(jù)集獲得的信息增益，獲得信息增益最高的特征就是最好的選擇。如何度量數(shù)據(jù)集的無序程度的方式是計算信息熵。
2.分類算法除了需要測量信息熵，還需要劃分?jǐn)?shù)據(jù)集，度量花費數(shù)據(jù)集的熵，以便判斷當(dāng)前是否正確地劃分了數(shù)據(jù)集。我們將對每個特征劃分?jǐn)?shù)據(jù)集的結(jié)果計算一次信息熵，然后判斷按照哪個特征劃分?jǐn)?shù)據(jù)集是最好的劃分方式。
3.由于特征值可能多于兩個，因此可能存在大于兩個分支的數(shù)據(jù)集劃分。第一次劃分之后，數(shù)據(jù)將被向下傳遞到樹分支的下一個節(jié)點，在這個節(jié)點上，我們可以再次劃分?jǐn)?shù)據(jù)。因此我們可以采用遞歸的原則處理數(shù)據(jù)集。 遞歸結(jié)束的條件是：程序遍歷完所有劃分?jǐn)?shù)據(jù)集的屬性，或者每個分支下的所有實例都具有相同的分類。
4.。如果數(shù)據(jù)集已經(jīng)處理了所有屬性，但是類標(biāo)簽依然不是唯一的，此時我們需要決定如何定義該葉子節(jié)點，在這種情況下，我們通常會采用多數(shù)表決的方法決 定該葉子節(jié)點的分類。
5,遞歸構(gòu)建決策樹
6.構(gòu)造注解樹
繪制一棵完整的樹需要一些技巧。我們雖然有x,y坐標(biāo)，但是如何放置所有的樹節(jié)點卻是個問 題。我們必須知道有多少個葉節(jié)點，以便可以正確確x 軸的長度；我們還需要知道樹有多少層，以便可以正確確定y軸的高度
7.通 過計算樹包含的所有葉子節(jié)點數(shù)，劃分圖形的寬度，從而計算得到當(dāng)前節(jié)點中心位置，也就是 說 , 我們按照葉子節(jié)點的數(shù)目將x軸劃分為若干部分。
8.依靠訓(xùn)練數(shù)據(jù)構(gòu)造了決策樹之后，我們可以將它用于實際數(shù)據(jù)的分類。在執(zhí)行數(shù)據(jù)分類時，需要決策樹以及用于構(gòu)造樹的標(biāo)簽向量。然后，程序比較測試數(shù)據(jù)與決策樹上的數(shù)值，遞歸執(zhí)行 該過程直到進(jìn)人葉子節(jié)點；最后將測試數(shù)據(jù)定義為葉子節(jié)點所屬的類型
9.為了節(jié)省計算時間，最好能夠在每次執(zhí)行分類時調(diào)用巳經(jīng)構(gòu)造好的決策樹,為 了解決這個問題，需要使用python莫塊pickle序列化對象.

語法

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

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

3.list索引值,featVec[:a]指第0個元素到第a-1個元素，[b:]指

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

4.用python語言原生的集合set數(shù)據(jù)類型。集合數(shù)據(jù)類型與列表類型似，不同之處僅在于集合類型中的每個值互不相同。從列表中創(chuàng)建集合是python語言得到列表中唯一元素值的最快方法
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ù)用于獲取對象的哪些維的數(shù)據(jù)，參數(shù)為一些序號（即需要獲取的數(shù)據(jù)在對象中的序號）

a = [1,2,3] 
>>> b=operator.itemgetter(1)      //定義函數(shù)b，獲取對象的第1個域的值
>>> b(a) 
>>> b=operator.itemgetter(1,0)  //定義函數(shù)b，獲取對象的第1個域和第0個的值
>>> b(a) 
(2, 1)
要注意，operator.itemgetter函數(shù)獲取的不是值，而是定義了一個函數(shù)，通過該函數(shù)作用到對象上才能獲取值。

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

參數(shù)說明：
(1) cmp參數(shù)
cmp接受一個函數(shù)，拿整形舉例，形式為:
def f(a,b):
return a-b
如果排序的元素是其他類型的，如果a邏輯小于b，函數(shù)返回負(fù)數(shù)；a邏輯等于b，函數(shù)返回0；a邏輯大于b，函數(shù)返回正數(shù)就行了

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

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

例子：
(1)按照元素長度排序
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}]

對于本決策樹中用到的sort（）
（1）iterable指定要排序的list或者iterable
（2）cmp為函數(shù)，指定排序時進(jìn)行比較的函數(shù)，可以指定一個函數(shù)或者lambda函數(shù)，如：
students為類對象的list，沒個成員有三個域，用sorted進(jìn)行比較時可以自己定cmp函數(shù)，例如這里要通過比較第三個數(shù)據(jù)成員來排序，代碼可以這樣寫：

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

（3）key為函數(shù)，指定取待排序元素的哪一項進(jìn)行排序，函數(shù)用上面的例子來說明，代碼如下：

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

key指定的lambda函數(shù)功能是去元素student的第三個域（即：student[2]），因此sorted排序時，會以students所有元素的第三個域來進(jìn)行排序。
有了上面的operator.itemgetter函數(shù)，也可以用該函數(shù)來實現(xiàn)，例如要通過student的第三個域排序，可以這么寫：

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

sorted函數(shù)也可以進(jìn)行多級排序，例如要根據(jù)第二個域和第三個域進(jìn)行排序，可以這么寫：

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

即先根據(jù)第二個域排序，再根據(jù)第三個域排序。
（4）reverse參數(shù)就不用多說了，是一個bool變量，表示升序還是降序排列，默認(rèn)為false（升序排列），定義為True時將按降序排列。
8.Python count() 方法用于統(tǒng)計字符串里某個字符出現(xiàn)的次數(shù)?？蛇x參數(shù)為在字符串搜索的開始與結(jié)束位置。
count()方法語法：

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

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

if __name__=='__main__':  
    a=1       # 對象 1 被 變量a引用，對象1的引用計數(shù)器為1  
    b=a       # 對象1 被變量b引用，對象1的引用計數(shù)器加1  
    c=a       #1對象1 被變量c引用，對象1的引用計數(shù)器加1  
    del a     #刪除變量a，解除a對1的引用  
    del b     #刪除變量b，解除b對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]     #拷貝列表，也不會有數(shù)據(jù)對象的復(fù)制，而是創(chuàng)建新的變量引用  
    del li[0]  
    print(li)      #輸出[2, 3, 4, 5]  
    print(first)   #輸出 1  

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

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

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

#!/usr/bin/python

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

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

以上實例輸出結(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__":

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




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


# def createPlot():   #第一個版本的createPlot()函數(shù)
#    fig = plt.figure(1, facecolor='white')  #先創(chuàng)建了一個新圖形并清空繪圖區(qū)   # 類似于Matlab的figure，定義一個畫布(暫且這么稱呼吧)，背景為白色 
#    #  把畫布清空
#    fig.clf()
#  #  createPlot.ax1為全局變量，繪制圖像的句柄，subplot為定義了一個繪圖，111表示figure中的圖有1行1列，即1個，最后的1代表第一個圖 
# #  frameon表示是否繪制坐標(biāo)軸矩形
#    createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses
#   #  繪制結(jié)點 
#    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é)點
   # axis()命令可以方便的獲取和設(shè)置XY軸的一些屬性。
   #  nodeTxt為要顯示的文本，centerPt為文本的中心點，箭頭所在的點，parentPt為指向文本的點  
   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é)點數(shù)目
    numLeafs = 0
    a =  list(myTree.keys())
    firstStr = a[0]   # keys() 函數(shù)以列表返回一個字典所有的鍵。
    secondDict = myTree[firstStr]
    for key in secondDict.keys():   #。如果子節(jié)點是字典類型，則 該節(jié)點也是一個判斷節(jié)點，需要遞歸調(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ù)
    maxDepth = 0    #計算遍歷過程中遇到判 斷節(jié)點的個數(shù)。該函數(shù)的終止條件是葉子節(jié)點，一旦到達(dá)葉子節(jié)點，則從遞歸調(diào)用中返回，并將 計算樹深度的變量加一
    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ù)先存儲的樹信息，避免了每次測試代碼時都要從數(shù)據(jù)中創(chuàng)建樹的麻煩
    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é)點中填充文本信息
   xMid = (parentPt[0] - cntrPt[0]) / 2.0 + cntrPt[0] # 求中間點的橫坐標(biāo) 
   yMid = (parentPt[1] - cntrPt[1]) / 2.0 + cntrPt[1]  # 求中間點的縱坐標(biāo) 
   createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)  #繪制樹結(jié)點 

#繪制決策樹    >也是個遞歸函數(shù)。樹的寬度用于計算放置判斷節(jié)點的 位置，主要的計算原則是將它放在所有葉子節(jié)點的中間，而不僅僅是它子節(jié)點的中間
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]  #得到第一個特征    用兩個全局變量plotTree.xOff和plotTree.yOff追蹤已經(jīng)繪制的節(jié)點位置，
   cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.yOff)  #計算坐標(biāo)，x坐標(biāo)為當(dāng)前樹的葉子結(jié)點數(shù)目除以整個樹的葉子結(jié)點數(shù)再除以2，y為起點
   plotMidText(cntrPt, parentPt, nodeTxt)   #計算父節(jié)點和子節(jié)點的中間位置，并在此處添加簡單的文本標(biāo)簽信息0
   plotNode(firstStr, cntrPt, parentPt, decisionNode)
   secondDict = myTree[firstStr]
   plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD   #，按比例減少全局變量  plotTree.yOff，并標(biāo)注此處將要繪制子節(jié)點
   #因為我們是自頂向下繪制圖形， 因此需要依次遞減_y坐標(biāo)值，而不是遞增^y坐標(biāo)值。
   for key in secondDict.keys():
      if type(secondDict[     #如果不是葉子節(jié)點則遞歸調(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é)點是葉子節(jié)點則在圖形上畫出葉子節(jié)點，
         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é)點之后，增加全局變量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;  #將樹繪制在水平方向和垂直方向的中心位置
    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): #計算給定數(shù)據(jù)集的熵。
    numEntries = len(dataSet)
    labelCounts = {}#創(chuàng)建一個數(shù)據(jù)字典，他的鍵值是最后一列的數(shù)值
    for featVec in dataSet:#為所有可能分類創(chuàng)建字典
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0#為當(dāng)前沒有出現(xiàn)的類別創(chuàng)建鍵值并加入字典
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob, 2) #計算熵的公式
    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()  #測試熵的計算
# 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:   #將所有符合要求的元素抽取出來。
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])#extend() 函數(shù)用于在列表末尾一次性追加另一個序列中的多個值（用新列表擴(kuò)展原來的列表）。
            retDataSet.append(reducedFeatVec)
    return retDataSet

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

def chooseBestFeatureToSplit(dataSet):     #遍歷整個數(shù)據(jù)集， 計算香農(nóng)熵和spliDataSet()函數(shù)，找到最好的特征劃分方式。
#在函數(shù)中調(diào)用的數(shù)據(jù)需要滿足一定的要求：第一個要 求是，數(shù)據(jù)必須是一種由列表元素組成的列表，而且所有的列表元素都要具有相同的數(shù)據(jù)長度；
#  第二個要求是，數(shù)據(jù)的最后一列或者每個實例的最后一個元素是當(dāng)前實例的類別標(biāo)簽。
    numFeatures = len(dataSet[0]) - 1   #行判定當(dāng)前數(shù)據(jù)集包含多少特征屬性。
    baseEntropy = calcShannonEnt(dataSet)   #計算了整個數(shù)據(jù)集的原始香農(nóng)熵
    bestInfoGain = 0.0
    bestFeatures = -1
    for i in range(numFeatures):  #。第1個for循環(huán)遍歷數(shù)據(jù)集中的所有特征
        featList = [example[i] for example in dataSet]  #遍歷第i個特征
        uniqueVals = set(featList)  #set類型：集合數(shù)據(jù)類型與列表類型相似，不同之處僅在于集合類型中的每個值互不相同
        newEntropy = 0.0
        for value in uniqueVals:    #按各個特征來計算的香農(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ù)：分類名稱的列表，返回出現(xiàn)次數(shù)最多的分類名稱
    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ù)據(jù)集和特征標(biāo)簽列表。
    classList = [example[-1] for example in dataSat]   #包含了數(shù)據(jù)集的所有類標(biāo)簽。
    if classList.count(classList[0]) == len(classList):  #遞歸函數(shù)的第一個停止條件是所有的 類標(biāo)簽完全相同，則直接返回該類標(biāo)簽0
        return classList[0]
    if len(dataSat[0]) == 1:   #遞歸函數(shù)的第二個停止條件是使用完了所有特征，仍然不能將數(shù)據(jù)集劃分成僅包含唯一類別的分組?。
        return majorityCnt(classList)  #。由于第二個條件無法簡單地返回唯一的類標(biāo) 簽 ，這里使用majorityCnt函數(shù)挑選出現(xiàn)次數(shù)最多的類別作為返回值。
    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ù)
    a = list(inputTree.keys())
    firstStr = a[0]
    secondDict = inputTree[firstStr]
    featl = list(featLabels)
    featIndex = featl.index(firstStr)  #使用index方法查找當(dāng)前列表中第一個匹配firstStr變量的元素0，確定當(dāng)前用來判斷的特征值
    key = testVec[featIndex]    #獲取當(dāng)前輸入的特征值
    valueOfFeat = secondDict[key]    #根據(jù)獲取的特征值進(jìn)入決策樹的下一層
    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塊存儲決策樹
def storeTree(inputTree, filename):
    import pickle
    fw = open(filename, 'wb+')
    #決策樹序列化
    pickle.dump(inputTree, fw)   #序列化對象可以在磁 盤上保存對象，并在需要的時候讀取出來。任何對象都可以執(zhí)行序列化操作，字典對象也不例外
    fw.close()

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

# mydat, labels = createDataSet()    小測試
# 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