《模式识别-聚类分析》由会员分享，可在线阅读，更多相关《模式识别-聚类分析（82页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学图像识别与人工智能研究所,2018/1/5,1,模式识别原理,聚类分析,2.1 聚类分析的概念,一、聚类分析的基本思想 根据各个待分类的模式特征相似程度进行分类，相似的归为一类，不相似的归为另一类。,基本内容,模式相似性度量,聚类算法,聚类分析的概念,聚类分析的基本思想 根据各个待分类的模式特征相似程度进行分类，相似的归为一类，不相似的归为另一类。,基本内容,模式相似性度量,聚类算法,2018/1/5,10,特征量的类型物理量：直接反映特征的实际物理意义如:长度、重量、速度等。处理前需要离散化。次序量：按某种规则确定的只反映特征的次序关系或等级如:产品的等级、病症的级或期。已是离散
2、量。名义量：非数值的特征数值化标识，如男性与女性、事物的状态、种类等。需要数值化。这些特征的数值指标既无数量含义，也无次序关系，只是用数字代表各种状态。,方法的有效性,本质上,模式特征点在特征空间中的分布情况，同类的模式特征点密集，不同类的相距较远,取决于分类算法和特征点分布情况的匹配,技术上,1，特征选取不当使分类无效2，特征选取不足可能使不同类别的模式判为一类3，特征选取过多可能有害无益，增加分析负担4，量纲选取不当,2018/1/5,12,特征选取不当,特征选取不足,2018/1/5,13,量纲不同对聚类的影响,2018/1/5,14,14,聚类准则对聚类结果的影响,羊,狗,猫, 鲨鱼,
3、蜥蜴,蛇,麻雀，海鸥,金鱼,青蛙,(a)繁衍后代的方式,金鱼,鲨鱼,羊,狗,猫,蜥蜴,蛇,麻雀，海鸥,青蛙,(b) 肺的存在,金鱼,鲨鱼,羊,狗,猫,蜥蜴,蛇,麻雀，海鸥,青蛙,(c) 生存环境,金鱼,蜥蜴,蛇,麻雀，海鸥,青蛙,(d)繁衍后代的方式和是否存在肺,鲨鱼,羊,狗,猫,2018/1/5,15,距离测度对聚类结果的影响,数据的粗聚类是2类,细聚类为4类,模式相似性测度,距离测度相似测度匹配测度,2018/1/5,16,距离测度,2018/1/5,17,欧氏(Euclidean)距离：2. 绝对值距离(街区距离，Manhattan距离)：3. 切氏(Chebyshev)距离:4. 明氏
4、(Minkowski)距离:,设,5. 马氏(Mahalanobis)距离: 设n维矢量 是矢量集 中的两个矢量,性质：对一切非奇异线性变换都是不变的。即，具有坐标系比例、旋转、平移不变性，并且从统计意义上尽量去掉了分量间的相关性。,5. Camberra距离：,该距离能克服量纲的影响，但不能克服分量间的相关性。,2018/1/5,19,马氏距离具有线性变换不变性,证明：设，有非奇异线性变换：则,2018/1/5,20,故,2018/1/5,21,21,例,求点 和 至均值点 的距离。解：由题设，可得从而马氏距离它们之比达 倍。若用欧氏距离，则算得的距离值相同：,已知一个二维正态母体G的分布为
5、,相似性测度,2018/1/5,22,1. 角度相似系数：2. 相关系数:3. 指数相似系数:,设,匹配测度,2018/1/5,23,设 为二值特征,1. Tanimoto测度：2. Rao测度:3. 简单匹配系数:4. Dice系数:5. Kulzinsky系数,2018/1/5,24,24,例,设(1) Tanimoto测度(2) Rao测度(3) 简单匹配测度(4) Dice系数(5) Kulzinsky系数,则,聚类分析,2.2 模式的相似性测度,没有哪个测度是最好的,1，简单而易于理解2，易于实现3，满足速度要求4，考虑数据的知识,选择时，可考虑以下几点,类的定义与类间距离,类的定义
6、,定义1：集合S中任两个元素 ， 的距离 有 其中h为给定的阈值，称S对于阈值h组成一类定义2：集合S中任一个元素 与 的距离 有： k为集合S中元素的个数， h为给定的阈值， 称S对于阈值h组成一类,模式的特征矢量作为集合中的元素,定义3：集合S中 ， 的距离 有 ， 其中h，r为给定的阈值，称S对于阈值h和r组成一类定义4：集合S中元素对于任一 ，存在某 使距离： 称S对于阈值h组成一类定义5：若将集合S任意分成两类S1,S2，这两类的距离D(S1,S2) 满足 ，称S对于阈值h组成一类,2.3 类的定义与类间距离,2.3.1 类的定义,类的划分具有人为规定性，这反映在定义的选取及参数的选
7、择上。一个分类结果的优劣最后只能根据实际来评价，因此较多地利用研究对象的知识才能选择适当的类的定义，从而使分类结果更符合实际。,类间距离,一、最近距离法： 两个聚类 和 之间的最近距离为： 式中 表示 和 之间的距离 如果 是由 和 两类合并而成的，则有,二、最远距离法： 两个聚类 和 之间的最近距离为： 式中 表示 和 之间的距离 如果 是由 和 两类合并而成的，则有,三、中间距离法：,四、重心距离法： 设 和 的重心分别为 和 ，它们分别有样本 和 个，将 和 合并为 ，则 有 个样本，则它的重心为： 设另一类 的重心为 ，则它与 的距离是：,2018/1/5,33,五、平均距离两类p和q
8、间的距离平方定义为这两类元素两两之间的平均平方距离，即设l =p q ，类平均距离的递推公式为,六、离差平方和法设类t的重心是 ，t的类内离差平方和定义为设l =p q ，则sl要变大。把两类合并所增加的离差平方和定义为两类平方距离，即 ，可以证明 k与l =p q的离差平方和的递推公式,2018/1/5,35,35,类间距离递推公式,（其中l =p q ）,聚类的准则函数,为了对模式集进行有效的分类，某些算法需要一个能对分类过程或分类结果的优劣进行评估的准则函数,已定义,模式与模式的相似性测度,类与类之间的距离,一、类内距离准则：二、类间距离准则：三、基于类内、类间距离的准则函数：四、基于模
9、式与类核的距离的准则函数：,聚类的准则函数,2018/1/5,38,（一）类内距离准则（误差平方和准则）,式中，nj是j中的样本个数，,适用于各类模式呈团状分布，且同类样本比较密集的情况。,2018/1/5,39,（二）类间距离准则,式中， 是总的样本均值矢量，,加权类间距离准则,对于两类问题 ，可以定义,2018/1/5,40,（三）基于类内类间距离的准则函数,构造能同时使Jwmin和JBmax的准则函数类内离差矩阵（Scatter Matrix）,总的类内离差矩阵,总的离差矩阵,类间离差矩阵,2018/1/5,41,ST = SW + SB （,证明：,2018/1/5,42,（三）基于类
10、内类间距离的准则函数,聚类的基本目标是使 JWB=TrSBmax和JWW =TrSWmin因此可定义如下聚类准则函数,Jimax，(i=1,2,3,4)即，类内越“紧”，类间越“开”，聚类效果越好。,2018/1/5,43,（四）基于模式与类核的距离的准则函数,定义一个核Kj=K(x,Vj)表示类j的模式分布结构，其中Vj是j的一个参数集，x是特征空间中的一点。 基于模式与核的距离的准则函数定义为,聚类算法,聚类的技术方案,三种策略：1、根据相似性阈值和最小距离原则的简单聚类方法2、按最小距离原则不断进行两类合并的方法3、根据准则函数动态聚类法,根据相似性阈值和最小距离原则的简单聚类方法,一、
11、根据相似性阈值和最小距离原则的简单方法1、条件及约定： 待分类的模式集 , 选定的类内距离门限T2、基本思想： 计算模式特征矢量到聚类中心的距离并和门限 比较，决定归属该类或作为新的一类中心。这种算法通常选择欧氏距离。3、算法步骤 （1）任取一个模式特征矢量作为第一个聚类中心，令 类的中心 （2）计算X2到Z1的距离d21,若d21T，则建立一个新类 ，令,（3）假设已有聚类中心Z1,Z2,Zk，计算Xi到Zj(j=1,2,k)的距离dij, 若 若（4）如果 i=N Goto(3), 否则停止这类算法的突出优点是算法简单。但聚类过程中，类的中心一旦确定将不会改变，模式一旦指定类后也不再改变。
12、从算法的过程可以看出，该算法结果很大程度上依赖于距离门限T的选取及模式参与分类的次序。如果能有先验知识指导门限T的选取，通常可获得较合理的效果。也可考虑设置不同的T和选择不同的次序，最后选择较好的结果进行比较。,2018/1/5,47,简单聚类图例,2018/1/5,48,初始条件不同的简单聚类结果,初始中心不同,样本顺序不同,1 2 3 4 5,1 2 3 4 5,1 2 3 4 5,1 2 3 4 5,10 9 8,10 9 8,8 7 6,8 7 6,11 6 7,11 6 7,9 10 11,9 10 11,二、最大最小距离算法1、条件及约定： 待分类的模式集 , 选定比例系数2、基本思想 模式特征矢量集中以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类3、算法步骤（1）任取一个模式特征矢量作为第一个聚类中心，令 类的中心（2）从待分类矢量集中选取距离Z1最远的特征矢量作为第二个聚类中心Z2（3）计算未被作为聚类中心的各模式矢量与Z1、Z2之间的距离： 确定最小值：,二、最大最小距离算法3、算法步骤 (续)（4）若 则相应的特征矢量 作为第三个聚类中心 Goto (5), 否则 Goto(6)（5）设存在k个聚类中心， 如果 ，则 ， Goto(5)，否则Goto(6)（6）当判断出不再有新的聚类中心后，计算： 当,
