2.1.3 模式聚类

2.1.2节介绍的模式分类器在学习状态时所利用的样本必须是已知类别的，因此这种学习称为有监督学习。在一些实际的应用中，往往没有已知类别的样本可供利用，甚至将提供的样本应分成几类都不知道。例如，卫星遥感照片上各像素点的分类问题，我们不知道各像素点属于哪一类，甚至不知道应将照片上的像素点分成几类。

本节要讨论的内容就是将未知类别的样本集划分成若干子集（类），划分的直接成果是完成了样本的分类，可能的间接成果是确定了分类器的参数。由于所用样本是没有类别标志的，因此通常称为无监督学习。

无监督学习以“物以类聚”为指导思想，对未知类别的样本集根据样本之间的相似程度分类，相似的归为一类，不相似的归为另一类，故这种模式聚类称为聚类分析。

采用模式聚类，首先要解决两个问题：一是如何衡量两个样本的相似程度；二是相似到什么程度归为一类。这就涉及模式相似性的测度和聚类准则。

模式聚类是统计模式识别的另一重要工具，它把模式归入到同样的类或聚合类；同一个聚合类比不同聚合类中的模式更相近。已知若干模式和它们的特征，但不知道每个模式的类别，且事先也不知道究竟分成多少类，在此基础上使用某种相似性度量的方法，即基于“物以类聚”的观点，把特征相似的模式归为一类的方法称为模式聚类法。这种方法是一种非监督学习的方法。

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

（1）相似性测度

相似性测度用于衡量同类样本的类似性和不同类样本的差异性。常用的测度有：

1）欧氏距离（即欧几里得距离，简称距离）

设Xi和X j为两个样本，其欧氏距离定义为

显然，样本Xi和X j间的距离越小，越相似。

2）街坊距离

街坊距离的表达式为

与欧氏距离相比，街坊距离减小了计算量。

3）角度相似性函数

角度相似性利用样本Xi和X j间夹角的余弦来定义，即

距离和角度相似性函数作为相似性的测度各有其局限性。距离对于坐标系的旋转和位移是不变的，而对于放大和缩小并不具有不变性的性质。角度相似性函数对于坐标系的旋转、放大和缩小均具有不变性，但对于位移不具有不变性的性质。用角度相似性函数作为相似性的测度还有一个缺点，当本属不同类的样本分布在从模式空间原点出发的一条直线上时，所有样本之间的角度相似性函数几乎都等于1，这会造成将这些样本全归为一类的错误。

（2）聚类准则

为了评价聚类结果的好坏，必须定义准则函数。有了模式相似性测度和准则函数后，聚类就变成了使准则函数取极值的优化问题了。

常用的准则函数是误差平方和准则。

若Ni是第i类ωi中的样本数目，mi是这些样本的均值，即

把ωi中的各样本X与均值mi间的误差平方和对所有类相加后为

式中，J 是误差平方和聚类准则，它度量了用 c 个聚类中心m1,m2,…,mc代表 c 个样本子集m1,m2,…,mc时所产生的总的误差平方和。对于不同的聚类，J值当然是不同的，使J值极小的聚类是误差平方和准则下的最优结果。这种类型的聚类通常称为最小方差划分。

2.层次聚类法

模式聚类的三要素为相似性测度、聚类准则和聚类算法。选定相似性测度和聚类准则后，下面的问题是用什么算法找出使准则函数取极值的最好聚类结果。现有的两种聚类算法是非迭代的层次聚类算法和迭代的动态聚类算法。本节将讨论层次聚类算法。

层次聚类算法又称系统聚类法、分级聚类法，该方法先把所有样本各自视为一类，然后计算类与类之间的相似性，选择相似性最大的一对类别合并成一个新类，进而在新的类别划分下重复合并操作，直到满足停止条件。由此可见，层次聚类法具有如下性质：在某一级划分时归入同一类样本，在此后的划分中，它们永远属于同一类。

从上面的讨论也可发现，层次聚类法需要解决两方面的问题：一是如何衡量类别的相似性；二是聚类操作应停止在哪一级上。

通常不同类别的相似性通过类间距离来度量，设类ωi和类ωj之间的距离用Δ(ωi,ωj)表示，最常用的类间距离定义有以下几种。

（1）最近距离

类ωi和类ωj之间的最近距离Δ(ωi,ωj)为ωi类中所有样本与ωj类中所有样本间的最小距离，即

（2）最远距离

类ωi和类ωj之间的最远距离Δ(ωi,ωj)为ωi类中所有样本与ωj类中所有样本间的最大距离，即。

（3）均值距离

类ωi和类ωj之间的最近距离Δ(ωi,ωj)为ωi类的均值mi与ωj类的均值m j之间的距离，即Δ(ωi,ωj)=d(mi,m j)。

三种距离的表达式中d( )可以是任何一种模式相似性测度。

由于定义类间距离的方法不同，故得到的聚类结果可能不一致。

聚类可能以3种方式终止：所有的样本合并为一类；达到所规定的类别数；所有的类别相似性测度大于给定的相似性阈值。

已知样本集为{X1,X2,…,XN}，下面给出层次聚类的具体步骤：

（a）以N个样本作为N个类别，计算每类间的相似度，形成相似度矩阵；

（b）在相似度矩阵中寻找最相似的两个类别，将这两个类别合并；

（c）重新计算各类别间的相似度，获得新的相似度矩阵；

（d）判断是否达到聚类终止的条件，如达到，则聚类终止，否则转到步骤（b）。

3.c-均值算法

c-均值算法是动态聚类法的一种。动态聚类法的特点在于聚类过程通过不断的迭代来完成，且在迭代中通常容许样本从一个聚合类中转移到另一个聚合类中。动态聚类过程如图2-2所示。

c-均值算法的指导思想是假定样本集中的全体样本可分为c类，并选定c个初始聚类中心，然后根据最小距离原则将每个样本分配到某一类中，之后不断迭代计算各类的聚类中心并依新的聚类中心调整聚类情况，直到迭代收敛。

设样本集为{X1,X2,…,X N}，聚合的 c 个类别用ω1,ω2,…,ωc表示，各类的中心分别为m1,m2,…,mc，则c-均值算法采用的准则函数为

在进行聚类之前，还必须预先确定类别数c和初始聚类中心。

类别数c如果不能通过先验知识确定，则可采用作图法近似求出。对c从小到大应用c-均值算法进行聚类，在不同的c值下取得不同的J值，分别用Jc表示，显然准则函数Jc随着c的增加而减小，这样就可作出一条Jc-c 曲线。若曲线上存在一个拐点，则拐点对应的类别数即为欲求的最佳类别数；若拐点不明显，则该方法失效。

初始聚类中心的选择与聚类结果直接相关，选择不同的初始聚类中心会产生不同的聚类结果。初始聚类中心的选择方法较多，例如：

·根据问题的性质，凭经验选择。

·用前c个样本作为初始聚类中心。

·将全部样本随机地分为c类，以每类的均值作为初始聚类中心。

·当样本数N较大时，先随机从中选择一部分样本采用层次聚类法将其聚成c类，以每类的均值作为初始聚类中心。

c-均值算法可描述如下：

（a）选择c个初始聚类中心m1(1),m2(1),…,mc(1), k=1。

（b）计算所有样本与各聚类中心的距离

按最小距离原则将样本X进行聚类，即若

则X∈ωj。

（c）重新计算聚类中心

式中，Ni为当前ωi类中的样本数目。

（d）若存在任一i∈{1,2,…,c}，有mi(k+1)≠mi(k)，则 k=k+1，转向步骤（b）；若任意i∈{1,2,…,c}，都有mi(k+1)=mi(k)，则聚类结束。