第二章 距离分类器和
聚类分析
2.1 距离分类器
? 一、模式的距离度量
距离函数应满足的条件
? 对称性,? ? ? ?
,,dd ?X Y Y X
? ?,0d ?XY
? ? ? ? ? ?,,,d d d??X Y X Z Y Z
? 非负性：
? 三角不等式：
常用的距离函数
? 欧几里德距离,(Eucidean Distance)
? ? ? ?
1
2
2
1
,
n
ii
i
d x y
?
??
????
??
?XY
常用的距离函数
? 街市距离,(Manhattan Distance)
? ?
1
,
n
ii
i
d x y
?
???XY
常用的距离函数
? 明氏距离,(Minkowski Distance)
? ?
1
1
,
mn
m
ii
i
d x y
?
??
????
??
?XY
常用的距离函数
? 角度相似函数,(Angle Distance)
? ?,
T
d
?
?
XY
XY
XY
1
n
T
ii
i
xy
?
?? ?XY
是 X与 Y之间的内积
X 为矢量 X的长度，也称为范数
二、单个标准样本距离分类器
M个类别：
12,,,M? ? ?L
每个类别有一个标准样本：
12 MT,T,,TL
对待识样本 X进行分类。
建立分类准则
如果有：
? ?0 a r g m in,i
i
id? XT
则判别：
0i
??X
距离分类器
类 别 1 距 离
类 别 2 距 离
类 别 M 距 离
.,,
最
小
值
选
择
器
待 识 模 式 识 别 结 果
三、多标准样本的距离分类器
M个类别：
12,,,M? ? ?L
第 m个类别有训练样本集合：
对待识样本 X进行分类。
? ? ? ? ? ?? ?
12,,,m
m m m
KX X XL
多标准样本的距离分类器
? 平均样本法
对每一类求一个标准样本 T(m)，使 T(m)到
所有训练样本的平均距离最小：
? ? ? ?
1
1 mKmm
i
imK ?
? ?TX
平均样本法的特点
? 算法简单
? 存储量小
? 计算量小
? 效果不一定很好
平均距离法
已知 Ωi类有训练样本集：
定义待识模式 X与类别 Ωi的距离：
? ? ? ? ? ?? ?
12,,,i
i i i
KT T TL
? ? ? ?? ?
1
1,,iK i
ij
ji
dd
K ?
?? ?X X T
最近邻法
待识模式 X与类别 Ωi的距离：
? ? ? ?? ?
1
,m in,
i
i
ij jKdd ????X X T
最近邻法的改进
? 平均样本法：用一点代表一个类别，过
于集中；
? 最近邻法：以类内的每一点代表类别，
过于分散；
? 改进最近邻法：将每个类别的训练样本
划分为几个子集，以子集的平均样本作
为代表样本。
K-近邻法
1,计算 X与所有训练样本的距离；
2,对所计算出的距离从小到大排序；
3,统计前 K个中各类样本的个数 Ni；
4,如果：
则判别：
0 1a r g m a x iiMiN???
0i??X
2.2 聚类分析
? 简单聚类法
? 系统聚类法
? 动态聚类法
简单聚类法（试探法）
1,最近邻规则的简单试探法
2,最大最小距离算法
最近邻规则的简单试探法
已知,N个待分类模式 {X1,X2,…, XN}，
阈值 T(每个样本到其聚类中心的最大距离 )，
分类到 Ω1,Ω2,…，类别中心为 Z1,Z2,…
最近邻规则的简单试探法
第一步：取任意的样本作为第一个聚类中
心,Z1=X1；
计算 D21=||X2-Z1||；
如果 D21 >T，则增加新类别,Z1=X1；
否则,X2归入 Ω1类，重新计算：
Z1=(X1+ X2)/2
最近邻规则的简单试探法
第二步：设已有 M个类别，加入样本 Xk
计算 Dk1=||Xk-Z1||,Dk2=||Xk-Z2||… ；
如果 Dki >T，则增加新类别 ΩM+1
ZM+1=Xk；
否则,Xk归入最近的一类，重新计算该
类的聚类中心：
最大最小距离算法
? 基本思路,以最大距离原则选取新的聚
类中心，以最小距离原则进行模式归类；
? 已知, N个待识模式 {X1,X2,…, XN}，
阈值比例系数 θ 。
最大最小距离算法
1,任选样本作为第一个聚类中心 Z1；
2,从样本集中选择距离 Z1最远的样本 Xi作
为第二个聚类中心,Z2= Xi，设定阈值：
T= θ ||Z1- Z2||；
最大最小距离算法
3,计算未被作为聚类中心的各样本 Xi与 Z1，
Z2之间的距离，以其中的最小值作为该
样本的距离 di；
4,若 di >T，将 Xi作为第 3个聚类中心，
Z3= Xi，转 3；否则，转 5
5,按照最小距离原则，将所有样本分到各
类别中。
系统聚类法
? 基本思路,首先每一个样本自成一类，然
后按照距离准则逐步合并，类别数由多到
少，达到合适的类别数为止。
? 已知, N个待识模式 {X1,X2,…, XN}，类
别数 M。
类与类之间的距离
? 最短距离：
? ? ? ?? ?? ?m in,ij
ij l kDd? XX
? 最长距离：
? ? ? ?? ?? ?m a x,ij
ij l kDd? XX
? 平均距离：
? ? ? ?? ?21,ij
i j l k
ij
Dd
NN
? ? XX
系统聚类算法
? 第一步 建立 N个初始类别，每个样本一
个类别，计算距离矩阵 D=(Dij)；
? 第二步 寻找 D中的最小元素，合并相应
的两个类别，建立新的分类，重新计算
距离矩阵 D；
? 重复第二步，直到类别数为 M为止。
动态聚类法
? 基本思想,首先选择若干个样本点作为
聚类中心，然后各样本点向各个中心聚
集，得到初始分类；判断初始分类是否
合理，如果不合理，则修改聚类中心。
? 包括, K-均值算法,ISODATA算法。
K-均值算法 (C-均值 )
? 第一步：任选 K个初始聚类中心；
? 第二步：将每一个待分类样本分到 K个类
别中去；
? 第三步：计算各类的聚类中心；
? 第四步：检验新的聚类中心与旧的聚类
中心是否相等，相等则算法结束；否则
转第二步。
2.3 聚类结果评价
? 类内距离方差,
2
1 i
M
Wi
i
J
? ? ?
????
X
XZ
? 类间距离方差,
2
1
M
Bi
i
J
?
??? ZZ
1
1 M
i
iM ?
? ?ZZ
? 各类的样本数
聚类分析
2.1 距离分类器
? 一、模式的距离度量
距离函数应满足的条件
? 对称性,? ? ? ?
,,dd ?X Y Y X
? ?,0d ?XY
? ? ? ? ? ?,,,d d d??X Y X Z Y Z
? 非负性：
? 三角不等式：
常用的距离函数
? 欧几里德距离,(Eucidean Distance)
? ? ? ?
1
2
2
1
,
n
ii
i
d x y
?
??
????
??
?XY
常用的距离函数
? 街市距离,(Manhattan Distance)
? ?
1
,
n
ii
i
d x y
?
???XY
常用的距离函数
? 明氏距离,(Minkowski Distance)
? ?
1
1
,
mn
m
ii
i
d x y
?
??
????
??
?XY
常用的距离函数
? 角度相似函数,(Angle Distance)
? ?,
T
d
?
?
XY
XY
XY
1
n
T
ii
i
xy
?
?? ?XY
是 X与 Y之间的内积
X 为矢量 X的长度，也称为范数
二、单个标准样本距离分类器
M个类别：
12,,,M? ? ?L
每个类别有一个标准样本：
12 MT,T,,TL
对待识样本 X进行分类。
建立分类准则
如果有：
? ?0 a r g m in,i
i
id? XT
则判别：
0i
??X
距离分类器
类 别 1 距 离
类 别 2 距 离
类 别 M 距 离
.,,
最
小
值
选
择
器
待 识 模 式 识 别 结 果
三、多标准样本的距离分类器
M个类别：
12,,,M? ? ?L
第 m个类别有训练样本集合：
对待识样本 X进行分类。
? ? ? ? ? ?? ?
12,,,m
m m m
KX X XL
多标准样本的距离分类器
? 平均样本法
对每一类求一个标准样本 T(m)，使 T(m)到
所有训练样本的平均距离最小：
? ? ? ?
1
1 mKmm
i
imK ?
? ?TX
平均样本法的特点
? 算法简单
? 存储量小
? 计算量小
? 效果不一定很好
平均距离法
已知 Ωi类有训练样本集：
定义待识模式 X与类别 Ωi的距离：
? ? ? ? ? ?? ?
12,,,i
i i i
KT T TL
? ? ? ?? ?
1
1,,iK i
ij
ji
dd
K ?
?? ?X X T
最近邻法
待识模式 X与类别 Ωi的距离：
? ? ? ?? ?
1
,m in,
i
i
ij jKdd ????X X T
最近邻法的改进
? 平均样本法：用一点代表一个类别，过
于集中；
? 最近邻法：以类内的每一点代表类别，
过于分散；
? 改进最近邻法：将每个类别的训练样本
划分为几个子集，以子集的平均样本作
为代表样本。
K-近邻法
1,计算 X与所有训练样本的距离；
2,对所计算出的距离从小到大排序；
3,统计前 K个中各类样本的个数 Ni；
4,如果：
则判别：
0 1a r g m a x iiMiN???
0i??X
2.2 聚类分析
? 简单聚类法
? 系统聚类法
? 动态聚类法
简单聚类法（试探法）
1,最近邻规则的简单试探法
2,最大最小距离算法
最近邻规则的简单试探法
已知,N个待分类模式 {X1,X2,…, XN}，
阈值 T(每个样本到其聚类中心的最大距离 )，
分类到 Ω1,Ω2,…，类别中心为 Z1,Z2,…
最近邻规则的简单试探法
第一步：取任意的样本作为第一个聚类中
心,Z1=X1；
计算 D21=||X2-Z1||；
如果 D21 >T，则增加新类别,Z1=X1；
否则,X2归入 Ω1类，重新计算：
Z1=(X1+ X2)/2
最近邻规则的简单试探法
第二步：设已有 M个类别，加入样本 Xk
计算 Dk1=||Xk-Z1||,Dk2=||Xk-Z2||… ；
如果 Dki >T，则增加新类别 ΩM+1
ZM+1=Xk；
否则,Xk归入最近的一类，重新计算该
类的聚类中心：
最大最小距离算法
? 基本思路,以最大距离原则选取新的聚
类中心，以最小距离原则进行模式归类；
? 已知, N个待识模式 {X1,X2,…, XN}，
阈值比例系数 θ 。
最大最小距离算法
1,任选样本作为第一个聚类中心 Z1；
2,从样本集中选择距离 Z1最远的样本 Xi作
为第二个聚类中心,Z2= Xi，设定阈值：
T= θ ||Z1- Z2||；
最大最小距离算法
3,计算未被作为聚类中心的各样本 Xi与 Z1，
Z2之间的距离，以其中的最小值作为该
样本的距离 di；
4,若 di >T，将 Xi作为第 3个聚类中心，
Z3= Xi，转 3；否则，转 5
5,按照最小距离原则，将所有样本分到各
类别中。
系统聚类法
? 基本思路,首先每一个样本自成一类，然
后按照距离准则逐步合并，类别数由多到
少，达到合适的类别数为止。
? 已知, N个待识模式 {X1,X2,…, XN}，类
别数 M。
类与类之间的距离
? 最短距离：
? ? ? ?? ?? ?m in,ij
ij l kDd? XX
? 最长距离：
? ? ? ?? ?? ?m a x,ij
ij l kDd? XX
? 平均距离：
? ? ? ?? ?21,ij
i j l k
ij
Dd
NN
? ? XX
系统聚类算法
? 第一步 建立 N个初始类别，每个样本一
个类别，计算距离矩阵 D=(Dij)；
? 第二步 寻找 D中的最小元素，合并相应
的两个类别，建立新的分类，重新计算
距离矩阵 D；
? 重复第二步，直到类别数为 M为止。
动态聚类法
? 基本思想,首先选择若干个样本点作为
聚类中心，然后各样本点向各个中心聚
集，得到初始分类；判断初始分类是否
合理，如果不合理，则修改聚类中心。
? 包括, K-均值算法,ISODATA算法。
K-均值算法 (C-均值 )
? 第一步：任选 K个初始聚类中心；
? 第二步：将每一个待分类样本分到 K个类
别中去；
? 第三步：计算各类的聚类中心；
? 第四步：检验新的聚类中心与旧的聚类
中心是否相等，相等则算法结束；否则
转第二步。
2.3 聚类结果评价
? 类内距离方差,
2
1 i
M
Wi
i
J
? ? ?
????
X
XZ
? 类间距离方差,
2
1
M
Bi
i
J
?
??? ZZ
1
1 M
i
iM ?
? ?ZZ
? 各类的样本数
