模式识别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,济南大学 模
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模式识别 03 聚类分析
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-6585336.html