决策树

决策树

屏幕快照 2018-02-23 下午4.08.21.png

C3决策树算法流程

一般来说最理想的是样本都属于同一个分类，但是一般情况下，我们根据选取特征来实现最好分类结果呢？

我们都用纯净来说明分类效果好，样本集的纯度可以用熵来进行衡量

熵是信息论中的概念，用来表示集合的无序程度，熵越大表示集合越混乱，反之则表示集合越有序。

假如一个随机变量 X 的取值为 X = {x1,x1,...,xn}（一般对应类别），每一种取到的概率分别是 {p1,p1,...,pn}，那么 X 的熵定义为

屏幕快照 2018-03-13 下午8.59.16.png

在决策树的生成过程中，我们的目标就是要划分后的子集中其熵最小，这样后续的的迭代中，就更容易对其进行分类。

既然是递归过程，那么就需要制定递归的停止规则.

1.子集的熵达到阈值
2.子集规模够小
3.进一步划分的增益小于阈值

假设集合 U，一次拆分后变为了两个集合 u1 和 u2 ，则有：

IG = H(U) - (Pu1 x H(u1) + Pu2 x H(u2))

IG为信息增益。Pu1,Pu2代表2个子集的权重。

1.遍历每个决策条件（如：位置、来源网站），对结果集进行拆分
2.计算该决策条件下，所有可能的拆分情况的信息增益，信息增益最大的拆分为本次最优拆分
3.递归执行1、2两步，直至信息增益<=0

C4.5是机器学习算法中的另一个分类决策树算法，它是基于ID3算法进行改进后的一种重要算法。改进有如下几个要点：

屏幕快照 2018-03-13 下午9.28.56.png

比如我们以Day为特征来划分，这时候你会发现信息增益很大。不过显然这种特征对于样本的分隔没有任何意义。
那么导致这样的偏差的原因是什么呢？从上面的例子应该能够感受出来，原因就是该特征可以选取的值过多。解决办法自然就想到了如何能够对树分支过多的情况进行惩罚,从而引出了信息增益率。

屏幕快照 2018-03-13 下午9.11.09.png

比如一个特征温度为温度，那么这个时候计算每个温度的最大信息增益是不合适的。那么我们可以采用划分一个范围，

20160706164012543.png

然后判断在哪一个节点的分裂信息最大，就可以化成两部分，比如如下0～2，2～13。

屏幕快照 2018-03-13 下午9.19.01.png

最后编辑于：2018.03.13 21:35:22

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。