模式识别课件：a02.ppt

1、1第二章第二章 聚类分析聚类分析 (Clustering Analysis) 2.1 2.1 聚类分析的概念聚类分析的概念2.2 2.2 模式相似性测度模式相似性测度2.3 2.3 类的定义与类间距离类的定义与类间距离2.4 2.4 聚类的算法聚类的算法22.1 2.1 聚类分析的概念聚类分析的概念一、聚类分析的基本思想一、聚类分析的基本思想 相似的归为一类。相似的归为一类。 模式相似性的度量和聚类算法。模式相似性的度量和聚类算法。 无监督分类无监督分类（Unsupervised） 。二、特征量的类型二、特征量的类型 物理量物理量-(-(重量、长度、速度重量、长度、速度) ) 次序量次序量-(

2、-(等级、技能、学识等级、技能、学识) ) 名义量名义量-(-(性别、状态、种类性别、状态、种类) )第二章第二章 聚类分析聚类分析3三、方法的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。2.1 聚类分析的概念2w2W1w1W2x1xb分类无效时的情况分类无效时的情况1.1.特征选取特征选取不当不当使分类无效。使分类无效。第二章第二章 聚类分析聚类分析4三、方法的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。2.1 聚类分析的概念分类无效时的情况分类无效时的情况2.2.特征选取特征选取

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

4、 聚类分析的概念分类无效时的情况分类无效时的情况4.4.量纲选取不当。量纲选取不当。第二章第二章 聚类分析聚类分析7三、方法的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。2.1 聚类分析的概念分类无效时的情况分类无效时的情况4.4.量纲选取不当。量纲选取不当。第二章第二章 聚类分析聚类分析8三、方法的有效性三、方法的有效性 取决于分类算法和特征取决于分类算法和特征点分布情况的匹配。点分布情况的匹配。2.1 聚类分析的概念分类无效时的情况分类无效时的情况4.4.量纲选取不当。量纲选取不当。第二章第二章 聚类分析聚类分析9下列是一些动物的名称

5、：下列是一些动物的名称：羊羊 （sheepsheep）狗狗 （dogdog）蓝鲨（蓝鲨（blue sharkblue shark） 蜥蜴蜥蜴 （lizardlizard）毒蛇（毒蛇（viperviper）猫猫 （catcat）麻雀（麻雀（sparrowsparrow）海鸥海鸥 （seagullseagull）金鱼（金鱼（gold fishgold fish）绯鲵鲣（绯鲵鲣（red-mulletred-mullet）蛙蛙 （frogfrog）要对这些动物进行分类，则不同的特征有不同的分法：要对这些动物进行分类，则不同的特征有不同的分法：特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响第二

6、章第二章 聚类分析聚类分析10特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响羊羊, , 狗狗, , 猫猫蓝鲨蓝鲨蜥蜴蜥蜴, ,毒蛇毒蛇, ,麻雀麻雀, ,海鸥海鸥, ,金鱼金鱼, ,绯鲵鲣绯鲵鲣, , 青蛙青蛙(a) 按繁衍后代的方式分按繁衍后代的方式分哺乳动物哺乳动物非哺乳动物非哺乳动物第二章第二章 聚类分析聚类分析11金鱼金鱼绯鲵鲣绯鲵鲣蓝鲨蓝鲨羊羊, ,狗狗, ,猫猫蜥蜴蜥蜴, ,毒蛇毒蛇麻雀麻雀, ,海鸥海鸥 青蛙青蛙(b) 按按肺是否存在肺是否存在分分无肺无肺有肺有肺特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响第二章第二章 聚类分析聚类分析12青蛙青蛙羊羊, ,

7、狗狗, ,猫猫 蜥蜴蜥蜴, ,毒蛇毒蛇麻雀麻雀, ,海鸥海鸥 金鱼金鱼绯鲵鲣绯鲵鲣 蓝鲨蓝鲨(c) 按按生活环境生活环境分分陆地陆地水里水里两栖两栖特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响第二章第二章 聚类分析聚类分析13蓝鲨蓝鲨金鱼金鱼绯鲵鲣绯鲵鲣蜥蜴蜥蜴, ,毒蛇毒蛇麻雀麻雀, ,海鸥海鸥 青蛙青蛙羊羊, ,狗狗, ,猫猫(d) 按按繁衍后代方式和肺是否存在繁衍后代方式和肺是否存在分分非哺乳且有肺非哺乳且有肺哺乳且无肺哺乳且无肺哺乳且有肺哺乳且有肺非哺乳且无肺非哺乳且无肺特征选取不同对聚类结果的影响特征选取不同对聚类结果的影响第二章第二章 聚类分析聚类分析14距离测度不同距

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

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

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

11、分析。从而来支持这个假说。假说。第二章第二章 聚类分析聚类分析20四、基于分组的预测 对现有数据进行聚类分析，形成模式的特征，并用特征表示聚类，接下来，对于一个未知模式，就可以用前面的聚类来确定是哪一类？聚类应用的四个基本方向例如：考虑被同种疾病感染的病人数据集。例如：考虑被同种疾病感染的病人数据集。先按聚类分析进行分类，然后对新的病人确定他先按聚类分析进行分类，然后对新的病人确定他适合的聚类，从而判断他病情。适合的聚类，从而判断他病情。第二章第二章 聚类分析聚类分析212.2 2.2 模式相似性测度模式相似性测度 用于描述各模式之间特征的相似程度用于描述各模式之间特征的相似程度 距距 离离

12、测测 度度 相相 似似 测测 度度 匹匹 配配 测测 度度第二章第二章 聚类分析聚类分析222.2 2.2 模式相似性测度模式相似性测度一、距离测度一、距离测度( (差值测度差值测度) )测度基础：测度基础：两个矢量矢端的距离两个矢量矢端的距离测度数值：测度数值：两矢量各相应分量之差的函数两矢量各相应分量之差的函数。时，等号成立；时，等号成立；0),(yxd，当且仅当，当且仅当xy),(),(xydyxd),(),(),(yzdzxdyxd第二章第二章 聚类分析聚类分析232.2 2.2 模式相似性测度模式相似性测度常用的距离测度有：常用的距离测度有：1.1.欧氏欧氏(Euclidean)(E

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

14、章 聚类分析聚类分析272.2 模式相似性测度第二章第二章 聚类分析聚类分析现金识别例子现金识别例子( (欧氏平均距离欧氏平均距离) )数据样本介绍：数据样本介绍：10个文本文件个文本文件文件名：文件名：rmb00.txt rmb09.txt每个文件有每个文件有4个币种的数据，分别是：个币种的数据，分别是： 100圆、圆、50圆、圆、20圆、圆、10圆圆每个币种有新旧两种版本，每个币种有新旧两种版本，4个方向，故有个方向，故有8个数据块：个数据块：如如100圆的圆的8个数据块：个数据块： data100a,data100b,data100c,data100ddata100a,data100b,

15、data100c,data100d老版老版 data100e,data100f,data100g,data100hdata100e,data100f,data100g,data100h新版新版每个数据块有每个数据块有8个传感器数据：个传感器数据： 传感器传感器1，传感器，传感器2，传感器传感器8每个传感器有每个传感器有60个采样数据：个采样数据： 数据数据1，数据，数据2，数据，数据60现金识别例子现金识别例子Eucliden=15.000000Eucliden=15.000000Manhattan=33.000000Manhattan=33.000000Chebyshev=11.000000

16、Chebyshev=11.000000Minkowski=11.039449m=8Minkowski=11.039449m=8100100元元A A面第面第1 1个样本第个样本第1010点和点和2020点的距离点的距离X:X: (75, 76,101, 83,102, 96, 91, 82) (75, 76,101, 83,102, 96, 91, 82)Y:Y: (70, 74, 90, 76, 99, 96, 90, 86) (70, 74, 90, 76, 99, 96, 90, 86)X-Y: X-Y: 5, 2, 11, 7, 3, 0, 1, -45, 2, 11, 7, 3, 0

17、, 1, -4距离测度距离测度rmbdis现金识别例子现金识别例子欧式平均距离欧式平均距离100a-100a:( 2.65,49.66) 24.41100a-100a:( 2.65,49.66) 24.41100a-100b:(16.37,55.87) 33.97100a-100b:(16.37,55.87) 33.97100a-100c:( 3.87,58.34) 29.41100a-100c:( 3.87,58.34) 29.41100a-100d:( 6.86,53.74) 33.04100a-100d:( 6.86,53.74) 33.04100a-100e:( 3.87,62.12)

18、 27.51100a-100e:( 3.87,62.12) 27.51100a-100f:(13.60,67.61) 34.67100a-100f:(13.60,67.61) 34.67100a-100g:(11.40,68.56) 32.27100a-100g:(11.40,68.56) 32.27100a-100h:(11.27,68.61) 34.43100a-100h:(11.27,68.61) 34.43100a- 50a:(18.76,76.20) 40.72100a- 50a:(18.76,76.20) 40.72100a- 20a:(13.23,81.28) 42.87100a

19、- 20a:(13.23,81.28) 42.87100a- 10a:(12.45,90.91) 54.99100a- 10a:(12.45,90.91) 54.99现金识别例子现金识别例子100100圆圆A A面的马式矩阵面的马式矩阵SWSW为为: : 43.5 53.9 64.8 52.7 52.7 52.3 46.8 37.943.5 53.9 64.8 52.7 52.7 52.3 46.8 37.9 53.9 132.0 137.5 107.8 59.6 74.0 52.1 31.5 53.9 132.0 137.5 107.8 59.6 74.0 52.1 31.5 64.8 13

20、7.5 165.9 124.1 74.6 84.1 67.6 37.1 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 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.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 52.3 74.0 84.1

21、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 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 37.9 31.5 37.1 35.2 57.9 55.0 51.9 54.7现金识别例子现金识别例子SWSW的逆矩阵为的逆矩阵为: : 0.3 -0.0 0.1 -0.1 -0.1 -0.1 -0.2 0.20.3 -0.0 0.1 -0.1 -0.1 -0.1 -0.2 0.2 -0.0 0.3 -0.1

22、 -0.1 0.1 -0.6 0.3 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.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.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.1 -0.0 0.1 0.7 -0.7 -0.4 0.2 -0.1 -0.6 -0.2 0.3 -0

23、.7 2.2 -0.0 -1.0 -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.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 0.2 0.2 0.4 -0.2 0.2 -1.0 -0.5 1.0现金识别例子现金识别例子马式平均距离马式平均距离100a: ( 7.46, 80.05) 39.73100a: ( 7.46, 80.05) 39.73100b: (26.75, 179.86) 91

24、.89100b: (26.75, 179.86) 91.89100c: (14.50, 231.44) 103.76100c: (14.50, 231.44) 103.76100d: (11.69, 155.28) 78.58100d: (11.69, 155.28) 78.58100e: ( 5.65,2968.84) 247.42100e: ( 5.65,2968.84) 247.42100f: (39.19,2191.91) 108.10100f: (39.19,2191.91) 108.10100g: (10.68,2875.99) 265.16100g: (10.68,2875.99

25、) 265.16100h: ( 9.41,2673.54) 107.56100h: ( 9.41,2673.54) 107.56 50a: (22.78, 221.07) 101.41 50a: (22.78, 221.07) 101.41 20a: (22.51, 343.26) 162.90 20a: (22.51, 343.26) 162.90 10a: (20.93, 975.67) 256.38 10a: (20.93, 975.67) 256.38现金识别例子现金识别例子马式平均距离马式平均距离a: 39.73 101.41 162.90 256.38a: 39.73 101.41

26、 162.90 256.38b: 91.89 230.25 288.69 659.47b: 91.89 230.25 288.69 659.47c: 103.76 135.94 257.57 724.96c: 103.76 135.94 257.57 724.96d: 78.58 171.10 330.97 675.90d: 78.58 171.10 330.97 675.90e: 247.42 443.46 333.93 218.71e: 247.42 443.46 333.93 218.71f: 108.10 328.11 305.19 607.51f: 108.10 328.11 305

27、.19 607.51g: 265.16 956.58 818.83 348.42g: 265.16 956.58 818.83 348.42h: 107.56 339.64 387.10 628.88h: 107.56 339.64 387.10 628.88100圆圆 50圆圆 20圆圆 10圆圆其中马式矩阵为其中马式矩阵为100100圆圆A A面的，上面是各面到面的，上面是各面到100100圆圆A A面的均值点的平均马式距离。面的均值点的平均马式距离。现金识别例子现金识别例子100100圆圆A A面的传感器面的传感器1 1到其它各面传感器到其它各面传感器1 1的街坊距离的街坊距离372.2

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

29、相关系数与其它各面的相关系数412.2 模式相似性测度二、相似测度3.指数相似系数 (2-2-13)niiiiyxnyxe122)(43exp1),(式中式中 为相应分量的协方差，为相应分量的协方差， 为矢量维数。为矢量维数。它不受量纲变化的影响。它不受量纲变化的影响。 2in42现金识别例子现金识别例子100100圆圆A A面传感器面传感器1 1与其它各面的相关系数与其它各面的相关系数432.2 模式相似性测度当特征只有两个状态（当特征只有两个状态（0 0，1 1）时，常用匹配测度。）时，常用匹配测度。0 0表示无此特征表示无此特征 1 1表示有此特征。故称之为表示有此特征。故称之为二值特征

30、二值特征。 对于给定的对于给定的x x和和y y中的某两个相应分量中的某两个相应分量x xi i与与y yj j若若x xi i=1,y=1,yj j=1 =1 ，则称，则称 x xi i与与y yj j是是 (1-1)(1-1)匹配匹配；若若x xi i=1,y=1,yj j=0 =0 ，则称，则称 x xi i与与y yj j是是 (1-0)(1-0)匹配；匹配；若若x xi i=0,y=0,yj j=1 =1 ，则称，则称 x xi i与与y yj j是是 (0-1)(0-1)匹配；匹配；若若x xi i=0,y=0,yj j=0 =0 ，则称，则称 x xi i与与y yj j是是 (

31、0-0)(0-0)匹配。匹配。二、匹配测度二、匹配测度442.2 模式相似性测度452.2 模式相似性测度 三、匹配测度(1)Tanimoto测度测度yxyyxxyxcbaayxs),(46例例2.2.22.2.2 可以看出，它等于可以看出，它等于共同具有的特征数目共同具有的特征数目与分别与分别具有的特征种类总数之比。这里只考虑具有的特征种类总数之比。这里只考虑(1-1)(1-1)匹配而匹配而不考虑不考虑(0-0)(0-0)匹配。匹配。)0, 1, 1, 0, 1, 0(x) 1, 0, 1, 1, 0, 0(y 1 , 3 , 3yxyyxx511331),(yxs设设则则2.2 模式相似性

32、测度47现金识别例子现金识别例子100100圆圆A A面面与其它各面的匹配系数与其它各面的匹配系数TanimotoTanimoto482.2 模式相似性测度 三、匹配测度(2) RaoRao测度测度注：注：(1-1)匹配特征数目和所选用的特征数目之比。匹配特征数目和所选用的特征数目之比。nyxecbaayxs),(49现金识别例子现金识别例子100100圆圆A A面面与其它各面的匹配系数与其它各面的匹配系数RaoRao502.2 模式相似性测度 三、匹配测度(3) (3) 简单匹配系数简单匹配系数注：上式分子为注：上式分子为(1-1)匹配特征数目与匹配特征数目与(0-0)匹配特征匹配特征数目之

33、和，分母为所考虑的特征数目。数目之和，分母为所考虑的特征数目。neayxm),(51现金识别例子现金识别例子100100圆圆A A面面与其它各面的匹配系数与其它各面的匹配系数SimpleSimple522.2 模式相似性测度 三、匹配测度(4) Dice系数系数(5) Kulzinsky系数系数的总数俩矢量中匹配个数11)-(12),(yyxxyxcbaayxm匹配个数匹配个数0)-(11)-(01)-(12),(yxyyxxyxcbayxm53现金识别例子现金识别例子100100圆圆A A面面与其它各面的匹配系数与其它各面的匹配系数dicedice54现金识别例子现金识别例子100100圆圆

34、A A面面与其它各面的匹配系数与其它各面的匹配系数KulzinskyKulzinsky55作业作业P44: 2.1, 2.35623 类的定义与类间距离2.3.1 2.3.1 类的定义类的定义定义之定义之1 1 设集合设集合S S中任意元素中任意元素x xi i与与y yj j间的距离间的距离d dijij有有 d dijij h h其中其中h h为给定的阀值，称为给定的阀值，称S S对于阀值对于阀值h h组成一类。组成一类。 类的定义有很多种，类的划分具有人为规定性，这反类的定义有很多种，类的划分具有人为规定性，这反映在定义的选取及参数的选择上。一个分类结果的优劣最映在定义的选取及参数的选择

35、上。一个分类结果的优劣最后只能根据实际来评价。后只能根据实际来评价。书中的其它定义方法请大家自行参考学习书中的其它定义方法请大家自行参考学习5723 类的定义与类间距离2.3.2 2.3.2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法5823 类的定义与类间距离2.3.2 2.3.2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法式中式中 表示表示

36、和和 之间的距离。之间的距离。 ijjikldD,minijdkixwljxw59现金识别例子现金识别例子100100圆圆A A面面与其它各面的最小距离与其它各面的最小距离6023 类的定义与类间距离2.3.2 2.3.2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法式中式中 表示表示 和和 之间的距离。之间的距离。ijdkixwljxw ijjikldD,max61现金识别例子现金识别例子100100圆圆A A面面与其它各面的最大距离与其它各面的最大距离6223 类的定

37、义与类间距离2.3.2 2.3.2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法pw wqw wkw wpqkpqDkqDklDkpDlw wpqkqkpklDDDD2222412121qplwww6323 类的定义与类间距离2.3.2 2.3.2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法22222)(pqqpqpkqqpqkpqppklDnnn

38、nDnnnDnnnDnp,nq分别为类分别为类w wp和和w wq的的样本个数样本个数6423 类的定义与类间距离2.3.2 2.3.2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法wwqjpixxijqppqdnnD22165现金识别例子现金识别例子100100圆圆A A面面与其它各面的平均距离与其它各面的平均距离6623 类的定义与类间距离2.3.2 2.3.2 类间距离测度方法类间距离测度方法 最近距离法最近距离法 最远距离法最远距离法 中间距离法中间距离法 重心距

39、离法重心距离法 平均距离法平均距离法 离差平方和法离差平方和法wtixtititxxxxs)()(qplwwwqplpqsssD2)()(2qpqpqpqppqxxxxnnnnDtxpxqx分别为对应类的重心分别为对应类的重心类内离差平方和类内离差平方和 2222pqlkkkqlkqkkplkpkklDnnnDnnnnDnnnnD递推公式为递推公式为:67222222kqkppqkqqkppklDDDDDD 最近距离法最近距离法 1/2 1/2 0 -1/2 最远距离法最远距离法 1/2 1/2 0 1/2 中间距离法中间距离法 1/2 1/2 -1/4 0 重心距离法重心距离法 0 平均距离

40、法平均距离法 0 0 可变平均法可变平均法 0 可变法可变法 0 离差平方和法离差平方和法 0pqqppnnnqpqnnnqpqppnnnqpqnnnqppnnn )1 (qpqnnn )1 (112121lkpknnnnlkqknnnnlkknnn6823 类的定义与类间距离2.3.3 2.3.3 聚类的准则函数聚类的准则函数判别分类结果好坏的一般标准：判别分类结果好坏的一般标准：类内距离小，类间距离大。类内距离小，类间距离大。 某些算法需要一个能对分类过程或分类结果某些算法需要一个能对分类过程或分类结果的优劣进行评估的准则函数。如果聚类准则函数的优劣进行评估的准则函数。如果聚类准则函数选择

41、得好，聚类质量就会高。聚类准则往往是和选择得好，聚类质量就会高。聚类准则往往是和类的定义有关的，是类的定义的某种体现。类的定义有关的，是类的定义的某种体现。692.3.3 2.3.3 聚类的准则函数聚类的准则函数一、类内距离准则一、类内距离准则 设有待分类的模式集设有待分类的模式集 在某种相似性测在某种相似性测度基础上被划分为度基础上被划分为 类，类，类内距离准则函数类内距离准则函数 定义为定义为:( 表示表示 类的模式均类的模式均值矢量。值矢量。)Nxxx,21cjjinicjx, 2 , 1;, 2 , 1)(；WJcjnijjiWjmxJ112)(2-3-20)23 类的定义与类间距离j

42、mjw7023 类的定义与类间距离71加权类内距离准则加权类内距离准则 : :WWJ21jcjjWWdNnJ(2-3-22)2)()(2)()() 1(2jjijjkxxjkjijjjxxnndww(2-3-23)式中，2)()(jkjixx表示jw类内任两个模式距离2) 1(jjnn 个组合数，所以2jd表示类内Nnj表示jw类先验概率的估计频率。平方和，共有两模式间的均方距离。N为待分类模式总数，7223 类的定义与类间距离73加权类间距离准则加权类间距离准则: :对于两类问题，类间距离有时取)()(21212mmmmJB(2-3-26)2BJ和WBJ的关系是221BWBJNnNnJ(2-

43、3-27)max)()(1cjjjjWBmmmmNnJ(2-3-25)7423 类的定义与类间距离75 的类内离差阵定义为的类内离差阵定义为 (2-3-28)(2-3-28)jw), 2 , 1()(1)(1)()(cjmxmxnSjjijnijijjWj23 类的定义与类间距离mjjwjnijijjxnm1)(1), 2 , 1(cj式中式中 为类为类 的模式均值矢量的模式均值矢量 (2-3-29)(2-3-29)7677例例2.3 .1 证明：证明：jnijijicjjjTmxmxnNnS1)()(1)(1jnijjjjijjijcjjmmmmmxmxnNn1)()(1)()(1BWSSB

44、WTSSS23 类的定义与类间距离NiiiTmxmxNS1)(1jnijijicjmxmxN1)()(1)(178 聚类的基本目的是使聚类的基本目的是使 或或 。利用线形代数有关矩阵。利用线形代数有关矩阵的迹和行列式的性质的迹和行列式的性质, ,可以定义如下可以定义如下4 4个聚类的准则个聚类的准则函数函数: : TrmaxBS11TrWBJS SBWSSJ1213TrWTJS STWSSJ14TrminWS23 类的定义与类间距离7911TrWBJS SBWSSJ1213TrWTJS STWSSJ1423 类的定义与类间距离 由它们的构造可以看出，为得到好的聚类由它们的构造可以看出，为得到好

45、的聚类结果，应该使它们尽量的大。这类准则也大量结果，应该使它们尽量的大。这类准则也大量用在特征提取和选择中。用在特征提取和选择中。 8011TrWBJS SBWSSJ1213TrWTJS STWSSJ1423 类的定义与类间距离J1= 7.60886 J2= 0.0010397J1= 7.60886 J2= 0.0010397J3= 15.6089 J4= 62.9116J3= 15.6089 J4= 62.9116用纸币数据计算获得的结果：用纸币数据计算获得的结果：81作业作业P44: 2.4, 2.5, 2.68224 聚类的算法 2.4.1 聚类的技术方案聚类的技术方案聚类分析有很多具体

46、的算法聚类分析有很多具体的算法,有的比较简单有的比较简单,有的相对复杂和完善有的相对复杂和完善,但归纳起来就是三大类但归纳起来就是三大类:1、按最小距离原则简单聚类方法、按最小距离原则简单聚类方法2、按最小距离原则进行两类合并的方法、按最小距离原则进行两类合并的方法3、依据准则函数动态聚类方法、依据准则函数动态聚类方法8324 聚类的算法 (1) 简单聚类方法简单聚类方法 针对具体问题确定相似性阈值，将模式到各聚针对具体问题确定相似性阈值，将模式到各聚类中心间的距离与阈值比较，当大于阈值时该模类中心间的距离与阈值比较，当大于阈值时该模式就作为另一类的类心，小于阈值时按最小距离式就作为另一类的类

47、心，小于阈值时按最小距离原则将其分划到某一类中。原则将其分划到某一类中。这类算法运行中模式的类别及类的中心一旦确这类算法运行中模式的类别及类的中心一旦确定将不会改变。定将不会改变。8424 聚类的算法 首先视各模式自成一类首先视各模式自成一类, ,然后将距离最小的两然后将距离最小的两类合并成一类类合并成一类, ,不断地重复这个过程，直到成为不断地重复这个过程，直到成为两类为止。两类为止。(2) 按最小距离原则进行两类合并的方法按最小距离原则进行两类合并的方法这类算法运行中，类心不断地修正，但模式这类算法运行中，类心不断地修正，但模式类别一旦指定后就不再改变，就是模式一旦划为类别一旦指定后就不再

48、改变，就是模式一旦划为一类后就不再被分划开，这类算法也称为谱系聚一类后就不再被分划开，这类算法也称为谱系聚类法。类法。8524 聚类的算法 (3) 依据准则函数动态聚类法依据准则函数动态聚类法设定一些分类的控制参数，定义一个能表征聚设定一些分类的控制参数，定义一个能表征聚类结果优劣的准则函数，聚类过程就是使准则函类结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。数取极值的优化过程。算法运行中，类心不断地修正，各模式的类别算法运行中，类心不断地修正，各模式的类别的指定也不断地更改。这类方法有的指定也不断地更改。这类方法有C C均值法、均值法、ISODATAISODATA法等。法等。8

49、624 聚类的算法-简单聚类方法简单聚类方法 8724 聚类的算法-简单聚类方法简单聚类方法 8824 聚类的算法-简单聚类方法简单聚类方法 8924 聚类的算法-简单聚类方法简单聚类方法 这类算法的突出优点是算法简单。但聚类过程这类算法的突出优点是算法简单。但聚类过程中，类的中心一旦确定将不会改变，模式一旦指定中，类的中心一旦确定将不会改变，模式一旦指定类后也不再改变。类后也不再改变。算法特点算法特点:从算法的过程可以看出，该算法结果很大程度从算法的过程可以看出，该算法结果很大程度上依赖于距离门限上依赖于距离门限T的选取及模式参与分类的次序。的选取及模式参与分类的次序。如果能有先验知识指导门

50、限如果能有先验知识指导门限T的选取，通常可获得的选取，通常可获得较合理的效果。也可考虑设置不同的较合理的效果。也可考虑设置不同的T和选择不同和选择不同的次序，最后选择较好的结果进行比较。的次序，最后选择较好的结果进行比较。9024 聚类的算法-简单聚类方法简单聚类方法 简单聚类图简单聚类图例例91例例2.4.12.4.1：初始条件不同的简单聚类结果：初始条件不同的简单聚类结果初始中心不同门限不同样本顺序不同 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 1