基于DBSCAN的自适应非均匀密度聚类算法研究

摘要

随着信息技术的高速发展，数据的规模呈现爆炸式增长。从错综复杂的数据中挖掘出有价值的信息具有巨大的实际意义。聚类算法作为数据挖掘领域中的一类重要方法，被广泛应用于数据分析与挖掘中。DBSCAN算法是一种典型的聚类算法，以数据密度为度量，可以识别数据集中任意形状的类及噪音点。本论文以DBSCAN算法为研究对象，针对其对数据参数Eps和MinPts敏感、在处理非均匀密度数据集时效果不理想等问题进行研究，提出了改进方法，并给出了一种适合于大规模数据的聚类方法。
　　论文的研究工作得到了国家自然科学基金项目(No.61172072、61271308)、北京市自然科学基金项目(No.4112045)和高等学校博士学科点专项科研基金(No.20100009110002)的支持。论文的主要工作如下:
　　首先，为了提高DBSCAN算法对非均匀密度数据集聚类的准确性，本文提出了自适应的非均匀密度聚类算法(Adaptive Varied-Density-Based Spatial Clustering of Applications with Noise，AV-DBSCAN)。该算法改变了DBSCAN算法的邻域及类的定义，将DBSCAN算法中的Eps-邻域改为MinPts-邻域;并通过M-近邻有向图间接得到全局密度参数Eps和MinPts的值，减少了人为选择密度参数的困难。算法将一个类定义为类核心集与类边界集的组合。在聚类中引入有向图的最大连通分量思想，用以识别数据集中的类核心集;再利用有向图的弱连通性识别剩余数据集中的类边界集。与DBSCAN算法相比，该算法在保持相同时间复杂度的前提下，不仅提高了对非均匀密度数据聚类的准确性，也降低了对密度参数的敏感性。
　　然后，为了适应当今数据集规模不断加大，本文提出了基于平衡迭代归约的自适应非均匀密度聚类算法(Balanced Iterative Reducing-Adaptive Varied-Density-Based Spatial Clustering of Applications with Noise,BIRAV-DBSCAN)。该算法综合了BIRCH算法简单高效与AV-DBSCAN算法准确性高的优势。它可以利用有限的内存资源及较少I/O消耗，以较小的误差对大规模的非均匀密度数据集进行高效率聚类，并且可以识别数据集中任意形状的类和异常点。由于该算法扩展性较好，如果将该算法与并行化技术结合可以增大对大规模数据集的处理能力。
　　最后，为了评估AV-DBSCAN和BIRAV-DBSCAN算法的有效性及可靠性，本文采用两个仿真数据集及一个新闻数据集进行实验。实验结果验证了AV-DBSCAN算法在对非均匀密度数据集聚类时具有较高准确性;BIRAV-DBSCAN算法在有限的精度损失下，聚类的效率更高，并且其运行时间随着数据集规模的增长呈线性增长趋势。因此BIRAV-DBSCAN算法更为适宜较大规模数据集的聚类问题。

目录

声明

致谢

摘要

1．1 论文背景及意义

1．2 国内外研究现状

1．3 论文主要内容

1．4 论文组织结构

2 相关理论

2．1 基于密度的聚类算法DBSCAN

2．1．1 概念

2．1．2 算法实现

2．2 图的存储及连通性

2．2．1 有向图的存储

2．2．2 有向图的连通性

2．3 强连通分量搜索算法Tarjan

2．4 文本数据预处理

2．4．1 中文分词

2．4．2 文本表示

2．4．2 相似度计算

2．5 本章小结

3 非均匀密度数据集下的聚类算法AV-DBSCAN

3．1 问题描述

3．2 算法概念

3．3 算法准备工作

3．3．1 M-近邻有向图

3．3．2 参数选择

3．3．3 MinPts-邻域有向图

3．4 算法实现

3．4．1 算法原理及流程

3．4．2 算法实现伪代码

3．4．3 算法分析

3．5 本章小结

4 大规模非均匀密度数据下的聚类算法BIRAV-DBSCAN

4．1 问题描述

4．2 利用层次结构的平衡迭代归约聚类算法BIRCH

4．2．1 概念

4．2．2 聚类流程

4．3 BIRAV-DBSCAN算法实现

4．3．1 第一阶段BIRCH聚类

4．3．2 第二阶段AV-DBSCAN聚类

4．3．3 算法分析

4．4 本章小结

5 实验结果与分析

5．1 性能评价指标

5．2 仿真数据集实验

5．2．1 聚类实现

5．2．2 结果分析

5．3 真实数据集实验

5．3．1 数据采集

5．3．2 数据预处理

5．3．3 聚类实现

5．3．4 结果分析

5．4 本章小结

6．1 总结

6．2 展望

参考文献

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集