机器学习 - 决策树

2019-07-29 Views Machine Learning2051字8 min read
featureimg

决策树是一种常见的机器学习算法,它的思想十分朴素,类似于我们平时利用选择做决策的过程。

引言

通俗的来理解决策树,比如说下班的时候,我们会根据很多情况来决定我们接下来做什么,比如说像下面这张图这样:

decision tree

这也就引出了我们的问题——人凭借自己的感觉来决定做每个决策的先后顺序,那么计算机是怎么知道什么时候该做什么决策呢?这也就引出了信息熵的概念。

正文

信息熵

1948 年,香农提出了信息熵的概念解决了信息的量化问题【我们今天知道的1bit就是信息量化的结果】(如果不知道什么是熵的读者可以戳这里)。信息熵是被用来衡量信息的不确定性的东西,根据常识我们也可以知道,当一个东西不确定性越大的时候,我们想要了解它就要知道更多的信息。信息熵根据定义为如下表达式:

H(X)=xXP(x)log2P(x)H\left( X \right) =-\sum_{x\in X}^{}{P\left( x \right) \log _{2}^{}P\left( x \right)}

其中, P(x) 表示事件出现的概率。例如,1个盒子里分别有5个苹果🍎和5个梨,
我们随之从中取出一个水果。那么这个水果是苹果还是梨呢?这个问题的信息量多大呢?由于苹果和梨出现的概率都是1/2 ,代入信息熵公式,可以得到其信息熵为:

H(X)=(12log212+12log212)=1H\left( X \right) =-\left( \frac{1}{2}\log _{2}^{}\frac{1}{2}+\frac{1}{2}\log _{2}^{}\frac{1}{2} \right) =1

所以要知道这个水果是苹果/梨的信息量为1比特。
所以,为了知道最大量的信息,决策树会遍历所有的特征,计算用这个特征作为划分数据前后的特征时信息熵的差值(这时候计算的熵也被称为条件熵)。计算出来信息增益最大即差值最大的特征就是划分数据集的特征。

比如,一个盒子里共有红、白、黑、蓝4种颜色的球共16个,其中红球2个,白球2个,黑球4个,蓝球8个。红球和黑球的体积一样,都为1个单位;白球和蓝球的体积一样,都为2个单位。红球、白球和黑球的质量一样,都是1个单位,蓝球的质量为2个单位。
我们应该优先选择体积这个特征,还是优先选择质量这个特征来作为数据集划分依据呢?根据前面介绍的结论,我们先计算基础信息熵,即划分数据集前的信息熵。从已知信息容易知道,红球、白球、黑球、蓝球出现的概率分别为2/16,、2/16、4/16,8/16,因此基础信息熵为:

H(Dbase)=(216log2216+216log2216+416log2416+816log2816)=1.75H\left( D_{base}^{} \right) =-\left( \frac{2}{16}\log _{2}^{}\frac{2}{16}+\frac{2}{16}\log _{2}^{}\frac{2}{16}+\frac{4}{16}\log _{2}^{}\frac{4}{16}+\frac{8}{16}\log _{2}^{}\frac{8}{16} \right) =1.75

接着使用体积来划分数据集,此时会划分出两个数据集,第一个子数据集里是红球和黑球,第二个子数据集里是白球和蓝球,我们计算这种划分方式的信息熵。其中第一个子数据集里,红球2个,黑球4个,其概率分别为2/6和4/6,因此第一个子数据集的信息煽为:

H(D1sub1)=(26log226+46log246)=0.918296H\left( D1_{sub1}^{} \right) =-\left( \frac{2}{6}\log _{2}^{}\frac{2}{6}+\frac{4}{6}\log _{2}^{}\frac{4}{6} \right) =0.918296

第二个子数据集里,白球2个,蓝球8个,其概率分别为2/10和8/10,因此第二个子数据集的信息熵为:

H(D1sub2)=(210log2210+810log2810)=0.721928H\left( D1_{sub2}^{} \right) =-\left( \frac{2}{10}\log _{2}^{}\frac{2}{10}+\frac{8}{10}\log _{2}^{}\frac{8}{10} \right) =0.721928

因此,使用体积来划分数据集后,其信息熵H= 1.640224,其信息增益为0.109776,如图所示。

information entropy - 6Gini Impurity

以上就列举了一个计算信息增益的过程。通过比较用不同特征划分这组数据的信息增益,决策树会选择信息增益最大的作为分类的特征。

信息熵与热力学熵

但其实作为熵来看,信息熵又和热力学的熵有着一定的区别。根据定义我们可以知道,熵是用来衡量不确定性的东西,这也同时意味着如果我们把数据划分得越细,理论上信息熵是可以接近于0的。这也就意味着数据已经被我们划分到了最小的类别,不能再划分了,这时的数据是最纯的。
热力学第二定律说明宇宙是在不断熵增的,而信息论告诉我们,我们在看书学知识的过程其实是一个减熵的过程,因为我们得到了信息。所以人类其实就是在不断消耗资源让宇宙熵增的过程中,在不断获取信息、创造信息来减熵来让世界更加有序

决策树实现

1、离散化

很多时候我们我们会发现,因为数据是连续的(比如说考试成绩),我们没法很好的用决策树来划分数据集。这个时候我们会把数据离散化,即把0-60评定为差,60-80评定为良,80-100评定为优秀。通过这种方法,我们就可以把数据离散化,划分成三种类别。

2、正则项

在决策树创建的时候很容易把类别最多的特征用来划分数据(即划分完之后每一个类别里只有少量元素,但有很多类别)。比如说我们把商品的ID作为了划分商品的依据,这样划分出来的数据看起来是最纯的,因为每个ID只对应一个数据。但这样就达不到我们的效果。这样的解决办法就是在计算每一项的信息熵时加上一个与类别个数成正比的正则项。

3、基尼不纯度

基尼不纯度是一种类似于信息熵的计算方法,它被用于衡量信息不纯度。其公式表达如下:

Gini(D)=xXP(x)(1P(x))=1xXP(x)2Gini\left( D \right) =\sum_{x\in X}^{}{P\left( x \right) \left( 1-P\left( x \right) \right) =1-\sum_{x\in X}^{}{P\left( x \right) _{}^{2}}}

在决策树构建中,我们可以选择使用基尼不纯度也可以使用信息熵,这两者没有太大区别。

4、剪枝算法

在决策树构建的过程中,很容易因为把类别划分得过细而出现过拟合的问题。所以就有了剪枝算法。
剪枝算法分为前剪枝后剪枝
前剪枝就是在构建决策树的同时对决策树进行限制,比如限制子节点的样本个数,当小于每一个样本个数就停止再分。
后剪枝就是在决策树构建完成之后进行剪枝。比如,计算合并相邻的两个节点之后信息熵的增加会不会高过某一个限定值,如果不高过这个限定值就把这两个节点合并。


注:如果文中有什么问题,欢迎在评论区指出;有不懂的也可以在评论区提问哦!


EOF
本文章采用CC BY-NC-SA 4.0进行许可。转载请注明出处!
上一篇

飞鸟集


下一篇

机器学习 - 逻辑回归