文档介绍：决策树算法的研究与改进
第46卷..第4期厦门大学学报(自然科学版)Vol. 46.. No. 4 ..2007 年 7 月 Journal of Xiamen U niversity ( Natural Science) Jul. 20T rees) 算法一致，. 5算法能实现基于规则的剪枝. 因为算法生成的每个叶子都和一条规则相关联，这个规则可以从树的根节点直到叶节点的路径上以逻辑合取式的形式读出.
3 .. CART 算法[1]
决策树的分类过程就是把训练集划分为越来越小
，显然决策树的分支应该停止了，，一般情况下，很难一步就达到目标，所以，如果不止一步才能结束的话，这个分类的过程就是一个递归树的生长过程，CART是仅有的一种通用的树生长算法.
节点属性选择准则
CART的节点选择准则是使节点的不纯度尽可能小， (impurity) 的不纯度比度量纯度更有利于分类，所以使用不纯度，主要有以下几种：
燔不纯度的计算公式为
Imp(N ) = - j
P ( j ) log2 P( .. j ) ( 1)
其中P ( . . j )是节点N处属于..j类样本数占总样本数，如果所有的样本都是同一类别的，则不纯度为零，否则就是一个大于零的正值.
题的方差不纯度定义为
Imp (N ) = P ( . . 1 ) P ( . . 2 ) ( 2)
很明显，
式(2)用于多类分类问题时它的值由下式得到
Imp(N ) = i . j
P ( ..i )P ( j ) = 1- j
P 2 ( . . j )
(3)
这就是Gini不纯度.
误分类不纯度
Imp(N ) = 1 - maxP( . . j ) ( 4)

个指标的峰值特性是最好的，但它的缺陷是导数不连续，因而在连续参数空间搜索最大值时会出现问题.
如果通过不纯度来选择属性，与ID3中的最大化
，不纯度下降可
以使用下式计算
..Imp (N ) = Imp(N ) -PL Imp (N L )-
..P R Imp( N R ) ( 5)
其中N L和N R是左右子节点，Imp( N L )和Imp(N R ) 是相应的不纯度，用于多类问题的简单推广是
..Imp( s) = Imp(N )-
M
k= 1
p k Imp (N k ) ( 6)
其中P k是分支到节点N k的训练样本占的比例，且满足
M
k = 1
P k = ，这个式子存在缺陷，如果M越大，显然..Imp(N )也越大，但是这个时候的分类未必是更有意义的，，对式(6)的一个改进是
..ImpM( s)=
..Imp ( s)
M
k= 1
Pk log2p k
(7)
这个公式实际上是式(6)的归一化.
分支停止准则
一般地，总存在一些样本不能从另一类样本中分
离出来，这就需要判断什么时候决策树的生长应该停，那么数据很可能会被#过拟合..极端情况下，节点只对应单一样本，决策树就变成一个查找表，这样对有较大噪声的，如果决策树停止的太早，对训练样本的误差就不够小，因而分类能力就很差.
一种判断停止分支的方法是验证和交叉验证技
术，即选择一部分样本进行训练，然后用剩余的样本作测试验证，选分支使得节点的不纯度下降差小于这个阈值，即
maxs . . ImpM ( s) < th 时，停止分支.
剪枝(Pr uning )
树充分的生长，后，对所有相邻的成对叶节点，准是如果消去它们使得不纯度的增长很小，就执行消，然，
断标准，可以从任何节点开始剪枝.
剪枝技术的一个缺陷是，如果样本数很大的话，则
计算量代价会非常高，，在一般的