第二章聚类分析.pptx

《第二章聚类分析.pptx》由会员分享，可在线阅读，更多相关《第二章聚类分析.pptx（163页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第二章 聚类分析 (Clustering Analysis)2.1 聚类分析的概念2.2 模式相似性测度2.3 类的定义与类间距离2.4 聚类的算法第1页/共163页22.1 聚类分析的概念一、聚类分析的基本思想 相似的归为一类。模式相似性的度量和聚类算法。无监督分类（Unsupervised）。二、特征量的类型 物理量-(重量、长度、速度)次序量-(等级、技能、学识)名义量-(性别、状态、种类)第二章 聚类分析第2页/共163页3三、方法的有效性 取决于分类算法和特征点分布情况的匹配。2.1 聚类分析的概念22W11W2x1xb分类无效时的情况1.特征选取不当使分类无效。第二章 聚类分析第

2、3页/共163页4三、方法的有效性 取决于分类算法和特征点分布情况的匹配。2.1 聚类分析的概念分类无效时的情况2.特征选取不足可能使不同类别的模式判为一类。22W11W2x1x33W第二章 聚类分析第4页/共163页5三、方法的有效性 取决于分类算法和特征点分布情况的匹配。2.1 聚类分析的概念分类无效时的情况3.特征选取过多可能无益反而有害,增加分析负担并使分析效果变差。22W11W2x1xb第二章 聚类分析第5页/共163页6三、方法的有效性 取决于分类算法和特征点分布情况的匹配。2.1 聚类分析的概念分类无效时的情况4.量纲选取不当。第二章 聚类分析第6页/共163页7三、方法的有效性

3、 取决于分类算法和特征点分布情况的匹配。2.1 聚类分析的概念分类无效时的情况4.量纲选取不当。第二章 聚类分析第7页/共163页8三、方法的有效性 取决于分类算法和特征点分布情况的匹配。2.1 聚类分析的概念分类无效时的情况4.量纲选取不当。第二章 聚类分析第8页/共163页9下列是一些动物的名称：羊 （sheep）狗 （dog）蓝鲨（blue shark）蜥蜴 （lizard）毒蛇（viper）猫 （cat）麻雀（sparrow）海鸥 （seagull）金鱼（gold fish）绯鲵鲣（red-mullet）蛙 （frog）要对这些动物进行分类，则不同的特征有不同的分法：特征选取不同对聚类

4、结果的影响第二章 聚类分析第9页/共163页10特征选取不同对聚类结果的影响羊,狗,猫蓝鲨蜥蜴,毒蛇,麻雀,海鸥,金鱼,绯鲵鲣,青蛙(a)按繁衍后代的方式分哺乳动物非哺乳动物第二章 聚类分析第10页/共163页11金鱼绯鲵鲣蓝鲨羊,狗,猫蜥蜴,毒蛇麻雀,海鸥 青蛙(b)按肺是否存在分无肺有肺特征选取不同对聚类结果的影响第二章 聚类分析第11页/共163页12青蛙羊,狗,猫 蜥蜴,毒蛇麻雀,海鸥 金鱼绯鲵鲣 蓝鲨(c)按生活环境分陆地水里两栖特征选取不同对聚类结果的影响第二章 聚类分析第12页/共163页13蓝鲨金鱼绯鲵鲣蜥蜴,毒蛇麻雀,海鸥 青蛙羊,狗,猫(d)按繁衍后代方式和肺是否存在分非哺

5、乳且有肺哺乳且无肺哺乳且有肺非哺乳且无肺特征选取不同对聚类结果的影响第二章 聚类分析第13页/共163页14距离测度不同,聚类结果也不同数据的粗聚类是两类,细聚类为4类第二章 聚类分析第14页/共163页15综上可见:选择什么特征？选择多少个特征？选择什么样的量纲？选择什么样的距离测度？这些对分类结果都会产生极大影响。第二章 聚类分析第15页/共163页聚类过程遵循的基本步骤 一、特征选择(feature selection)尽可能多地包含任务关心的信息二、近邻测度(proximity measure)定量测定两特征如何“相似”或“不相似”三、聚类准则（clustering criterion

6、）以蕴涵在数据集中类的类型为基础四、聚类算法（clustering algorithm）按近邻测度和聚类准则揭示数据集的聚类结构五、结果验证（validation of the results）常用逼近检验验证聚类结果的正确性六、结果判定（interpretation of the results）由专家用其他方法判定结果的正确性第16页/共163页17聚类应用的四个基本方向一、减少数据 许多时候，当数据量N很大时，会使数据处理变得很费力。因此可使用聚类分析的方法将数据分成几组可判断的聚类m（mN）来处理，每一个类可当作独立实体来对待。从这个角度看，数据被压缩了。第二章 聚类分析第17页/共1

7、63页18二、假说生成 在这种情况下，为了推导出数据性质的一些假说，对数据集进行聚类分析。因此，这里使用聚类作为建立假说的方法，然后用其他数据集验证这些假说。聚类应用的四个基本方向第二章 聚类分析第18页/共163页19聚类应用的四个基本方向三、假说检验 用聚类分析来验证指定假说的有效性。例如：考虑这样的假说“大公司在海外投资”。要验证这个假说是否正确，就要对大公司和有代表性的公司按规模、海外活跃度、成功完成项目的能力等进行聚类分析。从而来支持这个假说。第二章 聚类分析第19页/共163页20四、基于分组的预测 对现有数据进行聚类分析，形成模式的特征，并用特征表示聚类，接下来，对于一个未知模式

8、，就可以用前面的聚类来确定是哪一类？聚类应用的四个基本方向例如：考虑被同种疾病感染的病人数据集。先按聚类分析进行分类，然后对新的病人确定他适合的聚类，从而判断他病情。第二章 聚类分析第20页/共163页212.2 模式相似性测度 用于描述各模式之间特征的相似程度 距 离 测 度 相 似 测 度 匹 配 测 度第二章 聚类分析第21页/共163页222.2 模式相似性测度一、距离测度(差值测度)测度基础：两个矢量矢端的距离测度数值：两矢量各相应分量之差的函数。时，等号成立；，当且仅当第二章 聚类分析第22页/共163页232.2 模式相似性测度常用的距离测度有：1.欧氏(Euclidean)距离

9、 第二章 聚类分析第23页/共163页242.2 模式相似性测度4.明氏(Minkowski)距离 (2-2-4)2.绝对值距离(街坊距离或Manhattan距离)(2-2-2)3.切氏(Chebyshev)距离 (2-2-3)第二章 聚类分析第24页/共163页252.2 模式相似性测度第二章 聚类分析第25页/共163页262.2 模式相似性测度5.马氏(Mahalanobis)距离注意！马氏距离对一切非奇异线性变换都是不变的，这说明它不受特征量纲选择的影响，并且是平移不变的。上面的V的含义是这个矢量集的协方差阵的统计量，故马氏距离加入了对特征的相关性的考虑。第二章 聚类分析第26页/共1

10、63页272.2 模式相似性测度第二章 聚类分析第27页/共163页第28页/共163页现金识别例子(欧氏平均距离)数据样本介绍：10个文本文件文件名：rmb00.txt rmb09.txt每个文件有4个币种的数据，分别是：100圆、50圆、20圆、10圆每个币种有新旧两种版本，4个方向，故有8个数据块：如100圆的8个数据块：data100a,data100b,data100c,data100d老版 data100e,data100f,data100g,data100h新版每个数据块有8个传感器数据：传感器1，传感器2，传感器8每个传感器有60个采样数据：数据1，数据2，数据60第29页/共

11、163页现金识别例子Eucliden=15.000000Manhattan=33.000000Chebyshev=11.000000Minkowski=11.039449m=8100元A面第1个样本第10点和20点的距离X:(75,76,101,83,102,96,91,82)Y:(70,74,90,76,99,96,90,86)X-Y:5,2,11,7,3,0,1,-4距离测度rmbdis第30页/共163页现金识别例子欧式平均距离100a-100a:(2.65,49.66)24.41100a-100b:(16.37,55.87)33.97100a-100c:(3.87,58.34)29.4

12、1100a-100d:(6.86,53.74)33.04100a-100e:(3.87,62.12)27.51100a-100f:(13.60,67.61)34.67100a-100g:(11.40,68.56)32.27100a-100h:(11.27,68.61)34.43100a-50a:(18.76,76.20)40.72100a-20a:(13.23,81.28)42.87100a-10a:(12.45,90.91)54.99第31页/共163页现金识别例子100圆A面的马式矩阵SW为:43.5 53.9 64.8 52.7 52.7 52.3 46.8 37.9 53.9 132.

13、0 137.5 107.8 59.6 74.0 52.1 31.5 64.8 137.5 165.9 124.1 74.6 84.1 67.6 37.1 52.7 107.8 124.1 105.5 57.5 67.2 54.5 35.2 52.7 59.6 74.6 57.5 76.2 71.7 65.8 57.9 52.3 74.0 84.1 67.2 71.7 73.1 62.8 55.0 46.8 52.1 67.6 54.5 65.8 62.8 59.6 51.9 37.9 31.5 37.1 35.2 57.9 55.0 51.9 54.7第32页/共163页现金识别例子SW的逆矩

14、阵为:0.3 -0.0 0.1 -0.1 -0.1 -0.1 -0.2 0.2-0.0 0.3 -0.1 -0.1 0.1 -0.6 0.3 0.2 0.1 -0.1 0.3 -0.1 -0.0 -0.2 -0.3 0.4-0.1 -0.1 -0.1 0.2 0.1 0.3 -0.1 -0.2-0.1 0.1 -0.0 0.1 0.7 -0.7 -0.4 0.2-0.1 -0.6 -0.2 0.3 -0.7 2.2 -0.0 -1.0-0.2 0.3 -0.3 -0.1 -0.4 -0.0 1.2 -0.5 0.2 0.2 0.4 -0.2 0.2 -1.0 -0.5 1.0第33页/共163

15、页现金识别例子马式平均距离100a:(7.46,80.05)39.73100b:(26.75,179.86)91.89100c:(14.50,231.44)103.76100d:(11.69,155.28)78.58100e:(5.65,2968.84)247.42100f:(39.19,2191.91)108.10100g:(10.68,2875.99)265.16100h:(9.41,2673.54)107.56 50a:(22.78,221.07)101.41 20a:(22.51,343.26)162.90 10a:(20.93,975.67)256.38第34页/共163页现金识别例

16、子马式平均距离a:39.73 101.41 162.90 256.38b:91.89 230.25 288.69 659.47c:103.76 135.94 257.57 724.96d:78.58 171.10 330.97 675.90e:247.42 443.46 333.93 218.71f:108.10 328.11 305.19 607.51g:265.16 956.58 818.83 348.42h:107.56 339.64 387.10 628.88100圆 50圆 20圆 10圆其中马式矩阵为100圆A面的，上面是各面到100圆A面的均值点的平均马式距离。第35页/共163

17、页现金识别例子100圆A面的传感器1到其它各面传感器1的街坊距离第36页/共163页372.2 模式相似性测度二、相似测度测度基础：以两矢量的方向是否相近作为考虑的基础,矢量长度并不不重要。设1.角度相似系数(夹角余弦)(2-2-11)注意：坐标系的旋转和尺度的缩放是不变的,但对一般的线形变换和坐标系的平移不具有不变性。第37页/共163页38现金识别例子100圆A面传感器1与其它各面的相似系数第38页/共163页392.2 模式相似性测度二、相似测度2.相关系数它实际上是数据中心化后的矢量夹角余弦。(2-2-12)第39页/共163页40现金识别例子100圆A面传感器1与其它各面的相关系数第

18、40页/共163页412.2 模式相似性测度二、相似测度3.指数相似系数 (2-2-13)式中 为相应分量的协方差，为矢量维数。它不受量纲变化的影响。第41页/共163页42现金识别例子100圆A面传感器1与其它各面的相关系数第42页/共163页432.2 模式相似性测度当特征只有两个状态（0，1）时，常用匹配测度。0表示无此特征 1表示有此特征。故称之为二值特征。对于给定的x和y中的某两个相应分量xi与yj若xi=1,yj=1，则称 xi与yj是 (1-1)匹配；若xi=1,yj=0，则称 xi与yj是 (1-0)匹配；若xi=0,yj=1，则称 xi与yj是 (0-1)匹配；若xi=0,y

19、j=0，则称 xi与yj是 (0-0)匹配。二、匹配测度第43页/共163页442.2 模式相似性测度第44页/共163页452.2 模式相似性测度 三、匹配测度(1)Tanimoto测度第45页/共163页46例 可以看出，它等于可以看出，它等于共同具有的特征数目共同具有的特征数目与分与分别具有的特征种类总数之比。这里只考虑别具有的特征种类总数之比。这里只考虑(1-1)(1-1)匹匹配而不考虑配而不考虑(0-0)(0-0)匹配。匹配。设则2.2 模式相似性测度第46页/共163页47现金识别例子100圆A面与其它各面的匹配系数Tanimoto第47页/共163页482.2 模式相似性测度 三

20、、匹配测度(2)Rao测度注：(1-1)匹配特征数目和所选用的特征数目之比。第48页/共163页49现金识别例子100圆A面与其它各面的匹配系数Rao第49页/共163页502.2 模式相似性测度 三、匹配测度(3)简单匹配系数注：上式分子为(1-1)匹配特征数目与(0-0)匹配特征数目之和，分母为所考虑的特征数目。第50页/共163页51现金识别例子100圆A面与其它各面的匹配系数Simple第51页/共163页522.2 模式相似性测度 三、匹配测度(4)Dice系数(5)Kulzinsky系数第52页/共163页53现金识别例子100圆A面与其它各面的匹配系数dice第53页/共163页

21、54现金识别例子100圆A面与其它各面的匹配系数Kulzinsky第54页/共163页55作业P44:2.1,2.3第55页/共163页5623 类的定义与类间距离类的定义定义之1 设集合S中任意元素xi与yj间的距离dij有 dij h其中h为给定的阀值，称S对于阀值h组成一类。类的定义有很多种，类的划分具有人为规定性，这反映在定义的选取及参数的选择上。一个分类结果的优劣最后只能根据实际来评价。书中的其它定义方法请大家自行参考学习第56页/共163页5723 类的定义与类间距离类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法第57页/共163页582

22、3 类的定义与类间距离类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法式中 表示 和 之间的距离。第58页/共163页59现金识别例子100圆A面与其它各面的最小距离第59页/共163页6023 类的定义与类间距离类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法式中 表示 和 之间的距离。第60页/共163页61现金识别例子100圆A面与其它各面的最大距离第61页/共163页6223 类的定义与类间距离类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法pqkpqkpqDk

23、qDklDkpDl第62页/共163页6323 类的定义与类间距离类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法np,nq分别为类p和q的样本个数第63页/共163页6423 类的定义与类间距离类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法第64页/共163页65现金识别例子100圆A面与其它各面的平均距离第65页/共163页6623 类的定义与类间距离类间距离测度方法 最近距离法 最远距离法 中间距离法 重心距离法 平均距离法 离差平方和法分别为对应类的重心类内离差平方和 递推公式为:第66页/共163页

24、67 最近距离法最近距离法 1/2 1/2 0 -1/2 最远距离法最远距离法 1/2 1/2 0 1/2 中间距离法中间距离法 1/2 1/2 -1/4 0 重心距离法重心距离法 0 平均距离法平均距离法 0 0 可变平均法可变平均法 0 可变法可变法 0 离差平方和法离差平方和法 0第67页/共163页6823 类的定义与类间距离聚类的准则函数判别分类结果好坏的一般标准：类内距离小，类间距离大。某些算法需要一个能对分类过程或分类结果的优劣进行评估的准则函数。如果聚类准则函数选择得好，聚类质量就会高。聚类准则往往是和类的定义有关的，是类的定义的某种体现。第68页/共163页69聚类的准则函数

25、一、类内距离准则 设有待分类的模式集 在某种相似性测度基础上被划分为 类，类内距离准则函数 定义为:(表示 类的模式均值矢量。)(2-3-20)23 类的定义与类间距离第69页/共163页7023 类的定义与类间距离第70页/共163页71加权类内距离准则 :(2-3-22)(2-3-23)式中，表示类内任两个模式距离 个组合数，所以表示类内表示类先验概率的估计频率。平方和，共有两模式间的均方距离。N为待分类模式总数，第71页/共163页7223 类的定义与类间距离第72页/共163页73加权类间距离准则:对于两类问题，类间距离有时取(2-3-26)和的关系是(2-3-27)(2-3-25)第

26、73页/共163页7423 类的定义与类间距离第74页/共163页75 的类内离差阵定义为 (2-3-28)23 类的定义与类间距离式中 为类 的模式均值矢量 (2-3-29)第75页/共163页76第76页/共163页77例2.3.1 证明：23 类的定义与类间距离第77页/共163页78 聚类的基本目的是使 或 。利用线形代数有关矩阵的迹和行列式的性质,可以定义如下4个聚类的准则函数:23 类的定义与类间距离第78页/共163页7923 类的定义与类间距离 由它们的构造可以看出，为得到好的聚类结果，应该使它们尽量的大。这类准则也大量用在特征提取和选择中。第79页/共163页8023 类的定

27、义与类间距离J1=7.60886 J2=0.0010397J3=15.6089 J4=62.9116用纸币数据计算获得的结果：第80页/共163页81作业P44:2.4,2.5,2.6第81页/共163页8224 聚类的算法 聚类的技术方案聚类分析有很多具体的算法,有的比较简单,有的相对复杂和完善,但归纳起来就是三大类:1、按最小距离原则简单聚类方法2、按最小距离原则进行两类合并的方法3、依据准则函数动态聚类方法第82页/共163页8324 聚类的算法(1)简单聚类方法 针对具体问题确定相似性阈值，将模式到各聚类中心间的距离与阈值比较，当大于阈值时该模式就作为另一类的类心，小于阈值时按最小距离

28、原则将其分划到某一类中。这类算法运行中模式的类别及类的中心一旦确定将不会改变。第83页/共163页8424 聚类的算法 首先视各模式自成一类,然后将距离最小的两类合并成一类,不断地重复这个过程，直到成为两类为止。(2)按最小距离原则进行两类合并的方法这类算法运行中，类心不断地修正，但模式类别一旦指定后就不再改变，就是模式一旦划为一类后就不再被分划开，这类算法也称为谱系聚类法。第84页/共163页8524 聚类的算法(3)依据准则函数动态聚类法设定一些分类的控制参数，定义一个能表征聚类结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。算法运行中，类心不断地修正，各模式的类别的指定也不断

29、地更改。这类方法有C均值法、ISODATA法等。第85页/共163页8624 聚类的算法-简单聚类方法 第86页/共163页8724 聚类的算法-简单聚类方法 第87页/共163页8824 聚类的算法-简单聚类方法 第88页/共163页8924 聚类的算法-简单聚类方法 这类算法的突出优点是算法简单。但聚类过程中，类的中心一旦确定将不会改变，模式一旦指定类后也不再改变。算法特点:从算法的过程可以看出，该算法结果很大程度上依赖于距离门限T的选取及模式参与分类的次序。如果能有先验知识指导门限T的选取，通常可获得较合理的效果。也可考虑设置不同的T和选择不同的次序，最后选择较好的结果进行比较。第89页

30、/共163页9024 聚类的算法-简单聚类方法 简单聚类图例第90页/共163页91例：初始条件不同的简单聚类结果初始中心不同门限不同样本顺序不同 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 10 9 8 10 9 8 8 7 6 8 7 6 11 6 7 11 6 7 9 10 11 9 10 11第91页/共163页9224 聚类的算法简单聚类法程序 simpleclustering第92页/共163页9324 聚类的算法最大最小距离法 第93页/共163页9424 聚类的算法-最大最小距离法 算法原理步骤 选任一模式特征矢量作为第一个聚类中心例如，。作

31、为第二个聚类中心。从待分类矢量集中选距离最远的特征矢量第94页/共163页95 计算未被作为聚类中心的各模式特征矢量与、之间的距离，并求出它们之中的最小值，为表述简洁，虽然某些模式已选做聚类中心，但上面仍将所有模式下角标全部列写出来，因这并不影响算法的正确性。即第95页/共163页96则相应的特征矢量作为第三个聚类中心，然后转至；否则，转至最后一步。若 设存在个聚类中心，计算未被作为聚类中心,并算出如果，则否则，转至最后一步。的各特征矢量到各聚类中心的距离并转至；第96页/共163页97 当判断出不再有新的聚类中心之后，将模式特中去，即计算当，则判。征矢量按最小距离原则分到各类这种算法的聚类结

32、果与参数心的选取有关。如果没有先验知识指导和取，可适当调整和选取最合理的一种聚类。以及第一个聚类中的选，比较多次试探分类结果，第97页/共163页9824 聚类的算法最大最小距离法程序 maxminclustering第98页/共163页9924 聚类的算法层次聚类法(Hierarchical Clustering Method)(系统聚类法、谱系聚类法）按最小距离原则不断进行两类合并 谱系聚类法第99页/共163页10024 聚类的算法层次聚类法(Hierarchical Clustering Method)(系统聚类法、谱系聚类法）按最小距离原则不断进行两类合并 算法思想 首先将 N 个模

33、式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。谱系聚类法第100页/共163页10124 聚类的算法 谱系聚类法第101页/共163页10224 聚类的算法 谱系聚类法第102页/共163页103例：如下图所示 1、设全部样本分为6类，2、作距离矩阵D(0)3、求最小元素：4、把1,3合并7=(1,3)4,6合并8=(4,6)5、作距离矩阵D(1)1234523314474855262685913D(0)第103页/共163页104例：如下图所示 1、设全部样本分为6类，2、

34、作距离矩阵D(0)3、求最小元素：4、把1,3合并7=(1,3)4,6合并8=(4,6)5、作距离矩阵D(1)D(1)728238745522第104页/共163页1056 6、若合并的类数没有达到要求，转、若合并的类数没有达到要求，转3 3。否则停止。否则停止。3 3、求最小元素：、求最小元素：4 4、8,5,28,5,2合并合并,9=,9=（2,5,4,62,5,4,6）第105页/共163页106第106页/共163页10724 聚类的算法谱系聚类法程序 Hierarchical clustering第107页/共163页10824 聚类的算法最大距离和层次聚类算法的一个共同特点是某个模

35、式一旦划分到某一类之后，在后继的算法过程中就不改变了，而简单聚类算法中类心一旦选定后在后继算法过程中也不再改变了。因此，这些方法效果一般不会太理想。第108页/共163页1092.确定评估聚类质量的准则函数。1.确定模式和聚类的距离测度。当采用欧氏距离时，是计算此模式和该类中心的欧氏距离；为能反映出类的模式分布结构，应采用马氏距离，设该类的均矢为，协方差阵为，则模式和该类的与该类均矢的马氏距离：距离平方为3.确定模式分划及聚类合并或分裂的规则。24 聚类的算法动态聚类算法要点第109页/共163页11024 聚类的算法动态聚类的基本步骤1.建立初始聚类中心，进行初始聚类；2.计算模式和类的距离

36、，调整模式的类别；3.计算各聚类的参数，删除、合并或分裂一些聚类；4.从初始聚类开始，运用迭代算法动态地改变模式的类别和聚类的中心使准则函数取得极值或设定的参数达到设计要求时停止。第110页/共163页11124 聚类的算法动态聚类的框图产生初始聚类中心聚类检验聚类合理性待分类模式 分类结果合理再迭代/修改参数不合理第111页/共163页112 条件及约定 设待分类的模式特征矢量集为：类的数目C是事先取定的。24 聚类的算法 动态聚类法C-均值法 算法思想 该方法取定 C个类别和选取 C个初始聚类中心，按最小距离原则将各模式分配到 C类中的某一类，之后不断地计算类心和调整各模式的类别，最终使各

37、模式到其判属类别中心的距离平方之和最小。第112页/共163页11324 聚类的算法 动态聚类法C-均值法第113页/共163页11424 聚类的算法 动态聚类法C-均值法第114页/共163页115选代表点初始分类分类合理否4.动态聚类框图24 聚类的算法 动态聚类法C-均值法最终分类Y修改分类N第115页/共163页116例使用聚类算法实现图像分割在散射图上形成了两个聚类，利用模式识别的方法将其分开，就实现了图象的分割。第116页/共163页117 例：例：已知有已知有2020个样本，每个样本有个样本，每个样本有2 2个特征，数据分个特征，数据分布布如下图如下图,使用使用C C均值法实现样

38、本分类（均值法实现样本分类（C=2C=2）。）。第一步：令C=2，选初始聚类中心为样本序号样本序号x x1 1x x2 2x x3 3x x4 4x x5 5x x6 6x x7 7x x8 8x x9 9x x1010特征特征x x1 10 01 10 01 12 21 12 23 36 67 7特征特征x x2 20 00 01 11 11 12 22 22 26 66 6x11x12x13x14x15x16x17x18x19x2086789789896777788899第117页/共163页118第118页/共163页11900第二步：000）（-10100）（-10001）（-所以因为

39、-所以因为同理,12,21=-=-.20652065都属于、离计算出来，判断与第二个聚类中心的距、同样把所有因此分为两类：),.,()1(),()1(205422311=18,221=NNGG二、一、第120页/共163页121第121页/共163页122第122页/共163页123第三步：第三步：更新聚类中心更新聚类中心第123页/共163页124第124页/共163页125第四步：第四步：第二步：第二步：第三步第三步：更新聚类中心：更新聚类中心第125页/共163页126第126页/共163页127clustering24 聚类的算法 动态聚类法C-均值法程序第127页/共163页128作

40、业P45:2.7,2.8第128页/共163页12924 聚类的算法 动态聚类法C-均值法关于C-均值法收敛性的分析第129页/共163页13024 聚类的算法 动态聚类法C-均值法当模式分布呈现类内团聚状，C-均值算法是能达到很好的聚类结果，故应用较多。从算法的迭代过程看，C-均值算法是能使各模式到其所判属的类别中心距离(平方)之和为最小的最佳聚类。第130页/共163页13124 聚类的算法 动态聚类法C-均值法的改进 在类别数未知的情况下，可使类数C由较小值逐步增加，对于每个选定的C分别使用该算法。显然准则函数J是随C的增加而单调减少。C的调整 作一条C一J曲线，其曲率变化的最大点对应的

41、类数是比较接近最优的类数。在增加过程中，总会出现使本来较密集的类再拆开的情况，此时J虽减小，但减小速度将变缓。如果作一条C一J曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。然而在许多情况下，曲线并无明显的这样的点。第131页/共163页13224 聚类的算法 动态聚类法C-均值法的改进 初始聚类中心的选取 凭经验选择初始类心。将模式随机地分成C类，计算每类中心，以其作为初始类心。（最大密度），求以每个特征点为球心、某一正数d0为半径的球形域中特征点个数，这个数称为该点的密度。选取密度最大的特征点作为第一个初始类心Z1，然后在与Z1大于某个距离d的那些特征点中选取具有“最大”密度的特征

42、点作为第二个初始类心Z2，如此进行，选取C个初始聚类中心。第132页/共163页13324 聚类的算法 动态聚类法C-均值法的改进 初始聚类中心的选取 用相距最远的C个特征点作为初始类心。具体地讲，是按前述的最大最小距离算法求取C个初始聚类中心。当N较大时，先随机地从N个模式中取出一部分模式用谱系聚类法聚成C类，以每类的重心作为初始类心。设已标准化的待分类模式集为 希望将它们分为C类。第133页/共163页134 设已标准化的待分类模式集为 希望将它们分为C类。设:计算:显然0aiC，若ai最接近整数j，则把xi分划至中wj。对所有样本都实行上述处理，就可实现初始分类，从而产生初始聚类中心。第

43、134页/共163页13524 聚类的算法 动态聚类法C-均值法的改进 用类核代替类心 前面的算法存在一个不足，即只用一个聚类中心点作为一类的代表，但一个点往往不能充分地反映该类的模式分布结构，从而损失了很多有用的信息。当类的分布不是球状或近似球状时，这种算法很难有较好的效果。此时，可用类核代替类心，类核可以是一个函数、一个点集或其他适当的模型。比如前面我们讲过的马式距离。第135页/共163页136(3)动态聚类法ISODATA算法(Iterative Self-Organizing Data Analysis Techniques Algorithm 迭代自组织数据分析)特点：启发性推理、

44、分析监督、控制聚类结构及人机交互。算法思想：在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地“自组织”，以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。第136页/共163页137ISODATA算法原理步骤 预置 设定聚类分析控制参数：=预期的类数，=每一类中允许的最少模式数目，=初始聚类中心个数(可以不等于c)，=类内各分量分布的距离标准差上界，(分裂用)=两类中心间的最小距离下界，(合并用)=在每次迭代中可以合并的类的最多对数，=允许的最多迭代次数。第137页/共163页138ISODATA

45、算法原理步骤 第138页/共163页139ISODATA算法原理步骤 第139页/共163页140ISODATA算法原理步骤 计算各类的中心 计算分类后的参数:各类中心、类内平均距离及总体平均距离。计算各类中模式到类心的平均距离 计算各个模式到其类内中心的总体平均距离第140页/共163页141ISODATA算法原理步骤 第141页/共163页142ISODATA算法原理步骤 计算各类类内距离的标准差矢量式中，为分量编号，为类的编号，为矢量维数，是 的第 个分量，是 的第 个分量。第142页/共163页143ISODATA算法原理步骤 第143页/共163页144ISODATA算法原理步骤 第

46、144页/共163页145ISODATA算法原理步骤 第145页/共163页146ISODATA算法原理步骤 第146页/共163页147第147页/共163页148ISODATA算法举例(二维)(1)初始值设定:类间距离上限距离标准差上界最少模式数目合并的类的最多对数第148页/共163页149ISODATA算法举例(2)聚类(只有一个中心):第149页/共163页150ISODATA算法举例(3)因 ,无合并:(4)计算聚类中心、类内平均距离和总的平均距离。第150页/共163页151ISODATA算法举例(5)因不是最后一步迭代，且 ，转至(6)求 的标准差矢量 第151页/共163页1

47、52ISODATA算法举例(7)算得(6)因 且 将 分裂成两类，取 ，则 且 转(2)第152页/共163页153ISODATA算法举例(2)聚类(两个中心):(3)因 ,无合并:第153页/共163页154ISODATA算法举例(4)计算聚类中心、类内平均距离和总的平均距离。(5)因这是偶次迭代，满足算法原理步骤中 的条件，故转 第154页/共163页155ISODATA算法举例(9)计算类间距离 由 ，类不能合并。(11)因不是最后一次迭代(，题设 )，判断是否修改参数。由上面结果可知，已获得所要求类别数目，类间距离大于类内距离，每类样本数都有样本总数的足够大的百分比，因此不改变参数。第

48、155页/共163页156(2)(4)计算结果与前一次迭代结果相同。(7)(8),分裂条件不满足，转至。(11)，无新的变化，转至。(6)计算 和 的标准差矢量(5)没有任一种情况被满足，到。(9)与前一次迭代结果相同，(10)无合并发生。第156页/共163页157 与前一次迭代结果相同。因是最后一次迭代，令 ，转至。，同前。因 ，无合并发生。因是最后一次迭代,结束。第157页/共163页158Start输入样本数据，置c;Nc;选初始类心zj，j=1,2,.Nc(1)置控制参数：n,s,D,L,I(3)合并判决：nj s)(djd)(nj2(n+1)Ncc/2(6)计算各类类内距离的标准差

49、矢量(7)找出最大分量(10)合并处理(11)结束判决：Ip I(9)计算各类对类间距离NEndYNc=Nc+1Ip=Ip+1(8)分裂处理YNY转修改参数修改参数否转重新聚类N第160页/共163页161Start输入样本数据，置c;Nc;选初始类心zj，j=1,2,.Nc(1)置控制参数：n,s,D,L,I(2)聚类：if dil=minD(xi,z1),D(xi,z2),D(xi,zNc)then xil(3)合并判决：nj n NYNc=Nc-1(4)计算分类后的参数：类心 zj;类内平均距离dj;总类内平均距离d修改参数入口重新聚类入口第161页/共163页162作业P45:2.9,2.10第162页/共163页163感谢您的观看！第163页/共163页