模式识别-聚类分析.ppt

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