博文
算法学习（一）：决策树
||
最近在看论文时经常遇到一些重要的算法，觉得自己还是应该先去学一下相关算法然后再进一步读论文。在小利学长的指导下准备在这两周学习被评为数据挖掘领域的Top10算法。
（一）：决策树
1：定义
书中的概念理解起来就是已知多组对象的属性和对象所属的分类，我们通过建立决策树来预测某一新加入的组对象所属的分类。决策树的建立是通过对已有数据的训练，叶子节点是对象所属的分类，非叶子节点包含属性的测试条件，每个分叉路径代表相应的属性取值。
下图就是一个典型的决策树的例子：
2：如何生成决策树
（1）：ID3
因为一个对象有多个属性，既然决策树的每个非叶子节点都是一个属性，那么选取什么样的属性作为根节点。
首先解决哪种生成树是最优的。书中给出了一个奥坎姆剃刀假设：优先选择拟合数据的最简单的假设。但并没有证明，貌似这是一个比较直观的原则，没有证明。
我的理解是如果假设或者模型过于复杂，那么其限制条件更多，得到的结果更趋向于特殊化，则对已有数据的拟合是比较的高的，但对于预测的数据则是比较低的。
接下来就是如何使决策树更简单，选取什么样的属性作为根节点。
ID3算法通过自顶向下构造决策树来进行学习。构造过程是从“哪一个属性将在树的根节点被测试？”这个问题开始。分类能力最好的属性被选为根节点。然后为根节点属性的每个可能的值产生一个分支，然后递归地进行这一过程。如图
ID3算法提出了“信息增益”的统计属性来衡量给定的属性区分训练样例的能力。
先学习一下“熵”。ID3算法中利用熵来刻画属性划分后的不纯性的程度。不纯性的程度越低，则树越倾斜。
熵：
其中p(i|t)表示给定节点t中属于类i的比例
举一个例子：
假设S是一个关于布尔概念的有14个样例的集合，它包括9个正例和5个反例（我们采用记号[9+，5-]来概括这样的数据样例），那么S相对于这个布尔样例的熵为：
Entropy（[9+，5-]）=-（9/14）log2（9/14）-（5/14）log2（5/14）=0.940。
信息增益：
其中Sv是S中属性A的值为v的子集
举一个例子：
假定S是一套有关天气的训练样例，描述它的属性包括可能是具有Weak和Strong两个值的Wind。像前面一样，假定S包含14个样例，[9+，5-]。在这14个样例中，假定正例中的6个和反例中的2个有Wind =Weak，其他的有Wind=Strong。由于按照属性Wind分类14个样例得到的信息增益可以计算如下:
有了信息增益这个概念之后，在生成决策树的过程中不断迭代选择剩余属性中信息增益最大的属性作为子子树的根节点。
（2）：C4.5
C4.5是对ID3的改进
1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；
2) 在树构造过程中进行剪枝；
3) 能够完成对连续属性的离散化处理；
4) 能够对不完整数据进行处理。
2) 在树构造过程中进行剪枝；
3) 能够完成对连续属性的离散化处理；
4) 能够对不完整数据进行处理。
由于信息增益度量存在一个内在的偏置，偏袒具有较多值的属性。在C4.5中提出一个信息增益比率。
先介绍分裂信息：
其中S1到Sc是c个值的属性A分割S而形成的c个样例子集。
增益比率：
https://blog.sciencenet.cn/blog-796597-627003.html
下一篇：算法学习（二）：贝叶斯分类器
扫一扫，分享此博文