针对非均匀数据集的DBSCAN过滤式改进算法

摘要

数据挖掘是从海量的数据中挖掘出隐含的、先前未知的、对决策有潜在价值的知识和规则。聚类分析是数据挖掘领域中的一个重要研究课题。所谓聚类是将物理或抽象的集合分组成为类似的对象组成的多个类的过程。由聚类所生成的类是一组数据对象的集合，这些对象与同一个类中的对象彼此相似，与其它类中的对象相异。在许多应用中，可将一个类中的数据对象作为一个整体处理。当分析一个较大的、复杂的、连续的、有许多变量的数据库和完全未知的结构时，聚类是一个非常有用的工具。
　　 目前，聚类分析算法大体上分为划分的方法，层次的方法，基于密度的方法，基于网格的方法和基于模型的方法。DBSCAN算法是一种典型的基于密度的方法，该算法的优点是可以发现任意形状的聚类，且聚类结果受噪音点影响小。但是该算法存在如下缺点：算法中需使用到全局变量Eps和MinPts，若变量取值不当，会影响聚类质量；当数据分布不均匀时，采用全局统一的变量，会降低聚类质量。
　　 针对DBSCAN算法的缺点，本文在结合一种减少邻域搜索思想的同时，提出了一种DBSCAN过滤式改进算法。该算法首先对k-dist数据进行一维聚类，同时去掉噪声类，从而得到能代表主要密度水平的类；然后再根据一维聚类结果自动计算出Epsi,为后面的过滤式聚类作好准备。
　　 在得到参数Epsi后，该算法根据不同的Eps分别进行聚类，从而找出非均匀数据集中的各种聚类。在聚类过程中，每当下一次调用聚类算法进行聚类时，将去掉已经聚成类的数据点，以避免数据点被重复聚类。
　　 由于改进算法首先通过对k-dist数据进行一维聚类，以得到不同密度水平的Epsi，然后再根据Epsi进行过滤式聚类。因此，在针对密度不均匀的数据集时，改进算法的聚类质量更好，并更能反映数据集的分布特征。

目录

文摘

英文文摘

声明

1绪论

1.1研究背景和意义

1.2国内外研究现状

1.3本论文的研究内容

1.4论文章节安排

2数据挖掘及聚类算法分析

2.1数据挖掘概述

2.1.1数据挖掘概念

2.1.2数据挖掘过程

2.1.3数据挖掘的功能

2.2聚类算法综述

2.2.1划分方法(Partitioning methods)

2.2.2层次方法(Hierarchy methods)

2.2.3基于网格的方法(grid-based methods)

2.2.4基于模型的方法(model-based methods)

2.2.5基于密度的聚类(density-based methods)

2.3本章小结

3 DBSCAN算法和FDBSCAN算法

3.1 DBSCAN算法简介

3.1.1算法思想

3.1.2算法框架

3.2 DBSCAN算法局限性分析

3.3 DBSCAN算法现有的一些改进

3.4 FDBSCAN算法

3.4.1算法思想

3.4.2算法框架

3.4.3时间复杂度分析

3.5本章小结

4基于过滤的DBSCAN改进算法

4.1 k-dist图的描述

4.2 DBSCAN过滤式改进算法基本思想

4.3参数Epsi的确定

4.4算法流程

4.5实验结果与分析

4.6小结

5论文总结

致谢

参考文献

附录