数据挖掘中聚类分析的研究综述

1、数据挖掘中聚类分析的研究综述0 引言数据挖掘，也称知识发现数据库（KDD）【1】，就是从实际的大量的、不完全的，含有噪声的数据中去提取出人们事先不知道的、隐含在其中的对人们有用的知识和信息的过程。数据挖掘经常被企业决策者利用，通过挖掘企业中存储的大量数据中的潜在的有价值的信息，从而帮助企业经营者做出正确的决策，为企业创造更多的利益。聚类技术作为数据挖掘的的重要技术之一，也更多的为人们认识和使用。本文分析了几种主要的聚类算法的优点及存在的问题，并指出K-Means【2】聚类技术在通信领域的绝对优势。1 聚类的定义聚类分析【3】仅根据在数据中发现的描述对象及其关系的信息，将数据对象分组。其目标是，

2、组内的对象相互之间是相关的，而不同组的对象是不相关的，组内相似度越大，组间差别度越大，聚内效果就越好。聚类分析技术作为强大的辅助工具在科学研究、社会服务、市场营销等多个领域发挥了巨大的作用。因此聚类分析技术研究也成为一个热点课题。2 聚类分析算法中的数据结构和数据类型2.1 数据结构 一般聚类分析中的数据用以下两种数据结构来表示：数据矩阵对象-属性结构组成了数据矩阵。它由n个对象组成，例如：人；用P个属性来描述每个对象，例如：身高、体重、出生日期等。可以使用nXP矩阵或关系表的形式来表示数据矩阵，如式（1）所示。 （1）相异度矩阵相异度矩阵是一个对象-对象结构。它包含n个对象互相之间差异。我们

3、一般用n X n矩阵来表示相异度矩阵，如式（2）所示。 （2）2.2 数据类型 在实际应用中，数据挖掘任务面对的更多的是非数值型数据对象以及复合数据类型，数据复杂且多样化，布尔类型、有序数据类型、分段数值变量、标称型变量、二元、序数型以及混合型组合变量和比例型变量等都是在数据挖掘中常常会遇到的数据类型变量。3 主要的聚类算法目前，在数据挖掘中聚类的算法主要可分为以下几种：划分算法、层次方法、基于密度的算法、基于模型的方法以及基于网格的方法。下面将详细列出几种算法，并予以简单的介绍和分析。3.1 划分方法 所谓划分方法就是将包含有n个数据对象的数据集合分为m个组，其中每个组都是一个聚类，从定义可

4、以看出，这种聚类要满足以下两点：每个分组至少要包含一个一个数据对象；每个数据对象只能归属在一个分组当中，不能出现一个数据对象同时归属几个分组的情况，使用反复迭代的方法进行分组效果会更佳。最终在计算时，使得每次改进后的分组方案较之前一次都更胜一筹，同一分组当中，各个数据对象越近越好，而一些部分的算法应用对于条件的限制可以适当放宽一些。在聚类算法中，k-平均（k-means）算法和k-中心点（k-medoids）算法是最重要的两种算法，除此之外的其他类型的划分方法都是在它们的基础上演化而来的。3.2 层次方法 层次聚类算法将数据集进行层次分解。分为自下向上凝聚的（agglomerative）层次聚

5、类和自上向下的分裂法（divisive）层次聚类两种。凝聚的层次聚类将每个数据对象单独分成一个组，再逐步合并分组达到终止函数的限制。分裂法层次聚类，先将所有数据对象放到一个分组中，然后再渐渐划分为小的分组，直到达到了某个终止条件。常用的层次聚类方法包括BIRCH，CURE，ROCK，Chameleon算法等。3.3 基于密度的方法 目前，对于非球形数据集的聚变来说，基于距离的算法是可行的，但对于其他类型的巨变则须另当别论。在基于密度的聚类算法中，密度代替了数据的相似性，根据数据对象的分布密度，将密度聚类分析算法及应用足够大的区域相连结，从而发现任意形状的簇。这类算法除了可以发现任意形状的簇，而

6、且能有效地起到消除噪声的作用。密度算法主要包括DBSCAN，OPTICS，DENCLUE等。3.4 基于网格的方法 所谓基于网格的聚类算法就是一种把量化的网格空间进行聚类的算法。一方面，这种算法可以提高计算效率；但另一方面这种算法很难检测到斜侧边界的聚类，只能针对垂直或水平的聚类。基于网格的聚类算法一般与数据集的大小不相关，而计算时间的复杂程度只决定于网格单元的数目，WaveCluster、STING、CLIQUE等都是常见的基于网格的聚类算法。3.5 基于模型的方法 所谓基于模型的算法就是一种通过给每个聚类设定模型并在此基础上进行数据集选择的计算方法。这类算法试图对给定数据和某些数学模型之间

7、的拟合进行优化。基于模型的聚类计算方法是以数据符合潜在的概率分布的假设前提为基础的，EM、神经网络、概念聚类等都是常见的基于模型的算法。3.6 聚类方法的比较 目前，聚类算法包含很多种，它们各不相同，有各自的特色：基于层次的算法适用于不同粒度上多层次的聚类结构；而基于密度的算法适用于形状任意、数目不确定的聚类，而且还能起到消除噪声的作用；基于模型的计算方法适用于已知数据分布的聚类；基于划分的算法在处理聚类个数固定的聚类上有着明显优势，而且它偏好球形的聚类；而基于网格的聚类有较强的计算优势。因此，在进行数据挖掘中聚类分析时，人们可以根据具体应用场景和实际需求选择最佳聚类方法。4 总结与展望随着科技的发展和信息量的成倍增长，聚类算法的研究和应用也越来越受到人们的关注。以通信企业为例，通信企业的客户量大，拥有海量的通信数据，聚类算法中的K-Means算法恰恰是一种高效的可伸缩的算法，它在处理大数据量尤其是海量数据时有着明显的优势，而且聚类的质量相对较好。K-Means算法效果主要受下列几个因素的影响：选择初始凝聚点；聚类个数K的设定；变量值的标准化及距离选择；异常值处理；变量的相关性；优化准则。参考文献：【1】李丹丹.数据挖掘技术及其发展趋势.电脑应用技术，2007（69）：38-41.【2】CLIFTON CHRISTOPHER W