CICC科普栏目｜什么是决策树？决策是选择or匹配？

由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

分类树（决策树）是一种十分常用的分类方法。他是一种监管学习，所谓监管学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。

组成

□决策点，是对几种可能方案的选择，即最后选择的最佳方案。如果决策属于多级决策，则决策树的中间可以有多个决策点，以决策树根部的决策点为最终决策方案。

○状态节点，代表备选方案的经济效果（期望值），通过各状态节点的经济效果的对比，按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。

△结果节点，将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。 

机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测。

从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。

一个决策树包含三种类型的节点：

1. 决策节点：通常用矩形框来表示

2. 机会节点：通常用圆圈来表示

3. 终结点：通常用三角形来表示

决策树学习也是资料探勘中一个普通的方法。在这里，每个决策树都表述了一种树型结构，它由它的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。 当不能再进行分割或一个单独的类可以被应用于某一分支时，递归过程就完成了。另外，随机森林分类器将许多决策树结合起来以提升分类的正确率。

决策树同时也可以依靠计算条件概率来构造。

决策树如果依靠数学的计算方法可以取得更加理想的效果。 数据库已如下所示：

　　(x, y) = (x1, x2, x3…, xk, y)

相关的变量 Y 表示我们尝试去理解，分类或者更一般化的结果。 其他的变量x1, x2, x3 等则是帮助我们达到目的的变量。

决策树的剪枝

剪枝是决策树停止分支的方法之一，剪枝有分预先剪枝和后剪枝两种。预先剪枝是在树的生长过程中设定一个指标，当达到该指标时就停止生长，这样做容易产生“视界局限”，就是一旦停止分支，使得节点N成为叶节点，就断绝了其后继节点进行“好”的分支操作的任何可能性。不严格的说这些已停止的分支会误导学习算法，导致产生的树不纯度降差最大的地方过分靠近根节点。后剪枝中树首先要充分生长，直到叶节点都有最小的不纯度值为止，因而可以克服“视界局限”。然后对所有相邻的成对叶节点考虑是否消去它们，如果消去能引起令人满意的不纯度增长，那么执行消去，并令它们的公共父节点成为新的叶节点。这种“合并”叶节点的做法和节点分支的过程恰好相反，经过剪枝后叶节点常常会分布在很宽的层次上，树也变得非平衡。后剪枝技术的优点是克服了“视界局限”效应，而且无需保留部分样本用于交叉验证，所以可以充分利用全部训练集的信息。但后剪枝的计算量代价比预剪枝方法大得多，特别是在大样本集中，不过对于小样本的情况，后剪枝方法还是优于预剪枝方法的。

优点

决策树易于理解和实现，人们在在学习过程中不需要使用者了解很多的背景知识，这同时是它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的意义。

对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

易于通过静态测试来对模型进行评测，可以测定模型可信度；如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。 

缺点

1)对连续性的字段比较难预测。

2)对有时间顺序的数据，需要很多预处理的工作。

3)当类别太多时，错误可能就会增加的比较快。

4)一般的算法分类的时候，只是根据一个字段来分类。 

算法

C4.5

C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：

1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；

2) 在树构造过程中进行剪枝；

3) 能够完成对连续属性的离散化处理；

4) 能够对不完整数据进行处理。

C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

具体算法步骤如下；

1创建节点N

2如果训练集为空，在返回节点N标记为Failure

3如果训练集中的所有记录都属于同一个类别，则以该类别标记节点N

4如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类；

5for each 候选属性 attribute_list

6if 候选属性是连续的then

7对该属性进行离散化

8选择候选属性attribute_list中具有最高信息增益率的属性D

9标记节点N为属性D

10for each 属性D的一致值d

11由节点N长出一个条件为D=d的分支

12设s是训练集中D=d的训练样本的集合

13if s为空

14加上一个树叶，标记为训练集中最普通的类

15else加上一个有C4.5（R - {D},C，s）返回的点

CART

背景：

分类与回归树(CART——Classification And Regression Tree)) 是一种非常有趣并且十分有效的非参数分类和回归方法。它通过构建二叉树达到预测目的。

分类与回归树CART 模型最早由Breiman 等人提出，已经在统计领域和数据挖掘技术中普遍使用。它采用与传统统计学完全不同的方式构建预测准则，它是以二叉树的形式给出，易于理解、使用和解释。由CART 模型构建的预测树在很多情况下比常用的统计方法构建的代数学预测准则更加准确，且数据越复杂、变量越多，算法的优越性就越显著。模型的关键是预测准则的构建，准确的。

定义：

分类和回归首先利用已知的多变量数据构建预测准则, 进而根据其它变量值对一个变量进行预测。在分类中, 人们往往先对某一客体进行各种测量, 然后利用一定的分类准则确定该客体归属那一类。例如, 给定某一化石的鉴定特征, 预测该化石属那一科、那一属, 甚至那一种。另外一个例子是, 已知某一地区的地质和物化探信息, 预测该区是否有矿。回归则与分类不同, 它被用来预测客体的某一数值, 而不是客体的归类。例如, 给定某一地区的矿产资源特征, 预测该区的资源量。[6] 

实例

为了适应市场的需要，某地准备扩大电视机生产。市场预测表明：产品销路好的概率为0.7；销路差的概率为0.3。备选方案有三个：第一个方案是建设大工厂，需要投资600万元，可使用10年；如销路好，每年可赢利200万元；如销路不好，每年会亏损40万元。第二个方案是建设小工厂，需投资280万元；如销路好，每年可赢利80万元；如销路不好，每年也会赢利60万元。第三个方案也是先建设小工厂，但是如销路好，3年后扩建，扩建需投资400万元，可使用7年，扩建后每年会赢利190万元。

　　各点期望：

点②：0.7×200×10+0.3×（-40）×10-600（投资）=680（万元）

决策树分析

点⑤：1.0×190×7-400=930（万元）

点⑥：1.0×80×7=560（万元）

比较决策点4的情况可以看到，由于点⑤（930万元）与点⑥（560万元）相比，点⑤的期望利润值较大，因此应采用扩建的方案，而舍弃不扩建的方案。把点⑤的930万元移到点4来，可计算出点③的期望利润值。

点③：0.7×80×3+0.7×930+0.3×60×（3+7）-280 = 719（万元）

最后比较决策点1的情况。由于点③（719万元）与点②（680万元）相比，点③的期望利润值较大，因此取点③而舍点②。这样，相比之下，建设大工厂的方案不是最优方案，合理的策略应采用前3年建小工厂，如销路好，后7年进行扩建的方案。

• 参考资料

• 1.  戴淑芬 ．管理学教程 ：北京大学出版社，2009：76-79

• 2.  曹赛玉.几种决策概率模型在现实生活中的应用.理论与实践理论月刊，2006（5）

• 3.  基于决策树的数据挖掘算法的应用与研究  ．拓步ERP资讯网 [引用日期2013-01-16]

• 4.  陈诚,基于AFS理论的模糊分类器设计, 大连理工大学,2010

• 5.  什么是决策树？  ．中国机床网[引用日期2013-01-16]

• 6.  Jiawei Han．数据挖掘概念与技术：机械工业出版社，2012

• 7.  决策树  ．云南大学[引用日期2013-01-22]







决策是选择or匹配？





决策，指决定的策略或办法。

选择，单指向，1、挑选，选取；动词。2、指为自己做的决定。

匹配，双指向，一般指配合或搭配，也指结婚。“匹配”一词在不同的领域有着不同的意思，它既是数学语言，又是计算机方面的术语，其含义复杂多变。




因此，决策 = 选择 + 匹配





由于匹配是信息的双向配对，所以在技术的商业化运用中，匹配具有其他技术所没有的优势：信息的“主动出击”和信息的高成交率。在信息的传播过程和信息处理过程中都有极大的优势。目前较常见的匹配商业化运用主要体现在以下两个方面：




交友匹配

交友网站是率先运用匹配技术的网站，如百合网根据用户自身的资料再填写对对方的要求，根据“我的条件——TA对我的要求”和“我对TA的要求——TA的条件”这样的关系进行条件项的匹配。这是一种比较传统的匹配。酷配网在进行交友方面的匹配时，则根据用户的兴趣爱好来进行匹配，用户可以输入：杭州周末 登山。这一系列的匹配关键字，可以匹配到同样有这方面爱好的朋友，因为酷配发布的需求是有30天的匹配时间的。所以在这段时间内，你可以源源不断的得到匹配结果，这些有的是你在你发布前的，有的是在你发布需求后面发布的，都可以匹配在一起。省去你每天都要搜索的麻烦，让你“一劳永逸”。




生活信息处理

现实生活中的很多信息是有明确的行为和目的的，在同一个需求下面往往有很明确的供需对应关系，如房产中就有很明确的出租——求租、出售——求购的行为。而现在普通网站往往只是提供信息的展示，方便他人搜索、查阅，不能有效的将这些信息很好的对应起来，这个时候匹配就体现出强大的优势。这方面的案例可以参考雅虎空间和酷配网。

由于酷配网专注于匹配技术的运用，在其平台上，匹配的优势发挥得淋漓尽致，主要在酷配网上发布需求，稍等片刻，酷配就会为您自动匹配到相关的需求信息，并按照匹配度从高到低排列，省掉以往的“搜索——检索”的漫长过程，用户免去这一步有时候还真不大习惯。

来源：人机与认知实验室