共计 2758 个字符，预计需要花费 7 分钟才能阅读完成。
决策树概念
决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。
可以看到，决策树的决策过程非常直观，容易被人理解。目前决策树已经成功运用于医学、制造产业、天文学、分支生物学以及商业等诸多领域。知道了决策树的定义以及其应用方法，下面介绍决策树的构造算法。
上图以一个西瓜的决策树为例，决策树的判定顺序就是一个树的搜索过程，首先判定西瓜的色泽，若西瓜的颜色是青绿色，则继续判定当前西瓜的根蒂情况，要是蜷缩的话继续听敲声，若敲声浑浊，则可以判定当前的西瓜是个好瓜，如此完成决策树决策的过程。
决策树的构造
不同于贝叶斯算法，决策树的构造过程不依赖领域知识，它使用属性选择度量来选择将元组最好地划分成不同的类的属性。所谓决策树的构造就是进行属性选择度量确定各个特征属性之间的拓扑结构。
构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。分裂属性分为三种不同的情况：
1、属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。
2、属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支。
3、属性是连续值。此时确定一个值作为分裂点split_point，按照>split_point和<=split_point生成两个分支。
如何选择最优划分属性的方法是决策树的关键所在，常用的有ID3算法（信息增益算法），C45算法（增益率）和CART算法
ID3算法
从信息论知识中我们直到，期望信息越小，信息增益越大，从而纯度越高。所以ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。下面先定义几个要用到的概念。
设D为用类别对训练元组进行的划分，则D的熵（entropy）表示为：
其中pi表示第i个类别在整个训练元组中出现的概率，可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是D中元组的类标号所需要的平均信息量。
现在我们假设将训练元组D按属性A进行划分，则A对D划分的期望信息为：
而信息增益即为两者的差值：
ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂。下面我们继续用SNS社区中不真实账号检测的例子说明如何使用ID3算法构造决策树。为了简单起见，我们假设训练集合包含10个元素：
其中s、m和l分别表示小、中和大。
设L、F、H和R表示日志密度、好友密度、是否使用真实头像和账号是否真实，下面计算各属性的信息增益。
因此日志密度的信息增益是0.276。
用同样方法得到H和F的信息增益分别为0.033和0.553。
因为F具有最大的信息增益，所以第一次分裂选择F为分裂属性，分裂后的结果如下图表示：
在上图的基础上，再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。
上面为了简便，将特征属性离散化了，其实日志密度和好友密度都是连续的属性。对于特征属性为连续值，可以如此使用ID3算法：
先将D中元素按照特征属性排序，则每两个相邻元素的中间点可以看做潜在分裂点，从第一个潜在分裂点开始，分裂D并计算两个集合的期望信息，具有最小期望信息的点称为这个属性的最佳分裂点，其信息期望作为此属性的信息期望。
C4.5算法
ID3算法存在一个问题，就是偏向于多值属性，例如，如果存在唯一标识属性ID，则ID3会选择它作为分裂属性，这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率（gain ratio）的信息增益扩充，试图克服这个偏倚。
C4.5算法首先定义了“分裂信息”，其定义可以表示成：
其中各符号意义与ID3算法相同，然后，增益率被定义为：
C4.5选择具有最大增益率的属性作为分裂属性，其具体应用与ID3类似，不再赘述。
ID3算法和C45对比
ID3对于可取值数量较多的属性具有较好的偏好，C45则对可取值数量较少的属性具有较好的偏好
CART
设
代表单个样本的
个属性，
表示所属类别。CART算法通过递归的方式将
维的空间划分为不重
叠的矩形。划分步骤大致如下
（1）选一个自变量
，再选取
的一个值
，
把
维空间划分为两部分，一部分的所有点都满足
，
另一部分的所有点都满足
，对非连续变量来说属性值的取值只有两个，即等于该值或不等于该值。
（2）递归处理，将上面得到的两部分按步骤（1）重新选取一个属性继续划分，直到把整个
维空间都划分完。
在划分时候有一个问题，它是按照什么标准来划分的 ？ 对于一个变量属性来说，它的划分点是一对连续变量属
性值的中点。假设
个样本的集合一个属性有
个连续的值，那么则会有
个分裂点，每个分裂点为相邻
两个连续值的均值。每个属性的划分按照能减少的杂质的量来进行排序，而杂质的减少量定义为划分前的杂质减
去划分后的每个节点的杂质量划分所占比率之和。而杂质度量方法常用Gini指标，假设一个样本共有
类，那么
一个节点
的Gini不纯度可定义为
其中
表示属于
类的概率，当Gini(A)=0时，所有样本属于同类，所有类在节点中以等概率出现时，Gini(A)
最大化，此时
。
有了上述理论基础，实际的递归划分过程是这样的：如果当前节点的所有样本都不属于同一类或者只剩下一个样
本，那么此节点为非叶子节点，所以会尝试样本的每个属性以及每个属性对应的分裂点，尝试找到杂质变量最大
的一个划分，该属性划分的子树即为最优分支。
下面举个简单的例子，如下图
上述图中，属性有3个，分别是有房情况，婚姻状况和年收入，其中有房情况和婚姻状况是离散的取值，而年
收入是连续的取值。拖欠贷款者属于分类的结果。
假设现在来看有房情况这个属性，那么按照它划分后的Gini指数计算如下
而对于婚姻状况属性来说，它的取值有3种，按照每种属性值分裂后Gini指标计算如下
最后还有一个取值连续的属性，年收入，它的取值是连续的，那么连续的取值采用分裂点进行分裂。如下
根据这样的分裂规则CART算法就能完成建树过程.
部分参考：
http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html
