结合蚁群算法与基于划分的DBSCAN聚类算法的研究

摘要

聚类算法是一种无监督的算法。它是一种将分散着的数据对象划分到相应的类当中的过程。在聚类之后，同一个类当中的数据对象及其相似的，相反，在不同类当中的数据对象则尽可能不相似。
　　基于密度的聚类算法能够根据数据对象临近区域的密度将数据对象聚集到一起。DBSCAN聚类算法是经典的基于密度聚类算法之一。它能够发现任意形状的簇，并且只需要两个全局参数Eps和Minpts。DBSCAN被证明对于复杂的数据集和大规模数据都有较好的处理能力。但是，当数据集不断增大的时候，DBSCAN聚类算法需要较高的内存和I/O支持。并且算法对高维的和复杂形状的数据处理能力较差。因此，基于划分的DBSCAN聚类算法(PDBSCAN)被提出用于解决经典的DBSCAN算法的一些缺点。但是当数据集密度不均匀的时候，PDBSCAN聚类算法效果仍然很差。总的来说，DBSCAN与PDBSCAN算法都对初始参数很敏感。
　　本研究采用将蚁群优化算法与基于密度划分的DBSCAN聚类算法结合(即PACA-DBSCAN)来提高聚类效果。算法首先采用改进的蚁群聚类算法(ACA)和本文提出的基于密度划分的方法来对数据集进行初始化，将数据集划分成N个数据子集。之后再采用DBSCAN聚类算法对每一个数据子集进行聚类。本文通过五个数据集来说明PACA-DBSCAN的聚类结果优于DBSCAN和PDBSCAN算法。另外还利用两个经典的数据集来横向的将PACA-DBSCAN与ACA和KHM等算法进行比较，实验表明PACA-DBSCAN算法效果优于其他类型聚类算法。

目录

声明

摘要

引言

第一章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．3 本文研究的内容及结构

1．3．1 本文研究的内容

1．3．2 本文结构

第二章 数据挖掘以及聚类算法概述

2．1 数据挖掘概述

2．2 数据挖掘方法

2．3 聚类算法概述

2．3．1 聚类算法的基本概念

2．3．2 聚类算法的定义

2．3．3 聚类的相似性度量

2．4 聚类分析的主要算法

2．4．1 划分方法(Partitioning Method)

2．4．2 层次方法(Hierarchical Method)

2．4．3 基于密度的方法(Density-based Method)

2．4．4 基于网格的方法(Grid-based Method)

2．4．5 基于模型的方法(Model-based Method)

2．4．6 其他聚类方法

第三章 优化算法以及蚁群算法

3．1 优化算法概述

3．2 蚁群算法概述

3．3 基于蚁群觅食原理的蚁群算法

3．4 基于蚁堆形成原理的蚁群算法

3．4．1 蚁堆算法概念

3．4．2 蚁堆算法的流程

第四章 蚁群算法和基于划分的DBSCAN算法结合

4．1 DBSCAN(A density-based)聚类算法

4．2 基于划分的DBSCAN算法PDBSCAN(Partitioning-based DBSCAN algorithm)

4．2．1 合并聚类结果

4．2．2 将噪声点合并到簇

4．2．3 合并噪声点

4．3 PDBSCAN聚类算法的缺点

4．4 结合蚁群算法的基于密度划分DBSCAN聚类算法

4．4．1 基于点密度的划分方法

4．4．2 基于改进的蚁群算法的划分方法

4．4．3 结合蚁群算法的基于密度划分DBSCAN聚类算法(PACA-DBSCAN)

4．5 试验结果及分析

4．5．1 数据集

4．5．2 实验结果

第五章 结束语

参考文献

致谢

在学期间公开发表著作和论文情况