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

《模式识别03-聚类分析.ppt》由会员分享，可在线阅读，更多相关《模式识别03-聚类分析.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模式识别导论模式识别导论聚类分析聚类分析李金屏李金屏李金屏李金屏济南大学济南大学济南大学济南大学信息科学与工程学院信息科学与工程学院信息科学与工程学院信息科学与工程学院 模式识别与智能系统研究所模式识别与智能系统研究所模式识别与智能系统研究所模式识别与智能系统研究所山东省网络环境智能计算技术重点实验室山东省网络环境智能计算技术重点实验室山东省网络环境智能计算技术重点实验室山东省网络环境智能计算技术重点实验室20112011年年年年9 9月月月月2023/5/20济南大学 模式识别与智能系统研究所(R)2目录目录复习复习说明说明模式相似性测度模式相似性测度类的定义、类间距离和聚类准则类的定义、类

2、间距离和聚类准则聚类算法聚类算法总结和作业总结和作业2023/5/20济南大学 模式识别与智能系统研究所(R)3目录目录复习复习说明说明模式相似性测度模式相似性测度类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则聚类算法聚类算法总结和作业总结和作业2023/5/20济南大学 模式识别与智能系统研究所(R)4复习复习模式识别的基本过程模式识别的基本过程l l为什么要进行特征提取？为什么要进行特征提取？l l什么是特征？什么是特征？l l如何抽取和表示特征？如何抽取和表示特征？l l识别和训练（两种训练方式）识别和训练（两种训练方式）l l识别系统的性能评价识别系统的性能评价特征矢量的特点

3、：随机性（为什么？）特征矢量的特点：随机性（为什么？）l l随机矢量的数字特征：有哪些？随机矢量的数字特征：有哪些？l l什么是正态分布（高斯分布）？写出一维和二维情况下的什么是正态分布（高斯分布）？写出一维和二维情况下的具体表达式和每个符号的具体含义。具体表达式和每个符号的具体含义。2023/5/20济南大学 模式识别与智能系统研究所(R)5复习复习根据模式识别的基本过程，讨论如何区分正常的楼根据模式识别的基本过程，讨论如何区分正常的楼房维修和爬楼盗窃？房维修和爬楼盗窃？l lKey:Key:维修：一般白天；安全工具；工作服；长时停留；有灯光等维修：一般白天；安全工具；工作服；长时停留；有灯

4、光等盗窃：一般夜间；主要徒手；夜行衣；不逗留；无灯光等盗窃：一般夜间；主要徒手；夜行衣；不逗留；无灯光等当然前提是能够检测到移动目标和判定大小当然前提是能够检测到移动目标和判定大小如何区分这两种水果（自动分拣机）：梨和桃子？如何区分这两种水果（自动分拣机）：梨和桃子？l lKey:Key:梨：青或黄；无沟；粗糙多斑点；尾桔蒂等梨：青或黄；无沟；粗糙多斑点；尾桔蒂等桃：红或青；有沟；光滑少斑点；尾多尖等桃：红或青；有沟；光滑少斑点；尾多尖等2023/5/20济南大学 模式识别与智能系统研究所(R)6目录目录复习复习说明说明模式相似性测度模式相似性测度类的定义、类间距离和聚类准则类的定义、类间距离

5、和聚类准则聚类算法聚类算法总结和作业总结和作业2023/5/20济南大学 模式识别与智能系统研究所(R)7说明说明特征的选取特征的选取l l特征选取要合适特征选取要合适l l特征选取不足有可能将不同类别判为一类特征选取不足有可能将不同类别判为一类l l特征过多可能有害无益特征过多可能有害无益假设根据已有特征已经能够正确分类假设根据已有特征已经能够正确分类新增加的特征与原有特征的关系：新增加的特征与原有特征的关系：独立、不相关或者相关独立、不相关或者相关若独立或者不相关，则分类结果不变，但是增加负担；若独立或者不相关，则分类结果不变，但是增加负担；若相关，增加冗余；则重要特征占若相关，增加冗余；

6、则重要特征占“比重比重”减少；导致误判减少；导致误判增加和负担增加增加和负担增加l l量纲要合适量纲要合适2023/5/20济南大学 模式识别与智能系统研究所(R)8目录目录复习复习说明说明模式相似性测度模式相似性测度类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则聚类算法聚类算法总结和作业总结和作业2023/5/20济南大学 模式识别与智能系统研究所(R)9模式相似性测度模式相似性测度为了能够划分模式的类别，必须首先定义相似性测为了能够划分模式的类别，必须首先定义相似性测度，描述各个模式之间特征的相似程度。度，描述各个模式之间特征的相似程度。距离测度距离测度距离测度距离测度l l描述

7、两个矢量描述两个矢量x x和和y y之间的距离之间的距离d d(x x,y y)应该满足如下公理：应该满足如下公理：d d(x x,y y)0 0，d d(x x,y y)=0 iff=0 iff x x=y y;d d(x x,y y)=)=d d(y y,x x););d d(x x,y y)d d(x x,z z)+)+d d(z z,y y););l l需要说明，某些距离测度不满足公理需要说明，某些距离测度不满足公理3 3，只是在广义上称，只是在广义上称为距离。为距离。2023/5/20济南大学 模式识别与智能系统研究所(R)10模式相似性测度模式相似性测度距离测度距离测度距离测度距离

8、测度设设x x=(=(x x1 1,x x2 2,x xn n)T T,y y=(=(y y1 1,y y2 2,y yn n)T Tl l欧式距离（欧式距离（欧式距离（欧式距离（EuclideanEuclidean）d(d(x x,y y)=|)=|x x-y y|=|=i i=1=1 n n(x xi i-y yi i)2 2 1/21/2l l绝对值距离（绝对值距离（绝对值距离（绝对值距离（ManhattanManhattan距离）距离）距离）距离）d(d(x x,y y)=)=i i=1=1 n n|x xi i-y yi i|l l切氏距离（切氏距离（切氏距离（切氏距离（Chebya

9、hevChebyahev）d(d(x x,y y)=max)=maxi i|x xi i-y yi i|l l闵科夫斯基距离（闵科夫斯基距离（闵科夫斯基距离（闵科夫斯基距离（MinkowskiMinkowski）d(d(x x,y y)=)=i i=1=1 n n(x xi i-y yi i)mm 1/m1/m m=2,1,m=2,1,时分别是欧式距离、绝对值距离和切氏距离。时分别是欧式距离、绝对值距离和切氏距离。2023/5/20济南大学 模式识别与智能系统研究所(R)11模式相似性测度模式相似性测度距离测度距离测度距离测度距离测度l l马氏距离（马氏距离（马氏距离（马氏距离（Mahalan

10、ohisMahalanohis）设设n n维矢量维矢量x xi i和和x xj j是矢量集是矢量集 x x1 1,x x2 2,x xn n 中的两个矢量，其中的两个矢量，其马氏距离马氏距离d d是：是：d d2 2(x xi i,x xj j)=()=(x xi i-x xj j)T T V V-1-1(x xi i-x xj j)2023/5/20济南大学 模式识别与智能系统研究所(R)12模式相似性测度模式相似性测度距离测度距离测度距离测度距离测度l lCamberraCamberra距离（距离（距离（距离（LanceLance距离、距离、距离、距离、WillimsWillims距离）距

11、离）距离）距离）能克服量纲引起的问题，但无法克服分量间的相关性。能克服量纲引起的问题，但无法克服分量间的相关性。2023/5/20济南大学 模式识别与智能系统研究所(R)13模式相似性测度模式相似性测度相似测度相似测度相似测度相似测度设设x x=(=(x x1 1,x x2 2,x xn n)T T,y y=(=(y y1 1,y y2 2,y yn n)T Tl l角度相似系数（夹角余弦）角度相似系数（夹角余弦）角度相似系数（夹角余弦）角度相似系数（夹角余弦）对于坐标系的旋转和尺度缩放是不变的，但对于一般的线对于坐标系的旋转和尺度缩放是不变的，但对于一般的线性变换和坐标系的平移不具有不变性。

12、性变换和坐标系的平移不具有不变性。l l指数相似系数指数相似系数指数相似系数指数相似系数不受量纲变化影响。其中不受量纲变化影响。其中 i i2 2为相应分量的方差。为相应分量的方差。2023/5/20济南大学 模式识别与智能系统研究所(R)14匹配测度匹配测度匹配测度匹配测度l l有时特征只有两个状态，即二值特征。有时特征只有两个状态，即二值特征。令令a a=i ix xi iy yi i,b b=I I(1-(1-x xi i)y yi i,c c=I I x xi i(1-(1-y yi i),),e e=I I(1-(1-x xi i)(1-)(1-y yi i)l lTanimotoT

13、animoto测度测度模式相似性测度模式相似性测度l lRaoRao测度测度2023/5/20济南大学 模式识别与智能系统研究所(R)15拓展思维拓展思维拓展思维拓展思维l l其他的匹配测度？其他的匹配测度？其他的匹配测度？其他的匹配测度？相同特征的比例？即相同特征的比例？即(1-1)(1-1)和和(0-0)(0-0)在所有特征中占有的比例在所有特征中占有的比例相同特征与不同特征的比例？相同特征与不同特征的比例？模式相似性测度模式相似性测度l l一个问题一个问题一个问题一个问题：特征空间中，两个特征矢量分别如下，计算其：特征空间中，两个特征矢量分别如下，计算其间不同距离：间不同距离：x x=(

14、1,1,0,1,0,0)=(1,1,0,1,0,0)T T,y y=(1,0,0,1,0,1)=(1,0,0,1,0,1)T T x x=(180,75,50)=(180,75,50)T T,y y=(170,70,55)=(170,70,55)T T如何获得这些特征不如何获得这些特征不如何获得这些特征不如何获得这些特征不是模式识别所研究的是模式识别所研究的是模式识别所研究的是模式识别所研究的内容，是其他相关学内容，是其他相关学内容，是其他相关学内容，是其他相关学科的研究范畴科的研究范畴科的研究范畴科的研究范畴2023/5/20济南大学 模式识别与智能系统研究所(R)16目录目录复习复习说明说

15、明模式相似性测度模式相似性测度类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则聚类算法聚类算法总结和作业总结和作业类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则类的定义类的定义类间距离类间距离聚类准则聚类准则2023/5/20济南大学 模式识别与智能系统研究所(R)172023/5/20济南大学 模式识别与智能系统研究所(R)18类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则类的定义类的定义类的定义类的定义研究聚类算法，必须首先给出类的定义。研究聚类算法，必须首先给出类的定义。不同类的定义，适合于不同的类内模式分布情况。不同类的定义，适合于不同的类内模式分布情况。只

16、考虑距离层面的定义，相似测度和匹配测度可以类推。只考虑距离层面的定义，相似测度和匹配测度可以类推。l l类定义一类定义一类定义一类定义一：集合：集合S S中任意两个元素中任意两个元素x xi i和和x xj j的距离的距离d dij ij满足满足d dij ij h h则则S S对于阈值对于阈值h h组成一类。组成一类。思考思考思考思考：这种定义，适合于哪种分布？：这种定义，适合于哪种分布？Key:Key:团簇状，各类相聚较远。团簇状，各类相聚较远。2023/5/20济南大学 模式识别与智能系统研究所(R)19类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则2023/5/20济南大学

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

18、聚类准则类的定义、类间距离和聚类准则类的定义类的定义类的定义类的定义l l类定义三类定义三类定义三类定义三：集合：集合S S，对于其中任意一个元素，对于其中任意一个元素x xi i S S，都存在，都存在x xj j S S，其距离，其距离d dij ij h h，则称，则称S S对于阈值对于阈值h h组成一类。组成一类。思考：这种定义，适合于哪种分布？思考：这种定义，适合于哪种分布？Key:Key:长条状。长条状。类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则类的定义类的定义类间距离类间距离聚类准则聚类准则2023/5/20济南大学 模式识别与智能系统研究所(R)222023/5/

19、20济南大学 模式识别与智能系统研究所(R)23类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则类间距离类间距离类间距离类间距离l l最近距离法最近距离法最近距离法最近距离法两个类别两个类别 k k和和 l l之间的最近距离：之间的最近距离：D Dklkl=min=minij ij d dij ij d dij ij表示表示x xi ik k和和x xj jl l之间的距离。之间的距离。如果如果 l l是由两类是由两类 p p和和 q q合并而成，则有递推公式：合并而成，则有递推公式：D Dklkl=min =min D Dkpkp,D Dkqkq l l最远距离法最远距离法最远距离法

20、最远距离法两个类别两个类别 k k和和 l l之间的最远距离：之间的最远距离：D Dklkl=max=maxij ij d dij ij d dij ij表示表示x xi ik k和和x xj jl l之间的距离。之间的距离。如果如果 l l是由两类是由两类 p p和和 q q合并而成，则有递推公式：合并而成，则有递推公式：D Dklkl=max =max D Dkpkp,D Dkqkq 2023/5/20济南大学 模式识别与智能系统研究所(R)24类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则类间距离类间距离类间距离类间距离l l中间距离法中间距离法中间距离法中间距离法三角形三角形

21、 kpqkpq边边pqpq中线长的平方和：中线长的平方和：可以作为新类可以作为新类 l l=p p q q与与 k k间间的距离的递推公式。的距离的递推公式。2023/5/20济南大学 模式识别与智能系统研究所(R)25类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则类间距离类间距离类间距离类间距离l l重心距离法重心距离法重心距离法重心距离法：一个类的空间位置用重心表示，两个类的重：一个类的空间位置用重心表示，两个类的重心之间的距离作为二者的距离。心之间的距离作为二者的距离。l l设类设类 p p、q q的重心分别是的重心分别是x xp p、x xq q，有样本，有样本n np p、

22、n nq q。类。类 l l=p p q q，则，则n nl l=n np p+n nq q。则。则 l l的重心为：的重心为：l l另一个类另一个类 k k与与 l l的距离平方是：的距离平方是：D Dkl kl2 2=(=(x xk k-x xl l)T T(x xk k-x xl l)化简后得到：化简后得到：2023/5/20济南大学 模式识别与智能系统研究所(R)26类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则类间距离类间距离类间距离类间距离l l平均距离法平均距离法平均距离法平均距离法l l两类两类 p p、q q之间的距离可以定义为这两类元素之间的平均之间的距离可以定义

23、为这两类元素之间的平均平方距离，即平方距离，即l l设类设类 l l=p p q q，则递推公式为：，则递推公式为：类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则类的定义类的定义类间距离类间距离聚类准则聚类准则2023/5/20济南大学 模式识别与智能系统研究所(R)27聚聚聚聚类类类类准准准准则则则则l l类类类类内距离准内距离准内距离准内距离准则则则则设设待分待分类类的模式集合的模式集合 x x1 1,x x2 2,x xN N，在某种相似性，在某种相似性测测度的基度的基础础上被划分上被划分为为c c类类 c ci i(j j);j j=1,2,3,=1,2,3,c c;i i=

24、1,2,=1,2,n nj j。显显然，然，类类内聚内聚类类准准则则函数函数J JWW定定义为义为：显显然，然，J JWW越小越好。越小越好。（误误差平方和准差平方和准则则）特点：取决于特点：取决于类类心的心的选选取；取；同同类样类样本分布密集，各本分布密集，各类类分布区域体分布区域体积积相差不大。相差不大。2023/5/20济南大学 模式识别与智能系统研究所(R)28类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则聚聚聚聚类类类类准准准准则则则则l l类间类间类间类间距离准距离准距离准距离准则则则则其中其中mmj j是是类类的模式平均矢量，的模式平均矢量，mm为总为总的模式平均矢量；

25、的模式平均矢量；n nj j是是 j j类类所含模式个数，所含模式个数，N N是所有模式的个数。是所有模式的个数。l l加加权权的的类间类间距离准距离准则则：2023/5/20济南大学 模式识别与智能系统研究所(R)29类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则拓展思维：两类情况下结果如何？与JWB关系如何？聚聚聚聚类类类类准准准准则则则则l l类类类类内、内、内、内、类间类间类间类间距离准距离准距离准距离准则则则则希望聚希望聚类结类结果：果：类类内距离越小越好，内距离越小越好，类间类间距离越大越好。距离越大越好。设设待分待分类类模式集模式集 x xi i;i i=1,2,=1,

26、2,N N。分成。分成c c类类，j j类类含含n nj j个模个模式。分式。分类类后各模式是后各模式是 x xi i(j j);j j=1,2,=1,2,c c;i i=1,2,=1,2,n nj j j j类类内离差内离差阵阵和和总总的的类类内离差内离差阵阵分分别别如下：如下：类间类间离差离差阵阵：总总的离差的离差阵阵：S SWW,S SB B和和S ST T之之间间的关系：的关系：S ST T=S SWW+S SB B2023/5/20济南大学 模式识别与智能系统研究所(R)30类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则Can You Prove it?2023/5/20济

27、南大学 模式识别与智能系统研究所(R)31类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则聚聚聚聚类类类类准准准准则则则则l l类类类类内、内、内、内、类间类间类间类间距离准距离准距离准距离准则则则则聚聚类类的基本目的基本目标标：TrTrS SB B maxmax；TrTrS SWW minmin定定义义如下聚如下聚类类准准则则：J J1 1=Tr=TrS SWW-1-1 S SB B J J2 2=|=|S SWW-1-1 S SB B|J J3 3=Tr=TrS SWW-1-1 S ST T J J4 4=|=|S SWW-1-1 S ST T|思考：思考：思考：思考：这这这这些准

28、些准些准些准则应该则应该则应该则应该越大越好，越大越好，越大越好，越大越好，还还还还是越小越好？是越小越好？是越小越好？是越小越好？类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则聚聚聚聚类类类类准准准准则则则则l l基于模式与基于模式与基于模式与基于模式与类类类类核距离的准核距离的准核距离的准核距离的准则则则则函数函数函数函数前面是以一个点（前面是以一个点（类类心）表示一心）表示一类类的位置并代替的位置并代替类类核；缺点核；缺点是：是：严严重重损损失了各失了各类类在特征空在特征空间间中所占子空中所占子空间间（类类域）的形域）的形状和各状和各类类中各个模式在中各个模式在类类域中的分布情

29、况。域中的分布情况。引入引入类类核：核：K Kj j=K K(x x,V Vj j)，表示，表示 j j类类的的模式分布模式分布模式分布模式分布结结结结构构构构。其中。其中V Vj j是是 j j的一个的一个参数集参数集参数集参数集，x x是特征空是特征空间间中中一点一点一点一点。还应该还应该引入一个模式引入一个模式x x与核与核K Kj j的距离以及准的距离以及准则则函数；模式函数；模式x x与与核核K Kj j的距离依的距离依赖赖于于K Kj j的构造。的构造。d(d(x x,K Kl l)=min)=minj j d(d(x x,K Kj j)x x l l。准准则则函数（函数（显显然，

30、然，J JK Kminmin）：）：2023/5/20济南大学 模式识别与智能系统研究所(R)322023/5/20济南大学 模式识别与智能系统研究所(R)33目录目录复习复习说明说明模式相似性测度模式相似性测度类的定义、类间距离和聚类准则类的定义、类间距离和聚类准则聚类算法聚类算法总结和作业总结和作业聚类算法聚类算法概述概述概述概述l l聚类算法有许多具体算法。从算法算法的基本策略看，可聚类算法有许多具体算法。从算法算法的基本策略看，可以分为三类：以分为三类：根据相似性阈值和最小距离原则的简单聚类方法。根据相似性阈值和最小距离原则的简单聚类方法。首先需要确定各聚类中心。首先需要确定各聚类中心

31、。按照最小距离原则不断将两类进行合并。按照最小距离原则不断将两类进行合并。l l各个模式首先自成一类，然后将距离最小的两类合并成一类。各个模式首先自成一类，然后将距离最小的两类合并成一类。此过程不断重复，直至满足条件。此过程不断重复，直至满足条件。l l该算法类心不断修正，但模式类别一旦指定就不再改变。该算法类心不断修正，但模式类别一旦指定就不再改变。依据准则函数的动态聚类法依据准则函数的动态聚类法l l是一个准则函数取极值的优化过程。是一个准则函数取极值的优化过程。l l类心不断修正，各模式类别有不断改变。例如类心不断修正，各模式类别有不断改变。例如C-C-均值、均值、ISODATAISOD

32、ATA法、近邻函数法等法、近邻函数法等2023/5/20济南大学 模式识别与智能系统研究所(R)34聚类算法聚类算法相似性阈值和最小距离准则的简单聚类法（相似性阈值和最小距离准则的简单聚类法（相似性阈值和最小距离准则的简单聚类法（相似性阈值和最小距离准则的简单聚类法（1 1）l l基本思想基本思想基本思想基本思想：计算各个特征矢量到聚类中心的距离并和阈值：计算各个特征矢量到聚类中心的距离并和阈值（门限）（门限）T T进行比较，决定归属哪一类或作为新的一个类进行比较，决定归属哪一类或作为新的一个类心。常用欧氏距离。心。常用欧氏距离。l l算法原理算法原理算法原理算法原理：(1)(1)取任意一个模

33、式特征向量作为第一个聚类中心。例如，取任意一个模式特征向量作为第一个聚类中心。例如，令令 1 1类的中心类的中心z z1 1=x=x1 1。(2)(2)计算下一个模式特征矢量计算下一个模式特征矢量x x2 2到到z z1 1的距离的距离d d2121。如果。如果d d2121TT，则建立新的一类则建立新的一类 2 2，其中心，其中心z z2 2=x=x2 2；若；若d d2121 T T，则，则x x2 2 1 1。2023/5/20济南大学 模式识别与智能系统研究所(R)35聚类算法聚类算法相似性阈值和最小距离准则的简单聚类法（相似性阈值和最小距离准则的简单聚类法（相似性阈值和最小距离准则的

34、简单聚类法（相似性阈值和最小距离准则的简单聚类法（2 2）(3)(3)假如已有聚类中心假如已有聚类中心z z1 1,z,z2 2,z,zk k,计算尚未确定类别的模式计算尚未确定类别的模式特征矢量特征矢量x xi i到各类别中心到各类别中心z zj j(j=1,2,k)(j=1,2,k)的距离的距离d dij ij。若。若d dij ijTT（j=1,2,kj=1,2,k），则），则x xi i作为新的一类作为新的一类 k+1k+1的中心，的中心，z zk+1k+1=x=xi i；否则，如果；否则，如果d dl l=min=minj j d dij ij，则指判，则指判x xi il l。检查

35、是否所有的。检查是否所有的模式都分划完类别，如果分划完毕则结束；否则返回模式都分划完类别，如果分划完毕则结束；否则返回(3)(3)。l l性能分析性能分析性能分析性能分析：计算简单。计算简单。类心一经确定不再改变，模式一旦指判也不改变；故依赖于类心一经确定不再改变，模式一旦指判也不改变；故依赖于距离门限选取、待分类特征矢量参与分类的次序即聚类中心距离门限选取、待分类特征矢量参与分类的次序即聚类中心的选取等。的选取等。参数和次序不同，结果可能会有差别。参数和次序不同，结果可能会有差别。参数和次序不同，结果可能会有差别。参数和次序不同，结果可能会有差别。当有特征矢量先验知识来指导门限当有特征矢量先

36、验知识来指导门限T T及初始中心及初始中心z z1 1的选取时，的选取时，往往结果合理。往往结果合理。2023/5/20济南大学 模式识别与智能系统研究所(R)36聚类算法聚类算法聚类算法聚类算法最大最小距离法（最大最小距离法（最大最小距离法（最大最小距离法（1 1）l l基本思想基本思想基本思想基本思想：以最大距离原则选取新的聚类中心，以最小距：以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。离原则进行模式归类。l l例：例：1010个模式样本点：个模式样本点：xx1 1(0 0),x(0 0),x2 2(3 8),x(3 8),x3 3(2 2),x(2 2),x4 4(1 1

37、),(1 1),x x5 5(5 3),x(5 3),x6 6(4 8),x(4 8),x7 7(6 3),x(6 3),x8 8(5 4),(5 4),x x9 9(6 4),x(6 4),x1010(7 5)(7 5)2023/5/20济南大学 模式识别与智能系统研究所(R)38聚类算法聚类算法最大最小距离法（最大最小距离法（最大最小距离法（最大最小距离法（2 2）l l第一步第一步第一步第一步：选任意一个模式样本：选任意一个模式样本作为第作为第1 1个聚类中心，如个聚类中心，如z z1 1=x=x1 1l l第二步第二步第二步第二步：选距离：选距离z z1 1最远的样本最远的样本作为第作

38、为第2 2个聚类中心。经计算，个聚类中心。经计算，|x|x6 6zz1 1|最大，所以最大，所以z z2 2=x=x6 6l l第三步第三步第三步第三步：逐个计算其余各模式样本：逐个计算其余各模式样本xxi i,i=1,2,N,i=1,2,N与与zz1 1,z,z2 2 之之间的距离，即间的距离，即d di1i1=|x=|xi izz1 1|，d di2i2=|x=|xi izz2 2|并选出其中的最小距离并选出其中的最小距离min(dmin(di1i1,d,di2i2)，i=1,2,Ni=1,2,Nl l第四步第四步第四步第四步：在所有模式样本的：在所有模式样本的最小值中选出最大距离最小值中

39、选出最大距离最小值中选出最大距离最小值中选出最大距离，若该最大，若该最大值达到值达到|z|z1 1zz2 2|的一定比例以上，则相应的样本点取为第的一定比例以上，则相应的样本点取为第3 3个聚类个聚类中心中心z z3 3，即若，即若maxmin(dmaxmin(di1i1,d,di2i2),i=1,2,N),i=1,2,N|z|z1 1zz2 2|，则，则z z3 3=x=xi i。否则，若无新聚类中心，则找聚类中心过程结束。否则，若无新聚类中心，则找聚类中心过程结束。聚类算法聚类算法最大最小距离法（最大最小距离法（最大最小距离法（最大最小距离法（3 3）l l第五步第五步第五步第五步：若有：

40、若有z z3 3存在，则计算存在，则计算maxmin(dmaxmin(di1i1,d,di2i2,d,di3i3),i=1,2,N),i=1,2,N。若该值超过。若该值超过|z|z1 1 z z2 2|的一的一定比例，则存在定比例，则存在z z4 4，否则找聚类中心的过程结束。此例无，否则找聚类中心的过程结束。此例无z z4 4。l l第六步第六步第六步第六步：将模式样本：将模式样本xxi i,i=1,2,N,i=1,2,N按最近距离分到最近按最近距离分到最近的聚类中心：的聚类中心：z z1 1=x=x1 1：xx1 1,x,x3 3,x,x4 4 为第一类为第一类z z2 2=x=x6 6：

41、xx2 2,x,x6 6 为第二类为第二类z z3 3=x=x7 7：xx5 5,x,x7 7,x,x8 8,x,x9 9,x,x1010 为第三类为第三类聚类算法聚类算法谱系聚类法（谱系聚类法（谱系聚类法（谱系聚类法（1 1）l lHierarchical Clustering MethodHierarchical Clustering Method，谱谱系聚系聚类类法，又称法，又称为为系系统统聚聚类类法、法、层层次聚次聚类类法。法。l l算法步算法步算法步算法步骤骤骤骤：第一步第一步第一步第一步：设设初始模式初始模式样样本共有本共有N N个，每个个，每个样样本自成一本自成一类类，即，即建立

42、建立N N类类，G G1 1(0)(0),G,G2 2(0)(0),G,GNN(0)(0)。计计算各算各类类之之间间的距离（初始的距离（初始时时即即为为各各样样本本间间的距离），得到一个的距离），得到一个N N N N维维的距离矩的距离矩阵阵D D(0)(0)。这这里，里，标标号号(0)(0)表示聚表示聚类类开始运算前的状开始运算前的状态态。第二步第二步第二步第二步：假设前一步聚类运算中已求得距离矩阵：假设前一步聚类运算中已求得距离矩阵D D(n)(n)，n n为逐为逐次聚类合并的次数，则求次聚类合并的次数，则求D D(n)(n)中的最小元素。如果它是中的最小元素。如果它是G Gi i(n)(

43、n)和和G Gj j(n)(n)两类之间的距离，则将两类之间的距离，则将G Gi i(n)(n)和和G Gj j(n)(n)两类合并为一类，由此两类合并为一类，由此建立新的分类：建立新的分类：G G1 1(n+1)(n+1),G,G2 2(n+1)(n+1),2023/5/20济南大学 模式识别与智能系统研究所(R)41聚类算法聚类算法谱系聚类法（谱系聚类法（谱系聚类法（谱系聚类法（2 2）第三步第三步第三步第三步：计算合并后新类别之间的距离矩阵，得：计算合并后新类别之间的距离矩阵，得D D(n+1)(n+1)。计。计算算G Gij ij(n+1)(n+1)与其它没有发生合并的与其它没有发生合

44、并的G G1 1(n+1)(n+1),G,G2 2(n+1)(n+1),之间的距离，之间的距离，可采用多种不同的距离计算准则进行计算。可采用多种不同的距离计算准则进行计算。返回第二步，重复返回第二步，重复计计算及合并，直到得到算及合并，直到得到满满意的分意的分类结类结果。果。例如：达到所需的聚例如：达到所需的聚类类数目，或数目，或D D(n)(n)中的最小分量超中的最小分量超过给过给定定的的阈值阈值D D等等。2023/5/20济南大学 模式识别与智能系统研究所(R)42聚类算法聚类算法谱系聚类法（谱系聚类法（谱系聚类法（谱系聚类法（3 3）l l说明说明说明说明：可以利用之前介绍的有关距离定

45、义和类间距离递推公式。可以利用之前介绍的有关距离定义和类间距离递推公式。类间距离定义不同，聚类过程也不同。类间距离定义不同，聚类过程也不同。在迭代过程中，距离矩阵的最小元素值不断改变。如果有单在迭代过程中，距离矩阵的最小元素值不断改变。如果有单调不减关系则称类间距离对于类的合并具有单调性。最近距调不减关系则称类间距离对于类的合并具有单调性。最近距离法、最远距离法、平均法等类间距离都有该性质，重心法离法、最远距离法、平均法等类间距离都有该性质，重心法无此性质。无此性质。l l练习练习练习练习：6 6个样本，按照最小距离原则进行聚类（个样本，按照最小距离原则进行聚类（请聚成两类请聚成两类请聚成两类

46、请聚成两类）：）：x x1 1=(0,3,1,2,0)=(0,3,1,2,0)T T,x,x2 2=(0,3,0,1,0)=(0,3,0,1,0)T T,x,x3 3=(3,3,0,0,1)=(3,3,0,0,1)T T,x x4 4=(1,1,0,2,0)=(1,1,0,2,0)T T,x,x5 5=(3,2,1,2,1)=(3,2,1,2,1)T T,x,x6 6=(4,1,1,1,0)=(4,1,1,1,0)T T2023/5/20济南大学 模式识别与智能系统研究所(R)43聚类算法聚类算法C-C-均值（均值（均值（均值（1 1）l l这是一种动态聚类法（这是一种动态聚类法（Dynami

47、c Clustering AlgorithmDynamic Clustering Algorithm）。）。l l前述算法特点前述算法特点前述算法特点前述算法特点：一旦模式划分后后续不再改变。：一旦模式划分后后续不再改变。l l动态聚类动态聚类技术要点技术要点技术要点技术要点：确定模式和聚类的距离测度。一般采用欧氏距离。为能反映确定模式和聚类的距离测度。一般采用欧氏距离。为能反映模式分布结构，可以采用马氏距离；设均矢为模式分布结构，可以采用马氏距离；设均矢为 ，斜方差阵，斜方差阵，则距离为，则距离为d d2 2=(=(x x-)T T-1-1(x x-)确定评估聚类质量的准则函数。确定评估聚类

48、质量的准则函数。确定模式分划及聚类合并或分裂的规则。确定模式分划及聚类合并或分裂的规则。2023/5/20济南大学 模式识别与智能系统研究所(R)44聚类算法聚类算法C-C-均值（均值（均值（均值（2 2）l l动态聚类基本步骤：动态聚类基本步骤：建立初始聚类中心，进行初始聚类；建立初始聚类中心，进行初始聚类；计算模式和类的距离，调整模式类别；计算模式和类的距离，调整模式类别；计算各聚类的参数，删除、合并或分裂一些聚类；计算各聚类的参数，删除、合并或分裂一些聚类；从初始聚类开始，运用迭代算法动态地改变模式类别和聚类从初始聚类开始，运用迭代算法动态地改变模式类别和聚类中心，使得准则函数取得极值或

49、者设定参数达到设计要求。中心，使得准则函数取得极值或者设定参数达到设计要求。2023/5/20济南大学 模式识别与智能系统研究所(R)45聚类算法聚类算法C-C-均值（均值（均值（均值（3 3）l l类的数目类的数目c c是预先取定的。是预先取定的。l l算法步骤：算法步骤：任选任选c c个模式特征矢量作为初始聚类中心：个模式特征矢量作为初始聚类中心：z z1 1(0)(0),z z2 2(0)(0),z zc c(0)(0),令令k k=0.=0.将待分类的模式特征矢量集将待分类的模式特征矢量集 x xi i 中每个模式按照最小距离原中每个模式按照最小距离原则分划给则分划给c c类中的某一类

50、，即类中的某一类，即If If d dil il(k k)=min=minj j d dij ij(k k)，i i=1,2,=1,2,N N Then Then x xi il l(k k+1)+1)k k表示迭代次数。于是产生新的聚类表示迭代次数。于是产生新的聚类 j j(k k+1)+1)(j j=1,2,=1,2,c c)聚类算法聚类算法C-C-均值（均值（均值（均值（4 4）计算重新分类后的各类心计算重新分类后的各类心其中，其中，j j=1,2,=1,2,c c;n nj j(k k+1)+1)为为 j j(k k+1)+1)类中所含模式的个数。类中所含模式的个数。如果如果z zj