机器学习算法学习02：决策树的学习以及应用决策树解决Cora数据集论文分类问题

1.前言

决策树方法作为非常经典的机器学习方法，曾经一度是作为专家推荐系统的研究方向。在数十年前，那时的部分人工智能学家相信，通过将生活中的事情逐一用逻辑表示，再通过决策树对这些逻辑的回答进行逐一选择，最终可以使得机器分辨所有物体。即使到了现在，决策树系统逐渐退出人工智能应用领域的今天，他的思想还仍然在生活中被应用着。学习并掌握决策树算法对我们来说依旧十分重要。本次实验代码已发布在GITHUB上，需要的可以上GIT自取：liujiawen-jpg/Decision-Tree: Machine Learn 02 (github.com)

2.算法分析

2.1算法概述

决策树算法其实用逻辑可以非常简单的解释，就是我们将生活中的问题转化为一个个逻辑问题，我们用下面这张图来进行解释：

如上图，我们想要决定今天到底要不要出去外面玩。那么有时候外面天气可能下雨刮风 或者说非常炎热，我们可能只想窝在家里打游戏，决策树模拟了我们这种决策树过程。我们以最左边的叶子节点来叙述。首先我们要查看外面的天气景色（outlook）属性，发现是晴天，接下来我们判断湿度是否大于七十，如果大于，很可惜又热又湿的天气并不适合我出去玩，只能在家里玩游戏了。但是如果小于七十，那么今天是一个不可多得的好天气，我们应该出去玩。

通过上面这个案例，我们得知了决策树算法的大致流程，是不是觉得他看起来并不是很难。好像过于抽象到连数学公式都很难描述他😂😂😂。但这里其实有一个很重要的因素，那么就是为什么outLook（这里我们称之为决策属性）的决策优先级要排在humidity（湿度）,windy（刮风的）之前。在这个简单的例子之前我们还能判断他的优先级，但是进入一些足够复杂，决策属性足够多的问题时，我们是否还能主观判断谁应该作为优先级，所以选择决策属性的优先级也变得极为重要（如何判断优先级，我们留到后面再说）。那么到这里决策树的算法步骤相信大家就看得出来了：

1. 选择数据集中各个决策属性的优先级

2. 通过各个决策属性各个优先级，训练集的数据和标签用于生成决策树（这里可以认为是在训练步骤）

3. 将测试集输入决策树，通过各个决策树的属性比较，最终由遍历到的叶子节点的标签作为测试结果的标签

2.2 算法优化

看似上面的步骤，已经十分完美了，但这里还需要注意一个问题，如果最终测试数据遍历下去找到的叶子节点为空怎么办（即没有对应的叶子节点）。为什么会出现这样的结果呢？这是很正常的，首先我们需要知道，我们决策树全部都是基于我们的训练数据来生成的，我们仍然用上面的决策树进行举例：

如果我们的训练集中没有出现Humidity(湿度)<=70的时候，即生成的决策树中不存在最左边的叶子节点的时候，但我们测试的时候遇到了这种结果我们应该如何解决？我们的算法应该返回什么结果 ，总不能返回对不起无查询结果而返回吧。这个时候前人提出了一个改进方法，当查询到的叶子节点为空时。算法统计该空节点的兄弟节点中出现最多的类别作为我们返回的类别。

比如上图这种出现情况最左边的叶子节点为空的时候，我们统计他的兄弟节点发现只有一个节点他的类别是不出去玩，那么我们就放心地选择不出去玩算了（虽然你发现这样的结果和真实相悖，但没办法训练集如果没有办法包括所有情况的话，我们只能使用类似投票表决的方法来决定了）。那么改良后的步骤就调整为这样：

1. 选择数据集中各个决策属性的优先级
2. 通过各个决策属性各个优先级，训练集的数据和标签用于生成决策树（这里可以认为是在训练步骤）
3. 将测试集输入决策树，通过各个决策树的属性比较，最终由遍历到的叶子节点的标签作为测试数据的结果，如果遍历到的叶子节点为空，则统计该空节点的兄弟节点中出现次数最多的标签，作为测试数据的输出结果。

那么到这里算法陈述完了，接下来我们需要使用代码对于上述算法的实现。

3.算法代码

3.1 决策属性优先级选择

在之前，我们说过一个数据拥有非常多的属性，选择各个属性在决策树节点中的优先级变得尤为重要，但是到底用什么标准去划分，用什么公式去划分显得尤为重要，这里我使用了三种方法用于进行数据集的划分：

3.1.1 信息熵

信息熵是由信息论之父香农提出的，他认为数据的混乱程度是可以进行量化的，于是提出了信息熵的概念，对于数据U我们对的信息熵定义如下：
$H(U)=E\left[-\log p_i\right]=-{\sum }_{i=1}^n{p}_i\log p_i$

这里做出解释，n为数据中的类别，$p_i$为i类别出现的概率，$log{p}_i$为以2为底数$p_i$为真值的结果，对每个类我们计算这两种结果，并将求他们的乘积之和作为该数据集的信息熵，信息熵代表数据集的混乱程度。下面我们编写代码来将该公式来实现：

#计算信息熵
def calcShannonEnt(dataSet, method = 'none'):
    numEntries = len(dataSet)
    labelCount = 
    for feature in dataSet:
        if method =='prob': #统计信息增益率时使用
            label =  feature
        else:
            label = feature[-1] #输入信息默认最后一维为标签
        if label not in labelCount.keys():
            labelCount[label]=1
        else:
            labelCount[label]+=1
    shannonEnt = 0.0
    for key in labelCount:
        numLabels = labelCount[key]
        prob = numLabels/numEntries
        shannonEnt -= prob*(log(prob,2))
    return shannonEnt

通过上述代码，我们便可以将一个数据集的信息熵计算出来，那么回到我们原来的问题上，我们如何通过计算信息熵来确定决策属性的优先级呢？这里我们还需要一个信息增益增益：
$$\mathrm{Gain}(D,a)=\mathrm{Ent}(D)-\sum _{v=1}^V\frac{\left|D^v\right|}{|D|}\mathrm{Ent}\left(D^v\right)$$
也就是对每个可以用来决策的属性，我们都用它划分数据集后并计算划分后的信息熵，然后用总的数据集的信息熵减去该信息熵，这我们称之为该属性的信息增益。可以发现当该属性划分后的数据集的混乱程度越低（也就是说使用他划分后效果好），信息熵越低，则它所带来的的信息增益也会越大。所以我们遍历所有决策属性计算他们的信息增益，选取信息增益的大小作为我们划分数据属性的优先级：

#使用决策属性划分数据集，会将数据集axis维度的值等于value的值的数据集切出来
def splitDataSet(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

#选择最佳划分数据集的属性
def chooseBestFeatureToSplit(dataSet):
    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 #计算每个信息值的信息增益
        if(infoGain > bestInfoGain): #信息增益最大的作为
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature #返回信息增益的最佳索引

3.2.2 信息增益率

但是信息增益其实是有偏向性的，他十分偏向于拥有更多选择的决策属性（如果我们将数据编号拿来也作为决策属性毫无疑问他将作为第一优先级的决策属性）这也导致了部分情况下决策树正确率受到了影响，那么学者又提出了一个新的数据划分方法–信息增益率（Gain ratio）。也就是是在原有信息增益的情况下我们多考虑一个对于属性内部也计算一次信息熵：
$$\mathrm{Gain}\mathrm{ratio}(D,a)=\frac{\mathrm{Gain}(D,a)}{\mathrm{IV}(a)}$$

$$\mathrm{I}\mathrm{V}(a)=-\sum _{v=1}^V\frac{\left|D^v\right|}{|D|}{\log }_2\frac{\left|D^v\right|}{|D|}$$

也就是说，我们也需要对内部再次进行一次划分并用类似信息熵的方式来求IV(a)：

def calcShannonEnt(dataSet, method = 'none'):
    numEntries = len(dataSet)
    labelCount = 
    for feature in dataSet:
        if method =='prob': #当参数为prob时转而计算信息增益率
            label =  feature
        else:
            label = feature[-1]
        if label not in labelCount.keys():
            labelCount[label]=1
        else:
            labelCount[label]+=1
    shannonEnt = 0.0
    for key in labelCount:
        numLabels = labelCount[key]
        prob = numLabels/numEntries
        shannonEnt -= prob*(log(prob,2))
    return shannonEnt

def chooseBestFeatureToSplit3(dataSet): #使用信息增益率进行划分数据集
    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]
        newEntropyProb = calcShannonEnt(featList, method='prob') #计算内部信息增益率
        uniqueVals = set(featList)
        newEntropy = 0.0
        for value in uniqueVals:
            # 通过不同的特征值划分数据子集
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob *calcGini(subDataSet)
        newEntropy  = newEntropy/newEntropyProb
        infoGain = baseEntropy - newEntropy #计算每个信息值的信息增益
        if(infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature #返回信息增益的最佳索引

3.3.3 基尼系数

基尼系数，相信大家并不陌生，各个新闻中也经常出现。它经常被用于衡量国家的贫富差距，在CART决策树中，作者采用他来作为决策属性划分的依据。在这里就让我们揭开他的神秘面纱，一起来看看他具体是如何计算的，对于数据集D我们定义基尼系数如下：
$$\begin{array}{rl}\mathrm{Gini}(D)& =\sum _{k=1}^{|\mathcal{Y}|}\sum _{k^{\prime }\ne k}{p}_k{p}_{k^{\prime }}\\ & =1-\sum _{k=1}^{|\mathcal{Y}|}{p}_k^2\end{array}$$
$查看详情$

机器学习---算法---决策树

.../blog.csdn.net/qq_43208303/article/details/84837412 决策树是一种机器学习的方法。决策树的生成算法有ID3,C4.5和CART等。决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶... 查看详情

机器学习算法之决策树

一.简介　　决策树的一个重要任务是理解数据中蕴含的知识信息。    决策树优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。    缺点：可能产生过... 查看详情

机器学习——决策树（上）原理

Decisiontree决策树是机器学习中一种基本的分类和回归算法，是依托于策略抉择而建立起来的树。其主要优点是模型具有可读性，分类速度快，易于理解。决策树的思想主要来源于Quinlan在1986年提出的ID3算法和1993年提出... 查看详情

机器学习决策树

1、决策树简介1.1决策树概述决策树算法是一种基于树形结构的分类算法，它能从给定的无序的训练样本中，提炼出树型的分类模型，树形中包含判断模块和终止模块。它是一种典型的分类算法，首先对数据进行处理，利用归纳... 查看详情

机器学习不同决策树的节点分裂准则

决策树是一个非常常见并且优秀的机器学习算法，它易于理解、可解释性强，其可作为分类算法，也可用于回归模型。本文将分三篇介绍决策树，根据不同分裂准则分为不同决策树，包括ID3、C4.5、CART。不同决... 查看详情

机器学习决策树理论第二卷

决策树内容来至于《统计学习与方法》李航,《机器学习》周志华,以及《机器学习实战》PeterHarringTon,相互学习,不足之处请大家多多指教！本卷的大纲为1CART算法1.1CART回归树1.2CART分类树2CART剪枝3总结1CART算法CART分类与回归树(classi... 查看详情

机器学习之路--决策树(代码片段)

...使用不熟悉的数据集合，并从中提取一系列规则，在这些机器根据数据集创建规则是，就是机器学习的过程。二，相关知识1决 查看详情

机器学习入门之决策树算法

1、什么是决策树（DecisionTree）       决策树是一个类似于流程图的树结构，其中每一个树节点表示一个属性上的测试，每一个分支代表一个属性的输出，每一个树叶节点代表一个类或者类的分布，树的... 查看详情

《机器学习实战》-决策树(代码片段)

目录决策树决策树简介决策树的构造信息增益划分数据集递归构建决策树在Python中使用Matplotlib注解绘制树形图Matplotlib注解构造注解树测试和存储分类器测试算法：使用决策树执行分类使用算法：决策树的存储示例：使用决策树... 查看详情

机器学习算法整理决策树

决策树的训练与测试如何切分特征（选择节点）衡量标准-熵 信息增益决策树构造实例信息增益：表示特征X使得类Y的不确定性减小的程度。（分类后的专一性，希望分类后的结果是同类在一起）Outlook=sunny时，熵值=(-2/5)*log(2/... 查看详情

机器学习算法：决策树算法简介以及分类原理(代码片段)

学习目标知道什么是决策树知道如何求解信息熵知道信息增益的求解过程知道信息增益率的求解过程知道基尼系数的求解过程知道信息增益、信息增益率和基尼系数三者之间的区别、联系决策树思想的来源非常朴素，程序设... 查看详情

机器学习-决策树(decisiontree)算法

学习彭亮《深度学习基础介绍：机器学习》课程[toc]决策树概念决策树是一种用于监督学习的层次模型，由此，局部区域通过少数几步递归分裂决定。决策树是一个类似流程图的树结构：其中每个结点表示在一个... 查看详情

机器学习实战精读--------决策树

感觉自己像个学走路的孩子，每一步都很吃力和认真！机器根据数据集创建规则，就是机器学习。决策树：从数据集合中提取一系列规则，适用于探索式的知识发现。决策树本质：通过一系列规则对数据进行分类的过程。决策树... 查看详情

机器学习算法

分类算法： 决策树：    对每一节点，根据feature进行分类。选择信息增益最大的feature，也就是选择将不确定性降低最多的feature。随机森林：多个决策树的投票机制来改善决策树，假设有m棵决策树，要有m个一... 查看详情

鹅厂优文|决策树及id3算法学习

...决策树是一种用树形结构来辅助行为研究、决策分析以及机器学习的方式，是机器学习中的一种基本的分类方法。决策树(DecisionTree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概... 查看详情

机器学习基于决策树的隐性眼镜选择(代码片段)

实验介绍1.实验内容本实验学习并实现决策树算法。2.实验目标通过本实验掌握决策树算法的基本原理。3.实验知识点香农熵信息增益4.实验环境python3.6.55.预备知识Python编程基础准备工作  点击屏幕右上方的下载实验数据模块&#x... 查看详情

实验四决策树算法及应用(代码片段)

博客班级机器学习作业要求实验四作业目标决策树算法及应用学号3180701124一、【实验目的】理解决策树算法原理，掌握决策树算法框架；理解决策树学习算法的特征选择、树的生成和树的剪枝；能根据不同的数据类型，选择不... 查看详情