文档介绍：决议树算法介绍(DOC)
决议树算法介绍(DOC)
2/22
决议树算法介绍(DOC)
分类与预测
分类是一种应用特别宽泛的数据挖掘技术，应用的例子也好多。比如，根据信立一棵决议树，重点问题就在于，怎样选择一个合适的分裂属性来进行一次分裂，以及怎样拟订合适的分裂谓词来产生相应的分支。各样决议树算法的主要区别也正在于此。
修剪决议树
利用决议树算法建立一个初始的树之后，为了有效地分类，还要对其进行剪枝。这是因为，由于数据表示不当、有噪音等原因，会造成生成的决议树过大或过分拟合。因此为了简化决议树，寻找一颗最优的决议树，剪枝是一个必不可少的过
程。
往常，决议树越小，就越容易理解，其存储与传输的代价也就越小，但决议树过小会致使错误率较大。反之，决议树越复杂，节点越多，每个节点包含的训练样本个数越少，则支持每个节点样本数量也越少，可能致使决议树在测试集上的分类错误率越大。因此，剪枝的基来源则就是，在保证一定的决议精度的前提下，使树的叶子节点最少，叶子节点的深度最小。要在树的大小和正确率之间寻找平衡点。
不同的算法，其剪枝的方法也不尽相同。常有的剪枝方法有预剪枝和后剪枝两种。
，CART则采用后剪枝。
预剪枝，是指在建立决议树以前，先拟订好生长停止准则（比如指定某个评估参数的阈值），在树的生长过程中，一旦某个分支知足了停止准则，则停止该分支的生长，这样就能够限制树的过分生长。采用预剪枝的算法有可能过早地停止决议树的建立过程，但由于不必生成完整的决议树，算法的效率很高，适合应用于大规模问题。
后剪枝，是指待决议树完全生长结束后，再根据一定的准则，剪去决议树中那些不具一般代表性的叶子节点或许分支。这时，能够将数据集区分为两个部分，一个是训练数据集，一个是测试数据集。训练数据集用来生成决议树，而测试数据集用来对生成的决议树进行测试，并在测试的过程中经过剪枝来对决议树进行优化。
决议树算法介绍(DOC)
决议树算法介绍(DOC)
5/22
决议树算法介绍(DOC)
生成原则
在生成一棵最优的决议树之后，就能够根据这棵决议树来生成一系列规则。这些规则采用“If...，Then...”的形式。从根节点到叶子节点的每一条路径，都能够生成一条规则。这条路径上的分裂属性和分裂谓词形成规则的前件（If部分），叶子节点的类标号形成规则的后件（Then部分）。
比如，：
If（年纪<40）and（职业=“学生”or职业=“教师”）Then信用等级=“优”
If（年纪<40）and（职业!=“学生”and职业!=“教师”）Then信用等级=“良”
If（年纪>=40）and（月薪<1000）Then信用等级=“差”
决议树算法介绍(DOC)
决议树算法介绍(DOC)
6/22
决议树算法介绍(DOC)
If（年纪>=40）and（月薪>=1000and月薪<=3000）Then信用等级=“良”If（年纪>=40）and（月薪>3000）Then信用等级=“优”
这些规则即可应用到对未来观察样本的分类中了。
决议树算法介绍(DOC)
决议树算法介绍(DOC)
7/22
决议树算法介绍(DOC)
、
与
决议树算法介绍(DOC)
决议树算法介绍(DOC)
21/21
决议树算法介绍(DOC)
ID3算法是最有影响力的决议树算法之一，由Quinlan提出。ID3算法的某些弱
；，使其综合性
能大幅度提高。，其算法细节属于商业机密，因
此没有被公然，，包括
Clementine。
决议树算法介绍(DOC)
决议树算法介绍(DOC)
21/21
决议树算法介绍(DOC)
信息增益
任何一个决议树算法，其核心步骤都是为每一次分裂确定一个分裂属性，即终究按照哪一个属性来把目前数据集区分为若干个子集，进而形成若干个“树枝”。ID3算法采用“信息增益”为胸怀来选择分裂属性的。哪个属性在分裂中产生的信息增益最大，就选择该属性