“机器学习实战”刻意练习——分类问题：决策树

Dear 丶 2023-06-12 11:20 57阅读 0赞

参考：  
[Python3《机器学习实战》学习笔记（二）：决策树基础篇之让我们从相亲说起 - Jack-Cui - CSDN博客][Python3_ - Jack-Cui - CSDN]  
[Python3《机器学习实战》学习笔记（三）：决策树实战篇之为自己配个隐形眼镜 - Jack-Cui - CSDN博客][Python3_ - Jack-Cui - CSDN 1]

# 一、概述 #

你是否玩过二十个问题的游戏，游戏的规则很简单：参与游戏的一方在脑海里想某个事物，其他参与者向他提问题，只允许提20个问题，问题的答案也只能用对或错回答。问问题的人通过推断分解，逐步缩小待猜测事物的范围。  
决策树的工作原理与20个问题类似，用户输入一系列数据，然后给出游戏的答案。

我们经常使用决策树处理分类问题，近来的调查表明决策树也是最经常使用的数据挖掘算法。它之所以如此流行，一个很重要的原因就是不需要了解机器学习的知识，就能搞明白决策树是如何工作的。

如果你以前没有接触过决策树，完全不用担心，它的概念非常简单。即使不知道它也可以通过简单的图形了解其工作原理。  
下图所示的流程图就是一个决策树：  
长方形代表**判断模块（decision block）**  
椭圆形代表**终止模块（terminating block）**，表示已经得出结论，可以终止运行。  
从判断模块引出的左右箭头称作**分支（branch）**，它可以到达另一个判断模块或者终止模块。

下图构造了一个假想的邮件分类系统，它首先检测发送邮件域名地址。  
如果地址为myEmployer.com，则将其放在分类“无聊时需要阅读的邮件”中。  
如果邮件不是来自这个域名，则检查邮件内容里是否包含单词曲棍球，如果包含则将邮件归类到“需要及时处理的朋友邮件”，如果不包含则将邮件归类到“无需阅读的垃圾邮件”。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70]  
之前的k-近邻算法可以完成很多分类任务，但是它最大的缺点就是*无法给出数据的内在含义*，决策树的主要优势就在于数据形式非常容易理解。  
决策树算法能够**读取数据集合，构建类似于上图的决策树。**

决策树的一个重要任务是为了数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，在这些机器根据数据集创建规则时，就是机器学习的过程。

优点和缺点：

*  优点：**计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据**。
 *  缺点：可能会产生**过度匹配**问题。

适用数据类型：

*  **数值型**
 *  **标称型**

决策树的一般流程：

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

# 二、代码实现（python3） #

## 1.决策树的构造 ##

在构造决策树时，我们需要解决的第一个问题就是，**当前数据集上哪个特征在划分数据分类时起决定性作用**。

为了找到决定性的特征，划分出最好的结果，我们必须评估每个特征。  
完成测试之后，原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型，则当前无需阅读的垃圾邮件已经正确地划分数据分类，无需进一步对数据集进行分割。如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。

如何划分数据子集的算法和划分原始数据集的方法相同，直到所有具有相同类型的数据均在一个数据子集内。

一些决策树算法采用二分法划分数据，《机器学习实战》并不采用这种方法。  
如果依据某个属性划分数据将会产生4个可能的值，我们将把数据划分成四块，并创建四个不同的分支。  
《机器学习实战》使用**ID3算法**划分数据集，每次划分数据集时我们只选取一个特征属性，如果训练集中存在20个特征，第一次我们选择哪个特征作为划分的参考属性呢？  
在回答这个问题之前，我们必须采用量化的方法判断如何划分数据。

### 信息增益 ###

划分数据集的大原则是：**将无序的数据变得更加有序**。  
我们可以使用多种方法划分数据集，但是每种方法都有各自的优缺点。组织杂乱无章数据的一种方法就是使用信息论度量信息。  
在划分数据集之前之后信息发生的变化称为**信息增益**，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。  
集合信息的度量方式称为**香农熵**或者简称为**熵**，这个名字来源于信息论之父克劳德·香农。

熵定义为**信息的期望值**，在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事务可能划分在多个分类之中，则**符号xi的信息**定义为  
 l ( x i ) = − l o g 2 P ( x i ) l(x\_\{i\})=-log\_\{2\}P(x\_\{i\}) l(xi)=−log2P(xi)  
其中, P ( x i ) P(x\_\{i\}) P(xi)为选择该分类的概率。

为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：  
 H = − ∑ i = 1 n P ( x i ) l o g 2 P ( x i ) H=-\\sum\_\{i=1\}^\{n\}P(x\_\{i\})log\_\{2\}P(x\_\{i\}) H=−i=1∑nP(xi)log2P(xi)  
其中，n为分类的数目。

from math import log
    
    def createDataSet():
        """ 示例DataSet - - - - """
        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): 
        """ 计算给定数据集的香农熵 - - - - dataSet - 给定数据集 """
        numEntries = len(dataSet) 
        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
            #利用log计算熵
            shannonEnt -= prob * log(prob,2) 
        return shannonEnt
    
    if __name__ == "__main__":
        myDat,labels=createDataSet()
        print(calcShannonEnt(myDat))
        #0.9709505944546686

*  熵越高，则说明**混合的数据也越多**。
 *  得到熵之后，我们就可以按照**获取最大信息增益**的方法划分数据集。
 *  **信息增益**是熵的减少或者是数据无序度的减少

另外，另一个度量集合无序程度的方法是基尼不纯度（Gini impurity），简单地说就是从一个数据集中随机选取子项，度量其被错误分类到其他分组里的概率。这里不作介绍。

### 划分数据集 ###

我们将对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。  
想象一个分布在二维空间的数据散点图，需要在数据之间划条线，将它们分成两部分。

def splitDataSet(dataSet, axis, value): 
        """ 按照给定特征划分数据集 - - - - dataSet - 待划分的数据集 axis - 划分数据集的特征 value - 特征的返回值(判断值) """
        retDataSet = []
        #遍历数据集中的每个元素，一旦发现符合要求的值，则将其添加到新创建的列表中
        for featVec in dataSet:
            if featVec[axis] == value:
                #新元素不需包含此时分类用的特征
                reducedFeatVec = featVec[:axis] 
                reducedFeatVec.extend(featVec[axis+1:]) 
                retDataSet.append(reducedFeatVec)
        return retDataSet
    
    if __name__ == "__main__":
        myDat,labels=createDataSet()
        print(splitDataSet(myDat,0,0))
        #[[1, 'no'], [1, 'no']]

接下来我们将遍历整个数据集，循环计算香农熵和splitDataSet()函数，找到最好的特征划分方式。熵计算将会告诉我们如何划分数据集是最好的数据组织方式。

def chooseBestFeatureToSplit(dataSet): 
        """ 选择最好的数据集划分方式 - - - - dataSet - 待划分的数据集 """
        numFeatures = len(dataSet[0]) - 1 
        #数据集的香农熵
        baseEntropy = calcShannonEnt(dataSet) 
        #记录信息增益和最优特征的索引值
        bestInfoGain, bestFeature = 0.0, -1 
        for i in range(numFeatures):
            #取出所有元素第i个特征的值
            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 
            if (infoGain > bestInfoGain):
                bestInfoGain = infoGain 
                bestFeature = i 
        return bestFeature
    
    if __name__ == "__main__":
        myDat,labels=createDataSet()
        print(chooseBestFeatureToSplit(myDat))
        #0

在上述chooseBestFeatureToSplit()函数中调用的dataSet需要满足一定的要求：

*  数据必须是一种由列表元素组成的列表，且所有的列表元素都要具有**相同的数据长度**；
 *  数据的最后一列或者每个实例的最后一个元素是当前实例的**类别标签**。

### 递归构建决策树 ###

由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分。第一次划分之后，数据将被向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据。  
因此我们可以采用**递归**的原则处理数据集。

递归结束的条件是：

*  程序遍历完**所有划分数据集的属性**  
    同理，可以设置算法可以划分的最大分组数目
 *  或者每个分支下的**所有实例都具有相同的分类**  
    如果所有实例具有相同的分类，则得到一个叶子节点或者终止块  
    任何到达叶子节点的数据必然属于叶子节点的分类

如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们需要决定如何定义该叶子节点，在这种情况下，我们通常会采用多数表决的方法决定该叶子节点的分类。

import operator
    
    def createTree(dataSet, labels):
        """ 创建决策树 - - - - dataSet - 数据集 labels - 标签列表 """
        classList = [example[-1] for example in dataSet]  
        #如果类别完全相同则停止继续划分
        if classList.count(classList[0]) == len(classList):            
            return classList[0]
        #遍历完所有特征时返回出现次数最多的类标签
        if len(dataSet[0]) == 1:                                    
            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:                                                           
            myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), labels.copy())
        return myTree
    
    if __name__ == "__main__":
        myDat,labels=createDataSet()
        print(createTree(myDat,labels))
        #{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

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

我们已经学习了如何从数据集中创建树，然而字典的表示形式非常不易于理解，而且直接绘制图形也比较困难。本节我们将使用Matplotlib库创建树形图。

### Matplotlib 注解 ###

Matplotlib提供了一个注解工具annotations，可以在数据图形上添加文本注释，用于解释数据的内容。  
由于数据上面直接存在文本描述非常丑陋，因此工具内嵌支持带箭头的划线工具，使得我们可以在其他恰当的地方指向数据位置，并在此处添加描述信息，解释数据内容。

绘制一棵完整的树需要一些技巧。我们虽然有x、y坐标，但是如何放置所有的树节点却是个问题。  
我们必须知道有多少个叶节点，以便可以正确确定x轴的**长度**；我们还需要知道树有多少层，以便可以正确确定y轴的**高度**。

def getNumLeafs(myTree):
        """ 获取叶节点的数目 - - - - myTree - 决策树 """
        numLeafs = 0 
        #获取结点属性
        firstStr = list(myTree.keys())[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):
        """ 获取叶节点的深度 - - - - myTree - 决策树 """
        maxDepth = 0 
        firstStr = list(myTree.keys())[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

现在我们可以将前面学到的方法组合在一起，绘制一棵完整的树。其余部分代码如下：

import matplotlib.pyplot as plt
    from matplotlib.font_manager import FontProperties
    
    def plotNode(nodeTxt, centerPt, parentPt, nodeType):
        """ 绘制结点 - - - - nodeTxt - 结点名 centerPt - 文本位置 parentPt - 标注的箭头位置 nodeType - 结点格式 """
        #定义箭头格式
        arrow_args = dict(arrowstyle="<-") 
        #设置中文字体
        font = FontProperties(fname=r'/Users/lql70/Downloads/simsun.ttc', size=16) 
        #绘制节点
        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 plotMidText(cntrPt, parentPt, txtString):
        """ 计算在父子节点间填充文本信息的位置 - - - - 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):
        """ 递归绘制决策树 - - - - myTree - 决策树 parentPt - 父节点位置 nodeTxt - 结点名 """
        #设置结点格式
        decisionNode = dict(boxstyle="sawtooth", fc="0.8")  
        #设置叶结点格式
        leafNode = dict(boxstyle="round4", fc="0.8")
        #获取决策树叶结点数目，决定了树的宽度 
        numLeafs = getNumLeafs(myTree) 
        #获取决策树层数
        depth = getTreeDepth(myTree)
    
        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] 
        #y偏移
        plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD 
        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
    
    def createPlot(inTree):
        """ 创建决策树绘制面板 - - - - inTree - 决策树 """
        #创建fig
        fig = plt.figure(1, facecolor='white') 
        #清空fig
        fig.clf() 
        axprops = dict(xticks=[], yticks=[])
        #去掉x、y轴
        createPlot.ax1 = plt.subplot(111, frameon=False, **axprops) 
        #获取决策树叶结点数目
        plotTree.totalW = float(getNumLeafs(inTree))  
        #获取决策树层数
        plotTree.totalD = float(getTreeDepth(inTree)) 
        #x、y偏移 
        plotTree.xOff = -0.5/plotTree.totalW
        plotTree.yOff = 1.0
        #调用 plotTree()绘制决策树
        plotTree(inTree, (0.5,1.0), '')
        plt.show()
    
    
    if __name__ == "__main__":
        myDat,labels=createDataSet()
        myTree=createTree(myDat,labels)
        print(myTree)
        createPlot(myTree)

绘制结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70 1]

# 3.测试和存储分类器 #

依靠训练数据构造了决策树之后，我们可以将它用于实际数据的分类。

## (1)测试算法：使用决策树执行分类 ##

在执行数据分类时，需要**决策树**以及用于**构造树的标签向量**。  
然后，程序比较测试数据与决策树上的数值，递归执行该过程直到进入叶子节点；最后将测试数据定义为叶子节点所属的类型。

在存储带有特征的数据会面临一个问题：  
程序无法确定特征在数据集中的位置，例如前面例子的第一个用于划分数据集的特征是nosurfacing属性，但是在实际数据集中该属性存储在哪个位置？是第一个属性还是第二个属性？  
**特征标签列表**将帮助程序处理这个问题。  
使用index方法查找当前列表中第一个匹配firstStr变量的元素 。然后代码递归遍历整棵树，比较testVec变量中的值与树节点的值，如果到达叶子节点，则返回当前节点的分类标签。

def classify(inputTree, featLabels, testVec):
        """ 决策树的分类函数 - - - - inputTree - 已经生成的决策树 featLabels - 存储选择的最优特征标签 testVec - 测试数据列表，顺序对应最优特征标签 """
        firstStr = list(inputTree.keys())[0]
        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
    
    if __name__ == "__main__":
        myDat,labels=createDataSet()
        #因为createTree()会删除labels中标签，所以需要先对其创建副本
        labels2=labels.copy()
        myTree=createTree(myDat,labels)
        #print(myTree)
        #createPlot(myTree)
        classify(myTree,labels2,[1,1])

## （2）使用算法：决策树的存储 ##

造决策树是很耗时的任务，即使处理很小的数据集，如前面的样本数据，也要花费几秒的时间，如果数据集很大，将会耗费很多计算时间。然而用创建好的决策树解决分类问题，则可以很快完成。

因此，为了节省计算时间，最好能够在每次执行分类时调用已经构造好的决策树。

为了解决这个问题，需要使用**Python模块pickle序列化对象**，序列化对象可以在磁盘上保存对象，并在需要的时候读取出来。  
任何对象都可以执行序列化操作，字典对象也不例外。

import pickle
    def storeTree(inputTree, filename):
        """ 存储决策树 - - - - inputTree - 已经生成的决策树 filename - 决策树的存储文件名 """
        with open(filename, 'wb') as fw:
            pickle.dump(inputTree, fw)
    
    if __name__ == "__main__":
        myDat,labels=createDataSet()
        #因为createTree()会删除labels中标签，所以需要先对其创建副本
        labels2=labels.copy()
        myTree=createTree(myDat,labels)
        storeTree(myTree, 'classifierStorage.txt')
        #print(myTree)
        #createPlot(myTree)
        #classify(myTree,labels2,[1,1])

在该Python文件的相同目录下，会生成一个名为classifierStorage.txt的txt文件，这个文件**二进制存储**（意思是它存了但你估计看不懂） 着决策树。

# 三、决策树实战：预测隐形眼镜类型 #

本节我们将通过一个例子讲解决策树如何预测患者需要佩戴的隐形眼镜类型。

使用小数据集，我们就可以利用决策树学到很多知识：  
眼科医生是如何判断患者需要佩戴的镜片类型；  
一旦理解了决策树的工作原理，我们甚至也可以帮助人们判断需要佩戴的镜片类型。

**隐形眼镜数据集**包含很多患者眼部状况的观察条件以及医生推荐的隐形眼镜类型。隐形眼镜类型包括硬材质、软材质以及不适合佩戴隐形眼镜。  
一共有24组数据，数据的Labels依次是age、prescript、astigmatic、tearRate、class，也就是第一列是年龄，第二列是症状，第三列是是否散光，第四列是眼泪数量，第五列是最终的分类标签。

## 使用决策树预测隐形眼镜类型过程 ##

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

## 代码 ##

if __name__ == "__main__":
        fr=open('2-DecisionTree/lenses.txt')
        lenses=[line.strip().split('\t') for line in fr.readlines()]
        lensesLabals=['age','prescript','astigmatic','tearRate']
        lensesTree=createTree(lenses,lensesLabals)
        print(lensesTree)
        createPlot(lensesTree)

运行结果：

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

图示如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70 2]

# 四、总结 #

决策树分类器就像*带有终止块的流程图*，终止块表示分类结果。

开始处理数据集时，我们首先需要测量集合中数据的不一致性，也就是**熵**，然后寻找最优方案划分数据集，直到数据集中的所有数据属于同一分类。

ID3算法可以用于**划分标称型数据集**。

构建决策树时，我们通常采用**递归**的方法将数据集转化为决策树。

一般我们并不构造新的数据结构，而是使用Python语言内嵌的数据结构**字典存储树节点信息**。

使用**Matplotlib的注解功能**，我们可以将存储的树结构转化为容易理解的图形。

Python语言的**pickle模块**可用于存储决策树的结构。

隐形眼镜的例子表明决策树可能会产生过多的数据集划分，从而产生过度匹配数据集的问题。我们可以通过**裁剪决策树**，合并相邻的无法产生大量信息增益的叶节点，消除过度匹配问题。

还有其他的决策树的构造算法，最流行的是**C4.5**和**CART**，之后讨论回归问题时将介绍CART算法。

再贴一下来自 Jack-Cui 总结的决策树的优缺点（链接在前面）

> 决策树的一些优点：
> 
>  *  易于理解和解释，决策树可以可视化。
>  *  几乎不需要数据预处理。其他方法经常需要数据标准化，创建虚拟变量和删除缺失值。决策树还不支持缺失值。
>  *  使用树的花费（例如预测数据）是训练数据点(data points)数量的对数。
>  *  可以同时处理数值变量和分类变量。其他方法大都适用于分析一种变量的集合。
>  *  可以处理多值输出变量问题。
>  *  使用白盒模型。如果一个情况被观察到，使用逻辑判断容易表示这种规则。相反，如果是黑盒模型（例如人工神经网络），结果会非常难解释。即使对真实模型来说，假设无效的情况下，也可以较好的适用。
> 
> 决策树的一些缺点：
> 
>  *  决策树学习可能创建一个过于复杂的树，并不能很好的预测数据。也就是过拟合。修剪机制（现在不支持），设置一个叶子节点需要的最小样本数量，或者数的最大深度，可以避免过拟合。
>  *  决策树可能是不稳定的，因为即使非常小的变异，可能会产生一颗完全不同的树。这个问题通过decision trees with an ensemble来缓解。
>  *  学习一颗最优的决策树是一个NP-完全问题under several aspects of optimality and even for simple  
>     concepts。因此，传统决策树算法基于启发式算法，例如贪婪算法，即每个节点创建最优决策。这些算法不能产生一个全家最优的决策树。对样本和特征随机抽样可以降低整体效果偏差。
>  *  概念难以学习，因为决策树没有很好的解释他们，例如，XOR, parity or multiplexer problems.
>  *  如果某些分类占优势，决策树将会创建一棵有偏差的树。因此，建议在训练之前，先抽样使样本均衡。

[Python3_ - Jack-Cui - CSDN]: https://blog.csdn.net/c406495762/article/details/75663451
[Python3_ - Jack-Cui - CSDN 1]: https://blog.csdn.net/c406495762/article/details/76262487
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191112183117614.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191113221720217.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191114165854950.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmFzaGlfRg==,size_16,color_FFFFFF,t_70