基于粒子群的DBSCAN算法研究
VIP免费
摘 要
数据挖掘是指从大量的数据中来挖掘有价值的知识和规则，该知识和规则必
须是先前未知的、隐含的、对决策有潜在价值的。聚类分析是数据挖掘领域中的
一个热点研究问题。所谓的聚类就是将具体的或者抽象的很多集合分成多个类的
过程，该过程要求生成的属于同一类中的数据对象之间彼此相似，而属于不同类
之间的对象的差异较大。在现实应用中，通常将同一类中的对象作为一个整体来
处理。聚类分析在分析比较庞大的、连续的、复杂的、许多变量组成的未知的结
构时，是一种非常有用的工具。
目前，聚类分析方法大体上分为基于划分的方法，基于层次的方法，基于密
度的方法，基于网络的方法和基于模型的方法等。DBSCAN ( Density-Based Spatial
Clustering of Applications with Noise) 算法是一种典型的基于密度的聚类方法。该
算法的优点就是能够发现任意形状的簇类，而且聚类的结果不受噪声点的影响。
但是，该算法存在以下的缺点：当面对海量数据时，该算法对内存和 I/0 要求比较
高；该算法需要输入全局变量 Eps 和MinPts 参数，当该参数选择不理想时，会很
大程度上影响到聚类的质量；当数据集分布不均匀比较散乱时，若采用统一的变
量，聚类的结果往往不好。
针对 DBSCAN 算法的缺点，本文提出了一种基于粒子群优化与 DBSCAN 算
法相结合的 DSUPSO 算法(DBSCAN Using Particle Swarm Optimization,基于粒子
群的 DBSCAN 算法)。首先针对输入参数敏感的缺点，利用粒子群算法中粒子中的
信息共享、收敛最优解非常快的优势，通过设定合适的适应度函数，提出了自动
选择输入参数 MinPts、
Eps 的解决方案；这种方法不需要特殊领域的知识，从而屏
蔽了人们对于参数的依赖。实验证明，通过该方法优化得到的结果作为输入参数
有较好的聚类结果。
而对于数据分布不均匀的情况下，由于使用全局的变量，使得聚类的效果比
较差，很多噪声点容易划入簇中，或者簇中的点被当作噪声点的问题，本文对初
始DBSCAN 得到的聚类结果利用各个数据点到核心点的距离的差的平方的和作为
适应度值，再次利用粒子群算法的优势，对聚类后的结果进行优化。实验证明，
DSUPSO 算法在聚类质量上优于原始的 DBSCAN 算法。
DSUPSO 算法利用粒子群算法的优势，优化了输入参数，从而给人们提供了
一种新的选取参数的方法。同时在聚类结果不够理想的情况下，再次利用了粒子
群算法，对聚类的结果进行了优化，使得聚类的质量得到进一步的提高。
关键词：数据挖掘 聚类分析 DBSCAN 算法 粒子群算法
ABSTRACT
Data Mining denotes to get valuable knowledge and rules from lots of data, and the
knowledge and rules must have never been known to the public and must have potential
value in helping making decisions. Clustering is a problem which is being widely
researched in the field of Data Mining. Clustering is the process to classify the concrete
or abstract classes into many different clusters, and the process requires that the data
objects in one cluster are very similar to each other, and objects from different clusters
have the most manifest difference. In many applications, we often tackle the objects
from one class as one entirety. Clustering is a very useful tool in analyzing known
structures which are bulky, continuous, complicated and made of many variables.
Nowadays, Clustering can be divided into the following ways: partition based
method, density based method, hierarchy based method, gridding based method and
model based method. DBSCAN is a typical method based on density. Its advantage is
that it can find out arbitrary shape clusters, and the results will be hardly affected by any
noise points. But, there are still many disadvantages, such as: it has a high demand of
the memory and the I/O equipments, the algorithm needs the input of global variables,
which will affect the quality of clustering if the parameters are not correctly chosen, and
when the data distribution is not average, if we use unite variable, the result is often not
very good.
To solve the disadvantage of DBSCAN, this paper puts up the DSUPSO algorithm
which combines the method based on Particle Swarm Optimization and DBSCAN. In
response to the sensitivity of input variables, We take advantage of PSO which is with
better global optimization capability，this method does not need knowledge of a special
field, so we do not need to depend on the parameters. Experiments show that using the
results after the optimization of this method as the input parameter, we can get better
results.
About the situation where the distribution of data is not average, because of the use
of global variables, the results is often very bad, many noise points are classified into
clusters , on the other hand many points which belongs to clusters are as to noise points,
so we use the advantage of PSO to optimize the results. The experiments show that the
DSUPSO algorithm is better than the DBSCAN algorithm in the quality of clustering.
The DSUPSO algorithm use the advantage of PSO to optimize the input
parameters, and give us a new way to chose parameters. And we use the PSO to
optimize the results of clustering when the distribution of data is not average. It proves
that we further raise the quality of clustering.
Key Words: Data Mining, Clustering, DBSCAN, Particle Swarm
Optimization
目 录
中文摘要
ABSTRACT
第一章 绪 论 ....................................................... 1
§1.1 研究背景和研究意义 ......................................... 1
§1.2 研究领域发展现状 ........................................... 2
§1.3 本文工作概述和论文结构 ..................................... 3
第二章 数据挖掘及聚类算法 .......................................... 4
§2.1 数据挖掘概述 ............................................... 5
§2.2 数据挖掘中的常用技术 ....................................... 7
§2.2.1 决策树 ................................................. 7
§2.2.2 神经网络 ............................................... 9
§2.2.3 关联规则 ............................................... 9
§2.2.4 统计学习 .............................................. 10
§2.2.5 聚类分析 .............................................. 10
§2.3 聚类分析概述 .............................................. 11
§2.3.1 聚类分析常用数据类型 .................................. 11
§2.3.2 聚类分析相似度度量方法 ................................ 12
§2.4 聚类分析主要方法 .......................................... 14
§2.5 小结 ...................................................... 15
第三章 粒子群算法及其在聚类中的应用 ............................... 16
§3.1 粒子群算法简介 ............................................ 16
§3.1.1 粒子群算法的由来 ...................................... 16
§3.1.2 粒子群算法原理 ........................................ 17
§3.1.3 粒子群算法参数设置 .................................... 21
§3.2 基于粒子群的聚类算法 ...................................... 23
§3.3 小结 ...................................................... 24
第四章 基于粒子群的 DBSCAN 改进算法 ..............................25
§4.1 DBSCAN 算法 ............................................. 25
§4.1.1 DBSCAN 算法中基本概念 ............................... 25
§4.1.2 算法的基本思想 ........................................ 26
§4.1.3 该算法现有的一些改进 .................................. 28
§4.2 用粒子群(PSO)来优化 DBSCAN 输入参数 ......................29
§4.2.1 优化参数算法构造的基本思想 ............................ 29
§4.2.2 优化参数算法的算法框架 ................................ 29
§4.3 用粒子群(PSO)来优化 DBSCAN 聚类结果 ......................31
§4.3.1 优化聚类质量算法构造的基本思想 ........................ 31
§4.3.2 优化聚类质量的算法框架 ................................ 31
§4.4 实验结果及分析 ............................................ 34
§4.4.1 针对输入参数优化的验证 ................................ 34
§4.4.1 利用粒子群对聚类结果的优化的验证 ...................... 38
第五章 结论 ....................................................... 41
§5.1 总结 ...................................................... 41
§5.2 存在的问题及可以改进的地方 ................................ 41
参考文献 .......................................................... 41
在读期间公开发表的论文和承担科研项目及取得成果 .................... 45
致 谢 ........................................................... 47
第一章 绪论
1
第一章 绪 论
§1.1 研究背景和研究意义
随着计算机技术、网络技术以及通讯技术的飞速发展，我们进入了一个高速
发展的信息社会时代。数据库、数据仓库以及 WEB 等各种各样的数据源，各种不
同渠道的海量数据汇集成了浩瀚的海洋。人们面临的问题不再是无信息可用，而
是如何在这浩瀚的海洋之中找到蕴藏之中的有巨大价值的知识宝藏。创造总来源
于需求，在人们迫切需求的召唤下，数据挖掘和知识发现由此诞生。
一般认为，广义的数据挖掘又称知识发现。是指从海量的、不完整的、有噪
声和随机的数据中，提取隐含在其中的、人们事先不知道的但又是可信的，潜在
的和有价值的信息和知识的过程。它是一门综合性学科，涉及很多学科，例如：
数据库技术、机器学习、模式发现、统计分析、人工智能、信息检索、信号处理
及可视化技术等。目前已广泛应用于零售业、银行业、医学等诸多领域。
正所谓物以类聚，聚类是数据挖掘领域一个重要的方法。它是指将数据集分
成一些不同的类别，使异类中的数据对象尽可能不相同，而同一类中的数据尽可
能相同。在很多应用中，聚类分析可以作为一种数据预处理的手段，从而来进一
步作为进一步分析和处理数据的基础。与此同时，聚类分析还可以作为获得数据
分布情况、观察每个类的特征以及对某一特定类进一步分析的工具。通过聚类分
析，我们能够识别稀疏和密集的区域，发现全局的分布模式及数据属性中的各种
相互关系等。不同的算法有着不同的优势所在。有的适用于任意形状的数据集，
有的适用于小量数据集。其目的都是在将数据集进行高质量、高效率的聚类。
DBSCAN 是最具代表性的一个基于密度聚类的方法。此算法的优势在于是从
数据对象的分布密度开始，把密度足够大的区域连接起来，从而可以各种各样形
状的类。它还能去处掉噪声点影响。但是它最大的缺点是需要用户输入参数，因
此对参数非常敏感。当参数选择不好时，则聚类结果会很差。本文针对该算法的
缺点进行了研究，提出了 DSUPSO 算法,该算法较好的解决了以上问题。此外，在
该算法中使用粒子群优化对输入的参数进行优化，同时对结果进行评估。
粒子群算法是一种高效的全局优化算法。它基于群体智能理论，通过群体之
中的粒子间的竞争和合作，进行群体智能优化搜索。它在解决嘈杂无序的大量数
据时，提供了高效的寻优解决方法。相对其他算法，它有防止粒子容易陷入局部
最优，能够更高效搜索而且稳定的优势。因此近年来被广泛应用于数据挖掘领域。
本文基于粒子群算法，对 DBSCAN 算法的输入参数进行优化，从而得到较优
的输入参数，在聚类的结果不够理想的情况，对聚类的结果进行了优化，从而得
到更好的聚类结果。
摘要：
展开>>
收起<<
摘要数据挖掘是指从大量的数据中来挖掘有价值的知识和规则，该知识和规则必须是先前未知的、隐含的、对决策有潜在价值的。聚类分析是数据挖掘领域中的一个热点研究问题。所谓的聚类就是将具体的或者抽象的很多集合分成多个类的过程，该过程要求生成的属于同一类中的数据对象之间彼此相似，而属于不同类之间的对象的差异较大。在现实应用中，通常将同一类中的对象作为一个整体来处理。聚类分析在分析比较庞大的、连续的、复杂的、许多变量组成的未知的结构时，是一种非常有用的工具。目前，聚类分析方法大体上分为基于划分的方法，基于层次的方法，基于密度的方法，基于网络的方法和基于模型的方法等。DBSCAN(Density-BasedS...
相关推荐
作者：陈辉
分类：高等教育资料
价格：15积分
属性：48 页
大小：1.13MB
格式：PDF
时间：2024-11-19
