信息熵、信息增益以及决策树
信息熵是信息论的范畴，利用概率论和统计的方法，因此信息熵也被称为基于概率分布的信息熵。在介绍信息熵概念之前，先介绍一个基本的概念：区分能力。所谓区分能力是指把对象划分到具体分组的能力，比如金庸武侠小说里的英雄人物，每一个武侠人物都是性别、智商、情商、侠义、个性5个属性，如何根据这个5个属性来区分不同的武侠人物。如果某个属性可以将被测试的人物尽可能分到相应的组，那么可以认为这个问题的区分能力强。
我们看性别和智商两个属性。
图片来源：极客时间程序员的数学基础课
我们看性别属性，可以将人群大致等分，智商属性将人群8/2 分，因此智商属性的区分能力要低于性别。
如何用两个科学的指标来度量区分能力，这就要引入信息熵和信息增益的概念。
信息熵是用来描述集合纯净度的，举个简单的例子，如果某个集合里面只有一种类型的元素，全部元素属于同一个分组，我们说这个集合是纯净的，熵为0，如果集合中的元素属于不同的分组，那集合是不纯净的，熵大于0。即熵值越大，集合越不纯净。熵的计算公式如下所示。
其中n是集合中分组的数量 pi表示第i个分组的元素在集合中出现的概率。
我们可以举几个简单的例子来理解信息熵。
假设我们有一个集合，里面只有一种类型的元素A，如下图所示。
那么集合中分组的数量为1，集合中的元素属于分组A的概率为1，那么该集合的信息熵=-100%*log(100%)=0
我们来看另外一个集合，这个集合里面包含两种类型的元素A和B，各占一半，如下图所示。
图片来源程序员的数学基础课
那个这个集合的熵=-50%*log(50%)-50%log(50%)=1，高于刚才那个集合的熵。
从上面的例子可知，集合中包含的元素越多，分布的越均匀，集合的熵值越大，或者说越混乱，熵值反映了集合的纯净度。
我们计算了一个集合的熵，那么把集合划分成多个子集合后如何计算整体的熵呢？
T表示某个划分（按照某个属性划分集合），Pv表示划分后某个小集合，Pv/P表示小集合出现的概率，Entropy(Pv)表示小集合的熵。由公式可知，集合划分成多个小集合的整体熵值等于各个小集合熵值的加权平均。
我们仍然举一个简单的例子来说明，如下图所示。
图片来源极客时间程序员的数学基础课
根据之前的介绍，A、B、C三种类型组成的元素的整体集合的熵值为1.58，我们对集合进行某种划分，分成两个集合，一个集合只有C，熵值为0，一个集合包含A、B两种元素，熵值为1，那么划分之后的整体熵值为2/3*1+1/3*0=0.67。
T表示当前选择的特征
Gain(P,T）是两个熵值的差值，差值越大，信息增益越大，越应该选择这个特征。
决策树属于归纳推理算法，适用于分类问题。我们可以先看一个决策树分类的例子。根据属性来划分分类。
图片来源极客时间程序员的数学基础课
决策树的模型构建出来就是一个树形结构，这个是决策树名字的由来。决策树的构建就利用到了信息熵和信息增益的概念了，其构建过程为。
-
根据集合中样本的分类，计算集合的熵，然后根据每个集合熵值的加权平均计算整体的熵值，注意一开始集合只有一个，并且包含所有样本
-
根据信息增益，计算每个特征的区分能力，选择区分能力最强的特征对集合进行细分
-
有了新的划分之后，重复第1步和第2步
训练数据集P，经过特征T划分成n个子集合，Pi表示第一个子集合元素的数量，P表示划分前集合元素的数量。分裂信息的公式与信息熵的公式看着类似，其实是不一样的，信息熵关注的是集合内部，集合数量再多，集合越纯净，熵值越小，而分裂信息是集合越多，分裂信息越大。因此可以使用分裂信息来惩罚取值较多的特征。
信息增益率的计算公式如下所示。
Gain(P,T）表示训练数据集P按照特征T划分后的信息增益，GainRation(P，T)是训练数据集P按照特征T划分后的信息增益率。
另外一种常见的决策树算法为CART，其与ID3以及C4.5算法不同之处主要在于：
-
CART不是采用信息增益或信息增益率，而是采用基尼系数来选择特征
-
ID3以及C4.5根据特征值属性的个数来划分，可能有多个分组，而CART采用了二叉树，每次划分都是分为两个分组
基尼系数也是用来描述集合纯净度的指标，与熵类似，基尼系数的计算公式如下所示。
n表示集合中分类的数量，集合中分类数量越多，基尼系数越大，集合越不纯净
按照特征T划分之后，我们计算整体的基尼系数
m为集合按照特征T划分后子集合的数量，Pj为第j个集合
决策树算法主要基于信息熵、信息增益、信息增益率以及基尼系数，其优势是容易理解和实现，决策树算法的缺点是受训练样本影响较大，比较容易过拟合。在预测阶段，如果新出现的数据与原先的训练样本相差较大，则分类效果会比较差。
针对决策树的缺点，科学家们提出了剪枝和随机森林，以后再做介绍。