基于密度的局部离群点挖掘算法研究

论文摘要

离群点挖掘作为数据挖掘的重要组成部分,能够从大量复杂的数据中找到小部分与其他数据相比最不一致、显著异常的数据点,这些异常点往往包含着非常重要的信息。本文通过研究现有的离群点挖掘算法以及目前国内外在离群点挖掘工作上的进展情况,针对离群点挖掘的热点问题,分别在大规模高维数据和空间数据这两个离群点挖掘研究热点上,提出了基于聚类约减的局部离群点检测算法和基于Voinoroi图的局部加权空间离群点挖掘算法。在大规模高维数据集上,由于LOF算法需要反复遍历数据库计算所有点的邻域,时间复杂度非常高,本文提出一种改进的离群点挖掘算法。算法使用核K-means聚类将数据点映射到高维核空间中,通过高维核空间突出了样本之间的差异,选取数据集内真实的点代替均值点,从而减小离群点的干扰。最后对划分好的数据簇,通过度量函数判断数据簇内点的分布情况,选出离群点候选集,仅对该候选集内的点进行局部离群点挖掘。基于核K-means聚类的离群点检测算法约减了参与计算的数据点,从而降低了执行时间。在空间数据挖掘中,由于空间数据具有自相关性和空间异质性,因此,传统的离群点挖掘方法在空间领域内挖掘效果并不理想。本文根据空间离群点挖掘的现有问题,提出了基于Voronoi图的局部加权空间离群点挖掘算法,该方法将空间数据的属性划分为空间属性和非空间属性,通过空间属性确定空间数据的邻域,解决了数据的自相关性；通过计算对象的局部离群因子,解决空间数据的异质性。使用Voronoi图查找数据对象的邻域能够将时间复杂度降低到O（nlogn）,并且该方法避免了人为输入参数的行为,减少了算法对用户的依赖性。同时对于不同邻域、不同的属性添加局部权值,增加局部重要属性对离群点的影响程度,进一步提升了算法的精度。两种方法分别在真实数据集上进行了实验,实验结果表明,本文提出的方法在时间复杂度和查找精度上都有一定的优越性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 离群点挖掘的研究背景和意义
• 1.2 离群点挖掘国内外研究热点
• 1.2.1 挖掘高维大规模数据离群点
• 1.2.2 挖掘空间离群点
• 1.2.3 挖掘数据流离群点
• 1.3 本文主要研究内容以及创新点
• 1.4 论文组织结构
• 第二章 离群点挖掘方法及其分类
• 2.1 基于统计分布的离群点挖掘方法
• 2.2 基于距离的离群点挖掘方法
• 2.3 基于密度的离群点挖掘方法
• 2.4 基于偏差的离群点挖掘方法
• 2.5 本章小结
• 第三章 基于聚类约减的局部离群点挖掘算法研究
• 3.1 LOF算法介绍和分析
• 3.2 改进的核k-means算法介绍
• 3.3 基于聚类约减的局部离群点挖掘算法思想
• 3.3.1 算法相关定义
• 3.3.2 算法过程描述
• 3.3.3 算法时间复杂度分析
• 3.4 实验以及结果分析
• 3.4.1 参数对执行时间的影响
• 3.4.2 算法的可伸缩性
• 3.4.3 算法的精度
• 3.5 本章小结
• 第四章 基于Voronoi图的局部加权空间离群点挖掘算法
• 4.1 空间离群点挖掘的背景介绍
• 4.2 Voronoi图相关知识
• 4.2.1 Voronoi多边形背景知识
• 4.2.2 Voronoi图相关定义
• 4.2.3 Voronoi图构造方法
• 4.2.4 Voronoi图相关性质
• 4.3 基于Voronoi图的局部加权空间离群点挖掘算法
• 4.3.1 算法相关定义和原理
• 4.3.2 算法过程描述
• 4.3.3 算法的时间复杂度分析
• 4.4 实验以及结果分析
• 4.4.1 算法精确度分析
• 4.4.2 算法执行效率分析
• 4.4.3 算法可伸缩性和依赖性分析
• 4.5 本章小结
• 第五章 总结与展望
• 5.1 本文工作总结
• 5.2 进一步工作
• 参考文献
• 致谢
• 攻读硕士学位之间所发表的论文