聚类算法综述

宋坤

（重庆交通大学 信息科学与工程学院，重庆 400074）

聚类算法综述

宋坤

（重庆交通大学 信息科学与工程学院，重庆 400074）

聚类是将物理或抽象对象的集合组成为由类似的对象组成的多个类的过程，是研究数据间逻辑上或物理上的相互关系的技术，是数据挖掘技术中的重要组成部分。结合国内研究现状，论文介绍各类主要的聚类算法及其应用领域。

数据挖掘；相互关系；聚类

1　背景及意义

数据挖掘中聚类算法的应用很广泛。在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群。 在生物学上，聚类能用于基因和蛋白质的分类，获得对种群中固定结构的认识［1］。聚类在地球观测数据中相似地区的确定发挥作用。聚类也能用来对web上的文档进行分类，以发现有用的信息。聚类分析能作为一种独立的工具来获得数据分布的情况，观察每个簇的特点，并对某些特定的节点进一步分析。此外，聚类还可以作为其他方法的预处理步骤。

作为统计学的一个分支，聚类分析已经被广泛地研究若干年，主要集中在基于距离的聚类分析。

2　聚类算法简介

聚类是一个将数据集划分为若干组或簇的过程，使得同一类的数据对象之间的相似度较高，而不同类的数据对象之间的相似度较低。聚类问题的关键是把相似的事物聚集在一起。

2.1传统聚类算法

2.1.1层次方法

层次法对给定的数据对象集合进行层次似的分解。按层次分解的形成方式，层次法可分为凝聚和分裂两大类。凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个类，然后相继地合并相近的类，直到所有的类合并为一个（层次的最上层），或者达到一个终止条件为止。层次方法 （Hierarchical Method）中代表算法BIRCH、CURE、ROCK、CHAMELEON 算法等［2］。

2.1.2划分方法

给定一个包含n个数据对象的数据集，划分法构建数据的k个划分，每个划分表示一个类，并且k ≤ n。同时满足如下的要求：①每个组至少包含一个对象；②每个对象属于且仅属于一个组。其代表算法有K-MEANS、K-MEDOIDS、大型数据库划分方法（CLARANS）等。

2.1.3密度方法

该方法主要思想是：只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域内必须至少包含某个数目的点。其代表算法有DBSCAN、OPTICS和DE NCLUE等［3］。

2.2新发展的聚类算法

2.2.1基于模糊的聚类方法

基于目标函数的模糊聚类方法，该方法把聚类归结成一个带约束的非线性规划问题，通过优化求解获得数据集的模糊划分和聚类。该方法设计简单，解决问题的范围广，还可以转化为优化问题而借助经典数学的非线性规划理论求解，并易于在计算机上实现。因此，随着计算机的应用和发展，基于目标函数的模糊聚类算法成为新的研究热点。在基于目标函数的聚类算法中，FCM 类型算法的理论最为完善、应用最为广泛。

2.2.2基于粒度的聚类方法

如果从信息粒度的角度来看，就会发现聚类和分类的相通之处：聚类操作实际上是在一个统一粒度下进行计算的；分类操作是在不同粒度下进行计算的。在粒度原理下，聚类和分类的相通使得很多分类的方法也可以用在聚类方法中。作为一个新的研究方向，虽然目前粒度计算还不成熟，尤其是对粒度计算语义的研究还相当少，但是相信随着粒度计算理论本身的不断完善和发展。

2.2.3量子聚类

该方法把聚类问题看作一个物理系统，其很好的例子就是基于相关点的 Pott 自旋和统计机理提出的量子聚类模型。并且许多算例表明，对于传统聚类算法无能为力的几种聚类问题，该算法都得到了比较满意的结果［4］。

2.2.4谱聚类

为了能在任意形状的样本空间上聚类，且收敛于全局最优解，学者们开始研究一类新型的聚类算法，称为谱聚类算法（Spectral Clustering Algorithm）。谱聚类算法最初用于计算机视觉、VLSI设计等领域，最近才开始用于机器学习中，并迅速成为国际上机器学习领域的研究热点［5］。

3　结语

数据聚类正在蓬勃的发展，有贡献的领域包括数据挖掘，统计学，机器学习，空间数据库技术，生物学以及市场营销。现在数据聚类分析已经成为一个非常活跃的研究课题。

［1］田野，刘大有，杨博. 复杂网络聚类算法在生物网络中的应用［J］. 计算机科学与探索，2010，04:330-337.

［2］Amineh Amini，Teh Ying Wah，Hadi Saboohi. On Density-Based Data Streams Clustering Algorithms: A Survey［J］. Journal of Computer Science & Technology，2014，01:116-141.

［3］Local and global approaches of affinity propagation clustering for large scale data［J］. Journal of Zhejiang University（Science A:An International Applied Physics & Engineering Journal），2008，10:1373-1381.

［4］王玉瑛. 量子聚类及其在社团检测中的应用［D］.西安电子科技大学，2014.

［5］蔡晓妍，戴冠中，杨黎斌. 谱聚类算法综述［J］. 计算机科学，2008，07:14-18.

TP311.13

A

1003-5168（2015）11-254-01

宋坤（1989.07- ），男，河南新乡人，重庆交通大学信息科学与工程学院2013级硕士研究生，软件工程专业，研究方向：数据挖掘。