[机器学习]决策树(decision tree)--6.基尼指数

上一篇文章我们介绍了增益率，本文介绍基尼指数(Gini index)。

CART决策树使用基尼指数来选择划分属性。

CART是Classification and Regression Tree的简称，这是一种著名的决策树学习算法，分类和回归任务都可用。

分类树：基尼指数最小准则。

回归树：平方误差最小准则。

数据集D的纯度可用基尼值来度量： $Gini(D)=1-\sum_{k=1}^K p_{k}^2$ 。

属性a的基尼指数定义为： $Giniindex(D,a)=\sum_{v=1}^V \frac{\vert D^v \vert }{\vert D \vert } Gini(D^v )$ 。

如何理解上面的公式呢？我们简单举个例子：

样例数据

$Gini(D,工资)=\frac{3}{8} *(1-(\frac{3}{3} )^2-(\frac{0}{3} ) ^2 )+\frac{5}{8} *(1-(\frac{3}{5} ) ^ 2 - (\frac{2}{5} ) ^ 2) = 0.3$

简单解释下为啥要这样算。

首先工资有两个取值，分别是0和1。当工资=1时，有3个样本。

所以： $\frac{\vert D^v \vert }{\vert D \vert } = \frac{3}{8}$ 。

同时，在这三个样本中，工作都是好。

所以： $Gini(D^v )=1-(\frac{3}{3} )^2-(\frac{0}{3} ) ^2$ 。

就有了加号左边的式子： $\frac{3}{8} *(1-(\frac{3}{3} )^2-(\frac{0}{3} ) ^2 )$

同理，当工资=0时，有5个样本，在这五个样本中，工作有3个是不好，2个是好。

就有了加号右边的式子： $\frac{5}{8} *(1-(\frac{3}{5} ) ^ 2 - (\frac{2}{5} ) ^ 2)$ 。

同理，可得压力的基尼指数如下：

$Gini(D,压力)=\frac{3}{8} *(1-(\frac{2}{3} )^2-(\frac{1}{3} ) ^2 )+\frac{5}{8} *(1-(\frac{1}{5} ) ^ 2 - (\frac{4}{5} ) ^ 2) = 0.37$

平台的基尼指数如下：

$Gini(D,平台 = 0 )=\frac{3}{8} *(1-(\frac{3}{3} )^2-(\frac{0}{3} ) ^2 )+\frac{5}{8} *(1-(\frac{3}{5} ) ^ 2 - (\frac{2}{5} ) ^ 2) = 0.3$

$Gini(D,平台 = 1 )=\frac{3}{8} *(1-(\frac{2}{3} )^2-(\frac{1 }{3} ) ^2 )+\frac{5}{8} *(1-(\frac{4}{5} ) ^ 2 - (\frac{1}{5} ) ^ 2) = 0.37$

$Gini(D,平台 = 2 )=\frac{2}{8} *(1-(\frac{1}{2} )^2-(\frac{1}{2} ) ^2 )+\frac{6}{8} *(1-(\frac{4 }{6} ) ^ 2 - (\frac{2}{6} ) ^ 2) = 0.46$

注意啦，在计算时，工资和平台的计算方式有明显的不同。因为工资只有两个取值0和1，而平台有三个取值0,1,2。所以在计算时，需要将平台的每一个取值都单独进行计算。比如：当平台=0时，将数据集分为两部分，第一部分是平台=0，第二部分是平台<>0。

根据基尼指数最小准则，我们优先选择工资或者平台=0作为D的第一特征。

我们选择工资作为第一特征，那么当工资=1时，工作=好，无需继续划分。当工资=0时，需要继续划分。

当工资=0时，继续计算基尼指数：

$Gini(D_{0} ,压力)=\frac{3}{5} *(1-(\frac{2}{3} )^2-(\frac{1}{3} ) ^2 )+\frac{2}{5} *(1-(\frac{2}{2} ) ^ 2 - (\frac{0}{2} ) ^ 2) = 0.27$

$Gini(D_{0} ,平台 = 0 )=\frac{2}{5} *(1-(\frac{2}{2} )^2-(\frac{0}{2} ) ^2 )+\frac{3}{5} *(1-(\frac{3}{3} ) ^ 2 - (\frac{0}{3} ) ^ 2) = 0$

$Gini(D_{0} ,平台 = 1 )=\frac{2}{5} *(1-(\frac{2}{2} )^2-(\frac{0}{2} ) ^2 )+\frac{3}{5} *(1-(\frac{2}{3} ) ^ 2 - (\frac{1}{3} ) ^ 2) = 0.27$

$Gini(D_{0} ,平台 = 2 )=\frac{1 }{5} *(1-(\frac{1}{1} )^2-(\frac{0}{1} ) ^2 )+\frac{4}{5} *(1-(\frac{2}{4} ) ^ 2 - (\frac{2}{4 } ) ^ 2) = 0.4$

当平台=0时，基尼指数=0，可以优先选择。

同时，当平台=0时，工作都是好，无需继续划分，当平台=1,2时，工作都是不好，也无需继续划分。直接把1,2放到树的一个结点就可以。

最后需要注意的是，CART算法构建的决策树是二叉树。至于为什么是二叉树，我们后面会继续介绍。