文档介绍：

分类是一种应用非常广泛的数据挖掘技术，应用的例子也很多。例如，根据信用卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用；根据某种病症的诊断记录，来分析哪些药物组合可以带来良好的治疗树过大或过度拟合。因此为了简化决策树，寻找一颗最优的决策树，剪枝是一个必不可少的过程。
通常，决策树越小，就越容易理解，其存储与传输的代价也就越小，但决策树过小会导致错误率较大。反之，决策树越复杂，节点越多，每个节点包含的训练样本个数越少，则支持每个节点样本数量也越少，可能导致决策树在测试集上的分类错误率越大。因此，剪枝的基本原则就是，在保证一定的决策精度的前提下，使树的叶子节点最少，叶子节点的深度最小。要在树的大小和正确率之间寻找平衡点。
不同的算法，其剪枝的方法也不尽相同。常有的剪枝方法有预剪枝和后剪枝两种。，CART则采用后剪枝。
预剪枝，是指在构建决策树之前，先制定好生长停止准则（例如指定某个评估参数的阈值），在树的生长过程中，一旦某个分支满足了停止准则，则停止该分支的生长，这样就可以限制树的过度生长。采用预剪枝的算法有可能过早地停止决策树的构建过程，但由于不必生成完整的决策树，算法的效率很高，适合应用于大规模问题。
后剪枝，是指待决策树完全生长结束后，再根据一定的准则，剪去决策树中那些不具一般代表性的叶子节点或者分支。这时，可以将数据集划分为两个部分，一个是训练数据集，一个是测试数据集。训练数据集用来生成决策树，而测试数据集用来对生成的决策树进行测试，并在测试的过程中通过剪枝来对决策树进行优化。
生成原则在生成一棵最优的决策树之后，就可以根据这棵决策树来生成一系列规则。这些规则采用“If...,Then...”的形式。从根节点到叶子节点的每一条路径，都可以生成一条规则。这条路径上的分裂属性和分裂谓词形成规则的前件（If部分），叶子节点的类标号形成规则的后件（Then部分）。
例如，：
If（年龄＜40）and（职业二“学生”or职业二“教师”）Then信用等级二“优”
If（年龄＜40）and（职业匸“学生”and职业匸“教师”）Then信用等级二“良”
If（年龄＞=40）and（月薪＜1000）Then信用等级二“差”
If（年龄＞=40）and（月薪＞=1000and月薪＜=3000）Then信用等级二“良”
If（年龄＞=40）and（月薪＞3000）Then信用等级二“优”这些规则即可应用到对未来观测样本的分类中了。
ID3、
ID3算法是最有影响力的决策树算法之一，由Quinlan提出。；，使其综合性能大幅度提高。，其算法细节属于商业机密，因此没有被公开，，包括Clementine。

，其核心步骤都是为每一次分裂确定一个分裂属性，即究竟按照哪一个属性来把当前数据集划分为若干个子集，从而形成若干个“树枝”。
ID3算法采用“信息增益”为度量来选择分裂属性的。哪个属性在分裂中产生的信息增益最大，就选择该属性作为分裂属性。那么什么是信息增益呢？这需要首先了解“熵”这个概念。
熵，是数据集中的不确定性、突发性或随机性的程度的度量。当一个数据集中的记录全部都属于同一类的时候，则没有不确定性，这种情况下的熵为0。
决策树分类的基本原则是，数据集被分裂为若干个子集后，要使每个子集中的数据尽可能的“纯”，也就是说子集中的记录要尽可能属于同一个类别。如果套用熵的概念，即要使分裂后各子集的熵尽可能的小。
例如在一次分裂中,数据集D被按照分裂属性“年龄”分裂为两个子集D1和D2,。
H(D)
年龄
<40
K40
2
H〔D<

3H(D2)
其中,H(D).H(D}H(6)，抜照“牟龄”将薮据冀D分裂为D3和0所得到的信息增益为：
Gain{D7年龄)二H(D卜[P(DJxH(D])+P(DJ汽H(Dj]
其中，P((D*是D中的样本菠划分到吐中的閒率*P(D1)xH(DI)+P(D2)xH(D2)是H(Di)和H(D2)的幅加权和S
显燃，如果內和氏中的数据越“纯”，H(DO和H(6)的越小，倍息増益就越大*或者说爛下降得越多°
按照这个方法，测试每一个属性的信息増益，选择缗益值最大的属性作为分裂属性°下面给出倍息增益的