1.4 聚类设计

前面介绍的分类问题是利用已知类别的样品训练集来构造分类器的。其训练集样品是已知类别的，所以又称为有监督学习或有教师分类，在已知类别样品的“指导”监督下对单个待测样品进行分类。聚类问题则不同，它事先不了解一批样品中的每一个样品的类别或者其他的先验知识，而唯一的分类根据是样品的特性，利用样品的特性来构造分类器。这种分类称为无监督分类，通常叫做聚类或集群。

聚类分析就是对探测数据进行分类分析的一个工具，许多学科要根据所测得的或感知到的相似性对数据进行分类，把探测数据归入到各个聚合类中，且在同一个聚合类中的模式比不同聚合类中的模式更相似，从而对模式间的相互关系做出估计。聚类分析的结果可以被用来对数据提出初始假设，分类新数据，测试数据的同类型及压缩数据。

聚类算法的重点是寻找特征相似的聚合类。人类是二维的最佳分类器，然而大多数实际的问题涉及高维的聚类。对高维空间内的数据的直观解释，其困难是显而易见的，另外，数据也不会服从规则理想分布，这就是有大量聚类算法出现在文献中的原因。

1.聚类的定义

Evertt提出一个聚合类是一些相似的实体集合，而且不同聚合类的实体是不相似的。在一个聚合类内的两个点间的距离小于在这个类内任一点和不在这个类内的另一点间的距离。聚合类可以被描述成在n维空间内，存在较高密度点的连续区域和较低密度点的区域，而较低密度点的区域把其他较高密度点的区域分开。

在模式空间S中，若给定N个样品X1，X2，…，XN，聚类的定义是：按照相互类似的程度找到相应的区域R1，R2，…，RM，对任意Xi（i=1，2，…，N）归入其中一类，而且不会同时属于两类，即

R1∪R2∪…∪RM=R

Ri∩Rj=∅（i≠j）

选择聚类的方法应以一个理想的聚类概念为基础。然而，如果数据不满足由聚类技术所做的假设，则算法不是去发现真实的结构而是在数据上强加某种结构。

2.聚类准则

设有未知类别的N个样品，要把它们划分到M类中去，可以有多种优劣不同的聚类方法；怎样评价聚类的优劣，这就需要确定一种聚类准则。但客观地说，聚类的优劣是就某一种评价准则而言的，很难有对各种准则均呈优良表现的聚类方法。

聚类准则的确定，基本上有两种方法。一种是凭经验，根据所分类的问题，确定一种准则，并用它来判断样品分类是否合理。例如，以距离函数作为相似性的度量，用不断修改的阈值来探究对此种准则的满足程度。另一种是规定一种准则函数，其函数值与样品的划分有关，当取得极小值时，就认为得到了最佳划分。下面给出一种简单而又广泛应用的准则，即误差平方和准则：

设有N个样品，分属于ω1，ω2，…，ωM类，设有Ni个样品的ωi类，其均值为

因为有若干种方法可将N个样品划分到M类中去，因此对应一种划分，可求得一个误差平方和J，要找到使J值最小的那种划分。定义误差平方和

经验表明，当各类样品均很密集，各类样品个数相差不大，而类间距离较大时，适合采用误差平方和准则，如图1-6（a）所示。若各类样品数相差很大，类间距离较小时，就有可能将样品数多的类一分为二，而得到的J值却比大类保持完整时小，误以为得到了最优划分，实际上得到了错误的划分，如图1-6（b）所示。

图1-6 样品分布与误差平方和准则关系