第六章 聚类分析(2)

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.5d(x1,x4)=5.4d(x1,x5)=5d(x2,x3)=1.5,d(x2,x4)=5,d(x2,x5)=5.29d(x3,x4)=3.5,d(x3,x5)=4.03d(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,…,Ck}。每个类包括nk个样本。每个样本就是一个类，因此∑nk=N(k=1,…,K)用类的重心或下面的公式定义类CK的均值向量Mk:knikikkMxe122)(KkkkeE122kniikkkxnM1)/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.36e22=[(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→x1∈C1d(M1,x2)=1.79和d(M2,x2)=3.40→x2∈C1d(M1,x3)=0.83和d(M2,x3)=2.01→x3∈C1d(M1,x4)=3.41和d(M2,x4)=2.01→x4∈C2d(M1,x5)=3.60和d(M2,x5)=2.01→x5∈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.03因此，x2属于类C1，新的重心是：M1={0,1}b)第三个样本x3和重心M1比较：d(x3,M1)=(1.52+12)1/2=1.83x3∈C1→C1={x1,x2,x3}→M1={0.5,0.66}c)第四个样本x4和重心M1比较：d(x4,M1)=(4.52+0.662)1/2=4.553x4→C2={x4}→M2={5,0}d)第五个样本和这两个类的重心相比较：d(x5,M1)=(4.52+1.442)1/2=4.723d(x5,M2)=(02+22)1/2=23x5∈C2→C2={x4,x5}→M2={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.66SMC(Y,X4)=4/6=0.66SMC(Y,X2)=3/6=0.50SMC(Y,X5)=2/6=0.33SMC(Y,X3)=2/6=0.33SMC(Y,X6)=2/6=0.33用1-最近邻规则(K=1)，新样本不能被分类。因为x1和x4具有最高相似度(最小距离)，其中一个在C1，另一个在C2。用３-最近邻规则(K=３)，选取3个最大相似度中，有两个在C1，因此Y分给C1。