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

第6章聚类分析

第6章聚类分析

6.1聚类分析的基本概念

6.2模式相似性测度和聚类准则

6.3基于距离阈值的聚类法

6.4层次聚类法

6.5动态聚类算法

第6章聚类分析

聚类是按照一定的要求和规律对事物进行区分和分类的

过程。在这一过程中没有任何关于类别的先验知识，也没有

教师的指导，仅靠事物间的相似性作为类属划分的准则，使

其得到的每个类中的模式(样本)是相似的，而不同类之间的

模式(样本)差别较大。聚类源于很多领域，包括数学、计算

机科学、统计学、生物学和经济学。

本章讨论聚类分析的基本概念、模式相似性测度和聚类

准则，重点介绍基于距离阈值的聚类法、层次聚类法和动态

聚类法。

第6章聚类分析

6.1聚类分析的基本概念

聚类体现了“人以群分，物以类聚”的思想，是一种重

要的人类行为。早在孩提时代，一个人就能通过不断地改进

下意识中的聚类模式来学会如何区分诸如猫和狗，桌子和椅

子等对象。聚类也是一个古老的问题，它伴随着人类社会的

产生和发展而不断深化，人类要认识世界就必须区别不同的

事物并且认识事物间的相似性。

第6章聚类分析

下面我们以动物为例进行说明：羊、狗、猫(哺乳动物)、

麻雀、海鸥(鸟类)、蛇、蜥蜴(爬虫类)、金鱼、蓝鲨(鱼)、青

蛙(两栖)。如果我们按照肺是否存在来对它们进行分类，则

金鱼和蓝鲨是一类，其他的动物为第二类(见图6.1(a))。如

果我们以它们生活的环境进行分类，则羊、狗、猫、麻雀、

海鸥、蛇和蜥蜴都是陆生动物，金鱼和蓝鲨是水生动物，青

蛙由于是两栖动物将独自成为第三类(见图6.1(b))。当然我

们还可以以它们繁衍后代的方式等其他的聚类准则来对这些

动物进行分类，这里就不再一一列举了。

第6章聚类分析

图6.1不同聚类准则下的聚类分析

第6章聚类分析

聚类分析是指用数学的方法研究和处理给定对象的分类

过程。下面给出聚类分析的数学描述。

设X={x1，x2，…，xn}是待聚类的样本集，聚类分析就

是将样本集X聚集成c个子类ω1，ω2，…，ωc，并使得ω1，

ω2，…，ωc满足下列条件：

i,1ic

12cX(6-1)

ij,1ijc

从上述条件可以看出，样本集中的每个样本一定只属于

某一类，并且最多只属于这一类。

第6章聚类分析

由于在分类中不需要用训练样本进行学习和训练，因此

聚类分析属于无监督分类的范畴。需要指出的是，当人为选

定某些特征，采用某种模式相似性度量，运用某种聚类算法

时，实际上已引入了某些知识和信息，从而隐含地对模式集

的分类结构做了大致的估计。使用不同的特征，或采用不同

的模式相似性度量，或运用不同的聚类算法等都将产生不同

的聚类结果。所以在处理实际问题时，必须要深入了解问题，

使选用的特征和相似性度量、运行的聚类算法等能与问题很

好的匹配。

第6章聚类分析

6.2模式相似性测度和聚类准则

6.2.1模式相似性测度

模式之间具有一定的相似性，利用相似性度量可以定量

地衡量模式间的相似程度，并对相似的模式进行归类。这里

我们以量之间的测度为例进行介绍。

1.距离测度

设向量x和y之间的距离记为

ρ(x，y)，ρ(x，y)应满足如下的公理：

(1)ρ(x，y)≥0,当且仅当x=y时等号成立，即

(x,y)0xy；

第6章聚类分析

(2)ρ(x，y)=ρ(y，x)；

(3)ρ(x，y)≤ρ(x，z)+ρ(z，y)。

TT

设x=(x1，x2，…，xd)，y=(y1，y2，…，yd)，下面给出

几种常用的距离测度。

欧氏(Euclidean)距离：

d

21/2

(x,y)[(xiyi)](6-2)

i