机器学习笔记三 决策树算法

决策树算法

• • （一）基本介绍
  • （二）决策树算法概述
  • （三）决策树构建
  • （四） 实例：使用决策树预测隐形眼镜类型

（一）基本介绍

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。

1） 开始：构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按着这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。

2） 如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。

3）如果还有子集不能够被正确的分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点，如果递归进行，直至所有训练数据子集被基本正确的分类，或者没有合适的特征为止。

4）每个子集都被分到叶节点上，即都有了明确的类，这样就生成了一颗决策树。

1.1 决策树原理

原理：不断通过数据集的特征来划分数据集，直到遍历所有划分数据集的属性，或每个分支下的实例都具有相同的分类，决策树算法停止运行。

1.2 决策树的优缺点及适用类型

优点 :计算复杂度不高, 输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。
缺点 :可能会产生过度匹配问题。
适用数据类型:数值型和标称型

先举一个小例子，让你了解决策树是干嘛的，简单来说，决策树算法就是一种基于特征的分类器，拿邮件来说吧，试想一下，邮件的类型有很多种，有需要及时处理的邮件，无聊是观看的邮件，垃圾邮件等等，我们需要去区分这些，比如根据邮件中出现里你的名字还有你朋友的名字，这些特征就会就可以将邮件分成两类，需要及时处理的邮件和其他邮件，这时候在分类其他邮件，例如邮件中出现buy，money等特征，说明这是垃圾推广文件，又可以将其他文件分成无聊是观看的邮件和垃圾邮件了。

使用决策树做预测需要以下过程：

1. 收集数据：可以使用任何方法。比如想构建一个相亲系统，我们可以从媒婆那里，或者通过参访相亲对象获取数据。根据他们考虑的因素和最终的选择结果，就可以得到一些供我们利用的数据了。

2. 准备数据：收集完的数据，我们要进行整理，将这些所有收集的信息按照一定规则整理出来，并排版，方便我们进行后续处理。

3. 分析数据：可以使用任何方法，决策树构造完成之后，我们可以检查决策树图形是否符合预期。

4. 训练算法：这个过程也就是构造决策树，同样也可以说是决策树学习，就是构造一个决策树的数据结构。

5. 测试算法：使用经验树计算错误率。当错误率达到了可接收范围，这个决策树就可以投放使用了。

6. 使用算法：此步骤可以使用适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

1.3 信息增益

划分数据集的大原则是：将无序数据变得更加有序，但是各种方法都有各自的优缺点，信息论是量化处理信息的分支科学，在划分数据集前后信息发生的变化称为信息增益，获得信息增益最高的特征就是最好的选择，所以必须先学习如何计算信息增益，集合信息的度量方式称为香农熵，或者简称熵。

信息增益: 在划分数据集之前之后信息发生的变化成为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

熵定义为信息的期望值，如果待分类的事物可能划分在多个类之中，则符号 x i ​ xi​ xi​的信息定义为：

l ( x i ​ ) = − l o g 2 ​ p ( x i ​ ) l(xi​)=−log2​p(xi​) l(xi​)=−log2​p(xi​)

其中， p ( x i ) p(xi) p(xi)是选择该分类的概率。

为了计算熵，我们需要计算所有类别所有可能值所包含的信息期望值，通过下式得到： H = − ∑ i = 1 n ​ p ( x i ​ ) l o g 2 ​ p ( x i ​ ) H=-\sum_{i=1}^{n}​p(xi​)log2​p(xi​) H=−i=1∑n​​p(xi​)log2​p(xi​)

其中，n为分类数目，熵越大，随机变量的不确定性就越大。

当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empirical entropy)。什么叫由数据估计？比如有10个数据，一共有两个类别，A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。其中有3个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据数据数出来的。我们定义贷款申请样本数据表中的数据为训练数据集D，则训练数据集D的经验熵为H(D)，|D|表示其样本容量，及样本个数。设有K个类Ck，k = 1,2,3,···,K，|Ck|为属于类Ck的样本个数，这经验熵公式可以写为：

H ( D ) = − Σ ∣ c k ​ ∣ ∣ D ∣ ​ l o g 2 ∣ c k ​ ∣ ​ ∣ D ∣ ​ ​ H(D)=−Σ\frac{∣ck​∣}{∣D∣} ​log2\frac{∣ck​∣​}{∣D∣}​ ​ H(D)=−Σ∣D∣∣ck​∣​​log2∣D∣∣ck​∣​​​​

在理解信息增益之前，要明确——条件熵

信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。

条件熵H(Y∣X)
H(Y∣X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy) H(Y|X)，定义X给定条件下Y的条件概率分布的熵对X的数学期望：

H ( Y ∣ X ) = ∑ i = 1 n ​ p i ​ H ( Y ∣ X = x i ​ ) H(Y∣X)= \sum_{i=1}^{n}​pi​H(Y∣X=xi​) H(Y∣X)=i=1∑n​​pi​H(Y∣X=xi​)

其中， p i = P ( X = x i ) pi=P(X=xi) pi=P(X=xi)
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的分别为经验熵和经验条件熵，此时如果有0概率，令 0 l o g 0 = 0 0log0=0 0log0=0

信息增益：信息增益是相对于特征而言的。所以，特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：

g ( D , A ) = H ( D ) − H ( D ∣ A ) g(D,A)=H(D)−H(D∣A) g(D,A)=H(D)−H(D∣A)

一般地，熵H(D)与条件熵H(D|A)之差成为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

信息增益值的大小相对于训练数据集而言的，并没有绝对意义，在分类问题困难时，也就是说在训练数据集经验熵大的时候，信息增益值会偏大，反之信息增益值会偏小，使用信息增益比可以对这个问题进行校正，这是特征选择的另一个标准。

信息增益比：特征A对训练数据集D的信息增益比 g R ​ ( D , A ) gR​(D,A) gR​(D,A)定义为其信息增益 g ( D , A ) g(D,A) g(D,A)与训练数据集D

D的经验熵之比：

g R ​ ( D , A ) = g ( D , A ) ​ H ( D ) gR​(D,A)=\frac{g(D,A)​}{H(D)} gR​(D,A)=H(D)g(D,A)​​

代码：

"""
函数说明：计算给定数据集的经验熵（香农熵）
Parameters：
    dataSet：数据集
Returns：
    shannonEnt：经验熵
 

"""
def calcShannonEnt(dataSet):
    #返回数据集行数
    numEntries=len(dataSet)
    #保存每个标签（label）出现次数的字典
    labelCounts={}
    #对每组特征向量进行统计
    for featVec in dataSet:
        currentLabel=featVec[-1]                     #提取标签信息
        if currentLabel not in labelCounts.keys():   #如果标签没有放入统计次数的字典，添加进去
            labelCounts[currentLabel]=0
        labelCounts[currentLabel]+=1                 #label计数

    shannonEnt=0.0                                   #经验熵
    #计算经验熵
    for key in labelCounts:
        prob=float(labelCounts[key])/numEntries      #选择该标签的概率
        shannonEnt-=prob*log(prob,2)                 #利用公式计算
    return shannonEnt                                #返回经验熵


"""
函数说明：计算给定数据集的经验熵（香农熵）
Parameters：
    dataSet：数据集
Returns：
    shannonEnt：信息增益最大特征的索引值
 
     
"""


def chooseBestFeatureToSplit(dataSet):
    #特征数量
    numFeatures = len(dataSet[0]) - 1
    #计数数据集的香农熵
    baseEntropy = calcShannonEnt(dataSet)
    #信息增益
    bestInfoGain = 0.0
    #最优特征的索引值
    bestFeature = -1
    #遍历所有特征
    for i in range(numFeatures):
        # 获取dataSet的第i个所有特征
        featList = [example[i] for example in dataSet]
        #创建set集合{}，元素不可重复
        uniqueVals = set(featList)
        #经验条件熵
        newEntropy = 0.0
        #计算信息增益
        for value in uniqueVals:
            #subDataSet划分后的子集
            subDataSet = splitDataSet(dataSet, i, value)
            #计算子集的概率
            prob = len(subDataSet) / float(len(dataSet))
            #根据公式计算经验条件熵
            newEntropy += prob * calcShannonEnt((subDataSet))
        #信息增益
        infoGain = baseEntropy - newEntropy
        #打印每个特征的信息增益
        print("第%d个特征的增益为%.3f" % (i, infoGain))
        #计算信息增益
        if (infoGain > bestInfoGain):
            #更新信息增益，找到最大的信息增益
            bestInfoGain = infoGain
            #记录信息增益最大的特征的索引值
            bestFeature = i
            #返回信息增益最大特征的索引值
    return bestFeature

（二）决策树算法概述

2.1 算法理论

决策树构建的伪代码如下：

显然，决策树的生成是一个递归过程，在决策树基本算法中，有3种情导致递归返回：

1. 当前结点包含的样本全属于同一类别，无需划分；

2. 属性集为空，或是所有样本在所有属性上取值相同，无法划分；

3. 当前结点包含的样本集合为空，不能划分。

划分选择：

决策树学习的关键是第8行，即如何选择最优划分属性，一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越高。

2.2 ID3算法

ID3算法通过对比选择不同特征下数据集的信息增益和香农熵来确定最优划分特征。

香农熵：

from collections import Counter
import operator
import math

def calcEnt(dataSet):
    classCount = Counter(sample[-1] for sample in dataSet)
    prob = [float(v)/sum(classCount.values()) for v in classCount.values()]
    return reduce(operator.add, map(lambda x: -x*math.log(x, 2), prob))

纯度差，也称为信息增益，表示为

上面公式实际上就是当前节点的不纯度减去子节点不纯度的加权平均数，权重由子节点记录数与当前节点记录数的比例决定。信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大，效果越好。

信息增益准则对可取值数目较多的属性有所偏好。

2.3 C4.5算法

C4.5决策树生成算法相对于ID3算法的重要改进是使用信息增益率来选择节点属性。它克服了ID3算法存在的不足：ID3算法只适用于离散的描述属性，对于连续数据需离散化，而C4.5则离散连续均能处理。

增益率定义为：

其中

需注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

2.4 CART算法

CART决策树使用“基尼指数”来选择划分属性，数据集D的纯度可用基尼值来度量：

它反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此Gini(D)越小，则数据集D的纯度越高。

from  collections import Counter
import operator

def calcGini(dataSet):
    labelCounts = Counter(sample[-1] for sample in dataSet)
    prob = [float(v)/sum(labelCounts.values()) for v in labelCounts.values()]
    return 1 - reduce(operator.add, map(lambda x: x**2, prob))

2.5 剪枝处理

为避免过拟合，需要对生成树剪枝。决策树剪枝的基本策略有“预剪枝”和“后剪枝”。预剪枝是指在决策树生成过程中，对每个结点划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点（有欠拟合风险）。后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶节点。

**剪枝（pruning）：**从已经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化分类树模型。

**实现方式：**极小化决策树整体的损失函数或代价函数来实现

（三）决策树构建

3.1 数据处理（子功能模块）

使用ID3算法划分数据集，即通过对比选择不同特征下数据集的信息增益和香农熵来确定最优划分特征。

1. 计算香农熵：

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']
    return dataSet, labels

def calcShannonEnt(dataSet):
    '''
    计算给定数据集的香农熵
    '''
    numEntries = len(dataSet)
    labelCounts = {}
    #统计每个类别出现的次数，保存在字典labelCounts中
    for featVec in dataSet:
        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) #取2为底的对数
    return shannonEnt

if __name__== "__main__":
    '''
    计算给定数据集的香农熵
    '''
    dataSet,labels = createDataSet()
    shannonEnt = calcShannonEnt(dataSet)

2. 划分数据集

def splitDataSet(dataSet, axis, value):
    '''
    按照给定特征划分数据集
    dataSet：待划分的数据集
    axis：   划分数据集的第axis个特征
    value：  特征的返回值（比较值）
    '''
    retDataSet = []
    #遍历数据集中的每个元素，一旦发现符合要求的值，则将其添加到新创建的列表中
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
            #extend()和append()方法功能相似，但在处理列表时，处理结果完全不同
            #a=[1,2,3]  b=[4,5,6]
            #a.append(b) = [1,2,3,[4,5,6]]
            #a.extend(b) = [1,2,3,4,5,6]
    return retDataSet

划分数据集的结果如下所示：

选择最好的数据集划分方式。接下来我们将遍历整个数据集，循环计算香农熵和 splitDataSet() 函数，找到最好的特征划分方式：

def chooseBestFeatureToSplit(dataSet):
    '''
    选择最好的数据集划分方式
    输入：数据集
    输出：最优分类的特征的index
    '''
    #计算特征数量
    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0; bestFeature = -1
    for i in range(numFeatures):
        #创建唯一的分类标签列表
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        #计算每种划分方式的信息熵
        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
        #计算最好的信息增益，即infoGain越大划分效果越好
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

3.2 递归构建决策树

目前我们已经学习了从数据集构造决策树算法所需要的子功能模块，其工作原理如下：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。递归结束的条件是：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。

由于特征数目并不是在每次划分数据分组时都减少，因此这些算法在实际使用时可能引起一定的问题。目前我们并不需要考虑这个问题，只需要在算法开始运行前计算列的数目，查看算法是否使用了所有属性即可。如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们通常会采用多数表决的方法决定该叶子节点的分类。

1. 在 trees.py 中增加如下投票表决代码：

import operator
def majorityCnt(classList):
    '''
    投票表决函数
    输入classList:标签集合，本例为：['yes', 'yes', 'no', 'no', 'no']
    输出：得票数最多的分类名称
    '''
    classCount={}
    for vote in classList:
        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]

2. 创建树的函数代码（主函数）：

def createTree(dataSet,labels):
    '''
    创建树
    输入：数据集和标签列表
    输出：树的所有信息
    '''
    # classList为数据集的所有类标签
    classList = [example[-1] for example in dataSet]
    # 停止条件1:所有类标签完全相同，直接返回该类标签
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 停止条件2:遍历完所有特征时仍不能将数据集划分成仅包含唯一类别的分组，则返回出现次数最多的类标签
    #
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    # 选择最优分类特征
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    # myTree存储树的所有信息
    myTree = {bestFeatLabel:{}}
    # 以下得到列表包含的所有属性值
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    # 遍历当前选择特征包含的所有属性值
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree

本例返回 myTree 为字典类型，如下：

{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

3.3 测试分类和存储分类器

利用决策树的分类函数：

def classify(inputTree,featLabels,testVec):
    '''
    决策树的分类函数
    inputTree:训练好的树信息
    featLabels:标签列表
    testVec:测试向量
    '''
    # 在2.7中，找到key所对应的第一个元素为：firstStr = myTree.keys()[0]，
    # 这在3.4中运行会报错：‘dict_keys‘ object does not support indexing，这是因为python3改变了dict.keys,
    # 返回的是dict_keys对象,支持iterable 但不支持indexable，
    # 我们可以将其明确的转化成list，则此项功能在3中应这样实现：
    firstSides = list(inputTree.keys())
    firstStr = firstSides[0]
    secondDict = inputTree[firstStr]
    # 将标签字符串转换成索引
    featIndex = featLabels.index(firstStr)
    key = testVec[featIndex]
    valueOfFeat = secondDict[key]
    # 递归遍历整棵树，比较testVec变量中的值与树节点的值，如果到达叶子节点，则返回当前节点的分类标签
    if isinstance(valueOfFeat, dict):
        classLabel = classify(valueOfFeat, featLabels, testVec)
    else: classLabel = valueOfFeat
    return classLabel

if __name__== "__main__":
    '''
    测试分类效果
    '''
    dataSet,labels = createDataSet()
    myTree = createTree(dataSet,labels)
    ans = classify(myTree,labels,[1,0])

决策树模型的存储：

def storeTree(inputTree,filename):
    '''
    使用pickle模块存储决策树
    '''
    import pickle
    fw = open(filename,'wb+')
    pickle.dump(inputTree,fw)
    fw.close()

def grabTree(filename):
    '''
    导入决策树模型
    '''
    import pickle
    fr = open(filename,'rb')
    return pickle.load(fr)

if __name__== "__main__":
    '''
    存取操作
    '''
    storeTree(myTree,'mt.txt')
    myTree2 = grabTree('mt.txt')

3.4 使用 Matplotlib 绘制树形图

上节我们已经学习如何从数据集中创建决策树，然而字典的表示形式非常不易于理解，决策树的主要优点就是直观易于理解，如果不能将其直观显示出来，就无法发挥其优势。本节使用 Matplotlib 库编写代码绘制决策树。

1. 创建名为 treePlotter.py 的新文件：

import matplotlib.pyplot as plt

# 定义文本框和箭头格式
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")

# 绘制带箭头的注释
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',
             xytext=centerPt, textcoords='axes fraction',
             va="center", ha="center", bbox=nodeType, arrowprops=arrow_args )

def createPlot():
    fig = plt.figure(1, facecolor='grey')
    fig.clf()
    # 定义绘图区
    createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses
    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()

if __name__== "__main__":
    '''
    绘制树节点
    '''
    createPlot()

结果如下：

2. 构造注解树

绘制一棵完整的树需要一些技巧。我们虽然有 x, y 坐标，但是如何放置所有的树节点却是个问题。我们必须知道有多少个叶节点，以便可以正确确x轴的长度；我们还需要知道树有多少层，来确定y轴的高度。这里另一两个新函数 getNumLeafs() 和 getTreeDepth() ，来获取叶节点的数目和树的层数，createPlot() 为主函数，完整代码如下：

import matplotlib.pyplot as plt

# 定义文本框和箭头格式
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")

# 绘制带箭头的注释
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',
             xytext=centerPt, textcoords='axes fraction',
             va="center", ha="center", bbox=nodeType, arrowprops=arrow_args )

def createPlot(inTree):
    '''
    绘树主函数
    '''
    fig = plt.figure(1, facecolor='white')
    fig.clf()
    # 设置坐标轴数据
    axprops = dict(xticks=[], yticks=[])
    # 无坐标轴
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
    # 带坐标轴
#    createPlot.ax1 = plt.subplot(111, frameon=False)
    plotTree.totalW = float(getNumLeafs(inTree))
    plotTree.totalD = float(getTreeDepth(inTree))
    # 两个全局变量plotTree.xOff和plotTree.yOff追踪已经绘制的节点位置，
    # 以及放置下一个节点的恰当位置
    plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;
    plotTree(inTree, (0.5,1.0), '')
    plt.show()


def getNumLeafs(myTree):
    '''
    获取叶节点的数目
    '''
    numLeafs = 0
    firstSides = list(myTree.keys())
    firstStr = firstSides[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        # 判断节点是否为字典来以此判断是否为叶子节点
        if type(secondDict[key]).__name__=='dict':
            numLeafs += getNumLeafs(secondDict[key])
        else:   numLeafs +=1
    return numLeafs

def getTreeDepth(myTree):
    '''
    获取树的层数
    '''
    maxDepth = 0
    firstSides = list(myTree.keys())
    firstStr = firstSides[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__=='dict':
            thisDepth = 1 + getTreeDepth(secondDict[key])
        else:   thisDepth = 1
        if thisDepth > maxDepth: maxDepth = thisDepth
    return maxDepth


def plotMidText(cntrPt, parentPt, txtString):
    '''
    计算父节点和子节点的中间位置，并在此处添加简单的文本标签信息
    '''
    xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]
    yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
    createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)

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)
    firstSides = list(myTree.keys())
    firstStr = firstSides[0]
    cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)
    # 标记子节点属性值
    plotMidText(cntrPt, parentPt, nodeTxt)
    plotNode(firstStr, cntrPt, parentPt, decisionNode)
    secondDict = myTree[firstStr]
    # 减少y偏移
    plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
    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
            plotTree(secondDict[key],cntrPt,str(key))        #recursion
        else:   #it's a leaf node print the leaf node
            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


def retrieveTree(i):
    '''
    保存了树的测试数据
    '''
    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]



if __name__== "__main__":
    '''
    绘制树
    '''
    createPlot(retrieveTree(1))

测试结果：

（四） 实例：使用决策树预测隐形眼镜类型

处理流程：

1. 收集数据：提供的文本文件
2. 准备数据：解析tab键分割的数据行
3. 分析数据：快速检测数据，确保正确地解析数据内容，使用cerateplot()函数绘制最终的树形图
4. 训练算法：使用测试过的createTree（）函数
5. 测试算法：编写测试函数验证决策树可以正确分类给定的数据实例
6. 使用算法：存储树的数据结构，以便下次使用时无需重新构造

数据如下所示，其中最后一列表示类标签：

Python 调用代码：

import trees
import treePlotter

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

决策树效果：

总结：
使用的算法成为ID3，它是一个号的算法但无法直接处理数值型数据，尽管我们可以通过量化的方法将数值型数据转化为标称型数值，但如果存在太多的特征划分，ID3算法仍然会面临其他问题。
分类决策树模型表示基于特征对实例进行分类的树形结构，可以看做是一个定义在特征空间划分上的类的条件概率分布。通过特征选择，树的生成和树的剪枝，旨在构建一个与训练数据拟合很好并且复杂度小的决策树。 由于生成的决策树存在过拟合的问题，需要对其进行剪枝，往往是从已生成的树上减掉一些叶子节点或者子树并将其父节点作为新的叶节点从而化简生成新的决策树。