模式识别讲义--聚类分析ppt课件.ppt

《模式识别讲义--聚类分析ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分类与聚类的区别分类：用已知类别的样本训练集来设计分类器（监督学习）聚类（集群）：用事先不知样本的类别，而利用样本的先验知识来构造分类器（无监督学习）聚类分析（ClusteringAnalysis）聚类分析解决主要问题1.如何评价样本间的类似程度；2.如何根据样本间的类似程度聚类。特征量的类型1.物理量：反映实际物理或几何意义，如重量2.次序量：只反映次序关系，如产品等级等3.名义量：只用数字代表各种状态，如性别编码方法有效性1.特征选取不当2.特征选取不足3.特征选取过多4.量纲选取不当模式相似性测度

2、距离测度：以两个矢量矢端的距离为基础1.欧式距离：(Euclidean)2.绝对值距离：（Manhattan）3.切氏距离：（Chebyshev）距离测度4.明氏距离：（Minkowski）5.马氏距离（Mahalanobis）类的定义1.集合S中任意两个元素xi,xj的距离dij满足如下条件之一，则S对于阈值h组成一类，h为阈值。2.集合S中元素满足对于任一xi,存在xj的距离dij满足dij≤h，则S对于阈值h组成一类，h为阈值。3.若将集合任意分为两类S1，S2，这两类间的距离D(S1,S2）满足

3、D(S1,S2)≤h，则称S对于阈值h组成一类。类间距离定义最短距离：两类中相距最近的两样品间的距离最长距离：两类中相距最远的两个样本间的距离。中间距离：设ω1类和ω2ω3类间的最短距离为d12，最长距离为d13，ω2ω3类的长度为d23，则中间距离为：类间距离定义（续）重心距离：即均值间的距离。设ωp,ωq重心分别为xp,xq，他们分别有样本np,nq个。将合并为ωl，nl=np+nq个样本，重心为：类间距离定义（续）平均距离：两类中各个元素两两之间的距离平方相加后取平均值类间距离定义（续）离差平方和

4、：设N个样品原分q类，则第i类离差平方和为离差平方和增量：设样本已分成ωp,ωq两类，若把ωp,ωq合为ωr类，则定义离差平方聚类的准则函数—类内距离聚类的准则函数—类间距离基于类内、类间距离准则聚类的技术方案根据相似性阈值和最小距离原则的简单聚类确定相似性阈值，将模式到各聚类中心间的距离与阈值比较，都大于阈值时该模式就作为另一类的类心，小于阈值时按最小距离原则将其分划到某一类中。按最小距离原则不断进行两类合并的方法首先视各模式自成一类，然后将距离最小的两类合并成一类，不断地重复这个过程，直到成为两类为

5、止。依据准则函数动态聚类法设定一些分类的控制参数，定义一个能表征聚类过程或结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。根据相似性阈值和最小距离原则的简单聚类l．条件及约定待分类的模式集为{X1,X2,…,XN}，选定类内距离门限T。2．算法思想计算模式特征矢量到聚类中心的距离并和门限T比较，决定归属哪类或作为新的一类中心。通常采用欧氏距离。3.算法步骤(1)取任意的一个模式作为聚类中心。ω1，中心z1=x1(2)计算下一模式x2到z1的距离d21，ifd21>T建立新类ω2，中心为z2=

6、x2；否则x2属于ω1。(3)设有z1,z2,…,zk,计算未定类别xi到zj(j=1,…,k)的距离dij，ifdij>T建立新类ωk+1，中心为zk+1=xi；否则如果dil=min[dij],j=1,2,…,k,则xi属于ωl。未结束，返回（3）。最大最小距离算法1．条件及约定待分类的模式特征矢量集为{Xl,X2…,XN}，选定比例系数θ2．基本思想在模式特征矢量集中以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。通常使用欧氏距离。3.算法步骤(1)取任意的一个模式作为第一类聚类中心。

7、ω1，中心z1=x1(2)选取距z1最远的特征矢量最为第二个聚类中心z2。(3)计算未作为聚类中心的各模式Xi与z1，z2的距离，求最小值.。(4)最大最小距离算法(5)设存在k个聚类中心，计算未作为聚类中心的各模式Xi到各聚类中心的距离dij，并算出(6)将各模式特征矢量按最小距离的原则分到各类中去。1234567891003215465670821383445系统聚类(谱系聚类法)1．条件及约定设待分类的模式特征矢量集为{Xl，X2…，XN}，Gi(k)表示第k次合并时的第i类。2．基本思想首先视N

8、个模式各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。3.算法步骤(1)初始分类。令k=0，每个模式自成一类，(2)计算各类间的距离，生成(3)找出前一步矩阵D（k）的最小元素，设它是Gi(k)和Gj(k)距离，将其合并为一类，形成G1(k+1)，G1(k+1)，…,k=k+1,m=m-1.(4)检查类的个数，如果大于2，转（2）