题外话：从四月份决定复习机器学习之后。虽然整理笔记的速度很慢，但还是起到了理清思路的问题。等这个笔记写差不多以后准备玩玩深度学习。

什么是决策树

第一个例子

• 输入数据x：M个样本数据，每个数据包括年龄、性别、职业、每日使用计算机时间等；
• 输出数据y：该样本是否喜欢计算机游戏

我们可以用这样的一个模型：

我们发现这样一个决策树，可以做分类、也可以做回归，classfication and regression tree，所以叫CART。

如果我们建立了很多这样的树，最后得到的结果是这些树的叠加，就成了随机森林。

多个决策树就构成了随机森林

第二个例子

加入平面上有如下的数据点，分绿色和红色两种，我们应该如何将它们区分开呢？

我们可以拿刀一点一点地将它们分开。

分两份

分四份

分五份

根据上一节的内容可知，随着我们这样一刀一刀分下去，整个系统的信息熵在下降。

决策树的特点

上面的两个例子非常直观，总结上面的例子，决策树有以下特点：

• 决策树是一种树形结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。
• 决策树学习是以实例为基础的归纳学习，是一种有监督学习。
• 决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一颗熵值下降最快的树，到叶子结点处熵为零，此时每个叶节点中的实例都属于同一类。（和梯度下降一样，仍然属于一种Greed算法，也就是说有可能陷入局部最优解。）

接下来我们将会介绍三种最常见的决策树算法，分别是ID3，C4.5和CART。

ID3算法

ID3(Iterative Dichotomiser 3)，翻译过来就叫迭代二叉树三代，多么富有程序员气息的一个名字。
我们先造个轮子了解一下原理，下面的代码是MLA里的例子。

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

def createDataSet():#创建一个样例数据集
    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):#香农熵计算函数
    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):#按照给定特征划分数据集
    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()，功能很类似也有区别，append是直接把元素搞进去，无论这个元素是不是可迭代对象，而extend会把可迭代对象拆开，然后再搞进去。
splitDataSet()函数的作用是，把dataset中第axis个属性为value的数据挑出来，并且删除了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):#选择信息增益最大的属性划数据
    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

#如果把所有特征都消耗完了，叶子结点的类标签仍然不是唯一的，我们需要用多数投票的方式定义该节点
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):#递归构建算法
    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                            

#将测试数据应用到已经训好的决策树上
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模块实现了基本的数据序列和反序列化。通过pickle模块的序列化操作我们能够将程序中运行的对象信息保存到文件中去，永久存储；通过pickle模块的反序列化操作，我们能够从文件中创建上一次程序保存的对象。利用这个模块，我们可以把我们用数据训出来的决策树保存下来。

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)

现在，轮子已经完全被造好了，画图函数就不贴上来了，我们可以跑一个数据来看看。

>>>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'}}}}

嘿嘿，通过这样一个简单的例子，原理已经被我们掌握了。

应用sklearn的ID3算法

我们还是应用Iris数据，我们都知道Iris有四个特征，为了可视化，现在我们先用前两个特征来个分类，其实这样问题也不大，应该还记得我们做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'  # 数据文件路径
    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是训练集的比例，也可以制定样本个数，random_state是种子数。

    # 决策树参数估计
    # min_samples_split = 10：如果该结点包含的样本数目大于10，则(有可能)对其分支
    # min_samples_leaf = 10：若将某结点分支后，得到的每个子结点样本数目都大于10，则完成分支；否则，不进行分支
    model = DecisionTreeClassifier(criterion='entropy')
    #用信息增益为目标函数，就是ID3算法
    model.fit(x_train, y_train)
    y_test_hat = model.predict(x_test)      # 测试数据

    # 保存
    # 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)  # 生成网格采样点
    x_show = np.stack((x1.flat, x2.flat), axis=1)  # 测试点
    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)  # 测试点

    cm_light = mpl.colors.ListedColormap(['#A0FFA0', '#FFA0A0', '#A0A0FF'])
    cm_dark = mpl.colors.ListedColormap(['g', 'r', 'b'])
    y_show_hat = model.predict(x_show)  # 预测值
    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)  # 预测值的显示
    plt.scatter(x_test[0], x_test[1], c=y_test.ravel(), edgecolors='k', s=150, zorder=10, cmap=cm_dark, marker='*')  # 测试数据
    plt.scatter(x[0], x[1], c=y.ravel(), edgecolors='k', s=40, cmap=cm_dark)  # 全部数据
    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'鸢尾花数据的决策树分类', fontsize=17)
    plt.show()

    # 训练集上的预测结果
    y_test = y_test.reshape(-1)
    print y_test_hat
    print y_test
    result = (y_test_hat == y_test)   # True则预测正确，False则预测错误
    acc = np.mean(result)
    print '准确度: %.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)  # 测试数据
        result = (y_test_hat == y_test)  # True则预测正确，False则预测错误
        if d == 1:
            print result
        err = 1 - np.mean(result)
        err_list.append(err)
        # print d, ' 准确度: %.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()

用前两个特征，我们得到了如下结果：

颜色代表类型，圆圈是train数据，星星是test数据

光看图，界面很扭曲，很明显有点过拟合，在测试集上的准确度60.00%。
可见对ID3的深度如果不加限制，很容易陷入过拟合的情况，这也是ID3算法的最重要的缺陷。
那么如果我们对决策树的深度加以限制，这本质是一种预剪枝，并统计测试集上的错误率：

我们发现深度为3的时候错误率是最低的，但也有20%，总所周至Iris是性状非常良好的数据集。但我们在上述过程中只是用了前两个属性，所以我们接着对其他属性组合进行了测试。

特征：   花萼长度  +  花萼宽度     预测正确数目： 123     准确率: 82.00%
特征：   花萼长度  +  花瓣长度     预测正确数目： 145     准确率: 96.67%
特征：   花萼长度  +  花瓣宽度     预测正确数目： 144     准确率: 96.00%
特征：   花萼宽度  +  花瓣长度     预测正确数目： 143     准确率: 95.33%
特征：   花萼宽度  +  花瓣宽度     预测正确数目： 145     准确率: 96.67%
特征：   花瓣长度  +  花瓣宽度     预测正确数目： 147     准确率: 98.00%

后面几组数据界面的形状都非常好。数据降维的本质是将高维空间的对象有选择地映射在低维平面上加以观察，所以说维度的选择也很重要。

ID3有很多错缺陷，比如说这种算法就很倾向于选择取值较多的属性，另外只能处理标称型数据，为了克服这些缺陷，那么在此基础上有发展了C4.5算法。