第 6章 聚类分析
本章目标
?辩别类有不同表示法和相似度的不同量度标
准。
?比较凝聚聚类和分区聚类算法的基本特征。
?用相似度的单链接或全链接度量标准实现凝
聚算法。
?推导分区聚类的 K-平均法并分析其复杂性。
?解释增量聚类算法的实现和它的优缺点。
?聚类分析是依据样本间关联的量度标
准将其自动分成几个群组，且使同一
群组内的样本相似，而属于不同群组
的样本相异的一组方法。聚类分析的
一个附加的结果是对每个类的综合描
述，这种结果对于更进一步深入分析
数据集的特征是尤其重要。
6.1 聚类概念
?聚类的样本是用度量指标的一个向量表示,或
更正式的说法是,用多维空间的一个点来表示。
同类中的样本比属于不同类的样本彼此具有
更高的相似性。聚类方法尤其适合用来探讨
样本间的相互关联关系从而对一个样本结构
做一个初步的评价。人们能够对一维、二维
或三维的样本进行聚类分析，但是大多数现
实问题涉及到更高维的聚类。
?例如：下表是一个简单聚类例子，包含了 9个
顾客的信息，分三类，两个特征值 (数量,价
格 )
类 1:购少量高价商品，类 2：购大量的高价品，
类 3：购小量的低价商品。
?聚类是一个非常难的问题,因为在一个 n维的
样本空间数据可以以不同的形状和大小揭示
类。
?下面基于欧几里得二维空间的聚类过程的一
个示例。
?上面数据可以分类三个类也可以分为四个类，
类的数量的任意性是聚类过程中的主要问题。
?另一方面，上面的类是能够直接观察到的。
对于高维欧几里得空间里的一组点，就无法
从视觉上观察到。
? 聚类分析输入可以用一组有序数对 (X,s)或
(X,d)表示。聚类系统的输出是一个分区
∧ ={G1,G2,…,GN}，其中 Gk(k=1,…,N)是
X的子集。
?G1,G2,…,GN称为类，每一个类用一些特征
描述。聚类结果是类和它的特征或描述。
?规范化的描述有以下几种图式,
1.通过它们的重心或类中关系远的（边界）
点表示 n维空间的一类点 。
2,使用聚类树中节点图形化地表示一个类。
3.使用样本属性的逻辑表达式表示类。
?现有的用于数据挖掘的聚类方法分为
四类,分割法,分层法,密度法和网格法。
?分割聚类法一般是通过优化一个评价
函数把数据分割成 K个部分，主要有两
种方法,K-means聚类法和 K-medoid聚
类法,K-means法在处理海量数据库方
面很有效，特别是对数值属性处理。
K-prototypes是结合 K-means和 K-
modiod的优点，可以同时处理数值与
符号属性和聚类法
?分层聚类法是由不同层次的分割聚类
组成，层次之间的分割具有嵌套关系。
分层聚类法不必事先输入聚类块数 K，
基于模糊相似关系的模糊聚类属于这
种聚类法。
?密度聚类法是利用数据密度函数进行
聚类。
?网格聚法利用空间量子化方法把数据
分到有限个单元进行聚类，这种方法
效率高，与数据大小无关，仅与单元
数有关。
?值得注意的是：没有哪一种聚类技术对揭示
多维数据集中的构造种类是普遍适用的。使
用者对问题的理解和与其相应的数据类型是
选择合适方法的最好标准，大多数聚类算法
基于下面两种常见方法,
1.层次聚类
2.迭代的平方误差分区聚类
?层次方法按群组的嵌套顺序组织数据，以树
状图或树形结构来表示。
?平方误差分区算法试图得到一个使类内分散
最小而类间分散最大的分区。它是非层次的。
6.2 相似度的度量
?为了规范化相似度的度量标准，我们有如下
约定：在样本空间Ｘ的聚类算法中，用一个
数据向量表示一个样本 x(或特征向量，观察
值 )。假定每一个样本 xi∈ Ｘ,i=1,…,n都用向
量 xi={xi1,xi2,… xim}来表示,m的值是样本
的维数（特征）,n是一个样本数 。
?如果某个样本 xi的单个分量 xij是一个特征或
属性值，那么每一组成 xij,j=1,..,m是一个
域 Pj。 则每一个特征的值的取值范围 。
?Pj可以是二元类型，整型，实数，或某一特
征的一组分类。 例如 Pj是一组颜色,Pj
={白,黑,红,蓝,绿 }。
?由于相似度是定义一个聚类的基础，因此在
聚类分析中有必要建立同一特征空间中的两
种模式的相似度的度量标准。而且聚类分析
过程的质量取决于对度量标准的选择。
?一般地，不是计算两个样本间的相似度，而
是用特征空间中的距离作为度量标准计算两
个样本间的相异度。
? 聚类中的, 相似度, 意味着当 x和 x’是两个相似样本
时,s(x,x’)的取值是很大的，当 x和 x’不相似时，
s(x,x’)的取值是很小的。而且，相似度的度量标准 S
具有自反性,
s(x.x’)=s(x.x’)
对于大多数聚类方法，相似度的度量可以标准化为,
0≤s(x,x ’)≤1
? 相异度的度量标准用 d(x,x’)来表示 。 通常称相异度为
距离。当 x和 x’相似时,d很小，当 x和 x’不相似时,d
很大。而且 d>0,d(x,x’)=d(x’,x)，
d(x,x’’)≤d(x,x’)+d(x’,x’’)
?距离度量标准的算式,
1.欧氏距离,
2.L1距离或城区距离,
3.明考斯基距离,
?显然,p=1时 (3)与 (2)距离一样 ;p=2时 (3)
与 (1)距离一样。
?
?
??
m
k
jkikji xxxxd
1
1 ),(
p
m
k
p
jkikjip xxxxd
/1
1
))((),( ?
?
??
2/1
1
2
2 ))((),( ?
?
??
m
k
jkikji xxxxd
?欧氏 n维空间模型不仅给出了欧氏距离，还
给出另外的相似度度量标准，余弦相关就是
其中之一,
?则有：当 xi=λ ·xj,λ>0 时 scos(xi,xj)=1;
当 xi=λ ·xj,λ<0 时 scos(xi,xj)=-1
?例如：对于一个四维向量
x1={1,0,1,0},x2={2,1,-3,-1}
scos(xi,xj)=(2+0+3+0)/(21/2·151/2)=-0.18。
2/1
1 1
22
1
c o s ]/[])([),( ? ??
? ??
??
m
k
m
k
jkik
m
k
jkikji xxxxxxs
?由于样本中的特征可能包含一些或全部
不连续值，这种情况不可能采用上面距
离度量标准。实际上，对于异类样本的
不同特征使用不同的距离度量标准。下
面介绍一个可行的二元类型数据的距离
度量标准。
?假定,每一个样本都由 n维向量 xi表示,该
向量 xi由一个二类型数值组成。两个样
本 xi和 xj间的距离量度标准计算方法是,
?第一步：构造样本 xi和 xj的 2× 2列联表,
1.a为样本中 xi和 xj同时为 1的数量。
2,b为样本中 xi=1和 xj=0的数量。
3,c为样本中 xi=0和 xj=1的数量。
4,d为样本中 xi和 xj同时为 0的数量。
?例如,xi={0,0,1,1,0,1,0,1}
xj={0,1,1,0,0,1,0,0}
则 a=2,b=2,c=1,d=3
?第二步,采用下面 3种方式计算二元特性样本
的相似度。
1.简单匹配系数,
Ssmc(xi,xj)=(a+d)/(a+b+c+d)
2.Jaccard系数,Sjc(xi,xj)=a/(a+b+c)
3.Rao系数,Src(xi,xj)=a/(a+b+c+d)
?在环境已知的情况下,两个点 xi和 xj之间
的相似度可用互近邻距离 (mutual
Neighbor Distance,MND)来度量,它定义
如下,
MND(xi,xj)=NN(xi,xj)+NN(xj,xi)
其中,NN(xi,xj)是 xj对 xi点的邻近数目。
如果 xi是 xi离最近的点，那么 NN(xi,xj)
等于 1，如果它是第二近的点,
NN(xi,xj)等于 2，以此类推。下图是 MND
量度标准的计算。
?NN(A,B)=NN(B,A)=1→ MND(A,B)=2
?NN(B,C)=1,NN(C,B)=2→ MND(B,C)=3
?通过对图 6-3加入 3个新点 D,E,F得出图 6-4。
?因为环境改变了，样本点 A,B,C之间的
距离也改变了。
?NN(A,B)=1,NN(B,A)=4→ MND(A,B)=5
?NN(B,C)=1,NN(C,B)=2→ MND(B,C)=3
?尽管 A和 B未动，但因引入离 A近的其他点，
使 A和 B的 MND增大了,B和 C点变得比 A和
B具有更高的相似度。
?一般地，根据样本之间的一个距离度量标
准，可以确定类 (样本集 )间的距离度标准，
这些度量标准对评价一个聚类过程的质量
是必不可少的。广泛应用于 Ci和 Cj的距离度
量标准是,
1)Dmin(Ci,Cj)=min|pi-pj|
2)Dmean(Ci,Cj)=|mi-mj| 其中 mi和 mj是 Ci
和 Cj的质心
3)Davg(Ci,Cj)=1/(ninj)∑∑|pi-pj|
4)Dmax(Ci,Cj)=max|pi-pj|
本章目标
?辩别类有不同表示法和相似度的不同量度标
准。
?比较凝聚聚类和分区聚类算法的基本特征。
?用相似度的单链接或全链接度量标准实现凝
聚算法。
?推导分区聚类的 K-平均法并分析其复杂性。
?解释增量聚类算法的实现和它的优缺点。
?聚类分析是依据样本间关联的量度标
准将其自动分成几个群组，且使同一
群组内的样本相似，而属于不同群组
的样本相异的一组方法。聚类分析的
一个附加的结果是对每个类的综合描
述，这种结果对于更进一步深入分析
数据集的特征是尤其重要。
6.1 聚类概念
?聚类的样本是用度量指标的一个向量表示,或
更正式的说法是,用多维空间的一个点来表示。
同类中的样本比属于不同类的样本彼此具有
更高的相似性。聚类方法尤其适合用来探讨
样本间的相互关联关系从而对一个样本结构
做一个初步的评价。人们能够对一维、二维
或三维的样本进行聚类分析，但是大多数现
实问题涉及到更高维的聚类。
?例如：下表是一个简单聚类例子，包含了 9个
顾客的信息，分三类，两个特征值 (数量,价
格 )
类 1:购少量高价商品，类 2：购大量的高价品，
类 3：购小量的低价商品。
?聚类是一个非常难的问题,因为在一个 n维的
样本空间数据可以以不同的形状和大小揭示
类。
?下面基于欧几里得二维空间的聚类过程的一
个示例。
?上面数据可以分类三个类也可以分为四个类，
类的数量的任意性是聚类过程中的主要问题。
?另一方面，上面的类是能够直接观察到的。
对于高维欧几里得空间里的一组点，就无法
从视觉上观察到。
? 聚类分析输入可以用一组有序数对 (X,s)或
(X,d)表示。聚类系统的输出是一个分区
∧ ={G1,G2,…,GN}，其中 Gk(k=1,…,N)是
X的子集。
?G1,G2,…,GN称为类，每一个类用一些特征
描述。聚类结果是类和它的特征或描述。
?规范化的描述有以下几种图式,
1.通过它们的重心或类中关系远的（边界）
点表示 n维空间的一类点 。
2,使用聚类树中节点图形化地表示一个类。
3.使用样本属性的逻辑表达式表示类。
?现有的用于数据挖掘的聚类方法分为
四类,分割法,分层法,密度法和网格法。
?分割聚类法一般是通过优化一个评价
函数把数据分割成 K个部分，主要有两
种方法,K-means聚类法和 K-medoid聚
类法,K-means法在处理海量数据库方
面很有效，特别是对数值属性处理。
K-prototypes是结合 K-means和 K-
modiod的优点，可以同时处理数值与
符号属性和聚类法
?分层聚类法是由不同层次的分割聚类
组成，层次之间的分割具有嵌套关系。
分层聚类法不必事先输入聚类块数 K，
基于模糊相似关系的模糊聚类属于这
种聚类法。
?密度聚类法是利用数据密度函数进行
聚类。
?网格聚法利用空间量子化方法把数据
分到有限个单元进行聚类，这种方法
效率高，与数据大小无关，仅与单元
数有关。
?值得注意的是：没有哪一种聚类技术对揭示
多维数据集中的构造种类是普遍适用的。使
用者对问题的理解和与其相应的数据类型是
选择合适方法的最好标准，大多数聚类算法
基于下面两种常见方法,
1.层次聚类
2.迭代的平方误差分区聚类
?层次方法按群组的嵌套顺序组织数据，以树
状图或树形结构来表示。
?平方误差分区算法试图得到一个使类内分散
最小而类间分散最大的分区。它是非层次的。
6.2 相似度的度量
?为了规范化相似度的度量标准，我们有如下
约定：在样本空间Ｘ的聚类算法中，用一个
数据向量表示一个样本 x(或特征向量，观察
值 )。假定每一个样本 xi∈ Ｘ,i=1,…,n都用向
量 xi={xi1,xi2,… xim}来表示,m的值是样本
的维数（特征）,n是一个样本数 。
?如果某个样本 xi的单个分量 xij是一个特征或
属性值，那么每一组成 xij,j=1,..,m是一个
域 Pj。 则每一个特征的值的取值范围 。
?Pj可以是二元类型，整型，实数，或某一特
征的一组分类。 例如 Pj是一组颜色,Pj
={白,黑,红,蓝,绿 }。
?由于相似度是定义一个聚类的基础，因此在
聚类分析中有必要建立同一特征空间中的两
种模式的相似度的度量标准。而且聚类分析
过程的质量取决于对度量标准的选择。
?一般地，不是计算两个样本间的相似度，而
是用特征空间中的距离作为度量标准计算两
个样本间的相异度。
? 聚类中的, 相似度, 意味着当 x和 x’是两个相似样本
时,s(x,x’)的取值是很大的，当 x和 x’不相似时，
s(x,x’)的取值是很小的。而且，相似度的度量标准 S
具有自反性,
s(x.x’)=s(x.x’)
对于大多数聚类方法，相似度的度量可以标准化为,
0≤s(x,x ’)≤1
? 相异度的度量标准用 d(x,x’)来表示 。 通常称相异度为
距离。当 x和 x’相似时,d很小，当 x和 x’不相似时,d
很大。而且 d>0,d(x,x’)=d(x’,x)，
d(x,x’’)≤d(x,x’)+d(x’,x’’)
?距离度量标准的算式,
1.欧氏距离,
2.L1距离或城区距离,
3.明考斯基距离,
?显然,p=1时 (3)与 (2)距离一样 ;p=2时 (3)
与 (1)距离一样。
?
?
??
m
k
jkikji xxxxd
1
1 ),(
p
m
k
p
jkikjip xxxxd
/1
1
))((),( ?
?
??
2/1
1
2
2 ))((),( ?
?
??
m
k
jkikji xxxxd
?欧氏 n维空间模型不仅给出了欧氏距离，还
给出另外的相似度度量标准，余弦相关就是
其中之一,
?则有：当 xi=λ ·xj,λ>0 时 scos(xi,xj)=1;
当 xi=λ ·xj,λ<0 时 scos(xi,xj)=-1
?例如：对于一个四维向量
x1={1,0,1,0},x2={2,1,-3,-1}
scos(xi,xj)=(2+0+3+0)/(21/2·151/2)=-0.18。
2/1
1 1
22
1
c o s ]/[])([),( ? ??
? ??
??
m
k
m
k
jkik
m
k
jkikji xxxxxxs
?由于样本中的特征可能包含一些或全部
不连续值，这种情况不可能采用上面距
离度量标准。实际上，对于异类样本的
不同特征使用不同的距离度量标准。下
面介绍一个可行的二元类型数据的距离
度量标准。
?假定,每一个样本都由 n维向量 xi表示,该
向量 xi由一个二类型数值组成。两个样
本 xi和 xj间的距离量度标准计算方法是,
?第一步：构造样本 xi和 xj的 2× 2列联表,
1.a为样本中 xi和 xj同时为 1的数量。
2,b为样本中 xi=1和 xj=0的数量。
3,c为样本中 xi=0和 xj=1的数量。
4,d为样本中 xi和 xj同时为 0的数量。
?例如,xi={0,0,1,1,0,1,0,1}
xj={0,1,1,0,0,1,0,0}
则 a=2,b=2,c=1,d=3
?第二步,采用下面 3种方式计算二元特性样本
的相似度。
1.简单匹配系数,
Ssmc(xi,xj)=(a+d)/(a+b+c+d)
2.Jaccard系数,Sjc(xi,xj)=a/(a+b+c)
3.Rao系数,Src(xi,xj)=a/(a+b+c+d)
?在环境已知的情况下,两个点 xi和 xj之间
的相似度可用互近邻距离 (mutual
Neighbor Distance,MND)来度量,它定义
如下,
MND(xi,xj)=NN(xi,xj)+NN(xj,xi)
其中,NN(xi,xj)是 xj对 xi点的邻近数目。
如果 xi是 xi离最近的点，那么 NN(xi,xj)
等于 1，如果它是第二近的点,
NN(xi,xj)等于 2，以此类推。下图是 MND
量度标准的计算。
?NN(A,B)=NN(B,A)=1→ MND(A,B)=2
?NN(B,C)=1,NN(C,B)=2→ MND(B,C)=3
?通过对图 6-3加入 3个新点 D,E,F得出图 6-4。
?因为环境改变了，样本点 A,B,C之间的
距离也改变了。
?NN(A,B)=1,NN(B,A)=4→ MND(A,B)=5
?NN(B,C)=1,NN(C,B)=2→ MND(B,C)=3
?尽管 A和 B未动，但因引入离 A近的其他点，
使 A和 B的 MND增大了,B和 C点变得比 A和
B具有更高的相似度。
?一般地，根据样本之间的一个距离度量标
准，可以确定类 (样本集 )间的距离度标准，
这些度量标准对评价一个聚类过程的质量
是必不可少的。广泛应用于 Ci和 Cj的距离度
量标准是,
1)Dmin(Ci,Cj)=min|pi-pj|
2)Dmean(Ci,Cj)=|mi-mj| 其中 mi和 mj是 Ci
和 Cj的质心
3)Davg(Ci,Cj)=1/(ninj)∑∑|pi-pj|
4)Dmax(Ci,Cj)=max|pi-pj|
