0x00 前言
决策树学习算法有三个步骤：
- 特征选择
- 决策树生成
- 决策树剪枝
特征选择，就是决策树的构造过程。
为了找到最优的划分特征，我们需要先了解一些信息论的知识。
- 信息熵(information entropy)
- 条件熵(conditional entropy)
- 信息增益(information gain)
- 信息增益率(information gain ratio)
- 基尼指数(Gini index)
0x01 信息熵
1.1 什么是信息熵
熵是热力学中的概念，表示混乱程度。熵越大，热力系统中粒子无规则的运动越剧烈；熵越小，粒子越趋近于静止的状态。
引申到信息论和概率统计中，信息熵表示随机变量的不确定度。对于一组数据来说，越随机、不确定性越高，信息熵越大；不确定性越低，信息熵越小。
为了计算熵，我们需要计算所有类别所有可能值所包含的信息期望值，著名的香农公式：
在一个系统中，有k类的信息，其中是选择该分类的概率（n/k），再乘p的对数，求和后加上负号。这是因为概率是小于1的数，是小于0的数，我们要求得到的熵是大于0的。
下面构造三个例子：假设有三组，每组为三类的信息，每组每类的概率为：
按照公式，分别计算信息熵：
我们看到，信息熵H值越小，说明数据的不确定性越小。第一个式子，每种分类情况都是均等的；第二个式子，数据有70%的概率是落在第三类中，因此要比第一个式子更稳定；第三个式子，干脆只有一个类，因此熵最小为0（特别稳定）。
如果在二分类的情况下，信息熵公式也可以写为下面的形式：
1.2 计算二分类信息熵并可视化
代码语言：javascript复制import numpy as npimport matplotlib.pyplot as plt
# p可以传递数值，也可以传递向量。因此使用np.logdef entropy(p): return -p * np.log(p) - (1-p) * np.log(1-p) # linspace生成向量x，从0到1均匀取值，绘制出x在不同值时对应的信息熵x = np.linspace(0.01,0.99,100)
plt.plot(x,entropy(x))plt.show()
形似抛物线，以0.5为对称轴。当x=0.5时，曲线取到最大值，也就是说对于信息熵来说，只有两个类别，其中一个类别是0.5，另一个类别是1-0.5时，此时信息熵是最大的，也就是最不确定的。如果x偏向于某一类，确定性变高了，信息熵变低了。
0x02 条件熵
2.1 条件熵的定义
设有随机变量。条件熵表示在已知随机变量的条件下随机变量的不确定性。
随机变量给定的条件下随机变量的条件熵定义为给定条件下，的条件概率分布的熵对的数学期望:
其中，
注意，与信息熵不同的是，条件熵是数学期望，而不是变量的不确定性。
2.2 信息熵和条件熵的区别
下面通过一个例子来讲一下信息熵和条件熵的区别。
在上面这棵“相亲决策树”中，对于结果（叶子结点），有随机变量Y={见,不见}。我们可以统计出，见的个数占2/6=1/3；不见的个数占4/6=2/3。那么变量Y的熵，可以根据公式计算得到： 。
对于条件熵来说，我们还需要增加一个变量X，假设是年龄这一特征。那么在年龄<=30的情况下，有五种结果，见的个数占2/5；不见的个数占3/5。在年龄大于30的情况下，只有一种结果，见为0，不见为1.
那么此时，可以得到如下的式子：
然后我们终于可以计算条件熵：
随机变量给定的条件下随机变量的条件熵定义为给定条件下，的条件概率分布的熵对的数学期望:
其中，
现在计算已知年龄的条件下的条件熵，以30为界有两种情况，然后将上述结果带入公式中，求得期望。
其实条件熵意思是按一个新的变量的每个值对原变量进行分类，比如上面这个题把“见与不见”按“年龄”分成了两类。
然后在每一个小类里面，都计算一个小熵，然后每一个小熵乘以各个类别的概率，然后求和。
所谓小类，就是不包含当前所选特征的其他维度，即当前的特征是给定的条件，在其他维度下求熵，是条件下的。各类别的概率，是当前这个小类别（年龄>30）下的样本量除以总的样本量。
我们用另一个变量对原变量分类后，原变量的不确定性就会减小了，因为新增了Y的信息，可以感受一下。不确定程度减少了多少就是信息的增益。
0x03 信息增益
3.1 什么是信息熵增益
在划分数据集前后信息发生的变化称为信息增益，获得信息增益最高的特征就是最好的选择。
信息增益就是：
以某特征划分数据集前后的熵的差值
划分前，样本集合D的熵（也称经验熵）是为H(D)；使用某个特征A划分数据集D，计算划分后的数据子集（给定特征A的情况下，数据集D）的条件熵（经验条件熵）H(D|A)。则公式为：
在计算过程中，使用所有特征划分数据集D，得到多个特征划分数据集D的信息增益（列表）。从这些信息增益中选择最大的，因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。
3.2 信息熵增益的使用
通过对信息增益的进一步理解，我们发现：对于待划分的数据集D，其经验熵H(D)是不变的，但是划分之后得到的条件熵H(D|A)是变化的（特征A的选择不同）。
条件熵H(D|A)越小，说明使用此特征划分得到的子集的不确定性越小（也就是纯度越高），因为得到的信息增益就越大。说明在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集D。
信息增益偏向取值较多的特征。
原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较偏向取值较多的特征。
0x04 信息增益率
4.1 为什么需要信息增益率
我们已经知道，选取信息增益大的特征，可以得到更好的划分。那么为什么要用信息增益比呢？信息增益比优于信息增益的地方在哪呢？
这是因为，信息增益偏向于选择取值较多的特征，容易过拟合。
假设在信用卡逾期风险预测场景中，有如下数据：
信用级别 | 工资级别 | 是否逾期 |
|---|---|---|
1 | 1 | 是 |
2 | 1 | 否 |
3 | 2 | 是 |
4 | 2 | 否 |
那么此时我们分别计算“信用级别”和“工资级别”条件下“预期”的条件熵。
A = H(是否逾期|信用级别)= p(信用等级=1)H(是否逾期|信用等级=1) p(信用等级=2)H(是否逾期|信用等级=2) p(信用等级=3)H(是否逾期|信用等级=3) p(信用等级=4)H(是否逾期|信用等级=4)=0
B = H(是否逾期|工资级别)= p(工资级别=1)H(是否逾期|工资级别=1) p(工资级别=2)H(是否逾期|工资级别=2)
很显然 B > A，也就是说，对于增益信息：g(D|信用级别) > g(D|工资级别)。很明显，信息增益偏向于选择取值较多的特征，但是根据熵的公式可知，特征越多，熵越大。
那么有什么办法呢？是在信息增益的基础之上乘上一个惩罚参数，对树分支过多的情况进行惩罚，抵消了特征变量的复杂程度，避免了过拟合的存在。
4.2 信息增益率的定义
特征A对训练数据集D的信息增益比定义为：其信息增益g(D,A)与训练数据集D关于特征A的值的熵HA(D)之比，即：
注意，其中的HA(D)是：对于样本集合D，将当前特征A作为随机变量（取值是特征A的各个特征值），求得的经验熵。（之前是把集合类别（年龄、长相）作为随机变量，现在把某个特征作为随机变量，按照此特征的特征取值对集合D进行划分，计算熵HA(D)）
其中，$H_A(D)=−sum_i=1}^n frac {D_i|D|logfracD_i|D|$，n是特征AA取值的个数。注意区别H(D|A)和HA(D)。
信息增益比本质：是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。
信息增益比 = 惩罚参数 * 信息增益
所谓惩罚参数，是数据集D以特征A作为随机变量的熵的倒数，即：将特征A取值相同的样本划分到同一个子集中（之前所说数据集的熵是依据类别进行划分的）。
信息增益比的缺点是：偏向取值较少的特征。原因：当特征取值较少时HA(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。
基于以上特点，在使用增益信息比时，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。
0x05 基尼系数
5.1 基尼系数的定义
基尼系数（Gini），也被称为基尼不纯度，表示在样本集合中一个随机选中的样本被分错的概率。
Gini系数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，基尼指数集合越不纯。
即：基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率
有如下公式：
对上述公式进行说明：
- 表示选中的样本属于k类别的概率，则这个样本被分错的概率是
- 因为样本集合中有k个类别，一个随机选中的样本可以属于这k个类别中的任意一个，因而累加所有的k个类别。
- 当二分类时，
样本集合D的基尼系数：假设集合中有K个类别，每个类别的概率是，其中表示类别k的样本个数，表示样本总数，则：
5.2 特征A划分样本集合D之后的基尼指数
一般来说，我们在使用中，用某个特征划分样本集合只有两个集合（CART）：
- 等于给定的特征值的样本集合D1
- 不等于给定的特征值的样本集合D2
这样就可以对拥有多个取值的特征的二值处理。
举个例子：
假设现在有特征 “学历”，此特征有三个特征取值：“本科”，“硕士”， “博士”，
当使用“学历”这个特征对样本集合D进行划分时，划分值分别有三个，因而有三种划分的可能集合，划分后的子集如下：
- 划分点：“本科”，划分后的子集合 ：{本科}，{硕士，博士}
- 划分点：“硕士”，划分后的子集合 ：{硕士}，{本科，博士}
- 划分点：“硕士”，划分后的子集合 ：{博士}，{本科，硕士}
对于上述的每一种划分，都可以计算出基于划分特征=某个特征值将样本集合D划分为两个子集的纯度：
因而对于一个具有多个取值（超过2个）的特征，需要计算以每一个取值作为划分点，对样本D划分之后子集的纯度Gini(D,Ai)，(其中Ai表示特征A的可能取值)。然后从所有的可能划分的Gini(D,Ai)中找出Gini指数最小的划分，这个划分的划分点，便是使用特征A对样本集合D进行划分的最佳划分点。
0xFF 总结
本篇介绍了一系列的概念：信息熵、条件熵、信息增益、信息增益率、基尼系数等。虽然没怎么介绍算法，但是这些前置概念是必须的。
这篇文章的标题是《决策树的特征选择》，特征选择也就是选择最优划分属性，从当前数据的特征中选择一个特征作为当前节点的划分标准。我们希望在不断划分的过程中，决策树的分支节点所包含的样本尽可能属于同一类，即节点的“纯度”越来越高。
而选择最优划分特征的标准（上面介绍的这些概念）不同，也导致了决策树算法的不同。
