文档介绍：分类与决策树概述
分类与预测
分类是一种应用非常广泛的数据挖掘技术， 应用的例子也很多。例如，根据信用 卡支付历史记录，来判断具备哪些特征的用户往往具有良好的信用； 根据某种病
症的诊断记录，来分析哪些药物组合可以带来良好的治疗效果。 这些过程的一个
共同特点是：根据数据的某些属性，来估计一个特定属性的值。|例如在信用分析 案例中，根据用户的“年龄”、“性别”、“收入水平”、“职业”等属性的值， 来估计该用户“信用度”属性的值应该取“好”还是“差”， 在这个例子中，所
研究的属性“信用度”是一个离散属性， 它的取值是一个类别值，这种问题在数 据挖掘中被称为分类。
还有一种问题，例如根据股市交易的历史数据估计下一个交易日的大盘指数， 这 里所研究的属性“大盘指数”是一个连续属性， 它的取值是一个实数。那么这种 问题在数据挖掘中被称为预测。
总之，当估计的属性值是离散值时，这就是分类；当估计的属性值是连续值时， 这就是预测。
决策树的基本原理
.构建决策树
通过一个实际的例子，来了解一些与决策树有关的基本概念。
表3-1是一个数据库表，记载着某银行的客户信用记录，属性包括“姓名”、“年 龄”、“职业”、“月薪”、......、“信用等级”，每一行是一个客户样本， 每一列是一个属性（字段）。这里把这个表记做数据集 D。
表3-1信用记录表
|姓名
年龄
职业
月薪
…… 信用等级
张山
23
学生
1000
**,1■** i 良
王刚
45
公务员
3000
…… 优
李一海
38
职员
800
ft 11 ■ 1 ■
源芳
5C
W l- H
教师
A 1 1 1 I 1
2600
良
银行需要解决的问题是，根据数据集 D,建立一个信用等级分析模型，并根据这 个模型，产生一系列规则。当银行在未来的某个时刻收到某个客户的贷款申请时， 依据这些规则，可以根据该客户的年龄、职业、月薪等属性，来预测其信用等级， 以确定是否提供贷款给该用户。这里的信用等级分析模型，就可以是一棵决策树。 在这个案例中，研究的重点是“信用等级”这个属性。 给定一个信用等级未知的 客户，要根据他/她的其他属性来估计“信用等级”的值是“优”、“良”还是
“差”，也就是说，要把这客户划分到信用等级为“优”、“良”、“差”这 3 个类别的某一类别中去。这里把“信用等级”这个属性称为“类标号属性”。数 据集D中“信用等级”属性的全部取值就构成了类别集合：］Class={ “优”，
a小力 a -4A-力 ,
艮， 差 ｝。
在决策树方法中，有两个基本的步骤。其一是构建决策树，其二是将决策树应用 于数据库。大多数研究都集中在如何有效地构建决策树， 而应用则相对比较简单。 构建决策树算法比较多，在 Clementine中提供了 4种算法，包括C&RT CHAID ，输入训练数据集，就可以构造出一棵类似 。
一棵决策树是一棵有向无环树，它由若干个节点、分支、分裂谓词以及类别组成。 节点是一棵决策树的主体。其中，没有父亲节点的节点称为 根节点，
中的节点1;没有子节点的节点称为 叶子节点，、5、6、7、 8。一个节点按照某个属性分裂时，这个属性称为分裂属性，如节点 1按照“年 龄”被分裂，这里“年龄”就是分裂属性，同理，“职业”、“月薪”也是分裂 属性。每一个分支都会被标记一个分裂谓词， 这个分裂谓词就是分裂父节点的具 体依据，例如在将节点1分裂时，产生两个分支，对应的分裂谓词分别是“年龄 <40”和“年龄>=40'。另外，每一个叶子节点都被确定一个类标号，这里是
“优”、“良”或者“差”。
基于以上描述，下面给出决策树的定义：
给定一个数据集DYhhM｝.其中匕士貂加-g是口中的第i个样本（曰工…再）激据 集横式包含的属性集为｛AeA2lA）, q是第i个样本的第j个属性a的值（j=*同 时给定类标号集合0£1£%..£或｝.对于数据集D,决策树是指具有下列3个性质的树上 ＜每个非叶子节点都被标记一个分裂属性Ai0
个 每个分支都被标记一个分裂谓词，这个分裂谓词是分裂父节点的具体依据＜
中 每个叶子节点都被标记一个类标号CjE3
由此可以看出，构建一棵决策树，关键问题就在于，如何选择一个合适的分裂属 性来进行一次分裂，以及如何制定合适的分裂谓词来产生相应的分支。各种决策 树算法的主要区别也正在于此。
.修剪决策树
利用决策树算法构建一个初始的树之后，为了有效地分类，还要对其进行 剪枝。
这是因为，由于数据表示不当、有噪音等原因，会造成生成的决策树过大