1-2 决策树节点划分时的特征选择依据

依据不同的决策树算法，在划分子节点时进行特征选择的依据有信息增益、信息增益比（又称信息增益率）、基尼系数三种。依次阐述如下：

0. 什么是信息熵？

如果没有学过信息论等与信息理论相关的书，初看信息熵是会有点懵逼的。在机器学习领域，信息熵的定义如下：

信息熵是度量样本集合纯度的一种最常用的指标，假设样本集合D的样本数一共有D个，一共有K类（标签），其中第k类样本所占的比例为pk，则该样本集的信息熵为：

信息熵计算公式

有两点可以加强理解：① 信息熵是一个与类别标签相关，而与特征无关的量；②其实际反映的就是这个样本集中不同类别的样本的占比情况，也就是前面所说的纯度。

如何直观的理解信息熵？可以从熵的最初概念出发，熵是表示体系混乱程度的度量，熵越大自然纯度就越小。

吊诡的地方在哪里呢？在于前面的信息二字，信息熵越大到底代表信息量越大还是信息量越小？如果我们把信息量理解的直观一点，两者是反着的，信息熵越大，能给我们利用的信息就越少。

举个简单的栗子，样本集D有10个人。如果是5个好人5个坏人，信息熵就会大于8个好人2个坏人的情况。

样本分布的越均衡，信息熵越大，信息量越小

为什么呢？因为5:5的比例确实带不来任何信息，假设我们现在就只有这么个样本集，然后来一个新样本，我们判断这个新样本是个好人还是坏人？5:5的样本集告诉我们，有0.5的概率是好人0.5的概率是坏人，也就是跟随机抛硬币一样，无论我们最后给新样本定什么标签，都有50%的错误率。但假设我们的样本集是8:2，其它什么特征都不用，我们可以判断，这个新样本80%的概率是好人，20%的概率是坏人，所以我们应该无脑的把所有人都判断为好人，这样我们预计只有20%的错误率。

这就是信息熵发挥的作用，样本类别越均衡，就是纯度越小，信息熵越大，可用的信息就越少。

1. 信息增益

前面扯了这么多废话把信息熵弄明白，信息增益就简单多了。如果我们按照某个特征的取值，把原始样本集划分为若干个子集，然后用某种方式求一下这些子集的信息熵“之和”，我们希望什么，我们希望划分后的信息熵要减小得尽可能的多，这个信息熵的减小量，就是信息增益。

第一个问题：划分后的子集信息熵之和怎么算？按照信息熵定义，每个子集都能算一个信息熵出来，简单求个和吗？那肯定不行，毕竟还有个样本量的问题，把样本量考虑进去，就相当于给每个子集的信息熵配一个权重，这个权重就是这个子集的样本数占样本总数的比例，然后加权求个和，这就是划分子集后的信息熵求法。

假设按某个特征的取值把原始样本集划分为D1、D2、Dv等若干个子集，划分后的整体信息熵这么求

用原始的信息熵减去上面这个划分后的信息熵，就是信息增益咯。再说一遍，信息增益就是信息熵的减小量。

基于特征a划分样本集后的信息增益求法

补充点废话：信息增益大意味着什么？意味着划分后的样本集们普遍的信息熵较小，也就是纯度较大，纯度较大意味着什么，意味着划分后的各个子集有可能这个子集全是好人，那个子集全是坏人，这不正是我们想要的吗，我们要的恰恰就就是根据特征来有效判断人的好坏，所以选信息增益大的特征进行样本划分也就是理所当然的了。

使用信息增益来划分节点的决策树算法叫ID3算法

2. 信息增益比（率）

信息增益有什么问题？假设我们有两个特征可供选择，性别与年龄，其中性别的取值只有男和女两种，而年龄的取值有18、19、20、...、64、65几十个。这会带来什么问题呢？定性想一下，特征取值越多，划分后的各个子集就会越小，而越小的子集其分布就越有可能偏。还是按前面的栗子来说，10个人按性别划分成5个男人5个女人，而这两个子集里有分别都有好人和坏人，信息增益可能just soso，但如果按年龄分，假设10个人恰好是10个不同的年龄，那划分后每个子集里要么是一个好人要么是一个坏人，纯度杠杠的，信息增益杠杠的。但这是否代表年龄真的是个更好用得特征？并不是，这是因为我们的样本集终究是有限个样本构成的，当特征取值很多时，子集越小，越小就越有可能出现统计学意义上的偏差，从而使其信息增益看起来大。废话了这么多，想说明什么问题呢？就是“依据信息增益划分子集”这个标准会偏爱可取值数多的特征，而这个特征在刻画样本时不一定强。

为了平衡这一点，我们要设法对信息增益做个类似归一化的操作，让不同特征间能有可比性。归一化肯定要考虑特征取值数了，但直接把信息增益除以特征取值数就太简单粗暴了，因此我们再定义一个指标，这个指标称之为特征的固有值，整体上与特征的可取值数会正相关，定义如下：

特征a的固有值

使用特征a的信息增益除以特征a的固有值，就是信息增益比了，使用信息增益比来划分节点的决策树算法叫C4.5算法。

前面说过，信息增益会偏爱取值数较多的特征，那么信息增益比是不是一视同仁了呢？没有，信息增益比会偏爱取值数较少的特征（捂脸哭）。所以最机智的做法应该是设法结合两者。

3. 基尼系数

其实决策树的节点划分这个事儿吧，搞这么多指标出来自然有它的理由，但这些指标说来说去呢，为的都是一件事儿，那就是我们要找到最有用的特征来划分节点。那什么是最有用呢？就是能最有效的区分样本的类别。不管什么指标，本质上度量的都是这个事儿。

基尼系数自然也是如此了，基尼系数反映了从样本集中随机抽取两个样本，其类别标记不一致的概率，原始样本集的基尼系数这么算：

跟信息熵一样，是个与类别有关但与特征无关的量

为毛说基尼系数反映了随机选取的两个样本类别不一致的概率呢？pk是不同类别的样本所占的比例，因此它们的和为1，一堆介于0~1之间的pk的平方和，什么时候最小？当所有的pk相等的时候平方和最小，这个可以用初中数学知识证明。而当每个类别所占的比例都一样的时候，随机抽取的两个样本不一样的概率最大。比如，在5个好人5个坏人里随机抽俩人，这俩人一个是好人一个是坏人的概率还是蛮大的，但如果在9个好人1个坏人里抽俩人，这俩人就有更大概率是两个好人。因此基尼系数度量的也是纯度，由于前面有个1-，基尼系数越大，意味着纯度越小（也意味着信息熵越大）。

理解了基尼系数和信息熵反应的本质是一样的之后，这事就好说了，信息增益是信息熵的减小量，对比想一下这儿就是用划分后基尼系数减小量咯？差不多，但不完全一样，这里是直接用了划分后基尼系数，哪个特征最小就用哪个。为毛呢？因为划分前大家都是一个基尼系数啊，划分后基尼系数最小，可不就是划分后基尼系数减小量最大嘛，所以是一回事。从这个角度来说，前面用信息增益最大也没必要，直接用划分后信息熵最小的那个就行了，效果是一样一样的。

按特征a划分子集后的基尼系数计算方法，跟前面的划分后的信息熵计算方法套用了几乎一毛一样的公式

使用基尼系数划分特征的决策树算法叫CART算法。CART的全称是classify and regression tree（分类和回归树），回归树是什么玩意，以后再说了。

以上就是决策树节点划分时特征选择所用的三个指标。