决策树-ID3算法和C4.5算法
决策树是一种有监督(现有样本已知分类结果)的机器学习方法。
它通过对已有样本的学习生成一颗决策树(可看成if-then规则集合)，从而能对新样本作出相应分类。
本文重点阐述如何选择特征建立决策树，并给出理解算法的具体实例。
本文目录
一、什么是决策树
决策树：通过对已知样本的学习，一步一步将特征进行分类，从而将整个特征空间进行划分，进而区分出不同类别的算法。
我们在逻辑判断中用到的思想if, else if ,else, then，其实就是决策树的思想。
只是用哪个条件特征先做if，哪个条件后做if得到的结果会比较好呢？
1970年，一名叫昆兰的大牛采用了信息论中的熵来度量最优特征选择。昆兰把这个算法称为ID3算法。
该算法一出，它的简洁和高效就引起了轰动。
接下来我们详细介绍ID3算法。
二、ID3算法详解
1 什么是熵
熵度量了事物的不确定性，越不确定的事物，熵越大。
随机变量X的熵公式如下：
其中n表示随机变量X的n种不同离散取值，pi表示X取值为i的概率，log表示以2为底或以e为底的对数。
假设随机变量X表示掷一枚硬币的结果，它有两种可能的取值，正面或反面，各占1/2，这时随机变量X的熵为：
假设随机变量X表示掷一枚骰子的结果，它有六种可能的取值，{1,2,3,4,5,6}，各占1/6，这时随机变量X的熵为：
掷一枚骰子的不确定性比掷一枚硬币的不确定性大，熵值也大。
了解了熵的概念，下面我们详细介绍ID3算法。
2 ID3算法
在决策树的每一个节点，我们都要选择最优的特征进行分裂。那么怎么定义在该次分裂中该特征是最优选择？
ID3算法采用信息增益来衡量变量是不是最优的。我们Gain(D,a)来表示信息增益，具体公式如下：
若当前样本集合D中总共有K类，其中第k类的样本所占比例为pk，则D的信息熵公式如下：
为了更清晰地理解信息增益公式，以及决策树如何选择特征，我们看一个构造的简单例子：
正例(放贷)占11/17，反例占6/17，根节点的信息熵为：
计算当前特征集合{学历，是否有房子，信贷表现}中每个特征的信息增益，选择信息增益最大的特征进行分裂。
学历有4个可能取值：{初中及以下，高中，大学，研究生及以上}
D1(学历=初中及以下)={1，2，3，4}，正例2/4，反例2/4。
D2(学历=高中)={5，6，7，8，9，10}，正例4/6，反例2/6。
D3(学历=大学)={11，12，13，14}，正例3/4，反例1/4。
D4(学历=研究生及以上)={15，16，17}，正例2/3，反例1/3。
4个分支节点的信息熵为：
则学历的信息增益为：
同理，可以算出其它两个特征的信息增益。
我们发现
所以根节点我们选择的划分特征为“信贷表现”。
从而可以得到三个子节点。对于这三个节点，可以递归地使用信息增益寻找最优划分特征，进行进一步的分裂，从而建立最终的决策树。
在该文章的实例中，信贷表现良好和非常好的样本最终都放贷了。说明这两个子节点中的样本非常纯。
现实数据可能远比实例中的数据复杂，不是信贷表现良好就一定会放贷。有些信贷表现好，也可能是养的信贷数据，还要从别的维度去佐证这个客户有能力且有意愿还贷，才会最终给这个客户放贷。
接下来对第一个分支结点：D1(信贷表现=较差)={2,4,7,10,11,17}，计算当前特征集合{学历，是否有房子}中每个特征的信息增益，选择信息增益最大的特征进行分裂。
当前结点正例(放贷)占1/6，反例占5/6，当前节点的信息熵为：
学历有4个可能取值：{初中及以下，高中，大学，研究生及以上}
D11(学历=初中及以下)={2，4}，正例0/2，反例2/2。
D12(学历=高中)={7，10}，正例0/2，反例2/2。
D13(学历=大学)={11}，正例1/1，反例0/1。
D14(学历=研究生及以上)={17}，正例0/1，反例1/1。
4个分支节点的信息熵为：
那么当前分支节点特征学历的信息熵为：
同理可以求出特征是否有房子的信息熵为：
可以发现
于是我们选择学历作为当前划分特征，得到最终的决策树如下：
从上面的结果可以发现，对于信贷表现较差的客户，学历是初中及以下和高中的都拒绝了，学历是大学的放贷了，学历是研究生的拒绝了(为什么大学学历可以放贷，研究生学历却不行？)。
从这里可以看出，用信息增益准则虽然可以构建出一颗决策树，通过这颗树可以对新进来的样本进行最终的决策(放贷或拒绝）。
但是这样的决策树存在一些问题。
3 ID3算法的缺点
从求解信息增益的公式中可以看出，信息增益准则对取值类别较多(分的类别越多，分到每一个子节点的样本数量越少，子节点是同一个类别的可能性越大)的特征有所偏好。
假设实例数据集中的编号也是一个候选划分特征，那么该特征的每一个类别中只有一个样本(非常纯)。
所有分支节点的信息熵都为0，该节点的信息增益就为根节点的信息熵，值为0.936，大于特征信贷表现的信息增益0.706。
应该选择编号建立决策树？
显然，这样生成的决策树不具备泛化能力。
而且ID3算法没有考虑连续特征，比如长度是连续值，无法使用ID3算法。
同样的，对于缺失值和过拟合也都没有考虑，只是寻找信息增益最大的特征进行划分。
那我们要如何改进这个算法？
二、C4.5算法详解
对于之前讲到的ID3算法，存在四个主要不足：一是信息增益准则对取值类别较多的特征有所偏好，二是不能处理连续特征，三是没有考虑缺失值处理，四是过拟合。
昆兰在C4.5算法中改进了这四个问题。
1 第一个问题的改进办法
对于第一个问题，C4.5算法采用信息增益率，做为变量的最终筛选标准。
通过引进一个和特征类别数目成正比的量作为分母，来消除这种偏好。
信息增益率公式如下：
其中，Gain(D,a)就是ID3算法中的信息增益，IV(a)就是和特征类别数目成正比的量。
IV(a)的具体公式如下：
在全量样本中，特征学历有4个可能取值：{初中及以下，高中，大学，研究生及以上}，是否有房子有2个可能取值：{有，无}，信贷表现有3个可能取值：{较差，良好，非常好}。
分别看下这3个特征对应的的IV(a)值：
IV(学历)=1.95 (n=4)
IV(是否有房子)=0.936 (n=2)
IV(信贷表现)=1.55 (n=3)
可以发现，特征中类别数越多，IV值越大，放在分母可以避免信息增益更偏好类别多特征的缺点。
但是，除以这个分母后会不会使得算法更偏向于特征类别较少的变量？
答案是：会的。
所以C4.5算法没有直接选择信息增益率最大的特征进行划分，而是先挑出信息增益高于平均水平的特征，再从中选择信息增益率最好的特征，尽可能避免类别数目对划分特征选择的影响。
2 第二个问题的改进办法
对于第二个问题，不能处理连续特征。C4.5的思想是将连续特征离散化。
比如一个集合中有n个样本，m个特征，m个特征中有一个连续特征A。特征A有n个取值，从小到大排列为a1,a2,...,an。算出相邻两个样本的平均值作为划分点，一共有n-1个划分值。
对于这n-1个点，分别计算以该点作为二元分类点时的信息增益，选择信息增益最大的点作为该连续特征的二元离散分裂点。
比如取到了信息增益最大的点为au，则小于au的值为类别1，大于au的值为类别2。从而实现了连续特征的离散化。
对于第三个问题，不能处理缺失值问题。刘建平老师的博客中有详细的阐述，感兴趣的可以自行了解。
对于第四个问题，C4.5引入了正则化系数进行初步剪枝，等到讲CART树剪枝时对比进行阐述。
虽然C4.5算法对ID3算法的几个主要问题进行了改进，但是仍然有优化的空间。
比如C4.5算法只能用于分类，不能用于回归。C4.5使用了熵模型，里面有大量的对数运算，非常耗时。
这些问题在CART树里进行了改进。
接下来会重点整理CART树相关知识点，敬请期待。
参考文献：
周志华《机器学习》 https://www.cnblogs.com/pinard/p/6050306.html https://zhuanlan.zhihu.com/p/126294494?utm_source=wechat_session&utm_medium=social&utm_oi=1090367802518536192&utm_content=first https://zhuanlan.zhihu.com/p/85374168?utm_source=wechat_session&utm_medium=social&utm_oi=1090367802518536192&utm_content=first https://zhuanlan.zhihu.com/p/85374168?utm_source=wechat_session&utm_medium=social&utm_oi=1090367802518536192&utm_content=firsthttps://zhuanlan.zhihu.com/p/26760551?utm_source=wechat_session&utm_medium=social&utm_oi=1090367802518536192&utm_content=first