聚类算法

聚类技术[2]正在蓬勃发展，对此有贡献的研究领域包括数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销等。各种聚类方法也被不断提出和改进，而不同的方法适合于不同类型的数据，因此对各种聚类方法、聚类效果的比较成为值得研究的课题。 1 聚类算法的分类

目前，有大量的聚类算法[3]。而对于具体应用，聚类算法的选择取决于数据的类型、聚类的目的。如果聚类分析被用作描述或探查的工具，可以对同样的数据尝试多种算法，以发现数据可能揭示的结果。

主要的聚类算法可以划分为如下几类：划分方法、层次方法、基于密度的方法、基于网格的方法以及基于模型的方法[4-6]。

每一类中都存在着得到广泛应用的算法，例如：划分方法中的k-means[7]聚类算法、层次方法中的凝聚型层次聚类算法[8]、基于模型方法中的神经网络[9]聚类算法等。 目前,聚类问题的研究不仅仅局限于上述的硬聚类，即每一个数据只能被归为一类，模糊聚类[10]也是聚类分析中研究较为广泛的一个分支。模糊聚类通过隶 属函数来确定每个数据隶属于各个簇的程度，而不是将一个数据对象硬性地归类到某一簇中。目前已有很多关于模糊聚类的算法被提出，如著名的FCM算法等。

本文主要对k-means聚类算法、凝聚型层次聚类算法、神经网络聚类算法之SOM,以及模糊聚类的FCM算法通过通用测试数据集进行聚类效果的比较和分析。 2 四种常用聚类算法研究 2.1 k-means聚类算法

k-means是划分方法中较经典的聚类算法之一。由于该算法的效率高，所以在对大规模数据进行聚类时被广泛应用。目前，许多算法均围绕着该算法进行扩展和改进。

k-means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。k-means算法的处理过程如下：首先，随机地 选择k个对象，每个对象初始地代表了一个簇的平均值或中心;对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇;然后重新计算每个簇的平均值。 这个过程不断重复，直到准则函数收敛。通常，采用平方误差准则，其定义如下：

这里E是数据库中所有对象的平方误差的总和，p是空间中的点，mi是簇Ci的平均值[9]。

该目标函数使生成的簇尽可能紧凑独立，使用的距离度量是欧几里得距离,当然也可以用其他距离度量。k-means聚类算法的算法流程如下： 输入：包含n个对象的数据库和簇的数目k； 输出：k个簇，使平方误差准则最小。 步骤：

(1) 任意选择k个对象作为初始的簇中心； (2) repeat；

(3) 根据簇中对象的平均值，将每个对象(重新)赋予最类似的簇； (4) 更新簇的平均值，即计算每个簇中对象的平均值； (5) until不再发生变化。 2.2 层次聚类算法

根据层次分解的顺序是自底向上的还是自上向下的，层次聚类算法分为凝聚的层次聚类算法和分裂的层次聚类算法。

凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。四种广泛采用的簇间距离度量方法如下：

这里给出采用最小距离的凝聚层次聚类算法流程： (1) 将每个对象看作一类，计算两两之间的最小距离； (2) 将距离最小的两个类合并成一个新类； (3) 重新计算新类与所有类之间的距离；

(4) 重复(2)、(3)，直到所有类最后合并成一类。 2.3 SOM聚类算法

SOM神经网络[11]是由芬兰神经网络专家Kohonen教授提出的，该算法假设在输入对象中存在一些拓扑结构或顺序，可以实现从输入空间(n维)到输出平面(2维)的降维映射，其映射具有拓扑特征保持性质,与实际的大脑处理有很强的理论联系。

SOM网络包含输入层和输出层。输入层对应一个高维的输入向量，输出层由一系列组织在2维网格上的有序节点构成，输入节点与输出节点通过权重向量连接。 学习过程中，找到与之距离最短的输出层单元，即获胜单元，对其更新。同时，将邻近区域的权值更新，使输出节点保持输入向量的拓扑特征。 算法流程：

(1) 网络初始化，对输出层每个节点权重赋初值；

(2) 将输入样本中随机选取输入向量，找到与输入向量距离最小的权重向量； (3) 定义获胜单元，在获胜单元的邻近区域调整权重使其向输入向量靠拢； (4) 提供新样本、进行训练；

(5) 收缩邻域半径、减小学习率、重复，直到小于允许值，输出聚类结果。 2.4 FCM聚类算法

1965年美国加州大学柏克莱分校的扎德教授第一次提出了‘集合’的概念。经过十多年的发展，模糊集合理论渐渐被应用到各个实际应用方面。为克服非此即彼的分类缺点，出现了以模糊集合论为数学基础的聚类分析。用模糊数学的方法进行聚类分析，就是模糊聚类分析[12]。

FCM算法是一种以隶属度来确定每个数据点属于某个聚类程度的算法。该聚类算法是传统硬聚类算法的一种改进。

算法流程：

(1) 标准化数据矩阵；

(2) 建立模糊相似矩阵，初始化隶属矩阵； (3) 算法开始迭代，直到目标函数收敛到极小值；

(4) 根据迭代结果，由最后的隶属矩阵确定数据所属的类，显示最后的聚类结果。 3 四种聚类算法试验 3.1 试验数据

实验中，选取专门用于测试分类、聚类算法的国际通用的UCI数据库中的IRIS[13]数据集，IRIS数据集包含150个样本数据，分别取自三种不同 的莺尾属植物setosa、versicolor和virginica的花朵样本,每个数据含有4个属性，即萼片长度、萼片宽度、花瓣长度，单位为cm。 在数据集上执行不同的聚类算法，可以得到不同精度的聚类结果。 3.2 试验结果说明

文中基于前面所述各算法原理及算法流程，用matlab进行编程运算，得到表1所示聚类结果。

如表1所示，对于四种聚类算法，按三方面进行比较：(1)聚错样本数：总的聚错的样本数，即各类中聚错的样本数的和；(2)运行时间：即聚类整个 过程所耗费的时间，单位为s；(3)平均准确度：设原数据集有k个类,用ci表示第i类，ni为ci中样本的个数，mi为聚类正确的个数,则mi/ni为 第i类中的精度，则平均精度为：

3.3 试验结果分析

四种聚类算法中，在运行时间及准确度方面综合考虑，k-means和FCM相对优于其他。但是，各个算法还是存在固定缺点：k-means聚类算法的初 始点选择不稳定，是随机选取的，这就引起聚类结果的不稳定，本实验中虽是经过多次实验取的平均值，但是具体初始点的选择方法还需进一步研究；层次聚类虽然 不需要确定分类数，但是一旦一个分裂或者合并被执行，就不能修正，聚类质量受限制；FCM对初始聚类中心敏感，需要人为确定聚类数，容易陷入局部最优 解；SOM与实际大脑处理有很强的理论联系。但是处理时间较

长，需要进一步研究使其适应大型数据库。

聚类分析因其在许多领域的成功应用而展现出诱人的应用前景，除经典聚类算法外，各种新的聚类方法正被不断被提出。

聚类算法总结：

--------------------------------------------------------- 聚类算法的种类：

基于划分聚类算法（partition clustering)

是一种典型的划分聚类算法，它用一个聚类的中心来代表一个簇，即在迭代过程中选择的聚点不k-means： 中的一个点，该算法只能处理数值型数据 k-modes： k-prototypes： k-medoids： CLARA： CLARANS： K-Means算法的扩展，采用简单匹配方法来度量分类型数据的相似度 结合了K-Means和K-Modes两种算法，能够处理混合型数据 在迭代过程中选择簇中的某点作为聚点，PAM是典型的k-medoids算法 CLARA算法在PAM的基础上采用了抽样技术，能够处理大规模数据 CLARANS算法融合了PAM和CLARA两者的优点，是第一个用于空间数据库的聚类算法 Focused 采用了空间索引技术提高了CLARANS算法的效率 CLARAN： PCM： 模糊集合理论引入聚类分析中并提出了PCM模糊聚类算法

基于层次聚类算法：

采用抽样技术先对数据集D随机抽取样本，再采用分区技术对样本进行分区，然后对每个分CURE： 最后对局部聚类进行全局聚类 ROCK： 也采用了随机抽样技术，该算法在计算两个对象的相似度时，同时考虑了周围对象的影响 CHEMALOEN（变色龙首先由数据集构造成一个K-最近邻图Gk ,再通过一个图的划分算法将图Gk 划分成大量的算法）： 图代表一个初始子簇,最后用一个凝聚的层次聚类算法反复合并子簇，找到真正的结果簇 SBAC算法则在计算对象间相似度时，考虑了属性特征对于体现对象本质的重要程度，对于SBAC： 象本质的属性赋予较高的权值 BIRCH算法利用树结构对数据集进行处理，叶结点存储一个聚类，用中心和半径表示，顺序BIRCH： 对象，并把它划分到距离最近的结点，该算法也可以作为其他聚类算法的预处理过程 BUBBLE： BUBBLE-FM： BUBBLE算法则把BIRCH算法的中心和半径概念推广到普通的距离空间 BUBBLE-FM算法通过减少距离的计算次数，提高了BUBBLE算法的效率

基于密度聚类算法：

DBSCAN算法是一种典型的基于密度的聚类算法，该算法采用空间索引技术来搜索对象的邻域，引入DBSCAN： 象”和“密度可达”等概念，从核心对象出发，把所有密度可达的对象组成一个簇 GDBSCAN： 算法通过泛化DBSCAN算法中邻域的概念，以适应空间对象的特点 DBLASD： OPTICS： 满意的结果 OPTICS算法结合了聚类的自动性和交互性，先生成聚类的次序，可以对不同的聚类设置不同的参数，FDC算法通过构造k-d tree把整个数据空间划分成若干个矩形空间，当空间维数较少时可以大大提高FDC： 效率

基于网格的聚类算法：

STING： 利用网格单元保存数据统计信息，从而实现多分辨率的聚类 在聚类分析中引入了小波变换的原理，主要应用于信号处理领域。（备注：小波算法在信号处理，图WaveCluster： 密解密等领域有重要应用，是一种比较高深和牛逼的东西） CLIQUE： OPTIGRID： 是一种结合了网格和密度的聚类算法

基于神经网络的聚类算法：

自组织神经网络该方法的基本思想是--由外界输入不同的样本到人工的自组织映射网络中，一开始时，输入样本引起SOM： 胞的位置各不相同，但自组织后会形成一些细胞群，它们分别代表了输入样本，反映了输入样本的

基于统计学的聚类算法： COBWeb： COBWeb是一个通用的概念聚类方法，它用分类树的形式表现层次聚类 CLASSIT： AutoClass： 立 是以概率混合模型为基础，利用属性的概率分布来描述聚类，该方法能够处理混合型的数据，但要求各

---------------------------------------------------------

几种常用的聚类算法从可伸缩性、适合的数据类型、高维性（处理高维数据的能力）、异常数据的抗干扰度、聚类形状和算法效率6个方面进行了综合性能评价，评价结果如表1所示： 算法名称 WaveCluster ROCK BIRCH CURE K-Prototypes DENCLUE OptiGrid CLIQUE DBSCAN CLARANS 可伸缩性 很高 很高 较高 较高 一般 较低 一般 较高 一般 较低 适合的数据类型 数值型 混合型 数值型 数值型 混合型 数值型 数值型 数值型 数值型 数值型 高维性 很高 很高 较低 一般 较低 较高 较高 较高 较低 较低 异常数据的抗干扰性 较高 很高 较低 很高 较低 一般 一般 较高 较高 较高 聚类形状 任意形状 任意形状 球形 任意形状 任意形状 任意形状 任意形状 任意形状 任意形状 球形

--------------------------------------------------------- 目前聚类分析研究的主要内容：

对聚类进行研究是数据挖掘中的一个热门方向，由于以上所介绍的聚类方法都存在着某些缺点，因此近些年对于聚类分析的研究很多都专注于改进现有的聚类方法或者是提出一种新的聚类方法。以下将对传统聚类方法中存在的问题以及人们在这些问题上所做的努力做一个简单的总结：

1 从以上对传统的聚类分析方法所做的总结来看，不管是k-means方法，还是CURE方法，在进行聚类之前都需要用户事先确定要得到的聚类的数目。然而在现实数据中，聚类的数目是未知的，通常要经过不断的实验来获得合适的聚类数目，得到较好的聚类结果。

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

3 随着信息时代的到来，对大量的数据进行分析处理是一个很庞大的工作，这就关系到一个计算效率的问题。有文献提出了一种基于最小生成树的聚类算法，该算法通过逐渐丢弃最长的边来实现聚类结果，当某条边的长度超过了某个阈值，那么更长边就不需要计算而直接丢弃，这样就

极大地提高了计算效率，降低了计算成本。

4 处理大规模数据和高维数据的能力有待于提高。目前许多聚类方法处理小规模数据和低维数据时性能比较好，但是当数据规模增大，维度升高时，性能就会急剧下降，比如k-medoids方法处理小规模数据时性能很好，但是随着数据量增多，效率就逐渐下降，而现实生活中的数据大部分又都属于规模比较大、维度比较高的数据集。有文献提出了一种在高维空间挖掘映射聚类的方法PCKA（Projected Clustering based on the K-Means Algorithm），它从多个维度中选择属性相关的维度，去除不相关的维度，沿着相关维度进行聚类，以此对高维数据进行聚类。

5 目前的许多算法都只是理论上的，经常处于某种假设之下，比如聚类能很好的被分离，没有突出的孤立点等，但是现实数据通常是很复杂的，噪声很大，因此如何有效的消除噪声的影响，提高处理现实数据的能力还有待进一步的提高。