决策树（Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy ＝ 系统的凌乱程度，使用算法ID3， C4．5和C5．0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

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

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

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

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

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

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

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

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

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

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

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

（x， y） ＝ （x1， x2， x3…， xk， y）

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

优点

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

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

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

缺点

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

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

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

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

算法

1、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）返回的点

2、CART

背景：

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

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

定义：

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