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

1、模式识别导论聚类分析,李金屏 济南大学 信息科学与工程学院 模式识别与智能系统研究所 山东省网络环境智能计算技术重点实验室 2011年9月,2020/10/11,济南大学 模式识别与智能系统研究所(R),2,目录,复习 说明 模式相似性测度 类的定义、类间距离和聚类准则 聚类算法 总结和作业,2020/10/11,济南大学 模式识别与智能系统研究所(R),3,目录,复习 说明 模式相似性测度 类的定义、类间距离和聚类准则 聚类算法 总结和作业,2020/10/11,济南大学 模式识别与智能系统研究所(R),4,复习,模式识别的基本过程 为什么要进行特征提取？ 什么是特征？ 如何抽取和表示特征？

2、 识别和训练（两种训练方式） 识别系统的性能评价 特征矢量的特点：随机性（为什么？） 随机矢量的数字特征：有哪些？ 什么是正态分布（高斯分布）？写出一维和二维情况下的具体表达式和每个符号的具体含义。,2020/10/11,济南大学 模式识别与智能系统研究所(R),5,复习,根据模式识别的基本过程，讨论如何区分正常的楼房维修和爬楼盗窃？ Key: 维修：一般白天；安全工具；工作服；长时停留；有灯光等 盗窃：一般夜间；主要徒手；夜行衣；不逗留；无灯光等 当然前提是能够检测到移动目标和判定大小 如何区分这两种水果（自动分拣机）：梨和桃子？ Key: 梨：青或黄；无沟；粗糙多斑点；尾桔蒂等 桃：红或青

3、；有沟；光滑少斑点；尾多尖等,2020/10/11,济南大学 模式识别与智能系统研究所(R),6,目录,复习 说明 模式相似性测度 类的定义、类间距离和聚类准则 聚类算法 总结和作业,2020/10/11,济南大学 模式识别与智能系统研究所(R),7,说明,特征的选取 特征选取要合适 特征选取不足有可能将不同类别判为一类 特征过多可能有害无益 假设根据已有特征已经能够正确分类 新增加的特征与原有特征的关系： 独立、不相关或者相关 若独立或者不相关，则分类结果不变，但是增加负担； 若相关，增加冗余；则重要特征占“比重”减少；导致误判增加和负担增加 量纲要合适,2020/10/11,济南大学 模式

4、识别与智能系统研究所(R),8,目录,复习 说明 模式相似性测度 类的定义、类间距离和聚类准则 聚类算法 总结和作业,2020/10/11,济南大学 模式识别与智能系统研究所(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，只是在广义上称为距离。,2020/10/11,济南大

5、学 模式识别与智能系统研究所(R),10,模式相似性测度,距离测度 设x=(x1, x2, , xn)T, y=(y1, y2, , yn)T 欧式距离（Euclidean） 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,时分别是欧式距离、绝对值距离和切氏距离。,2020/10/11,济南大学 模式识别与智能

6、系统研究所(R),11,模式相似性测度,距离测度 马氏距离（Mahalanohis） 设n维矢量xi和xj是矢量集x1, x2, , xn中的两个矢量，其马氏距离d是： d2(xi, xj) = (xi-xj)T V-1 (xi-xj),2020/10/11,济南大学 模式识别与智能系统研究所(R),12,模式相似性测度,距离测度 Camberra距离（Lance距离、Willims距离） 能克服量纲引起的问题，但无法克服分量间的相关性。,2020/10/11,济南大学 模式识别与智能系统研究所(R),13,模式相似性测度,相似测度 设x=(x1, x2, , xn)T, y=(y1, y2,

7、 , yn)T 角度相似系数（夹角余弦） 对于坐标系的旋转和尺度缩放是不变的，但对于一般的线性变换和坐标系的平移不具有不变性。,指数相似系数 不受量纲变化影响。其中i2为相应分量的方差。,2020/10/11,济南大学 模式识别与智能系统研究所(R),14,匹配测度 有时特征只有两个状态，即二值特征。 令a=ixiyi, b=I (1-xi) yi, c=I xi(1-yi), e=I (1-xi)(1-yi) Tanimoto测度,模式相似性测度,Rao测度,2020/10/11,济南大学 模式识别与智能系统研究所(R),15,拓展思维 其他的匹配测度？ 相同特征的比例？即(1-1)和(0-

8、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,如何获得这些特征不是模式识别所研究的内容，是其他相关学科的研究范畴,2020/10/11,济南大学 模式识别与智能系统研究所(R),16,目录,复习 说明 模式相似性测度 类的定义、类间距离和聚类准则 聚类算法 总结和作业,类的定义、类间距离和聚类准则,类的定义 类间距离 聚类准则,2020/10/11

9、,济南大学 模式识别与智能系统研究所(R),17,2020/10/11,济南大学 模式识别与智能系统研究所(R),18,类的定义、类间距离和聚类准则,类的定义 研究聚类算法，必须首先给出类的定义。 不同类的定义，适合于不同的类内模式分布情况。 只考虑距离层面的定义，相似测度和匹配测度可以类推。 类定义一：集合S中任意两个元素xi和xj的距离dij满足 dijh 则S对于阈值h组成一类。 思考：这种定义，适合于哪种分布？ Key: 团簇状，各类相聚较远。,2020/10/11,济南大学 模式识别与智能系统研究所(R),19,类的定义、类间距离和聚类准则,2020/10/11,济南大学 模式识别与

10、智能系统研究所(R),20,类的定义、类间距离和聚类准则,类的定义 类定义二：集合S中任意两个元素xi和xj的距离dij满足 则S对于阈值h组成一类。其中k为集合S中元素的个数。 思考：这种定义，适合于哪种分布？ Key:仍然是团簇状，各类相聚较远。,2020/10/11,济南大学 模式识别与智能系统研究所(R),21,类的定义、类间距离和聚类准则,类的定义 类定义三：集合S，对于其中任意一个元素xiS，都存在xj S，其距离dijh，则称S对于阈值h组成一类。 思考：这种定义，适合于哪种分布？ Key:长条状。,类的定义、类间距离和聚类准则,类的定义 类间距离 聚类准则,2020/10/11

11、,济南大学 模式识别与智能系统研究所(R),22,2020/10/11,济南大学 模式识别与智能系统研究所(R),23,类的定义、类间距离和聚类准则,类间距离 最近距离法 两个类别k和l之间的最近距离：Dkl=minij dij dij表示xik和xjl之间的距离。 如果l是由两类p和q合并而成，则有递推公式： Dkl = min Dkp, Dkq 最远距离法 两个类别k和l之间的最远距离：Dkl=maxij dij dij表示xik和xjl之间的距离。 如果l是由两类p和q合并而成，则有递推公式： Dkl = max Dkp, Dkq,2020/10/11,济南大学 模式识别与智能系统研究所

12、(R),24,类的定义、类间距离和聚类准则,类间距离 中间距离法 三角形kpq 边pq中线长的平方和： 可以作为新类l= p q与k间的距离的递推公式。,2020/10/11,济南大学 模式识别与智能系统研究所(R),25,类的定义、类间距离和聚类准则,类间距离 重心距离法：一个类的空间位置用重心表示，两个类的重心之间的距离作为二者的距离。 设类p、q的重心分别是xp、xq，有样本np、nq。类l= p q，则nl = np+nq 。则l的重心为： 另一个类k与l的距离平方是： Dkl2 = (xk - xl)T (xk - xl) 化简后得到：,2020/10/11,济南大学 模式识别与智能

13、系统研究所(R),26,类的定义、类间距离和聚类准则,类间距离 平均距离法 两类p、q之间的距离可以定义为这两类元素之间的平均平方距离，即 设类l= p q，则递推公式为：,类的定义、类间距离和聚类准则,类的定义 类间距离 聚类准则,2020/10/11,济南大学 模式识别与智能系统研究所(R),27,聚类准则 类内距离准则 设待分类的模式集合x1, x2, , xN，在某种相似性测度的基础上被划分为c类ci(j); j=1,2,3, , c; i=1,2, , nj。 显然， 类内聚类准则函数JW定义为： 显然，JW越小越好。 （误差平方和准则） 特点：取决于类心的选取； 同类样本分布密集，

14、各类分布区域体积相差不大。,2020/10/11,济南大学 模式识别与智能系统研究所(R),28,类的定义、类间距离和聚类准则,聚类准则 类间距离准则 其中mj是类的模式平均矢量，m为总的模式平均矢量；nj是j类所含模式个数，N是所有模式的个数。 加权的类间距离准则：,2020/10/11,济南大学 模式识别与智能系统研究所(R),29,类的定义、类间距离和聚类准则,拓展思维：两类情况下结果如何？ 与JWB关系如何？,聚类准则 类内、类间距离准则 希望聚类结果：类内距离越小越好，类间距离越大越好。 设待分类模式集xi; i = 1, 2, , N。分成c类，j类含nj个模式。分类后各模式是xi

15、(j); j = 1, 2, , c; i = 1, 2, , nj j类内离差阵和总的类内离差阵分别如下： 类间离差阵： 总的离差阵： SW, SB和ST之间的关系： ST = SW + SB,2020/10/11,济南大学 模式识别与智能系统研究所(R),30,类的定义、类间距离和聚类准则,Can You Prove it?,2020/10/11,济南大学 模式识别与智能系统研究所(R),31,类的定义、类间距离和聚类准则,聚类准则 类内、类间距离准则 聚类的基本目标：TrSBmax；TrSWmin 定义如下聚类准则： J1 = TrSW-1 SB J2 = |SW-1 SB| J3 =

16、TrSW-1 ST J4 = |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）：,2

17、020/10/11,济南大学 模式识别与智能系统研究所(R),32,2020/10/11,济南大学 模式识别与智能系统研究所(R),33,目录,复习 说明 模式相似性测度 类的定义、类间距离和聚类准则 聚类算法 总结和作业,聚类算法,概述 聚类算法有许多具体算法。从算法算法的基本策略看，可以分为三类： 根据相似性阈值和最小距离原则的简单聚类方法。 首先需要确定各聚类中心。 按照最小距离原则不断将两类进行合并。 各个模式首先自成一类，然后将距离最小的两类合并成一类。此过程不断重复，直至满足条件。 该算法类心不断修正，但模式类别一旦指定就不再改变。 依据准则函数的动态聚类法 是一个准则函数取极值的

18、优化过程。 类心不断修正，各模式类别有不断改变。例如C-均值、ISODATA法、近邻函数法等,2020/10/11,济南大学 模式识别与智能系统研究所(R),34,聚类算法,相似性阈值和最小距离准则的简单聚类法（1） 基本思想：计算各个特征矢量到聚类中心的距离并和阈值（门限）T进行比较，决定归属哪一类或作为新的一个类心。常用欧氏距离。 算法原理： (1) 取任意一个模式特征向量作为第一个聚类中心。例如，令1类的中心z1 = x1。 (2) 计算下一个模式特征矢量x2到z1的距离d21。如果d21T，则建立新的一类2，其中心z2=x2；若d21T，则x21。,2020/10/11,济南大学 模式

19、识别与智能系统研究所(R),35,聚类算法,相似性阈值和最小距离准则的简单聚类法（2） (3) 假如已有聚类中心z1, z2, , zk, 计算尚未确定类别的模式特征矢量xi到各类别中心zj(j=1, 2, , k)的距离dij。若dijT（j=1,2,k），则xi作为新的一类k+1的中心，zk+1=xi；否则，如果dl = minj dij，则指判xil。检查是否所有的模式都分划完类别，如果分划完毕则结束；否则返回(3)。 性能分析： 计算简单。 类心一经确定不再改变，模式一旦指判也不改变；故依赖于距离门限选取、待分类特征矢量参与分类的次序即聚类中心的选取等。参数和次序不同，结果可能会有差别

20、。 当有特征矢量先验知识来指导门限T及初始中心z1的选取时，往往结果合理。,2020/10/11,济南大学 模式识别与智能系统研究所(R),36,聚类算法,聚类算法,最大最小距离法（1） 基本思想：以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。 例：10个模式样本点： x1(0 0), x2(3 8), x3(2 2), x4(1 1), x5(5 3), x6(4 8), x7(6 3), x8(5 4), x9(6 4), x10(7 5),2020/10/11,济南大学 模式识别与智能系统研究所(R),38,聚类算法,最大最小距离法（2） 第一步：选任意一个模式样本 作为第

21、1个聚类中心，如z1 = x1 第二步：选距离z1最远的样本 作为第2个聚类中心。经计算，| x6z1|最大，所以z2 = x6 第三步：逐个计算其余各模式样本xi, i = 1,2,N与z1, z2之间的距离，即di1 = |xiz1|，di2 = |xiz2| 并选出其中的最小距离min(di1, di2)，i = 1,2,N 第四步：在所有模式样本的最小值中选出最大距离，若该最大值达到|z1z2|的一定比例以上，则相应的样本点取为第3个聚类中心z3，即若maxmin(di1, di2), i = 1,2,N|z1z2|，则z3=xi。否则，若无新聚类中心，则找聚类中心过程结束。,聚类算法

22、,最大最小距离法（3） 第五步：若有z3存在，则计算 maxmin(di1, di2, di3), i = 1,2,N。若该值超过|z1z2|的一定比例，则存在z4，否则找聚类中心的过程结束。此例无z4。 第六步：将模式样本xi, i = 1,2,N按最近距离分到最近的聚类中心： z1 = x1：x1, x3, x4为第一类 z2 = x6：x2, x6为第二类 z3 = x7：x5, x7, x8, x9, x10为第三类,聚类算法,谱系聚类法（1） Hierarchical Clustering Method，谱系聚类法，又称为系统聚类法、层次聚类法。 算法步骤： 第一步：设初始模式样本共

23、有N个，每个样本自成一类，即建立N类，G1(0), G2(0), , GN(0)。计算各类之间的距离（初始时即为各样本间的距离），得到一个NN维的距离矩阵D(0)。这里，标号(0)表示聚类开始运算前的状态。 第二步：假设前一步聚类运算中已求得距离矩阵D(n)，n为逐次聚类合并的次数，则求D(n)中的最小元素。如果它是Gi(n)和Gj(n)两类之间的距离，则将Gi(n)和Gj(n)两类合并为一类，由此建立新的分类：G1(n+1), G2(n+1), ,2020/10/11,济南大学 模式识别与智能系统研究所(R),41,聚类算法,谱系聚类法（2） 第三步：计算合并后新类别之间的距离矩阵，得D(n

24、+1)。计算Gij(n+1)与其它没有发生合并的G1(n+1), G2(n+1), 之间的距离，可采用多种不同的距离计算准则进行计算。 返回第二步，重复计算及合并，直到得到满意的分类结果。例如：达到所需的聚类数目，或D(n)中的最小分量超过给定的阈值D等。,2020/10/11,济南大学 模式识别与智能系统研究所(R),42,聚类算法,谱系聚类法（3） 说明： 可以利用之前介绍的有关距离定义和类间距离递推公式。 类间距离定义不同，聚类过程也不同。 在迭代过程中，距离矩阵的最小元素值不断改变。如果有单调不减关系则称类间距离对于类的合并具有单调性。最近距离法、最远距离法、平均法等类间距离都有该性质

25、，重心法无此性质。 练习： 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)T,2020/10/11,济南大学 模式识别与智能系统研究所(R),43,聚类算法,C-均值（1） 这是一种动态聚类法（Dynamic Clustering Algorithm）。 前述算法特点：一旦模式划分后后续不再改变。 动态聚类技术要点： 确定模式和聚类的距离测度。一般采用欧氏距离。为能反映模式分布结构，可以采用马

26、氏距离；设均矢为，斜方差阵，则距离为d2 = (x-)T-1(x-) 确定评估聚类质量的准则函数。 确定模式分划及聚类合并或分裂的规则。,2020/10/11,济南大学 模式识别与智能系统研究所(R),44,聚类算法,C-均值（2） 动态聚类基本步骤： 建立初始聚类中心，进行初始聚类； 计算模式和类的距离，调整模式类别； 计算各聚类的参数，删除、合并或分裂一些聚类； 从初始聚类开始，运用迭代算法动态地改变模式类别和聚类中心，使得准则函数取得极值或者设定参数达到设计要求。,2020/10/11,济南大学 模式识别与智能系统研究所(R),45,聚类算法,C-均值（3） 类的数目c是预先取定的。 算

27、法步骤： 任选c个模式特征矢量作为初始聚类中心：z1(0), z2(0), zc(0),令k = 0. 将待分类的模式特征矢量集xi中每个模式按照最小距离原则分划给c类中的某一类，即 If dil(k)=minjdij(k)，i=1, 2, , N Then xil(k+1) k表示迭代次数。于是产生新的聚类j(k+1) (j = 1, 2, , c),聚类算法,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)。 说

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