决策树(decision tree)——(2)生成算法

朱雀 2023-09-29 11:19 5阅读 0赞

\*\*注：本博客为李航《统计学习方法》读书笔记，虽然有一些自己的理解，但是其中仍然有大量文字摘自李老师和周老师的书籍内容。

--------------------

本章将介绍决策树学习的生成算法．首先介绍ID3的生成算法，然后再介绍C4.5中的生成算法．这些都是决策树学习的经典算法.

### **ID3算法** ###

ID3算法的核心是在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树．

具体方法是：

从根结点（root node）开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子结点;再对子结点递归地调用以上方法，构建决策树;直到所有特征的信息增益均很小或没有特征可以选择为止．最后得到一个决策树．ID3相当于用极大似然法进行概率模型的选择。

**算法(ID3算法)**

这里直接举例说明比较清楚，因为用数学来解释对数学不好的人，不太友好

**贷款申请样本数据表**

![2338c161488d405ea321c004848f6aee.png][]

例 对训练集训练，利用ID3算法建立决决策树。

利用结果，由于特征![A\_\{3\}][A_3](有自己的房子)的信息增益值最大，所以选择特征![A\_\{3\}][A_3]作为根结点的特征．它将训练数据集D划分为两个子集![D\_\{1\}][D_1]（![A\_\{3\}][A_3]取值为“是”)和![D\_\{2\}][D_2]（![A\_\{3\}][A_3]取值为“否”)．由于![D\_\{1\}][D_1]只有同一类的样本点，所以它成为一个叶结点，结点的类标记为“是”

对![D\_\{2\}][D_2],则需从特征![A\_\{1\}][A_1](年龄)，![A\_\{2\}][A_2]（有工作）和![A\_\{3\}][A_3]（信贷情况）中选择新的特征．计算各个特征的信息增益:

![1aeb66ec98c54ca38ad980259d3e0125.png][]

选择信息增益最大的特征![A\_\{2\}][A_2](有工作）作为结点的特征．由于4有两个可能取值，从这一结点引出两个子结点:一个对应“是”(有工作）的子结点，包含3个样本，它们属于同一类，所以这是一个叶结点，类标记为“是”:另一个是对应“否”(无工作）的子结点，包含6个样本，它们也属于同一类，所以这也是一个叶结点，类标记为“否”.  
这样生成一个如图所示的决策树．该决策树只用了两个特征（有两个内部结点)

![0d39bb89fb9e4407961feec1db800b21.png][]

**ID3算法只有树的生成，所以该算法生成的树容易产生过拟合.**

###  ###

### **使用python实现ID3算法：** ###

**先对数据集进行属性标注：**

*  年龄：0代表青年，1代表中年，2代表老年；
 *  有工作：0代表否，1代表是；
 *  有自己的房子：0代表否，1代表是；
 *  信贷情况：0代表一般，1代表好，2代表非常好；
 *  类别(是否给贷款)：no代表否，yes代表是。

from math import log
    import operator
    
    """
    函数说明:创建测试数据集
    年龄：0代表青年，1代表中年，2代表老年；
    有工作：0代表否，1代表是；
    有自己的房子：0代表否，1代表是；
    信贷情况：0代表一般，1代表好，2代表非常好；
    类别(是否给贷款)：no代表否，yes代表是。
    """
    
    
    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  # 返回数据集和分类属性
    
    
    """
    函数说明:计算给定数据集的经验熵(香农熵)
    Parameters:
        dataSet - 数据集
    Returns:
        shannonEnt - 经验熵(香农熵)
    """
    
    
    def calcShannonEnt(dataSet):
        numEntires = len(dataSet)  # 返回数据集的行数
        labelCounts = {}  # 保存每个标签(Label)出现次数的字典
        for featVec in dataSet:  # 对每组特征向量进行统计
            currentLabel = featVec[-1]  # 提取标签(Label)信息
            if currentLabel not in labelCounts.keys():  # 如果标签(Label)没有放入统计次数的字典,添加进去
                labelCounts[currentLabel] = 0
            labelCounts[currentLabel] += 1  # Label计数
        shannonEnt = 0.0  # 经验熵(香农熵)
        for key in labelCounts:  # 计算香农熵
            prob = float(labelCounts[key]) / numEntires  # 选择该标签(Label)的概率
            shannonEnt -= prob * log(prob, 2)  # 利用公式计算
        return shannonEnt  # 返回经验熵(香农熵)
    
    
    """
    函数说明:按照给定特征划分数据集
    Parameters:
        dataSet - 待划分的数据集
        axis - 划分数据集的特征
        value - 需要返回的特征的值
    """
    
    
    def splitDataSet(dataSet, axis, value):
        retDataSet = []  # 创建返回的数据集列表
        for featVec in dataSet:  # 遍历数据集
            if featVec[axis] == value:
                reducedFeatVec = featVec[:axis]  # 去掉axis特征
                reducedFeatVec.extend(featVec[axis + 1:])  # 将符合条件的添加到返回的数据集
                retDataSet.append(reducedFeatVec)
        return retDataSet  # 返回划分后的数据集
    
    
    """
    函数说明:选择最优特征
    Parameters:
        dataSet - 数据集
    Returns:
        bestFeature - 信息增益最大的(最优)特征的索引值
    """
    
    
    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]
            uniqueVals = set(featList)  # 创建set集合{},元素不可重复
            newEntropy = 0.0  # 经验条件熵
            for value in uniqueVals:  # 计算信息增益
                subDataSet = splitDataSet(dataSet, i, value)  # subDataSet划分后的子集
                prob = len(subDataSet) / float(len(dataSet))  # 计算子集的概率
                newEntropy += prob * calcShannonEnt(subDataSet)  # 根据公式计算经验条件熵
            infoGain = baseEntropy - newEntropy  # 信息增益
            print("第%d个特征的增益为%.3f" % (i+1, infoGain))  # 打印每个特征的信息增益
            if (infoGain > bestInfoGain):  # 计算信息增益
                bestInfoGain = infoGain  # 更新信息增益，找到最大的信息增益
                bestFeature = i  # 记录信息增益最大的特征的索引值
        return bestFeature  # 返回信息增益最大的特征的索引值
    
    
    """
    函数说明:统计classList中出现此处最多的元素(类标签)
    Parameters:
        classList - 类标签列表
    Returns:
        sortedClassCount[0][0] - 出现此处最多的元素(类标签)
    """
    
    
    def majorityCnt(classList):
        classCount = {}
        for vote in classList:  # 统计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]  # 返回classList中出现次数最多的元素
    
    
    """
    函数说明:递归构建决策树
    Parameters:
        dataSet - 训练数据集
        labels - 分类属性标签
        featLabels - 存储选择的最优特征标签
    Returns:
        myTree - 决策树
    """
    
    
    def createTree(dataSet, labels, featLabels):
        classList = [example[-1] for example in dataSet]  # 取分类标签(是否放贷:yes or no)
        if classList.count(classList[0]) == len(classList):  # 如果类别完全相同则停止继续划分
            return classList[0]
        if len(dataSet[0]) == 1:  # 遍历完所有特征时返回出现次数最多的类标签
            return majorityCnt(classList)
        bestFeat = chooseBestFeatureToSplit(dataSet)  # 选择最优特征
        bestFeatLabel = labels[bestFeat]  # 最优特征的标签
        featLabels.append(bestFeatLabel)
        myTree = {bestFeatLabel: {}}  # 根据最优特征的标签生成树
        del (labels[bestFeat])  # 删除已经使用特征标签
        featValues = [example[bestFeat] for example in dataSet]  # 得到训练集中所有最优特征的属性值
        uniqueVals = set(featValues)  # 去掉重复的属性值
        for value in uniqueVals:
            subLabels = labels[:]
            # 递归调用函数createTree(),遍历特征，创建决策树。
            myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels, featLabels)
        return myTree
    
    
    """
    函数说明:使用决策树执行分类
    Parameters:
        inputTree - 已经生成的决策树
        featLabels - 存储选择的最优特征标签
        testVec - 测试数据列表，顺序对应最优特征标签
    Returns:
        classLabel - 分类结果
    """
    
    
    def classify(inputTree, featLabels, testVec):
        firstStr = next(iter(inputTree))  # 获取决策树结点
        secondDict = inputTree[firstStr]  # 下一个字典
        featIndex = featLabels.index(firstStr)
        for key in secondDict.keys():
            if testVec[featIndex] == key:
                if type(secondDict[key]).__name__ == 'dict':
                    classLabel = classify(secondDict[key], featLabels, testVec)
                else:
                    classLabel = secondDict[key]
        return classLabel
    
    
    
    from keshihua import createPlot
    if __name__ == '__main__':
        dataSet, labels = createDataSet()
        print(f'经验熵：{calcShannonEnt(dataSet)}')
        featLabels = []
        myTree = createTree(dataSet, labels, featLabels)
        print(myTree)
        testVec = [1,0]  # 测试数据,按生成决策树特征从上往下进行
        result = classify(myTree, featLabels, testVec)
        if result == 'yes':
            print('放贷')
        if result == 'no':
            print('不放贷')
    
        # 可视化
        #mytree = {'有自己的房子': {0: {'有工作': {0: 'no', 1: 'yes'}}, 1: 'yes'}}
        #createPlot(mytree)

**代码说明：**

*  **收集数据**  
    利用 createDataSet() 函数输入数据，这里数据比较少，所以就不单独写个文件存放数据了。

*  **分析数据**  
    计算数据集的香农熵的函数，按照给定特征划分数据集，选择最好的数据集划分方式

*  **训练算法**

*  **分类**

*  **测试**

**最终生成决策树：**

![99f71406d5b74a7ab099736d7e134ebc.png][]

**可视化：**

新建一个keshihua.py文件，导入上面.py中即可。

# =====================================Matplotlib实现决策树可视化===========================================
    from matplotlib.font_manager import FontProperties
    import matplotlib.pyplot as plt
    
    
    
    # 定义文本框和箭头格式
    decisionNode = dict(boxstyle='sawtooth', fc='0.8')
    leafNode = dict(boxstyle='round4', fc='0.8')
    arrow_args = dict(arrowstyle='<-')
    # 设置中文字体
    font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)
    
    """
    函数说明:获取决策树叶子结点的数目
    Parameters:
        myTree - 决策树
    Returns:
        numLeafs - 决策树的叶子结点的数目
    """
    
    
    def getNumLeafs(myTree):
        numLeafs = 0  # 初始化叶子
        # python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性，
        # 可以使用list(myTree.keys())[0]
        firstStr = next(iter(myTree))
        secondDict = myTree[firstStr]  # 获取下一组字典
        for key in secondDict.keys():
            if type(secondDict[key]).__name__ == 'dict':  # 测试该结点是否为字典，如果不是字典，代表此结点为叶子结点
                numLeafs += getNumLeafs(secondDict[key])
            else:
                numLeafs += 1
        return numLeafs
    
    
    """
    函数说明:获取决策树的层数
    Parameters:
        myTree - 决策树
    Returns:
        maxDepth - 决策树的层数
    """
    
    
    def getTreeDepth(myTree):
        maxDepth = 0  # 初始化决策树深度
        # python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性，
        # 可以使用list(myTree.keys())[0]
        firstStr = next(iter(myTree))
        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
    
    
    
    
    
    """
    
    函数说明:绘制结点
    Parameters:
        nodeTxt - 结点名
        centerPt - 文本位置
        parentPt - 标注的箭头位置
        nodeType - 结点格式
    """
    
    
    def plotNode(nodeTxt, centerPt, parentPt, nodeType):
        arrow_args = dict(arrowstyle="<-")  # 定义箭头格式
        font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)  # 设置中文字体
        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)
    
    
    """
    函数说明:标注有向边属性值
    Parameters:
        cntrPt、parentPt - 用于计算标注位置
        txtString - 标注的内容
    """
    
    
    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)
    
    
    """
    函数说明:绘制决策树
    Parameters:
        myTree - 决策树(字典)
        parentPt - 标注的内容
        nodeTxt - 结点名
    """
    
    
    def plotTree(myTree, parentPt, nodeTxt):
        decisionNode = dict(boxstyle="sawtooth", fc="0.8")  # 设置结点格式
        leafNode = dict(boxstyle="round4", fc="0.8")  # 设置叶结点格式
        numLeafs = getNumLeafs(myTree)  # 获取决策树叶结点数目，决定了树的宽度
        depth = getTreeDepth(myTree)  # 获取决策树层数
        firstStr = next(iter(myTree))  # 下个字典
        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  # y偏移
        for key in 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 - 决策树(字典)
    """
    
    
    def createPlot(inTree):
        fig = plt.figure(1, facecolor='white')  # 创建fig
        fig.clf()  # 清空fig
        axprops = dict(xticks=[], yticks=[])
        createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)  # 去掉x、y轴
        plotTree.totalW = float(getNumLeafs(inTree))  # 获取决策树叶结点数目
        plotTree.totalD = float(getTreeDepth(inTree))  # 获取决策树层数
        plotTree.xOff = -0.5 / plotTree.totalW;
        plotTree.yOff = 1.0;  # x偏移
        plotTree(inTree, (0.5, 1.0), '')  # 绘制决策树
        plt.show()

![d594afd1b5a746e4bf0dfd5c2501dc3c.png][]

[2338c161488d405ea321c004848f6aee.png]: https://img-blog.csdnimg.cn/2338c161488d405ea321c004848f6aee.png
[A_3]: https://latex.csdn.net/eq?A_%7B3%7D
[D_1]: https://latex.csdn.net/eq?D_%7B1%7D
[D_2]: https://latex.csdn.net/eq?D_%7B2%7D
[A_1]: https://latex.csdn.net/eq?A_%7B1%7D
[A_2]: https://latex.csdn.net/eq?A_%7B2%7D
[1aeb66ec98c54ca38ad980259d3e0125.png]: https://img-blog.csdnimg.cn/1aeb66ec98c54ca38ad980259d3e0125.png
[0d39bb89fb9e4407961feec1db800b21.png]: https://img-blog.csdnimg.cn/0d39bb89fb9e4407961feec1db800b21.png
[99f71406d5b74a7ab099736d7e134ebc.png]: https://img-blog.csdnimg.cn/99f71406d5b74a7ab099736d7e134ebc.png
[d594afd1b5a746e4bf0dfd5c2501dc3c.png]: https://img-blog.csdnimg.cn/d594afd1b5a746e4bf0dfd5c2501dc3c.png