关于数据挖掘中聚类分析的研究进展

刘俊 刘希玉

山东师范大学管理与经济学院 山东 250014

0 引言

随着信息技术的飞速发展以及信息获取的便利，人们已被大量的信息淹没。如何从信息的海洋中提取出人们感兴趣的知识，以帮助人们完成特定的任务成为了一个迫切需要解决的问题，基于这样一种需求，用来帮助用户从这些海量数据中分析出其间所蕴涵的有价值的模式和知识的技术——数据挖掘就应运而生了。

所谓数据挖掘，就是从大量的、不完全的、有噪声的、模糊的、随机的、无序的数据中提取隐含在其中的有效的、有价值的、可理解的模式，进而发现有用的或是潜在有用的知识，并得出时间的趋向和关联，为用户提供问题求解层次的决策支持能力。

聚类分析是数据挖掘中一种很重要的技术。所谓聚类，就是把拥有大量数据的集合分成若干簇，在同一个簇中的数据对象之间最大程度的相似，而在不同簇中的数据对象之间具有最大程度的不同。在实际应用中，一个聚类结果会影响到数据挖掘的后续工作，通常一个好的聚类结果会使数据分析工作变得简单清晰，比较容易得到用户想要的知识，而一个糟糕的聚类结果却正好相反，甚至得不到用户想要的结果。因此聚类分析成了数据挖掘中的最为关键的部分，发展成为一个很活跃的研究方向。

1 对聚类分析研究成果的概述

对于数据挖掘中聚类分析的传统方法，根据其基本的思想，可以分成以下几类：划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法。

（1）划分方法

划分方法的基本思想是：给定具有N个对象或元组的数据库，指明想要得到的簇的数目k，一个划分方法利用采取的算法将这N个对象划分成k个分组，其中k

K-means方法：在具有n个对象的数据集中，随机选择k个对象，每个对象初始的代表一个簇的中心，根据所采用的距离度量（如欧几里得距离度量）计算剩余的每个对象与这k个初始簇中心点的距离，将对象分配到与其具有最小距离的簇中，这样具有n个对象的数据集被划分成k个簇，然后重新计算每个簇的平均值。该过程不断的循环迭代，直到新计算的平均值与上一次的平均值相比没有变化。

从该方法的过程可以看出，当结果簇间具有明显的区别时，k-means方法具有很好的效果，但是当存在孤立点时，孤立点对k-means方法会产生很大的影响，因为平均值对孤立点很敏感。另外，k-means方法需要事先指定聚类的数目。

K-medoids方法与k-means方法的过程类似，只是该方法用簇中一个实际的对象代替簇的平均值，所以相比较k-means方法而言，其不易受孤立点的影响。但是该方法要进行不断的对比和比较，其计算代价很高，而且不太适合于大型数据集。K-medoids方法需要事先指定要得到的簇的数目。

k-means方法和k-medoids方法是目前最为流行的聚类方法，当前发展的许多聚类技术都是在这两种方法的基础上进行拓展（如模糊k-means聚类方法），以及在这两种方法的基础上进行的改进。

（2）层次方法

层次聚类方法通过将数据组织成若干组并形成一个相应的树状图来进行聚类。根据其聚类的过程是自下而上还是自上而下，层次聚类方法又分成了聚合聚类和分解聚类两种。其主要思想如下：

聚合聚类方法：将数据集中的每一个对象看作是一个单独的簇，然后根据某个给定的原则将这些簇进行合并，直到数据集中的对象形成一个簇或者是满足事先定义的某个终止条件。

分解聚类方法：与聚合聚类方法恰好相反，将所有的数据集看成是一个大的聚类，根据某个给定的规则对这个簇进行划分，细化成越来越小的簇，直到每个数据对象自成一个簇或者达到某个终止条件。

几种典型的层次方法有BIRCH，CURE等。

BIRCH方法是一种综合性的层次聚类算法，它利用聚类特征（CF）和聚类特征树（CF tree）来描述聚类过程。CF是一个三元组，它对对象子类的信息给出了总结性描述；一个CF tree是高度平衡的树，它有两个参数：分支因子和阈值，它存储了层次聚类的聚类特征。分支因子定义为每个非叶节点孩子的最大数目，而阈值是指存储在树的叶子节点中的子聚类的最大直径。

BIRCH方法由于采用了CF tree汇总一个类的有关信息，从而使一个类可以用对应的CF表示，而不必用具体的一组数据点表示，因此大大提高了聚类算法对大型数据库的高效性和可扩展性，具有良好的聚类质量。但该方法又受到了CF tree节点大小的限制，CF tree节点并不总是与用户所认为的自然聚类相对应。而且，如果簇不是球形，BIRCH算法则不能很好地工作。

CURE采用了一种新的层次聚类方法，对k-means方法和k-medoids方法进行了折中，选择了位于基于质心和基于代表对象方法之间的中间策略。由于CURE方法选择数据空间中一定数目的具有代表性的点来代表一个簇，因此该方法可以识别复杂形状和大小不同的簇，而且能很好地过滤孤立点。然而该方法对用户输入的参数（如样本大小、收缩因子a）具有敏感性，同时也需要用户事先指明想要得到的聚类的数目。

（3）基于密度的方法

对于非球形的簇，用对象之间的距离来度量相似性是不够的，因此为了发现任意形状的簇，利用密度（数据或对象点的数目）来代替距离，提出了基于密度的聚类方法。该方法从数据对象的分布密度出发，将簇看成是由低密度区域分割开的高密度对象区域。

DBSCAN是一种典型的基于密度的方法，它通过检查数据库中每个点的e邻域来进行聚类。其基本思想：检查一个对象p的e邻域的密度是否足够高，即一定距离e内数据点的个数是否超过临界值minpts（minpts由用户事先指定），如果p的e邻域内的数据个数多于minpts个点，则创建一个以p为中心点的新簇。然后DBSCAN反复的寻找从这些中心点直接密度可达的对象并将其添加到簇中，当没有新的对象可以添加到任何簇中时，该过程结束。

DBSCAN用对象或数据点的数目表示类的密度，利用密度可达性来进行聚类，因此能很好的处理噪声，此外该方法能发现空间数据库中任意形状的密度连通集，对数据的输入顺序也不太敏感。但是该方法中使用的e邻域和阈值需要事先指定，参数的设置依赖于具体的应用。

（4）基于网格的方法

该方法采用一个多分辨率的网格数据结构，它首先将数据空间划分成有限数目的单元，形成一个网格结构，所有的处理都是以单个的单元为对象。处理速度通常与目标数据库中记录的个数无关，它只与单元的个数有关，故这种方法的一个突出优点就是处理速度很快。代表性算法有STING。

STING算法将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。高层单元的统计参数可以很容易地从低层单元的计算得到。

STING的执行效率比较高，而且利于并行处理和增量更新。但是如果数据粒度比较细，算法处理的代价会明显的增加；而且该算法没有考虑子单元和其他相邻单元之间的关系，尽管该算法处理速度较快，但是可能会降低簇的质量和精确性。

（5）基于模型的方法

基于模型的方法为每个簇都假定了一个模型，并寻找数据对给定模型的最佳拟合。该方法通过构建反映数据点空间分布的密度函数来实现聚类。这种聚类方法试图优化给定的数据和某些数学模型之间的适应性。

人工神经网络就是一种基于模型的聚类方法，是模拟生物神经网络的结构和功能而设计的一种信息处理系统。人工神经网络方法将每个簇描述为一个标本，标本作为簇的原型，不一定对应特定的数据实例和对象。根据某些距离度量，新的对象可以被分配给标本与其最相似的簇。被分配给一个簇的对象的属性可以根据该簇的标本的属性来预测。

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

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

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

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

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

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

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

3 总结与展望

通过以上的分析可以看出，目前对于聚类的研究虽然成果很多，但是还不够成熟，基本的理论方法还不够完善，对实际的应用也还不够广泛，还需要对其作进一步的研究：

（1）继续进行理论上的研究，寻求在理论上的改进和完善，提高各种方法的性能以及对现实数据的应用能力。

（2）寻求与其他学科的结合，寻找各学科之间的接口，完善现有的方法；并从其他学科获得一些启发，提出一些新方法，比如可以从代数拓扑中有关拓扑空间同伦等价的概念来研究聚类分析。

（3）增强聚类分析的应用能力，将其更广泛的应用于实践，为我们的生产生活提供便利，真正发挥其效能。

[1]贺玲，吴玲达，蔡益朝.数据挖掘中的聚类算法综述[J].计算机应用研究.2007.

[2]胡庆林，叶念渝，朱明富.数据挖掘中聚类算法的综述[J].计算机与数字工程.2007.

[3]Jiawei Han，Micheline Kamber.Data Mining:Concepts and Techniques[M].机械工业出版社.2007.

[4]邹志文，朱金伟.数据挖掘算法研究与综述[J].计算机工程与设计.2005.