模式识别聚类续精选文档.ppt

《模式识别聚类续精选文档.ppt》由会员分享，可在线阅读，更多相关《模式识别聚类续精选文档.ppt（77页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模式识别聚类续本讲稿第一页，共七十七页 两种简单的聚类算法两种简单的聚类算法本讲稿第二页，共七十七页 两种简单的聚类算法（续）两种简单的聚类算法（续）2最大最小距离聚类算法最大最小距离聚类算法例：例：样样本分布如本分布如图图所示。所示。本讲稿第三页，共七十七页本讲稿第四页，共七十七页本讲稿第五页，共七十七页系统聚类系统聚类：先把每个样本作为一类，然系统聚类：先把每个样本作为一类，然后根据它们间的相似性和相邻性聚合。后根据它们间的相似性和相邻性聚合。相似性、相邻性一般用距离表示相似性、相邻性一般用距离表示（1）两类间的距离）两类间的距离1、最短距离：两类中相距最近的两样本间、最短距离：两类中相距

2、最近的两样本间的距离。的距离。本讲稿第六页，共七十七页 2、最长距离、最长距离 ：两类中相距最远的两个样本间的距：两类中相距最远的两个样本间的距离。离。3、中间距离：最短距离和最长距离都有片面、中间距离：最短距离和最长距离都有片面性，因此有时用中间距离。性，因此有时用中间距离。设设1类和类和23类间的最类间的最短距离为短距离为d12，最长距离为，最长距离为d13，23类的长度为类的长度为d23，则，则中间距离为中间距离为d0：本讲稿第七页，共七十七页4、重心距离：均值间的距离、重心距离：均值间的距离5、类平均距离：两类中各个元素两两之间的距、类平均距离：两类中各个元素两两之间的距离平方相加后取

3、平均值离平方相加后取平均值 本讲稿第八页，共七十七页6、离差平方和：设N个样品原分q类，则定义第i类的离差平方和为：离差平方和增量：设样本已分成p,q两类，若把p,q合为r类，则定义离差平方：本讲稿第九页，共七十七页（2）系统聚类的算法）系统聚类的算法 首先将首先将m个样品自成一类，然后每次将具有最小距离个样品自成一类，然后每次将具有最小距离的两类合并，合并后重新计算类与类之间的距离，这个的两类合并，合并后重新计算类与类之间的距离，这个过程一直继续到所有样品归为一类为止。过程一直继续到所有样品归为一类为止。例：如下图所示例：如下图所示 1、设全部样本分为、设全部样本分为6类，类，本讲稿第十页，

4、共七十七页12345293116449166452543646642581192、作距离矩阵、作距离矩阵D(0)本讲稿第十一页，共七十七页3、求最小元素：4、把1,3合并7=(1,3)4,6合并8=(4,6)5、作距离矩阵D(1)728298491652544本讲稿第十二页，共七十七页6、若合并的类数没有达到要求，转3。否则停止。3、求最小元素：4、8,5,2合并,9=（2,5,4,6）本讲稿第十三页，共七十七页分解聚类分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。目标函数 两类均值方差 N：总样本数，：1类样本数 ：2类样本数，本讲稿第十四页，共七十七页v分解聚类框图：初始分类调

5、整分类方案最终结果目标函数达到最优？本讲稿第十五页，共七十七页对分算法：略 例：已知21个样本，每个样本取二个特征，原始资料矩阵如下表：样本号 12345678910 x10022445667x2655343121011 12 13 14 15 16 17 18 19 20 21-4-2-3-3-5100-1-1-3322021-1-2-1-3-5本讲稿第十六页，共七十七页本讲稿第十七页，共七十七页目标函数解：第一次分类时计算所有样本，分别划到时的E值，找出最大的。1、开始时，本讲稿第十八页，共七十七页 2、分别计算当 划入 时的E值把 划入时有本讲稿第十九页，共七十七页 然后再把 划入 时对

6、应的E值，找出一个最大的E值。把 划为 的E值最大。E(1)=56.6再继续进行第二，第三次迭代计算出 E(2),E(3),本讲稿第二十页，共七十七页 次数 E值 1 56.6 2 79.16 3 90.90 4 102.61 5 120.11 6 137.15 7 154.10 8 176.15 9 195.26 10 213.07 11 212.01本讲稿第二十一页，共七十七页 第10次迭代 划入 时，E最大。于是分成以下两类：每次分类后要重新计算 的值。可用以下递推公式：本讲稿第二十二页，共七十七页动态聚类兼顾系统聚类和分解聚类一、动态聚类的方法概要一、动态聚类的方法概要 先选定某种距离

7、作为样本间的相似性的先选定某种距离作为样本间的相似性的度量度量;确定评价聚类结果的准则函数确定评价聚类结果的准则函数;给出某种初始分类，用迭代法找出使准给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。则函数取极值的最好的聚类结果。本讲稿第二十三页，共七十七页 二、代表点的选取方法：代表点就是初始分类二、代表点的选取方法：代表点就是初始分类的聚类中心数的聚类中心数k 凭经验选代表点，根据问题的性质、数据分布，从凭经验选代表点，根据问题的性质、数据分布，从直观上看来较合理的代表点直观上看来较合理的代表点k;将全部样本随机分成将全部样本随机分成k类，计算每类重心，把这些重心类，计算每

8、类重心，把这些重心作为每类的代表点作为每类的代表点;本讲稿第二十四页，共七十七页 按密度大小选代表点：按密度大小选代表点：以每个样本作为球心，以以每个样本作为球心，以d为半径做球形为半径做球形;落在球内的样本落在球内的样本数称为该点的密度，并按密度大小排序。首先选密度最大的作为数称为该点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代表点的距离大于二大密度点距第一代表点的距离大于d1（人为规定的正数）则把（人为规定的正数）则把第二大密度点作为第二代表点，否则不能作为代

9、表点，这样按第二大密度点作为第二代表点，否则不能作为代表点，这样按密度大小考察下去，所选代表点间的距离都大于密度大小考察下去，所选代表点间的距离都大于d1。d1太小，代太小，代表点太多，表点太多，d1太大，代表点太小，一般选太大，代表点太小，一般选d12d。对代表点内的。对代表点内的密度一般要求大于密度一般要求大于T。T0为规定的一个正数。为规定的一个正数。用前用前k个样本点作为代表点。个样本点作为代表点。本讲稿第二十五页，共七十七页三、初始分类和调整三、初始分类和调整 选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，

10、把所有样本归于最近的聚类中心点，形成初始分类，再重新计算的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。各聚类中心，称为成批处理法。选一批代表点后选一批代表点后,依次计算其它样本的归类，当计算完第一个依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处归类。即每个样本的归类都改变一次聚类中

11、心。此法称为逐个处理法。理法。直接用样本进行初始分类，先规定距离直接用样本进行初始分类，先规定距离d,把第一个样本作为把第一个样本作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于中心距离小于d，就把第二个样本归于第一类，否则第二个样本就成，就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于于还是小于d，决定分裂还是合并。，决定分裂还是合并。本讲稿第二十六页，共七十七页最佳初始分类。如图所示

12、，随着初始分类k的增大，准则函数下降很快，经过拐点A后，下降速度减慢。拐点A就是最佳初始分类。本讲稿第二十七页，共七十七页1C均值聚类算法均值聚类算法聚类准则函数是误差平方和准则：聚类准则函数是误差平方和准则：四、四、c均值与均值与ISODATA聚类算法聚类算法本讲稿第二十八页，共七十七页算法特点：每次迭代中都要考查每个样本的分类是否正确，若不正确，就要调整，在全部样本调整完之后，再修改聚合中心，进入下一次迭代。如果在某一个迭代运算中，所有的样本都被正确分类，则样本不会调整，聚合中心也不会有变化，也就是收敛了。c个初始聚合中心的选择对聚类结果有较大影响。本讲稿第二十九页，共七十七页本讲稿第三十

13、页，共七十七页本讲稿第三十一页，共七十七页本讲稿第三十二页，共七十七页 对每个聚合中的每个样本，计算：2)(|)(|1IZxnniikiiii-=r，ci,.2,1=iir表示cJ减少的部分。2)(|)(|1IZxnnjikjjij-+=r，cj,.2,1=，ij ijr表示cJ增加的部分。令：minijijilrr=，若iiilrr，则把样本)(ikx移到聚合中心lw中，并修改聚合中心和cJ值。)(11)()1()(ikiiiixIZnIZIZ-+=+)(11)()1()(iklljlxIZnIZIZ-+-=+)()()1(iliiccIJIJrr-=+判断：若)()1(IJIJcc+，则1

14、+=II，返回。否则，算法结束。本讲稿第三十三页，共七十七页本讲稿第三十四页，共七十七页本讲稿第三十五页，共七十七页本讲稿第三十六页，共七十七页Jc与C的关系曲线上述上述C均值算法，其类型数目假定已知，均值算法，其类型数目假定已知，为为c。对于未知时，可以令。对于未知时，可以令c逐渐增加。逐渐增加。使用使用C均值算法，误差平方和均值算法，误差平方和Jc随随c的增的增加而单调减少。最初，由于加而单调减少。最初，由于c较小，类型的较小，类型的分裂会使分裂会使 Jc迅速减小，但当迅速减小，但当c增加到一定数增加到一定数值时，值时，Jc的减小速度会减慢，直到的减小速度会减慢，直到c=n时，时，Jc=0

15、。Jc-C关系曲线如下图。关系曲线如下图。本讲稿第三十七页，共七十七页图中，曲线的拐点A对应着接近最优的c值。并非所有的情况都容易找到JcC关系曲线的拐点，此时c值将无法确定。下面介绍一种确定类型数目c的方法。本讲稿第三十八页，共七十七页2ISODATA聚类算法聚类算法ISODATA算法：Iterative Self-Organizing Data Analysis Technigues Algorithm，迭代自组织的数据分析算法。ISODATA算法特点：可以通过类的自动合并（两类合一）与分裂（一类分为二），得到较合理的类型数目c。具体算法步骤：给定控制参数k：预期的聚类中心数目。四、四、c

16、均值与均值与ISODATA聚类算法（续）聚类算法（续）本讲稿第三十九页，共七十七页本讲稿第四十页，共七十七页本讲稿第四十一页，共七十七页本讲稿第四十二页，共七十七页本讲稿第四十三页，共七十七页本讲稿第四十四页，共七十七页本讲稿第四十五页，共七十七页本讲稿第四十六页，共七十七页本讲稿第四十七页，共七十七页本讲稿第四十八页，共七十七页本讲稿第四十九页，共七十七页本讲稿第五十页，共七十七页本讲稿第五十一页，共七十七页ISODATA算法中，起始聚合中心的选取对聚类过程和结果都有较大影响，如果选择的好，则算法收敛快，聚类质量高。注意：ISODATA与C均值算法的异同点：都是动态聚类算法。C均值简单，IS

17、ODATA复杂。C均值中，类型数目固定，ISODATA中，类型数目可变。本讲稿第五十二页，共七十七页各类呈椭圆状分布时C-均值算法效果不好本讲稿第五十三页，共七十七页五、基于样本和核相似性度量基于样本和核相似性度量的聚类算法采用一个“核”来代表一个类核Kj可以是一个函数，一个点集，等等样本和核之间相似性的度量准则函数，最小化的目标本讲稿第五十四页，共七十七页样本和核相似性度量的聚类算法（续）算法步骤类似于C-均值1.选择初始划分并计算初始核2.重新分配各个样本3.修正核，并重复2-3直至收敛C-均值算法=以类均值为核，欧氏距离作为样本和核之间的相似性度量本讲稿第五十五页，共七十七页样本和核相似

18、性度量的聚类算法（续）算法收敛的充分条件：准则函数J满足，K修正之前的分类和对应的核 ，修正之后的分类和对应的本讲稿第五十六页，共七十七页样本和核相似性度量的聚类算法（续）正态核函数，适用于各类为正态分布参数集 从各类样本中估计相似性度量本讲稿第五十七页，共七十七页样本和核相似性度量的聚类算法（续）主轴核函数，适用于各类样本集中在各自的主轴方向上的子空间里的情况 是第j类样本协方差阵的前 个最大特征值对应的特征向量系统 是样本到主轴子空间的距离本讲稿第五十八页，共七十七页样本和核相似性度量的聚类算法（续）可以拟合各种形状的分布需要预先知道数据的分布形状本讲稿第五十九页，共七十七页本讲稿第六十页

19、，共七十七页六、近邻函数准则近邻函数准则算法近邻函数：样本间相似性的度量如果yi是yj的第I个近邻，yj是yi的第K个近邻近邻函数使得密度相近的点容易聚成一类本讲稿第六十一页，共七十七页近邻函数准则算法（续）纯粹按照欧氏距离，则黄色点归为第一类按照近邻函数值，黄色点归为第二类。这是比较合理的本讲稿第六十二页，共七十七页近邻函数准则算法（续）同一类中的点之间存在“连接”。连接损失就定义为两点之间的近邻函数ij。一个点和其自身的连接损失定义为ii=2N，以惩罚只有一个点的聚类不同类的点不存在连接，连接损失为ij=0总类内损失本讲稿第六十三页，共七十七页近邻函数准则算法（续）第i类和第j类之间的最小

20、近邻函数值定义为第i类内最大连接损失记为imax第i类与第j类之间的连接损失定义为ij,本讲稿第六十四页，共七十七页近邻函数准则算法（续）ij的设计目标是：如果两类间的最小近邻值大于任何一方的类内的最大连接损失时，损失代价就是正的，从而应该考虑把这两类合并本讲稿第六十五页，共七十七页近邻函数准则算法（续）总类间损失准则函数本讲稿第六十六页，共七十七页近邻函数准则算法（续）算法步骤1.计算距离矩阵2.用距离矩阵计算近邻矩阵Mij，Mij表示yj是yi的第几个近邻3.计算近邻函数矩阵Lij=Mij+Mji-2I,Lii=2N4.在L 中，每个点与其最近邻连接，形成初始的划分5.对每两个类计算ij

21、和imax，jmax，只要ij 小于imax、jmax中的任何一个，就合并两类（建立连接）。重复至没有新的连接发生为止本讲稿第六十七页，共七十七页例：如图所示样本，使用近邻函数准则聚类。解：计算D矩阵，结果从简；计算M矩氏，结果从简；计算L矩阵，结果见表本讲稿第六十八页，共七十七页L12345678910 1112124 138486916 17 17 192124 038111114 17 17 18 1833024 110 13 912 15 16 18 17483124 710 610 14 16 15 1154810 724 00413 14 16 17681113 10 024 40

22、818 14 167611960424 0612 13 158914 12 10 40024 4812 14916 17 15 14 13 86424 13610 17 17 16 16 14 18 12 8124 031117 18 18 15 16 14 13 12 3024 112 19 18 17 1117 16 15 15 63124本讲稿第六十九页，共七十七页本讲稿第七十页，共七十七页 最小张树聚类术语：线段：两个模式样本点的连线路径：连接两点的线段序列回路：闭合路径连通图形：任两点之间有一条或一条以上的路径者。（即各点之间是连结起来的，但不一定直接相连。树图：没有回路的连通图形（

23、单线顺序相连，不闭合，不返回）本讲稿第七十一页，共七十七页张树图：包含模式样本集合中每一点的树图（即连结每一个模式样本点且没有重复的连通图）线段权重（线的重要性），（可取点间距离）整个树图的权重为树图中各线段权重之和。最小张树图：权重最小的张树图（若以距离作权重，则各模式样本点以最小距离连结每一样本点，且无重复），沿着该路线，连结相邻每点间的距离总和min一条路，经过最多点，代价最小。主直径：在最小张树图中走过最多模式样本点的那条路径本讲稿第七十二页，共七十七页最小张树图构成方法：计算距离表所有距离按从小到大顺序排列按距离从小到大顺序连结点对。规则：最小生成树算法，找到图的最小生成树，然后把树

24、上最长的边去掉形成两个类。在两个子图中再去掉最长边，依次进行下去本讲稿第七十三页，共七十七页ABDCFE4259810234例：递增排序：BC、DF、DE、EF、AB、AC、CD、AD、CF连接顺序：BC AB CD DF DE本讲稿第七十四页，共七十七页缺点：对密集点集之间干扰敏感改进：引入树的直径和点深度点的深度：与该点连接的最长分支的长度算法步骤如下：给定混合样本集，生成最小张树(可按距离给权值)；确定最小张树上的直径和计算直径上各点深度；绘制直径上各点的深度图，找出局部最小值；去掉局部最小值的点，获得分离的类型聚合。本讲稿第七十五页，共七十七页本讲稿第七十六页，共七十七页小结聚类是一个面向具体数据，具体应用的任务针对不同的数据，不同的目标选择不同的聚类算法算法对数据尺度(scale)敏感的问题采取什么样的相似性度量？数据的各个特征是可比较的吗？除了预先指定，怎么确定分类的数目？本讲稿第七十七页，共七十七页