决策分析中的决策树法与数据挖掘中的决策树模型

最近本人一直在研究数据分析的思路、手段和方法。其中有一个重要的切入点是我之前一直在使用的决策树。这里将该方法的来龙去脉整体地做个总结阐述。现在我们在网上搜决策树，绝大部分相关资料都是跟决策树演算法相关的。谁让计算机是当今显学，而数据挖掘又是计算机领域中的显学呢？反而该算法的灵感来源，决策分析中的决策树法就不那么明了了。为了区别起见，下文中把决策分析中的决策树方法统一称为决策树法，把数据挖掘中的决策树算法统一叫做决策树算法。这种称呼是约定俗成的，前者是前辈，后者是晚辈，都是借用了决策树模型的思路处理不同问题，之间只有一字之差。

背景：决策分析

决策树的产生和发展，均是在经济管理学领域的“决策分析”（decision analysis）这一理论背景下进行的。决策分析从字面上就很容易理解，就是为做出某种决定而进行数据分析的过程，其目标是帮助人们进行进一步良好决策的工具和方法论。决策分析一般分四个步骤：(1)形成决策问题，包括提出方案和确定目标；(2)判断自然状态及其概率；(3)拟定多个可行方案；(4)评价方案并做出选择。例如，作为一个年近30的北漂，“是该回家发展还是继续漂”就是一个典型的决策问题，为此收集数据，确定回家乡和继续北漂两个方案下各种好处坏处并划定权值和概率，以此进行计算并评价各个方案，就是一个典型的决策分析过程。最终分析结果会对这个北漂做出理性选择提供帮助。

决策分析根据决策问题的是否包含随机因素可分为三大类：确定型决策（不包含随机因素），风险型决策（随机因素的概率是可测定的），不确定型决策（随机因素的概率不可测定）。相关介绍。不同的问题类型在具体处理方法上有很大区别。之前提的北漂青年的决策例子，因为其中的很多因素，例如未来20年的总收入的测算，中间变量太多，很难计算出准确概率，故而该案例是一个典型的不确定型决策。诺贝尔经济学奖丹尼尔•卡尼曾出过一论文集《不确定状况下的判断:启发式和偏差》，就是讲不确定型决策的案例和各种解决方法的，包含大量数学概念，包括对主观评价的量化，有兴趣的童鞋可以一看。因为不确定型决策较为复杂且主观评价原则比重较大，故而，如果可能，就应尽量将随机因素的概率测定出来，把不确定型决策转化为风险型决策来计算，从而获得更为客观的决策依据。从这个角度讲，在可预见的未来，大数据技术及相关基础设施正是变不可控为可控、变不确定型为风险型决策的法宝。风险型决策的常用决策分析技术有期望值法、决策树法、马尔科夫分析方法等等。其中，决策树法是对决策局面的一种图解，最为直观明确，以下重点介绍。

决策分析中的决策树法

决策树（Decision Tree），早在19世纪末，就被西方经济学、数学方面的专家应用于实践。在20世纪30-40年代又有大发展，是现在经济管理学中必修的内容。它本质是一个基于概率与图论思想，获取最优方案的风险型决策方法。这里我做了一个简单的例子来说明：

某学校领导想拉向某公司赞助。但是呢，是否应该先花钱做个案例以便更好地拉赞助，需要作出决策。其中，做案例的成本是1万，公司赞助的金额是10万。根据该投资公司的历年情况估算，在有案例的时候给与赞助的概率是70%，在没有案例仅靠学校名声的情况下给予投资的概率是40%。那么请辅助领导做决策，到底是应该先花钱做个案例呢，还是不做案例。

首先，我们将上面这个问题描述规范化为表格：

决策类型            结果状态             状态 概率      收益

投资做案例         拉到赞助               70%            10W-1W

投资做案例         没拉到赞助            30%            -1W

不做案例             拉到赞助                40%            10W

不做案例             没拉到赞助            60%            0

然后我们就可以根据以上表格画出决策树：

解释一下图中的元素：

□——决策节点（decision node），是对几种可能方案的选择，即最后选择的最佳方案。决策树的根节点都是决策节点。
○——成为选择节点或者叫机会节点(change node)，代表备选方案，通过各状态节点的经济效果的对比，按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出现的自然状态数目。每个分枝上要注明该状态出现的概率（probability）。
△——结果节点或者叫终结节点（terminal node），将每个备选方案在各种自然状态下取得的损益值（payoff）标注于结果节点的右端。决策树的叶节点都是终结节点。

决策树的图解比表格更加清楚明了。而且，决策树也是一种计算模型，从决策树的各个终结节点开始，一层层往上计算概率（probability）和损益值（payoff），从而可以得出每一种决策的实际损益值。这个计算过程称之为回滚计算（rollback），可以得出究竟哪个方案比较好：

如上图所示，通过回滚计算，我们可以得出，做案例的实际损益值是正收入9 * 0.7 + (-1) *0.3 = 6 (W) ， 不做案例的实际损益值10 * 0.4 +0 *0.6 = 4 (W) 。根据计算结果，做案例的计算回报比不做案例的要大，故而用红线标出值得选择的方案。

以上只是一个简单的例子。实际应用场景远远比这复杂，决策树也跟着变得复杂。例如，有多级决策，意味着决策树上不仅有一个方块形的决策节点；有多值决策，损益值不是一个金钱值就能衡量，而是有许多个权重不一值来综合进行考量；更普遍的是带有变量的决策，每个选择状态可能涉及多个变量，而这些变量跟概率值、损益值可能相关；还有马尔科夫决策，中间带有马尔科夫节点，意味着该节点的概率值跟前一个节点有线性相关的关系；有的决策中有逻辑节点，意味着会有当XX变量低于XX值时会做出XX判断之类的转折。总而言之，决策树法是风险型决策分析中一个非常有用、可以研究地很深的领域。既条件明确论证充分的决策树，其结果可以作为论文论据使用。

既然决策树这么有用，自然有很多相关的客户端软件可以让我们用计算机来画决策树并做相关计算。如 PrecisionTree ，treeage等等。

数据挖掘中的决策树算法

请再回顾一下决策树法的使用过程，我将其归纳为三步：规范化，图形化和计算。其中第一步规范化是任何数据分析都绕不开的工作；第二步图形化实际是一个建模过程，决策树法主要依靠人类智慧来进行建模；第三步，计算则通常可以依赖计算机。显然，人们并不以此满足。是否可以使用计算机智能，直接对规范化数据进行建模呢？是否可以把之前简单例子中的规范化表格直接输入计算机，让计算机自己生成图形，然后就把预测结果告诉我们呢？真的可以这么懒嘛？事实是可以的，那就是数据挖掘中的决策树算法。

自20世纪60年代以来，一代一代不断有人工智能、机器学习、数据挖掘、统计分析领域的专家学者改进着决策树演算法，相关论文极多。其基本原理为：通过演算法中所规定的分类条件对于整体数据进行分类，产生一个决策节点，并持续依照演算法规则分类，直到数据无法再分类为止。一言以蔽之，决策树算法是一种递归分类算法。

决策树算法的理念与上文所提到的决策树法如出一辙，但是由于处理的问题不同，所以它们又有很大区别：因为数据挖掘处理的数据对象很多是用户不能完全清楚的数据，有很多不确定性，所以只能使用递归式的决策树生成方法；同时，为了化简算法，决策树算法将节点类型也做了简化：只有叶节点 (Leaf Node)和决策节点 (Decision nodes) 两类（这样有点像当初图灵为什么选择二进制而不是十进制，因为状态越多算法编起来越麻烦）；最后，决策树算法更多地依赖计算机智能来生成决策树模型，虽然通常也需要人类智慧的介入调整一些参数。

决策树演算法依据其分类规则以及可适用分析数据类型的不同，延伸出多种决策树演算法，常用的有如下几类：

1. C5.0

决策树算法领域中，叫CXX的算法有好几个，之间有继承关系，如ID3, C.4.5，C5.0等等，C5.0就是C4.5的最新改进算法。此演算法的分类原理主要是利用资讯衡量标准 (Information Measure) 来构建决策树，并对每一个节点产生不同数目的分支来分割数据，直到数据无法分割为止。C5.0 的目标字段 (Target) 测量级别，不适用于连续类型 (Continuous) 的测量级别。而输入字段的数据型态则适用连续类型 (Continuous) 的测量级别。

2. CHAID (Chi-Square Automatic Interaction Detector)

此演算法和前述的 C5.0 概念很像，均可以在每一个节点产生不同数目的分支来分割数据，用来建立决策树。但是在背后分类的原理则利用卡方分析检定 (Chi-square F test) 来进行分支，通过卡方检定来计算节点中的 P-value，来决定数据是否仍须进行分支。另外，CHAID 的目标字段 (Target) 的测量级别可适用于连续类型 (Continuous) 的测量级别，但在输入字段则只适用分类类型 (Categorical) 的测量级别。

3. QUEST (Quick Unbiased Efficient Statistical Tree)

此演算法是利用统计方法分割数据，即以判定决策树是否仍需进行分支，以建立二元的决策树。QUEST 在变数的数据型态限制上，跟 C5.0 一样，目标字段 (Target) 测量级别，不适用于连续类型 (Continuous) 的测量级别。但在输入字段的测量级别则适用连续类型 (Continuous) 的测量级别。

4. CART Tree (Classification and Regression Tree)

构建决策树的原理是使用 Gini Ratio 作为判定决策树是否仍须进行分支的依据，并建立二叉树型的决策树。此演算法不管是在目标变数 (Target) 以及输入字段的测量级别均适用连续类型 (Continuous) 的测量级别做分析。

-----------------------------------------------------------------------------------

决策树算法的应用

现在决策树算法是每一个专业型数据分析软件的标配。SPSS，SAS，mathlab, Clementine都有， R和python也都有相应实现包。现在我们的问题是，如何在实际层面进行操作？好在这方面的文章和书实在太多。为了实际使用，我们必须首先搞清楚决策树算法的使用场景。

前文提到，决策树算法是一种递归分类算法。分类在数据挖掘中是一项非常重要的任务。简单地说，分类就是把数据库中的一条数据项映射到给定类别中的某个类别。分类可用于预测，预测的目的是从历史数据记录中自动推导出对给定数据的趋势描述。而决策树算法是最知名的分类算法。

在使用决策树演算法进行分析之前，首要工作就是选择适当的决策树算法。一般来说，会根据所要分析数据的特性以及数据型态等选择初步的演算法。接下来再通过比较初步筛选的决策树分析出来的结果，选择最适合的决策树演算法。

之后就是拿选好的决策树算法，通过训练子集构造决策树。如果该树不能对所有给出的训练子集正确分类，那么选择一些其它的训练子集加入到原来的子集中，重复该过程一直到时形成正确的决策集。决策树可以根据属性的取值对一个未知实例集进行分类。使用决策树对实例进行分类的时候，由树根开始对该对象的属性逐渐测试其值，并且顺着分支向下走，直至到达某个叶结点，此叶结点代表的类即为该对象所处的类。生成的决策树规则，是能以二维表的形式保存下来的，如果是SPSS还能以SPSS语法或者SQL语法导出，从而多次利用。以下是一些使用SPSS对具体案例使用决策树算法进行分析的例子：

IBM SPSS Modeler: 银行电话行销数据栏位和特征分析

沈浩老师的博客：多变量分析

总结

相对而言，决策树算法的应用场景更广阔，因为借用了机器智能来进行分类，节省了人的精力，之前说的三类决策分析，只要数据适当，都可以分类预测给你看。决策树法则更简单，常用于经济学、医疗领域的成本分析等一些数据量不大，但更强调准确性和逻辑性的场合。