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

赵学武　刘向娇　尹孟洋

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

关键词：数据挖掘；聚类；聚类算法；簇；核密度

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2014）16-3710-03

Abstract：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 information becomes more and more important. Data mining is a data analysis technique 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 commonly used clustering algorithms that include the clustering algorithm based on classification， the clustering algorithm based on hierarchies and the clustering algorithm based on density and the clustering algorithm based grid， and then analyzes their characteristics. The operation process of nearest neighbor clustering algorithm is illustrated in detail by an example. The summary of the clustering algorithms has positive significance for the research and development of clustering.

Key words： data mining； clustering； clustering algorithm； cluster； kernel density

近年来，通信技术、计算机技术、信息技术的快速发展和不断完善，使社会上每天产生了大量的诸如文本、音频、视频、图像等数据。面对这些海量数据，如何从中找到有价值的知识和信息是目前研究者研究的一个重要课题，数据挖掘技术在这种背景下应运而生了。数据挖掘是从大量数据中提取或挖掘出潜在的、有价值的、可理解的知识和规则的过程，并为用户决策提供支持。作为一个应用驱动的领域，数据挖掘吸纳了诸如统计学习、机器学习、模式识别、数据库和数据仓库、信息检索、可视化、算法、高性能计算和许多应用领域的大量技术[1]。数据挖掘是一种新式的具有一定深度的数据处理技术；聚类分析是一种重要的分析数据的方法，是将物理的或抽象的对象集合分成相似的对象类的过程[2]，是人们发现事物内在联系的有效手段之一[3]。划分后的对象类被称为簇，因此聚类的结果是一个簇集，也称为一个聚类。聚类分析的主要目标是在没有先验信息的前提下将样本空间中的数据集按照某种度量标准划分成若干类，使得按照这一标准在同一类中的个体尽可能相似而在不同类中的个体有较大差异[4]。聚类分析并没有对簇的数目和结构做出事先的假定，因此它是一种无监督学习的方法，其具体实现有不同的算法。

1 数据挖掘常用聚类算法简要介绍

聚类分析是数据挖掘中占具着重要地位，它是在数据对象没有类标号的情况下，把数据对象集划分成若干个簇，使得同一个簇内的数据对象高度相似，不同簇间的数据对象高度相异。聚类分析技术在生物学、商务智能和Web搜索等领域得到了广泛应用。到目前为止出现了一些实现聚类分析的算法，其中比较常用的有基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法和基于网格的聚类算法等。

1）基于划分的聚类算法

对于给定的n个对象集，将数据对象集划分成不重叠的子集（簇），使得每个数据对象恰（只）在一个子集中，每个子集中至少有一个数据对象。基于划分的聚类算法将问题归结为一个优化问题，具有深厚的泛函基础，是聚类算法研究的重要分支之一[5]。

K-均值聚类算法是基于划分的聚类算法中最著名、最常用的算法之一，它的基本思路如下：对于给定的数据对象集D，通过参数K指定簇的数目，为每个簇指定一个质心 （中心点）；然后，每个点被指派到最近的质心，而指派到同一个质心的点集形成一个簇。之后，根据被指派到簇的点，更新每个簇的质心，重复指派和更新过程，直到质心不再发生变化。K-均值算法思想简单、局部搜索能力强，收敛速度快[6]；其簇数K必须由用户指定。K-均值有以下局限性：a）当真实簇的大小差异很大、密度变化很大或为非球形簇时，K-均值很难找到真实存在的簇；b）当数据对象集包含离群点时，K-均值存在问题；c）K-均值仅限于具有中心（质心）概念的数据对象集。endprint

2）基于层次的聚类算法

层次聚类算法依据数据对象间的相似度做迭代性的层次分解。根据建立层次方向的不同，可以分为自底向上的凝聚算法和自顶向下的分裂算法。前者是首先把每个对象作为一个群组，然后逐次合并当前最相似的群组或对象，直到仅剩一个组群为止或满足终止条件；后者是首先将所有对象放在一个群组中，然后迭代执行：把一个簇划分为更小的簇，直到每个群组中只有一个对象或满足终止条件为止。层次聚类算法的优点是能够得到不同粒度上的多层次聚类结构[7]。

（1） 最近邻聚类算法。首先把每个数据对象作为一个簇，然后迭代进行：计算当前所有簇中两两之间的相似性，把相似性最大的两个簇之间加一条链使之合并成为一个更大的簇，重复进行，直到只剩下一个簇为止。最近邻算法的优势是能够处理非椭圆形状的簇，其局限性是对噪声和离群点比较敏感。

（2） 最远邻聚类算法。从所有数据对象中每个对象作为一个簇开始，然后进行迭代：计算所有簇中两两之间的最大距离，然后从中选取距离最小的两个簇，在其间添加一条链形成一个更大的簇，重复操作直到只剩下一个簇为止。最远邻近聚类算法的优势是对噪声和离群点比较不敏感，其局限性是可能使较大的簇破裂且偏好球形簇。

3）基于密度的聚类算法

基于密度的聚类算法中类簇被定义为连通的稠密子区域[8]，其主要思想是在数据点（数据对象）分布中，高密度的区域被低密度的区域所分隔，将密度足够高的区域划分成簇。这种算法的优点是不受噪声和离群点的影响，并且可以发现任意形状的簇。

DBSCAN是一种基于高密度连通区域的基于密度的聚类[1]，在数据挖掘中是一个非常著名的聚类算法。该算法的过程可以简单描述如下：首先将所有数据点标记为核心点、边界点和噪声点；然后删除噪声点；接着在所有核心点中，为其距离在给定邻域之内的核心点之间加入一条边；然后每组连通的核心点形成一个簇；最后将每个边界点指派到一个与之关联的核心点的簇中。在DBSCAN算法中，需要确定邻域半径（Eps）和数据点个数的阈值（MinPts）；该算法具有抗噪声和能够发现任意形状的簇的优势，但同时也具有易受密度变化的影响和不适应处理高维数据的缺点。

DENCLUE是一种基于密度分布函数的聚类算法，具有坚实的数学基础。DENCLUE的基本思想是核密度函数通过使用个体数据对象影响之和对点集总密度建模。DENCLUE算法的主要步骤：（1）推导出衡量数据点占据空间的密度函数；（2）识别局部最大点（密度吸引点）；（3）沿着密度增长最大的方向移动，将每个点关联到一个密度吸引点；（4）得到与特定的密度吸引点相关联的点构成的簇；（5）删去密度吸引点的密度小于事先指定阈值的簇；（6）合并通过密度大于或等于噪声阈值[ξ]的点路径连接的簇。DENCLUE除了具有和DBSCAN算法的特点外，提供了较DBSCAN更加灵活、更加精确的计算密度的方法，可以适用于任何复杂数据对象，是一种比较有效的基于核密度的聚类算法。

4）基于网格的聚类算法

基于网格的聚类算法是一种比较新颖的采用空间驱动的聚类算法，把数据对象集划分为数目有限的单元，创建网格单元的集合并形成一个网络结构；然后由足够稠密的网格单元形成簇。该算法具有处理速度快的优点，这是因为它的处理时间通常独立于数据对象集，而只依赖于量化空间中每一维的单元数。

STING是一种面向网格的多分辨率聚类算法，它将数据点空间划分成矩形单元。这些矩形单元形成一个层次结构，并与不同级别的分辨率相对应。每个网格单元的属性的统计信息被预先保存下来，被用于查询处理或其它数据分析任务。网格结构的最底层的粒度决定了STING聚类的质量。STING算法除了具有处理速度快以外，还具有网格结构独立于查询、有利于并行处理和增量更新等特点。

2 基于层次的聚类算法实例

基于层次的聚类算法是数据挖掘中最重要的聚类算法之一，将需要处理的数据点组织成树状图的形式来表示聚类的结果。自底向上的层次聚类算法和自顶向下的层次聚类算法是基于层次的聚类算法的两种形式，其中前者又是比较常见的层次聚类算法。在自底向上的层次聚类中，计算当前簇集中两个簇之间的距离，然后将符合条件的两个簇合并为一个簇；重复上述操作，直到仅剩一个簇为止。

给出平面上的6个点，如表1所示。用最近邻聚类算法对其聚类，说明该算法的操作过程。最近邻聚类算法的操作过程如下：

1） 计算表1中6个点中两两之间的欧几里德距离，如表2所示。

2） 每一个点是一个簇，如图2中（a1）所示；

3） 计算最近的两个簇，将其合并为一个簇；

4） 若有两个分开的簇，则重复3），否则结束。

3 总结

本文首先介绍了数据挖掘聚类技术中目前比较常用的流行算法，并分析了这些算法的特点。然后描述了以最近邻聚类算法为代表的层次聚类算法的操作过程，并得到了聚类的结果——树状图结构。聚类分析算法经常应用在金融、教育等行业，具有较好的应用发展前景。因此，可以对其做深入研究。

参考文献：

[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] 雷小锋，何涛，李奎儒，等.面向结构稳定性的分裂-合并聚类算法[J].计算机科学，2010，37（11）：217-222.

[6] 曹永春，邵亚斌，田双亮，蔡正琦.一种基于免疫遗传算法的聚类方法[J].广西师范大学学报：自然科学版，2013，31（3）：59-64.

[7] 王永贵，林琳，刘宪国.结合双粒子和K-means的混合文本聚类算法[J].计算机应用研究， 2014，31（2）：364-368.

[8] 刘雷，王洪国，邵增珍，等.一种基于峰群原理的划分聚类算法[J].计算机应用研究， 2011，28（5）：1699-1702.endprint

2）基于层次的聚类算法

层次聚类算法依据数据对象间的相似度做迭代性的层次分解。根据建立层次方向的不同，可以分为自底向上的凝聚算法和自顶向下的分裂算法。前者是首先把每个对象作为一个群组，然后逐次合并当前最相似的群组或对象，直到仅剩一个组群为止或满足终止条件；后者是首先将所有对象放在一个群组中，然后迭代执行：把一个簇划分为更小的簇，直到每个群组中只有一个对象或满足终止条件为止。层次聚类算法的优点是能够得到不同粒度上的多层次聚类结构[7]。

（1） 最近邻聚类算法。首先把每个数据对象作为一个簇，然后迭代进行：计算当前所有簇中两两之间的相似性，把相似性最大的两个簇之间加一条链使之合并成为一个更大的簇，重复进行，直到只剩下一个簇为止。最近邻算法的优势是能够处理非椭圆形状的簇，其局限性是对噪声和离群点比较敏感。

（2） 最远邻聚类算法。从所有数据对象中每个对象作为一个簇开始，然后进行迭代：计算所有簇中两两之间的最大距离，然后从中选取距离最小的两个簇，在其间添加一条链形成一个更大的簇，重复操作直到只剩下一个簇为止。最远邻近聚类算法的优势是对噪声和离群点比较不敏感，其局限性是可能使较大的簇破裂且偏好球形簇。

3）基于密度的聚类算法

基于密度的聚类算法中类簇被定义为连通的稠密子区域[8]，其主要思想是在数据点（数据对象）分布中，高密度的区域被低密度的区域所分隔，将密度足够高的区域划分成簇。这种算法的优点是不受噪声和离群点的影响，并且可以发现任意形状的簇。

DBSCAN是一种基于高密度连通区域的基于密度的聚类[1]，在数据挖掘中是一个非常著名的聚类算法。该算法的过程可以简单描述如下：首先将所有数据点标记为核心点、边界点和噪声点；然后删除噪声点；接着在所有核心点中，为其距离在给定邻域之内的核心点之间加入一条边；然后每组连通的核心点形成一个簇；最后将每个边界点指派到一个与之关联的核心点的簇中。在DBSCAN算法中，需要确定邻域半径（Eps）和数据点个数的阈值（MinPts）；该算法具有抗噪声和能够发现任意形状的簇的优势，但同时也具有易受密度变化的影响和不适应处理高维数据的缺点。

DENCLUE是一种基于密度分布函数的聚类算法，具有坚实的数学基础。DENCLUE的基本思想是核密度函数通过使用个体数据对象影响之和对点集总密度建模。DENCLUE算法的主要步骤：（1）推导出衡量数据点占据空间的密度函数；（2）识别局部最大点（密度吸引点）；（3）沿着密度增长最大的方向移动，将每个点关联到一个密度吸引点；（4）得到与特定的密度吸引点相关联的点构成的簇；（5）删去密度吸引点的密度小于事先指定阈值的簇；（6）合并通过密度大于或等于噪声阈值[ξ]的点路径连接的簇。DENCLUE除了具有和DBSCAN算法的特点外，提供了较DBSCAN更加灵活、更加精确的计算密度的方法，可以适用于任何复杂数据对象，是一种比较有效的基于核密度的聚类算法。

4）基于网格的聚类算法

基于网格的聚类算法是一种比较新颖的采用空间驱动的聚类算法，把数据对象集划分为数目有限的单元，创建网格单元的集合并形成一个网络结构；然后由足够稠密的网格单元形成簇。该算法具有处理速度快的优点，这是因为它的处理时间通常独立于数据对象集，而只依赖于量化空间中每一维的单元数。

STING是一种面向网格的多分辨率聚类算法，它将数据点空间划分成矩形单元。这些矩形单元形成一个层次结构，并与不同级别的分辨率相对应。每个网格单元的属性的统计信息被预先保存下来，被用于查询处理或其它数据分析任务。网格结构的最底层的粒度决定了STING聚类的质量。STING算法除了具有处理速度快以外，还具有网格结构独立于查询、有利于并行处理和增量更新等特点。

2 基于层次的聚类算法实例

基于层次的聚类算法是数据挖掘中最重要的聚类算法之一，将需要处理的数据点组织成树状图的形式来表示聚类的结果。自底向上的层次聚类算法和自顶向下的层次聚类算法是基于层次的聚类算法的两种形式，其中前者又是比较常见的层次聚类算法。在自底向上的层次聚类中，计算当前簇集中两个簇之间的距离，然后将符合条件的两个簇合并为一个簇；重复上述操作，直到仅剩一个簇为止。

给出平面上的6个点，如表1所示。用最近邻聚类算法对其聚类，说明该算法的操作过程。最近邻聚类算法的操作过程如下：

1） 计算表1中6个点中两两之间的欧几里德距离，如表2所示。

2） 每一个点是一个簇，如图2中（a1）所示；

3） 计算最近的两个簇，将其合并为一个簇；

4） 若有两个分开的簇，则重复3），否则结束。

3 总结

本文首先介绍了数据挖掘聚类技术中目前比较常用的流行算法，并分析了这些算法的特点。然后描述了以最近邻聚类算法为代表的层次聚类算法的操作过程，并得到了聚类的结果——树状图结构。聚类分析算法经常应用在金融、教育等行业，具有较好的应用发展前景。因此，可以对其做深入研究。

参考文献：

[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] 雷小锋，何涛，李奎儒，等.面向结构稳定性的分裂-合并聚类算法[J].计算机科学，2010，37（11）：217-222.

[6] 曹永春，邵亚斌，田双亮，蔡正琦.一种基于免疫遗传算法的聚类方法[J].广西师范大学学报：自然科学版，2013，31（3）：59-64.

[7] 王永贵，林琳，刘宪国.结合双粒子和K-means的混合文本聚类算法[J].计算机应用研究， 2014，31（2）：364-368.

[8] 刘雷，王洪国，邵增珍，等.一种基于峰群原理的划分聚类算法[J].计算机应用研究， 2011，28（5）：1699-1702.endprint

2）基于层次的聚类算法

层次聚类算法依据数据对象间的相似度做迭代性的层次分解。根据建立层次方向的不同，可以分为自底向上的凝聚算法和自顶向下的分裂算法。前者是首先把每个对象作为一个群组，然后逐次合并当前最相似的群组或对象，直到仅剩一个组群为止或满足终止条件；后者是首先将所有对象放在一个群组中，然后迭代执行：把一个簇划分为更小的簇，直到每个群组中只有一个对象或满足终止条件为止。层次聚类算法的优点是能够得到不同粒度上的多层次聚类结构[7]。

（1） 最近邻聚类算法。首先把每个数据对象作为一个簇，然后迭代进行：计算当前所有簇中两两之间的相似性，把相似性最大的两个簇之间加一条链使之合并成为一个更大的簇，重复进行，直到只剩下一个簇为止。最近邻算法的优势是能够处理非椭圆形状的簇，其局限性是对噪声和离群点比较敏感。

（2） 最远邻聚类算法。从所有数据对象中每个对象作为一个簇开始，然后进行迭代：计算所有簇中两两之间的最大距离，然后从中选取距离最小的两个簇，在其间添加一条链形成一个更大的簇，重复操作直到只剩下一个簇为止。最远邻近聚类算法的优势是对噪声和离群点比较不敏感，其局限性是可能使较大的簇破裂且偏好球形簇。

3）基于密度的聚类算法

基于密度的聚类算法中类簇被定义为连通的稠密子区域[8]，其主要思想是在数据点（数据对象）分布中，高密度的区域被低密度的区域所分隔，将密度足够高的区域划分成簇。这种算法的优点是不受噪声和离群点的影响，并且可以发现任意形状的簇。

DBSCAN是一种基于高密度连通区域的基于密度的聚类[1]，在数据挖掘中是一个非常著名的聚类算法。该算法的过程可以简单描述如下：首先将所有数据点标记为核心点、边界点和噪声点；然后删除噪声点；接着在所有核心点中，为其距离在给定邻域之内的核心点之间加入一条边；然后每组连通的核心点形成一个簇；最后将每个边界点指派到一个与之关联的核心点的簇中。在DBSCAN算法中，需要确定邻域半径（Eps）和数据点个数的阈值（MinPts）；该算法具有抗噪声和能够发现任意形状的簇的优势，但同时也具有易受密度变化的影响和不适应处理高维数据的缺点。

DENCLUE是一种基于密度分布函数的聚类算法，具有坚实的数学基础。DENCLUE的基本思想是核密度函数通过使用个体数据对象影响之和对点集总密度建模。DENCLUE算法的主要步骤：（1）推导出衡量数据点占据空间的密度函数；（2）识别局部最大点（密度吸引点）；（3）沿着密度增长最大的方向移动，将每个点关联到一个密度吸引点；（4）得到与特定的密度吸引点相关联的点构成的簇；（5）删去密度吸引点的密度小于事先指定阈值的簇；（6）合并通过密度大于或等于噪声阈值[ξ]的点路径连接的簇。DENCLUE除了具有和DBSCAN算法的特点外，提供了较DBSCAN更加灵活、更加精确的计算密度的方法，可以适用于任何复杂数据对象，是一种比较有效的基于核密度的聚类算法。

4）基于网格的聚类算法

基于网格的聚类算法是一种比较新颖的采用空间驱动的聚类算法，把数据对象集划分为数目有限的单元，创建网格单元的集合并形成一个网络结构；然后由足够稠密的网格单元形成簇。该算法具有处理速度快的优点，这是因为它的处理时间通常独立于数据对象集，而只依赖于量化空间中每一维的单元数。

STING是一种面向网格的多分辨率聚类算法，它将数据点空间划分成矩形单元。这些矩形单元形成一个层次结构，并与不同级别的分辨率相对应。每个网格单元的属性的统计信息被预先保存下来，被用于查询处理或其它数据分析任务。网格结构的最底层的粒度决定了STING聚类的质量。STING算法除了具有处理速度快以外，还具有网格结构独立于查询、有利于并行处理和增量更新等特点。

2 基于层次的聚类算法实例

基于层次的聚类算法是数据挖掘中最重要的聚类算法之一，将需要处理的数据点组织成树状图的形式来表示聚类的结果。自底向上的层次聚类算法和自顶向下的层次聚类算法是基于层次的聚类算法的两种形式，其中前者又是比较常见的层次聚类算法。在自底向上的层次聚类中，计算当前簇集中两个簇之间的距离，然后将符合条件的两个簇合并为一个簇；重复上述操作，直到仅剩一个簇为止。

给出平面上的6个点，如表1所示。用最近邻聚类算法对其聚类，说明该算法的操作过程。最近邻聚类算法的操作过程如下：

1） 计算表1中6个点中两两之间的欧几里德距离，如表2所示。

2） 每一个点是一个簇，如图2中（a1）所示；

3） 计算最近的两个簇，将其合并为一个簇；

4） 若有两个分开的簇，则重复3），否则结束。

3 总结

本文首先介绍了数据挖掘聚类技术中目前比较常用的流行算法，并分析了这些算法的特点。然后描述了以最近邻聚类算法为代表的层次聚类算法的操作过程，并得到了聚类的结果——树状图结构。聚类分析算法经常应用在金融、教育等行业，具有较好的应用发展前景。因此，可以对其做深入研究。

参考文献：

[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] 雷小锋，何涛，李奎儒，等.面向结构稳定性的分裂-合并聚类算法[J].计算机科学，2010，37（11）：217-222.

[6] 曹永春，邵亚斌，田双亮，蔡正琦.一种基于免疫遗传算法的聚类方法[J].广西师范大学学报：自然科学版，2013，31（3）：59-64.

[7] 王永贵，林琳，刘宪国.结合双粒子和K-means的混合文本聚类算法[J].计算机应用研究， 2014，31（2）：364-368.

[8] 刘雷，王洪国，邵增珍，等.一种基于峰群原理的划分聚类算法[J].计算机应用研究， 2011，28（5）：1699-1702.endprint