2.3.2　聚类类型

经过持续了半个多世纪深入研究聚类算法，聚类技术已经成为常用的数据分析技术之一。其各种算法的提出、发展、演化使得聚类算法家族不断壮大。下面就针对目前数据分析和数据挖掘业界主流的认知对聚类算法进行介绍。

1．划分方法

给定具有n个对象的数据集，采用划分方法对数据集进行k个划分，每个划分（每个组）代表一个簇。k≤n，并且每个簇至少包含一个对象，而且每个对象一般来说只能属于一个组。对于给定的k值，划分方法是：一般要做一个初始划分，然后采取迭代重新定位技术，通过让对象在不同组间移动来改进划分的准确度和精度。一个好的划分原则是：同一个簇中对象之间的相似性很高（或距离很近），而不同簇的对象之间相异度很高（或距离很远）。

（1）K-Means算法：又叫K均值算法，这是目前最著名、使用最广泛的聚类算法。在给定一个数据集和需要划分的数目k后，该算法可以根据某个距离函数反复把数据划分到k个簇中，直到收敛为止。K-Means算法用簇中对象的平均值来表示划分的每个簇，大致的步骤是：首先把随机抽取的k个数据点作为初始的聚类中心（种子中心），然后计算每个数据点到每个种子中心的距离，并把每个数据点分配到距离它最近的种子中心；一旦所有的数据点都被分配完成，每个聚类的聚类中心（种子中心）按照本聚类（本簇）的现有数据点重新计算；这个过程不断重复，直到收敛，即满足某个终止条件为止，最常见的终止条件是误差平方和SSE（指令集）局部最小。

（2）K-Medoids算法：又叫K中心点算法，该算法用最接近簇中心的一个对象来表示划分的每个簇。K-Medoids算法与K-Means算法的划分过程相似，两者最大的区别是K-Medoids算法是用簇中最靠近中心点的一个真实的数据对象来代表该簇的，而K-Medoids算法是用计算出来的簇中对象的平均值来代表该簇的，这个平均值是虚拟的，并没有一个真实的数据对象具有这些平均值。

2．层次方法

在给定n个对象的数据集后，可用层次方法（Hierarchical Methods）对数据集进行层次分解，直到满足某种收敛条件为止。按照层次分解的形式不同，层次方法又可以分为凝聚层次聚类和分裂层次聚类。

（1）凝聚层次聚类：又叫自底向上方法，一开始将每个对象作为单独的一类，然后相继合并与其相近的对象或类，直到所有小的类别合并成一个类，即层次的最上面，或者达到一个收敛，即终止条件为止。

（2）分裂层次聚类：又叫自顶向下方法，一开始将所有对象置于一个簇中，在迭代的每一步中，类会被分裂成更小的类，直到最终每个对象在一个单独的类中，或者满足一个收敛，即终止条件为止。

3．基于密度的方法

传统的聚类算法都是基于对象之间的距离，即距离作为相似性的描述指标进行聚类划分，但是这些基于距离的方法只能发现球状类型的数据，而对于非球状类型的数据来说，只根据距离来描述和判断是不够的。鉴于此，人们提出了基于密度的方法（Density-Based Methods），其原理是：只要邻近区域内的密度（对象的数量）超过了某个阈值，就继续聚类。换言之，给定某个簇中的每个数据点（数据对象），在一定范围内必须包含一定数量的其他对象。该算法从数据对象的分布密度出发，把密度足够大的区域连接在一起，因此可以发现任意形状的类。该算法还可以过滤噪声数据（异常值）。基于密度的方法的典型算法包括DBSCAN（Density-Based Spatial Clustering of Application with Noise），以及其扩展算法OPTICS（Ordering Points to Identify the Clustering Structure）。其中，DBSCAN算法会根据一个密度阈值来控制簇的增长，将具有足够高密度的区域划分为类，并可在带有噪声的空间数据库里发现任意形状的聚类。尽管此算法优势明显，但是其最大的缺点就是，该算法需要用户确定输入参数，而且对参数十分敏感。

4．基于网格的方法

基于网格的方法（Grid-Based Methods）将把对象空间量化为有限数目的单元，而这些单元则形成了网格结构，所有的聚类操作都是在这个网格结构中进行的。该算法的优点是处理速度快，其处理时间常常独立于数据对象的数目，只跟量化空间中每一维的单元数目有关。基于网格的方法的典型算法是STING（Statistical Information Grid，统计信息网格）算法。该算法是一种基于网格的多分辨率聚类技术，将空间区域划分为不同分辨率级别的矩形单元，并形成一个层次结构，且高层的低分辨率单元会被划分为多个低一层次的较高分辨率单元。这种算法从最底层的网格开始逐渐向上计算网格内数据的统计信息并储存。网格建立完成后，用类似DBSCAN的方法对网格进行聚类。