机器学习实战（六）决策树（上）

谁借莪１个温暖的怀抱￠ 2021-11-22 08:18 583阅读 0赞

### 文章目录 ###

*   *  一、从分类问题开始
     *  二、决策树模型
     *  三、信息论基础
     *  四、决策树建立
     *  五、ID3算法
     *  六、C4.5算法

**前言：**  
**决策树（Decision Tree）是一种基本的分类与回归方法，本文主要讨论分类决策树。** 决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。相比朴素贝叶斯分类，决策树的优势在于构造过程不需要任何领域知识或参数设置，因此在实际应用中，对于探测式的知识发现，决策树更加适用。

## 一、从分类问题开始 ##

**分类（Classification）任务就是确定对象属于哪个预定义的目标类。** 分类问题不仅是一个普遍存在的问题，而且是其他更加复杂的决策问题的基础，更是机器学习和数据挖掘技术中最庞大的一类算法家族。我们前面介绍过的很多算法（例如SVM，朴素贝叶斯等）都可以用来解决分类问题。作为本文的开始，我们首先来简单回顾一下什么是分类。

假设我们现在有如下表所示的一个属性集（feature set），它收集了几个病患的症状和对应的病症。症状包括头疼的程度、咳嗽的程度、体温以及咽喉是否肿痛，这些症状（feature）的组合就对应一个病症的分类（Cold 还是 Flu）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70]  
分类问题的本质就是当给定这样一个数据集后，要求我们训练出（或建立）一个模型ff。当出现一组新的特征向量时，要求我们预测（或判断）拥有这样一组特征向量的对象应当属于哪个类别。就我们现在给出的例子而言，假设你是一名医生，现在收治了一位新的病患，然后你通过问诊得知他的一些症状（包括头疼的程度、咳嗽的程度、体温以及咽喉是否肿痛），然后你就要根据你已经建立好的模型来判断该病人得的到底是Cold（普通感冒）还是Flu（流行性感冒）。

分类问题的类别数目可以是两类也可以是多类。二分类问题是最简单的分类问题，而多分类问题模型可以在二分类模型的基础上进行构建。我们在前面文章中一直使用的鸢尾花数据集就是一个典型的多分类问题，问题的最终目标是判断给定一朵花，它应该属于setosa、versicolor和virginica中的哪一类。

## 二、决策树模型 ##

**1.概念**  
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部节点和叶节点，内部节点表示一个特征或属性，叶节点表示一个类。  
分类的时候，从根节点开始，对实例的某一个特征进行测试，根据测试结果，将实例分配到其子结点；此时，每一个子结点对应着该特征的一个取值。如此递归向下移动，直至达到叶结点，最后将实例分配到叶结点的类中。

**2.举一个通俗的栗子**  
决策树可以理解成是很多if−then的规则组合.由决策树的根结点到叶结点的每一条路径构建一条规则；路径上的内部结点的特征对应着规则的条件，而叶结点对应着分类的结论。决策树的路径和其对应的if-then规则集合是等效的，它们具有一个重要的性质：互斥并且完备。这里的意思是说：每一个实例都被一条路径或一条规则所覆盖，而且只被一条规则所覆盖。  
**下图就是一棵典型的决策树:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 1]  
这棵决策树根据天气情况分类“星期六上午是否适合打网球”,根节点到叶节点的每一条路径构成了一条规则,路径上的内部节点对应规则的条件,叶节点的类对应着规则的结论.

规则1:如果晴天,湿度很高就不去打网球
    规则2:如果晴天,湿度一般就去打网球
    规则3:如果是阴天,就去打网球
    规则4:如果是雨天,而且大风,就不去打网球
    规则5:如果是雨天,但是微风,就去打网球

## 三、信息论基础 ##

如果我们根据这些条件逐步去构建决策树的话,如何选择每个节点呢? 比如我们的根节点是选年龄好还是选工作好? 不同的算法选择的标准不一样.在了解这些算法之前,请先阅读信息论基础这篇文章,确保理解了里面介绍到的概念.  
链接：[http://leijun00.github.io/2014/07/information-theory/][http_leijun00.github.io_2014_07_information-theory]

## 四、决策树建立 ##

**1.特征选择**  
选择一个合适的特征作为判断节点，可以快速的分类，减少决策树的深度。决策树的目标就是 **把数据集按对应的类标签进行分类。** 最理想的情况是，通过特征的选择能把不同类别的数据集贴上对应类标签。特征选择的目标 **使得分类后的数据集比较纯。** 如何衡量一个数据集纯度，这里就需要引入数据纯度函数。下面将介绍**两种表示数据纯度的函数。**

**2.信息增益**

信息熵表示的是不确定度，也就是不纯度。均匀分布时，不确定度最大，此时熵就最大。当选择某个特征对数据集进行分类时，分类后的数据集信息熵会比分类前的小，其差值表示为信息增益。信息增益可以衡量某个特征对分类结果的影响大小。

根据**信息增益(Information gain)** 来选取Feature作为决策树分裂的节点.特征A对训练数据集D的信息增益定义为集合D的经验熵(所谓经验熵,指的是熵是有某个数据集合估计得到的) **H(D)** 与特征A给定条件下D的经验条件熵 **H(D∣A)** 之差,记为 **g(D,A).**  
![在这里插入图片描述][20190725084614644.png]  
![在这里插入图片描述][20190725084632155.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 2]  
**3.基尼指数**  
基尼指数. 假设一共有K个类,样本属于第k类的概率是pk,则概率分布的基尼指数定义为:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 4]

## 五、ID3算法 ##

决策树学习的生成算法之一：ID3

**1.概念**  
ID3算法由Ross Quinlan发明，建立在“奥卡姆剃刀”的基础上：越是小型的决策树越优于大的决策树（be simple简单理论）。**ID3算法中根据信息增益评估和选择特征**，每次选择**信息增益**最大的特征作为判断模块建立子结点。  
**2.描述**

*  ID3算法可用于划分标称型数据集
 *  没有剪枝的过程为了去除过度数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点（例如设置信息增益阀值）。
 *  使用信息增益的话其实是有一个缺点，那就是它偏向于具有大量值的属性。就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性，而这样做有时候是没有意义的
 *  另外ID3不能处理连续分布的数据特征
 *  于是就有了C4.5算法。CART算法也支持连续分布的数据特征。  
    3.算法步骤如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 5]  
    **4.python代码实现：**

def chooseBestFeatureToSplitByID3(dataSet):
        '''
                选择最好的数据集划分方式
        :param dataSet:数据集
        :return: 划分结果
        '''
        numFeatures = len(dataSet[0]) - 1  # 最后一列yes分类标签，不属于特征向量
        baseEntropy = calcShannonEnt(dataSet)
        bestInfoGain = 0.0
        bestFeature = -1
        for i in range(numFeatures):  # 遍历所有特征
            infoGain = calcInformationGain(dataSet, baseEntropy, i)     # 计算信息增益
            if (infoGain > bestInfoGain):  # 选择最大的信息增益
                bestInfoGain = infoGain
                bestFeature = i
        return bestFeature  # 返回最优特征对应的维度
    
    def majorityCnt(classList):
        '''
        采用多数表决的方法决定叶结点的分类
        :param: 所有的类标签列表
        :return: 出现次数最多的类
        '''
        classCount={}
        for vote in classList:                  # 统计所有类标签的频数
            if vote not in classCount.keys():
                classCount[vote] = 0
            classCount[vote] += 1
        sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True) # 排序
        return sortedClassCount[0][0]
    
    def createTree(dataSet,labels):
        '''
        创建决策树
        :param: dataSet:训练数据集
        :return: 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 = chooseBestFeatureToSplitByID3(dataSet)   # 最优划分特征
        bestFeatLabel = labels[bestFeat]
        myTree = {bestFeatLabel:{}}         # 使用字典类型储存树的信息
        del(labels[bestFeat])
        featValues = [example[bestFeat] for example in dataSet]
        uniqueVals = set(featValues)
        for value in uniqueVals:
            subLabels = labels[:]       # 复制所有类标签，保证每次递归调用时不改变原始列表的内容
            myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
        return myTree

**5.ID3的详解**  
博主本人推荐可以看一下博客：  
[https://blog.csdn.net/zhihua\_oba/article/details/70340235][https_blog.csdn.net_zhihua_oba_article_details_70340235]

## 六、C4.5算法 ##

决策树学习的生成算法之二：C4.5  
**1.简介**  
C4.5继承了ID3算法的优点。并在以下几方面对ID3算法进行了改进：

*  克服了用信息增益选择属性时偏向选择取值多的属性的不足；
 *  在树构造过程中进行剪枝；
 *  能够完成对连续属性的离散化处理；
 *  能够对不完整数据进行处理。

**2. 分裂属性的选择——信息增益比**  
![在这里插入图片描述][20190725090550759.png]  
**3.描述**

*  C4.5算法产生的分类规则易于理解、准确率较高；
 *  但效率低，因树构造过程中，需要对数据集进行多次的顺序扫描和排序。
 *  因为必须多次数据集扫描，C4.5只适合于能够驻留于内存的数据集。
 *  在实现过程中，C4.5算法在结构与递归上与ID3完全相同，区别只在于选取决决策特征时的决策依据不同，二者都有**贪心**性质：即通过局部最优构造全局最优。
 *  注：贪心算法，感兴趣的可以了解一下 [https://www.jianshu.com/p/b613ae9d77ff][https_www.jianshu.com_p_b613ae9d77ff]

**4.算法步骤**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 6]  
**5.Python代码实现**

def chooseBestFeatureToSplitByC45(dataSet):
        '''
                选择最好的数据集划分方式
        :param dataSet:
        :return: 划分结果
        '''
        numFeatures = len(dataSet[0]) - 1  # 最后一列yes分类标签，不属于特征变量
        baseEntropy = calcShannonEnt(dataSet)
        bestInfoGainRate = 0.0
        bestFeature = -1
        for i in range(numFeatures):  # 遍历所有维度特征
            infoGainRate = calcInformationGainRatio(dataSet, baseEntropy, i)    # 计算信息增益比 
            if (infoGainRate > bestInfoGainRate):  # 选择最大的信息增益比
                bestInfoGainRate = infoGainRate
                bestFeature = i
        return bestFeature  # 返回最佳特征对应的维度

**6.C4.5详解**  
博主本人推荐，可以参考下博客：  
[https://blog.csdn.net/zhihua\_oba/article/details/70632622][https_blog.csdn.net_zhihua_oba_article_details_70632622]

**注：下一篇博客决策树（二）将会继续讲述使用CART算法生成决策树以及决策树的剪枝处理。** [https://blog.csdn.net/qs17809259715/article/details/97236114][https_blog.csdn.net_qs17809259715_article_details_97236114]

博客内容，仅是博主一人理解整理所得，如有错误，不足之处，欢迎指正，定会细心更改！

参考文档：

\[1\]《统计学习方法》李航著

\[2\]《机器学习实战》Peter Harrington著

\[3\] [https://blog.csdn.net/HerosOfEarth/article/details/52347820][https_blog.csdn.net_HerosOfEarth_article_details_52347820]

\[4\] [https://blog.csdn.net/hu948162999/article/details/73124135][https_blog.csdn.net_hu948162999_article_details_73124135]

\[5\] [https://blog.csdn.net/baimafujinji/article/details/51724371][https_blog.csdn.net_baimafujinji_article_details_51724371]

\[6\] [http://leijun00.github.io/2014/09/decision-tree/][http_leijun00.github.io_2014_09_decision-tree]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70]: /images/20211122/a8f357d2d75b4b059460fb61c3cd3c38.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 1]: /images/20211122/7c991f52140e4cf2819663ef4468a6cd.png
[http_leijun00.github.io_2014_07_information-theory]: http://leijun00.github.io/2014/07/information-theory/
[20190725084614644.png]: /images/20211122/939fc7d13cb348618a51b70d4f825343.png
[20190725084632155.png]: /images/20211122/75a1c1b9930f456eb7b8211c15759a27.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 2]: /images/20211122/0b82b5b87bd841d6ac5eb74701f771cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 3]: /images/20211122/2c697bae1e5140c4a434861608ab30b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 4]: /images/20211122/65d83adeff164dbd8898f58343a7f892.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 5]: /images/20211122/b91e2cb7720d4c6b978f57c9c2977ef0.png
[https_blog.csdn.net_zhihua_oba_article_details_70340235]: https://blog.csdn.net/zhihua_oba/article/details/70340235
[20190725090550759.png]: /images/20211122/34879075f09a4cfebd3270550b44c518.png
[https_www.jianshu.com_p_b613ae9d77ff]: https://www.jianshu.com/p/b613ae9d77ff
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 6]: /images/20211122/d9d67936b30244a68f2354d061f524de.png
[https_blog.csdn.net_zhihua_oba_article_details_70632622]: https://blog.csdn.net/zhihua_oba/article/details/70632622
[https_blog.csdn.net_qs17809259715_article_details_97236114]: https://blog.csdn.net/qs17809259715/article/details/97236114
[https_blog.csdn.net_HerosOfEarth_article_details_52347820]: https://blog.csdn.net/HerosOfEarth/article/details/52347820
[https_blog.csdn.net_hu948162999_article_details_73124135]: https://blog.csdn.net/hu948162999/article/details/73124135
[https_blog.csdn.net_baimafujinji_article_details_51724371]: https://blog.csdn.net/baimafujinji/article/details/51724371
[http_leijun00.github.io_2014_09_decision-tree]: http://leijun00.github.io/2014/09/decision-tree/