好多算法之類的，看理論描述，讓人似懂非懂，代碼走一走，現(xiàn)象就了然了。

引：

from sklearn import tree

names = ['size', 'scale', 'fruit', 'butt']
labels = [1,1,1,1,1,0,0,0]

p1 = [2,1,0,1]
p2 = [1,1,0,1]
p3 = [1,1,0,0]
p4 = [1,1,0,0]
n1 = [0,0,0,0]
n2 = [1,0,0,0]
n3 = [0,0,1,0]
n4 = [1,1,0,0]
data = [p1, p2, p3, p4, n1, n2, n3, n4]

def pred(test):
    dtre = tree.DecisionTreeClassifier()
    dtre = dtre.fit(data, labels)
    print(dtre.predict([test]))
    with open('treeDemo.dot', 'w') as f:
       f = tree.export_graphviz(dtre, out_file = f, feature_names = names)

pred([1,1,0,1])

　　畫出的樹如下：

　　關于這個樹是怎么來的，如果很粗暴地看列的數(shù)據(jù)浮動情況：

　　或者說是方差，方差最小該是第三列，fruit，然后是butt，scale（方差3.0），size（方差3.2857）。再一看樹節(jié)點的分叉情況，fruit，butt，size，scale，兩相比較，好像發(fā)現(xiàn)了什么？

衡量數(shù)據(jù)無序度：

　　劃分數(shù)據(jù)集的大原則是：將無序的數(shù)據(jù)變得更加有序。

　　那么如何評價數(shù)據(jù)有序程度？比較直觀地，可以直接看數(shù)據(jù)間的差距，差距越大，無序度越高。但這顯然還不夠聰明。組織無序數(shù)據(jù)的一種方法是使用信息論度量信息。在劃分數(shù)據(jù)集之前之后信息發(fā)生的變化叫做信息增益（information gain），為了讓信息更準確分類，必然希望信息增益最大化，那么信息增益如何計算？

　　集合信息的度量方式叫做香農(nóng)熵（名字源自信息論支付克勞德·香農(nóng)），簡稱熵（entropy）。

　　熵定義為期望值，如果P(Xi) 是分類為i的概率，那么對于分類i的熵L(Xi) 的公式是：

　　顯然地，隨著分類的概率越高，其熵（L(X)）越小。這很有意思，概率越高的東西，大家的期望值越低；越容易發(fā)生的事情，大家對它的發(fā)生不驚奇，沒有期待；反過來說，發(fā)生幾率越小的事情，一旦發(fā)生了，大家都會很驚奇，那么這個叫驚奇度可能比較合適hhh。

　　計算熵值，不僅是要看單個分類的熵，要看所有分類的期望值，其中n是分類數(shù)目：

　　從這個公式看來，這是一個帶權重（是i分類的概率）的期望和。這個值可以用來表示事情的無序度。熵越高，則混合的數(shù)據(jù)越多。

 　　另一種度量集合無序度的方法是基尼不純度（Gini impurity），公式原理并不太明白，先擺出來吧：

信息增益：

　　信息增益（設為infoGain）作為無序度減少程度。

　　某一列的直接按分類結果（label）的信息熵（設為baseEnt）與該列按標志值分類的信息熵（設為newEnt）的差距。

　　ID3算法應用其差值：

infoGain = baseEntropy – newEntropy

　　C4.5算法應用其比值，其中i為列標志值分類總數(shù)：

ID3創(chuàng)建決策樹：

　　以信息熵來作為數(shù)據(jù)無序度判斷依據(jù)的話，決策樹如何創(chuàng)建？

　　下面以這個 DataSet 作為計算demo，列名分別是：“不浮出水面是否可以生存”，“是否有腳蹼”，特別地，最后一列為 “是否為魚類” 的分類標簽：

那么有矩陣：

[[1,1,’yes’],

 [1,1,’yes’],

 [ 1,0,’no’],

 [ 0,1,’no’],

 [ 0,1,’no’]]

步驟1：

　　以label列作為分類標準，計算第一列熵，首先看第一列和標簽列，計算如下圖：

[0] 此處直接以0和1作為數(shù)據(jù)劃分判斷，對于標志性的數(shù)據(jù)可行，但如果是數(shù)值型的數(shù)據(jù)，那么就需要采取另一種決策樹的構造算法。

　　以此類推，計算第2列：

步驟2：

　　比較所有列的熵，取無序度最小（也即信息增益 infoGain = baseColEnt - newColEnt 最大）的列（特征），做為決策樹的節(jié)點。

　　上例中，第一列信息熵最高，那么第一個節(jié)點就是no surfacing特征列。

步驟3：

　　處理分裂節(jié)點。

　　此時取步驟2中獲得的特征列作DataSet行上的分類，劃分出若干數(shù)據(jù)塊后，其中信息熵為0的數(shù)據(jù)塊是不再分裂的節(jié)點；信息熵不為0的，需要處理為新的DataSet，回到步驟1進行計算。

　　對于本例，按照第一列，可以把DataSet分裂成2個數(shù)據(jù)塊[1]：

[[1,1,’yes’],

 [1,1,’yes’],

 [ 1,0,’no’]]  ——設為DataSet_A

和：

[[ 0,1,’no’],

 [ 0,1,’no’]]  ——設為DataSet_B

[1] 這兩個數(shù)據(jù)塊的劃分還是依靠標志型數(shù)據(jù)的0與1，數(shù)值型數(shù)據(jù)采用另外的決策樹構造法。

　　此時DataSet_B全部為一個分類，那么這個節(jié)點就結束了。

　　DataSet_A的標簽分類不止一個，那么這個節(jié)點還需要繼續(xù)分裂，而此時DataSet_A的第一列曾經(jīng)做過分類列，新的DataSet可以除去這一列，即DataSet = [[1,’yes’],[1,’yes’] ,[0,’no’]]重新進入步驟1。

步驟4：

　　繪制圖像，葉節(jié)點為分類的標簽結果，其中0為False，1為True。

　　這種構造決策樹的方法叫做ID3，ID3無法直接處理數(shù)值型數(shù)據(jù)，盡管可以通過量化的方法將數(shù)值型數(shù)據(jù)轉化為標志型的數(shù)據(jù)，但如果存在太多的特征劃分，ID3算法仍會有其他問題。其他的決策樹構造法，有C4.5和CART等。

　　ID3算法構建的決策樹，其數(shù)據(jù)值需要是標志型（例如0表示否，1表示是，或者其他字符串[2]，標志總數(shù)較少）的數(shù)據(jù)，如果是數(shù)值型的數(shù)據(jù)，需要換其他構建方法。另外，可能會出現(xiàn)匹配選項過多的問題，這叫做過度匹配（overfitting），為了減少過度匹配，可以裁剪決策樹。

[2] 一個隱形眼鏡類型的示例，數(shù)據(jù)集如下，列名依次為：age，prescript，astigmatic，tearRate，最后一列為標簽列，其中no lenses表示不適合佩戴隱形眼鏡，soft：軟材質，hard：硬材質。

young        myope      no     reduced   no lenses

young        myope      no     normal      soft

young        myope      yes   reduced   no lenses

young        myope      yes   normal      hard

young        hyper        no     reduced   no lenses

young        hyper        no     normal      soft

young        hyper        yes   reduced   no lenses

young        hyper        yes   normal      hard

pre   myope      no     reduced   no lenses

pre   myope      no     normal      soft

pre   myope      yes   reduced   no lenses

pre   myope      yes   normal      hard

pre   hyper        no     reduced   no lenses

pre   hyper        no     normal      soft

pre   hyper        yes   reduced   no lenses

pre   hyper        yes   normal      no lenses

presbyopic        myope      no     reduced   no lenses

presbyopic        myope      no     normal      no lenses

presbyopic        myope      yes   reduced   no lenses

presbyopic        myope      yes   normal      hard

presbyopic        hyper        no     reduced   no lenses

presbyopic        hyper        no     normal      soft

presbyopic        hyper        yes   reduced   no lenses

presbyopic        hyper        yes   normal      no lenses

其決策樹如下：

創(chuàng)建決策樹的類庫：

    from sklearn import tree

　　具體代碼可見上文，不過代碼示例是以基尼不純度作為數(shù)據(jù)劃分的評判準則，可以在聲明樹對象的時候傳入?yún)?shù)，criterion = “entropy”設置決策樹以信息熵作為劃分標準：

    dtre = tree.DecisionTreeClassifier(criterion="entropy")

　　此外，

    with open('treeDemo.dot', 'w') as f:
       f = tree.export_graphviz(dtre, out_file = f, feature_names = names)

　　這兩句會創(chuàng)建保存在運行路徑命名為treeDemo的dot文件，打開可見樹節(jié)點信息：

digraph Tree {

node [shape=box] ;

0 [label="butt <= 0.5\nentropy = 0.954\nsamples = 8\nvalue = [3, 5]"] ;

1 [label="fruit <= 0.5\nentropy = 1.0\nsamples = 6\nvalue = [3, 3]"] ;

0 -> 1 [labeldistance=2.5, labelangle=45, headlabel="True"] ;

2 [label="size <= 0.5\nentropy = 0.971\nsamples = 5\nvalue = [2, 3]"] ;

1 -> 2 ;

3 [label="entropy = 0.0\nsamples = 1\nvalue = [0, 1]"] ;

2 -> 3 ;

4 [label="scale <= 0.5\nentropy = 1.0\nsamples = 4\nvalue = [2, 2]"] ;

2 -> 4 ;

5 [label="entropy = 0.0\nsamples = 1\nvalue = [1, 0]"] ;

4 -> 5 ;

6 [label="entropy = 0.918\nsamples = 3\nvalue = [1, 2]"] ;

4 -> 6 ;

7 [label="entropy = 0.0\nsamples = 1\nvalue = [1, 0]"] ;

1 -> 7 ;

8 [label="entropy = 0.0\nsamples = 2\nvalue = [0, 2]"] ;

0 -> 8 [labeldistance=2.5, labelangle=-45, headlabel="False"] ;

}

　　這個文件可以通過dot.exe（下載鏈接https://graphviz.gitlab.io/_pages/Download/Download_windows.html）繪制圖像。

　　（在安裝目錄的命令行窗口走dot -Tpng sample.dot -o sample.png語句，即可得到?jīng)Q策樹圖像）

　　Samples是此時dataSet的樣本個數(shù)，那么還有2個問題，1.節(jié)點閾值是如何確定；2.節(jié)點上的value是什么意思？（葉節(jié)點上最終分類的標志是？）這個類庫的決策樹構造方法與數(shù)值有關。