第4章 聚类分析
4.1 聚类分析
聚类分析是指事先不了解一批样本中的每一个样本的类别或其他的先验知识，而唯一的分类根据是样本的特征，利用某种相似度度量的方法，把特征相同或相似的归为一类，实现聚类划分。
聚类分析就是对探测数据进行分类分析的一个工具，许多学科要根据所测得的或感知到的相似性对数据进行分类，把探测数据归入到各个聚合类中，且在同一个聚合类中的模式比不同聚合类中的模式更相似，从而对模式间的相互关系做出估计。聚类分析的结果可以被用来对数据提出初始假设，分类新数据，测试数据的同类型及压缩数据。
聚类算法的重点是寻找特征相似的聚合类。人是二维的最佳分类器，然而大多数实际的问题涉及高维的聚类，对高维空间内的数据的直观解释，其困难是显而易见的。另外，数据也不会服从规则现象分布，这就是有大量聚类算法出现在文献中的原因。
4.1.1 聚类的定义
Everett提出，一个聚合类是一些相似的实体集合，而且不同聚合类的实体是不相似的。在一个聚合类内的两个点间的距离小于在这个类内任一点和不在这个类内的另一任一点间的距离。聚合类可以被描述成在n维空间内存在较高密度点的连续区域和较低密度点的区域，而较低密度点的区域把其他较高密度点的区域分开。
在模式空间S中，若给定N个样本X1，X2，…，XN，聚类的定义是：按照相互类似的程度找到相应的区域R1，R2，…，RM，对任意Xi（i=1，2，…，N）归入其中一类，而且不会同时属于两类，即
这里∩、∪分别指交集和并集。
选择聚类的方法应以一个理想的聚类概念为基础。然而，如果数据不满足由聚类技术所做的假设，则算法不是去发现真实的结构而是在数据上强加某种结构。
4.1.2 聚类准则
设有未知类别的N个样本，要把它们划分到M类中去，可以有多种优劣不同的聚类方法，怎样评价聚类的优劣，这就需要确定一种聚类准则。但客观地说，聚类的优劣是就某一种评价准则而言，很难有对各种准则均呈优良表现的聚类方法。
聚类准则的确定，基本上有两种方法。一种是试探法，根据所分类的问题，确定一种准则，并用它来判断样本分类是否合理。例如，以距离函数作为相似性的度量，用不断修改的阈值来探究对此种准则的满足程度，当取得极小值时，就认为得到了最佳划分。另一种是规定一种准则函数，其函数值与样本的划分有关，当取得极小值时，就认为得到了最佳划分下给出的一种简单而又广泛应用的准则，即误差平方和准则：
设有N个样本，分属于ω1，ω2，…，ωM类，设有Ni个样本的ωj类，其均值为
因为有若干种方法可将N个样本划分到M类中去，因此对应一种划分，可求得一个误差平方和J，要找到使J值最小的那种划分。定义误差平方和
经验表明，当各类样本均很密集，各类样本个数相差不大，而类间距离较大时，适合采用误差平方和准则。若各类样本数相差很大，类间距离较小时，就有可能将样本数多的类一分为二，而得到的J值却比大类保存完整时小，误以为得到了最优划分，实际上得到了错误分类。
4.1.3 基于试探法的聚类设计
基于试探法的聚类设计采用假设某种分类方案，确定一种聚类准则，计算J值，找到J值最小的那一种分类方案，则认为该种方法为最优分类。基于试探的未知类别聚类算法，包括最临近规则的试探法、最大最小距离试探法和层次聚类试探法。
1．最临近规则的试探法
假设前i个样本已经被分到k个类中。则第i+1个样本应该归入哪—个类？假设归入ωa类，要使J最小，则应满足第i+1个样本到ωa类的距离小于给定的阈值；若大于给定的阈值T，则应为其建立一个新的类ωk+1。在未将所有的样本分类前，类数是不能确定的。
这种算法与第一个中心的选取、阈值T的大小、样本排列次序及样本分布的几何特性有关。这种方法运算简单，当用有关于模式几何分布的先验知识作指导给出阈值T及初始点时，则能较快地获得合理的聚类结果。
2．最大最小距离试探法
最临近规则的试探法受阈值T的影响很大。阈值的选取是聚类成败的关键之一。最大最小距离算法充分利用样本内部特性，计算出所有样本间的最大距离作为归类阈值的参考，改善了分类的准确性。例如，采用某样本到某一个聚类中心的距离小于最大距离的一半，则归入该类，否则建立新的聚类中心。
3．层次聚类试探法
层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为合并、分裂两种方案。
合并的层次聚类是一种自底向上的策略，首先将每个对象作为一个类，然后根据类间距离的不同，合并距离小于阈值的类，合并一些相似的样本，直到终结条件被满足。合并算法会在每一步减小聚类中心数量，聚类产生的结果来自于前一步的两个聚类的合并。绝大多数层次聚类方法属于这一类，它们只是在相似度的定义上有所不同。
分裂的层次聚类与合并的层次聚类相反，采用自顶向下的策略，它首先将所有对象置于同一个簇中，然后逐渐细分为越来越小的样本簇，直到达到了某个终止条件。分裂算法与合并算法的原理相反，在每一步增加聚类中心数目，每一步聚类产生的结果，都是将前一步的一个聚类中心分裂成两个而得到的。
常用的聚类方法有均值聚类、分层聚类和模糊聚类。