数据挖掘常用聚类算法研究

1、数据挖掘常用聚类算法研究摘要：信息社会的发展，使数据量以前所未有的 速度在增长，因此从海量数据中获取有用的知识和信 息就变得越来越重要。数据挖掘是一种综合多领域知 识而形成的数据分析技术，能够从大量数据中获取有 价值的知识并为决策提供支持。聚类分析算法是数据 挖掘中的一个核心内容，也是目前研究的一个热点。 该文首先讲述了基于划分的聚类算法、基于分层的聚 类算法、基于密度的聚类算法和基于网格的聚类算法 等常用的聚类分析算法，并分析了其特点；然后通过 举例详细描述了最近邻聚类算法的操作过程。聚类算 法的总结，对聚类的研究和发展具有积极意义。关键词：数据挖掘；聚类；聚类算法；簇；核密 中图分类号：t

2、p18文献标识码：a文章编号:1009-3044 (2014) 16-3710-03abstract： the development of the information society make the amount of data growing at an unprecedented rate, and so to obtain useful knowledge from huge amounts of data and in format! on becomes more and more important. data mining is a data analysis techn

3、ique formed by integrating multi-domain knowledge, which can acquire valuable knowledge from large amounts of data and provide support for decision. clustering analysis algorithm in data mining is a core content, which is also a hotspot in the research of the current. this article first describes co

4、mmonly used clusteri ng algorithms that in elude the clusteri ng algorithm based on classification， the clustering algorithm based on hierarchies and the clustering algorithm based on density and the clustering algorithm based grid， and the n an a lyzes their characteristics the operation process of

5、 nearest neighbor clustering algorithm is illustrated in detail by an example the summary of the clustering algorithms has positive sigrdficance for the research and development of clusteri ng.key words： data mining； clustering； clusteringalgorithm； cluster；kernel density近年来，通信技术、计算机技术、信息技术的快速发展和不断完

6、善，使社会上每天产牛了大量的诸如 文本、音频、视频、图像等数据。面对这些海量数据， 如何从中找到有价值的知识和信息是目前研究者研究 的一个重要课题，数据挖掘技术在这种背景下应运而 生了。数据挖掘是从大量数据中提取或挖掘出潜在的、 有价值的、可理解的知识和规则的过程，并为用户决 策提供支持。作为一个应用驱动的领域，数据挖掘吸 纳了诸如统计学习、机器学习、模式识别、数据库和 数据仓库、信息检索、可视化、算法、高性能计算和 许多应用领域的大量技术。数据挖掘是一种新式的 具有一定深度的数据处理技术；聚类分析是一种重要 的分析数据的方法，是将物理的或抽象的对象集合分 成相似的对象类的过程，是人们发现事物

7、内在联系 的有效手段之一。划分后的对象类被称为簇，因此 聚类的结果是一个簇集，也称为一个聚类。聚类分析 的主要目标是在没有先验信息的前提下将样本空间中 的数据集按照某种度量标准划分成若干类，使得按照 这一标准在同一类中的个体尽可能相似而在不同类中 的个体有较大差异。聚类分析并没有对簇的数目和 结构做出事先的假定，因此它是一种无监督学习的方 法，其具体实现有不同的算法。1数据挖掘常用聚类算法简要介绍聚类分析是数据挖掘中占具着重要地位，它是在 数据对象没有类标号的情况下，把数据对象集划分成若干个簇，使得同一个簇内的数据对象高度相似，不 同簇间的数据对象高度相异。聚类分析技术在生物学、 商务智能和w

8、eb搜索等领域得到了广泛应用。到目前 为止出现了一些实现聚类分析的算法，其中比较常用 的有基于划分的聚类算法、基于层次的聚类算法、基 于密度的聚类算法和基于网格的聚类算法等。1）基于划分的聚类算法对于给定的n个对象集，将数据对象集划分成不 重叠的子集（簇），使得每个数据对象恰（只）在一个 子集中，每个子集中至少有一个数据对象。基于划分 的聚类算法将问题归结为一个优化问题，具有深厚的 泛函基础，是聚类算法研究的重要分支之一。k-均值聚类算法是基于划分的聚类算法中最著名、 最常用的算法之一，它的基本思路如下：对于给定的 指定一个质心（中心点）；然后，每个点被指派到最近 的质心，而指派到同一个质心的

9、点集形成一个簇。之 后，根据被指派到簇的点，更新每个簇的质心，重复 指派和更新过程，直到质心不再发生变化。k-均值算 法思想简单、局部搜索能力强，收敛速度快6；其簇 数k必须由用户指定。k-均值有以下局限性：a）当真 实簇的大小差异很大、密度变化很大或为非球形簇时,数据对象集d,通过参数k指定簇的数目,为每个簇k-均值很难找到真实存在的簇；b）当数据对象集包含 离群点时，k-均值存在问题；c） k-均值仅限于具有中 心（质心）概念的数据对象集。 2）基于层次的聚类算法层次聚类算法依据数据对象间的相似度做迭代性的层次分解。根据建立层次方向的不同，可以分为自 底向上的凝聚算法和自顶向下的分裂算法。

10、前者是首 先把每个对象作为一个群组，然后逐次合并当前最相 似的群组或对象，直到仅剩一个组群为止或满足终止 条件；后者是首先将所有对象放在一个群组中，然后 迭代执行：把一个簇划分为更小的簇，直到每个群组 中只有一个对象或满足终止条件为止。层次聚类算法 的优点是能够得到不同粒度上的多层次聚类结构。（1）最近邻聚类算法。首先把每个数据对象作为一个簇，然后迭代进行:计算当前所有簇中两两之间的相似性，把相似性最大的两个簇之间加一条链使之 合并成为一个更大的簇，重复进行，直到只剩下一个 簇为止。最近邻算法的优势是能够处理非椭圆形状的 簇，其局限性是对噪声和离群点比较敏感。（2）最远邻聚类算法。从所有数据对

11、象中每个对象作为一个簇开始，然后进行迭代：计算所有簇中两两之间的最大距离，然后从中选取距离最小的两个簇,在其间添加一条链形成一个更大的簇，重复操作直到 只剩下一个簇为止。最远邻近聚类算法的优势是对噪 声和离群点比较不敏感，其局限性是可能使较大的簇 破裂且偏好球形簇。3)基于密度的聚类算法基于密度的聚类算法中类簇被定义为连通的稠密 子区域，其主要思想是在数据点（数据对象）分布 中，高密度的区域被低密度的区域所分隔，将密度足 够高的区域划分成簇。这种算法的优点是不受噪声和 离群点的影响，并且可以发现任意形状的簇。dbscan是一种基于高密度连通区域的基于密度的聚类，在数据挖掘中是一个非常著名的聚类

12、算法。该算法的过程可以简单描述如下：首先将所有数据点 标记为核心点、边界点和噪声点；然后删除噪声点； 接着在所有核心点中，为其距离在给定邻域之内的核 心点之间加入一条边；然后每组连通的核心点形成一 个簇；最后将每个边界点指派到一个与之关联的核心 点的簇中。在dbscan算法中，需要确定邻域半径（eps） 和数据点个数的阈值（minpts）；该算法具有抗噪声和 能够发现任意形状的簇的优势，但同时也具有易受密 度变化的影响和不适应处理高维数据的缺点。denclue是一种基于密度分布函数的聚类算法， 具有坚实的数学基础。denclue的基本思想是核密度 函数通过使用个体数据对象影响之和对点集总密度建

13、 模。denclue算法的主要步骤：（1）推导出衡量数据 点占据空间的密度函数；（2）识别局部最大点（密度 吸引点）；（3）沿着密度增长最大的方向移动，将每个 点关联到一个密度吸引点；（4）得到与特定的密度吸 引点相关联的点构成的簇；（5）删去密度吸引点的密 度小于事先指定阈值的簇；（6）合并通过密度大于或等于噪声阈值叨的点路径连接的簇。denclue除了 具有和dbscan算法的特点外，提供了较dbscan更 加灵活、更加精确的计算密度的方法，可以适用于任 何复杂数据对象，是一种比较有效的基于核密度的聚 类算法。4）基于网格的聚类算法基于网格的聚类算法是一种比较新颖的釆用空间驱动的聚类算法，

14、把数据对象集划分为数目有限的单 元，创建网格单元的集合并形成一个网络结构；然后 由足够稠密的网格单元形成簇。该算法具有处理速度 快的优点，这是因为它的处理时间通常独立于数据对 象集，而只依赖于量化空间中每一维的单元数。sting是一种面向网格的多分辨率聚类算法，它 将数据点空间划分成矩形单元。这些矩形单元形成一个层次结构，并与不同级别的分辨率相对应。每个网 格单元的属性的统计信息被预先保存下来，被用于查 询处理或其它数据分析任务。网格结构的最底层的粒 度决定了 sting聚类的质量。sting算法除了具有处理速度快以外，还具有网格结构独立于查询、有利于 并行处理和增量更新等特点。2基于层次的聚

15、类算法实例基于层次的聚类算法是数据挖掘中最重要的聚类 算法之一，将需要处理的数据点组织成树状图的形式来表示聚类的结果。自底向上的层次聚类算法和自顶 向下的层次聚类算法是基于层次的聚类算法的两种形 式，其中前者又是比较常见的层次聚类算法。在自底 向上的层次聚类中，计算当前簇集中两个簇之间的距 离，然后将符合条件的两个簇合并为一个簇；重复上 述操作，直到仅剩一个簇为止。给出平面上的6个点，如表1所示。用最近邻聚类算法对其聚类,说明该算法的操作过程。最近邻聚类算法的操作过程如下:1)计算表1中6个点中两两之间的欧几里德距离,如表2所示。2)每一个点是一个簇，如图2中(al)所示;3)计算最近的两个簇

16、,将其合并为一个簇;4)若有两个分开的簇，则重复3),否则结束。3总结本文首先介绍了数据挖掘聚类技术中目前比较常 用的流行算法，并分析了这些算法的特点。然后描述t以最近邻聚类算法为代表的层次聚类算法的操作过程，并得到了聚类的结果一一树状图结构。聚类分析 发展前景。因此，可以对其做深入研究。算法经常应用在金融、教育等行业,具有较好的应用参考文献：1 jiawei han, micheline kamber, jian pei.数据挖 掘概念与技术m.范明，孟小峰，译北京：机械工业 出版社,2012： 288-314.2 潘晓英，刘芳，焦李成.密度敏感的多智能体 进化聚类算法j.软件学报,2010,21(10)： 2420-2431.3 梁群玲，肖人岳，王向东.一种改进的自适应 蚁群聚类算法j.计算机应用研究，2011, 28 (4)：1263-1265.4 周涛，陆惠玲.数据挖掘中聚类算法研究进展j.计算机工程与应用，2012, 48 (12)： 100-111.5