Level 2 0 .4 0 .3
0 .3
Level 1 0 .6 0 .4
Level 0
有助于提高分类速度，减少特征提取所需费用 关键能否在分叉处找到合适的特征（集）和分类规则
12
2005/2
Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器
2005/2
Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器
9
{ω1 , ω 2 ,..., ω s }
简单的二叉树分类器（续）
~ fiห้องสมุดไป่ตู้
1
{ω1,..., ω s }
1
fi
fj
~ fj
fk
例：共有s个类 {ω1 , ω 2 ,..., ω s } ◆ 根据是否具有特征 {ω s +1,..., ω s } （集） f 分成两个子集 i
一般分类树（决策树）的定义（边书P113~）
n1
■
分类树T的组成： ◆ 一个根节点n1 ◆ 一组非终止节点ni ◆ 一组终止节点tj tj ：与各个类别对应
不同的终止节点也可与相同类别对应
■
分类树（决策树）示意图
◆
分类树T对应于特征空间一种划分 ◆ 某个被划分区域中某类样本最 多，该节点就与该类样本对应
ai ：该节点上表征这种映射的参数
设 ni 和 nj 为T(S,I) 的两个节点：
ni = (ai ,τ i ), τ i = I i1 , I i 2 ,..., I ipi n j = a j ,τ j , τ j = I j1 , I j 2 ,..., I jp j
(
)
{
{
}
}
若
则称 ni 为 nj 的父节点， nj 为 ni 的子节点 ■ 设 B ⊂ T (S , I ) 是节点的有穷集，且 n ∈ B 。 若B中没有一个元素是n的父节点，则称n是B的根节点
■
且τk 中的一个元素就是 i 。
注：若规定 I i ∩ I j = Φ (空集），当i ≠ j ，则每个类别标记只在一 个终止节点处出现。若允许同一类别标记在多个不同终止 节点出现，则可取消此规定。
（ 意即：同一个模式类可经由不同途径来判别 ）
2005/2 Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器 16
2005/2 Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器 19
(
r = [d i ( X ) − d i ( X )] Wi − W j
权向量的差比权向量本身更重要
2005/2
超平面 Hij 的法向量为 Wi − W j ，X 到Hij 的距离为
（见§3.2最小欧氏距离分类）
(
)
)
Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器
6
◆
虽有 C s = s (s − 1) / 2 个决策区域的“对”，只有相邻区域有界面 → 实际界面上的超平面个数常常少于 C s2 = s (s − 1) / 2 个 例1
2
多类问题中的线性判别函数（续5）
2005/2
Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器
◆
1
每次一分为二（两类问题分类），直到每个子集只有一类为止 ◆ 同一层特征fj和fk可以相同，也可以不同 ◆ 若能找到同一层特征都相同，划分s个类至少要 log 2 S个特征
2005/2 Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器 10
简单二叉分类树设计（续）
考虑提高分类速度：让类先验概率较大的靠近树根 设{ω1 , ω 2 ,..., ω s } 中的类先验概率满足 P(ω1 ) ≥ P(ω 2 ) ≥ ... ≥ P(ω s ) ' ' ◆ 将 ω s 与 ω s −1 合成为一个候选集 ω s −1 ，令P (ω s −1 ) = P (ω s −1 ) + P (ω s )
■
为便于论述，可令 I i ∩ I j = Φ (空集），当i ≠ j （注：实际上, 为避免上层分类错误在下层不可纠正，也可令 I i ∩ I j ≠ Φ ，i ≠ j ）
{
}
广义决策规则 f : S → τ ，表示全体样本集 S 到与各个类相对 应的子样本集 Si 的一个映射（即：将样本分配到相应各类） 若将属于第 i 类的样本映射到包含 i 的那个子集Ik，则识别正确 ■ 设T(S,I)是由全体样本集S和类别标记集 I 所形成的所有可能映 射的集合，则T(S,I)可表示为由二元组 (ai ,τ i )组成的集合， 集合 的每个元素 (ai ,τ i ) 称作一个节点
简单二叉树分类器示例
n1
x2 ≤ 5
◆
1 一个 I = { ,2,3} 的3类问题
n2
x1 ≤ 2
n3
x3 ≤ 4
◆ ◆
每次选用一个特征分类 最终确定X所属类别
n4
x2 ≤ 2
ω1
t3
ω3
t4
ω2
t5
ω3
t1
ω2
t2
2005/2
Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器
第五章 关于树状分类器和分段线 性分类器
2005/2
Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器
1
§5.1 多类线性判别和树状分类器（边书P112~）
多类问题中的线性判别函数（共有s>2个类）
◆
把s类问题转化成 (s-1) 个两类问题 第i个问题：用一个线性判别函数分开属于ωi 类的 样本和不属于ωi 类的样本
7
多类问题中的线性判别函数（续6）
例2
◆
线性机器：决策区域为凸形、单连通，简单、便于分析
2005/2
Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器
8
简单的二叉树分类器
把复杂的多类分类问题，转化成分层次的两类问题
不试图用一种算法在n维特征空间同时分开多个类别 每次使用一个特征（或特征集），把“当前的”模式类候选 集一分为二个候选子集（即：作为一个两类问题处理） 以此类推，直到把所有的类都分开（每个候选子集中只有 一个候选模式类）
例：汉字识别，常采用3-4级分类 例：10万人大样本库人脸识别 PCA特征脸粗分类、级联精细弹性匹配：允许识别率 下降0.5%时速度提高约50倍（丁嵘，清华大学博士论文，
2002年10月）
树结构设计、特征选择、分类规则确定都不容易 整体优化的理论和实践都比较复杂，有兴趣者可参 阅边书P115-116（一般同学不作为要求）
斜线阴影为不确定区域
2005/2
Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器
2
多类问题中的线性判别函数（续1）
◆
把s类问题转化成 (s-1) 个两类问题（续）
中间和四角区域为不确定区域
2005/2
Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器
简单二叉分类树设计
考虑减少错误概率
在分类树的较“上层”（接近树根）若分类错误，则在下 层不易纠正 → 可利用§4.2 “分层聚类”所获得的分类树
越接近树根相似度越小，易获较小错误概率 ◆ 关键能否在分叉处找到合适的特征（集）和分类规则 ◆ 如有必要，分叉两侧的集合的“交集”也可不为空集
◆
2005/2 Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器 11
~ fk
{ω1,...,ω s } 和 {ω s +1,...,ω s }
1 1 1
再根据是否具有特征 ω （集） fj，把{ 1 ,..., ω s } 再分成两个子集
◆
fp
~ fp
{ωl } {ω m }
◆
再根据是否具有特征 ω （集） fk，把 { s +1 ,..., ω s } 再分成两个子集
17
二叉树分类器对特征空间的划分
（每次只用一个特征时）
看成用与特征轴垂直的超平面来 划分特征空间，每次一分为二 关键在于能否找到相应特征把所 有类分开
fk
fj
fi
示意图
2005/2
Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器
18
讨论
简化特征空间的划分，判别简单明确 便于用硬件或软件实现 特别对超多类的分类问题，大幅度提高分类速度
1≤l ≤ p j
U I jl = I ik ,
1 ≤ k ≤ pi
2005/2
Xinggang Lin, Tsinghua University 第五章 关于树状分类器和分段线性分类器
15
一般分类树（决策树）的数学表述（续2）
■
若 B ⊂ T (S , I ) 满足如下条件，则称B为一棵分类树（决策树）： 1) B中有且只有一个根节点 2) 设 ni 和 nj 是 B 中的两个不同元素，则 U I ik ≠ U I jl
■
2005/2