題外話：從四月份決定復(fù)習(xí)機(jī)器學(xué)習(xí)之后柳洋。雖然整理筆記的速度很慢走敌，但還是起到了理清思路的問題惯豆。等這個筆記寫差不多以后準(zhǔn)備玩玩深度學(xué)習(xí)。

什么是決策樹

第一個例子

• 輸入數(shù)據(jù)x：M個樣本數(shù)據(jù)跪解，每個數(shù)據(jù)包括年齡炉旷、性別、職業(yè)、每日使用計(jì)算機(jī)時間等窘行；
• 輸出數(shù)據(jù)y：該樣本是否喜歡計(jì)算機(jī)游戲

我們可以用這樣的一個模型：

我們發(fā)現(xiàn)這樣一個決策樹骏啰，可以做分類、也可以做回歸抽高，classfication and regression tree，所以叫CART透绩。

如果我們建立了很多這樣的樹翘骂，最后得到的結(jié)果是這些樹的疊加，就成了隨機(jī)森林帚豪。

多個決策樹就構(gòu)成了隨機(jī)森林

第二個例子

加入平面上有如下的數(shù)據(jù)點(diǎn)碳竟，分綠色和紅色兩種，我們應(yīng)該如何將它們區(qū)分開呢狸臣？

我們可以拿刀一點(diǎn)一點(diǎn)地將它們分開莹桅。

分兩份

分四份

分五份

根據(jù)上一節(jié)的內(nèi)容可知，隨著我們這樣一刀一刀分下去烛亦，整個系統(tǒng)的信息熵在下降诈泼。

決策樹的特點(diǎn)

上面的兩個例子非常直觀，總結(jié)上面的例子煤禽，決策樹有以下特點(diǎn)：

• 決策樹是一種樹形結(jié)構(gòu)铐达，其中每個內(nèi)部節(jié)點(diǎn)表示在一個屬性上的測試，每個分支代表一個測試輸出檬果，每個葉節(jié)點(diǎn)代表一種類別瓮孙。
• 決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)，是一種有監(jiān)督學(xué)習(xí)选脊。
• 決策樹學(xué)習(xí)采用的是自頂向下的遞歸方法杭抠，其基本思想是以信息熵為度量構(gòu)造一顆熵值下降最快的樹，到葉子結(jié)點(diǎn)處熵為零恳啥，此時每個葉節(jié)點(diǎn)中的實(shí)例都屬于同一類偏灿。（和梯度下降一樣，仍然屬于一種Greed算法角寸，也就是說有可能陷入局部最優(yōu)解菩混。）

接下來我們將會介紹三種最常見的決策樹算法，分別是ID3扁藕，C4.5和CART沮峡。

ID3算法

ID3(Iterative Dichotomiser 3)，翻譯過來就叫迭代二叉樹三代亿柑，多么富有程序員氣息的一個名字邢疙。
我們先造個輪子了解一下原理，下面的代碼是MLA里的例子。

# -*-coding:utf-8 -*-
from math import log
import operator

def createDataSet():#創(chuàng)建一個樣例數(shù)據(jù)集
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing','flippers']
    #change to discrete values
    return dataSet, labels

def calcShannonEnt(dataSet):#香農(nóng)熵計(jì)算函數(shù)
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet: #the the number of unique elements and their occurance
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob,2) #log base 2
    return shannonEnt
    
def splitDataSet(dataSet, axis, value):#按照給定特征劃分?jǐn)?shù)據(jù)集
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]     #chop out axis used for splitting
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

python原生的方法extend()和append()疟游，功能很類似也有區(qū)別呼畸，append是直接把元素搞進(jìn)去，無論這個元素是不是可迭代對象颁虐，而extend會把可迭代對象拆開蛮原，然后再搞進(jìn)去。
splitDataSet()函數(shù)的作用是另绩，把dataset中第axis個屬性為value的數(shù)據(jù)挑出來儒陨，并且刪除了axis屬性，可見ID3每生長一層就消耗掉一個屬性笋籽。例如：

>>>mydat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>>splitDataSet(mydat,0,1)
[[1, 'yes'], [1, 'yes'], [0, 'no']]

def chooseBestFeatureToSplit(dataSet):#選擇信息增益最大的屬性劃數(shù)據(jù)
    numFeatures = len(dataSet[0]) - 1      #the last column is used for the labels
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0; bestFeature = -1
    for i in range(numFeatures):        #iterate over all the features
        featList = [example[i] for example in dataSet]#create a list of all the examples of this feature
        uniqueVals = set(featList)       #get a set of unique values
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)     
        infoGain = baseEntropy - newEntropy     #calculate the info gain; ie reduction in entropy
        if (infoGain > bestInfoGain):       #compare this to the best gain so far
            bestInfoGain = infoGain         #if better than current best, set to best
            bestFeature = i
    return bestFeature                      #returns an integer

#如果把所有特征都消耗完了蹦漠，葉子結(jié)點(diǎn)的類標(biāo)簽仍然不是唯一的，我們需要用多數(shù)投票的方式定義該節(jié)點(diǎn)
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):#遞歸構(gòu)建算法
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList): 
        return classList[0]#stop splitting when all of the classes are equal
    if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet
        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[:]       #copy all of labels, so trees don't mess up existing labels
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)#遞歸
    return myTree                            

#將測試數(shù)據(jù)應(yīng)用到已經(jīng)訓(xùn)好的決策樹上
def classify(inputTree,featLabels,testVec):
    firstStr = inputTree.keys()[0]
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    key = testVec[featIndex]
    valueOfFeat = secondDict[key]
    if isinstance(valueOfFeat, dict): 
        classLabel = classify(valueOfFeat, featLabels, testVec)
    else: classLabel = valueOfFeat
    return classLabel

python的pickle模塊實(shí)現(xiàn)了基本的數(shù)據(jù)序列和反序列化车海。通過pickle模塊的序列化操作我們能夠?qū)⒊绦蛑羞\(yùn)行的對象信息保存到文件中去笛园，永久存儲；通過pickle模塊的反序列化操作侍芝，我們能夠從文件中創(chuàng)建上一次程序保存的對象研铆。利用這個模塊，我們可以把我們用數(shù)據(jù)訓(xùn)出來的決策樹保存下來州叠。

def storeTree(inputTree,filename):
    import pickle
    fw = open(filename,'w')
    pickle.dump(inputTree,fw)
    fw.close()
    
def grabTree(filename):
    import pickle
    fr = open(filename)
    return pickle.load(fr)

現(xiàn)在蚜印，輪子已經(jīng)完全被造好了，畫圖函數(shù)就不貼上來了留量，我們可以跑一個數(shù)據(jù)來看看窄赋。

>>>myDat, labels = createDataSet()
>>>myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>>myTree = createTree(myDat, labels)
>>>myTree
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

嘿嘿，通過這樣一個簡單的例子楼熄，原理已經(jīng)被我們掌握了忆绰。

應(yīng)用sklearn的ID3算法

我們還是應(yīng)用Iris數(shù)據(jù)，我們都知道Iris有四個特征可岂，為了可視化错敢，現(xiàn)在我們先用前兩個特征來個分類，其實(shí)這樣問題也不大缕粹，應(yīng)該還記得我們做PCA的時候可以把特征降到兩維：

# -*- coding:utf-8 -*-

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib as mpl
from sklearn import tree
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
import pydotplus


# 花萼長度稚茅、花萼寬度，花瓣長度平斩，花瓣寬度
iris_feature_E = 'sepal length', 'sepal width', 'petal length', 'petal width'
iris_feature = u'花萼長度', u'花萼寬度', u'花瓣長度', u'花瓣寬度'
iris_class = 'Iris-setosa', 'Iris-versicolor', 'Iris-virginica'


if __name__ == "__main__":
    mpl.rcParams['font.sans-serif'] = [u'SimHei']
    mpl.rcParams['axes.unicode_minus'] = False

    path = '..\\8.Regression\\iris.data'  # 數(shù)據(jù)文件路徑
    data = pd.read_csv(path, header=None)
    x = data[range(4)]
    #pandas的類似one-hot的方法
    y = pd.Categorical(data[4]).codes
    # 為了可視化亚享，僅使用前兩列特征
    x = x.iloc[:, :2]
    x_train, x_test, y_train, y_test = train_test_split(x, y, train_size=0.7, random_state=1)
    #sklearn自帶的劃分train和test的方法，train_size是訓(xùn)練集的比例绘面，也可以制定樣本個數(shù)欺税，random_state是種子數(shù)侈沪。

    # 決策樹參數(shù)估計(jì)
    # min_samples_split = 10：如果該結(jié)點(diǎn)包含的樣本數(shù)目大于10，則(有可能)對其分支
    # min_samples_leaf = 10：若將某結(jié)點(diǎn)分支后晚凿，得到的每個子結(jié)點(diǎn)樣本數(shù)目都大于10亭罪，則完成分支；否則歼秽，不進(jìn)行分支
    model = DecisionTreeClassifier(criterion='entropy')
    #用信息增益為目標(biāo)函數(shù)应役，就是ID3算法
    model.fit(x_train, y_train)
    y_test_hat = model.predict(x_test)      # 測試數(shù)據(jù)

    # 保存
    # dot -Tpng my.dot -o my.png
    # 1、輸出
    with open('iris.dot', 'w') as f:
        tree.export_graphviz(model, out_file=f)
    # 2燥筷、給定文件名
    # tree.export_graphviz(model, out_file='iris1.dot')
    # 3扛吞、輸出為pdf格式
    dot_data = tree.export_graphviz(model, out_file=None, feature_names=iris_feature_E, class_names=iris_class,
                                    filled=True, rounded=True, special_characters=True)
    graph = pydotplus.graph_from_dot_data(dot_data)
    graph.write_pdf('iris.pdf')
    f = open('iris.png', 'wb')
    f.write(graph.create_png())
    f.close()

    # 畫圖
    N, M = 50, 50  # 橫縱各采樣多少個值
    x1_min, x2_min = x.min()
    x1_max, x2_max = x.max()
    t1 = np.linspace(x1_min, x1_max, N)
    t2 = np.linspace(x2_min, x2_max, M)
    x1, x2 = np.meshgrid(t1, t2)  # 生成網(wǎng)格采樣點(diǎn)
    x_show = np.stack((x1.flat, x2.flat), axis=1)  # 測試點(diǎn)
    print x_show.shape

    # # 打開該注釋前，確保注釋掉x = x[:, :2]
    # x3 = np.ones(x1.size) * np.average(x[:, 2])
    # x4 = np.ones(x1.size) * np.average(x[:, 3])
    # x_test = np.stack((x1.flat, x2.flat, x3, x4), axis=1)  # 測試點(diǎn)

    cm_light = mpl.colors.ListedColormap(['#A0FFA0', '#FFA0A0', '#A0A0FF'])
    cm_dark = mpl.colors.ListedColormap(['g', 'r', 'b'])
    y_show_hat = model.predict(x_show)  # 預(yù)測值
    print y_show_hat.shape
    print y_show_hat
    y_show_hat = y_show_hat.reshape(x1.shape)  # 使之與輸入的形狀相同
    print y_show_hat
    plt.figure(facecolor='w')
    plt.pcolormesh(x1, x2, y_show_hat, cmap=cm_light)  # 預(yù)測值的顯示
    plt.scatter(x_test[0], x_test[1], c=y_test.ravel(), edgecolors='k', s=150, zorder=10, cmap=cm_dark, marker='*')  # 測試數(shù)據(jù)
    plt.scatter(x[0], x[1], c=y.ravel(), edgecolors='k', s=40, cmap=cm_dark)  # 全部數(shù)據(jù)
    plt.xlabel(iris_feature[0], fontsize=15)
    plt.ylabel(iris_feature[1], fontsize=15)
    plt.xlim(x1_min, x1_max)
    plt.ylim(x2_min, x2_max)
    plt.grid(True)
    plt.title(u'鳶尾花數(shù)據(jù)的決策樹分類', fontsize=17)
    plt.show()

    # 訓(xùn)練集上的預(yù)測結(jié)果
    y_test = y_test.reshape(-1)
    print y_test_hat
    print y_test
    result = (y_test_hat == y_test)   # True則預(yù)測正確荆责，F(xiàn)alse則預(yù)測錯誤
    acc = np.mean(result)
    print '準(zhǔn)確度: %.2f%%' % (100 * acc)

    # 過擬合：錯誤率
    depth = np.arange(1, 15)
    err_list = []
    for d in depth:
        clf = DecisionTreeClassifier(criterion='entropy', max_depth=d)
        clf.fit(x_train, y_train)
        y_test_hat = clf.predict(x_test)  # 測試數(shù)據(jù)
        result = (y_test_hat == y_test)  # True則預(yù)測正確，F(xiàn)alse則預(yù)測錯誤
        if d == 1:
            print result
        err = 1 - np.mean(result)
        err_list.append(err)
        # print d, ' 準(zhǔn)確度: %.2f%%' % (100 * err)
        print d, ' 錯誤率: %.2f%%' % (100 * err)
    plt.figure(facecolor='w')
    plt.plot(depth, err_list, 'ro-', lw=2)
    plt.xlabel(u'決策樹深度', fontsize=15)
    plt.ylabel(u'錯誤率', fontsize=15)
    plt.title(u'決策樹深度與過擬合', fontsize=17)
    plt.grid(True)
    plt.show()

用前兩個特征亚脆，我們得到了如下結(jié)果：

顏色代表類型做院，圓圈是train數(shù)據(jù)，星星是test數(shù)據(jù)

光看圖濒持，界面很扭曲键耕，很明顯有點(diǎn)過擬合，在測試集上的準(zhǔn)確度60.00%柑营。
可見對ID3的深度如果不加限制屈雄，很容易陷入過擬合的情況，這也是ID3算法的最重要的缺陷官套。
那么如果我們對決策樹的深度加以限制酒奶，這本質(zhì)是一種預(yù)剪枝，并統(tǒng)計(jì)測試集上的錯誤率：

我們發(fā)現(xiàn)深度為3的時候錯誤率是最低的奶赔，但也有20%惋嚎，總所周至Iris是性狀非常良好的數(shù)據(jù)集。但我們在上述過程中只是用了前兩個屬性站刑，所以我們接著對其他屬性組合進(jìn)行了測試另伍。

特征：   花萼長度  +  花萼寬度     預(yù)測正確數(shù)目： 123     準(zhǔn)確率: 82.00%
特征：   花萼長度  +  花瓣長度     預(yù)測正確數(shù)目： 145     準(zhǔn)確率: 96.67%
特征：   花萼長度  +  花瓣寬度     預(yù)測正確數(shù)目： 144     準(zhǔn)確率: 96.00%
特征：   花萼寬度  +  花瓣長度     預(yù)測正確數(shù)目： 143     準(zhǔn)確率: 95.33%
特征：   花萼寬度  +  花瓣寬度     預(yù)測正確數(shù)目： 145     準(zhǔn)確率: 96.67%
特征：   花瓣長度  +  花瓣寬度     預(yù)測正確數(shù)目： 147     準(zhǔn)確率: 98.00%

后面幾組數(shù)據(jù)界面的形狀都非常好。數(shù)據(jù)降維的本質(zhì)是將高維空間的對象有選擇地映射在低維平面上加以觀察绞旅，所以說維度的選擇也很重要摆尝。

ID3有很多錯缺陷，比如說這種算法就很傾向于選擇取值較多的屬性因悲，另外只能處理標(biāo)稱型數(shù)據(jù)堕汞，為了克服這些缺陷，那么在此基礎(chǔ)上有發(fā)展了C4.5算法晃琳。