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，因此完美分割更好。在訓練決策樹時，可通過最大化基尼增益或最小化基尼指數來選擇最佳分割。