模式识别导论第6章聚类分析

《模式识别导论第6章聚类分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章聚类分析6.1聚类分析的基本概念6.2模式相似性测度和聚类准则6.3基于距离阈值的聚类法6.4层次聚类法6.5动态聚类算法聚类是按照一定的要求和规律对事物进行区分和分类的过程。在这一过程中没有任何关于类别的先验知识，也没有教师的指导，仅靠事物间的相似性作为类属划分的准则，使其得到的每个类中的模式(样本)是相似的，而不同类之间的模式(样本)差别较大。聚类源于很多领域，包括数学、计算机科学、统计学、生物学和经济学。　　本章讨论聚类分析的基本概念、模式相似性测度和聚类准则，重点介绍基于距离阈值的

2、聚类法、层次聚类法和动态聚类法。6.1聚类分析的基本概念　　聚类体现了“人以群分，物以类聚”的思想，是一种重要的人类行为。早在孩提时代，一个人就能通过不断地改进下意识中的聚类模式来学会如何区分诸如猫和狗，桌子和椅子等对象。聚类也是一个古老的问题，它伴随着人类社会的产生和发展而不断深化，人类要认识世界就必须区别不同的事物并且认识事物间的相似性。下面我们以动物为例进行说明：羊、狗、猫(哺乳动物)、麻雀、海鸥(鸟类)、蛇、蜥蜴(爬虫类)、金鱼、蓝鲨(鱼)、青蛙(两栖)。如果我们按照肺是否存在来对它

3、们进行分类，则金鱼和蓝鲨是一类，其他的动物为第二类(见图6.1(a))。如果我们以它们生活的环境进行分类，则羊、狗、猫、麻雀、海鸥、蛇和蜥蜴都是陆生动物，金鱼和蓝鲨是水生动物，青蛙由于是两栖动物将独自成为第三类(见图6.1(b))。当然我们还可以以它们繁衍后代的方式等其他的聚类准则来对这些动物进行分类，这里就不再一一列举了。图6.1不同聚类准则下的聚类分析聚类分析是指用数学的方法研究和处理给定对象的分类过程。下面给出聚类分析的数学描述。　　设X={x1，x2，…，xn}是待聚类的样本集，聚类分

4、析就是将样本集X聚集成c个子类ω1，ω2，…，ωc，并使得ω1，ω2，…，ωc满足下列条件：(6-1)从上述条件可以看出，样本集中的每个样本一定只属于某一类，并且最多只属于这一类。由于在分类中不需要用训练样本进行学习和训练，因此聚类分析属于无监督分类的范畴。需要指出的是，当人为选定某些特征，采用某种模式相似性度量，运用某种聚类算法时，实际上已引入了某些知识和信息，从而隐含地对模式集的分类结构做了大致的估计。使用不同的特征，或采用不同的模式相似性度量，或运用不同的聚类算法等都将产生不同的聚

5、类结果。所以在处理实际问题时，必须要深入了解问题，使选用的特征和相似性度量、运行的聚类算法等能与问题很好的匹配。6.2模式相似性测度和聚类准则6.2.1模式相似性测度　　模式之间具有一定的相似性，利用相似性度量可以定量地衡量模式间的相似程度，并对相似的模式进行归类。这里我们以量之间的测度为例进行介绍。1.距离测度　　设向量x和y之间的距离记为ρ(x，y)，ρ(x，y)应满足如下的公理：(1)ρ(x，y)≥0,当且仅当x=y时等号成立，即；(2)ρ(x，y)=ρ(y，x)；(3)

6、ρ(x，y)≤ρ(x，z)+ρ(z，y)。　　设x=(x1，x2，…，xd)T，y=(y1，y2，…，yd)T，下面给出几种常用的距离测度。　　欧氏(Euclidean)距离：　　绝对值距离(市区距离或Manhattan距离)：(6-2)(6-3)切氏(Chebyshev)距离：　　明氏(Minkowski)距离：　　可以看出，式(6-2)、式(6-3)和式(6-4)实际上分别是式(6-5)在p=2、1和∞时的特殊情况。在实际中应用较多的是欧氏距离，该距离测度具有平移性和旋转

7、不变性。　　马氏(Mahalanobis)距离：设向量xi和xj是向量集{x1，x2，…，xn}中的两个向量，它们之间的马氏距离定义为(6-4)(6-5)(6-6)其中(6-7)(6-8)由于V是这个向量集的样本协方差矩阵，因此马氏距离对特征的相关性做了处理。此外，马氏距离对一切非奇异线性变换都是不变的，它还是平移不变的。需要指出，当向量x和y分别是两个数据集中的样本时，设C是它们的互协方差矩阵，则x和y之间的马氏距离定义为ρ2(x，y)=(x－y)TC－1(x－y)(6-9)以上定义的模式

8、相似性度量都是距离测度，两个模式越相似，其测度值越小。2.相似测度　　角度相似系数(夹角余弦)：采用两个向量的夹角余弦来度量它们之间的相似性，定义为相关系数：数据中心化后的向量夹角余弦，定义为　　此处将向量x和y分别看为两个数据集中的样本，　　和　　分别是这两个数据集的平均向量。(6-10)(6-11)指数型相似系数：式中，σ2i为相应分量的方差，d为向量维数。　　以上都是相似测度，最大值为1。两个模式越相似，其测度值越大。(6-12