【十分钟 机器学习 系列课程】 讲义（二十六）：CART算法-基尼指数

欢迎回来。从本节开始将详细讲解生成决策树的CART算法，这个方法我们之前在讲【十分钟 机器学习 系列课程】 讲义（二十五）：决策树的后剪枝EBP和CCP代价复杂度剪枝时都有提到过，那么咱们今天就一起系统地学习一下吧。

壹 CART算法简介

CART算法是机器学习十大算法之一，要说到这个方法的创始人，在咱们之前的“基尼指数”在机器学习中的奥秘专门介绍到了Leo Breiman 的经历故事，感兴趣的小伙伴可以点击回看。

好啦，言归正传。

「CART算法包括三步走：选择特征、生成决策树、剪枝」。

1.名称解读

CART算法展开就是「Classification and Regression Tree」，对应的就是分类与回归树，在这里就是用树形结构来解决分类和回归的问题。

❝

• 如果输出变量是「离散」的，对应的就是「分类」问题。
• 如果输出变量是「连续」的，对应的就是「回归」问题。

❞

2.二叉树和多叉树的关系

在CART算法中，树形结构是二叉树模型，那么二叉树和多叉树有什么区别吗？举个栗子。

对于「纹理」这个特征而言，可以分为「清晰、稍模糊、模糊」三叉，但是如果把这个三叉树改成二叉树，就可以写成「清晰和不清晰」，接着在「不清晰」中，再分为「模糊和稍模糊」啦。

也就意味着把复杂的问题用简单的「yes or no」来表示出来，通常左边为「是」，右边为「否」。

贰 特征选择-基尼指数

要想生成一棵决策树，首先应该选择最优特征。

在之前的讲义中【十分钟 机器学习 系列课程】 讲义（二十一）：决策树的生成，「ID3算法通过信息增益求特征、C4.5通过信息增益比求特征」，而在CART算法中，是通过基尼指数来选择最优特征的。

那么基尼指数在经济学和机器学习中的区别是什么呢？在之前的两篇推文中专门有过详细的介绍哦。“基尼指数”在经济学中的奥秘 “基尼指数”在机器学习中的奥秘

这里咱们继续回到CART算法中的基尼指数。

❝

假设有 个类，样本点属于第 类的概率为 ，概率分布的基尼指数定义为：

❞

显然，这就是样本点「被错分的概率期望」。如果整个样本集只有一个类别，那么基尼指数就是0，表示样本集纯度达到最高值。反正总共就一个类，那么任意抽取一个样本，自然就知道它的归属类别啦。

那么这个基尼指数有啥特点呢？我们来好好欣赏一下这个公式。

对于二类分类问题

对于二类分类问题来说，如果样本点属于第一类的概率是 ，那么显而易见第二类的概率就是 啦，代入到这个公式里就是：

如果对给定的样本集合 ，可以分为两个子集 和 ：

其中， 就是 的经验值。

之所以单独把二分类的情况列出来，是因为在提出基尼指数的CART算法中用的就是这个，毕竟CART算法生成的是二叉决策树。但其实基尼指数完全可以用到多分类问题中，请跟我一起往下看。

对于多类分类问题

对于多分类问题，如果对给定的样本集合 ，可以分为 个子集： ， ， ， ，其基尼指数为

其中， 就是 的经验值。

叁 例题讲解

接着咱们就来一起「用基尼指数的最小化来选出最优特征」。

❝

对于特征A条件下，样本集D的基尼指数为：

❞

注意哦，这里就是选定了特征A，并且将数据集中按照特征分成了两个数据集，再分别求它们对应的基尼指数。

我们拿水蜜桃来举个栗子。一共10个桃子，其中5个好吃，5个不好吃。

那么我们可以计算出整个数据集的基尼指数：

「分类」：好吃和不好吃，两种。

Case 1 选择甜度特征，按照阈值0.2分成两组。

假设，甜度大于0.2的有6个桃子，其中5个好吃，1个不好吃，甜度小于等于0.2的有4个桃子，都不好吃，那么我们就可以列出这样一个二叉树。瞧，数据集就被分成了 和 两个。这里我们把甜度特征标记为 。

接着我们就来计算甜度特征下的基尼指数吧。

计算 数据集的基尼指数

接着计算 占比的权重为：

计算 数据集的基尼指数

接着计算 占比的权重为：

计算甜度特征下的基尼指数

Case 2 选择硬度特征，按照软硬分成两组。

假设，有5个硬桃子，其中2个好吃，3个不好吃，5个软桃子中，有3个好吃，2个不好吃。那么继续列出一个二叉树，这里我们把硬度特征标记为 。

计算 数据集的基尼指数

接着计算 占比的权重为：

计算 数据集的基尼指数

接着计算 占比的权重为：

计算甜度特征下的基尼指数

通过比较可以看出：

意味着：

❝

按照甜度分类时，分类的「确定性」更胜一筹，那么就可以用这个特征作为最优特征。

❞

好啦，这就是用基尼指数来找到最优特征的方法，通过对数据集中不同特征进行基尼指数的遍历计算，就能得出最小时对应的特征，这就完成了「CART算法」中的第一步。

下期我们继续给大家介绍后面的二步走哦。请喜欢讲义的小伙伴记得「转发+点赞+在看」，下期不见不散。感兴趣的小伙伴也可以看视频链接继续学习~祝大家周末愉快。