模式识别-聚类的算法课件

12·4聚类的算法2.4.1聚类的技术方案聚类分析有很多具体的算法,有的比较简单,有的相对复杂和完善,但归纳起来就是三大类:1、按最小距离原则简单聚类方法2、按最小距离原则进行两类合并的方法3、依据准则函数动态聚类方法12·4聚类的算法2.4.1聚类的技术方案聚类分析22·4聚类的算法(1)简单聚类方法

针对具体问题确定相似性阈值，将模式到各聚类中心间的距离与阈值比较，当大于阈值时该模式就作为另一类的类心，小于阈值时按最小距离原则将其分划到某一类中。这类算法运行中模式的类别及类的中心一旦确定将不会改变。22·4聚类的算法(1)简单聚类方法32·4聚类的算法首先视各模式自成一类,然后将距离最小的两类合并成一类,不断地重复这个过程，直到成为两类为止。(2)按最小距离原则进行两类合并的方法这类算法运行中，类心不断地修正，但模式类别一旦指定后就不再改变，就是模式一旦划为一类后就不再被分划开，这类算法也称为谱系聚类法。32·4聚类的算法首先视各模式自成一类,然后将距离最小42·4聚类的算法(3)依据准则函数动态聚类法设定一些分类的控制参数，定义一个能表征聚类结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。算法运行中，类心不断地修正，各模式的类别的指定也不断地更改。这类方法有—C均值法、ISODATA法等。42·4聚类的算法(3)依据准则函数动态聚类法设定一52·4聚类的算法--简单聚类方法

52·4聚类的算法--简单聚类方法62·4聚类的算法--简单聚类方法

62·4聚类的算法--简单聚类方法72·4聚类的算法--简单聚类方法

72·4聚类的算法--简单聚类方法82·4聚类的算法--简单聚类方法

这类算法的突出优点是算法简单。但聚类过程中，类的中心一旦确定将不会改变，模式一旦指定类后也不再改变。算法特点:从算法的过程可以看出，该算法结果很大程度上依赖于距离门限T的选取及模式参与分类的次序。如果能有先验知识指导门限T的选取，通常可获得较合理的效果。也可考虑设置不同的T和选择不同的次序，最后选择较好的结果进行比较。82·4聚类的算法--简单聚类方法这类算法的突出优点是92·4聚类的算法--简单聚类方法

简单聚类图例92·4聚类的算法--简单聚类方法简单聚类图例10例2.4.1：初始条件不同的简单聚类结果初始中心不同门限不同样本顺序不同

12345

12345

12345

12345

1098

1098

876

876

1167

1167

91011

9101110例2.4.1：初始条件不同的简单聚类结果初始中心不同门限112·4聚类的算法—最大最小距离法

112·4聚类的算法—最大最小距离法122·4聚类的算法--最大最小距离法

⒊算法原理步骤⑴选任一模式特征矢量作为第一个聚类中心例如，。作为第二个聚类中心。⑵从待分类矢量集中选距离最远的特征矢量122·4聚类的算法--最大最小距离法⒊算法原理步骤13⑶计算未被作为聚类中心的各模式特征矢量与、之间的距离，并求出它们之中的最小值，

为表述简洁，虽然某些模式已选做聚类中心，但上面仍将所有模式下角标全部列写出来，因这并不影响算法的正确性。即13⑶计算未被作为聚类中心的各模式特征矢量与、之间的距离14则相应的特征矢量作为第三个聚类中心，然后转至⑸；否则，转至最后一步⑹。⑷若⑸设存在个聚类中心，计算未被作为聚类中心,并算出如果，则否则，转至最后一步⑹。的各特征矢量到各聚类中心的距离并转至⑸；14则相应的特征矢量作为第三个聚类中心，然后转至⑸；否则，转15⑹当判断出不再有新的聚类中心之后，将模式特中去，即计算当，则判。征矢量按最小距离原则分到各类这种算法的聚类结果与参数心的选取有关。如果没有先验知识指导和取，可适当调整和选取最合理的一种聚类。以及第一个聚类中的选，比较多次试探分类结果，15⑹当判断出不再有新的聚类中心之后，将模式特中去，即计161617Z1X1Z2X6Z3X7Z4X1(0,0)08045X2(1,2)15829X3(2,2)84017X4(3,8)73134X5(5,3)34261X6(4,8)80029X7(6,3)45290X8(5,4)41262X9(6,4)52201X10(7,5)74185Theta=0.217Z1X1Z2X6Z3X7Z4X1(0,0)01818192·4聚类的算法层次聚类法(HierarchicalClusteringMethod)(系统聚类法、谱系聚类法）按最小距离原则不断进行两类合并

2.4.3谱系聚类法192·4聚类的算法层次聚类法(Hierarchica202·4聚类的算法层次聚类法(HierarchicalClusteringMethod)(系统聚类法、谱系聚类法）按最小距离原则不断进行两类合并⒉算法思想

首先将N个模式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。

2.4.3谱系聚类法202·4聚类的算法层次聚类法(Hierarchica212·4聚类的算法

2.4.3谱系聚类法212·4聚类的算法2.4.3谱系聚类法222·4聚类的算法

2.4.3谱系聚类法222·4聚类的算法2.4.3谱系聚类法23例2.4.3：如下图所示1、设全部样本分为6类，2、作距离矩阵D(0)3、求最小元素：4、把ω1,ω3合并ω7=(1,3)ω4,ω6合并ω8=(4,6)5、作距离矩阵D(1)ω1ω2ω3ω4ω5ω23ω314ω4748ω55262ω685913D(0)23例2.4.3：如下图所示ω1ω2ω3ω4ω5ω23ω324例2.4.3：如下图所示1、设全部样本分为6类，2、作距离矩阵D(0)3、求最小元素：4、把ω1,ω3合并ω7=(1,3)ω4,ω6合并ω8=(4,6)5、作距离矩阵D(1)D(1)ω7ω2ω8ω23ω874ω552224例2.4.3：如下图所示D(1)ω7ω2ω8ω23ω8256、若合并的类数没有达到要求，转3。否则停止。3、求最小元素：4、ω8,ω5,ω2合并,ω9=（2,5,4,6）256、若合并的类数没有达到要求，转3。否则停止。2626272·4聚类的算法最大距离和层次聚类算法的一个共同特点是某个模式一旦划分到某一类之后，在后继的算法过程中就不改变了，而简单聚类算法中类心一旦选定后在后继算法过程中也不再改变了。因此，这些方法效果一般不会太理想。272·4聚类的算法最大距离和层次聚类算法的一个共同特点是282.确定评估聚类质量的准则函数。确定模式和聚类的距离测度。当采用欧氏距离时，是计算此模式和该类中心的欧氏距离；为能反映出类的模式分布结构，应采用马氏距离，设该类的均矢为，协方差阵为，则模式和该类的与该类均矢的马氏距离：距离平方为3.确定模式分划及聚类合并或分裂的规则。2·4聚类的算法——动态聚类算法要点282.确定评估聚类质量的准则函数。确定模式和聚类的距292·4聚类的算法——动态聚类的基本步骤建立初始聚类中心，进行初始聚类；计算模式和类的距离，调整模式的类别；计算各聚类的参数，删除、合并或分裂一些聚类；从初始聚类开始，运用迭代算法动态地改变模式的类别和聚类的中心使准则函数取得极值或设定的参数达到设计要求时停止。292·4聚类的算法——动态聚类的基本步骤建立初始聚类中心302·4聚类的算法——动态聚类的框图产生初始聚类中心聚类检验聚类合理性待分类模式分类结果合理再迭代/修改参数不合理302·4聚类的算法——动态聚类的框图产生初始聚类中心聚类31⒈条件及约定

设待分类的模式特征矢量集为：类的数目C是事先取定的。2·4聚类的算法

2.4.3动态聚类法——C-均值法⒉算法思想

该方法取定C个类别和选取

C个初始聚类中心，按最小距离原则将各模式分配到C类中的某一类，之后不断地计算类心和调整各模式的类别，最终使各模式到其判属类别中心的距离平方之和最小。31⒈条件及约定2·4聚类的算法2.4.3动态聚类322·4聚类的算法

2.4.3动态聚类法——C-均值法322·4聚类的算法2.4.3动态聚类法——C-均值33例2.4.2使用聚类算法实现图像分割在散射图上形成了两个聚类，利用模式识别的方法将其分开，就实现了图象的分割。33例2.4.2使用聚类算法实现图像分割在散射图上形成了两34

例2.4.3：已知有20个样本，每个样本有2个特征，数据分布如下图,使用C－均值法实现样本分类（C=2）。第一步：令C=2，选初始聚类中心为样本序号x1x2x3x4x5x6x7x8x9x10特征x10101212367特征x20011122266x11x12x13x14x15x16x17x18x19x208678978989677778889934例2.4.3：已知有20个样本，每个样本有2个特征，数35353600第二步：000＝））－（（＝-10100＝））－（（＝-10001＝））－（（＝-所以因为Î-<-3600第二步：000＝））－（（＝-10100＝））－（（370)01()01(=-=-,Î->-所以因为同理,12,21Î\=->-Î\=-<-＝＝......20652065都属于、、离计算出来，判断与第二个聚类中心的距、、同样把所有因此分为两类：),...,,()1(),,()1(205422311==18,221==NNGG二、一、370)01()01(=-=-,Î->-所以因为同理,12,3838393940第三步：更新聚类中心40第三步：更新聚类中心414142第四步：第二步：第三步：更新聚类中心42第四步：4343应用图像分割44应用图像分割4445clustering2·4聚类的算法

2.4.3动态聚类法——C-均值法程序45clustering2·4聚类的算法2.4.3动46作业P45:2.7,2.846作业P45:2.7,2.8472·4聚类的算法

2.4.3动态聚类法——C-均值法关于C-均值法收敛性的分析472·4聚类的算法2.4.3动态聚类法——C-均值482·4聚类的算法

2.4.3动态聚类法——C-均值法当模式分布呈现类内团聚状，C-均值算法是能达到很好的聚类结果，故应用较多。从算法的迭代过程看，C-均值算法是能使各模式到其所判属的类别中心距离(平方)之和为最小的最佳聚类。482·4聚类的算法2.4.3动态聚类法——C-均值492·4聚类的算法

2.4.3动态聚类法——C-均值法的改进在类别数未知的情况下，可使类数C由较小值逐步增加，对于每个选定的C分别使用该算法。显然准则函数J是随C的增加而单调减少。⑴C的调整作一条C一J曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。在增加过程中，总会出现使本来较密集的类再拆开的情况，此时J虽减小，但减小速度将变缓。如果作一条C一J曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。然而在许多情况下，曲线并无明显的这样的点。492·4聚类的算法2.4.3动态聚类法——C-均值502·4聚类的算法

2.4.3动态聚类法——C-均值法的改进⑵初始聚类中心的选取①凭经验选择初始类心。②将模式随机地分成C类，计算每类中心，以其作为初始类心。③（最大密度），求以每个特征点为球心、某一正数d0为半径的球形域中特征点个数，这个数称为该点的密度。选取密度最大的特征点作为第一个初始类心Z1，然后在与Z1大于某个距离d的那些特征点中选取具有“最大”密度的特征点作为第二个初始类心Z2

，如此进行，选取C个初始聚类中心。502·4聚类的算法2.4.3动态聚类法——C-均值512·4聚类的算法

2.4.3动态聚类法——C-均值法的改进⑵初始聚类中心的选取④用相距最远的C个特征点作为初始类心。具体地讲，是按前述的最大最小距离算法求取C个初始聚类中心。⑤当N较大时，先随机地从N个模式中取出一部分模式用谱系聚类法聚成C类，以每类的重心作为初始类心。⑥设已标准化的待分类模式集为希望将它们分为C类。512·4聚类的算法2.4.3动态聚类法——C-均值52⑥设已标准化的待分类模式集为希望将它们分为C类。设:计算:显然0≤ai≤C，若ai最接近整数j，则把xi分划至中wj。对所有样本都实行上述处理，就可实现初始分类，从而产生初始聚类中心。52⑥设已标准化的待分类模式集为设:计算:532·4聚类的算法

2.4.3动态聚类法——C-均值法的改进⑶用类核代替类心前面的算法存在一个不足，即只用一个聚类中心点作为一类的代表，但一个点往往不能充分地反映该类的模式分布结构，从而损失了很多有用的信息。当类的分布不是球状或近似球状时，这种算法很难有较好的效果。此时，可用类核代替类心，类核可以是一个函数、一个点集或其他适当的模型。比如前面我们讲过的马式距离。532·4聚类的算法2.4.3动态聚类法——C-均值545455(3)动态聚类法——ISODATA算法(IterativeSelf-OrganizingDataAnalysisTechniquesAlgorithm迭代自组织数据分析)特点：启发性推理、分析监督、控制聚类结构及人机交互。算法思想： 在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地“自组织”，以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。55(3)动态聚类法——ISODATA算法(Iterati56ISODATA算法原理步骤⑴预置①设定聚类分析控制参数：=预期的类数，=每一类中允许的最少模式数目，=初始聚类中心个数(可以不等于c)，=类内各分量分布的距离标准差上界，(分裂用)=两类中心间的最小距离下界，(合并用)=在每次迭代中可以合并的类的最多对数，=允许的最多迭代次数。56ISODATA算法原理步骤⑴预置=预期的类数，=每57ISODATA算法原理步骤57ISODATA算法原理步骤58ISODATA算法原理步骤58ISODATA算法原理步骤59ISODATA算法原理步骤 ①计算各类的中心⑷计算分类后的参数:各类中心、类内平均距离及总体平均距离。②计算各类中模式到类心的平均距离 ③计算各个模式到其类内中心的总体平均距离59ISODATA算法原理步骤 ①计算各类的中心⑷60ISODATA算法原理步骤60ISODATA算法原理步骤61ISODATA算法原理步骤⑹计算各类类内距离的标准差矢量式中，为分量编号，为类的编号，为矢量维数，是的第个分量，是的第个分量。61ISODATA算法原理步骤⑹计算各类类内距离的标准62ISODATA算法原理步骤62ISODATA算法原理步骤63ISODATA算法原理步骤63ISODATA算法原理步骤64ISODATA算法原理步骤64ISODATA算法原理步骤65ISODATA算法原理步骤65ISODATA算法原理步骤666667ISODATA算法举例(二维)(1)初始值设定:类间距离上限距离标准差上界最少模式数目合并的类的最多对数67ISODATA算法举例(二维)(1)初始值设定:类间距离68ISODATA算法举例(2)聚类(只有一个中心):68ISODATA算法举例(2)聚类(只有一个中心):69ISODATA算法举例(3)

因,无合并:(4)计算聚类中心、类内平均距离和总的平均距离。69ISODATA算法举例(3)因,70ISODATA算法举例(5)因不是最后一步迭代，且，转至⑹(6)求的标准差矢量70ISODATA算法举例(5)因不是最后一步迭代，且71ISODATA算法举例(7)

算得(6)因且将分裂成两类，取，则且转(2)71ISODATA算法举例(7)算得(6)因72ISODATA算法举例(2)聚类(两个中心):(3)

因,无合并:72ISODATA算法举例(2)聚类(两个中心):(3)因73ISODATA算法举例(4)计算聚类中心、类内平均距离和总的平均距离。(5)因这是偶次迭代，满足算法原理步骤⑸中④的条件，故转⑼73ISODATA算法举例(4)计算聚类中心、类内平均距74ISODATA算法举例(9)计算类间距离由，类不能合并。(11)因不是最后一次迭代(，题设)，，判断是否修改参数。由上面结果可知，已获得所要求类别数目，类间距离大于类内距离，每类样本数都有样本总数的足够大的百分比，因此不改变参数。74ISODATA算法举例(9)计算类间距离由75(2)～(4)计算结果与前一次迭代结果相同。(7)

,分裂条件不满足，转至⑼。，无新的变化，，转至⑵。(6)计算和的标准差矢量(5)没有任一种情况被满足，到⑹。与前一次迭代结果相同，无合并发生。75(2)～(4)计算结果与前一次迭代结果相同。(7)(676⑵～⑷与前一次迭代结果相同。⑸因是最后一次迭代，令，转至⑼。⑼，同前。⑽因，无合并发生。⑾因是最后一次迭代,

结束。76⑵～⑷与前一次迭代结果相同。77Start输入样本数据，置c;Nc;选初始类心zj

，j=1,2,..Nc(1)置控制参数：

n,

s,

D,

,L,I(3)合并判决：

nj<

n