决策树算法

2022/8/29 1:25:10

本文主要是介绍决策树算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1.决策树

  在机器学习中,决策树是一个预测模型,他代表的是对象属性与对象值之间的一种映射关系。决策树是一种树形结构,其中每个内部节点表示一个属性上的测试,每个分支代表一个测试输出,每个叶节点代表一种类别。

  分类树(决策树)是一种十分常用的分类方法。它是一种监督学习,所谓监督学习就是给定一堆样本,每个样本都有一组属性和一个类别,这些类别是事先确定的,那么通过学习得到一个分类器,这个分类器能够对新出现的对象给出正确的分类。1986年 Quinlan提出了著名的ID3算法。在ID3算法的基础上,1993年Quinlan又提出了C4.5算法。通常使用的分类回归树(class and regress tree)是一个二叉树,所有的输入从根节点一步一步走到叶子结点,也就是所有的数据最总都会落到叶子结点,既可以做分类也可以做回归。

  比如,有如下信息,前四列分别为天气情况、、温度、湿度、风。最后一列为标签列,是否出去玩。

  通过上面信息,我们可以根据不同划分构造不同决策树。

  (1)基于天气划分

 

  (2)基于温度划分

 

   (3)基于湿度划分

 

  (4)基于是否有风划分

  上面的树很简单,只做了一次划分,如何构造一颗好的决策树呢?就没那么容易了,需要考虑的问题有很多。

2.信息熵与信息增益

  信息熵(information entropy)是信息论的基本概念。描述信息源各可能事件发生的不确定性。最早由1948年香农提出,并给出数学表达式。信息熵是用于衡量不确定性的指标,也就是离散随机事件出现的概率,简单地说“情况越混乱,信息熵就越大,反之则越小”。

 公式如下:

 具体理解如下:

 

  上式中,一般底数b为2。P表示事件发生的概率。其信息熵与概率的关系图如下图所示,当随件变量取值n=2时,表示i取1到2。此时P=1/n=0.5时,取最大值熵,此时混乱度最大,事件发生的不确定性最大。通过证明还可以发现信息熵的范围为[0,log(n)]。概率与信息熵的图大致为

 

  信息增益是表示特征X使得类Y的不确定性减少的程度,信息增益 = 熵 - 条件熵。计算公式如下:

   式子中,后一项H(Y|X)为条件熵,其计算公式如下:

  上式中P为x发生的概率。

3.基尼指数(Gini Index)

 

  P为概率,P越接近1,系数越接近0,表明划分越纯。Gini系数用于CART算法中。

4.ID3决策树

  ID3使用了信息增益的方式构造决策树,通过信息增益来划分数据属性。到底选择哪个特征作为第一个根节点,需要计算各自的信息增益。在给的数据列表中,标签列有9天玩,5天不玩,整体信息熵(2为底)为:

  H(X)=-9/14 *log(9/14)-5/14 *log(5/14)=0.940 bits

  对四个特征outlook、Temp、Humidity、Windy四个特征逐一分析,找出信息增益最大的作为根节点。先对outlook特征开始计算:

  H(outlook=sunny)=-2/5*log(2/5)-3/5*log(3/5)=0.971 bits

  H(outlook=overcast)=0

  H(outlook=rainy)=-3/5*log(3/5)-2/5 *log(2/5)=0.971 bits

  则选择outlook作为条件熵的信息熵值为:

  H(Y|X=outlook)=5/14 *0.971+4/14 * 0+5/14 *0.971=0.693 bits

  选择Outlook作为划分的决策树信息增益为

  Gain(outlook)=0.940-0.693=0.247

  同样的方式,计算剩下三个特征的信息增益,如下:

  Gain(temperature)=0.029

  Gain(humidity)=0.152

  Gain(windy)=0.048

  所以选择outlook作为根节点。

  继续根据不同分支按照剩下三个特征进行划分:

  第一个分支:

  Gain(temperature|sunny)=0.571

  Gain(humidity|sunny)=0.971

  Gain(windy|sunny)=0.420

  所以对该部分数据按湿度进行划分。

  第二个分支:

  标签全部为yes,信息熵为0,无需划分。

  第三个分支:

  Gain(temperature|rainy)=0.020

  Gain(humidity|rainy)=0.020

  Gain(windy|rainy)=0.971

  所以对该部分数据按照是否有风进行划分。

  通过划分可以得到如下的决策树:

 

 

划分后,每一个叶子结点的标签类型相同,不用再划分了。

5.C4.5决策树

  使用信息增益率(解决ID3问题考虑自身熵)来选择属性分裂,能处理连续型数据和不完整数据, 采用信息增益比选择特征,减少因特征值多导致信息增益大的问题。现在假设这样一种情况,如果每个属性每种类别只有一个样本,那么属性信息熵就为0.(或者增加一列ID,为样本的编号)此时,信息增益为类别熵,无法选择有效的分类特征。信息增益率用信息增益/内在信息,会导致属性的重要性随着内在信息的增大而减小(也就是说,如果这个属性本身不确定性就很大,那我就越不倾向于选取它)。信息增益率公式如下:

IGR=Gain/H

  Gain为信息每个属性的信息增益,H为每个属性的信息熵。分别计算outlook、temperature、humidity、windy的属性信息熵(以2为底)。

  H(outlook)=-5/14*log(5/14)-5/14*log(5/14)-4/14*log(4/14)=1.577

  H(temperature)= -4/14*log(4/14)-6/14*log(6/14)-4/14*log(4/14)=1.556

  H(humidity)=-7/14*log(7/14)-7/14*log(7/14)=1.0

  H(windy)= -6/14*log(6/14) -8/14*log(8/14)-8/14*log(8/14)=0.985

  计算信息增益率:

  IGR(outlook)=Gain(outlook)/H(outlook)=0.247/1.577=0.156

  IGR(temperature)=Gain(temperature)/H(temperature)=0.029/1.556=0.0186

  IGR(humidity)=Gain(humidity)/H(humidity)=0.152/1.0=0.151

  IGR(windy)=Gain(windy)/H(windy)=0.048/0.985=0.049

  Outlook的信息增益率最高,选择它作为分裂属性,也就是第一个根节点。最后对子节点根据信息增益率不断重复划分的过程,其结果与前面ID3算法得到的图一样。

  这里举个例子,只是便于简单理解C4.5算法。如下:

  C4.5算法倾向于选取属性的类别少的,这里是windy(与windy信息增益率最高一致)属性。

6.CART决策树(Classification and Regression Tree)

  使用GINI系数来当做衡量标准。CART分类树算法每次仅对某个特征的值进行二分,而不是多分,这样CART分类树算法建立起来的是二叉树,而不是多叉树。CART使用了 ​ ​CCP代价复杂度剪枝算法​​,对C4.5的剪枝方法进行了优化。关于CART算法目前没有详细研究,后续补充。

7.决策树剪枝

  决策树在不断重复划分过程中,有时会造成决策树分支过多导致过拟合.因此需要剪枝降低过拟合风险。决策树剪枝策略包括预剪枝与后剪枝。

  预剪枝:限制深度,叶子节点个数,叶子结点样本数,信息增益量等。

  后剪枝:通过一定的衡量标准判断是否需要分裂。衡量标准损失如下:

  C(T)为gini系数与样本数乘积,α为系数,T(leaf)为叶子结点阈值,叶子节点越多,损失越大。如果分裂后C变大,就不需要分裂。

8.决策树生成的终止条件

  (1) 当子节点中的样本属于同一类

  (2) 子节点没有样本

  (3) 特征已经用完了

 

 

参考资料:

https://zhuanlan.zhihu.com/p/493238757

https://blog.csdn.net/zjsghww/article/details/51638126

https://blog.51cto.com/u_14974790/5284485

 

不足或错误之处,恳请指正,有帮助请点赞,谢谢!



这篇关于决策树算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程