聚类方法第十一章优秀课件.ppt

《聚类方法第十一章优秀课件.ppt》由会员分享，可在线阅读，更多相关《聚类方法第十一章优秀课件.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、聚类方法第十一章第1页，本讲稿共38页划分聚类划分聚类一、按最邻近规则的简单试探法一、按最邻近规则的简单试探法 给N个待分类的模式样本 ，要求按距离阈值T分类到聚类中心v算法过程：算法过程：vStep 1：取任意的样本x xi i作为一聚类中的初始值，如令z z1 1=x=x1 1，计算若D21T，确定一新的聚类中心z z2 2=x=x2 2否则x x2 2以z z1 1为中心的聚类；第2页，本讲稿共38页vStep 2：假如已有聚类中心z z1 1和z z2 2，计算 若D31T和D32T，则确定一新的聚类中心z z3 3=x=x3 3；vStep i：第3页，本讲稿共38页v讨论讨论v这种

2、方法的优点：计算简单，若模式样本的集合分布的先验知识已知，则可获得较好的聚类结果。v在实际中，对于高维模式样本很难获得准确的先验知识，因此只能选用不同的阈值和起始点来试探，并对结果进行验证。v这种方法在很大程度上依赖于以下因素：v第一个聚类中心的位置（初始化问题初始化问题）v待分类模式样本排列次序（聚类样本的选择问题聚类样本的选择问题）v距离阈值T的大小（判决准则问题判决准则问题）v样本分布的几何性质（样本的固有特性问题样本的固有特性问题）第4页，本讲稿共38页层次聚类层次聚类v系统聚类：系统聚类：先把每个样本作为一类，然后根据它们间的相似性或相邻性聚合，类别由多到少，直到获得合适的分类要求为

3、止；相似性、相邻性用距离表示。聚合的关键就是每次迭代中形成的聚类之间以及它们和样本之间距离的计算，不同的距离函数会得到不同结果。v两类间距离计算准则两类间距离计算准则：v1.最短距离：两类中相距最近的两样本间的距离第5页，本讲稿共38页 2.最长距离 ：两类中相距最远的两个样本间的距离。3.类平均距离：两类中各个元素两两之间的距离平方相加后取平均值 4.类中心距离第6页，本讲稿共38页算法过程描述：算法过程描述：Step1：初始距离矩阵的计算D(0)说明：（1）距离矩阵元素的值是类与类之间的距离，距离的定义有多种。（2）距离矩阵，是对称矩阵。对角线上的元值表示同类之间的距离，即为0。Step2

4、：对于第n次迭代的距离矩阵D(n)进行聚合说明：距离矩阵中选择距离最小的，如果有相同的可以任选其中一个，要忽略对角线上的元素。第7页，本讲稿共38页 vStep3：根据第n次聚合结果，计算合并后的新类别之间的距离矩阵D(n+1)说明：合并类的距离计算应该符合距离的运算规则。如，距离反映的是两类的重心距离，那么合并后，应该仍然反映的重心的距离。vStep4：收敛性判决 说明：算法的收敛条件判断准则的确定。第8页，本讲稿共38页例例1：如下图所示（简单的一维情况）1、设全部样本分为6类，2、计算距离矩阵D(0)第9页，本讲稿共38页123456102903116044916640525436406

5、642581190第10页，本讲稿共38页3、求最小元素：4、把1,3合并7=(1,3)4,6合并8=(4,6)5、作距离矩阵D(1)，按最小距离准则728570290849160525440第11页，本讲稿共38页6、若合并的类数没有达到要求，转3。否则停止。3、求最小元素：4、8,5,2合并,9=（2,5,4,6）第12页，本讲稿共38页分解聚类分解聚类v分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。v目标函数：两类中心的距离 N：总样本数，：1类样本数 ：2类样本数，第13页，本讲稿共38页分解聚类框图分解聚类框图初始分类初始分类调整分类方案调整分类方案最终结果最终结果目标函

6、数目标函数达到最优先？达到最优先？第14页，本讲稿共38页例例2：已知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第15页，本讲稿共38页目标函数解：第一次分类时计算所有样本，分别划到 时的E值，找出最大E值对应的样本。1、开始时，第16页，本讲稿共38页 2、分别计算当 划入 时的E值把 划入 时有第17页，本讲稿共38页 然后再计算把 划入 时对应的E值，找出一个最大的E值。一直计算

7、下去 把 划为 的E值最大。E(1)=56.6再继续进行第二，第三次迭代计算出 E(2),E(3),第18页，本讲稿共38页 次数 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第19页，本讲稿共38页 第10次迭代 划入 时，E最大。于是分成以下两类：每次分类后要重新计算 的值。可用以下递推公式：第20页，本讲稿共38页第21页，本讲稿共38页动态聚类动态聚类-K-means一、动态聚类的方法概要一、动态聚类的方法概要 先选定某种距离作为样本

8、间的相似性的度量;确定评价聚类结果的准则函数;给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。第22页，本讲稿共38页选代表点初始分类分类合理否最终分类修改分类YN动态聚类框图动态聚类框图第23页，本讲稿共38页 二、代表点（种子点）的选取方法：二、代表点（种子点）的选取方法：代表点就是初始分类的k个聚类中心 凭经验选代表点，根据问题的性质、数据分布，从直观上看来较合理的k个代表点;将全部样本随机分成k类，计算每类重心，把这些重心作为每类的代表点;用前k个样本点作为代表点。第24页，本讲稿共38页 按密度大小选代表点：以每个样本作为球心，以d为半径做球形；落在球内的样本数称为该

9、点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代表点的距离大于d1（人为规定的正数）则把第二大密度点作为第二代表点，否则不能作为代表点，这样按密度大小考察下去，所选代表点间的距离都大于d1。d1太小，代表点太多，d1太大，代表点太小，一般选d12d。对代表点内的密度一般要求大于T。T0为规定的一个正数。第25页，本讲稿共38页三、初始分类和调整三、初始分类和调整 选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。选一批代表

10、点后,依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。直接用样本进行初始分类，先规定距离d,把第一个样品作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于d，就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于d，决定分裂还是合并。第26页，本讲稿共38页最佳初始分类：如图所示，随着初始分类k的增大，准则函数下降很快，经过拐点A后，下降速度减慢。拐

11、点A就是最佳初始分类。第27页，本讲稿共38页四、四、K-均值算法：成批处理法均值算法：成批处理法例：例：已知有20个样本，每个样本有2个特征，数据分布如下图第一步：令K=2，选初始聚类中心为样本序号x1x2x3x4x5x6x7x8x9x10特征x10101212367特征x20011122266x11x12x13x14x15x16x17x18x19x2086789789896777788899第28页，本讲稿共38页第29页，本讲稿共38页第30页，本讲稿共38页第31页，本讲稿共38页第32页，本讲稿共38页第三步：根据新分成的两类建立新的聚类中心第四步：转第二步。第二步：重新计算 到z1

12、(2),z2(2)的距离，把它们归为最近聚类中心，重新分为两类，第33页，本讲稿共38页第三步，更新聚类中心第34页，本讲稿共38页第四步，第二步，第三步，更新聚类中心第35页，本讲稿共38页v说明：说明：(1)K是指需要分成K类，均值是指每类的中心,就是该类所有样本的平均值，不一定就有某个样本在这个位置上。(2)算法的收敛性判别：前后两次迭代的结果，也就是每迭代分类后，分类都是一样的，此时停止。(3)K值和初始聚类中心对分类的结果影响很大。通常需要其它的算法来确定这两个的选取。第36页，本讲稿共38页v讨论讨论vK-均值算法的结果受如下选择的影响：v所选聚类的数目v聚类中心的初始分布v模式样本的几何性质v读入次序v在实际应用中，需要试探不同的K值和选择不同的聚类中心的起始值。v如果模式样本可以形成若干个相距较远的孤立的区域分布，一般都能得到较好的收敛效果。vK-均值算法比较适合于分类数目已知的情况。第37页，本讲稿共38页作业作业1.给定5个6维模式样本（如下），试按最小(欧氏)距离准则进行系统聚类分析。2.已知十个样本，每个样本2个特征，数据如下：用K-均值算法分成3类。样本序号1 2 3 4 5 6 7 8 9 10 x10 1 2 4 5 5 6 1 1 1 x20 1 1 3 3 4 5 4 5 6第38页，本讲稿共38页