决策树
维基百科，自由的百科全书
决策论中 (如风险管理)，决策树由一个决策图和可能的结果(包括资源成本和风险)组成， 用来创建到达目标的规划。决策树建立并用来辅助决策，是一种特殊的树结构。
目录 |
[编辑] 简介
机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。
从数据产生决策树的机器学习技术叫做决策树学习, 通俗说就是决策树。
决策数学习也是数据挖掘中一个普通的方法。在这里，每个决策树都表述了一种树型结构，他由他的分支来对该类型的对象依靠属性进行分类。每个决策树可以依靠对源数据库的分割进行数据测试。这个过程可以递归式的对树进行修剪。 The 递归 is completed when splitting is either non-feasible, or a singular classification can be applied to each element of the derived subset. A random forest classifier uses a number of decision trees, in order to improve the classification rate.
决策树同时也可以依靠计算条件概率来构造。
决策树如果依靠数学的计算方法可以取得更加理想的效果。 数据库已如下所示：
(x, y) = (x1, x2, x3…, xk, y)
相关的变量 Y 表示我们尝试去理解，分类或者更一般化的结果。 其他的变量x1, x2, x3 等则是帮助我们达到目的的变量。
[编辑] 类型
决策树有三个其他的名字:
- 分类树 分析是当预计结果可能为二进制类型(例如男女，输赢等)使用的概念。
- 回归树 分析是当局域结果可能为实数(例如房价，患者住院时间等)使用的概念。
- CART 分析是结合了上述二者的一个概念。。CART是Classification And Regression Trees的缩写.
[编辑] 举例阐述
下面我们用例子来说明：
小王是一家著名高尔夫俱乐部的经理。但是他被雇员数量问题搞得心情十分不好。某些天好像所有人都打玩高尔夫，以至于所有员工都忙的团团转还是应付不过来，而有些天不知道什么原因却一个人也不来，俱乐部为雇员数量浪费了不少资金。
小王的目的是通过下周天气预报寻找什么时候人们会打高尔夫，以适时调整雇员数量。因此首先他必须了解人们决定是否打球的原因。
在2周时间内我们得到以下记录:
天气状况有晴，云和雨；气温用华氏温度表示；相对湿度用百分比；还有有无风。当然还有顾客是不是在这些日子光顾俱乐部。最终他得到了14行5列的数据表格。
决策树模型就被建起来用于解决问题。
A decision tree is a model of the data that encodes the distribution of the class label (again the Y) in terms of the predictor attributes.
决策树是一个有向无环图。根结点代表所有数据。分类树算法finds out that the best way to explain the dependent variable, play, is by using the variable Outlook. Using the categories of the variable outlook three different groups were found:
打高尔夫的人分成三组，晴天打的，多云天打的和雨天打的。
我们得出第一个结论: 如果天气是多云，人们总是选择玩高尔夫，而只有少数很着迷的甚至在雨天也会玩。
接下来我们把晴天组的分为两部分，我们发现顾客不喜欢湿度高于70%的天气。
最终我们还发现，如果雨天还有风的话，就不会有人打了。
这就通过分类树给出了一个解决方案。 David, dismisses most of the staff on days that are sunny and humid or on rainy days that are windy because almost no one is going to play golf on those days. On the other days when a lot of people will play golf, you can hire some temporary staff to help you on the job.
结论是决策树帮助我们把复杂的数据表示转换成相对简单的直观的结构。
[编辑] 公式
[编辑] Gini impurity
CART算法(分类和回归树Classification and Regression Trees)使用。 It is based on squared probabilities of membership for each target category in the node. It reaches its minimum (zero) when all cases in the node fall into a single target category.
Suppose y takes on values in {1, 2, ..., m}, and let f(i, j) = frequency of value j in node i. That is, f(i, j) is the proportion of records assigned to node i for which y = j.
[编辑] 熵
算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是给予信息学理论中熵的概念。 
[编辑] 决策树的优点
相对于其他数据挖掘算法，决策树在以下几个方面拥有优势：
- 决策树易于理解和实现. 人们在通过解释后都有能力去理解决策树所表达的意义。
- 对于决策树，数据的准备往往是简单或者是不必要的 . 其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。
- 能够同时处理数据型和常规型属性。 其他的技术往往要求数据属性的单一。
- 是一个白盒模型如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。
- 易于通过静态测试来对模型进行评测。 表示有可能测量该模型的可信度。
- 在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
[编辑] 由决策树扩展为决策图
在决策树中所有从根到叶节点的路径都是通过“与”（AND）运算连接。在决策图中可以使用“或”来连接多于一个的路径。
A complement to Decision Trees is 词法分析.
[编辑] 相关条目
[编辑] 参考文献
- [1] T. Menzies, Y. Hu, Data Mining For Very Busy People. IEEE Computer, October 2003, pgs. 18-25.
- [2]决策数分析 mindtools.com
- [3]J.W. Comley and D.L. Dowe, "Minimum Message Length, MDL and Generalised Bayesian Networks with Asymmetric Languages", 第十一章 (pp265-294) in P. Grunwald, M.A. Pitt and I.J. Myung (eds)., Advances in Minimum Description Length: Theory and Applications, M.I.T. Press, April 2005, ISBN 0262072629. (本论文把决策树作为贝叶斯网络使用Minimum Message Length (MML的内部结点). 早期版本：Comley and Dowe (2003), .pdf.)
- [4]P.J. Tan and D.L. Dowe (2004), MML Inference of Oblique Decision Trees, 人工智能讲义 3339, Springer-Verlag, pp1082-1088. (此论文使用 Minimum Message Length.)
- [5] Eruditionhome 数据挖掘资源大词典
- [6]决策树基础 vanguardsw.com
- [7]General Morphological Analysis: A General Method for Non-Quantified Modelling From the Swedish Morphological Society
- [8]decisiontrees.net Interactive Tutorial
- [9][Morgan.Kaufmann.Data.Mining.Practical.Machine.Learning.Tools.and.Techniques.Second.Edition]Jun.2005,非常好的一本介绍决策树的书，是一本可以从基础学起的好书，另外介绍的weka决策树软件也不错。是JAVA编的。
