模式识别03-聚类分析.ppt

《模式识别03-聚类分析.ppt》由会员分享，可在线阅读，更多相关《模式识别03-聚类分析.ppt（56页珍藏版）》请在三一办公上搜索。

1、模式识别导论聚类分析,李金屏济南大学信息科学与工程学院 模式识别与智能系统研究所山东省网络环境智能计算技术重点实验室2011年9月,2023/11/15,济南大学 模式识别与智能系统研究所(R),2,目录,复习说明模式相似性测度类的定义、类间距离和聚类准则聚类算法总结和作业,2023/11/15,济南大学 模式识别与智能系统研究所(R),3,目录,复习说明模式相似性测度类的定义、类间距离和聚类准则聚类算法总结和作业,2023/11/15,济南大学 模式识别与智能系统研究所(R),4,复习,模式识别的基本过程为什么要进行特征提取？什么是特征？如何抽取和表示特征？识别和训练（两种训练方式）识别系统

2、的性能评价特征矢量的特点：随机性（为什么？）随机矢量的数字特征：有哪些？什么是正态分布（高斯分布）？写出一维和二维情况下的具体表达式和每个符号的具体含义。,2023/11/15,济南大学 模式识别与智能系统研究所(R),5,复习,根据模式识别的基本过程，讨论如何区分正常的楼房维修和爬楼盗窃？Key:维修：一般白天；安全工具；工作服；长时停留；有灯光等盗窃：一般夜间；主要徒手；夜行衣；不逗留；无灯光等当然前提是能够检测到移动目标和判定大小如何区分这两种水果（自动分拣机）：梨和桃子？Key:梨：青或黄；无沟；粗糙多斑点；尾桔蒂等桃：红或青；有沟；光滑少斑点；尾多尖等,2023/11/15,济南大学

3、 模式识别与智能系统研究所(R),6,目录,复习说明模式相似性测度类的定义、类间距离和聚类准则聚类算法总结和作业,2023/11/15,济南大学 模式识别与智能系统研究所(R),7,说明,特征的选取特征选取要合适特征选取不足有可能将不同类别判为一类特征过多可能有害无益假设根据已有特征已经能够正确分类新增加的特征与原有特征的关系：独立、不相关或者相关若独立或者不相关，则分类结果不变，但是增加负担；若相关，增加冗余；则重要特征占“比重”减少；导致误判增加和负担增加量纲要合适,2023/11/15,济南大学 模式识别与智能系统研究所(R),8,目录,复习说明模式相似性测度类的定义、类间距离和聚类准则

4、聚类算法总结和作业,2023/11/15,济南大学 模式识别与智能系统研究所(R),9,模式相似性测度,为了能够划分模式的类别，必须首先定义相似性测度，描述各个模式之间特征的相似程度。距离测度描述两个矢量x和y之间的距离d(x,y)应该满足如下公理：d(x,y)0，d(x,y)=0 iff x=y;d(x,y)=d(y,x);d(x,y)d(x,z)+d(z,y);需要说明，某些距离测度不满足公理3，只是在广义上称为距离。,2023/11/15,济南大学 模式识别与智能系统研究所(R),10,模式相似性测度,距离测度设x=(x1,x2,xn)T,y=(y1,y2,yn)T欧式距离（Euclid

5、ean）d(x,y)=|x-y|=i=1 n(xi-yi)21/2绝对值距离（Manhattan距离）d(x,y)=i=1 n|xi-yi|切氏距离（Chebyahev）d(x,y)=maxi|xi-yi|闵科夫斯基距离（Minkowski）d(x,y)=i=1 n(xi-yi)m1/m m=2,1,时分别是欧式距离、绝对值距离和切氏距离。,2023/11/15,济南大学 模式识别与智能系统研究所(R),11,模式相似性测度,距离测度马氏距离（Mahalanohis）设n维矢量xi和xj是矢量集x1,x2,xn中的两个矢量，其马氏距离d是：d2(xi,xj)=(xi-xj)T V-1(xi-x

6、j),2023/11/15,济南大学 模式识别与智能系统研究所(R),12,模式相似性测度,距离测度Camberra距离（Lance距离、Willims距离）能克服量纲引起的问题，但无法克服分量间的相关性。,2023/11/15,济南大学 模式识别与智能系统研究所(R),13,模式相似性测度,相似测度设x=(x1,x2,xn)T,y=(y1,y2,yn)T角度相似系数（夹角余弦）对于坐标系的旋转和尺度缩放是不变的，但对于一般的线性变换和坐标系的平移不具有不变性。,指数相似系数不受量纲变化影响。其中i2为相应分量的方差。,2023/11/15,济南大学 模式识别与智能系统研究所(R),14,匹配

7、测度有时特征只有两个状态，即二值特征。令a=ixiyi,b=I(1-xi)yi,c=I xi(1-yi),e=I(1-xi)(1-yi)Tanimoto测度,模式相似性测度,Rao测度,2023/11/15,济南大学 模式识别与智能系统研究所(R),15,拓展思维其他的匹配测度？相同特征的比例？即(1-1)和(0-0)在所有特征中占有的比例相同特征与不同特征的比例？,模式相似性测度,一个问题：特征空间中，两个特征矢量分别如下，计算其间不同距离：x=(1,1,0,1,0,0)T,y=(1,0,0,1,0,1)T x=(180,75,50)T,y=(170,70,55)T,如何获得这些特征不是模式

8、识别所研究的内容，是其他相关学科的研究范畴,2023/11/15,济南大学 模式识别与智能系统研究所(R),16,目录,复习说明模式相似性测度类的定义、类间距离和聚类准则聚类算法总结和作业,类的定义、类间距离和聚类准则,类的定义类间距离聚类准则,2023/11/15,济南大学 模式识别与智能系统研究所(R),17,2023/11/15,济南大学 模式识别与智能系统研究所(R),18,类的定义、类间距离和聚类准则,类的定义研究聚类算法，必须首先给出类的定义。不同类的定义，适合于不同的类内模式分布情况。只考虑距离层面的定义，相似测度和匹配测度可以类推。类定义一：集合S中任意两个元素xi和xj的距离

9、dij满足dijh则S对于阈值h组成一类。思考：这种定义，适合于哪种分布？Key:团簇状，各类相聚较远。,2023/11/15,济南大学 模式识别与智能系统研究所(R),19,类的定义、类间距离和聚类准则,2023/11/15,济南大学 模式识别与智能系统研究所(R),20,类的定义、类间距离和聚类准则,类的定义类定义二：集合S中任意两个元素xi和xj的距离dij满足则S对于阈值h组成一类。其中k为集合S中元素的个数。思考：这种定义，适合于哪种分布？Key:仍然是团簇状，各类相聚较远。,2023/11/15,济南大学 模式识别与智能系统研究所(R),21,类的定义、类间距离和聚类准则,类的定义

10、类定义三：集合S，对于其中任意一个元素xiS，都存在xj S，其距离dijh，则称S对于阈值h组成一类。思考：这种定义，适合于哪种分布？Key:长条状。,类的定义、类间距离和聚类准则,类的定义类间距离聚类准则,2023/11/15,济南大学 模式识别与智能系统研究所(R),22,2023/11/15,济南大学 模式识别与智能系统研究所(R),23,类的定义、类间距离和聚类准则,类间距离最近距离法两个类别k和l之间的最近距离：Dkl=minij dijdij表示xik和xjl之间的距离。如果l是由两类p和q合并而成，则有递推公式：Dkl=min Dkp,Dkq最远距离法两个类别k和l之间的最远距

11、离：Dkl=maxij dijdij表示xik和xjl之间的距离。如果l是由两类p和q合并而成，则有递推公式：Dkl=max Dkp,Dkq,2023/11/15,济南大学 模式识别与智能系统研究所(R),24,类的定义、类间距离和聚类准则,类间距离中间距离法三角形kpq边pq中线长的平方和：可以作为新类l=p q与k间的距离的递推公式。,2023/11/15,济南大学 模式识别与智能系统研究所(R),25,类的定义、类间距离和聚类准则,类间距离重心距离法：一个类的空间位置用重心表示，两个类的重心之间的距离作为二者的距离。设类p、q的重心分别是xp、xq，有样本np、nq。类l=p q，则nl

12、=np+nq。则l的重心为：另一个类k与l的距离平方是：Dkl2=(xk-xl)T(xk-xl)化简后得到：,2023/11/15,济南大学 模式识别与智能系统研究所(R),26,类的定义、类间距离和聚类准则,类间距离平均距离法两类p、q之间的距离可以定义为这两类元素之间的平均平方距离，即设类l=p q，则递推公式为：,类的定义、类间距离和聚类准则,类的定义类间距离聚类准则,2023/11/15,济南大学 模式识别与智能系统研究所(R),27,聚类准则类内距离准则设待分类的模式集合x1,x2,xN，在某种相似性测度的基础上被划分为c类ci(j);j=1,2,3,c;i=1,2,nj。显然，类内

13、聚类准则函数JW定义为：显然，JW越小越好。（误差平方和准则）特点：取决于类心的选取；同类样本分布密集，各类分布区域体积相差不大。,2023/11/15,济南大学 模式识别与智能系统研究所(R),28,类的定义、类间距离和聚类准则,聚类准则类间距离准则其中mj是类的模式平均矢量，m为总的模式平均矢量；nj是j类所含模式个数，N是所有模式的个数。加权的类间距离准则：,2023/11/15,济南大学 模式识别与智能系统研究所(R),29,类的定义、类间距离和聚类准则,拓展思维：两类情况下结果如何？与JWB关系如何？,聚类准则类内、类间距离准则希望聚类结果：类内距离越小越好，类间距离越大越好。设待分

14、类模式集xi;i=1,2,N。分成c类，j类含nj个模式。分类后各模式是xi(j);j=1,2,c;i=1,2,njj类内离差阵和总的类内离差阵分别如下：类间离差阵：总的离差阵：SW,SB和ST之间的关系：ST=SW+SB,2023/11/15,济南大学 模式识别与智能系统研究所(R),30,类的定义、类间距离和聚类准则,Can You Prove it?,2023/11/15,济南大学 模式识别与智能系统研究所(R),31,类的定义、类间距离和聚类准则,聚类准则类内、类间距离准则聚类的基本目标：TrSBmax；TrSWmin定义如下聚类准则：J1=TrSW-1 SBJ2=|SW-1 SB|J

15、3=TrSW-1 STJ4=|SW-1 ST|思考：这些准则应该越大越好，还是越小越好？,类的定义、类间距离和聚类准则,聚类准则基于模式与类核距离的准则函数前面是以一个点（类心）表示一类的位置并代替类核；缺点是：严重损失了各类在特征空间中所占子空间（类域）的形状和各类中各个模式在类域中的分布情况。引入类核：Kj=K(x,Vj)，表示j类的模式分布结构。其中Vj是j的一个参数集，x是特征空间中一点。还应该引入一个模式x与核Kj的距离以及准则函数；模式x与核Kj的距离依赖于Kj的构造。d(x,Kl)=minj d(x,Kj)x l。准则函数（显然，JKmin）：,2023/11/15,济南大学 模

16、式识别与智能系统研究所(R),32,2023/11/15,济南大学 模式识别与智能系统研究所(R),33,目录,复习说明模式相似性测度类的定义、类间距离和聚类准则聚类算法总结和作业,聚类算法,概述聚类算法有许多具体算法。从算法算法的基本策略看，可以分为三类：根据相似性阈值和最小距离原则的简单聚类方法。首先需要确定各聚类中心。按照最小距离原则不断将两类进行合并。各个模式首先自成一类，然后将距离最小的两类合并成一类。此过程不断重复，直至满足条件。该算法类心不断修正，但模式类别一旦指定就不再改变。依据准则函数的动态聚类法是一个准则函数取极值的优化过程。类心不断修正，各模式类别有不断改变。例如C-均值

17、、ISODATA法、近邻函数法等,2023/11/15,济南大学 模式识别与智能系统研究所(R),34,聚类算法,相似性阈值和最小距离准则的简单聚类法（1）基本思想：计算各个特征矢量到聚类中心的距离并和阈值（门限）T进行比较，决定归属哪一类或作为新的一个类心。常用欧氏距离。算法原理：(1)取任意一个模式特征向量作为第一个聚类中心。例如，令1类的中心z1=x1。(2)计算下一个模式特征矢量x2到z1的距离d21。如果d21T，则建立新的一类2，其中心z2=x2；若d21T，则x21。,2023/11/15,济南大学 模式识别与智能系统研究所(R),35,聚类算法,相似性阈值和最小距离准则的简单聚

18、类法（2）(3)假如已有聚类中心z1,z2,zk,计算尚未确定类别的模式特征矢量xi到各类别中心zj(j=1,2,k)的距离dij。若dijT（j=1,2,k），则xi作为新的一类k+1的中心，zk+1=xi；否则，如果dl=minj dij，则指判xil。检查是否所有的模式都分划完类别，如果分划完毕则结束；否则返回(3)。性能分析：计算简单。类心一经确定不再改变，模式一旦指判也不改变；故依赖于距离门限选取、待分类特征矢量参与分类的次序即聚类中心的选取等。参数和次序不同，结果可能会有差别。当有特征矢量先验知识来指导门限T及初始中心z1的选取时，往往结果合理。,2023/11/15,济南大学 模

19、式识别与智能系统研究所(R),36,聚类算法,聚类算法,最大最小距离法（1）基本思想：以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。例：10个模式样本点：x1(0 0),x2(3 8),x3(2 2),x4(1 1),x5(5 3),x6(4 8),x7(6 3),x8(5 4),x9(6 4),x10(7 5),2023/11/15,济南大学 模式识别与智能系统研究所(R),38,聚类算法,最大最小距离法（2）第一步：选任意一个模式样本作为第1个聚类中心，如z1=x1第二步：选距离z1最远的样本作为第2个聚类中心。经计算，|x6z1|最大，所以z2=x6第三步：逐个计算其余各模

20、式样本xi,i=1,2,N与z1,z2之间的距离，即di1=|xiz1|，di2=|xiz2|并选出其中的最小距离min(di1,di2)，i=1,2,N第四步：在所有模式样本的最小值中选出最大距离，若该最大值达到|z1z2|的一定比例以上，则相应的样本点取为第3个聚类中心z3，即若maxmin(di1,di2),i=1,2,N|z1z2|，则z3=xi。否则，若无新聚类中心，则找聚类中心过程结束。,聚类算法,最大最小距离法（3）第五步：若有z3存在，则计算maxmin(di1,di2,di3),i=1,2,N。若该值超过|z1z2|的一定比例，则存在z4，否则找聚类中心的过程结束。此例无z4

21、。第六步：将模式样本xi,i=1,2,N按最近距离分到最近的聚类中心：z1=x1：x1,x3,x4为第一类z2=x6：x2,x6为第二类z3=x7：x5,x7,x8,x9,x10为第三类,聚类算法,谱系聚类法（1）Hierarchical Clustering Method，谱系聚类法，又称为系统聚类法、层次聚类法。算法步骤：第一步：设初始模式样本共有N个，每个样本自成一类，即建立N类，G1(0),G2(0),GN(0)。计算各类之间的距离（初始时即为各样本间的距离），得到一个NN维的距离矩阵D(0)。这里，标号(0)表示聚类开始运算前的状态。第二步：假设前一步聚类运算中已求得距离矩阵D(n)

22、，n为逐次聚类合并的次数，则求D(n)中的最小元素。如果它是Gi(n)和Gj(n)两类之间的距离，则将Gi(n)和Gj(n)两类合并为一类，由此建立新的分类：G1(n+1),G2(n+1),2023/11/15,济南大学 模式识别与智能系统研究所(R),41,聚类算法,谱系聚类法（2）第三步：计算合并后新类别之间的距离矩阵，得D(n+1)。计算Gij(n+1)与其它没有发生合并的G1(n+1),G2(n+1),之间的距离，可采用多种不同的距离计算准则进行计算。返回第二步，重复计算及合并，直到得到满意的分类结果。例如：达到所需的聚类数目，或D(n)中的最小分量超过给定的阈值D等。,2023/11

23、/15,济南大学 模式识别与智能系统研究所(R),42,聚类算法,谱系聚类法（3）说明：可以利用之前介绍的有关距离定义和类间距离递推公式。类间距离定义不同，聚类过程也不同。在迭代过程中，距离矩阵的最小元素值不断改变。如果有单调不减关系则称类间距离对于类的合并具有单调性。最近距离法、最远距离法、平均法等类间距离都有该性质，重心法无此性质。练习：6个样本，按照最小距离原则进行聚类（请聚成两类）：x1=(0,3,1,2,0)T,x2=(0,3,0,1,0)T,x3=(3,3,0,0,1)T,x4=(1,1,0,2,0)T,x5=(3,2,1,2,1)T,x6=(4,1,1,1,0)T,2023/11

24、/15,济南大学 模式识别与智能系统研究所(R),43,聚类算法,C-均值（1）这是一种动态聚类法（Dynamic Clustering Algorithm）。前述算法特点：一旦模式划分后后续不再改变。动态聚类技术要点：确定模式和聚类的距离测度。一般采用欧氏距离。为能反映模式分布结构，可以采用马氏距离；设均矢为，斜方差阵，则距离为d2=(x-)T-1(x-)确定评估聚类质量的准则函数。确定模式分划及聚类合并或分裂的规则。,2023/11/15,济南大学 模式识别与智能系统研究所(R),44,聚类算法,C-均值（2）动态聚类基本步骤：建立初始聚类中心，进行初始聚类；计算模式和类的距离，调整模式类

25、别；计算各聚类的参数，删除、合并或分裂一些聚类；从初始聚类开始，运用迭代算法动态地改变模式类别和聚类中心，使得准则函数取得极值或者设定参数达到设计要求。,2023/11/15,济南大学 模式识别与智能系统研究所(R),45,聚类算法,C-均值（3）类的数目c是预先取定的。算法步骤：任选c个模式特征矢量作为初始聚类中心：z1(0),z2(0),zc(0),令k=0.将待分类的模式特征矢量集xi中每个模式按照最小距离原则分划给c类中的某一类，即If dil(k)=minjdij(k)，i=1,2,N Then xil(k+1)k表示迭代次数。于是产生新的聚类j(k+1)(j=1,2,c),聚类算法

26、,C-均值（4）计算重新分类后的各类心其中，j=1,2,c;nj(k+1)为j(k+1)类中所含模式的个数。如果zj(k+1)=zj(k)(j=1,2,c)，则结束；否则，k=k+1，转至(2)。说明：本算法是收敛的。,聚类算法,C-均值（5）性能分析：方法简单。这种算法的类数是确定的。取定的类别数目和初始的聚类中心影响很大。模式分布呈现类内团簇状，则效果很好。实际应用中，应该试探不同的c值和选择不同的初始类心，以便获得更优结果。可以进行按批修改和逐个修改。,聚类算法,C-均值（6）改进：可以让类数c从较小值逐步增加，准则函数J将逐步增加。做J-c曲线，找到曲率变化最大点，此时的类数比较接近最

27、优类数。（许多情况下无此明显点）初始聚类中心选取凭经验将模式随机分成c类，计算每类中心作为初始中心用相距最远的c个特征点作为初始类心（用最大最小距离法）选取密度最大的特征点作为初始类心。求每个特征点为球心，某个d0为半径的球形域中特征点个数（定义为该点的密度），选取密度最大的特征点作为第一个类心。然后在与第一个类心距离d的那些特征点中选取另一个密度最大的特征点作为第二个类心；以此类推。,聚类算法,C-均值（7）改进：用类核代替类心一个点往往不能充分反映该类的模式分布结构。当类的分布是球状或者近似球状时，效果尚可。定义类核函数Kj=Kj(x,Vj)，表示类j的模式分布情况，其中Vj是关于类j的一

28、个参数集。为了刻画x与j的接近程度，还应规定一个模式特征矢量x到核Kj的距离d2(xi,Kj)。马氏距离就是其中一种：d2(xi,j)=(xi-j)T-1(xi-j)主轴核函数：当已知各类样本分别在相应主轴附近分布时。Kj(x,Vj)=UjTx其中Uj=(u1,u2,umj)是j类的统计协方差矩阵的mj个最大特征值所对应的已规格化的特征矢量做成的矩阵。,2023/11/15,济南大学 模式识别与智能系统研究所(R),51,目录,复习说明模式相似性测度类的定义、类间距离和聚类准则聚类算法总结和作业,2023/11/15,济南大学 模式识别与智能系统研究所(R),52,总结和作业,特征选取时应该注

29、意的问题特征选取要合适特征选取不足有可能将不同类别判为一类特征过多可能有害无益量纲要合适相似性测度有哪些？距离测度：闵氏距离的特殊性；马氏距离的重要意义相似测度：角度或者方向是否一致匹配测度：针对二值特征类的定义有些适于团簇状，有些适于长条状；当然还有其他形状,总结和作业,类间距离测度方法最近距离法；最远距离法；中间距离法；重心距离法；平均距离法聚类的准则函数类内距离准则、类间距离准则、类内类间距离准则；基于模式与类核距离的准则函数聚类算法相似性阈值和最小距离准则的简单聚类法最大最小距离算法谱系聚类法动态聚类法（C-均值）：多种改进思路,2023/11/15,济南大学 模式识别与智能系统研究所

30、(R),53,2023/11/15,济南大学 模式识别与智能系统研究所(R),54,总结和作业,作业查阅资料：一篇关于聚类分析的论文。计算特征矢量之间的距离：任意构造10个人在程序设计、离散数学、数据结构、计算机组成原理4门课的成绩表。计算两两之间的欧式距离、绝对值距离，设计合适的阈值，能否进行分类？关于类的定义：如何定义类内各个样本的平均距离？如何定义类之间的距离？你如何理解准则函数？,总结和作业,2023/11/15,济南大学 模式识别与智能系统研究所(R),55,作业查询并整理所学过的聚类算法。做一做课间练习。准备之后的上机：最大最小距离算法。要求：给定了样本之后，能够自动按照该算法分成若干类（包括设定阈值等参数）。,THE END,Q/A?,