【理论篇】决策树算法 - 信息增益

连载上一篇文章末尾提到的两个问题：

1）如何选择特征？
2）如何进行特征的切分？

本节我们主要解决第一个问题：如何选择特征。

根节点的选择该用哪个特征呢？接下来呢？如何切分呢？

可以想象一下，根节点好比一个趁手的过滤网，通过根节点切分数据之后，可以很好地将样本初步区分开，即分类效果更好。根节点下面的节点，自然就是分类能力第二的特征了。

那如何评估特征的分类能力呢？

这就须要我们找到一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的那个当成根节点，以此类推。

熵：熵是表示随机变量不确定性的度量。

通俗讲就是物体内部的混乱程度，比如杂货市场里面什么都有，非常混乱，选择购买某类商品（随机变量）的不确定性很大，熵就越高。专卖店只卖一个牌子的商品，商品种类有限，不确定小，熵就越小。

举个栗子：

A 集合：[1,1,1,1,1,1,1,1,1,2] 
B 集合：[1,2,3,4,5,6,7,8,9,10]

上述两个集合，显然 A 集合的熵值要低，因为 A 里面只有两种类别，不确定性小；而 B 中类别太多了，熵值就会大很多。

熵的计算公式：H(X)=- ∑ pi * logpi, i=1,2, ... , n

熵可以帮助我们度量随机变量的不确定性，不确定性越大，得到的熵值也就越大。

那在分类任务中我们希望通过节点分支后数据类别的熵值大还是小呢？当然是越小越好了，数据通过节点分支后，我们希望每个分支的数据越干净越好，这样才能把不同的类别更好的区分开。

那如何决策一个节点的选择呢？我们可以使用数据集原始的熵值减去经过节点分支之后求取的熵，选择差额最大的作为第一个节点。

这个差额我们称之为信息增益，即特征 X 使得类 Y 的不确定性减少的程度。可以理解为分类后的专一性，希望分类后的结果是同类在一起。

有如下数据集：包含 4 个特征，分别是天气、温度、湿度以及是否有风；标签列为 Play 是否出游。

我们将根据该数据集，构造决策树，更具输入的户外情况来预测是否出游。

首先，原始数据集中有 9 天出游，剩下的 5 天不出游，所以原始数据集的熵为：

-9/14*log(9/14) - 5/14*log(5/14) = 0.940

接下来，我们选取根节点，分别计算 4 个特征切分后的熵值。先从 outlook 特征开始：

计算切分后的整体熵值，需要为每个切分后的数据集乘以一个权重参数：

5/14 * 0.971 + 4/14 * 0 + 5/14 * 0.971 = 0.693

上述的权重参数 5/14 4/14 5/14 即统计数据中，outlook 取值分别为 sunny，overcast，rainy 的概率。

经过 outlook 节点切分后，系统的熵值从原始的 0.940 下降到了 0.693 ，信息增益为 0.247。

同样的方式可以计算出其他特征的信息增益：

使用 temperature 切分数据集后的信息增益：

gain(temperature) = 0.029

使用 humidity 切分数据集：

使用 humidity 切分数据集后的信息增益：

gain(humidity)=0.152

使用 windy 切分数据集：

使用 windy 切分数据集后的信息增益：

gain(windy)=0.048

最后，我们选择信息增益最大的特征就可以了，相当于是遍历了一遍特征，找出来了根节点，然后再其余的特征中继续通过信息增益找接下来的分支节点。

使用信息增益作为衡量标准的决策树算法又称为 ID3 。但 ID3 算法对于分布稀疏的特征是存在问题的，具体是什么问题呢？

我们下节见~(*￣︶￣)

最后编辑于：2022.01.05 14:52:56