传统的聚类分析方法简介

【摘要】将一组（Set）物理的或者抽象的对象，根据它们之间的相似度，分为若干组（Group），其中相似的对象构成一组，这一过程就称为聚类过程（Clustering）。一个聚类（Cluster）就是由彼此相似的一组对象所构成的集合，不同聚类中的对象是不相似的。可以看出，聚类就是从给定的数据集中搜索出数据项（Items）之间所存在的有价值的联系。

有关的聚类方法主要有划分类方法、分层类方法、基于密度类方法、基于网格类方法和基于模型类方法。

一、划分方法（Partitioning Method）

给定一个有n个元素或者数据对象的数据集，划分方法将数据集划分为k个分组，其中每一个分组就代表一个聚类，k ≤ n。而且这k个分组满足下列条件：

（1）每一个分组至少包含一个数据对象；

（2）每一个数据对象属于且仅属于一个分组（注意：这个要求在某些模糊聚类算法中可以放宽）；

对于给定的k，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好，而所谓好的标准就是：同一分组中的对象相似度越大越好，而不同分组中的对象相似度越小越好。

代表算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法.

二、层次方法（Hierarchical Method）

层次方法就是通过分解所给定的数据对象集来创建一个层次。根据层次分解形成的方式，可以将层次方法分为自下而上和自上而下两种类型。自下而上的层次方法从每个对象均为一个（单独的）组开始，逐步将这些（对象）组进行合并，直到合并到了层次顶端或满足终止条件为止。自下而上的层次方法从所有对象均属于一个组开始，每一次循环将其（组）分解为更小的组，直到每个对象构成一组或满足终止条件为止。

代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等。

三、基于密度方法（Density-based Method）

大多数划分方法是基于对象间的距离进行聚类的，这类方法仅能发现圆形或球形的聚类而较难发现具有任意形状的聚类。而基于密度概念的聚类方法实际上就是不断增长所获得的聚类直到"邻近"（数据对象或点）密度超过一定阈值（如一个聚类中的点数，或一个给定半径内至少必须包含的点数）为止。这种方法可以用于消除数据中的噪声（异常数据），以及帮助发现任意形状的聚类。

代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等。

四、基于网格方法（Grid-based Method）

基于网格方法将对象空间划分为有限数目的单元以形成网格结构。所有聚类操作均是在这一网格结构上进行的。这种方法的主要优点就是处理时间由于与数据对象个数无关而仅仅与划分对象空间的网格数相关，从而显得相对较快。

代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法等。

五、基于模型方法（Model-based Method）

基于模型方法就是为每个聚类假设一个模型，然后再去发现符合相应模型的数据对象。一个基于模型的算法可以通过构造一个描述数据点空间分布的密度函数来确定具体聚类。它根据标准统计方法并考虑到"噪声"或异常数据，可以自动确定聚类个数，因而它可以产生很鲁棒的聚类方法。

基于划分聚类算法：（最常用也是最知名的就是k-means和k-medoids）

1）k-means是一种典型的划分聚类算法，它用一个聚类的中心来代表一个簇，即在迭代过程中选择的聚点不一定是聚类中的一个点，该算法只能处理数值型数据。

2）k-medoids算法的基本策略就是通过首先任意为每个聚类找到一个代表对象（Medoid）而首先确定n个数据对象的k个聚类（也需要循环进行），其它对象则根据它们与这些聚类代表的距离分别将它们归属到各相应聚类中（仍然依据距离最小）。

基于层次聚类算法：

1）BIRCH算法利用树结构对数据集进行处理，叶结点存储一个聚类，用中心和半径表示，顺序处理每一个对象，并把它划分到距离最近的结点，该算法也可以作为其他聚类算法的预处理过程。

2）CURE：采用抽样技术先对数据集D随机抽取样本，再采用分区技术

3）CHEMALOEN（变色龙算法）：首先由数据集构造成一个K-最近邻图Gk ,再通过一个图的划分算法将图Gk 划分成大量的子图,每个子图代表一个初始子簇,最后用一个凝聚的层次聚类算法反复合并子簇，找到真正的结果簇。

基于密度聚类算法：

1）DBSCAN算法是一种典型的基于密度的聚类算法，该算法采用空间索引技术来搜索对象的邻域，引入了"核心对象"和"密度可达"等概念，从

核心对象出发，把所有密度可达的对象组成一个簇。

2）OPTICS算法结合了聚类的自动性和交互性，先生成聚类的次序，可以对不同的聚类设置不同的参数，来得到用户满意的结果。

基于网格聚类算法：

1）STING算法利用网格单元保存数据统计信息，从而实现多分辨率的聚类。

2）CLIQUE算法是一种结合了网格和密度的聚类算法。

基于模型聚类算法：（这种聚类方法忽略不计，没有什么可研究可改进的地方）

1）统计方法COBWEB

2）SOM神经网络方法

传统的聚类方法一般都是适合于某种情况的聚类，没有一种方法能够满足各种情况下的聚类，比如BIRCH方法对于球状簇有很好的聚类性能，但是对于不规则的聚类，则不能很好的工作；K-medoids方法不太受孤立点的影响，但是其计算代价又很大。因此如何解决这个问题成为当前的一个研究热点，有学者提出将不同的聚类思想进行融合以形成新的聚类算法，从而综合利用不同聚类算法的优点，在一次聚类过程中综合利用多种聚类方法，能够有效的缓解这个问题。

我要打赏