模式识别聚类分析

模式识别聚类分析第1页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)2目录复习说明模式相似性测度类的定义、类间距离和聚类准则聚类算法总结和作业第2页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)3目录复习说明模式相似性测度类的定义、类间距离和聚类准则聚类算法总结和作业第3页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)4复习模式识别的基本过程为什么要进行特征提取？什么是特征？如何抽取和表示特征？识别和训练（两种训练方式）识别系统的性能评价特征矢量的特点：随机性（为什么？）随机矢量的数字特征：有哪些？什么是正态分布（高斯分布）？写出一维和二维情况下的具体表达式和每个符号的具体含义。第4页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)5复习根据模式识别的基本过程，讨论如何区分正常的楼房维修和爬楼盗窃？Key:维修：一般白天；安全工具；工作服；长时停留；有灯光等盗窃：一般夜间；主要徒手；夜行衣；不逗留；无灯光等当然前提是能够检测到移动目标和判定大小如何区分这两种水果（自动分拣机）：梨和桃子？Key:梨：青或黄；无沟；粗糙多斑点；尾桔蒂等桃：红或青；有沟；光滑少斑点；尾多尖等第5页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)6目录复习说明模式相似性测度类的定义、类间距离和聚类准则聚类算法总结和作业第6页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)7说明特征的选取特征选取要合适特征选取不足有可能将不同类别判为一类特征过多可能有害无益假设根据已有特征已经能够正确分类新增加的特征与原有特征的关系： 独立、不相关或者相关若独立或者不相关，则分类结果不变，但是增加负担；若相关，增加冗余；则重要特征占“比重”减少；导致误判增加和负担增加量纲要合适第7页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)8目录复习说明模式相似性测度类的定义、类间距离和聚类准则聚类算法总结和作业第8页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)9模式相似性测度

为了能够划分模式的类别，必须首先定义相似性测度，描述各个模式之间特征的相似程度。距离测度描述两个矢量x和y之间的距离d(x,y)应该满足如下公理：d(x,y)0，d(x,y)=0iffx=y;d(x,y)=d(y,x);d(x,y)

d(x,z)+d(z,y);需要说明，某些距离测度不满足公理3，只是在广义上称为距离。第9页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)10模式相似性测度距离测度 设x=(x1,x2,…,xn)T,y=(y1,y2,…,yn)T欧式距离（Euclidean） d(x,y)=||x-y||=[i=1n(xi-yi)2]1/2绝对值距离（Manhattan距离） d(x,y)=i=1n|xi-yi|切氏距离（Chebyahev） d(x,y)=maxi|xi-yi|闵科夫斯基距离（Minkowski） d(x,y)=[i=1n(xi-yi)m]1/m

m=2,1,时分别是欧式距离、绝对值距离和切氏距离。第10页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)11模式相似性测度距离测度马氏距离（Mahalanohis） 设n维矢量xi和xj是矢量集{x1,x2,…,xn}中的两个矢量，其马氏距离d是： d2(xi,xj)=(xi-xj)T

V-1(xi-xj)第11页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)12模式相似性测度距离测度Camberra距离（Lance距离、Willims距离） 能克服量纲引起的问题，但无法克服分量间的相关性。第12页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)13模式相似性测度相似测度设x=(x1,x2,…,xn)T,y=(y1,y2,…,yn)T角度相似系数（夹角余弦） 对于坐标系的旋转和尺度缩放是不变的，但对于一般的线性变换和坐标系的平移不具有不变性。指数相似系数 不受量纲变化影响。其中

i2为相应分量的方差。第13页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)14匹配测度有时特征只有两个状态，即二值特征。 令a=

ixiyi,b=

I(1-xi)

yi,c=

Ixi(1-yi),e=

I(1-xi)(1-yi)Tanimoto测度模式相似性测度Rao测度第14页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(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如何获得这些特征不是模式识别所研究的内容，是其他相关学科的研究范畴第15页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)16目录复习说明模式相似性测度类的定义、类间距离和聚类准则聚类算法总结和作业第16页，课件共56页，创作于2023年2月类的定义、类间距离和聚类准则类的定义类间距离聚类准则2023/8/22济南大学模式识别与智能系统研究所(R)17第17页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)18类的定义、类间距离和聚类准则类的定义研究聚类算法，必须首先给出类的定义。不同类的定义，适合于不同的类内模式分布情况。只考虑距离层面的定义，相似测度和匹配测度可以类推。类定义一：集合S中任意两个元素xi和xj的距离dij满足 dijh 则S对于阈值h组成一类。

思考：这种定义，适合于哪种分布？ Key:团簇状，各类相聚较远。第18页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)19类的定义、类间距离和聚类准则第19页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)20类的定义、类间距离和聚类准则类的定义类定义二：集合S中任意两个元素xi和xj的距离dij满足 则S对于阈值h组成一类。其中k为集合S中元素的个数。 思考：这种定义，适合于哪种分布？ Key:仍然是团簇状，各类相聚较远。第20页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)21类的定义、类间距离和聚类准则类的定义类定义三：集合S，对于其中任意一个元素xiS，都存在xjS，其距离dijh，则称S对于阈值h组成一类。 思考：这种定义，适合于哪种分布？ Key:长条状。第21页，课件共56页，创作于2023年2月类的定义、类间距离和聚类准则类的定义类间距离聚类准则2023/8/22济南大学模式识别与智能系统研究所(R)22第22页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)23类的定义、类间距离和聚类准则类间距离最近距离法两个类别

k和l之间的最近距离：Dkl=minij[dij] dij表示xi

k和xj

l之间的距离。如果l是由两类

p和q合并而成，则有递推公式： Dkl=min[Dkp,Dkq]最远距离法两个类别

k和l之间的最远距离：Dkl=maxij[dij] dij表示xi

k和xj

l之间的距离。如果l是由两类p和q合并而成，则有递推公式： Dkl=max[Dkp,Dkq]第23页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)24类的定义、类间距离和聚类准则类间距离中间距离法三角形

kpq边pq中线长的平方和：可以作为新类l=

p

q与k间的距离的递推公式。第24页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)25类的定义、类间距离和聚类准则类间距离重心距离法：一个类的空间位置用重心表示，两个类的重心之间的距离作为二者的距离。设类p、

q的重心分别是xp、xq，有样本np、nq。类l=

p

q，则nl=np+nq。则l的重心为：另一个类k与l的距离平方是：

Dkl2=(xk-xl)T(xk-xl)

化简后得到：第25页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)26类的定义、类间距离和聚类准则类间距离平均距离法两类p、

q之间的距离可以定义为这两类元素之间的平均平方距离，即设类l=

p

q，则递推公式为：第26页，课件共56页，创作于2023年2月类的定义、类间距离和聚类准则类的定义类间距离聚类准则2023/8/22济南大学模式识别与智能系统研究所(R)27第27页，课件共56页，创作于2023年2月聚类准则类内距离准则设待分类的模式集合{x1,x2,…,xN}，在某种相似性测度的基础上被划分为c类{ci(j);j=1,2,3,…,c;i=1,2,…,nj}。 显然，类内聚类准则函数JW定义为： 显然，JW越小越好。 （误差平方和准则）特点：取决于类心的选取； 同类样本分布密集，各类分布区域体积相差不大。2023/8/22济南大学模式识别与智能系统研究所(R)28类的定义、类间距离和聚类准则第28页，课件共56页，创作于2023年2月聚类准则类间距离准则 其中mj是类的模式平均矢量，m为总的模式平均矢量；nj是

j类所含模式个数，N是所有模式的个数。加权的类间距离准则：2023/8/22济南大学模式识别与智能系统研究所(R)29类的定义、类间距离和聚类准则拓展思维：两类情况下结果如何？与JWB关系如何？第29页，课件共56页，创作于2023年2月聚类准则类内、类间距离准则希望聚类结果：类内距离越小越好，类间距离越大越好。设待分类模式集{xi;i=1,2,…,N}。分成c类，

j类含nj个模式。分类后各模式是{xi(j);j=1,2,…,c;i=1,2,…,nj}

j类内离差阵和总的类内离差阵分别如下：类间离差阵：总的离差阵：SW,SB和ST之间的关系： ST=SW+SB2023/8/22济南大学模式识别与智能系统研究所(R)30类的定义、类间距离和聚类准则CanYouProveit?第30页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)31类的定义、类间距离和聚类准则聚类准则类内、类间距离准则聚类的基本目标：Tr[SB]max；Tr[SW]min定义如下聚类准则：

J1=Tr[SW-1

SB]

J2=|SW-1

SB|

J3=Tr[SW-1

ST]

J4=|SW-1

ST|思考：这些准则应该越大越好，还是越小越好？第31页，课件共56页，创作于2023年2月类的定义、类间距离和聚类准则聚类准则基于模式与类核距离的准则函数前面是以一个点（类心）表示一类的位置并代替类核；缺点是：严重损失了各类在特征空间中所占子空间（类域）的形状和各类中各个模式在类域中的分布情况。引入类核：Kj=K(x,Vj)，表示

j类的模式分布结构。其中Vj是j的一个参数集，x是特征空间中一点。还应该引入一个模式x与核Kj的距离以及准则函数；模式x与核Kj的距离依赖于Kj的构造。 d(x,Kl)=minj[d(x,Kj)]

x

l。准则函数（显然，JKmin）：2023/8/22济南大学模式识别与智能系统研究所(R)32第32页，课件共56页，创作于2023年2月2023/8/22济南大学模式识别与智能系统研究所(R)33目录复习说明模式相似性测度类的定义、类间距离和聚类准则聚类算法总结和作业第33页，课件共56页，创作于2023年2月聚类算法概述聚类算法有许多具体算法。从算法算法的基本策略看，可以分为三类：根据相似性阈值和最小距离原则的简单聚类方法。 首先需要确定各聚类中心。按照最小距离原则不断将两类进行合并。各个模式首先自成一类，然后将距离最小的两类合并成一类。此过程不断重复，直至满足条件。该算法类心不断修正，但模式类别一旦指定就不再改变。依据准则函数的动态聚类法是一个准则函数取极值的优化过程。类心不断修正，各模式类别有不断改变。例如C-均值、ISODATA法、近邻函数法等2023/8/22济南大学模式识别与智能系统研究所(R)34第34页，课件共56页，创作于2023年2月聚类算法相似性阈值和最小距离准则的简单聚类法（1）基本思想：计算各个特征矢量到聚类中心的距离并和阈值（门限）T进行比较，决定归属哪一类或作为新的一个类心。常用欧氏距离。算法原理：(1)取任意一个模式特征向量作为第一个聚类中心。例如，令

1类的中心z1=x1。(2)计算下一个模式特征矢量x2到z1的距离d21。如果d21>T，则建立新的一类

2，其中心z2=x2；若d21

T，则x2

1。2023/8/22济南大学模式识别与智能系统研究所(R)35第35页，课件共56页，创作于2023年2月聚类算法相似性阈值和最小距离准则的简单聚类法（2）(3)假如已有聚类中心z1,z2,…,zk,计算尚未确定类别的模式特征矢量xi到各类别中心zj(j=1,2,…,k)的距离dij。若dij>T（j=1,2,…,k），则xi作为新的一类

k+1的中心，zk+1=xi；否则，如果dl=minj[dij]，则指判xi

l。检查是否所有的模式都分划完类别，如果分划完毕则结束；否则返回(3)。性能分析：计算简单。类心一经确定不再改变，模式一旦指判也不改变；故依赖于距离门限选取、待分类特征矢量参与分类的次序即聚类中心的选取等。参数和次序不同，结果可能会有差别。当有特征矢量先验知识来指导门限T及初始中心z1的选取时，往往结果合理。2023/8/22济南大学模式识别与智能系统研究所(R)36第36页，课件共56页，创作于2023年2月聚类算法第37页，课件共56页，创作于2023年2月聚类算法最大最小距离法（1）基本思想：以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。例：10个模式样本点： {x1(00),x2(38),x3(22),x4(11), x5(53),x6(48),x7(63),x8(54), x9(64),x10(75)}2023/8/22济南大学模式识别与智能系统研究所(R)38第38页，课件共56页，创作于2023年2月聚类算法最大最小距离法（2）第一步：选任意一个模式样本 作为第1个聚类中心，如z1=x1第二步：选距离z1最远的样本 作为第2个聚类中心。经计算，||x6–z1||最大，所以z2=x6第三步：逐个计算其余各模式样本{xi,i=1,2,…,N}与{z1,z2}之间的距离，即di1=||xi–z1||，di2=||xi–z2|| 并选出其中的最小距离min(di1,di2)，i=1,2,…,N第四步：在所有模式样本的最小值中选出最大距离，若该最大值达到||z1–z2||的一定比例以上，则相应的样本点取为第3个聚类中心z3，即若max{min(di1,di2),i=1,2,…,N}>

||z1–z2||，则z3=xi。否则，若无新聚类中心，则找聚类中心过程结束。第39页，课件共56页，创作于2023年2月聚类算法最大最小距离法（3）第五步：若有z3存在，则计算 max{min(di1,di2,di3),i=1,2,…,N}。若该值超过||z1

z2||的一定比例，则存在z4，否则找聚类中心的过程结束。此例无z4。第六步：将模式样本{xi,i=1,2,…,N}按最近距离分到最近的聚类中心： z1=x1：{x1,x3,x4}为第一类 z2=x6：{x2,x6}为第二类 z3=x7：{x5,x7,x8,x9,x10}为第三类第40页，课件共56页，创作于2023年2月聚类算法谱系聚类法（1）HierarchicalClusteringMethod，谱系聚类法，又称为系统聚类法、层次聚类法。算法步骤：第一步：设初始模式样本共有N个，每个样本自成一类，即建立N类，G1(0),G2(0),…,GN(0)。计算各类之间的距离（初始时即为各样本间的距离），得到一个N

N维的距离矩阵D(0)。这里，标号(0)表示聚类开始运算前的状态。第二步：假设前一步聚类运算中已求得距离矩阵D(n)，n为逐次聚类合并的次数，则求D(n)中的最小元素。如果它是Gi(n)和Gj(n)两类之间的距离，则将Gi(n)和Gj(n)两类合并为一类，由此建立新的分类：G1(n+1),G2(n+1),…2023/8/22济南大学模式识别与智能系统研究所(R)41第41页，课件共56页，创作于2023年2月聚类算法谱系聚类法（2）第三步：计算合并后新类别之间的距离矩阵，得D(n+1)。计算Gij(n+1)与其它没有发生合并的G1(n+1),G2(n+1),…之间的距离，可采用多种不同的距离计算准则进行计算。返回第二步，重复计算及合并，直到得到满意的分类结果。例如：达到所需的聚类数目，或D(n)中的最小分量超过给定的阈值D等。2023/8/22济南大学模式识别与智能系统研究所(R)42第42页，课件共56页，创作于2023年2月聚类算法谱系聚类法（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)T2023/8/22济南大学模式识别与智能系统研究所(R)43第43页，课件共56页，创作于2023年2月聚类算法C-均值（1）这是一种动态聚类法（DynamicClusteringAlgorithm）。前述算法特点：一旦模式划分后后续不再改变。动态聚类技术要点：确定模式和聚类的距离测度。一般采用欧氏距离。为能反映模式分布结构，可以采用马氏距离；设均矢为

，斜方差阵，则距离为d2=(x-

)T

-1(x-

)确定评估聚类质量的准则函数。确定模式分划及聚类合并或分裂的规则。2023/8/22济南大学模式识别与智能系统研究所(R)44第44页，课件共56页，创作于2023年2月聚类算法C-均值（2）动态聚类基本步骤：建立初始聚类中心，进行初始聚类；计算模式和类的距离，调整模式类别；计算各聚类的参数，删除、合并或分裂一些聚类；从初始聚类开始，运用迭代算法动态地改变模式类别和聚类中心，使得准则函数取得极值或者设定参数达到设计要求。2023/8/22济南大学模式识别与智能系统研究所(R)45第45页，课件共56页，创作于2023年2月聚类算法C-均值（3）类的数目c是预先取定的。算法步骤：任选c个模式特征矢量作为初始聚类中心：z1(0),z2(0),…,zc(0),令k=0.将待分类的模式特征矢量集{xi}中每个模式按照最小距离原则分划给c类中的某一类，即 Ifdil(k)=minj[dij(k)]，i=1,2,…,NThenxi

l(k+1)

k表示迭代次数。于是产生新的聚类j(k+1)(j=1,2,…,c)第46页，课件共56页，创作于2023年2月聚类算法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)。说明：本算法是收敛的。第47页，课件共56页，创作于2023年2月聚类算法C-均值（5）性能分析：方法简单。这种算法的类数是确定的。取定的类别数目和初始的聚类中心影响很大。模式分布呈现类内团簇状，则效果很好。实际应用中，应该试探不同的c值和选择不同的初始类心，以便获得更优结果。可以进行按批修改和逐个修改。第48页，课件共56页，创作于2023年2月聚类算法C-均值（6）改进：可以让类数c从较小值逐步增加，准则函数J将逐步增加。做J-c曲线，找到曲率变化最大点，此时的类数比较接近最优类数。（许多情况下无此明显点）初始聚类中心选取凭经验将模式随机分成c类，计算每类中心作为初始中心用相距最远的c个特征点作为初始类心（用最大最小距离法）选取密度最大的特征点作为初始类心。求每个特征点为球心，某个d0为半径的球形域中特征点个数（定义为该点的密度），选取密度最大的特征点作为第一个类心。然后在与第一个类心距离d的那些特征点中选取另一个密度最大的特征点作为第二个类心；以此类推。第49页，课件共56页，创作于2023年2月聚类算法C-均值（7）改进：用类核代替类心一个点往往不能充分反映该类的模式分布结构。当类的分布是球状或者近似球状时，效果尚可。定义类核函数Kj=Kj(x,Vj)，表示类

j的模式分布情况，其中Vj是关