• 作者：韩信子@ShowMeAI
• 教程地址：www.showmeai.tech/tutorials/3…
• 本文地址：www.showmeai.tech/article-det…
• 声明：版权所有，转载请联系平台与作者并注明出处

引言

决策树（Decision Tree）是机器学习中一种经典的分类与回归算法。在本篇中我们讨论用于分类的决策树的原理知识。决策树模型呈树形结构，在分类问题中，一颗决策树可以视作 if-then 规则的集合。模型具有可读性，分类速度快的特点，在各种实际业务建模过程中广泛使用。

（本篇内容会涉及到不少机器学习基础知识，没有先序知识储备的宝宝可以查看ShowMeAI的文章 图解机器学习 | 机器学习基础知识。

1.决策树算法核心思想

1）决策树结构与核心思想

决策树（Decision tree）是基于已知各种情况（特征取值）的基础上，通过构建树型决策结构来进行分析的一种方式，是常用的有监督的分类算法。

决策树模型（Decision Tree model）模拟人类决策过程。以买衣服为例，一个顾客在商店买裤子，于是有了下面的对话：

决策树是一种预测模型，代表的是对象属性与对象值之间的映射关系。决策树是一种树形结构，其中：

• 每个内部结点表示一个属性的测试
• 每个分支表示一个测试输出
• 每个叶结点代表一种类别

如上图买衣服的例子，第一个「内部结点」对应于属性「材料」上的测试，两个分支分别是该属性取值为「牛仔」和「非牛仔」两种可能结果。当取值为「牛仔」时，则对下个属性「裤型」进行测试；若取值为「非牛仔」时，则对应于「叶结点」——「不买」。

决策树模型核心是下面几部分：

• 结点和有向边组成。
• 结点有内部结点和叶结点俩种类型。
• 内部结点表示一个特征，叶结点表示一个类。

2）决策树的发展史

决策树在发展过程中，有过很多不同类型的模型，典型的模型如ID3、C4.5和CART等，下面我们来简单介绍一下发展史中不同的模型。

2.决策树生长与最优属性的选择

上面介绍的决策树发展史里，大家对于不同的决策树模型有一个基础的理解了，下面一部分，我们来一起看一下决策树是如何生长构成的。

1）决策树生长流程

决策树的决策过程就是从根结点开始，测试待分类项中对应的特征属性，并按照其值选择输出分支，直到叶子结点，将叶子结点的存放的类别作为决策结果。简单说来，决策树的总体流程是自根至叶的递归过程，在每个中间结点寻找一个「划分」（split or test）属性。

如下图的伪代码，是详细的决策树生长（构建）流程。大家可以特别注意图中3类终止条件和返回的结果，而整个流程中，有非常核心的一步是「最优划分属性的选择」。

决策树停止生长的三个条件：

2）最优属性选择

下面我们来看看，决策树的最优划分属性选择，是怎么做的。

（1）信息熵

要了解决策树的「最优属性」选择，我们需要先了解一个信息论的概念「信息熵（entropy）」（相关知识可以参考ShowMeAI文章 图解AI数学基础 | 信息论），它是消除不确定性所需信息量的度量，也是未知事件可能含有的信息量，可以度量样本集合「纯度」。

对应到机器学习中，假定当前数据集$D$中有$y$类，其中第k类样本占比为$p_{k}$，则信息熵的计算公式如下：