• 算法对比

线性模型与决策树模型的对比：

线性模型是将所有的特征转变为概率，并对所有的特征加权求和，从而对模型进行分类，只能找到线性分割，而决策树模型是一个一个特征的进行处理，对每一个特征进行划分，可以找到非线性分割；

 

• 决策树算法ID3

ID3算法是一种贪心算法，用来构建决策树，ID3起源于概念学习系统，以信息熵的下降速度为选取测试属性的标准；即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。

要了解信息增益，需要先了解信息熵的概念。

熵（entropy）：热力学中表征物质状态的参量之一，其物理意义是体系混乱程度的度量；

信息熵（information entropy）：是度量样本集合纯度最常用的一种指标；

假定当前样本集合D中第K类样本所占的比例为Pk（k=1,2,3，…，|n|），则D的信息熵为：

Ent(D)的值越小，则样本集合D的纯度越高。

信息增益

假定离散属性a有n种可能取值（1~n），则a的信息熵为Ent(D)，以属性a对样本集合D进行划分，则会产生n个节点：

其中第m个分支节点（1<=m<=n），包含样本集合D中所有在属性a上取值为am的样本，记做Dm，不同的分支节点包含的样本数不同，给分支节点赋予权重|Dm|/|D|，由此可知，样本数越多，Dm越大，分支节点的影响越大。离散属性a对样本集合D进行划分的信息增益（information gain）为：

为便于记忆，以下二分类数据计算信息增益：

属性a	Label
A	True
B	True
A	False
B	False
A	False

这里一共有5条数据，属性a有A，B两类，目标label有True和False两类；下面开始计算label的信息熵；其中True有2个，False有3个：

再计算属性a的信息熵，属性a有A，B两个属性，且A有3个，其中一个是True，两个是False，而B有2个，一个True，一个False，这里先计算a中A对label的信息熵为：

同理得B对label的信息熵为：

则a对label的信息增益为：

缺点：单纯使用信息增益作为划分标准会导致结果不具有泛化性，例如上面若存在一个b属性的值为1、2、3、4、5，可以计算b对D的信息增益是极大的，但却不能很好的进行分类；此外，ID3采用信息增益来选择划分属性，对可取值数目较多的属性有所偏好，容易构建庞大的宽且浅的决策树。

C4.5算法

为避免ID3中提到的信息增益的缺点，在ID3的基础上，为减少信息增益偏好带来的不利影响，提出了增益率的概念，定义如下：

 

IV(a)是属性a的固有值，属性a可能的取值数目越多，则IV(a)越大；

增益率对取值数目较少的属性有所偏好，因此，C4.5算法不直接选择增益率最大的候选划分属性，而是使用一个启发式方法，先从候选划分属性中找到信息增益高于平均水平的属性，再从中选择增益率最高的；

 

CART – 分类回归树决策算法

与ID3采用信息增益作为属性划分标准，C4.5采用信息增益大于平均水平的属性中选择增益率最大的属性不同，CART采用Gini指数作为划分属性的选择标准；

基尼指数（Gini index）是度量样本集合纯度最常用的一种指标，反映了从样本集合D中随机抽取两个样本，其类别标记不一致的概率为：

Gini(D)的值越小，则样本集合D的纯度越高；

针对属性a的基尼指数

Gini_index(D,a)的值越小，以属性a进行划分越优(这里指的是分类是时候，CART做回归预测时，将采用另一种指标)；

还是以上面的数据集为例，计算Gini_index(D,a)；

先计算A类的基尼指数：

接着计算B类的基尼指数：

那么，