决策树

判别模型 屏幕快照 2018-02-23 下午4.08.21.png C3决策树算法流程

  1. 每次选择其中一个特征对样本集进行分类
  2. 对分类后的子集递归进行步骤1
一般来说最理想的是样本都属于同一个分类,但是一般情况下,我们根据选取特征来实现最好分类结果呢?
我们都用纯净来说明分类效果好,样本集的纯度可以用熵来进行衡量
熵是信息论中的概念,用来表示集合的无序程度,熵越大表示集合越混乱,反之则表示集合越有序。
假如一个随机变量 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个子集的权重。
C3决策树算法实现
1.遍历每个决策条件(如:位置、来源网站),对结果集进行拆分
2.计算该决策条件下,所有可能的拆分情况的信息增益,信息增益最大的拆分为本次最优拆分
3.递归执行1、2两步,直至信息增益<=0
C4.5 C4.5是机器学习算法中的另一个分类决策树算法,它是基于ID3算法进行改进后的一种重要算法。改进有如下几个要点:
  • 解决了信息增益(IG)的缺点
  • 解决了连续变量问题
信息增益的缺点
决策树
文章图片
屏幕快照 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 【决策树】机器学习算法之决策树
机器学习经典算法优缺点
决策树算法及实现
决策树之 C4.5 算法

    推荐阅读