聚类算法研究

摘要：聚类分析在数据挖掘领域中是一个非常重要的研究课题，该文阐述了聚类算法的基本原理和性能要求，并依据算法思想的不同把聚类算法分为五类，详细介绍了每一类的算法思想、优缺点及典型算法，有利于用户对聚类算法的选择和研究者对聚类算法的改进研究，最后探讨了聚类算法今后的发展趋势。

关键词：数据挖掘；聚类；聚类算法

中图分类号：TP391.1 文献标识码：A 文章编号：1007-9599 （2012） 21-0000-02

1 引言

信息科学技术的高速发展使得各行各业中人们面临的数据越来越多，聚类分析能够帮助人们从海量的数据中提取能够为人们所利用的信息和知识，目前聚类分析已经被广泛地运用于计算机的图像处理、经济学的市场分析、分子生物学的基因监测、web技术领域的信息检索等各个领域并取得一定成就，因此聚类分析已成为数据挖掘研究领域中很热门的研究课题之一。

2 聚类基本原理及性能要求

聚类简单来讲就是依据数据其自身的特征将数据集进行划分成若干类的过程，划分的结果是相同类内数据相似度尽可能大、不同类间数据相似度尽可能小，从而发现数据集的内在结构。

聚类在不同的应用领域有不同的特殊要求，聚类算法的典型性能要求有一下几个方面：

（1）伸缩性；

（2）兼容性；

（3）有效处理噪声数据；

（4）能处理基于约束的聚类；

（5）可解释性和可用性。

3 聚类算法的分类研究

随着人们对聚类算法的深入研究和应用实践，很多聚类算法被先后提出不同的聚类算法是基于不同的思想而开发出的，而且具有不同的优缺点，针对各种聚类算法的研究现状与构造思想，可以把目前的聚类算法大致如下几类：基于划分的方法（partitioning method），基于层次的方法（hierachical method），基于密度的方法（density-based method），基于网格的方法（grid-based method）和基于模型的方法（model-based method）。

3.1 划分方法

基于划分方法的聚类算法的基本思想是：给出要进行聚类的数据集（假设含有n个数据）和要生成的类的个数（假设为K，k

3.2 层次方法

层次聚类方法是把给定的数据对象集合进行逐层的分解， 每次迭代分解过程中，类的个数及类内的数据成员都会发生变化。层次聚类算法又可分成凝聚聚类方法和分裂聚类方法，凝聚聚类方法的基本思想是：首先每个数据单独成类，然后把相距最近的两个聚类合并，重复这个过程，这样就会逐步形成越来越大的类，直到所有的数据对象都属于同一个类或符合某一设定的结束条件。分裂聚类算法与凝聚型算法相反，首先将所有数据对象存放于一个类中，然后逐渐细分为越来越小的类，直到所有数据对象单独成类或符合某个设定的结束条件。典型的层次聚类算法有BIRCH、CURE、ROCK等算法。BIRCH算法是一种综合的层次聚类方法，其思想是首先将所有的数据对象按照一定的标准化成很多小的子聚类，然后再在子类上利用其它合适的聚类算法进行聚类。BIRCH算法伸缩性好并且适用于动态聚类。但是BIRCH算法不适应于非球状的聚类，对输入参数也有些特定要求。CURE算法在开始执行的时候是选择多个数据对象表示相应的类，这些数据对象在数据库中具有一定的代表性。然后根据规定的条件向聚类中心收缩。该算法受孤立点的影响比较小。但是该算法中由于初始中心数据的选择而受主观因素的影响比较突出。ROCK算法是基于CURE算法上的改进的算法，它是利用聚类间的连接进行聚类合并，ROCK算法比CURE算法更适用于类别属性的数据。基于层次的聚类在实际的操作过程中，每一步一旦执行不能被退回，而且各类之间的数据对象也不能任意交换，这样容易形成质量较差的聚类结果。但层次聚类算法实现起来非常简单，所以在实际应用中广受用户欢迎。

3.3 密度方法

基于密度的聚类的主要思想是依据数据对象的分布密度进行聚类，首先该算法将含有超过一定数目的数据对象的区域连接起来聚集成一类，然后对没有归类的区域进行聚类，只要一个区域内的数据对象的密度大过事先设定的阈值，就把该区域的数据对象和它最近的聚类合并为同一类。基于密度的聚类算法克服了基于距离聚类算法不能发现复杂形状聚类的弱点，而且基于密度的聚类算法不需要预先输入聚类的数目，并可用来过滤“噪声”数据。典型的基于密度的聚类算法有：DBSCAN算法、PTICS算法、DENCLUE算法等。DBSCAN聚类算法主要是通过检测数据库中每个数据点的临域来进行聚类。若一个点p的邻域中包含数据对象的密度大于最小阀值，就会创建一个以p作为中心点的新聚类，然后搜寻与中心数据点直接密度可达的数据点加入到相应聚类中，重复这个过程，直到所有聚类不在变化时，该算法结束。该算法的优点是可以发现任意形状的聚类并且能很好的处理噪声数据，缺点是对用户定义的参数敏感、算法效率不高。PTICS很好的处理了参数选择的问题，其算法思想是为自动交互的聚类分析计算出一个增强聚类顺序，而并不像其他聚类方法一样明确产生一个聚类。DENCLUE算法是一种基于一组密度分布函数的聚类算法，主要思想是首先用某种数学函数来刻画每个数据点的影响，所有数据点的影响函数的总和构成空间数据的整体密度，聚类通过确定全局密度函数的局部最大来得到。该聚类算法可以发现任意形状聚类，受孤立点的影响小。

3.4 网格方法

基于网格的聚类算法使用了一种多分辨率的网格数据结构，该类算法首先将数据空间划分为有限数目的单元（看似是由正方体或长方体组成的网格），然后以网格上的单元为对象进行聚类操作。基于网络的聚类算法的优点是处理速度快，因为该算法的处理时间不依赖于数据对象的个数，仅仅与划分的单元个数有关。另外该方法的聚类结果与数据的输入顺序无关，兼容性比较好，可以处理多种类型的数据，但这样操作却会带来一定的代价，使得聚类的质量和准确性有所降低。基于网格的聚类算法的缺点是只能寻找到边缘是垂直或水平的聚类，而无法发现斜边缘的聚类。典型的基于网格的聚类方法有STING、WaveCluster 和CLIQUE等算法。STING算法将空间划分为许多方形单元，再根据方形单元分辨率的级别不同把方形单元划分为不同的级别，然后这些方形单元再根据级别的不同构成一个层次结构。该算法有益于增量更新与并行处理，但聚类的质量往往受网格结构最底层的粒度大小的影响。Wavecluster算法以信号处理思想为基础网格聚类算法，该算法采用数据空间上强加的一个多维网络结构进行汇总数据。LIQUE 算法融合了基于密度和基于网格的聚类思想，即使对于大规模高维数据也能取得较好的聚类效果。

3.5 模型方法

基于模型的聚类方法的基本思想是：首先对要进行聚类的数据集设定多个数据模型，然后尝试寻找数据集与这些数学模型的最佳匹配，此方法操作的基础是假定数据集都有一个内在的混合概率分布。当前多数基于模型的算法主要应用于仿生学方面。基于模型的典型聚类方法有两种：统计学方法（例如COBWEB、CLASSIT和AutoClass）和神经网络方法（例如SOM、ART、LVQ）。COBWEB算法是一种非常有代表性的简单增量概念聚类算法，该算法使用分类属性-值对来描述输入对象，采用分类树的形式创建层次聚类。COBWEB 算法的优势是在不需要任何参数下可以自动更改划分中类的个数，这种操作是在每个属性上的概率分布是相互没有联系的基础上操作的，但COBWEB算法基于的假设条件不一定总是正确的，这在一定程度上会影响聚类结果，且该聚类算法不适合应用于数据量很大的数据集。CLASSIT算法是在COBWEB算法基础上改进的算法，该算法利用一个改进的分类描述方法，允许对连续取值属性进行增量式聚类操作，聚类过程中为每个结点中的所有属性存储相应的连续正态分布。CLASSIT算法同样也不适合应用于数据量很大的数据集。AutoClass 聚类算法类的个数由贝叶斯统计分析来估算获得。SOM[9]（Self-Organizing Maps ）算法效仿人脑处理信号的特点开发出的一种人工神经网络聚类算法，该算法是可视的、高纬的、无监督的，在信息处理领域（如图像处理、语音识别等）应用的比较广。

4 结束语

本文分析了基于不同思想的各类聚类算法，用户应该根据实际应用中的具体问题具体分析，选择恰当的聚类算法。聚类算法具有非常广泛的应用，改进聚类算法或者开发新的聚类算法是一件非常有意义工作，相信在不久的将来，聚类算法将随着新技术的出现和应用的需求而得到蓬勃的发展。

参考文献：

[1]陈良维.数据挖掘中聚类算法研究[J].载《微计算机信息》，2006，21.

[2]Anil K.Jain.Data clustering：50 years beyond K-means[J].Parrern Recognition Letters.2009（31）

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

[4]胡庆林，叶念渝，朱明富.数据挖掘中聚类算法研究[J].载《计算机与数字工程》，2007，2.

[作者简介]

刘凤芹（1984- ），女，山东济南人，山东师范大学信息科学与工程学院硕士研究生，主要研究方向为算法复杂性理论、计算生物学。