基于数据挖掘的聚类算法研究综述文献综述

文献综述学生姓名： 学号： 专业：网络工程 班级： 文献综述题目：基于数据挖掘的聚类算法研究综述 引用文献：中文 7 篇；英文 7 篇； 其中期刊：10 种；专著 3 本；引用文献时间跨度： 1967 年 2015 年 指导教师审阅签名： 摘要： 现代社会是一个高速发展的社会，交通便利，信息流通，人与人之间的交流越来越密切，在这样一个环境下，数据也在爆炸式增长。为了从海量的数据中提取有价值的信息，数据挖掘应运而生。而聚类算法作为数据挖掘的重要工具之一，在生物学、商务和 WEB 文档分类等方面得到广泛的应用。本文就数据挖掘中的聚类算法展开讨论。首先总结了基于数据挖掘的聚类算法的研究的目的和意义、国内外研究现状，然后简要阐述并归纳了传统的聚类算法，最后分析了数据挖掘领域内聚类算法的新发展。Abstract: Modern society is a high-speed development of the society. The convenient transportation , the flowing information and the communication between people which is closer and closer are changing our lives. In such an environment, the data is also in the explosive growth. In order to extract valuable information from the vast amount of data, data mining emerges as the times require. Clustering algorithm, as one of the important tools of data mining, has been widely used in biology, business and WEB document classification. In this paper, we discuss the clustering algorithm in data mining. Firstly, we summarize the based on clustering algorithm of data mining research purpose and significance, the domestic and foreign research status. Then, we briefly analyzed and summarized the traditional clustering algorithm. Finally, the paper analyzes the new developments in the field of class clustering algorithm of data mining.关键词：数据挖掘；聚类算法；新发展引言：资料显示，目前每天全球互联网流量累计达 2.5EB。人们已经明显感受到了大数据的来势凶猛。大数据不是掌握的数据越多越好，大数据的任务应当是从海量的数据中挖掘出有用的信息。数据挖掘有很多方法，其中聚类方法是数据挖掘应用最多的方法之一，所以本文针对基于数据挖掘的聚类算法的研究状况进行总结。1.研究的目的和意义我国古时的一句名言“物以类聚，人以群分”就体现了聚类思想，随着科技不断进步，这一思想也被发扬光大。聚类分析就是将聚类对象按照一定的规则分类，在某一类内，所有的对象之间的差别较小，而在不同的类，聚类对象的差别就相对而言较大一些了。 1聚类算法的目的是寻找数据中潜在的自然分组结构，而聚类分析则是用已有的数学方法对所给的数据对象进行分类以及表示不同的类的相似度，是在数据不做任何假设时进行分析计算的工具，它是机器学习中获取知识的非常重要的步骤。通过聚类分析，人们可以将数据按照一定的规则分类，以便于挖掘出有用的信息。根据潜在的各种不同的业务需要，因而对聚类算法提出了各种要求，具体如下 2：（1）可伸缩性：很多算法当只有少量的数据对象时聚类效果很好，对于大数据集时就会产生不同的错误。（2）具有处理不同类型属性的能力：可以处理不同种类的数据，如数值型或非数值型、离散或连续域内的数据等。（3）能够发现任意形状的聚类：一般的聚类方法用欧式距离来衡量数据的相似度，但是这样的算法只能发现具有相似密度和尺度的球状簇，而这无法满足各种不同应用的需要，好的聚类算法应该能够有效而正确地发现任意形状的聚类。（4）对输入参数不依赖：在聚类分析中，有很多聚类算法需要用户输入一些参数，聚类结果却对输入的参数非常敏感，只要参数稍有变动，结果就大不相同。 （5）聚类结果对输入数据顺序的低敏感性：对于同一个数据集，只是改变了输入数据的顺序，用同一个算法进行聚类，聚类效果却有所不同，这在实际应用中是不应当存在的。（6）处理噪声和高维数据的能力：现实世界里，大部分的数据都不是完美的，可能有各种各样的问题，孤立点、空缺等，好的方法应当可以处理这样的数据。很多聚类算法只能处理低维的数据，但是对高维的数据对象进行聚类却是一件困难的任务。（7）基于约束的聚类：在现实世界里，可能有各种约束条件，好的聚类算法在满足约束条件的同时，还不能对原本的聚类效果产生太大的影响。2. 国内外研究现状数据挖掘技术诞生于20世纪80年代 3。1989年8月，在美国底特律召开的第11届国际人工智能联合会议上，专家们对数据库中知识发现(Knowledge Discovery in Databases,KDD)进行了专题讨论。1997年开始，KDD拥有了专刊Knowledge Discovery and Data Mining，上面发表了很多数据挖掘和知识发现方面的研究成果和论文。经过多年的发展，数据挖掘技术的日趋成熟，现在，它一直都是计算机研究领域的热点。目前，国外研究数据挖掘主要有Bayes方法和Boosting方法的研究与改进、知识发现与数据库的紧密结合等方面。在数据挖掘的应用方面，主要体现在知识发现商业软件工具已经变为了建立解决问题的整体系统而不是孤立过程，主要用户有保险公司、银行、大型超市等。数据挖掘的研究正在被越来越多的高校和科研单位所重视，相信在不远的将来，数据挖掘的研究成果可以给我们的生活带来便利 4。国内对数据挖掘技术的研究开始于1997年，上海的研究机构研究了数据挖掘在税务系统中的应用。在这以后，国内就开始有越来越多的高校和研究机构进行对数据挖掘学习算法和理论方面的研究。例如中国科技大学、中科院等研究机构进行了基于数据挖掘的关联规则开采算法的研究和改进、上海交大在web数据挖掘方面有了突破性进展等。聚类分析作为数据挖掘主要的研究课题之一，从知网上搜索到关于聚类的文章可以追溯到1957年，后来国内外提出的聚类算法有很多，但是其中最为经典主要有基于划分、层次、密度、网格、模型等5大类。在此基础上，针对一些聚类算法的缺陷又提出了许多改进方法。近年来，随着各种新方法和新技术不断地发展，聚类算法的研究也取得飞速的进展。3. 研究的主要问题：传统聚类算法的分类：（1）基于划分的聚类算法基于划分的聚类算法的基本思想是用反复迭代的方法将原来的 N 组数据集分为 K 类（KN） 。Macqueen5提出的 k-means 算法由于其算法简单实用，发展至今已经算的上是应用最为广泛，最为人所知的算法了，但是其也存在对 k 值、噪声和孤立点敏感的弊端。Kaufman 和 Roussseeuw 提出的PAM（Partitioning Around Medoid）和 CLARA （Clustering Large Applications）算法 6中，每个类用接近该类中心的对象来表示，因此称之为 k-中心点方法。PAM 和 CLARA 算法可以看做是 k-means 的改进，因为如果数据对象中出现极端数据，k-means 由于基于均值，聚类效果会大受其影响，而 PAM 和 CLARA 算法是基于中心点的，受的影响会大大减小。对于海量的数据对象或者处理比较复杂的聚类，基于划分的聚类算法就有了很多改进算法。Huang 提出的 k-模（k-modes）方法、Lauritzen 提出的 EM（Expectation Maximization）算法、Ng 和 Han 提出的 CLARANS（Clustering Large Application based upon Randomized Search）算法。（2）基于层次的聚类方法基于层次的聚类算法的基本思想是不断地分解输入的数据对象，直到满足某种特定的条件，而这种分解是层次性的，聚类结果将样本组成一棵聚类树。基于层次的聚类算法优点是聚类结果是不同粒度上的多层次结构，而缺点就是合并或分裂点难以选择、难以处理复杂的数据和算法运行花费的时间较高。基于层次的聚类算法中比较具有代表性的算法有 Zhang 提出的 BIRCH（Balanced Iterative Reducing and Clustering using Hierarchies）算法 7，Guha 提出的 CURE（Clustering Using Representatives）方法以及其在 CURE 方法的基础上，又提出的适用于分类数据的 ROCK 方法。（3）基于网格的聚类算法基于网格的聚类算法的基本思想是将数据空间划分为有限个单元的网格结构，以单个单元为对象进行数据处理。它的优点是处理数据的速度很快，其处理速度只与单元的数目有关，而缺点却是为了追求速度导致的聚类结果精确度不高。Wang 提 出 的 STING 方法 8、Sheikholeslami 等提出的 Wavecluster 算法以及 Yu Dantong 提出的一种改进的 Wavecluster 算法都是小波变换聚类问题，可处理图像数据聚类问题；Agrawal 等提出的 CLIQUE 算法可用于聚类高维数据。（4）基于密度的聚类算法基于密度的聚类方法的基本思想是以空间中的一个样本为中心，单位体积内样本个数称为该点的密度，如果密度近似于某个固定的阈值，则将其划分到该阈值的类内。它的优点是只要数据在某个形状内聚类，它就可以发现可以发现任意形状的聚类，而不仅仅像 KNN 算法那样局限于类圆形。而它也存在从样本集获得的密度图很不均匀，从而产生伪聚类和对参数敏感的缺点。代表算法有 Ester 等提出了的 DBSCAN 算法9、 Ankerst 等提出的基于类排序方法的 OPTICS 算法、 ； Hinneburg 提出的 DENCLUE 方法等。（5）基于模型的聚类方法基于模型的聚类方法的基本思想是为每一类假定一个模型，寻找数据对给定模型的最佳拟合。模型聚类方法主要有统计学方法和神经网络方法。统计学方法中常用方法有 Fisher 提出的 COBWEB，Gennari 等提出的 CLASSIT 等。神经网络方法中有 D.E.Rumelhart 提出的竞争学习、Kohonen 提出的学习矢量量化、Kohonen 提出的 SOM 算法等。其中 SOM 算法 10将高维空间的数据转化到二维空间，并且在二维空间很好的保持了输入数据的相似性。SOM 的优点有：可以实时学习、具有自稳定性和自学习性、抗噪音能力强。聚类算法的新发展：由于实际应用中会遇到不同的约束条件和各种各样的数据，每一种聚类算法都只能适用于某一种情况。为了能够让聚类算法能够适用于更多的领域，聚类算法需要不断创新和改进。由于近年来新发展的聚类分析方法众多，本文选择几种运用最为广泛的方法进行分析。（1）模糊聚类算法模糊聚类主要优点是可以处理现实世界中大量存在的属性界限不明的对象。目前，FCM 模糊聚类算法11是模糊聚类算法中最为人所知的算法。FCM 模糊聚类算法主要步骤就是设定完算法所需的各个参数后，对聚类中心进行初始化，然后循环迭代更新隶属度函数值的 3.1 式和更新各聚类中心的 3.2 式，直到 FCM算法收敛,算法结束。（3.1）cjnkmxclblktj ,.1,.1112（3.2）cjxnkbkj ,.211（2）核聚类算法一般聚类算法是否可靠非常依赖于不同的类之间的特征差别是否明显。现实世界里，经常会发生不同的类的差别微弱的情况，这样的话，一般聚类算法的聚类结果就不是很理想。SCHOLKOPF B 首先提出了核聚类算法，该算法 12通过把输入的数据对象利用 Mercer 核映射到高维特征空间，优化了样本的特征空间，从而增大了各类样本之间的差别，这样就可以实现对差别微弱的样本类的聚类。（3）谱聚类算法BUHMANN.J.M 提出了谱聚类算法，该类算法是建立在谱图理论的基础上的，它利用数据的相似矩阵的特征向量进行聚类，使算法只与数据点的个数有关，而与维数无关。该算法的优点在于思想简单、易于实现、不易陷入局部最优解，这些优点使得它适合许多应用问题。谱聚类算法 13将每一个数据对象都看做图的顶点 V,将顶点之间的相似度量化看做相应顶点连接边 E的权值，数据对象转化为了基于相似度的无向加权图 G（V,E）,只要将图按照相似度进行划分就可以得到聚类的结果，进而使图的内部的数据相似度最大，而图之间的相似度最低。总结：总之，基于数据挖掘的聚类算法正跟随时代的步伐，利用新技术和新思想不断发展，应用到越来越多的领域。本文除了比较翔实地阐述研究意义及目的、研究现状外，还对各种聚类算法的基本构想、优缺点及实现思路作了进一步地分析。但是，聚类算法 14虽然众多，但是每一种聚类算法都有其各自的适用范围，在实际应用中应根据实际情况选择最佳的聚类算法，这样才能取得最佳的聚类效果。 参考文献1.周涛，陆慧玲数据挖掘中聚类算法研究进展J计算机工程与应用，2014(12)：100-1112.毛国君，段立娟，王实，石云数据挖掘原理与算法M 北京：清华大学出版社，2009156-1823.Inmon WH Building the data warehouseM Third EditionNew York：John Wiley and Sons，2002：31-454.陕粉丽数据挖掘技术的研究现状及应用J现代企业教育，2015(6)：101-1025. MacQueen JSome methods for classification and analysis of multivariate observationsCProc of the 5thSymposium on Mathematical Statistics and Probability，Berkeley1967：281-2976.Kaufman L，Rousseeuw P JFinding groups in data：an introduction to cluster analysisMNew York：John Wiley & Sons，19907.Zhang T，Ramakrishnan R，Livny MBIRCH：an efficient data clustering method for very large databasesCProc 1996 ACM-SIGMOD Int Conf Management of Data，1996：103-1148.Wang W，Yang J，Muntz RSTING：a statistical information grid approach to spatial data miningCProc 1997Int Conf Very Large Data Bases，1997：186-195 9.倪巍伟，陈耿，吴英杰一种基于局部密度的分布式聚类挖掘算法J软件学报，2008，19（9）：2339-234810.Teuvo KThe self-organizing mapJNeurocomputing，1998，21（13）：1-611.MohamedNA modified fuzzy c-means algorithm for bias field estimation and segmentation of MRI dataJ IEEE Transactions on Medical Imaging2002，21 (3)：193-19912.张莉，周伟达，焦李成核聚类算法J计算机学报，2002，25（6）：587-59013. 王玲，薄列峰，焦李成密度敏感的谱聚类J电子学报，2007，35（8）：1577-158114. 孙吉贵，刘杰，赵连宇聚类算法研究J软件学报，2008，19（1）：48-61