西瓜书重温(四): 决策树手推版_飞道的博客

西瓜书重温(四): 决策树手推版

2021-05-20 17:53 451人阅读评论(0)

1. 写在前面

今天复习的决策树模型，对应的是西瓜书的第四章内容，关于决策树模型，重要性不言而喻了，这个是后面集成学习模型的基础，集成学习里面不管是bagging家族里面的代表随机森林，还是boosting家族里面AdaBoost派系或者是GBDT->xgboost-lightgbm-catboost派系，他们的基模型往往都是用的决策树(CART树)，当然不是说其他的基模型不能用，但决策树来做集成真的是优势多多，所以从这里就能看出决策树模型的重要地位了，如果决策树的底层不是很了解，那么学习后面的那些经典集成方法就会特别的吃力。所以这是基础，而上面那些模型在面试里面也是非常喜欢问的知识，而问着问着，就可能不小心就会扯到最底层的决策树上面来，比如决策树是咋生成的？决策树分裂的时候有哪些准则？以这些准则代表的决策树生成算法有啥？决策树的剪枝怎么剪得？决策树是如何处理连续值的？决策树是如何处理缺失值的？这些问题，还都是比较普通的，在这个"内卷"的时代，这里还可以加一些难度，那就是写一下信息增益，信息增益比和基尼系数的公式，再加点难度，就是用python用ID3算法实现一棵决策树吧，写写大体的代码框架(这个是在实习面经上看到的，没看错，实习面经上)。

上面这些内容其实就是这篇文章的主要内容了，其实这次读西瓜书发现，上面这些内容，都是西瓜书里面黑纸白字写好的(代码题也是课后习题)，所以还是好好读书吧哈哈，对于算法工程师来讲，我觉得真没有捷径，多读书，多思考和总结才是王道。好吧，跑偏了，下面说一下我这篇文章要整理的内容了，首先，由于之前在白话系列整理过决策树白话机器学习算法理论+实战之决策树，所以那里有的，这里肯定不会再整理一遍。由于那里整理的时候是基于的统计学习方法看的，而这里重温西瓜书我觉得正好互为补充下，这篇文章是基于西瓜书上的内容进行展开，每一次重温会有不同的收获，所以首先，先从熵和信息的关系开始介绍，这样可以弄清楚啥子叫熵，而信息又对熵起到了什么作用，这样才好理解后面决策树的信息熵，信息增益啥的，否则，依然是知其然的状态，并没有知所以然(熵为啥是个那样的计算公式？），然后就是正式介绍决策树了，大理论由于上面那篇文章都总结完了，这里会少写一些，重点包括树的生成，树的剪枝已经后面的连续和缺失值的处理，当然在树生成部分，会手推一下熵的最大最小值的证明(从数学的角度感受下熵最大和最小对应的概率是啥样子)，补充CART回归，也会手算西瓜书上的几个例子加深印象等。这次大部分公式要动手写写了，这些可是真会考的东西呀。

这篇文章还是很长的，也无法一下子全概括出来，这次重温借助了很多资料，我也会一一放到链接下面，感兴趣的可以去看看。还是各取所需即可哈哈。

大纲如下：

熵和信息到底是咋回事？(熵，信息量的度量)
决策树的基本流程
决策树的划分选择(信息增益，信息增益比，基尼系数，ID3， C4.5, CART)
决策树的剪枝(预剪枝和后剪枝)
决策树连续值和缺失值的处理(连续值和缺失值)
多变量决策树(简单一提)
小总

Ok, let’s go!

2. 信息与信息熵

这里我们先了解下西瓜书里面提到的一个玄乎概念"信息熵"，原话是度量样本集合纯度最常用的一种指标。但如果只是这么理解，总感觉心理不太踏实，所以又找了一些资料看了下，先补充这一块的相关知识，可不仅仅是上面一句话这么简单哟！

2.1 什么是信息？什么又叫做熵？

首先，先看看什么叫做熵？因为信息和熵是相对的概念。

熵和信息数量相等，意义相反，获取信息意味着消除不确定性(熵)。

当一件事情(宏观态)有多种可能的情况(微观态)时，这件事情(宏观态)对某人(观察者)而言，具体是哪种情况(微观态)的不确定性叫做熵(Entropy), 通俗的可能会听到这样的解释，熵表示的是事件的混乱程度，信息论中，熵定义为信息的期望值(后面看公式就会更加明白)。

宏观态，指的是某个事件，不考虑内部细节的状态
微观态，指各种具体的可能，考虑具体细节的状态

这里拿第三篇链接的例子看下:

我们知道，面临多种可能性，我们对哪种情况是无法确定的，但是如果我们获得了某些信息之后呢？我们就会排除掉一些可能性，就会慢慢的得到正确的可能，所以信息就很好理解了。

能够消除该人对这件事情(宏观态)不确定的事物叫做信息。而不能够消除某人对某件事情不确定性的事物叫做噪音，噪音是干扰某人获得信息的事物。

数据是噪音与信息的混合，需要用知识将其分离

信息的性质：

同一个观察者对同一件事物接收到的信息与用于传递信息的信号形式无关 — 媒介无关
信息描述一个观察者确定一个宏观态是哪个微观态时需要的物理量，所以信息是相对的。接收到的信息是相对于观察者已经对该事件的实际了解程度。 — 相对个体
信息是客观的物理量，不随观察者的主观意识改变 — 客观存在，物理量
信息是相对于某件事情而言的，比如小明对正确答案是ABCD哪个的熵，和小明对于正确答案属于AB还是CD的熵是不一样的 — 相对具体事件

好吧，上面的这些确实会偏理论化，不利于直接学习，下面举个例子把上面串起来就行了，其实没有那么复杂:

我们做一道选择题的时候，对于正确答案ABCD哪个选项的不确定性就叫做熵。假设正确答案是C。

熵在ABCD这四种可能都是1/4的时候最大(最混乱)，而在确定C为正确答案时100%的时候最小。

而从一开始的ABCD最混乱的状态，到最终确定下正确答案C的过程中，也就是熵最大->熵最小的这个过程中，我们是需要各种信息来消除不确定性的，也就是获得了很多的信息量。

信息量在这个过程中扮演的角色:

调整概率，比如小红告诉小明一半的可能选C，那么小明对于C选项的确定性调整成了50%，那么小红给小明点播的这句话，就是信息

排除干扰，比如小红告诉小明D选项是错误的，那么小明就就可以排除D，然后把其他三项的概率进行调整33.3%，这句话也同样是信息

直接确定某件事情的实际情况，比如小红告诉小明答案是C，小明就把C调整到了100%。

但如果小红告诉小明，一定是ABCD里面的某一项，这时候并没有帮助小明消除对答案的不确定性，此时并不是说小红提供了假信息(并不是假的呀)，而是提供了一种噪声，即非信息。

再看下信息的性质理解:

比如小红告诉小明答案是C，与小红通过纸条方式，与小红拍两下桌子等告诉小明答案是C，这个过程中提供的信息是一样的。 — 媒介无关

小红会这道题，所以不管告不告诉小红答案是C，小红对这道题的熵都是0，观察者已经有对这件事情的所有信息，不确定性从最初就不存在。 — 相对个体

比如小明对正确答案是ABCD哪个的信息，和小明对于正确答案属于AB还是CD的信息是不一样的，这是两种事件 — 相对事件

最后，再看看两组对比关系。

概率 VS 熵

概率是某件事情(宏观态)某个可能情况(微观态)的确定性，比如ABCD的答案开始的时候都是1/4
熵是某人对某件事情(宏观态)到底是哪个情况(微观态)的不确定性

细品一下，这里说的不是一回事呀压根。

熵 VS 方差

对数据进行压缩时，要求方差最大化，目的是保留数据的更多信息。根据信息论， "信息熵"用来量化信息，从这个角度来看，方差和信息熵都可以用于量化信息
在统计学或者金融学，方差用来随机变量的波动情况或者不确定性，但此时的波动情况是与随机变量的取值有明确关系的，也就是随机变量的取值是有含义的才行，即方差于随机变量的取值有关。
而信息论中，熵也是表示信息的不确定度，但熵只依赖于随机变量的分布(至于概率有关)，而与随机变量的取值无关，所以相比于方差，信息熵更适合描述信息的不确定度。

2.2 信息是如何量化的呢？

上面如何定性的判断什么是信息，什么是熵？那么，信息是如何量化的？信息的单位是啥？下面从类比的角度来理解，信息熵也类似于一种物理量，如果这个不知道，热力熵听过没？类比呀！

类比质量(信息也是物理量)，质量是怎么量化的呢？一开始是定义个参照物，把这个参照物的质量定义为1千克，然后再测量其他物体的质量时，就看看待测物体相当于多少个参照物的质量，那么这里的多少个，就是待测物体的质量了
同样的，信息是消除事件的不确定性，那么我们就选择一个事件的不确定性(信息)作为参照事件。当想要测量其他事件的信息时(不确定性)，就看看待测事件的不确定性相当于"多少个"参照事件的不确定性。这里的多少个，便是信息量了。 当选择的参照事件是像抛硬币这样，只有两种等概率的情况事件的时候，测量的信息量的单位是bit(两种可能嘛,1bit就能表示出来)。

但是测量信息量和测量质量不太一样的一个地方，就是这里多少个的衡量，在测量质量的时候，我们用待测物体的质量除以参照物的质量，就会得到多少个。而测量信息量的时候，这里不能用除，因为抛掷3个硬币产生等可能的结果是 $2^3=8$ 种，而不是6种。所以这里是指数关系，那么当知道可能情况个数为 $m$ ，想求这些情况相当于多少个参照事件 $n$ 产生的时候，就用对数 $log_2m$ ，即有8个不确定情况的事件相当于3个硬币抛出的结果，即所含有的信息量是3bit。小明对于答案是ABCD是哪一项不确定性的所含的信息量是 $log_24=2$ bit。但这里的前提，这些不确定情况必须是等可能的，因为参照事件里面的两种情况就是等概率。

但是，如果面临事件里面的不确定性情况不是等概率的时候怎么办呢？比如小红告诉小明一半可能性选C了，那么相当于C概率是 $\frac{1}{2}$ ，其他A,B,C的概率是 $\frac{1}{6}$ ，那么这时候应该怎么计算信息量呢？

分别测量待测事件每种可能情况的信息量之后，乘以它们各自发生的概率求和(期望值)。所以上面这个例子的信息量就下面这个方式计算：
$\frac{1}{6}log_2{I_A}+\frac{1}{6}log_2{I_B}+\frac{1}{2}log_2{I_C}+\frac{1}{6}log_2{I_D}$

怎么知道概率为 $1 / 6$ 的情况的不确定性相当于抛掷多少个硬币所产生的不确定性呢？这里的 $m$ 是未知的，But, 概率的倒数等于等概率情况的个数。用概率的倒数替换等概率情况的个数 $m$ 之后，就能计算每种情况的信息量了。所以信息量
$\frac{1}{6}log_2{6}+\frac{1}{6}log_2{6}+\frac{1}{2}log_2{2}+\frac{1}{6}log_2{6}$
如果不太理解，可以这么想，先把这一个事件看成有6种等概率的情况，那么这个事件所含的信息量就是 $log_26$ bit，而其中每个情况的信息量是 $\frac{1}{6}log_26$ bit。但是这里的C有点特殊的是，它这种情况自己就占了其中的3个情况，这就相当于对于C这种情况来讲，如果想区分开的话，其实用不了 $log_26$ bit, 而是仅仅用 $log_22$ bit就能分开，因为这时候，其实相当于这个事件分成了两种等概率的情况，一种是是C占 $\frac{1}{2}$ ，一种是不是C占 $\frac{1}{2}$ 。所以C这里所含的信息量是 $\frac{1}{2}log_22$ 。

这个就是计算熵的公式了。什么？没看出来？
$-(\frac{1}{6}log_2\frac{1}{6}+\frac{1}{6}log_2\frac{1}{6}+\frac{1}{2}log_2\frac{1}{2}+\frac{1}{6}log_2\frac{1}{6})$

原来西瓜书上的熵计算公式是这么来的呀！
$Ent(D)=-\sum_{k=1}^{\mathcal{Y}}p_klog_2p_k$

好了，基础补充了之后，看下西瓜书正文了。

3. 决策树的基本流程

这里的基本流程指的是建树的基本流程哈，并且说的是用决策树进行分类任务，首先对于决策树，得知道是包含一个根节点、若干个内部节点和若干个叶子节点。

叶子节点对应于决策结果，其他节点对应属性测试
每个节点包含的样本集合根据属性测试的结果划分到子节点
根节点包含样本全集
从根节点到每个叶子节点的路径对应了一个判定测试序列

决策树的目的是为了产生一棵泛化能力强，处理未见示例能力强的决策树。那么怎么产生呢？西瓜书上给了一个递归的算法流程，这个是需要理解的？之前其实并没有好好注意这些细节，比如决策树啥时候结束呢，也就是啥时候不能划分了呢？不能划分了之后怎么确定具体类别呢？这个在算法图上一目了然, 完全符合递归的四要素。

这里说了无需划分的三种哦情况：

当前节点全部属于同一个类别了，说明这个叶子节点上直接不确定性为0了呀，找到答案了
当前属性集为空，或者是所有样本所有属性上取值相同: 属性集为空意味着没法划分，而属性上取值相同同样意味着没法划分了，这时候把类别定位所含样本最多的类
当前节点包含的样本集为空，这个的意思是属性集也有，但是没有样本集了，这个是有可能出现的，没法继续划分了，这时候类别定义为父节点所含样本最多的类。 这个在之前读的时候并没有发现这个细节，样本集都是空了，还要他干嘛？但不要忘了，我们这里是在训练集上训练的决策树，样本集是空，可能说明当前情况训练集没有符合的样本，可并不是代表测试集里面也没有这种情况的样本呀！

并且，还要注意，第二种和第三种情况，虽然都是无法划分，可处理的实质是不一样的，第二种情况是有样本没属性了，这时候利用的是当前节点样本里面的后验分布 $P (l a b e l ∣ s a m p l e)$ 。而第三种情况，是有属性，没有样本了，这时候只能看他爹里面的样本了，并不是划分到该节点下样本的信息得出来的，这属于利用他爹里面样本的先验分布 $P (s a m p l e ∣ l a b e l)$ ，可以体会下不同。

4. 决策树的划分选择

划分选择这里是非常重要的一块内容了，解决的是决策树在节点分裂的时候，是如何选择的最优划分属性问题。我们希望，随着划分过程不断进行，决策树的分支节点所包含的样本可能属于同一类别，即节点的"纯度"越来越高。

之所以前面对信息和熵进行解释和铺垫，就是希望这个地方，我们能有个更好的理解，也就是能自动的对比。构建决策树的过程其实非常类似于上面我们做选择题的过程(只不过这里换成了机器)。我们可以先回忆下上面我们做选择题的过程，然后一类比，瞬间就能理解决策树到底在干嘛了。

我们拿到一道选择题，有ABCD四个选项，如果不看题，我们会一脸懵逼，啊这，四个都有可能，且等概率呀，此时正是最混乱的时候，也就是熵最大的时候。

接下来，我们开始读题，这是我们获取信息的过程，通过读题，我们根据一些条件，比如条件1(这里脑回路了，想不出具体问题了), 我们心里立即就圈出这个条件，立即排除B，D，肯定从A，C里面选择。这时候，我们通过这个圈里面的条件，使得之前的信息熵2bit(4种等概率可能)，降到了1bit(两种等概率可能)，我们就可以断定条件1带来的信息量是1bit(借助这个信息，帮助我们排除了两种可能)，接下来，又读题，看到了条件2，大喊一声"都选C"，这时候我们的熵变成了0，确定了答案。

其实我们发现了吗? 其实决策树的生成过程，和我们做题的情景非常像，也是一个从熵最大，然后决策树不断的获取信息，使得熵慢慢减小得到决定结果的过程。

一开始，我们拿到了训练集，面临的样本各种类型的都有，熵最大，而这里的条件就好比样本的特征，根据这些条件带来的信息量，我们能够慢慢的使得样本进行合理划分，从而使得划分之后的小样本集合的熵慢慢减小，越来越容易确定是哪种可能(如果运气好的话，划分出的节点里面所有样本只有一个答案，那直接确定了)。而条件的选择应该怎么选呢？贪心的讲，如果哪个条件能给我带来的信息量最大，能够让熵减少的最快，我就选哪个了，而这，其实就是信息增益。

和上面不同的地方，就是我们这里面临的情况，并不是等概率发生的，所以计算熵的时候，得每种可能的信息量取对数然后乘以发生的概率求和的方式，也就是用熵的那个公式了。下面再看西瓜书就非常舒服了，当然在舒服之前，还得证明一个事情，就是:

$E n t (D)$ 的最小值是0，最大值是 $\log _{2}|\mathcal{Y}|, \mathcal{Y}$ 类别总数 — 西瓜书75页

这个其实通过上面已经定性的了解了，最小的时候，就是确定了最后的答案了，那所需的信息量就是0了，不混乱，而最大的时候，就是面临等概率的那多种可能的时候，这时候信息量的衡量，相当于抛 $\log _{2}|\mathcal{Y}|$ 枚硬币才能定出来。当然，这么说可能不够严谨，我们就用严谨的数学语言证明一下子吧。

主要是参考的《机器学习公式详解》，最大值：

从上面也可以看出来，当存在多种情况，且这些情况出现的可能性都一样的时候，此时熵会得到最大值 $log_2n$ , 最混乱的情况，下面看看熵最小的时候:

综上可知，但 $f(x_1, x_2, ...x_n)$ 取到最大值的时候， $x_1=x_2=...=x_n=\frac{1}{n}$ ，此时样本集合的纯度最低(最混乱), 而当 $f(x_1, x_2, ...x_n)$ 取到最小值的时候， $x_k=1, x_1=x_2=...x_{k-1}=x_{k+1}=.....=x_n=0$ ，此时样本集合纯度最高(确定了某一种情况了)。

4.1 信息增益

信息增益是决策树划分属性选择的指标之一，衡量的某个特征(条件)所能带来的信息量的多少。

我们知道，拿过一个数据集的时候，会有各个类别的样本进行混杂，此时应该是样本集合纯度最小的时候(最混乱)，即熵最大。而根据样本特征带来的信息量，我们能够对样本进行合理的划分，使得小样本集合的熵变小。信息增益描述的其实就是每个特征带来的信息量的多少，信息增益越大，说明某个特征带来的信息量越大，而我们选择最优划分属性的时候，就是选择信息增益大的特征。那么如何计算信息增益呢？

如果理解了上面的整个过程，就比较简单了，既然信息增益表示的是某个特征带来的信息量，那么我们先计算出原始样本的信息量，然后基于某个特征划分开样本，再计算划分后的样本的信息量，两者相减，不就是该特征能够带来的信息量了？就是这么玩的。但这里要注意下，就是基于某个特征划分开样本，这里的某个特征是会有不同的取值的，所以这里划分样本，是基于这不同的取值划分的样本，那么划分完之后，计算信息量，就得需要不同特征值下分别计算信息量，然后再加权求和，这里的权重其实就是某个特征值出现的概率( $\frac{\#_{某个特征值下的样本个数}}{\#_{总样本个数}}$ ）。

这就是西瓜书上信息增益的相关描述了， 信息增益越大，意味着属性 $a$ 划分所得的"纯度提升"越大，所以可使用信息增益来进行决策树的划分属性选择，而对应的决策树学习算法，就是著名的ID3算法了。

信息论中，信息增益也称为互信息，表示已知一个随机变量的信息后另一个随机变量的不确定性减少的程度。

西瓜书上给了一个基于西瓜数据集2.0进行属性选择的例子，首先是基于数据集先计算原始数据的熵，然后再计算基于各个特征划分后数据的熵，得到每个特征带来的信息增益，找到最大信息增益的那个进行划分。本来开始的时候，想再手算一遍来，但后来觉得这些原理懂了之后，再手算还是那些东西，所以这里换了种方式，我们用代码来手撸一下，正好和西瓜书上互补起来，这样应该比手算一遍来的更深刻一些，并且代码这块面试还真有考的哟。感兴趣的也可以自己玩一下，挺有意思的哈哈。

首先，给出数据集：

	# dataset 西瓜数据集2.0
    dataset = [
        ['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
        ['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'],
        ['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
        ['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '是'],
        ['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '是'],
        ['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '是'],
        ['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '是'],
        ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '是'],
        ['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '否'],
        ['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '否'],
        ['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '否'],
        ['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '否'],
        ['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '否'],
        ['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '否'],
        ['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '否'],
        ['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '否'],
        ['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '否'],
    ]

基于这个数据集，我们先来看看如何计算熵，思路就是先统计各个类别下的样本个数(字典)，接下来就是求每一类类别的概率，然后就是用上面的公式计算即可，也就是概率log概率，取负号，再累加，代码如下：

# 计算给定数据集的熵
def calcEnt(dataset):
    smaple_nums = len(dataset)

    # 统计不同类别的样本数量，这里用一个字典
    label_cou = defaultdict(int)

    for sample in dataset:
        cur_label = sample[-1]
        label_cou[cur_label] += 1

    Ent = 0.0
    for key in label_cou:
        prob = float(label_cou[key]) / smaple_nums
        Ent -= prob * log(prob, 2)

    return Ent

这样，给定数据集之后，就能算出当前数据集的熵来。

# 计算原来数据集的熵
sample_num = len(dataset)
base_ent = calcEnt(dataset)
print(base_ent)              # 0.9975025463691153   书上保留了3位

接下来，计算基于每个特征划分之后的样本的熵。这里需要两步

首先，先基于某个特征下的某个特征值，得到对应的样本子集
思路，遍历样本，如果特征值等于当前特征值，则进行保存，当然保存的时候，要避开当前特征了。

# 按照给定的特征值划分数据集
def splitDataset(dataset, fea_index, fea_val):
    """
    :param dataset: 数据集
    :param fea_index: 特征下标
    :param fea_val: 特征下的某个特征值
    :return: 基于该特征值得到样本子集
    """
    retDataSet = []
    for sample in dataset:
        if sample[fea_index] == fea_val:
            reducedSample = sample[:fea_index]
            reducedSample.extend(sample[fea_index+1:])
            retDataSet.append(reducedSample)

    return retDataSet

计算每个特征划分之后的信息熵
思路，遍历每个特征，每个特征下遍历每个特征值，得到对应的样本子集，这样就能计算每个特征各个特征值下的样本子集的信息熵，然后再乘以特征值出现的概率进行累加，就得到了当前特征下的信息熵(条件熵)

ef cal_feat_ent(dataset, feat_name, sample_num):

    index_feaname_map = {
     index: fea for index, fea in enumerate(feat_name)}
    feature_ent = defaultdict(int)

    feature_nums = len(dataset[0]) - 1
    # 遍历每个特征
    for i in range(feature_nums):
        # 每个特征下获取特征取值情况
        feature_list = set([sample[i] for sample in dataset])

        feat_ent = 0.0
        # 遍历当前特征下的所有取值情况，来计算当前特征下的熵值
        for fea_val in feature_list:
            subDataset = splitDataset(dataset, i, fea_val)
            prob = len(subDataset) / float(sample_num)
            feat_ent += prob * calcEnt(subDataset)

        feature_ent[index_feaname_map[i]] = feat_ent
    return feature_ent

我们基于这个函数，看看当前各个属性划分下的样本的信息熵：

# 计算当前数据集各个特征分割下的样本信息熵
feat_ent = cal_feat_ent(dataset, feat_name, sample_num)
print(feat_ent)

# 结果如下:
defaultdict(<class 'int'>, {
   '色泽': 0.88937738110375, '根蒂': 0.8548275868023224, '敲声': 0.8567211127541194, '纹理': 0.6169106490008467, '脐部': 0.7083437635274363, '触感': 0.9914560571925497})

计算各个特征的信息增益，也就是原始信息熵减去特征划分下的信息熵：

# 每个特征的信息增益
feat_info_gain = {
   }
for key in feat_ent:
    feat_info_gain[key] = base_ent - feat_ent[key]

print(feat_info_gain)

# 结果如下:
{
   '色泽': 0.10812516526536531, '根蒂': 0.14267495956679288, '敲声': 0.14078143361499584, '纹理': 0.3805918973682686, '脐部': 0.28915878284167895, '触感': 0.006046489176565584}

# 纹理的信息增益最大， 先拿这个节点进行划分

上面发现，和西瓜书上的计算是一样的。我们先选择纹理这个特征进行划分。

这时候，可以看到样本的信息熵从0.99多变到了0.72，这个就是纹理这个特征带来的信息量的作用。接下来就是递归的过程了，还记得上面的伪代码吗？接下来的步骤，就是递归生成决策树。第一个纹理特征用完了，在各个叶子节点上，基于其他的特征再进行划分即可。这里用代码来看是这样：

def createTree(dataset, feat_name, depth):

    # 获得所有样本的标签
    classList = [sample[-1] for sample in dataset]

    # 递归结束条件
    # 1. 类别完全相同， 则停止
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 2. 特征已经遍历完毕， 返回样本中类别数最多的
    if len(dataset[0]) == 1:
        return majorityClass(classList)

    # 开始划分
    bestFeat_index = choose_best_split(dataset, feat_name)
    bestFeat = feat_name[bestFeat_index]
    print("第{}轮， 选择特征 {}".format(depth, bestFeat))
    myTree = {
   bestFeat:{
   }}
    del feat_name[bestFeat_index]

    cur_feat_val = set([sample[bestFeat_index] for sample in dataset])
    for val in cur_feat_val:
        sub_feat_name = feat_name[:]
        myTree[bestFeat][val] = createTree(splitDataset(dataset, bestFeat_index, val), sub_feat_name, depth+1)

    return myTree

这里有两个函数， choose_best_split就是选择最优特征进行划分，就是在这里面，会先计算原始样本的信息熵，然后计算当前数据集下各个特征分割下样本的信息熵，求各个特征的信息增益，选择信息增益最大的特征索引返回即可。代码如下:

def choose_best_split(dataset, feat_name):

    # 计算原来数据集的熵
    sample_num = len(dataset)
    base_ent = calcEnt(dataset)
    print(base_ent)


    # 计算当前数据集各个特征分割下的样本信息熵
    feat_ent = cal_feat_ent(dataset, feat_name, sample_num)
    #print(feat_ent)

    # 每个特征的信息增益
    feat_info_gain = {
   }
    for key in feat_ent:
        feat_info_gain[key] = base_ent - feat_ent[key]

    print(feat_info_gain)

    # 选择最好的划分方式
    maxInfoGain = 0.0
    best_fea = None
    best_loc = 0
    for i, key in enumerate(feat_info_gain.keys()):
        if feat_info_gain[key] > maxInfoGain:
            maxInfoGain = feat_info_gain[key]
            best_fea = key
            best_loc = i

    return best_loc

还有个函数叫做majorityClass，这个函数的作用是如果所有特征都遍历完毕之后，也就是没有特征能划分样本了，那么就选取当前样本中类别最多的那个作为当前节点的类别。

def majorityClass(classList):
    class_cou = defaultdict(int)
    for cla in classList:
        class_cou[cla] += 1

    return sorted(class_cou.items(), key=lambda x: x[1], reverse=True)[0][0]

这样，决策树就建完了，看下最终的结果：

tree = createTree(dataset, feat_name, 1)

# 结果如下：
{
   '纹理': {
   '模糊': '否', '稍糊': {
   '触感': {
   '软粘': '是', '硬滑': '否'}}, '清晰': {
   '根蒂': {
   '硬挺': '否', '蜷缩': '是', '稍蜷': {
   '色泽': {
   '乌黑': {
   '触感': {
   '软粘': '否', '硬滑': '是'}}, '青绿': '是'}}}}}}

这棵树对应的就是西瓜书78页基于信息增益生成的决策树，这个也是著名的ID3算法的实现过程简化版，不过真实的ID3算法应该更加全面，具体代码我没看。

那么，怎么用这课决策树执行分类呢？这个依然是一个递归的过程：

def classify(inputTree, feat_name, testVec):

    # 当前分裂点
    first_fea = list(inputTree.keys())[0]
    # 分裂点的各个取值
    secondDict = inputTree[first_fea]
    feat_index = feat_name.index(first_fea)

    # 下面遍历接下来的一层下面的各个特征节点
    for key in secondDict.keys():
        if testVec[feat_index] == key:
            # 如果当前是个字典，那么还是一棵树，递归，否则，返回label即可
            if type(secondDict[key]).__name__ == 'dict':
                classLabel = classify(secondDict[key], feat_name, testVec)
            else:
                classLabel = secondDict[key]

    return classLabel

test_sample = ['青绿', '蜷缩', '沉闷', '稍糊', '凹陷', '硬滑']
label = classify(tree, feat_name_copy, test_sample)
print(label)    # 否

下面我们看看信息增益存在的问题，做个实验，就是把编号作为第一列也加入到数据集中，这时候建立的树是下面这样：

这棵树显然是没有泛化能力的，也就是信息增益对可取值个数较多的特征有偏好。好多文章也是点到这里为止了，但仿佛这句话读起来成了信息增益的问题了，但这个结论其实是不太准确的。举个例子吧:

假设有数据集 $D$ , 12个样本，6个正样本，6个负样本。再假设有基于特征a, 特征b两种划分

特征 $a$ : 两个取值，所以把数据集 $D$ 划分成了两个分支 $D_1$ 和 $D_2$

$D_1$ : 4个正例， 2个负例，此时的熵为 $Ent(D_1)=-(\frac{2}{3}log_2\frac{2}{3}+\frac{1}{3}log_2\frac{1}{3})$

$D_2$ : 2个正例， 4个负例，此时的熵为 $Ent(D_2)=-(\frac{1}{3}log_2\frac{1}{3}+\frac{2}{3}log_2\frac{2}{3})$

那么，基于特征 $a$ 划分之后，数据的条件熵 $\frac{1}{2}Ent(D_1)+\frac{1}{2}Ent(D_2)$

特征 $b$ : 四个取值，所以把数据集 $D$ 划分成了四个分支 $D_1$ , $D_2$ , $D_3$ , $D_4$

$D_1$ : 2个正例， 1个负例，此时的熵为 $Ent(D_1)=-(\frac{2}{3}log_2\frac{2}{3}+\frac{1}{3}log_2\frac{1}{3})$

$D_2$ : 2个正例， 1个负例，此时的熵为 $Ent(D_2)=-(\frac{2}{3}log_2\frac{2}{3}+\frac{1}{3}log_2\frac{1}{3})$

$D_3$ : 1个正例， 2个负例，此时的熵为 $Ent(D_3)=-(\frac{1}{3}log_2\frac{1}{3}+\frac{2}{3}log_2\frac{2}{3})$

$D_4$ : 1个正例， 2个负例，此时的熵为 $Ent(D_4)=-(\frac{1}{3}log_2\frac{1}{3}+\frac{2}{3}log_2\frac{2}{3})$

那么，基于特征 $b$ 划分之后，数据的条件熵 $\frac{1}{4}Ent(D_1)+\frac{1}{4}Ent(D_2)+\frac{1}{4}Ent(D_3)+\frac{1}{4}Ent(D_4)$ ，而显然，这个式子是和 $a$ 按个条件熵是相等的。

此时，信息增益的话并不是只偏向于分支多的特征 $b$ 吧，而是可能随机选择一个, 所以上面那个结论有些小问题的其实。那么信息增益真正的问题是啥呢？

上面那个例子，从直觉上，用特征 $a$ 对数据集划分得到的结果与用特征 $b$ 对数据集进行划分得到的结果是差不多的。但从机器学习的角度来看，此时特征 $a$ 的划分可能更好。原因是 $b$ 迅速地将样本空间划分的过小了，从而增加了过拟合的风险。

例如，我们要估计落入每个节点的正样本的真实比例（真实分布，非数据经验分布），此时我们可以用训练时数据在节点上的分布来作估计值。用特征 $a$ 的划分，在 $D_1$ 上它的估计值是 $2 / 3$ ；用特征 $b$ 的划分，在 $D_1$ 上它的估计值也是 $2 / 3$ 。但区别在于特征 $a$ 的划分用了 $6$ 个样本在估计，而特征 $b$ 的划分只用了 $3$ 个样本。所以用特征 $a$ 的划分进行估计时可能更加准确。

所以，当面临差不多的两种划分时，我们应该避免选择划分分支更多的那一个，因为它会将空间划分的更小，从而会导致其中统计量的可靠性变差(可能过拟合)。而信息增益在面临这样的选择时，不会偏向任意一方，而是随机选，这才是信息增益的问题

所以， C4.5的信息增益率的设计动机其实是来源于此，著名的C4.5决策树算法在选择特征的时候，不是用信息增益取衡量特征的好坏，而是用了信息增益率，这样既考虑了特征的各个取值下子样本集合的混乱程度尽量小，又控制了划分的分支还不要过多，或者如果两个特征带来的信息量差多的时候，依然会选择分支小的特征进行分裂。

下面就看C4.5是如何做到的。

4.2 信息增益率

信息增益比在信息增益的基础上，对每个特征的分支也进行了一定的惩罚，分支不能够过多，那么怎么才能做到这一点的， 分支精简些，也就是不混乱就行了呀，所以这里又在分支的层面上计算了下混乱程度，这个其实就比较好理解了，直接西瓜书的公式：
$\operatorname{Gain}_{\operatorname{ratio}}(D, a)=\frac{\operatorname{Gain}(D, a)}{\operatorname{IV}(a)}$

和信息增益的唯一不同，就是分母的这个东西，就是对分支数进行的限制，计算的是分支的混乱程度，也是一个信息熵：
$\mathrm{IV}(a)=-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \log _{2} \frac{\left|D^{v}\right|}{|D|}$
这个应该比较简单了，而换成代码的层面，计算特征信息增益的函数里面要同时计算出当前特征的分支信息熵，这样在后面计算特征信息增益的时候，在基础上除以分支信息熵IV即可

信息增益比通过增加一个分支层面的混乱情况解决了信息增益的那个问题，让指标倾向于划分结果少的特征，上面的那个例子，如果用信息增益比的话，特征 $a$ 的分支混乱情况是 $-(\frac{1}{2}log_2\frac{1}{2}+\frac{1}{2}log_2\frac{1}{2})$ ，而特征 $b$ 的分支混乱情况是 $-(\frac{1}{4}log_2\frac{1}{4}+\frac{1}{4}log_2\frac{1}{4}+\frac{1}{4}log_2\frac{1}{4}+\frac{1}{4}log_2\frac{1}{4})$ , 后者的分母要大，信息增益率会小。

所以4.5与ID3的最大区别在于，ID3仅仅追求每次节点划分能够带来最大的“收益”，而C4.5算法强调的是在保证足够收益的情况下，寻求最大“收益代价比”

但注意，信息增益率准则对分支少的特征又有偏好了，所以C4.5算法并不是直接选择信息增益率最大的候选划分属性，而是用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

所以，这里要注意到， C4.5在评估节点划分的优劣时，会同时使用信息增益和信息增益率，可不是只使用信息增益率呀，小细节要牢记，这个细节之前我也是忽略的，所以每次重温，都有新收获 😉

4.3 基尼系数

基尼系数也是衡量给定数据集的纯度指标，即这东西也是反映了样本的混乱程度，基尼系数越小，说明样本集合不确定程度低，反之，则越混乱，和熵是相似的。那么既然与熵类似，为啥还要有这个东西呢？那是因为，不管是上面的信息增益还是信息增益率的计算，都存在着大量的对数运算，而使用基尼系数表示信息纯度，在保留信息熵特性的同时可以简化模型的计算。 CART决策树就是使用"基尼系数"来选择划分属性的。

先来看看数据集的基尼系数如何计算：
$\operatorname{Gini}(D)=\sum_{k=1}^{|\mathcal{Y}|} p_{k}\left(1-p_{k}\right)=1-\sum_{k=1}^{|\mathcal{Y}|} p_{k}^{2}$
直观来看， $G i n i (D)$ 反映了从数据 $D$ 中随机抽取两个样本，其类别标记不一致的概率。而极端情况，假设某一类样本的概率为1，其他为0，说明情况非常确定，那么此时基尼系数为0，而如果每种可能的概率一样，那么此时后面那个平方求和项非常小，基尼系数接近1. 所以基尼系数越小，表示数据集的纯度越高。

如果特征 $a$ 有 $V$ 个取值，那么经特征 $a$ 划分之后的基尼系数和条件熵那个是类似的:
$a)=\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Gini}\left(D^{v}\right)$
在候选属性集合A中，选择使得划分后基尼系数最小的属性作为最优划分属性
$a_{*}=\underset{a \in A}{\arg \min }{ Gini}(D, a)$
这个其实和信息增益的那个非常类似，上面是信息增益最大的属性，而原始数据集D的熵固定，信息增益最大，其实对应的是条件熵最小，那么就和这里基尼系数最小一样了。只不过基尼系数计算的时候更加简单，没有对数的复杂运算罢了。

这里还得提一点，就是CART决策树是一棵二叉树，也就是不管你当前特征取值有多少个，我只分成两部分(是或者不是)，那么此时在特征 $a$ 的某一取值下划分成了 $D_1$ 和 $D_2$ 两部分，即
$D_{1}=(x, y) \in D \mid a(x)=某一取值v, D_{2}=D-D_{1}$
此时的基尼系数计算:
$\operatorname{Gini}(D, a=v)=\frac{\left|D_{1}\right|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} \operatorname{Gini}\left(D_{2}\right)$
通过计算每个特征的每个特征值划分下的基尼系数，就能直接确定出最优属性和最优划分点了。下面是具体CART生成树算法，来自《统计学习方法》

CART决策树的生成过程中，每次分裂只会产生两个分叉，二叉的好处是不会遇到ID3使用信息增益的那种问题，并且还不用很多的对数计算，所以CART决策树相比ID3或者C4.5来说，还是优势多多的。

5. 决策树的剪枝

剪枝是决策树学习算法对付"过拟合"的手段，有预剪枝和后剪枝两种策略，前者是在决策树的生成过程中进行剪枝，而后者是决策树生成完之后进行剪枝。注意，sklearn不支持后剪枝，可通过设置max_depth来进行预剪枝，或者设定min_impurity_decrease参数，指定信息熵或者基尼不纯度的阈值，来进行剪枝优化模型。

5.1 预剪枝

在决策树生成过程中，对每个节点划分前进行估计，若当前节点划分不能带来决策树泛化性能的上升，停止划分并将当前节点标记为叶节点。

西瓜书上举了详细的例子，剪枝的时候，要有一个验证集了，也就是需要看决策树的泛化性能。预剪枝的思路是这样， 在每一次决策树划分的时候，要对决策树划分前和划分后的泛化性能进行一个估计，只有当泛化性能提升的时候，才进行分裂。看西瓜书上的例子：

预剪枝策略使得决策树在生成过程中比较保守，确实是能降低过拟合风险了，并且能降低训练时间开销和测试开销，但也会带来欠拟合的风险，因为可能有些分支的当前划分不能提升泛化性能或者导致泛化性能下降，但是在基础上的后续划分可能会带来泛化性能的提升，而预剪枝的这种"贪心"策略，是无法感知到这些问题的，果断就完事。

5.2 后剪枝

先从训练集生成一棵完整的决策树，然后自底向上的对非叶子节点进行考察，若将该节点对应子树替换成叶子节点能带来泛化性能的提升，那么就干掉子树，把该节点直接标记为叶子节点。

后剪枝的思路是我先生成一棵比较复杂的决策树，然后从最后的第一个非叶子节点开始，先计算当前树的泛化性能，然后把这个非叶子节点标记为叶子节点，再计算树的泛化性能，如果后者的性能还高，那么就剪掉子树，直接标记为叶子，看图：

后剪枝决策树的欠拟合风险很小，泛化性能也往往优于预剪枝决策树。但由于要先有一棵树，再从树的基础上从底往上计算，往往训练时间开销比较大。

6. 决策树连续值和缺失值的处理

6.1 连续值的处理

对于连续属性，取值数目不再是有限了，不能直接对连续属性各个取值进行节点划分了，还要注意，ID3和C4.5的另一个不同ID3无法直接处理数值型数据，如果想处理，需要离散化特征，而C4.5就可以直接处理连续特征了。这个原因，我也在知乎上找了下，有大佬是这么解释的，具体可看下面的链接：

那么C4.5到底是如何处理连续特征呢？其实也比较简单，首先，把训练样本中连续特征的值先从小到大排序，基于每一个划分点(两两之间划一刀)，比如取值有0,1,0.3,…那么在前面两个划一刀就是0.2，那么就能把数据集D划分为两个分支，在这个特征上小于0.2的和大于0.2的，西瓜书上的公式其实更容易理解:
$T_{a}=\left\{\frac{a^{i}+a^{i+1}}{2} \mid 1 \leqslant i \leqslant n-1\right\}$
这里的 $a^i$ 就是从小到大排好序的序列，而除以2的这个操作，就是两两之间划一刀作为切分点，而数值计算就是找这两个数的中位数。这样就能像离散属性一样，来考察这些划分点了，选择最优的划分点划分即可。信息增益计算如下：

\begin{aligned} Gain (D, a) & = max_{t \in T_{a}} Gain (D, a, t) \\ = max_{t \in T_{a}} Ent (D) - \sum_{λ \in {-, +}} \frac{| D_{t}^{λ} |}{| D |} Ent (D_{t}^{λ}) \end{aligned}

$\begin{aligned} \operatorname{Gain}(D, a) &=\max _{t \in T_{a}} \operatorname{Gain}(D, a, t) \\ &=\max _{t \in T_{a}} \operatorname{Ent}(D)-\sum_{\lambda \in\{-,+\}} \frac{\left|D_{t}^{\lambda}\right|}{|D|} \operatorname{Ent}\left(D_{t}^{\lambda}\right) \end{aligned}$

G a i n (D, a) = t \in T_{a} max G a i n (D, a, t) = t \in T_{a} max E n t (D) - λ \in {-, +} \sum \frac{∣ ∣ D _{t}^{λ} ∣ ∣}{∣ D ∣} E n t (D_{t}^{λ})

这个是在

a

属性下找能获得最大信息增益的划分点。这里的"-“表示的是小于等于划分点值的样本集合，而”+"表示大于等于划分点值的样本集合。西瓜书上84也有个例子，可以好好看看，这里就不走了，有些多，并且思想也不是很复杂，只不过连续值这里划分每次都会出现两个叉了，也就是小于或者大于等于划分点的值。But， 与离散属性不同，若当前节点划分属性为连续属性，则该属性还可以作为后代节点的划分属性。

6.2 缺失值的处理

相对上面那个，这个相对重要一些，现实情况中遇到样本的某些属性是缺失的情况怎么办？

这里主要有两个问题 ① 属性值缺失的情况下如何进行划分属性选择？ ② 确定了划分属性之后，假设某样本在该属性上缺失了，要放到哪一边呢？

这里重点是理解这两个问题的解决方式，西瓜书上理论部分定义的那些符号可能会有些看起来不太好理解，我这里抄一遍没有意义，所以就我的理解记下结论，然后走一遍书上的例子即可(看懂例子)。

这里先针对上面两个问题说一下总的处理方式：

属性值缺失的时候划分属性选择，和前面一样，也是选择信息增益大的特征进行划分，只不过对于有缺失值的特征，计算信息增益的时候，只考虑在这个属性上不缺失的样本，那么相应的，这样算出来的信息增益要乘以一个比例，即非缺失样本所占的比例，理解成非缺失样本出现的概率会更容易。因为只有非缺失样本先出现，才能计算这个信息增益嘛。公式：
$\begin{aligned} Gain (D, a) & = ρ \times Gain (\tilde{D}, a) \\ = ρ \times (Ent (\tilde{D}) - \sum_{v = 1}^{V} {\tilde{r}}_{v} Ent ({\tilde{D}}^{v})) \end{aligned}$
这个公式理解的时候，后面括号就是用非缺失样本计算该属性带来的信息增益，这里的 $\rho$ 就是代表非缺失样本出现的概率，即 $\frac{\#_{非缺失样本}}{\#_{总样本}}$
确定好划分属性之后，缺失样本的划分问题，这时候把这个样本分配到所有的子节点上，但会根据各个子节点的样本个数，给当前样本施加一个权重，后面再计算信息增益的时候，对于这种样本就要考虑权重了。权重的计算比较简单，就是 $\frac{\#_{当前子节点上的样本}}{\#_{总样本}}$

这里还是走下书上的那个例题吧，把这个看懂了这一块就差不多。

西瓜书上算了一个"色泽"的，这里算个"纹理"的，毕竟后面以这个划分了，手推下：

其他的一样的计算法方式，那么既然纹理处的信息增益最大，那么从纹理处进行划分，看看是怎么划分的。

这里注意划分之后，再往下分裂时候的这个计算方式，带权重的样本会影响具体的熵计算过程和信息增益的计算过程。这个在这里写不开了，详细的可以看这篇文章，整理的非常好。这些过程，西瓜书上是略过的。

7. 多变量决策树

上面介绍的决策树，所形成的分类边界一个明显特性轴平行，即分类边界由若干个与坐标轴平行的分段组成。

这样的边界使得学习结果有较好的可解释性(每一段都对应了某个属性取值), 但如果学习任务较为复杂，需要很多段才能进行划分开，此时决策树相当复杂，计算开销会很大。

而斜决策树就是为了解决这个问题的，这种划分节点，不再是某种属性，而是属性的线性组合，每个非叶子节点是一个线性非分类器，此时就得到了斜的决策边界。

这个东西目前没有用过，所以先整理下主要是干嘛的，简单原理，等具体用到了再做补充吧。

8. 小总

到这里，西瓜书决策树这块梳理完毕，本来以为没啥补充的，但是一旦开始之后，还是不知不觉整理了这么多，主要针对西瓜书上没有的细节补充了很多，比如熵和信息，以及信息量的衡量方式这块，比如信息增益，熵的计算代码实现以及ID3算法的代码实现，比如信息增益存在的问题，比如处理缺失值这里，加权样本的递归分裂等。这样，决策树这块就基本完整啦。

后面的西瓜书重温系列文章，打算先停一段时间了，因为我发现，从重温每一章，到查阅各种资料进行查缺补漏，再到整理成博客所耗费的时间太长了，大部分时间都集中在了整理博客上，因为需要构思布局，构思语言和行文等(主要是真的想把重点知识比较通俗易懂的沉淀下来，而不是简单的抄一遍西瓜书)，而我这段时间正处在即将秋招的风口浪尖，通过找实习我发现了自己需要补充的其他知识太多了，所以我后面打算西瓜书依然会重温，但先暂且通过手写笔记的方式记录到笔记本上了，这样会节省一些时间学其他的知识，因为西瓜书后面的内容大部分偏手推的多，比如神经网络(感知机手推，前向反向传播手推)，朴素贝叶斯手推再到后面的无监督的那些概率模型手推，这一块知识如果想通俗易懂的全面整理，在构思和行文上需要花费超级多的时间，而我这段时间恰好是不敢耗费的，所以西瓜书重温系列打算秋招完了之后再进行补充啦 ， 10月之后见 😉。

参考:

周志华 - 《机器学习》
谢文睿 - 《机器学习公式详解》
信息熵
机器学习西瓜书白话解读
机器学习算法之决策树
《机器学习实战》
为什么C4.5决策树能处理连续特征，ID3树不能处理连续特征？

转载：https://blog.csdn.net/wuzhongqiang/article/details/116712254

查看评论

飞道的博客

飞道的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章