您的位置: 首页  >  文章  >  《Machine Learning in Action》| 第2章 决策树

《Machine Learning in Action》| 第2章 决策树

分类: 文章 • 2024-01-28 09:57:46

决策树

  • 决策树的一般流程
    (1) 收集数据：可以使用任何方法。
    (2) 准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。
    (3) 分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
    (4) 训练算法：构造树的数据结构。
    (5) 测试算法：使用经验树计算错误率。
    (6) 使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

调包

import numpy as np
import matplotlib.pyplot as plt
import operator
from matplotlib.font_manager import FontProperties
import pickle # pickle序列化存储和读取决策树

3.1.决策树的构造

3.1.1.计算给定数据集的香农熵

信息量为概率的负对数，概率越小，信息量越大
l(xi)=−log2p(xi)l(x_{i})=-log_{2}p(x_{i})
香农熵为信息量的期望，统计平均
H=E[l(xi)]=−∑i=1np(xi)⋅log2p(xi)H=E[l(x_{i})]=-\sum_{i=1}^{n}p(x_{i})\cdot log_{2}p(x_{i})

计算经验熵：

H(x)=−∑xp(x)log2p(x)=−∑k=1K∣ck∣∣D∣log2∣ck∣∣D∣H(x)=-\sum_{x}p(x)log_{2}p(x)=-\sum_{k=1}^{K}\frac{|c_k|}{|D|}log_{2}\frac{|c_k|}{|D|}
H(D)=−615log2615−915log2915=0.971H(D)=-\frac{6}{15}log_{2}\frac{6}{15}-\frac{9}{15}log_{2}\frac{9}{15}=0.971
H(D2)=−39log239−69log269=0.918H(D_{2})=-\frac{3}{9}log_{2}\frac{3}{9}-\frac{6}{9}log_{2}\frac{6}{9}=0.918

from math import log

"""
函数说明：计算给定数据集的经验熵(entropy)
Parameters:
    dataSet - 数据集
Returns:
    shannonEnt - 香农熵(经验熵)
"""
def calcShannonEnt(dataSet):
    numEntries = len(dataSet) # 数据集的词条数目
#    print('numEntries={}'.format(numEntries)) # numEntries=15
    labelCounts = {} #  保存每个标签出现次数的字典
    for featVec in dataSet: # 遍历数据集的每行数据
        currentLabel = featVec[-1] # 数据的最后一列是标签，记录当前标签
        if currentLabel not in labelCounts.keys(): # 如果字典里没有该标签
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1 # 当前出现次数+1
#     print('labelCounts={}'.format(labelCounts)) # labelCounts={'no': 6, 'yes': 9}
    shannonEnt = 0.0 # 初始化香农熵
    # 根据公式计算经验熵
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries # 计算类别的概率
        shannonEnt -= prob * log(prob, 2) # 计算经验熵，为信息量的期望
    return shannonEnt # 返回香农熵,shannonEnt=0.9709505944546686

>>>
myDat, labels = createDataSet() # 导入数据集
print('myDat={}'.format(myDat)) # 打印数据集
print('labels={}'.format(labels))
# 测试香农熵函数，验证香农熵
print('shannonEnt={}'.format(calcShannonEnt(myDat))) 

myDat=[[0, 0, 0, 0, 'no'], [0, 0, 0, 1, 'no'], [0, 1, 0, 1, 'yes'], [0, 1, 1, 0, 'yes'], [0, 0, 0, 0, 'no'], [1, 0, 0, 0, 'no'], [1, 0, 0, 1, 'no'], [1, 1, 1, 1, 'yes'], [1, 0, 1, 2, 'yes'], [1, 0, 1, 2, 'yes'], [2, 0, 1, 2, 'yes'], [2, 0, 1, 1, 'yes'], [2, 1, 0, 1, 'yes'], [2, 1, 0, 2, 'yes'], [2, 0, 0, 0, 'no']]
labels=['年龄', '有工作', '有自己的房子', '信贷情况']
shannonEnt=0.9709505944546686

3.1.2.验证香农熵函数

"""
函数说明：创建测试数据集
    测试集采用统计学习方法的贷款申请样本表
    年龄：0(青年)，1(中年)，2(老年)
    有工作：0(否)，1(是)
    有自己的房子：0(否)，1(是)
    信贷情况：0(一般)，1(好)，2(非常好)
    类别：yes(放贷)，no(不放贷)
Parameters:
    无
Returns:
    dataSet - 数据集
    labels - 特征标签
"""
def createDataSet():
    dataSet = [ # 数据集
            [0, 0, 0, 0,'no'],
            [0, 0, 0, 1, 'no'],
            [0, 1, 0, 1, 'yes'],
            [0, 1, 1, 0, 'yes'],
            [0, 0, 0, 0, 'no'],
            [1, 0, 0, 0, 'no'],
            [1, 0, 0, 1, 'no'],
            [1, 1, 1, 1, 'yes'],
            [1, 0, 1, 2, 'yes'],
            [1, 0, 1, 2, 'yes'],
            [2, 0, 1, 2, 'yes'],
            [2, 0, 1, 1, 'yes'],
            [2, 1, 0, 1, 'yes'],
            [2, 1, 0, 2, 'yes'],
            [2, 0, 0, 0, 'no']]
    labels = ['年龄', '有工作', '有自己的房子', '信贷情况'] # 特征标签
    return dataSet, labels # 返回数据集和分类属性

>>>
myDat, labels = createDataSet()
print("myDat = {}".format(myDat))
print("myDat的香农熵 = {}".format(calcShannonEnt(myDat)))
myDat[0][-1] = 'maybe'
print("修改后的myDat = {}".format(myDat))
print("修改后的myDat的香农熵 = {}".format(calcShannonEnt(myDat)))

myDat = [[0, 0, 0, 0, 'no'], [0, 0, 0, 1, 'no'], [0, 1, 0, 1, 'yes'], [0, 1, 1, 0, 'yes'], [0, 0, 0, 0, 'no'], [1, 0, 0, 0, 'no'], [1, 0, 0, 1, 'no'], [1, 1, 1, 1, 'yes'], [1, 0, 1, 2, 'yes'], [1, 0, 1, 2, 'yes'], [2, 0, 1, 2, 'yes'], [2, 0, 1, 1, 'yes'], [2, 1, 0, 1, 'yes'], [2, 1, 0, 2, 'yes'], [2, 0, 0, 0, 'no']]
myDat的香农熵 = 0.9709505944546686
修改后的myDat = [[0, 0, 0, 0, 'maybe'], [0, 0, 0, 1, 'no'], [0, 1, 0, 1, 'yes'], [0, 1, 1, 0, 'yes'], [0, 0, 0, 0, 'no'], [1, 0, 0, 0, 'no'], [1, 0, 0, 1, 'no'], [1, 1, 1, 1, 'yes'], [1, 0, 1, 2, 'yes'], [1, 0, 1, 2, 'yes'], [2, 0, 1, 2, 'yes'], [2, 0, 1, 1, 'yes'], [2, 1, 0, 1, 'yes'], [2, 1, 0, 2, 'yes'], [2, 0, 0, 0, 'no']]
修改后的myDat的香农熵 = 1.2309595631140104

3.1.3.划分数据集

"""
函数说明：按照给定特征划分数据集
Paramerters:
    dataSet - 待划分的数据集
    axis - 划分的参照特征
    value - 分界线特征的值
Returns:
    无
"""
def splitDataSet(dataSet, axis, value):
    retDataSet = [] # 创建返回的数据集列表
    for featVec in dataSet: # 遍历数据集，featVec: [0, 0, 0, 0, 'no']
        if featVec[axis] == value: # 找到划分特征的值，去掉axis特征
            reducedFeatVec = featVec[:axis] # 取axis之前的特征,如[1, 0, 1, 2, 'yes']去掉第3个特征,取[1, 0],
            reducedFeatVec.extend(featVec[axis+1:]) # 取axis之后的特征,取[2, 'yes'],添加到前一个列表的末尾为[1, 0, 2, 'yes']，alist.extend(blist)在列表末尾一次性追加另一个序列中的多个值
            retDataSet.append(reducedFeatVec) # 添加到划分数据集中
    return retDataSet # 返回划分后的数据集，如第1个特征为0的子集：retDataSet: [[0, 0, 0, 'no'], [0, 0, 1, 'no'], [1, 0, 1, 'yes'], [1, 1, 0, 'yes'], [0, 0, 0, 'no']]

3.1.4.测试划分数据集函数

>>>
myDat, labels = createDataSet()
print("myDat = {}".format(myDat))
print("myDat第一个特征为1的划分 = {}".format(splitDataSet(myDat,0,1)))
print("myDat第一个特征为0的划分 = {}".format(splitDataSet(myDat,0,0)))

myDat = [[0, 0, 0, 0, 'no'], [0, 0, 0, 1, 'no'], [0, 1, 0, 1, 'yes'], [0, 1, 1, 0, 'yes'], [0, 0, 0, 0, 'no'], [1, 0, 0, 0, 'no'], [1, 0, 0, 1, 'no'], [1, 1, 1, 1, 'yes'], [1, 0, 1, 2, 'yes'], [1, 0, 1, 2, 'yes'], [2, 0, 1, 2, 'yes'], [2, 0, 1, 1, 'yes'], [2, 1, 0, 1, 'yes'], [2, 1, 0, 2, 'yes'], [2, 0, 0, 0, 'no']]
myDat第一个特征为1的划分 = [[0, 0, 0, 'no'], [0, 0, 1, 'no'], [1, 1, 1, 'yes'], [0, 1, 2, 'yes'], [0, 1, 2, 'yes']]
myDat第一个特征为0的划分 = [[0, 0, 0, 'no'], [0, 0, 1, 'no'], [1, 0, 1, 'yes'], [1, 1, 0, 'yes'], [0, 0, 0, 'no']]

3.1.5选择最好的数据集划分方式

计算条件经验熵：

H(D∣A)=∑i=1np(xi)⋅H(Di)H(D|A)=\sum_{i=1}^{n}p(x_{i})\cdot H(D_{i})

H(D∣A1)=515∗H(D1)+515∗H(D2)+515∗H(D3)=0.888H(D|A_{1})=\frac{5}{15}*H(D_{1})+\frac{5}{15}*H(D_{2})+\frac{5}{15}*H(D_{3})=0.888

H(D∣A2)=515∗H(D1)+1015∗H(D2)=0.647H(D|A_{2})=\frac{5}{15}*H(D_{1})+\frac{10}{15}*H(D_{2})=0.647

H(D∣A3)=615∗H(D1)+915∗H(D2)=0.551H(D|A_{3})=\frac{6}{15}*H(D_{1})+\frac{9}{15}*H(D_{2})=0.551

H(D∣A4)=415∗H(D1)+615∗H(D2)+515∗H(D3)=0.647H(D|A_{4})=\frac{4}{15}*H(D_{1})+\frac{6}{15}*H(D_{2})+\frac{5}{15}*H(D_{3})=0.647

H(D2∣A1)=0.667H(D_{2}|A_{1})=0.667

H(D2∣A2)=0.000H(D_{2}|A_{2})=0.000

H(D2∣A4)=0.444H(D_{2}|A_{4})=0.444

计算信息增益：

g(D∣A)=H(D)−H(D∣A)g(D|A)=H(D)-H(D|A)

g(D∣A1)=H(D)−H(D∣A1)=0.083g(D|A_{1})=H(D)-H(D|A_{1})=0.083

g(D∣A2)=H(D)−H(D∣A2)=0.324g(D|A_{2})=H(D)-H(D|A_{2})=0.324

g(D∣A3)=H(D)−H(D∣A3)=0.420g(D|A_{3})=H(D)-H(D|A_{3})=0.420 最大

g(D∣A4)=H(D)−H(D∣A4)=0.363g(D|A_{4})=H(D)-H(D|A_{4})=0.363

  • 特征A3的信息增益最大，故选择特征A3作为最优特征

g(D2∣A1)=H(D2)−H(D2∣A1)=0.252g(D_{2}|A_{1})=H(D_{2})-H(D_{2}|A_{1})=0.252

g(D2∣A2)=H(D2)−H(D2∣A2)=0.918g(D_{2}|A_{2})=H(D_{2})-H(D_{2}|A_{2})=0.918最大

g(D2∣A4)=H(D2)−H(D2∣A4)=0.474g(D_{2}|A_{4})=H(D_{2})-H(D_{2}|A_{4})=0.474

  • 特征A2的信息增益最大，故选择特征A2作为结点特征
"""
函数说明：选择最优特征
Parameters:
    dataSet - 数据集
returns:
    bestFeature - 信息增益最大的特征的索引值，即最优特征索引值
"""
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1 # 特征数量4,去掉标签
    baseEntropy = calcShannonEnt(dataSet) # 计算数据集D的经验熵
    bestInfoGain = 0.0 # 初始化最大信息增益
    bestFeature = -1 # 初始化最优特征
    for i in range(numFeatures): # 遍历每个特征
        featList = [example[i] for example in dataSet] # 取每个数据的第i个特征值
        uniqueVals = set(featList) # 把这些特征作为一个集合
        newEntropy = 0.0 # 初始化经验条件熵
        # 根据公式计算经验条件熵
        for value in uniqueVals: # 遍历集合中的特征值
            subDataSet = splitDataSet(dataSet, i, value) # 取第i个特征值为value的子集
            prob = len(subDataSet) / float(len(dataSet)) #　计算子集的概率
            newEntropy += prob * calcShannonEnt(subDataSet) # 计算经验条件熵，为各个子集熵的期望
        infoGain = baseEntropy - newEntropy # 计算信息增益
#         print("数据集的经验熵:%.3f"%baseEntropy)
#         print('第%d个特征的经验条件熵:%.3f'%(i+1, newEntropy))
#         print("第%d个特征的信息增益:%.3f" % (i+1, infoGain)) # 打印每个特征的信息增益
        # 选择最大信息增益的特征作为最优特征
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain # 更新信息增益，找到最大的信息增益
            bestFeature = i # 记录信息增益最大的特征的索引值，即最优特征
    return bestFeature # 返回最优特征

3.1.6.测试选择最佳划分方式的函数

>>>
myDat, labels = createDataSet()
print("myDat = {}".format(myDat))
# 测试选择最优特征函数
print("最优特征为:第%d个特征"%(chooseBestFeatureToSplit(myDat)+1))

myDat = [[0, 0, 0, 0, 'no'], [0, 0, 0, 1, 'no'], [0, 1, 0, 1, 'yes'], [0, 1, 1, 0, 'yes'], [0, 0, 0, 0, 'no'], [1, 0, 0, 0, 'no'], [1, 0, 0, 1, 'no'], [1, 1, 1, 1, 'yes'], [1, 0, 1, 2, 'yes'], [1, 0, 1, 2, 'yes'], [2, 0, 1, 2, 'yes'], [2, 0, 1, 1, 'yes'], [2, 1, 0, 1, 'yes'], [2, 1, 0, 2, 'yes'], [2, 0, 0, 0, 'no']]
最优特征为:第3个特征

3.1.7.递归构建决策树

"""
函数说明：求出现次数最多分类的名称
Parameters:
    classList - 类列表
Returns:
    sortedClassCount[0][0] - 出现次数最多的类别
"""
def majorityCnt(classList):
    classCount = {} # 定义类别次数的字典
    for vote in classList:
        if vote not in classCount.keys(): #如果第一次遇到一个类 
            classCount[vote] = 0 # 新建一个类计数器
        classCount[vote] += 1 # 计数+1,classCount={'no': 6, 'yes': 9}
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) # 根据字典的值(value)降序排序
    #sortedClassCount=[('yes', 9), ('no', 6)] <元组列表>
    return sortedClassCount[0][0]

>>>
classList = [example[-1] for example in myDat]
print('classList:\n',classList) # 打印类别标签
test_class = majorityCnt(classList)
print("test_class:\n",test_class) # 测试最多分类函数，打印最多分类类别

classList:
 ['no', 'no', 'yes', 'yes', 'no', 'no', 'no', 'yes', 'yes', 'yes', 'yes', 'yes', 'yes', 'yes', 'no']
test_class:
 yes

"""
函数说明:创建决策树
Parameters:
    dataSet - 训练数据集
    labels - 分类属性标签
    featLabels - 存储选择的最优特征标签
Returns:
    myTree - 决策树
"""
def createTree(dataSet, featLabels):
    #复制一份特征列表，因为后边要对labels做del，会改变原参数
    labels = list.copy(featLabels)
    classList = [example[-1] for example in dataSet] # 取类标签(是否放贷：yes、no)
    # classList: ['no', 'no', 'yes', 'yes', 'no', 'no', 'no', 'yes', 'yes', 'yes', 'yes', 'yes', 'yes', 'yes', 'no']
    if classList.count(classList[0]) == len(classList): # 如果类标签中只有一类
        return classList[0] # 返回该类，结束函数
    if len(dataSet[0]) == 1: # 如果数据只有类标签没有特征数据，也就是用尽所有特征也没法把数据划分为单一类
        return majorityCnt(classList) # 返回出现次数最多的类标签
    bestFeat = chooseBestFeatureToSplit(dataSet) # 最优特征的序号: A3, A2
    bestFeatLabel = labels[bestFeat]  # 最优特征的标签:有自己的房子 有工作							#最优特征的标签
    myTree = {bestFeatLabel:{}} # 根据最优特征的标签生成树
    del(labels[bestFeat]) # 删除已经划分过的特征标签
    featValues = [example[bestFeat] for example in dataSet] # 取最优特征的所有特征值
#    递归第一次，数据集D(15个)的最优特征A3的所有值：[0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0]
#    递归第二次，数据集D2(9个)的最优特征A2的所有值：：[0, 0, 1, 0, 0, 0, 1, 1, 0]
    uniqueVals = set(featValues) # 最优特征的特征值的集合：{0, 1} set去掉重复值
    for value in uniqueVals: # 遍历特征，创建决策树
        #剩余的类别名称
        subLabels = labels[:]
        # 调用子节点递归函数
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree # 返回给父节点迭代函数

3.1.8.测试建立决策树的递归函数

>>>
myDat, labels = createDataSet()
myTree = createTree(myDat, labels)
print("myTree = {}".format(myTree))

myTree = {'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}

3.2.在Python中使用Matplotlib注解绘制树形图

3.2.1.Matplotlib注解

# 图形设置
# 设置中文字体
font = FontProperties(fname = r'C:\Windows\Fonts\simsun.ttc',size=14) 
# 定义文本框
decisionNode = dict(boxstyle = "sawtooth", fc = "0.8")  # boxstyle='sawtooth'边框样式为波浪形，fc是颜色深度
leafNode = dict(boxstyle = "round4", fc = "0.8")
# 定义箭头格式
arrow_args = dict(arrowstyle = "<-")

"""
函数说明：绘制结点
Parameters:
    nodeTxt - 结点文字
    centerPt - 子节点(中心点)
    parentPt - 父节点(标注的箭头位置)
    nodeType - 结点类型
Returns:
    无
"""
def plotNode(nodeTxt, centerPt, parentPt, nodeType): # 绘制箭头的注解
    '''
    plt.annotate()注解函数，用来对坐标中的数据进行注解
    xy-点的坐标(箭头尖端)；xytext-注解内容位置坐标(文本位置)；xycoords，textcoord是坐标xy与xytext的说明:'axes fraction'--0,0 是轴域左下角，1,1 是右上角；arrowprops-用于设置箭头的形状，类型为字典类型；
    **kwargs-用于接收其他设置参数，如bbox设置文本的边框形状:sawtooth波浪形；va，ha表示给定坐标是node的中心
    '''
    #调用createPlot.ax1 该值存放在createPlot()函数中,Python所有变量都是全局变量，可以直接访问 
    createPlot.ax1.annotate(nodeTxt, xy = parentPt, \
            xycoords = 'axes fraction', xytext = centerPt, \
            textcoords = 'axes fraction', va = "center", \
            ha = "center", bbox = nodeType, arrowprops = arrow_args, FontProperties=font)

"""
函数说明：创建绘制面板,进行测试
"""
def createPlot():
    fig = plt.figure(1, facecolor = 'white') # 建立白色fig(画布)
    fig.clf() # 清空fig
    createPlot.ax1 = plt.subplot(111, frameon = False) # createPlot.ax1为全局变量，绘制图像的句柄，subplot为在画布中定义了一个绘图，111表示figure中的图有1行1列，即1个，最后的1代表第一个图，frameon表示是否绘制坐标轴矩形，去掉矩形坐标轴                 
    plotNode(u'决策结点', (0.5, 0.1), (0.1, 0.5), decisionNode)
    plotNode(u'叶节点', (0.8, 0.1), (0.3, 0.8), leafNode)
    plt.show()

>>> createPlot()

《Machine Learning in Action》| 第2章 决策树

3.2.2.构造注解树

"""
函数说明：获取决策树叶节点的数目
Parameters:
    myTree - 决策树
Returns:
    numLeafs - 决策树叶节点的数目
"""
def getNumLeafs(myTree):
    '''
    决策树：myTree={'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
    '''
    numLeafs = 0 # 初始化叶节点数目
    firstStr = list(myTree.keys())[0] # 根节点类标签名称:有自己的房子、有工作
    secondDict = myTree[firstStr] # 根节点对应的字典:{0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}、{0: 'no', 1: 'yes'},keys=dict_keys([0, 1]),values=dict_values(['no', 'yes'])
    for key in list(secondDict.keys()): # 遍历字典中的每一个关键词
        #递归过程分析：根节点('有自己的房子')：key=0,secondDict[0]={'有工作': {0: 'no', 1: 'yes'}}(字典) 
        #=>(递归调用子结点:'有工作')key=0,secondDict[0]=no,此时叶子节点+1,为1，再循环，key=1,secondDict[1]=yes,叶子节点+1,为2,循环结束，返回numleaf=2,退出递归函数
        #=>回到根节点：key=1,secondDict[1]=yes,叶节点+1,为3,函数结束，返回numleaf=3
        if type(secondDict[key]).__name__ == 'dict': # 如果关键词下存放的还是字典，说明不是叶节点secondDict[0]=0
            numLeafs += getNumLeafs(secondDict[key]) # 递归调用函数，统计子节点中的叶节点数目
        else: # 若该节点不是字典类型，则该节点为叶节点,计数器+1
            numLeafs += 1
    return numLeafs # 返回叶节点的数目，3

"""
函数说明：获取决策树的深度(层数)
Parameters:
    myTree - 决策树
    
Returns:
    maxDepth - 决策树的深度(层数)
"""
def getTreeDepth(myTree):
    maxDepth = 0 # 初始化决策树深度
    firstStr = list(myTree.keys())[0] # 根节点类标签名称
    secondDict = myTree[firstStr] # 根节点对应的字典
    for key in list(secondDict.keys()): # 遍历字典中的每一个关键词
        #递归过程分析：根节点('有自己的房子')：key=0,secondDict[0]={'有工作': {0: 'no', 1: 'yes'}}(字典) 
        #=>(递归调用子结点:'有工作')key=0,secondDict[0]=no,此时子节点的thisDepth=1，再循环，key=1,secondDict[1]=yes,叶子节,thisDepth=1循环结束,返回maxDepth=1,退出递归函数
        #=>回到根节点：thisDepth+1,为2,更新maxDepth=2,再循环,key=1,secondDict[1]=yes,叶节点,thisDepth=1,函数结束，返回maxDepth=2
        if type(secondDict[key]).__name__ == 'dict': # 如果关键词下存放的还是字典，说明不是叶节点
            thisDepth = 1 + getTreeDepth(secondDict[key]) # 递归调用函数，统计子树深度+1(根结点)
        else: # 若该节点不是字典类型，则该节点为叶节点，深度为1
            thisDepth = 1
        if thisDepth > maxDepth: # 更新层数
            maxDepth = thisDepth
    return maxDepth # 返回决策树的最大深度,2

"""
函数说明：输出预先存储的树信息，避免每次测试代码时都要从数据中创建树,用于测试
"""
def retrieveTree(i):
    listOfTrees = [{'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}]
    return listOfTrees[i] # 返回预定义的树结构

>>>
print("retrieveTree(0) = {}".format(retrieveTree(0)))
myTree = retrieveTree(0)
print("叶节点数 = {}".format(getNumLeafs(myTree)))
print("层数 = {}".format(getTreeDepth(myTree)))

retrieveTree(0) = {'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
叶节点数 = 3
层数 = 2

3.2.3绘制决策树

"""
函数说明：绘制注释
Parameters:
    cntrPt、parentPt - 子节点和父节点位置
    txtString - 注释内容
Returns:
    无
"""
def plotMidText(cntrPt, parentPt, txtString):
    #绘制注释的坐标位置
    xMid = (parentPt[0] - cntrPt[0]) / 2.0 + cntrPt[0] # X轴
    yMid = (parentPt[1] - cntrPt[1]) / 2.0 + cntrPt[1] # Y轴
    #绘制注释
    createPlot.ax1.text(xMid, yMid, txtString, FontProperties = font)

"""
函数说明：绘制决策树
Parameters:
    myTree - 决策树
    parentPt - 父节点位置
    nodeTxt - 结点名
Returns:
    无
"""
def plotTree(myTree, parentPt, nodeTxt):
    numLeafs = getNumLeafs(myTree) # 获取决策树叶节点数目，3
    depth = getTreeDepth(myTree) # 获取决策树层数，2
    firstStr = list(myTree.keys())[0] # 根节点类标签名称:有自己的房子、有工作
    cntrPt = (plotTree.xOff + (1.0 + np.float(numLeafs)) / 2.0 \
             / plotTree.totalW, plotTree.yOff) # 子节点位置 
    plotMidText(cntrPt, parentPt, nodeTxt) # 注释文本内容
    plotNode(firstStr, cntrPt, parentPt, decisionNode) # 绘制决策结点
    secondDict = myTree[firstStr] # 根节点对应的字典
    plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD
    for key in list(secondDict.keys()):
        if type(secondDict[key]).__name__ == 'dict': # 测试该结点是否为字典，如果不是字典，代表此结点为叶子结点
            plotTree(secondDict[key], cntrPt, str(key)) # 不是叶结点，递归调用继续绘制
        else:
            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

"""
函数说明:创建绘制面板
Parameters:
    inTree - 决策树
Returns:
    无
"""
def createPlotTree(inTree):
    fig = plt.figure(1, facecolor = 'white') # 创建fig
    fig.clf() # 清空fig
    axprops = dict(xticks = [], yticks = [])
    createPlot.ax1 = plt.subplot(111, frameon = False, **axprops) # 去掉矩形坐标轴
    plotTree.totalW = np.float(getNumLeafs(inTree)) # 获取决策树叶结点数目，作为树的总宽度
    plotTree.totalD = np.float(getTreeDepth(inTree)) # 获取决策树层数，作为树的总高度
    plotTree.xOff = -0.5 / plotTree.totalW # 已经绘制的x轴位置，x偏移 
    plotTree.yOff = 1.0 # 已经绘制的y轴位置
    plotTree(inTree, (0.5, 1.0), '') # 绘制决策树
    plt.show() # 显示绘制结果

>>>
myTree = retrieveTree(0)
createPlotTree(myTree)

《Machine Learning in Action》| 第2章 决策树

>>>
myTree['有自己的房子'][1] = 'maybe'
createPlotTree(myTree)

《Machine Learning in Action》| 第2章 决策树

3.3.测试和存储分类器

3.3.1.使用决策树执行分类

"""
函数说明：使用决策树分类
Parameters:
    inputTree - 已经生成的决策树
    featLabels - 最优特征标签
    testVec - 测试向量，顺序对应最优特征标签
Returns:
    classLabel - 分类结果
"""
def classify(inputTree, featLabels, testVec):
    firstStr = list(inputTree.keys())[0] # 根节点特征标签:有自己的房子、有工作
    secondDict = inputTree[firstStr] # 根节点对应的字典:{0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}、{0: 'no', 1: 'yes'}
    featIndex = featLabels.index(firstStr) # 根特征对应的特征序号
#     print('featIndex:',featIndex)
    for key in secondDict.keys(): #遍历所有的关键词
        if testVec[featIndex] == key: # 匹配到了待分类向量的第featIndex个特征
            if type(secondDict[key]).__name__ == 'dict': # 结点为字典
                classLabel = classify(secondDict[key], featLabels, testVec) # 对该节点递归调用分类函数
            else:
                classLabel = secondDict[key]
    return classLabel # 返回分类结果

3.3.2.测试决策树分类函数

>>>
myDat, labels = createDataSet()
print("myDat = {}".format(myDat))
print("labels = {}".format(labels))
myTree = createTree(myDat, labels)
print("myTree = {}".format(myTree))
testVec = [0, 0, 0, 0] # [0, 1]代表没有房子有工作
result = classify(myTree, labels, testVec)
if result == 'yes':
     print('放贷')
if result == 'no':
     print('不放贷')

myDat = [[0, 0, 0, 0, 'no'], [0, 0, 0, 1, 'no'], [0, 1, 0, 1, 'yes'], [0, 1, 1, 0, 'yes'], [0, 0, 0, 0, 'no'], [1, 0, 0, 0, 'no'], [1, 0, 0, 1, 'no'], [1, 1, 1, 1, 'yes'], [1, 0, 1, 2, 'yes'], [1, 0, 1, 2, 'yes'], [2, 0, 1, 2, 'yes'], [2, 0, 1, 1, 'yes'], [2, 1, 0, 1, 'yes'], [2, 1, 0, 2, 'yes'], [2, 0, 0, 0, 'no']]
labels = ['年龄', '有工作', '有自己的房子', '信贷情况']
myTree = {'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
不放贷

3.3.3.存储读取决策树

"""
函数说明：存储决策器
Parameters:
    inputTree - 已经生成的决策树
    filename - 决策树的存储文件名
Returns:
    无
"""
def storeTree(inputTree, filename):
    with open(filename, 'wb') as fw: #相当于 fw = open(filename, 'wb')，必须用二进制写入
        pickle.dump(inputTree, fw) # pickle序列化对象存储到文件中

"""
函数说明：读取决策树
Parameters:
    filename - 决策树的存储文件名
Returns:
    pickle.load(fr) - 决策树字典
"""
def grabTree(filename):
    fr = open(filename, 'rb') # 读取二进制文件
    return pickle.load(fr) # 返回决策树字典


>>>
myTree = retrieveTree(0) # 测试预定义树结构
print('myTree={}'.format(myTree))  # 打印决策树
storeTree(myTree, "classifierStorage.txt")
loadedTree = grabTree("classifierStorage.txt")
print("读取到的决策树 = {}".format(loadedTree))

myTree={'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
读取到的决策树 = {'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}

3.4. 示例：预测隐形眼镜类型

3.4.1.读取数据

>>>
fr = open(r'D:\dataset\inaction\Decision Tree\lenses.txt')
lenses = [inst.strip().split('\t') for inst in fr.readlines()]
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
print('lenses:\n',lenses)
print('lensesLabels:\n',lensesLabels)

lenses:
 [['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']]
lensesLabels:
 ['age', 'prescript', 'astigmatic', 'tearRate']

3.4.2.生成决策树

>>>
lensesTree = createTree(lenses, lensesLabels)
print("lensesTree = {}".format(lensesTree))

lensesTree = {'tearRate': {'reduced': 'no lenses', 'normal': {'astigmatic': {'yes': {'prescript': {'myope': 'hard', 'hyper': {'age': {'pre': 'no lenses', 'presbyopic': 'no lenses', 'young': 'hard'}}}}, 'no': {'age': {'pre': 'soft', 'presbyopic': {'prescript': {'myope': 'no lenses', 'hyper': 'soft'}}, 'young': 'soft'}}}}}}

>>> createPlotTree(lensesTree)

《Machine Learning in Action》| 第2章 决策树

3.4.3.使用决策树模型进行分类

>>>
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
testVec = lenses[0][:-1]
result = classify(lensesTree, lensesLabels, testVec)
print('%s属于%s' % (testVec, result))

['young', 'myope', 'no', 'reduced']属于no lenses

对 lenses 数据集所有数据进行决策树分类预测

>>>
errorCount = 0.0 # 分类错误计数
for i in range(len(lenses)):
    classifierResult = classify(lensesTree, lensesLabels, lenses[i][:-1])
    classLabel = lenses[i][-1]
    print("分类返回结果:%s \t 真实结果:%s" % (classifierResult, classLabel))
    if classifierResult != classLabel:
        errorCount += 1.0 # 分类错误个数计数
print("错误总数:%d\n错误率:%g%%" % (errorCount, errorCount / len(lenses)  * 100)) #打印错误个数及错误率

分类返回结果:no lenses 	 真实结果:no lenses
分类返回结果:soft 	 真实结果:soft
分类返回结果:no lenses 	 真实结果:no lenses
分类返回结果:hard 	 真实结果:hard
分类返回结果:no lenses 	 真实结果:no lenses
分类返回结果:soft 	 真实结果:soft
分类返回结果:no lenses 	 真实结果:no lenses
分类返回结果:hard 	 真实结果:hard
分类返回结果:no lenses 	 真实结果:no lenses
分类返回结果:soft 	 真实结果:soft
分类返回结果:no lenses 	 真实结果:no lenses
分类返回结果:hard 	 真实结果:hard
分类返回结果:no lenses 	 真实结果:no lenses
分类返回结果:soft 	 真实结果:soft
分类返回结果:no lenses 	 真实结果:no lenses
分类返回结果:no lenses 	 真实结果:no lenses
分类返回结果:no lenses 	 真实结果:no lenses
分类返回结果:no lenses 	 真实结果:no lenses
分类返回结果:no lenses 	 真实结果:no lenses
分类返回结果:hard 	 真实结果:hard
分类返回结果:no lenses 	 真实结果:no lenses
分类返回结果:soft 	 真实结果:soft
分类返回结果:no lenses 	 真实结果:no lenses
分类返回结果:no lenses 	 真实结果:no lenses
错误总数:0
错误率:0%

3.5. 示例：预测西瓜数据集是否好瓜

西瓜数据集2.0

编号 色泽 根蒂 敲声 纹理 脐部 触感 好瓜
1 青绿 蜷缩 浊响 清晰 凹陷 硬滑 是
2 乌黑 蜷缩 沉闷 清晰 凹陷 硬滑 是
3 乌黑 蜷缩 浊响 清晰 凹陷 硬滑 是
4 青绿 蜷缩 沉闷 清晰 凹陷 硬滑 是
5 浅白 蜷缩 浊响 清晰 凹陷 硬滑 是
6 青绿 稍蜷 浊响 清晰 稍凹 软粘 是
7 乌黑 稍蜷 浊响 稍糊 稍凹 软粘 是
8 乌黑 稍蜷 浊响 清晰 稍凹 硬滑 是
9 乌黑 稍蜷 沉闷 稍糊 稍凹 硬滑 否
10 青绿 硬挺 清脆 清晰 平坦 软粘 否
11 浅白 硬挺 清脆 模糊 平坦 硬滑 否
12 浅白 蜷缩 浊响 模糊 平坦 软粘 否
13 青绿 稍蜷 浊响 稍糊 凹陷 硬滑 否
14 浅白 稍蜷 沉闷 稍糊 凹陷 硬滑 否
15 乌黑 稍蜷 浊响 清晰 稍凹 软粘 否
16 浅白 蜷缩 浊响 模糊 平坦 硬滑 否
17 青绿 蜷缩 沉闷 稍糊 稍凹 硬滑 否

3.5.1.读取数据

>>>
fr = open(r"D:\dataset\inaction\Decision Tree\watermelon2.0.txt", encoding='utf-8') # 文件中有汉字，设置utf-8编码
watermelon = [inst.strip().split('\t') for inst in fr.readlines()]
watermelonLabels = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']
print("dataSet:\n",watermelon)
print("Labels:\n",watermelonLabels)

dataSet:
 [['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'], ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'], ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'], ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'], ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'], ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '好瓜'], ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '好瓜'], ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '好瓜'], ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜'], ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '坏瓜'], ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '坏瓜'], ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '坏瓜'], ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '坏瓜'], ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '坏瓜'], ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '坏瓜'], ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '坏瓜'], ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜']]
Labels:
 ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']

3.5.2.生成决策树

>>>
watermelonTree = createTree(watermelon, watermelonLabels)
print("watermelonTree = {}".format(watermelonTree))

watermelonTree = {'纹理': {'清晰': {'根蒂': {'稍蜷': {'色泽': {'青绿': '好瓜', '乌黑': {'触感': {'硬滑': '好瓜', '软粘': '坏瓜'}}}}, '蜷缩': '好瓜', '硬挺': '坏瓜'}}, '模糊': '坏瓜', '稍糊': {'触感': {'硬滑': '坏瓜', '软粘': '好瓜'}}}}

3.5.3.绘制决策树

>>> createPlotTree(watermelonTree)

《Machine Learning in Action》| 第2章 决策树
附所有程序代码：

# -*- coding: utf-8 -*-
"""
Created on Wed Oct 24 10:39:54 2018

@author: YAOTIANLONG
"""
from matplotlib.font_manager import FontProperties
import matplotlib.pyplot as plt
from math import log
import operator
import pickle # 存储和读取决策树

##-----------------创建决策树----------
"""
函数说明：计算给定数据集的经验熵(entropy)
Parameters:
    dataSet - 数据集
Returns:
    shannonEnt - 香农熵(经验熵)
"""
def calcShannonEnt(dataSet):
    numEntries = len(dataSet) # 数据集的词条数目
#    print('numEntries={}'.format(numEntries)) # numEntries=15
    labelCounts = {} #  保存每个标签出现次数的字典
    for featVec in dataSet: # 遍历数据集的每行数据
        currentLabel = featVec[-1] # 数据的最后一列是标签，记录当前标签
        if currentLabel not in labelCounts.keys(): # 如果字典里没有该标签
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1 # 当前出现次数+1
#    print('labelCounts={}'.format(labelCounts)) # labelCounts={'no': 6, 'yes': 9}
    shannonEnt = 0.0 # 初始化香农熵
    # 根据公式计算经验熵
    '''
    H(D)=(|C1|/|D|)*log2|C1|/|D|)+(|C2|/|D|)*log2|C2|/|D|)...
    ------------------------------------------------------------
    H(D)=-6/15*log2(6/15)-9/15*log2(9/15)=0.971
    --------------------------------------------
    H(D2)=-3/9*log2(3/9)-6/9*log2(6/9)=0.918
    '''
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries # 计算类别的概率
        shannonEnt -= prob * log(prob, 2) # 计算经验熵，为信息量的期望
    return shannonEnt # 返回香农熵,shannonEnt=0.9709505944546686

"""
函数说明：创建测试数据集
    测试集采用统计学习方法的贷款申请样本表
    年龄：0(青年)，1(中年)，2(老年)
    有工作：0(否)，1(是)
    有自己的房子：0(否)，1(是)
    信贷情况：0(一般)，1(好)，2(非常好)
    类别：yes(放贷)，no(不放贷)
Parameters:
    无
Returns:
    dataSet - 数据集
    labels - 特征标签
"""
def createDataSet():
    dataSet = [ # 数据集
            [0, 0, 0, 0,'no'],
            [0, 0, 0, 1, 'no'],
            [0, 1, 0, 1, 'yes'],
            [0, 1, 1, 0, 'yes'],
            [0, 0, 0, 0, 'no'],
            [1, 0, 0, 0, 'no'],
            [1, 0, 0, 1, 'no'],
            [1, 1, 1, 1, 'yes'],
            [1, 0, 1, 2, 'yes'],
            [1, 0, 1, 2, 'yes'],
            [2, 0, 1, 2, 'yes'],
            [2, 0, 1, 1, 'yes'],
            [2, 1, 0, 1, 'yes'],
            [2, 1, 0, 2, 'yes'],
            [2, 0, 0, 0, 'no']]
    labels = ['年龄', '有工作', '有自己的房子', '信贷情况'] # 特征标签
    return dataSet, labels # 返回数据集和分类属性

"""
函数说明：按照给定特征划分数据集
Paramerters:
    dataSet - 待划分的数据集
    axis - 划分的参照特征
    value - 分界线特征的值
Returns:
    无
"""
def splitDataSet(dataSet, axis, value):
    retDataSet = [] # 创建返回的数据集列表
    for featVec in dataSet: # 遍历数据集，featVec: [0, 0, 0, 0, 'no']
        if featVec[axis] == value: # 找到划分特征的值，去掉axis特征
            reducedFeatVec = featVec[:axis] # 取axis之前的特征,如[1, 0, 1, 2, 'yes']去掉第3个特征,取[1, 0],
            reducedFeatVec.extend(featVec[axis+1:]) # 取axis之后的特征,取[2, 'yes'],添加到前一个列表的末尾为[1, 0, 2, 'yes']，alist.extend(blist)在列表末尾一次性追加另一个序列中的多个值
            retDataSet.append(reducedFeatVec) # 添加到划分数据集中
    return retDataSet # 返回划分后的数据集，如第1个特征为0的子集：retDataSet: [[0, 0, 0, 'no'], [0, 0, 1, 'no'], [1, 0, 1, 'yes'], [1, 1, 0, 'yes'], [0, 0, 0, 'no']]

"""
函数说明：选择最优特征
Parameters:
    dataSet - 数据集
returns:
    bestFeature - 信息增益最大的特征的索引值，即最优特征索引值
"""
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1 # 特征数量4,去掉标签
    baseEntropy = calcShannonEnt(dataSet) # 计算数据集D的经验熵
    bestInfoGain = 0.0 # 初始化最大信息增益
    bestFeature = -1 # 初始化最优特征
    for i in range(numFeatures): # 遍历每个特征
        featList = [example[i] for example in dataSet] # 取每个数据的第i个特征值
        uniqueVals = set(featList) # 把这些特征作为一个集合
        newEntropy = 0.0 # 初始化经验条件熵
        # 根据公式计算经验条件熵
        for value in uniqueVals: # 遍历集合中的特征值
            subDataSet = splitDataSet(dataSet, i, value) # 取第i个特征值为value的子集
            prob = len(subDataSet) / float(len(dataSet)) #　计算子集的概率
            newEntropy += prob * calcShannonEnt(subDataSet) # 计算经验条件熵，为各个子集熵的期望
        infoGain = baseEntropy - newEntropy # 计算信息增益
        '''
        H(D|A)=p1*H(D1)+p2*H(D2)+p3*H(D3)...
        ------------------------------------
        H(D|A1)=5/15*H(D1)+5/15*H(D2)+5/15*H(D3)=0.888
        H(D|A2)=5/15*H(D1)+10/15*H(D2)=0.647
        H(D|A3)=6/15*H(D1)+9/15*H(D2)=0.551
        H(D|A4)=4/15*H(D1)+6/15*H(D2)+5/15*H(D3)=0.608
        ----------------------------------------------
        H(D2|A1)=0.667
        H(D2|A2)=0.000
        H(D2|A4)=0.444
        '''
        '''
        g(D,A)=H(D)-H(D|A)
        -------------------
        g(D,A1)=H(D)-H(D|A1)=0.083
        g(D,A2)=H(D)-H(D|A2)=0.324
        g(D,A3)=H(D)-H(D|A3)=0.420 最大
        g(D,A4)=H(D)-H(D|A4)=0.363
        =>特征A3的信息增益最大，故选择特征A3作为最优特征
        ----------------------------------------------
        g(D2,A1)=H(D2)-H(D2|A1)=0.252
        g(D2,A2)=H(D2)-H(D2|A2)=0.918 最大
        g(D2,A4)=H(D2)-H(D|A4)=0.474
        =>特征A2的信息增益最大，故选择特征A2作为结点特征
        '''
#        print("数据集的经验熵:%.3f"%baseEntropy)
#        print('第%d个特征的经验条件熵:%.3f'%(i+1, newEntropy))
#        print("第%d个特征的信息增益:%.3f" % (i+1, infoGain)) # 打印每个特征的信息增益#        print('g(D,A%d)=%.3f'%(i+1,infoGain))
        # 选择最大信息增益的特征作为最优特征
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain # 更新信息增益，找到最大的信息增益
            bestFeature = i # 记录信息增益最大的特征的索引值，即最优特征
    return bestFeature # 返回最优特征
     
"""
函数说明：求出现次数最多分类的名称（最大投票表决机制）
Parameters:
    classList - 类列表
Returns:
    sortedClassCount[0][0] - 出现次数最多的类别
"""
def majorityCnt(classList):
    classCount = {} # 定义类别次数的字典
    for vote in classList:
        if vote not in classCount.keys(): #如果第一次遇到一个类 
            classCount[vote] = 0 # 新建一个类计数器
        classCount[vote] += 1 # 计数+1,classCount={'no': 6, 'yes': 9}
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True) # 根据字典的值(value)降序排序
    #sortedClassCount=[('yes', 9), ('no', 6)] <元组列表>
    return sortedClassCount[0][0]

"""
函数说明:创建决策树
Parameters:
    dataSet - 训练数据集
    labels - 分类属性标签
    featLabels - 存储选择的最优特征标签
Returns:
    myTree - 决策树
"""
def createTree(dataSet, featLabels):
    #复制一份特征列表，因为后边要对labels做del，会改变原参数
    labels = list.copy(featLabels)
    classList = [example[-1] for example in dataSet] # 取类标签(是否放贷：yes、no)
    # classList: ['no', 'no', 'yes', 'yes', 'no', 'no', 'no', 'yes', 'yes', 'yes', 'yes', 'yes', 'yes', 'yes', 'no']
    if classList.count(classList[0]) == len(classList): # 如果类标签中只有一类
        return classList[0] # 返回该类，结束函数
    if len(dataSet[0]) == 1: # 如果数据只有类标签没有特征数据，也就是用尽所有特征也没法把数据划分为单一类
        return majorityCnt(classList) # 返回出现次数最多的类标签
    bestFeat = chooseBestFeatureToSplit(dataSet) # 最优特征的序号: A3, A2
    bestFeatLabel = labels[bestFeat]  # 最优特征的标签:有自己的房子 有工作							#最优特征的标签
    myTree = {bestFeatLabel:{}} # 根据最优特征的标签生成树
    del(labels[bestFeat]) # 删除已经划分过的特征标签
    featValues = [example[bestFeat] for example in dataSet] # 取最优特征的所有特征值
#    递归第一次，数据集D(15个)的最优特征A3的所有值：[0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0]
#    递归第二次，数据集D2(9个)的最优特征A2的所有值：：[0, 0, 1, 0, 0, 0, 1, 1, 0]
    uniqueVals = set(featValues) # 最优特征的特征值的集合：{0, 1} set去掉重复值
    for value in uniqueVals: # 遍历特征，创建决策树
        #剩余的类别名称
        subLabels = labels[:]
        # 调用子节点递归函数
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree # 返回给父节点迭代函数

"""
函数说明：测试决策树构造
"""
def test0():
    print('----------------------测试决策树构造----------------------')
    myDat, labels = createDataSet() # 导入数据集
    print('myDat={}'.format(myDat)) # 打印数据集
    print('labels={}'.format(labels))
    # 测试香农熵函数，验证香农熵
    print('shannonEnt={}'.format(calcShannonEnt(myDat))) 
    # 测试按特征划分数据集函数
    print('myDat第1个特征为0的划分:\n',splitDataSet(myDat,0,0)) # 返回年龄为青年的5个数据集
    # 测试最多分类函数
    classList = [example[-1] for example in myDat]
    print('classList:\n',classList) # 打印类别标签
    test_class = majorityCnt(classList)
    print("test_class:\n",test_class) # 测试最多分类函数，打印最多分类类别
    # 测试选择最优特征函数
    print("-------最优特征为:第%d个特征"%(chooseBestFeatureToSplit(myDat)+1))
    # 测试创建决策树函数
    myTree = createTree(myDat, labels)
    print("-------生成的决策树:\n  myTree={}".format(myTree))
    
##-----------------在Python中使用Matplotlib注解绘制树形图----------
"""决策树可视化
可视化需要用到的函数：
getNumLeafs：获取决策树叶子结点的数目
getTreeDepth：获取决策树的层数
plotNode：绘制结点
plotMidText：标注有向边属性值
plotTree：绘制决策树
createPlot：创建绘制面板
显示中文，需要设置FontProperties
"""
###---------Matplotlib注解测试---------
# 图形设置
# 设置中文字体
font = FontProperties(fname = r'C:\Windows\Fonts\simsun.ttc',size=14) 
# 定义文本框
decisionNode = dict(boxstyle = "sawtooth", fc = "0.8")  # boxstyle='sawtooth'边框样式为波浪形，fc是颜色深度
leafNode = dict(boxstyle = "round4", fc = "0.8")
# 定义箭头格式
arrow_args = dict(arrowstyle = "<-")

"""
函数说明：绘制结点
Parameters:
    nodeTxt - 结点文字
    centerPt - 子节点(中心点)
    parentPt - 父节点(标注的箭头位置)
    nodeType - 结点类型
Returns:
    无
"""
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    '''
    plt.annotate()注解函数，用来对坐标中的数据进行注解
    xy-点的坐标(箭头尖端)；xytext-注解内容位置坐标(文本位置)；xycoords，textcoord是坐标xy与xytext的说明:'axes fraction'--0,0 是轴域左下角，1,1 是右上角；arrowprops-用于设置箭头的形状，类型为字典类型；
    **kwargs-用于接收其他设置参数，如bbox设置文本的边框形状:sawtooth波浪形；va，ha表示给定坐标是node的中心
    '''
    #调用createPlot.ax1 该值存放在createPlot()函数中,Python所有变量都是全局变量，可以直接访问 
    createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',# 绘制结点
		xytext=centerPt, textcoords='axes fraction',
		va="center", ha="center", bbox=nodeType, arrowprops=arrow_args, FontProperties=font)

"""
函数说明：创建绘制面板,进行测试
"""
def createPlot():
    fig = plt.figure(1, facecolor = 'white') # 建立白色fig(画布)
    fig.clf() # 清空fig
    createPlot.ax1 = plt.subplot(111, frameon = False) # createPlot.ax1为全局变量，绘制图像的句柄，subplot为在画布中定义了一个绘图，111表示figure中的图有1行1列，即1个，最后的1代表第一个图，frameon表示是否绘制坐标轴矩形，去掉矩形坐标轴                 
    plotNode(u'决策结点', (0.5, 0.1), (0.1, 0.5), decisionNode)
    plotNode(u'叶节点', (0.8, 0.1), (0.3, 0.8), leafNode)
    plt.show()

###---------构造注解树---------
"""
函数说明：获取决策树叶节点的数目
Parameters:
    myTree - 决策树
Returns:
    numLeafs - 决策树叶节点的数目
"""
def getNumLeafs(myTree):
    '''
    决策树：myTree={'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
    '''
    numLeafs = 0 # 初始化叶节点数目
    firstStr = list(myTree.keys())[0] #python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性，可以使用list(myTree.keys())[0]
    secondDict = myTree[firstStr] # 根节点对应的字典:{0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}、{0: 'no', 1: 'yes'},keys=dict_keys([0, 1]),values=dict_values(['no', 'yes'])
    for key in secondDict.keys(): # 遍历字典中的每一个关键词
        #递归过程分析：根节点('有自己的房子')：key=0,secondDict[0]={'有工作': {0: 'no', 1: 'yes'}}(字典) 
        #=>(递归调用子结点:'有工作')key=0,secondDict[0]=no,此时叶子节点+1,为1，再循环，key=1,secondDict[1]=yes,叶子节点+1,为2,循环结束，返回numleaf=2,退出递归函数
        #=>回到根节点：key=1,secondDict[1]=yes,叶节点+1,为3,函数结束，返回numleaf=3
        if type(secondDict[key]).__name__=='dict': # 如果关键词下存放的还是字典，说明不是叶节点secondDict[0]=0
            numLeafs += getNumLeafs(secondDict[key]) # 递归调用函数，统计子节点中的叶节点数目
        else:   
            numLeafs +=1 # 若该节点不是字典类型，则该节点为叶节点,计数器+1
    return numLeafs  # 返回叶节点的数目，3

"""
函数说明：获取决策树的深度(层数)
Parameters:
    myTree - 决策树
    
Returns:
    maxDepth - 决策树的深度(层数)
"""
def getTreeDepth(myTree):
    maxDepth = 0 # 初始化决策树深度
    firstStr = list(myTree.keys())[0] # 根节点类标签名称
    secondDict = myTree[firstStr] # 根节点对应的字典
    for key in secondDict.keys(): # 遍历字典中的每一个关键词
        #递归过程分析：根节点('有自己的房子')：key=0,secondDict[0]={'有工作': {0: 'no', 1: 'yes'}}(字典) 
        #=>(递归调用子结点:'有工作')key=0,secondDict[0]=no,此时子节点的thisDepth=1，再循环，key=1,secondDict[1]=yes,叶子节,thisDepth=1循环结束,返回maxDepth=1,退出递归函数
        #=>回到根节点：thisDepth+1,为2,更新maxDepth=2,再循环,key=1,secondDict[1]=yes,叶节点,thisDepth=1,函数结束，返回maxDepth=2           
        if type(secondDict[key]).__name__=='dict': # 如果关键词下存放的还是字典，说明不是叶节点
            thisDepth = 1 + getTreeDepth(secondDict[key]) # 递归调用函数，统计子树深度+1(根结点)
        else:   
            thisDepth = 1 # 若该节点不是字典类型，则该节点为叶节点，深度为1
        if thisDepth > maxDepth: maxDepth = thisDepth	 # 更新层数
    return maxDepth  # 返回决策树的最大深度,2

"""
函数说明：输出预先存储的树信息，避免每次测试代码时都要从数据中创建树,用于测试
"""
def retrieveTree(i):
    listOfTrees = [{'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}]
    return listOfTrees[i] # 返回预定义的树结构

###---------绘制决策树---------
"""
函数说明：绘制注释
Parameters:
    cntrPt、parentPt - 子节点和父节点位置
    txtString - 注释内容
Returns:
    无
"""
def plotMidText(cntrPt, parentPt, txtString):
    #绘制注释的坐标位置
	xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]	 # X轴													
	yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1] # Y轴
    #绘制注释
	createPlot.ax1.text(xMid, yMid, txtString, FontProperties = font)

"""
函数说明：绘制决策树
Parameters:
    myTree - 决策树
    parentPt - 父节点位置
    nodeTxt - 结点名
Returns:
    无
"""
def plotTree(myTree, parentPt, nodeTxt):
    numLeafs = getNumLeafs(myTree) # 获取决策树叶节点数目，3
    depth = getTreeDepth(myTree) # 获取决策树层数，2
    firstStr = list(myTree.keys())[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] # 根节点对应的字典
    plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD
    for key in list(secondDict.keys()):
        if type(secondDict[key]).__name__ == 'dict': # 测试该结点是否为字典，如果不是字典，代表此结点为叶子结点
            plotTree(secondDict[key], cntrPt, str(key)) # 不是叶结点，递归调用继续绘制
        else:
            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

"""
函数说明:创建绘制面板
Parameters:
    inTree - 决策树
Returns:
    无
"""
def createPlotTree(inTree):
    fig = plt.figure(1, facecolor = 'white') # 创建fig
    fig.clf() # 清空fig
    axprops = dict(xticks = [], yticks = [])
    createPlot.ax1 = plt.subplot(111, frameon = False, **axprops) # 去掉矩形坐标轴
    plotTree.totalW = float(getNumLeafs(inTree)) # 获取决策树叶结点数目，作为树的总宽度
    plotTree.totalD = float(getTreeDepth(inTree)) # 获取决策树层数，作为树的总高度
    plotTree.xOff = -0.5 / plotTree.totalW # 已经绘制的x轴位置，x偏移 
    plotTree.yOff = 1.0 # 已经绘制的y轴位置
    plotTree(inTree, (0.5, 1.0), '') # 绘制决策树
    plt.show() # 显示绘制结果																			#显示绘制结果

"""
函数说明：测试决策树绘制
"""
def test1():
    print('----------------------测试决策树绘制----------------------')
    createPlot() # 测试Matplotlib注解
    myTree = retrieveTree(0) # 测试预定义树结构
    print('myTree={}'.format(myTree))  # 打印决策树
    print('叶节点数:',getNumLeafs(myTree)) # 打印叶节点数
    print('层数:',getTreeDepth(myTree)) # 打印层数
    createPlotTree(myTree) # 绘制决策树
##-----------------测试决策树分类器----------
"""
函数说明：使用决策树分类
Parameters:
    inputTree - 已经生成的决策树
    featLabels - 最优特征标签
    testVec - 测试向量，顺序对应最优特征标签
Returns:
    classLabel - 分类结果
"""
def classify(inputTree, featLabels, testVec):
    firstStr = list(inputTree.keys())[0] # 根节点特征标签:有自己的房子、有工作
    secondDict = inputTree[firstStr] # 根节点对应的字典:{0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}、{0: 'no', 1: 'yes'}
    featIndex = featLabels.index(firstStr) # 根特征对应的特征序号
#     print('featIndex:',featIndex)
    for key in secondDict.keys(): #遍历所有的关键词
        if testVec[featIndex] == key: # 匹配到了待分类向量的第featIndex个特征
            if type(secondDict[key]).__name__ == 'dict': # 结点为字典
                classLabel = classify(secondDict[key], featLabels, testVec) # 对该节点递归调用分类函数
            else:
                classLabel = secondDict[key]
    return classLabel # 返回分类结果

"""
函数说明：测试决策树分类
"""
def test2():
    print('----------------------测试决策树分类----------------------')
    myDat, labels = createDataSet() # 导入数据
    print('myDat:\n',myDat) # 打印数据集
    print('labels:\n',labels) # 打印分类标签
    myTree = createTree(myDat, labels) # 创建决策树
    print('myTree={}'.format(myTree)) # 打印生存的决策树
    testVec = [0, 0, 0, 0] # 测试数据，[0,1]代表没房子有工作
    result = classify(myTree, labels, testVec) # 分类结果
    if result == 'yes':
        print('测试数据%s申请贷款结果为放贷'%testVec)
    if result == 'no':
        print('测试数据%s申请贷款结果为不放贷'%testVec)
        
##-----------------存储决策树分类器-----------------
"""
函数说明：存储决策器
Parameters:
    inputTree - 已经生成的决策树
    filename - 决策树的存储文件名
Returns:
    无
"""
def storeTree(inputTree, filename):
    with open(filename, 'wb') as fw: #相当于 fw = open(filename, 'wb')，必须用二进制写入
        pickle.dump(inputTree, fw) # pickle序列化对象存储到文件中

"""
函数说明：读取决策树
Parameters:
    filename - 决策树的存储文件名
Returns:
    pickle.load(fr) - 决策树字典
"""
def grabTree(filename):
    fr = open(filename, 'rb') # 读取二进制文件
    return pickle.load(fr) # 返回决策树字典

"""
函数说明：测试存储和读取决策树分类器
"""
def test3():
    myTree = retrieveTree(0) # 测试预定义树结构
    print('myTree={}'.format(myTree))  # 打印决策树
#    storeTree(myTree, r'D:\dataset\inaction\Decision Tree\classifierStorage.txt') #存储决策树模型
    loadedTree = grabTree(r'D:\dataset\inaction\Decision Tree\classifierStorage.txt') # 读取存储的决策树模型
    print('读取到的决策树={}'.format(loadedTree))

#-------------------示例1：预测隐形眼镜类型-------------------
"""
函数说明：测试利用决策树进行隐形眼镜类型分类
"""
def lensesTest():
    print('----------------------示例1：预测隐形眼镜类型----------------------')
    fr = open(r'D:\dataset\inaction\Decision Tree\lenses.txt')
    lenses = [inst.strip().split('\t') for inst in fr.readlines()] #逐行读取文件并按制表符划分数据到lenses列表 24*5
#    print('lenses:\n',lenses) # [['young', 'myope', 'no', 'reduced', 'no lenses'],...,['presbyopic', 'hyper', 'yes', 'normal', 'no lenses']]
    lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate'] #第一列是年龄，第二列是症状，第三列是是否散光，第四列是眼泪数量，第五列是最终的分类标签class
    lensesTree = createTree(lenses, lensesLabels) # 生成决策树
    print('lensesTree={}'.format(lensesTree))
    createPlotTree(lensesTree) # 绘制决策树
    testVec = lenses[0][:-1] # 第一条数据作为测试数据
    result = classify(lensesTree, lensesLabels, testVec)
    print('%s属于%s' % (testVec, result)) # 打印结果
    errorCount = 0.0 # 分类错误计数
    for i in range(len(lenses)):
        classifierResult = classify(lensesTree, lensesLabels, lenses[i][:-1])
        classLabel = lenses[i][-1]
        print("分类返回结果:%s \t 真实结果:%s" % (classifierResult, classLabel))
        if classifierResult != classLabel:
            errorCount += 1.0 # 分类错误个数计数
    print("错误总数:%d\n错误率:%g%%" % (errorCount, errorCount / len(lenses)  * 100)) #打印错误个数及错误率
    
#-------------------示例2：预测西瓜数据集是否好瓜-------------------
"""
函数说明：测试利用决策树进行西瓜数据集好瓜坏瓜分类
"""
def watermelonTest():
    print('----------------------示例2：预测西瓜数据集是否好瓜----------------------')
    # 读取数据
    fr = open(r"D:\dataset\inaction\Decision Tree\watermelon2.0.txt", encoding='utf-8') # 文件中有汉字，设置utf-8编码
    watermelon = [inst.strip().split('\t') for inst in fr.readlines()]
    watermelonLabels = ['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']
    print("watermelon:\n",watermelon)
    print("watermelonLabels:\n",watermelonLabels)
    # 生成决策树
    watermelonTree = createTree(watermelon, watermelonLabels)
    print("watermelonTree = {}".format(watermelonTree))
    # 绘制决策树
    createPlotTree(watermelonTree)
    
if __name__ == '__main__':
    test0() # 测试决策树构造
    test1() # 测试决策树绘制
    test2() # 测试决策树分类
    test3() # 测试决策树存储
    lensesTest() # 测试隐形眼镜分类
    watermelonTest() # 测试西瓜数据集分类

附所有执行结果：
《Machine Learning in Action》| 第2章 决策树
参考链接
西瓜书中ID3决策树的实现

相关推荐