2.2.1　基尼不纯度、基尼增益与基尼指数

训练决策树模型包括迭代地将当前数据分成两个分支。如何分割以及如何定量评估分割的优劣是待解决的核心问题。

假设有如下的两类数据点，分别用正方形和圆形表示，其分布如图2.2所示。可以看到，图中有5个正方形点和5个圆形点。如果以直线x=2为分界线对其进行分割，如图2.3所示，则可获得一个完美的分割。它将这个数据集完美地分割成两个子区域（分支），左边是5个正方形点，右边是5个圆形点。

图2.1　分类与回归示意图

图2.2　数据点示例图

但是，如果以直线x=1.5进行分割呢？这将导致如图2.4所示的不完美分割。左边是4个正方形点，右边是1个正方形点加上5个圆形点。很明显，这种分割是存在问题的，但是怎么量化呢？

图2.3　数据点完美分割示例图（以x=2为分界线）

图2.4　数据点不完美分割示例图（以x=1.5为分界线）

更进一步，如果再添加一类三角形点，那么如何衡量分割质量就变得更加重要了。想象一下如下两种分割：

●分割方案1：分支1包含3个正方形点、1个圆形点和1个三角形点，分支2包含3个圆形点和2个三角形点，如图2.5所示。

●分割方案2：分支1包含3个正方形点、1个圆形点和2个三角形点，分支2包含3个圆形点和1个三角形点，如图2.6所示。

图2.5　分割方案1

图2.6　分割方案2

哪种分割方式更好呢？这已经不是一目了然的事情了，我们需要一种方法来量化评估分割的好坏。

CART算法使用基尼不纯度（Gini impurity）来量化评估分割的好坏。假设在数据集中随机选取一个数据点，并根据数据集的类分布随机指定其分类归属。对于上述的数据集，我们会将其分类为正方形点和圆形点的概率均为0.5，因为每种形状均有5个数据点。那么，我们对数据点进行错误分类的概率是多少？这个问题的答案就是基尼不纯度。

示例1：整个数据集

首先计算整个数据集的基尼不纯度。如果我们随机选择一个数据点，它要么是正方形点（50%），要么是圆形点（50%）。

现在，我们根据类分布对数据点进行随机分类。由于每种形状都有5个数据点，所以有50%的概率将其分类为正方形，有50%的概率将其分类为圆形。我们将数据点错误分类的概率是多少呢？

如表2.1所示，上述所有事件中包含两次错误的分类，因此，错误分类的总概率为25%+25%=50%。

表2.1　数据点分类正误概率表

下面定义基尼不纯度的计算公式。假设有C个类，从类i中提取数据点的概率为p（i），记为p（i），i∈{1，2，3，…，C}，那么基尼不纯度的计算公式如下：

需要指出的是，基尼不纯度与基尼系数和基尼指数并不是一个概念。在经济学中，基尼系数（Gini coefficient）是一种统计学上的分散度，旨在表示一个国家或任何人群中的收入不平等或财富不平等情况。基尼系数是由意大利统计学家和社会学家Corrado Gini开发的，用于衡量频率分布值（例如收入水平）之间的不均衡性。基尼系数为0表示完全均衡，所有值都相同（例如，每个人的收入都相同）。基尼系数为1（或100%）表示完全不均衡（例如，对于许多人来说，只有一个人拥有所有的收入或消费，而其他人都没有收入或消费，那么基尼系数将为1）。我们稍后再介绍基尼指数。

回到上面的例子，我们有C=2，p（1）=p（2）=0.5，所以，

G=p（1）（1-p（1））+p（2）（1-p（2））

=0.5×（1-0.5）+0.5×（1-0.5）

=0.5

图2.7　数据点完美分割示例图

这与我们前面计算的错误分类总概率值是一致的。

示例2：完美分割

对于前面的完美分割，如图2.7所示，分割后两个分支的基尼不纯度分别是多少呢？

图2.7的左边是5个正方形点，所以它的基尼不纯度为

G_left=1×（1-1）+0×（1-0）=0

图2.7的右边是5个圆形点，所以它的基尼不纯度为

G_right=0×（1-0）+1×（1-1）=0

两个分支的不纯度都为0！完美分割把一个不纯度为0.5的数据集变成了两个不纯度为0的分支。基尼不纯度为0是最低的不纯度，只有当所有的东西都是同一类的时候才能实现（比如只有正方形点或只有圆形点）。

图2.8　数据点不完美分割示例图

示例3：不完美的分割

最后，我们计算不完美分割情况的基尼不纯度，如图2.8所示。

图2.8左边的分支全部为正方形点，因此，它的基尼不纯度为

G_left=0

图2.8右边的分支有1个正方形点和5个圆形点，所以，

如何量化评估分割的质量呢？以上述两种形状数据点分割的情况为例，整个数据集在未分割之前，其基尼不纯度为0.5。如果按示例3所示的分割，则左分支的基尼不纯度为0，右分支的基尼不纯度为0.278。而且，左分支有4个数据点，右分支有6个数据点。我们对每个分支的不纯度进行加权，以分支拥有的数据点数量作为权重，计算出分割以后整个数据集的基尼不纯度：

（0.4×0）+（0.6×0.278）≈0.167

因此，我们这次拆分所“去除”的不纯度是

0.5-0.167=0.333

我们把这个值叫作基尼增益（Gini gain）。对于一个样本数据集D，假设有属性A，它的取值为a_i，i∈{1，2，…，n}，初始的基尼不纯度为G（D）。则根据属性A的值a_i进行划分时，形成两个子集合D₁和D₂，其中D₁={v∈D|v_A=a_i}，D₂={v∈D|v_A=a_i}，则基尼不纯度G（D₁）和G（D₂）分别根据子集合D₁和D₂里的样本情况进行计算。集合D、D₁和D₂中的样本数量分别用|D|、|D₁|和|D₂|表示，则根据属性A的值a_i进行划分时，所获得的基尼增益的计算公式如下：

在针对节点进行属性和分割点的选择时，面对的是同一个数据集合D，这个集合可能是最初的完整数据集合，也可能是经过分割后形成的子集合。但无论哪种情况，G（D）都是相同的，因此可以对基尼增益的计算公式进行变换，得到基尼指数（Gini index），它的计算公式如下：

因此，更高的基尼增益等价于更好的分割，更低的基尼指数等价于更好的分割。

这就是CART决策树中用来挑选最佳分割的度量。例如，很容易验证，在上述数据集上，完美分割的基尼增益为0.5而基尼指数为0，不完美分割的基尼增益为0.333而基尼指数为0.167，因此完美分割更好。在训练决策树时，可通过最大化基尼增益或最小化基尼指数来选择最佳分割。