第4章 分类：基本概念、决策树与模型评估
4.1预备知识 4.2解决分类问题的一般方法 4.3决策树归纳 4.4模型的过分拟合 4.5评估分类器的性质 4.6比较分类器的方法
分类任务：确定对象属于哪个预定义的目标类
例子： 1、根据电子邮件的标题和内容检查 出垃圾邮件。 2、根据星系的形状对它们分类。
0.1
0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 p
二元分类问题不纯性度量之间的比较
不同的不纯性度量是一致的，但是作为测试条件的属性选择仍然 因不纯性度量的选择而异。
为确定测试条件的效果，我们需要比较父结点（划分前）的不纯性程度和 子女结点（划分后）的不纯性程度，它们的差越大，测试条件的效果就越
性别
车型
男
女 家用 运动
顾客ID
豪华 v1
v20
v10 v11
C0:6 C1:4
C0:4 C0:1 C1:6 C1:3
C0:8 C1:0
C0:1 C0:1 … C0:1 C0:0 … C0:0 C1:7 C1:0 C1:0 C1:1 C1:1
（a）
（b）
（c）
选择最佳划分的度量通常是根据划分后子女结点不纯性的度量。不纯的 程度越低，类分布就越倾斜。例如（0,1）的结点具有零不纯性，而均衡 分布（0.5, 0.5）的结点具有最高的不纯性。不纯性度量的例子包括：
（1）算法的第二步所创建的子女结点可能为空，即不存在与这些结点相关 联的记录。如果没有一个训练记录包含这样的结点相关联的属性值组合，这 种情形就可能发生。这时，该结点成为叶结点，类标号为其父结点上训练记 录中的多数类。
（2）在第二步，如果与 Dt 相关联的所有记录都具有相同的属性值（目标属 性除外），则不可能进一步划分这些记录。在这种情况下，该结点为叶结点， 其标号为与该结点相关联的训练记录中的多数类。
椭圆状的星系
螺旋状的星系
分类任务的输入数据是记录的集合。每条记录也称实例或者样例， 用元组（x, y）表示，其中x是属性的集合，而y是一个特殊的属性， 指出样例的类标号（也成为分类属性或目标属性）。
分类？回归？
分类（classification）
通过学习得到一个目标函数（target function）f ， 也成为分类模 型（classification model），把每个属性集x映射到一个预先定义的类标 号y。
Test Set
Class ? ? ? ? ?
Learning algorithm
Induction Learn Model
Apply Model
Deduction
训练集：由类标号已知的记录构成 检验集：由类标号未知的记录构成
Model
二类问题的混淆矩阵
实际的类
类=1 类=0
预测的类
类=1
类=0
f11
Hunt算法
Tid
有房者
1
是
2
否
3
否
4
是
5
否
6
否
7
是
8
否
9
否
10
否
婚姻状况
单身 已婚 单身 已婚 离异 已婚 离异 单身 已婚 单身
年收入
125k 100k 70k 120k 95k 60k 220k 85k 75k 90k
拖欠贷款者
否 否 否 否 是 否 否 是 否 是
Hunt算法构造决策树
有房者
Gini 1 (3 / 6)2 (3 / 6)2 0.5 Entropy (3/ 6) log 2 (3/ 6) (3/ 6) log 2 (3/ 6) 1 Error 1 max[3/ 6,3/ 6] 0.5
1
熵
0.9
Gini
分类误差 0.8
0.7
0.6
0.5
0.4
0.3
0.2
决策树归纳的设计问题
（1）如何分裂训练记录？
树增长过程的每个递归步骤都必须选择一个属性测试条件，将 记录划分成较小的子集。为了实现这个步骤。算法必须提供为 不同类型的属性指定测试条件的方法，并且提供评估每种测试 条件的客观度量。
（2）如何停止分裂过程？
决策树需要有结束条件，以终止决策树的生长过程。一个可能 的策略是分裂结点，直到所有的记录都属于同一个类，或者所 有的记录都具有相同的属性值。
在Hunt算法中，通过将训练记录相继划分成较纯的子集，以递归方式 建立决策树。设Dt 是与结点t相关联的训练记录集，而y {y1, y2 , , yc} 是类标号，Hunt算法的递归定义如下。
（1）如果 Dt 中所有记录都属于同一个类 yt ，则t是叶结点，用 yt 标记。
（2）如果 Dt 中包含属于多个类的记录，则选择一个属性测试条件， 将记录划分成较小的子集。对于测试条件的每个输出，创建一个子女 结点，并根据测试结果将 Dt 中的记录分布到子女结点中。然后，对于 每个子女结点，递归地调用该算法。
开始，将测试条件用于检验记录，根据测试结果选择适当的分支。沿着该 分支或者到达另一个内部结点，使用新的测试条件，或者到达一个叶结点。 到达叶结点之后，叶结点的类标号就被赋值给该检验记录。
名字 火烈鸟
体温 恒温
胎生 否
……
类标号
……
？
是
哺乳动 物
恒温
体温
胎生 否
非哺乳 动物
冷血
非哺乳 动物
如何建立决策树
好。增益 是一种可以用来确定划分效果的标准：
I ( parent)
k j 1
N(v j ) N
I (v j )
其中，I(•) 是给定结点的不纯性度量，N是父结点上的记录总数，k是 属性值的个数，N (v j ) 是与子女结点v j 相关联的记录个数。
准确率
正确预测数 预测总数
ቤተ መጻሕፍቲ ባይዱf11
f11 f10
f 00 f01
f 00
同样，分类模型的性能也可以用错误率（error rate）来表示，其定 义如下：
错误率
错误预测数 预测总数
f11
f10 f 01 f10 f 01
f 00
目标：寻求最高的准确率或者最低的错误率
1、什么是决策树？ 类似于流程图的树结构 每个内部节点表示在一个属性上的测试 每个分枝代表一个测试输出 每个叶节点代表类或类分布
目的： 1、描述性建模 分类模型可以作为解释性的工具，用于区分不同类中的对象。 2、预测性建模 分类模型还可以用于预测未知记录的类标号。
名字 体温 表皮 胎生 水生 飞行 有腿 冬眠 类标
覆盖
动物 动物
号
毒蜥 冷血 鳞片 否 否 否 是 是 ？
输入属性集（x）
分类模型
输出类标号（y）
分类器的任务：根据输入属性集x确定类标号y
表示属性测试条件的方法 1、二元属性
二元属性的测试条件产生两个可能的输出。
体温
恒温
冷血
二元属性的测试条件
2、标称属性 由于标称属性有多个属性值，它的测试条件可以用两种方法表示。
婚姻状 况
婚姻状 况
单身 离异 多路划分
已婚
婚姻状 况
婚姻状 况
已婚
单身，离异
单身
已婚，离异 单身，已婚
二元划分（通过属性值分组）
对于给定的属性集，可以构造的决策树的数目达指数级。 尽管某些决策树比其他决策树更准确，但是由于搜索空间是 指数规模的，找出最佳决策树在计算上是不可行的。
尽管如此，人们还是开发了一些有效的算法，能够在合 理的时间内构造出具有一定准确率的次最优决策树。这些算 法通常都采用贪心策略。
有许多决策树算法: Hunt算法 信息增益——Information gain （ID3） 增益比率——Gain ration（C4.5） 基尼指数——Gini index (SLIQ，SPRINT)
Training Set
Class No No No No Yes No No Yes No Yes
Tid 11 12 13 14 15
10
Attrib1 Attrib2
No
Small
Yes
Medium
Yes
Large
No
Small
No
Large
Attrib3 55K 80K 110K 95K 67K
分类技术非常适合预测或描述二元或标称类型的数据集，对序数分类不 太有效，因为分类技术不考虑隐含在目标类中的序关系。
分类技术是一种根据输入数据集建立分类模型的系统方法。
分 类 技 术
这些技术都使用一种学习算法确定分类模型，修改这个模型能够很好地 拟合输入数据中类标号和属性集之间的联系。学习算法得到的模型不仅 要很好地拟合输入数据，还要能够正确地预测未知样本的类标号。 训练算法的目标：建立具有很好的泛化能力的模型。
Tid 1 2 3 4 5 6 7 8 9 10
10
Attrib1 Attrib2
Yes
Large
No
Medium
No
Small
Yes
Medium
No
Large
No
Medium
Yes
Large
No
Small
No
Medium
No
Small
Attrib3 125K 100K 70K 120K 95K 60K 220K 85K 75K 90K
内部结点（internal node）：恰好有一条入边和两条或多条出边。
叶节点（leaf node）或终结点（terminal node）：恰好有一条入边， 但没有出边。
体温
根结点
内部结点