聚类综述 第5期

摘要：聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要计算。阐述了聚类算法的基本原理，应用方向等，总结了聚类算法的研究现状。

关键词：聚类 聚类分析

中图分类号：TP391 文献标识码：A 文章编号：1007-9416(2012)05-0204-02

1、引言

在对世界的分析和描述中，类或在概念上有意义的具有公共特性的对象组，扮演着重要的角色。的确，人类擅长将对象划分成组（聚类），并将特定的对象指派到这些组（分类）。利用聚类操作可以对数据进行分组和深入分析，获得其他方法不可能获得的信息。就理解数据而言，簇是潜在的类，而聚类分析是研究自动发现这些类的技术。

2、相关概念

聚类[1]:可以看作一种分类，是将物理或抽象对象的集合分成由类似的对象组成的多个类的过程。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。顾名思义是将一组对象划分为若干类，每个类中的对象相似度较高，类与类之间的对象相似度较差。

聚类分析[2]：根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是在相似的基础上收集数据来分类。它以相似性为基础，因此组内的相似性（同质性）越大，组间差别越大，聚类就越好，所分的类就越成功。

聚类分析的基本思想[3]：聚类分析是依据实验数据本身所具有的定性或定量的特征来对大量数据进行分组归类，以便了解数据集的内在结构，并且对每一个数据集进行描述的过程。其主要依据是用数学的方法研究和处理给定对象的分类，把一个没有类别标记的样本按照某种准则划分子类，使相似的样本尽可能归为一类。

3、聚类应用的四个基本方向[3]

减少数据：许多时候数据量n很大，会使处理变得很复杂费力，因此可将数据分成几组可判断的聚类m（m

假说生成：聚类算法依赖于猜测和假设，在这种情况下，为了推导出数据性质的一些假说，我们可对数据集进行聚类分析。这里使用聚类作为建立假说的方法，可使用其他数据集验证这些假说。

假说检验:在这种情况下，使用聚类分析来验证指定假说的有效性。例如，考虑下面的假说：“国内大公司都投资房地产”，验证这个假说是否正确的一种方法是对国内的大公司和有代表性的公司进行聚类分析。假定每个公司用它的规模、在房地产行业的活跃度以及应用研究上成功完成项目的能力来表示，在进行聚类分析后，如果相应于规模大并且能在房地产上投资的公司形成聚类，则聚类分析支持这个假说。

基于分组的预测：在这种情况下，我们对现有数据集进行聚类分析，形成模式的特征，并用特征表示聚类。如果给出一个未知模式，我们可以判定它最可能属于哪类，并用相应聚类的特征表示。

4、为了完成一个聚类任务，必须遵循下列步骤[3]

特征选择(feature selection)：必须选择合适的特征，尽可能多地包含任务关心的信息。在特征中，使信息冗长减少和最小化是主要目标。因为在有监督分类中，使用之前特征的预处理是必要的。

近邻测度(proximity measure)：用于定量测量两个特征向量如何“相似”或“不相似”。保证所有选中的特征具有相同的近邻行，并且没有占支配地位的特征，这是预处理期间必须要注意的一点。

聚类准则(clustering criterion)：聚类准则以蕴涵在数据集中的类型为基础。例如,L维空间的致密类特征向量可以根据一个准则判断，但是拉长类却需要另一个准则判断。聚类准则可以用代价函数或其他规则表示。

聚类算法(clustering algorithm)：已经采用近邻测度和聚类准则，这一步涉及到选择特定的算法，用于揭示数据集的聚类结构。

验证结果(validation of the results)：一旦用聚类算法得到结果，就必须验证其正确性。通常使用逼近检验。

结果判定（interpretation of the results）：在许多情况下，应用领域的专家必须用其他实验证据和分析判定聚类结果，最后做出正确的结论。

5、聚类分析计算方法主要有如下几种

划分法(partitioning methods)：给定一个有N个对象的数据集，利用分裂法构造K个分组，每个分组就代表一个聚类（K

层次法(hierarchical methods)：这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。根据层次分解的形成方式，该方法可分为“分解”和“合并”两种方案，并且经常与其他方法结合使用进行优化。代表算法有：BIRCH算法[7]、CURE算法等；

基于密度的方法(density-based methods)：基于密度的方法是根据密度完成对象的聚类。它是根据邻域对象的密度或者根据某种密度函数生成簇。与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这个方法的指导思想是，只要一个区域中的点的密度大过某个阀值，就把它加到与之相近的聚类中去。代表算法有：DBSCAN算法[9]、OPTICS算法[10]、ST-DBSCAN算法[11]等。

基于网格的方法(grid-based methods)：这种方法首先将数据空间量化为有限个单元的网格结构，然后利用网格结构完成聚类，所有的处理都是以单个的单元为对象的。它突出的优点就是处理速度很快，通常这与目标数据库中记录的个数无关，它只与把数据空间分为多少个单元有关。代表算法有：STING算法[12]、CLIQUE算法、WAVE-CLUSTER算法等。

基于模型的方法(model-based methods)：基于模型的方法给每一个聚类假定一个模型，并找出一个能适应相应模型的数据集。该方法试图优化给定的数据和某数学模型的拟合，这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的。通常有两种尝试方向：统计的方案和神经网络的方案。

6、聚类算法的现况

数据挖掘是近年来信息产业界非常热门的研究方向，聚类的用途很广泛，而聚类分析是数据挖掘中的核心技术。在商业上，聚类分析是细分市场的有效工具。虽然传统的聚类算法已经能比较成功的解决了低维数据的聚类问题，但是随着技术的进步使得数据库规模越来越大、复杂性越来越高，处理数据的工作越来越复杂，因此在处理许多问题时，现有的算法已无法处理和满足要求，特别是对于高维数据和大型数据的情况。高维数据聚类分析是聚类分析中一个非常活跃的领域，同时它也是一个具有挑战性的工作。目前，高维数据聚类分析在各个领域都有很广泛的应用，很多应用需要对包含大量特征项或者维数的对象进行分析，例如市场调查分析、信息安全、金融、娱乐、反恐等。

7、结语

本文介绍了一些聚类的基本知识，作为工具的聚类对数据的分组，从理论上学习掌握这部分知识，为下一步利用聚类知识作学习研究打下了基础。

参考文献

[1]Michalski R,Stepp R. Learning from Observation:Conceptual Clustering. Machine Learing.Spring-Verlag,1984.

[2]张明卫,刘莹,张斌,朱志良.一种基于概念的数据聚类模型.软件学报,Vol.20, No.9,September 2009：2387—2396.

[3]李晶皎,王爱侠等译.（希）西奥多里德斯 等著.电子工业出版社,2006.

[4]Han JW, Kamber M, Wrote; Fan M, Meng XF, Trans. Data Mining Concepts and Techniques. Beijing: China Machine Press, 2001.232-236 (in Chinese)

[5]N g, R. , Han, J. Efficient and effective cluster method fo r spatial data m ining. In: Bocca, J. , J arke, M. , Zanio lo, C. ,eds. P roceedings of the 20th International Conference of V ery L arge Data Bases. San F rancisco, CA: Mo rgan Kaufmann Publisher, 1994. 144～ 155.

[6]Ordonez C, Omiecinski E. FREM: Fast and robust EM clustering for large data sets. In: Kalpakis K, Goharian N, Grossman D, eds. Proc. of the 2002 ACM CIKM Int’l Conf. on Information and Knowledge Management. McLean: ACM Press, 2002. 590?599.

[7]Zhang T, Ramakrishnan R, Livny M. BIRCH: An efficient data clustering method for very large databases. In: Jagadish HV, Mumick IS, eds. Proc. of the 1996 ACM SIGMOD Int’l Conf. on Management of Data. Montreal: ACM Press, 1996. 103.114.