C3决策树算法流程

每次选择其中一个特征对样本集进行分类
对分类后的子集递归进行步骤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为特征来划分，这时候你会发现信息增益很大。不过显然这种特征对于样本的分隔没有任何意义。
那么导致这样的偏差的原因是什么呢？从上面的例子应该能够感受出来，原因就是该特征可以选取的值过多。解决办法自然就想到了如何能够对树分支过多的情况进行惩罚,从而引出了信息增益率。