6.3 凝聚层次聚类
?在层次聚类分析中，输入中不指定要分成
的类的个数。系统的输入为 (X,s)，系统的
输出是类的层次。
?大多数层次聚类过程不是基于最优的思想，
而是通过反复的分区直至收敛，找出一些
近似的、未达最优标准的解决方案。
?层次聚类算法分为：分裂算法和凝聚算法。
?分区算法从整个样本集开始，将它分成几个
子集，然后把每个子集分成更小的集合，依
次下去，最终，生成一个由粗略到精细的分
区序列。
?凝聚算法首先把每一个对象当作一个初始类，
然后将这些类合并一个更粗略的分区，反复
合并直至得到比较精细的分区，其过程是自
底向上的过程，分区从精细到粗糙。
?凝聚算法又分为单链接和全链接算法，两者
不同之处仅在于它们描述一对类的相似度的
方法。
?单链接算法基于两类之间的距离是从两个
类中抽取的两对样本 (一个取自第一类，另
一个取自第二个 )的距离中最小值。
?全链接算法基于两类间的距离是每对样本
的距离中的最大值。
?下图为两种算法的图解说明。
?凝聚聚类算法的基本步骤,
1.把每一个样本作为一个类，为所有不同的
无序样本对的类间距离构造一个序列，然
后按升序对这个序列进行排序。
2.通过已排序的距离序列，对于每一个不同
的阈值 dk形成一个样本图，图中将距离比 dk
更近的各对样本合并成一个新的类。如果
所有的样本都是这个图的元素则停止，否
则，重复该步骤。
3.这个算法的输出是一个嵌套层次图，可以
用希望的相似水平去截取，在相应的子图
中生成一个由简单联合标识的分区 (类聚 )
?例如：二维样本集共 5个点 {x1,x2,x3,x4,x5}
x1=(0,2),x2=(0,0),x3=(1.5,0),x4=(5.0),x5=(5,2)
其图形化表示如下图,
?第一步：计算欧氏距离。
d(x1,x2)=2,d(x1,x3)=2.5 d(x1,x4)=5.4 d(x1,x5)=5
d(x2,x3)=1.5,d(x2,x4)=5,d(x2,x5)=5.29
d(x3,x4)=3.5,d(x3,x5)=4.03
d(x4,x5)=2
按升序排列,
d(x2,x3)=1.5,d(x1,x2)=2,d(x4,x5)=2,d(x1,x3)=2.5,
d(x3,x4)=3.5,d(x3,x5)=4.03,d(x2,x4)=5,d(x1,x5)=5,
d(x2,x5)=5.29,d(x1,x4)=5.39
?第二步：单链接算法。
按最小距离合并 x2和 x3，生成新类
{x2,x3}，其距离为 1.5。 x4和 x5合并成
一个新类 {x4,x5}，其距离为 2。同时，
类 {x2,x3}和 {x1}间的最小距离也是 2.0，
将其合并成一个新类 {x1,x2,x3},其距
离为 2。最后，两个类 {x1,x2,x3}和 {x4,x5}
可以以更高的级别进行合并，其最小
单链接距离为 3.5。树状图如下,
?第三步：选择相似度阈值 s=2.2，从图可以
得出单链接算法最终生成类,{x1,x2,x3}和
{x4,x5}
?第二步：全链接算法。
按最小距离合并 x2和 x3，生成新类
{x2,x3}，其距离为 1.5。 x4和 x5合并成
一个新类 {x4,x5}，其距离为 2。而类
{x2,x3}和 {x1}间的最大距离是 2.5，将其
合并成一个新类 {x1,x2,x3} 。最后，两
个类 {x1,x2,x3}和 {x4,x5}可以以更高的级
别进行合并，其最大单链接距离为 5.4。
树状图如下,
?第三步：选择相似度阈值 s=2.2，从图可以
得出全链接算法最终生成类,{x1},{x2,x3}
和 {x4,x5}
?可见单链接和全链接算法得到类不同。
6.4 分区聚类
?每个分区聚类算法得到都是数据的一个分区,
而不是通过层次方法生成树状图这样的聚类
结构。分区聚类大规模数据集的应用场合。
?最常用的分区聚类方法是基于方差标准的方
法。其总的目标是根据固定的类数生成一个
总体方差最小的分区。
?假设给定的 n维空间上的 n个样本集被以某种
方式分区为 K个类 {C1,C2,…,C k}。每个类包括
nk个样本。每个样本就是一个类，因此
∑nk=N(k=1,…,K)
?用类的重心或下面的公式定义类 CK的均值
向量 Mk,
?
?
??
kn
i
kikk Mxe
1
22 )(
?
?
?
K
k
kk eE
1
22
?
?
?
kn
i
ikkk xnM
1
)/1(
?其中,xik是属于类 Ck的第 i个样本,Ck的
方差是 Ck中的每个样本及其重心的欧氏
距离的平方和。这个误差称为类内误差,
?包含 K个类的整个聚类空间的平方误差是
类内方差的和,
?方差聚类方法的目标是对于给出的 K，找出
使上式最小的包含 K个类的一个分区。
?K-平均分区聚类算法是最简单、最常用的
使用方差准则的算法。
?它从一个随机的初始分区开始，根据样本
和类间的相似度，将样本重新分配给各类，
直到达到一定的收敛准则。通常情况下，
当样本从一个类被分配到另一个类时，如
果不会出现总体误差减小的情况，便满足
收敛准则。
? K-平均算法的基本步骤,
1,选择一个含有随机选择样本的 K个类的初
始分区，然后计算这些类有重心。
2,通过将样本分配给与其重心距离最近的类
生成一个新分区。
3,用类的重心来计算新类的中心距离。
4,重复步骤 2和 3直到求出准则函数的最优解
(或直到类的成员稳定 )。
? 例如：由图 6-6给出的数据，采用 K-平均
算法聚类分析。
?假定要求的类的数量是两个，开始时，随机
形成两个类,C1={x1,x2,x4}和 C2={x3,x5}
?这两个类的重心是,
M1={(0+0+5)/3,(2+0+0)/3}={1.66,0.66}
M2={(1.5+5)/2,(0+2)/2}={3.25,1.00}
?类内方差,
e12=[(0-1.66)2+(2-0.66)2]+[(0-1.66)2+(0-0.66)2]+
[(5-1.66)2+(0-0.66)2]=19.36
e22=[(1.5-3.25)2+(0-1)2]+[(5-3.25)2+(2-1)2]=8.12
?总体平方误差,
E2= e12+ e22=19.36+8.12=27.48
?依据距离重心 M1和 M2的最小距离，再分配所
有的样本时，类内样本重新分布将是,
d(M1,x1)=((0-1.66)2+(2-0.66)2)1/2=2.14
和 d(M2,x1)=3.40→x 1∈ C1
d(M1,x2)=1.79和 d(M2,x2)=3.40→x 2∈ C1
d(M1,x3)=0.83和 d(M2,x3)=2.01→x 3∈ C1
d(M1,x4)=3.41和 d(M2,x4)=2.01→x 4∈ C2
d(M1,x5)=3.60和 d(M2,x5)=2.01→x 5∈ C2
? 新类 C1={x1,x2,x3}和 C2={x4,x5}的新重心是,
M1={0.5,0.67} ; M2={5.0,1.0}
? 新类内误差和总体平方误差是,
e12=4.17,e22=2.00,E=6.17
?经第一次迭代后，总体误差显著减小。本
例第一次迭代也是最后一次迭代，因为重
新计算重心距离分配类与第一次迭代相同，
所以算法停止。
?在使用迭代的分区聚类程序时，一个大的
缺憾是缺少一个可应用于初始分区的最佳
方向、更新分区、调整类数和停止准则等
方面的向导。
?K-平均算法对噪声和异常点非常敏感，因
为它们对均值的影响相当大。
?K-中心点算法对噪声和异常点不敏感 。
6.5 增量聚类
? 现在，有些应用涉及到成千上万个高维数
据集。由于数据集规模太大，不可能把整
个数据集储存在主存储器里。
? 有三个方法可处理这类数据的聚类分析,
1,可以把数据集存储在辅助存储器里，对数
据的各个子集进行独立地聚类，然后合并
生成整个数据集的聚类，称为分治方法。
2,可以使用增量聚类算法。
3,可以并行实现聚类算法，并行计算的好处
是提高了分治方法的效率。
? 增量聚类算法的步骤,
1,把第一个数据项分配到第一个类里。
2,考虑下一个数据项，把它分配到目前某个
类中或一个新类中。它基于一些准则的，
例如新数据项到目前类的重心的距离。在
这种情况下，每次添加一个新数据项到一
个目前的类中时，需要重新计算重心的值。
3,重复步骤 2，直到所有的数据样本都被聚
类完毕。
? 增量算法是非迭代的，需要主存储空间非
常小，所需要的时间也很少，即使采用迭
代算法，所需的计算时间也不会显著增加。
? 增量聚类存在的一个明显的缺点：对样本
的顺序非常敏感。不同的顺序会产生不同
的分区。
? 例如：仍然采用上例的数据集。假定样本
的顺序是 x1,x2,x3,x4,x5，则类相似度阈值
水平是 δ=3。
1,第一样本 x1为第一个类 C1={x1}。 C1的重心
为 M1={0,2}。
2,开始分析其他样本。
a)把第二个样本 x2和 M1比较，距离 d为,
d(x2,M1)=(02+22)1/2=2.0<3
因此,x2属于类 C1,新的重心是,
M1={0,1}
b)第三个样本 x3和重心 M1比较,
d(x3,M1)=(1.52+12)1/2=1.8<3
x3∈ C1 → C 1 ={x1,x2,x3} →M 1={0.5,0.66}
c)第四个样本 x4和重心 M1比较,
d(x4,M1)=(4.52+0.662)1/2=4.55>3
x4 → C 2 ={x4} →M 2={5,0}
d)第五个样本和这两个类的重心相比较,
d(x5,M1)=(4.52+1.442)1/2=4.72>3
d(x5,M2)=(02+22)1/2=2<3
x5∈ C2 → C 2 ={x4,x5} →M 2={5,1}
3,分析完所有的样本，聚类结果是获得两个
类,C1 ={x1,x2,x3}和 C2 ={x4,x5}
? 如果观察的样本的顺序不同，聚类结果也
不同。
? 对于大多数分区聚类算法，包括迭代方法，
都是通过该类的特征向量 CF给出的类的简
要表示，每个类的参数由 3部分组成，类
中点 (样本 )的个数，类的重心和类的半径。
? 类的半径定义为类中的点到重心的平均平
方距离的平方根 (平均类内方差 )。
? 当添加和删除类中的点时，可以通过旧的
CF来计算新 CF，而不需要用类中所有点
去计算新的 CF，这一点非常重要。
? 如果样本是分类的数据，就没有办法计算
类的重心来表述类。另一种算法 K-最近邻
法可用于估计样本和目前类间的距离 (或相
似度 ) 。
? 算法的基本步骤,
1,计算新的样本到所有已被分类的旧样本之
间的距离。
2,把这些距离按升序排列，选Ｋ个最近值的
样本。
3,运用投票原理，把新样本添加 (分类 )给已
选的Ｋ个样本中最大的类。
? 例如：给出 6个 6维分类的样本,
X1={A,B,A,B,C,B}
X2={A,A,A,B,A,B}
X3={B,B,A,B,A,B}
X4={B,A,B,A,C,A}
X5={A,C,B,A,B,B}
X6={A,C,B,A,B,B}
? 它们被聚集成两个类,
C1={x1,x2,x3}和 C2={x4,x5,x6}。
? 新样本 Y={A,C,A,B,C,A}属于哪一类？
? 运用Ｋ -最近邻算法，第一步求出新样本和
其他所有已聚类样本间的距离。
采用 SMC求出样本间的相似度，代替
求样本间的距离。
SMC(Y,X1)=4/6=0.66 SMC(Y,X4)=4/6=0.66
SMC(Y,X2)=3/6=0.50 SMC(Y,X5)=2/6=0.33
SMC(Y,X3)=2/6=0.33 SMC(Y,X6)=2/6=0.33
? 用 1-最近邻规则 (K=1)，新样本不能被分类。
因为 x1和 x4具有最高相似度 (最小距离 )，其
中一个在 C1，另一个在 C2 。
? 用３ -最近邻规则 (K=３ )，选取 3个最大相
似度中，有两个在 C1，因此 Y分给 C1。
?在层次聚类分析中，输入中不指定要分成
的类的个数。系统的输入为 (X,s)，系统的
输出是类的层次。
?大多数层次聚类过程不是基于最优的思想，
而是通过反复的分区直至收敛，找出一些
近似的、未达最优标准的解决方案。
?层次聚类算法分为：分裂算法和凝聚算法。
?分区算法从整个样本集开始，将它分成几个
子集，然后把每个子集分成更小的集合，依
次下去，最终，生成一个由粗略到精细的分
区序列。
?凝聚算法首先把每一个对象当作一个初始类，
然后将这些类合并一个更粗略的分区，反复
合并直至得到比较精细的分区，其过程是自
底向上的过程，分区从精细到粗糙。
?凝聚算法又分为单链接和全链接算法，两者
不同之处仅在于它们描述一对类的相似度的
方法。
?单链接算法基于两类之间的距离是从两个
类中抽取的两对样本 (一个取自第一类，另
一个取自第二个 )的距离中最小值。
?全链接算法基于两类间的距离是每对样本
的距离中的最大值。
?下图为两种算法的图解说明。
?凝聚聚类算法的基本步骤,
1.把每一个样本作为一个类，为所有不同的
无序样本对的类间距离构造一个序列，然
后按升序对这个序列进行排序。
2.通过已排序的距离序列，对于每一个不同
的阈值 dk形成一个样本图，图中将距离比 dk
更近的各对样本合并成一个新的类。如果
所有的样本都是这个图的元素则停止，否
则，重复该步骤。
3.这个算法的输出是一个嵌套层次图，可以
用希望的相似水平去截取，在相应的子图
中生成一个由简单联合标识的分区 (类聚 )
?例如：二维样本集共 5个点 {x1,x2,x3,x4,x5}
x1=(0,2),x2=(0,0),x3=(1.5,0),x4=(5.0),x5=(5,2)
其图形化表示如下图,
?第一步：计算欧氏距离。
d(x1,x2)=2,d(x1,x3)=2.5 d(x1,x4)=5.4 d(x1,x5)=5
d(x2,x3)=1.5,d(x2,x4)=5,d(x2,x5)=5.29
d(x3,x4)=3.5,d(x3,x5)=4.03
d(x4,x5)=2
按升序排列,
d(x2,x3)=1.5,d(x1,x2)=2,d(x4,x5)=2,d(x1,x3)=2.5,
d(x3,x4)=3.5,d(x3,x5)=4.03,d(x2,x4)=5,d(x1,x5)=5,
d(x2,x5)=5.29,d(x1,x4)=5.39
?第二步：单链接算法。
按最小距离合并 x2和 x3，生成新类
{x2,x3}，其距离为 1.5。 x4和 x5合并成
一个新类 {x4,x5}，其距离为 2。同时，
类 {x2,x3}和 {x1}间的最小距离也是 2.0，
将其合并成一个新类 {x1,x2,x3},其距
离为 2。最后，两个类 {x1,x2,x3}和 {x4,x5}
可以以更高的级别进行合并，其最小
单链接距离为 3.5。树状图如下,
?第三步：选择相似度阈值 s=2.2，从图可以
得出单链接算法最终生成类,{x1,x2,x3}和
{x4,x5}
?第二步：全链接算法。
按最小距离合并 x2和 x3，生成新类
{x2,x3}，其距离为 1.5。 x4和 x5合并成
一个新类 {x4,x5}，其距离为 2。而类
{x2,x3}和 {x1}间的最大距离是 2.5，将其
合并成一个新类 {x1,x2,x3} 。最后，两
个类 {x1,x2,x3}和 {x4,x5}可以以更高的级
别进行合并，其最大单链接距离为 5.4。
树状图如下,
?第三步：选择相似度阈值 s=2.2，从图可以
得出全链接算法最终生成类,{x1},{x2,x3}
和 {x4,x5}
?可见单链接和全链接算法得到类不同。
6.4 分区聚类
?每个分区聚类算法得到都是数据的一个分区,
而不是通过层次方法生成树状图这样的聚类
结构。分区聚类大规模数据集的应用场合。
?最常用的分区聚类方法是基于方差标准的方
法。其总的目标是根据固定的类数生成一个
总体方差最小的分区。
?假设给定的 n维空间上的 n个样本集被以某种
方式分区为 K个类 {C1,C2,…,C k}。每个类包括
nk个样本。每个样本就是一个类，因此
∑nk=N(k=1,…,K)
?用类的重心或下面的公式定义类 CK的均值
向量 Mk,
?
?
??
kn
i
kikk Mxe
1
22 )(
?
?
?
K
k
kk eE
1
22
?
?
?
kn
i
ikkk xnM
1
)/1(
?其中,xik是属于类 Ck的第 i个样本,Ck的
方差是 Ck中的每个样本及其重心的欧氏
距离的平方和。这个误差称为类内误差,
?包含 K个类的整个聚类空间的平方误差是
类内方差的和,
?方差聚类方法的目标是对于给出的 K，找出
使上式最小的包含 K个类的一个分区。
?K-平均分区聚类算法是最简单、最常用的
使用方差准则的算法。
?它从一个随机的初始分区开始，根据样本
和类间的相似度，将样本重新分配给各类，
直到达到一定的收敛准则。通常情况下，
当样本从一个类被分配到另一个类时，如
果不会出现总体误差减小的情况，便满足
收敛准则。
? K-平均算法的基本步骤,
1,选择一个含有随机选择样本的 K个类的初
始分区，然后计算这些类有重心。
2,通过将样本分配给与其重心距离最近的类
生成一个新分区。
3,用类的重心来计算新类的中心距离。
4,重复步骤 2和 3直到求出准则函数的最优解
(或直到类的成员稳定 )。
? 例如：由图 6-6给出的数据，采用 K-平均
算法聚类分析。
?假定要求的类的数量是两个，开始时，随机
形成两个类,C1={x1,x2,x4}和 C2={x3,x5}
?这两个类的重心是,
M1={(0+0+5)/3,(2+0+0)/3}={1.66,0.66}
M2={(1.5+5)/2,(0+2)/2}={3.25,1.00}
?类内方差,
e12=[(0-1.66)2+(2-0.66)2]+[(0-1.66)2+(0-0.66)2]+
[(5-1.66)2+(0-0.66)2]=19.36
e22=[(1.5-3.25)2+(0-1)2]+[(5-3.25)2+(2-1)2]=8.12
?总体平方误差,
E2= e12+ e22=19.36+8.12=27.48
?依据距离重心 M1和 M2的最小距离，再分配所
有的样本时，类内样本重新分布将是,
d(M1,x1)=((0-1.66)2+(2-0.66)2)1/2=2.14
和 d(M2,x1)=3.40→x 1∈ C1
d(M1,x2)=1.79和 d(M2,x2)=3.40→x 2∈ C1
d(M1,x3)=0.83和 d(M2,x3)=2.01→x 3∈ C1
d(M1,x4)=3.41和 d(M2,x4)=2.01→x 4∈ C2
d(M1,x5)=3.60和 d(M2,x5)=2.01→x 5∈ C2
? 新类 C1={x1,x2,x3}和 C2={x4,x5}的新重心是,
M1={0.5,0.67} ; M2={5.0,1.0}
? 新类内误差和总体平方误差是,
e12=4.17,e22=2.00,E=6.17
?经第一次迭代后，总体误差显著减小。本
例第一次迭代也是最后一次迭代，因为重
新计算重心距离分配类与第一次迭代相同，
所以算法停止。
?在使用迭代的分区聚类程序时，一个大的
缺憾是缺少一个可应用于初始分区的最佳
方向、更新分区、调整类数和停止准则等
方面的向导。
?K-平均算法对噪声和异常点非常敏感，因
为它们对均值的影响相当大。
?K-中心点算法对噪声和异常点不敏感 。
6.5 增量聚类
? 现在，有些应用涉及到成千上万个高维数
据集。由于数据集规模太大，不可能把整
个数据集储存在主存储器里。
? 有三个方法可处理这类数据的聚类分析,
1,可以把数据集存储在辅助存储器里，对数
据的各个子集进行独立地聚类，然后合并
生成整个数据集的聚类，称为分治方法。
2,可以使用增量聚类算法。
3,可以并行实现聚类算法，并行计算的好处
是提高了分治方法的效率。
? 增量聚类算法的步骤,
1,把第一个数据项分配到第一个类里。
2,考虑下一个数据项，把它分配到目前某个
类中或一个新类中。它基于一些准则的，
例如新数据项到目前类的重心的距离。在
这种情况下，每次添加一个新数据项到一
个目前的类中时，需要重新计算重心的值。
3,重复步骤 2，直到所有的数据样本都被聚
类完毕。
? 增量算法是非迭代的，需要主存储空间非
常小，所需要的时间也很少，即使采用迭
代算法，所需的计算时间也不会显著增加。
? 增量聚类存在的一个明显的缺点：对样本
的顺序非常敏感。不同的顺序会产生不同
的分区。
? 例如：仍然采用上例的数据集。假定样本
的顺序是 x1,x2,x3,x4,x5，则类相似度阈值
水平是 δ=3。
1,第一样本 x1为第一个类 C1={x1}。 C1的重心
为 M1={0,2}。
2,开始分析其他样本。
a)把第二个样本 x2和 M1比较，距离 d为,
d(x2,M1)=(02+22)1/2=2.0<3
因此,x2属于类 C1,新的重心是,
M1={0,1}
b)第三个样本 x3和重心 M1比较,
d(x3,M1)=(1.52+12)1/2=1.8<3
x3∈ C1 → C 1 ={x1,x2,x3} →M 1={0.5,0.66}
c)第四个样本 x4和重心 M1比较,
d(x4,M1)=(4.52+0.662)1/2=4.55>3
x4 → C 2 ={x4} →M 2={5,0}
d)第五个样本和这两个类的重心相比较,
d(x5,M1)=(4.52+1.442)1/2=4.72>3
d(x5,M2)=(02+22)1/2=2<3
x5∈ C2 → C 2 ={x4,x5} →M 2={5,1}
3,分析完所有的样本，聚类结果是获得两个
类,C1 ={x1,x2,x3}和 C2 ={x4,x5}
? 如果观察的样本的顺序不同，聚类结果也
不同。
? 对于大多数分区聚类算法，包括迭代方法，
都是通过该类的特征向量 CF给出的类的简
要表示，每个类的参数由 3部分组成，类
中点 (样本 )的个数，类的重心和类的半径。
? 类的半径定义为类中的点到重心的平均平
方距离的平方根 (平均类内方差 )。
? 当添加和删除类中的点时，可以通过旧的
CF来计算新 CF，而不需要用类中所有点
去计算新的 CF，这一点非常重要。
? 如果样本是分类的数据，就没有办法计算
类的重心来表述类。另一种算法 K-最近邻
法可用于估计样本和目前类间的距离 (或相
似度 ) 。
? 算法的基本步骤,
1,计算新的样本到所有已被分类的旧样本之
间的距离。
2,把这些距离按升序排列，选Ｋ个最近值的
样本。
3,运用投票原理，把新样本添加 (分类 )给已
选的Ｋ个样本中最大的类。
? 例如：给出 6个 6维分类的样本,
X1={A,B,A,B,C,B}
X2={A,A,A,B,A,B}
X3={B,B,A,B,A,B}
X4={B,A,B,A,C,A}
X5={A,C,B,A,B,B}
X6={A,C,B,A,B,B}
? 它们被聚集成两个类,
C1={x1,x2,x3}和 C2={x4,x5,x6}。
? 新样本 Y={A,C,A,B,C,A}属于哪一类？
? 运用Ｋ -最近邻算法，第一步求出新样本和
其他所有已聚类样本间的距离。
采用 SMC求出样本间的相似度，代替
求样本间的距离。
SMC(Y,X1)=4/6=0.66 SMC(Y,X4)=4/6=0.66
SMC(Y,X2)=3/6=0.50 SMC(Y,X5)=2/6=0.33
SMC(Y,X3)=2/6=0.33 SMC(Y,X6)=2/6=0.33
? 用 1-最近邻规则 (K=1)，新样本不能被分类。
因为 x1和 x4具有最高相似度 (最小距离 )，其
中一个在 C1，另一个在 C2 。
? 用３ -最近邻规则 (K=３ )，选取 3个最大相
似度中，有两个在 C1，因此 Y分给 C1。
