聚类算法研究综述

郑强 高群

摘要：随着数据挖掘技术的迅速发展，作为其重要的组成部分，聚类技术已经被广泛应用于数据分析、图像处理、市场研究等许多领域。聚类算法研究已经成为数据挖掘研究领域中非常活跃的一个研究课题。本文分析了各类常见聚类算法的应用场景及优缺点，指出了聚类分析研究重点关注内容。

关键词：聚类；划分聚类；层次聚类

1 引言

同时，聚类作为数据挖掘的主要方法之一，越来越引起人们的关注。聚类[1]分析是一种无先验知识的机器学习过程，是数据挖掘一个重要的分支，遵循同一个集合中的样本相似性最大，不同集合中的样本差异性最大的思想，把样本集分为若干个集合，每个集合称为一个簇。通过聚类， 人们能够识别密集的和稀疏的区域， 发现全局的分布模式以及数据属性之间有意义的相互关系。

聚类算法在计算机科学、生医学、地球科学、社会科学、经济学等领域都有广泛的应用。已有的经典聚类算法大致可分为五种：基于划分的、基于层次的、基于密度的、基于网格的和基于图论的聚类。本文比较了数据挖掘中典型的聚类算法，分析了它们各自的优缺点并指出了其面临的挑战。

2典型聚类算法

2.1划分聚类方法

划分聚类[2]将数据对象划分成不重叠的子集，使得每个数据对象都分布在不同的子集中。最经典的聚类算法是K-Means[3]，其主要思想是找出数据集的k个聚类中心，把数据集划分为是k个类簇，使得数据集中的数据点与所属类簇的类中心的距离平方和最小。该算法优点是算法简单易于实现，但是需人工指定聚类数，同时受聚类中心的初始选择影响大，易陷入局部最优解。K-modes是K-Means算法的一個延伸，主要是可处理分类属性数据，而不像K-Means那样只能处理数值属性的数据。K-Means和K-modes处理离群点时候性能较差。AP是Frey等人2007年提出的一种聚类算法，该算法与K-means算法等同属于k中心聚类方法， AP算法部分地克服了K-means对初始聚类中心的选择敏感且容易陷入局部极值的缺陷。

2.2基于密度的聚类

基于密度的聚类算法从数据对象的分布密度出发，将密度足够大的相邻区域连接起来，从而可以发现具有任意形状的聚类，并能有效处理异常数据，它主要用于对空间数据的聚类。DBSCAN[4]是一个典型的基于密度的聚类方法，它将聚类定义为一组密度连接的点集，然后通过不断生长足够高密度的区域来进行聚类。DENCLUE[5]则根据数据点在属性空间中的密度来进行聚类。从本质上讲，DENCLUE是基于密度的聚类算法与基于网格的预处理的结合，它受目标数据的维度影响较小。

2.3 基于网格的聚类

基于网格的聚类从对数据空间划分的角度出发，利用属性空间的多维网格数据结构，将空间划分为有限数目的单元以构成一个可以进行聚类分析的网格结构。该方法的主要特点是处理时间与数据对象的数目无关，但与每维空间所划分的单元数相关。与基于密度的聚类只能处理数值属性的数据所不同，基于网格的聚类可以处理任意类型的数据，但以降低聚类的质量和准确性为代价。STING[6]是一个基于网格多分辨率的聚类方法，它将空间划分为方形单元，不同层次的方形单元对应不同层次的分辨率。CLIQUE[7]也是一个基于网格的聚类算法，它结合了网格聚类与密度聚类的思想，对于处理大规模高维数据具有较好的效果。

2.4 基于图论的聚类

基于图论的方法是把聚类转换为一个组合优化问题，并利用图论和相关的启发式算法来解决该问题。基于超图的划分和基于光谱的图划分方法是这类算法的两个主要应用形式。该方法的一个优点在于它不需要进行一些相似度的计算，就能把聚类问题映射为图论中的一个组合优化问题。

2.5层次聚类算法

层次聚类[8]算法通过将数据组织成若干组并形成一个相应的树状图来进行聚类，它又可以分为两类，即自底向上的聚合层次聚类和自顶向下的分解层次聚类。聚合聚类的策略是先将每个对象各自作为一个原子聚类，然后对这些原子聚类逐层进行聚合，直至满足一定的终止条件；后者则与前者相反，它先将所有的对象都看成一个聚类，然后将其不断分解直至满足终止条件。

CURE[9]，ROCK[10] 和CHAMELEON[11] 算法是聚合聚类中最具代表性的三个方法。Guha 等人在1998 年提出了CURE 算法。该方法不用单个中心或对象来代表一个聚类，而是选择数据空间中固定数目的、具有代表性的一些点共同来代表相应的类，这样就可以识别具有复杂形状和不同大小的聚类，从而能很好地过滤孤立点。ROCK 算法是对CURE 的改进，除了具有CURE 算法的一些优良特性之外，它还适用于类别属性的数据。CHAMELEON算法是Karypis 等人于1999 年提出来的，它在聚合聚类的过程中利用了动态建模的技术。

结束语

本文分析了各类常见聚类算法的应用场景及优缺点，指出了聚类分析研究重点关注内容。聚类算法的研究具有广泛的应用前景，其今后的发展也面临着越来越多的挑战，尤其是以下几个方面更值得考虑：选取合适的聚类类别数；处理大规模数据和高维数据的能力；将领域知识引入聚类过程；对聚类的结果进行准确评价，以判断是否达到最优解等。

参考文献：

[1]孙吉贵， 刘杰， 赵连宇. 聚类算法研究[J]. 软件学报， 2008， 19（1）：48-61.

[2]卢志茂， 冯进玫， 范冬梅，等. 面向大数据处理的划分聚类新方法[J]. 系统工程与电子技术， 2014， 36（5）：1010-1015.

[3]Hartigan J A， Wong M A. Algorithm AS 136： A K-Means Clustering Algorithm[J]. Journal of the Royal Statistical Society， 1979， 28（1）：100-108.

[4]冯少荣， 肖荣俊. DBSCAN 聚类算法的研究与改进[D]. 中国矿业大学学报编辑部， 2008.

[5]张丽芳. 3种聚类算法性能比较分析[J]. 长江大学学报（自科版）， 2009（2）：250-251.

[6]李焱， 刘弘， 郑向伟. 折半聚类算法在基于社会力的人群疏散仿真中的应用[J]. 计算机应用， 2017， 37（5）：1491-1495.

[7]项响琴， 李红， 陈圣兵. CLIQUE聚类算法的分析研究[J]. 合肥学院学报（综合版）， 2011， 21（1）：54-58.

[8]淦文燕， 李德毅， 王建民. 一种基于数据场的层次聚类方法[J]. 电子学报， 2006， 34（2）：258-262.

[9]赵妍， 赵学民. 基于CURE的用户聚类算法研究[J]. 计算机工程与应用， 2012， 48（11）：97-101.

[10]金阳， 左万利. 一种基于动态近邻选择模型的聚类算法[J]. 计算机学报， 2007， 30（5）：756-762.

[11]龙真真， 张策， 刘飞裔，等. 一种改进的Chameleon算法[J]. 计算机工程， 2009， 35（20）：189-191.