决策树算法就是寻找最优的划分选择x，然后根据x将数据划分开来，不断迭代，即可产生一颗完整的决策树。

一、划分选择

1.信息熵

信息熵，是一个描述样本“纯度”的量。信息熵越小，数据越纯。（熵这个概念通常的理解就是：熵越大，越混乱；熵越小，越单一）。

设样本为D，第k类所占比例

举个例子来说，若D中只有1类，则Ent(D)=0，已经到达最小了，即最纯的样本。若D中有2类，分别占1/2，那么Ent(D)为：

显然类别变多（数据变得不单纯），信息熵会变大。

2.信息增益——ID3算法采用的划分依据

对于数据中的所有特征属性A，某个属性为a，a的可能取值有V个，分别是

用

即ID3算法用于划分的属性

3.增益率——C4.5决策树使用的划分依据

信息增益存在的问题：对取值多的属性有偏好。

假设属性a的表示编号，若有10个样本，则属性a的取值就有10种可能，，若按a的取值划分

增益率的定义为：

IV(a)和信息熵的公式特别像，可以直观理解为是数据集划分后的信息熵，属性越多、划分的越多，则熵越大，则增益率就会变小，就平衡了只有信息增益而存在的问题。

但C4.5也不是单纯的使用信息增益，而是分为了2步：

step1：找信息增益高于平均值的属性。

step2：从上述挑选出的属性中找到增益率最高的属性来划分。

4.基尼指数——CART决策树使用的划分依据

即使用基尼值而不是信息熵来作判断，基尼值的定义为：

假设数据集D有12个数据，

Case1：分2类，每类6个

Gini(D)=0.5x0.5+0.5x0.5=0.5

Case1：分3类，每类4个

Gini(D)=0.33x0.66+0.33x0.66+0.33x0.66=1-3x0.33x0.33=0.66

基尼指数越小，数据越单纯。

基尼指数的定义为：

选择具有最小基尼指数的属性划分即可。

二、决策树的其它问题

1.剪枝问题——预防过拟合

预剪枝：在划分前，先将划分后和不划分的两种情况在验证集上做对比，再决定是否划分。

后剪枝：先生成决策树，从后往前考察划分后的准确率，再决定是否减掉。

2.连续值处理——离散化

C4.5采用二分法，即设连续值得取值包括x1，x2，，，xn，那先求出每两个点之间的中点，然后对每个中点求信息增益，最大的那一个中点当做划分依据，可以化为两半。

3.缺失值处理

如何找划分属性：采用没有缺失值的样本子集来评估划分依据。

如何对缺失样本划分：对于在属性上缺失的样本，同时划到所有子节点中，并改变该样本权重。

欢迎关注我的公众号：慢慢学算法