决策树算法 算法|决策树算法究竟说的是什么？

决策树算法综述

决策树算法，顾名思义，是一种用于分类的树型决策结构。事实上，决策树算法在行业中得到广泛应用，不仅因为它具有良好的分类能力，更重要的是它具有很强的可解释性，直观易懂。事实上，基于决策树的逻辑结构与现实社会环境中人类的决策逻辑非常相似。例如，有一天，郝斌在思考人生中的三个主要问题:

这个思考过程可以简单的用下面的话来表达:

(1)今天是周末吗？如果不是周末，不要去，如果是周末，继续思考下一个问题；

(2)这周的工作完成了吗？如果还没有完成，就不要走，如果已经完成，继续思考下一个问题；

(3)今天是晴天吗？如果不是晴天，就不要去，如果是晴天，继续思考下一个问题；

(4)你今天能在电影院找到一个好位置吗？如果找不到好位置，就不要去了。如果能找到好位置，决定去电影院看电影；

如果思维过程是以决策树的形式表达的，那么它的形式如下:

在这种看电影的决策逻辑中，其实是由郝斌通过自己的历史多次看电影的经历总结出来的。这种形式的决策树算法其实是一种训练数据集，通过一系列的试题(比如“今天是周末吗？”)以输出分类目标进行判断。

决策树的表达形式非常直观，容易理解。一般来说，决策树由一个根节点、几个内部节点和几个叶节点组成。根节点和内部节点代表相应的测试条件，而叶节点代表最终的输出结果:

(1)根节点:根节点位于顶层，代表第一个测试条件。决策树只有一个根节点，根节点有零个或多个输出边。

(2)内部节点:位于根节点之下，代表一个测试条件。中间节点有一个输入边和两个或多个输出边。

(3)叶节点:决策树的终端节点，代表决策树的决策结果。叶节点只有一个传入边，但没有传出边。

可以看出，这种树状表达式实际上可以和前面提到的If-Then规则相互转换，其中从根节点到任意叶节点都会形成一个规则:If“是周末吗？”=“假”，然后“别走。”。值得注意的是，决策树形成的规则应该是互斥且完备的，即对于任何样本数据，只有一个与之对应的规则来输出分类结果。

决策树的生成

在实际应用过程中，我们不仅仅针对一个样本，而是要从大量的数据中找到规律。所以接下来的问题就是如何借助决策树算法总结内在蕴涵逻辑。回想决策树是用测试条件划分属性的方法，所以决策树的生成需要先回答两个问题:

(1)如何选择劈裂的试验条件？

(2)什么情况下可以选择结束分裂？

总的来说，我们分类的目标是希望“一个是一个，一个是两个”。所以我们希望当原始数据集被一个测试条件划分为两个或两个以上的数据集时，划分出来的数据集会更加“纯粹”，即划分后的任何子集都尽可能属于同一类别。

关于子集的“纯度”，我们可以通过下面的例子来理解:

1936年，我们的“渔夫”(R.A.Fisher)提供了虹膜数据集，这可能是机器学习领域最著名的分类数据集。

从鸢尾山和多色鸢尾中提取13个样品，用X(花瓣长度)和Y(萼片宽度)分割。可以看出，两种类型的鸢尾都可以通过花瓣长度完全准确的区分出来，但被萼片宽度分割后仍有混杂的情况。我们可以认为特征x划分的子集纯度更高。

显然，在生成树模型的过程中，我们应该为每个划分选择能够使子集更加纯粹的划分条件。随着数据集的不断划分，我们子集的纯度越来越高，直到这个节点下的样本属于同一个范畴。那么分裂应该在什么时候终止呢？一个直观的答案显然可以是“该节点下的所有样本都属于同一个类别(无需划分)”或者“该节点下的所有样本都具有相同的属性(继续划分并不能提高结果)”。下图显示了决策树的增长过程:

从以上决策树生长的流程图中，我们可以发现决策树的生长重点在于“纯度”计算公式，即如何选择最优的特征过程。接下来，我们将简要介绍不同决策树算法的划分方法。

(1)ID3系列算法:采用信息熵作为集合纯度的评价

假设我们的样本集D包含M个样本，每个样本的比例为

那么集合d的信息熵定义为:

计算时定义0log0=0。

ENT(D)越大，集合D的杂质度越高，越小。ENT(D)越低，集合D的纯度越高。因此，一些文献提到用信息熵来衡量样本集的“不纯”纯度。

信息熵的一个流行介绍可以在文章中找到:

(2)CART算法:采用GINI系数作为采集纯度的评价；

对于集合d，其纯度的相应计算公式为:

其中m是目标变量的类别数。类似于信息熵，基尼指数越低，代表集纯度越高。当节点只包含一个类别时，基尼系数取最小值0。5%.

由于每个算法都有很多内容，本期只简单介绍决策树的概念问题，下一期我们将详细介绍决策树中最经典的ID3系列算法。

注意:由于老坨最近比较忙，有些消息没有及时查看和回复(微信规定48小时内没有回复，不能再回复)，所以如果郝斌老坨没有及时回复，可以再留言。