基于Eps参数自适应估计的DBSCAN算法改进及其在离群点检测中应用

论文摘要

21世纪,是一个科学技术与数据爆发的时代,数据的规模越来越大,如何有效的从大规模数据中发掘出具有价值的信息成为一个重要的问题。聚类算法作为数据挖掘领域中一个重要研究方向,已逐渐发展成为一个非常活跃的研究课题,广泛被应用于生物信息学、医学、商业和营销、社交网络分析、计算机科学等信息分析领域。基于密度的聚类算法具有众多良好的性质,其中有一种非常重要的算法,DBSCAN（Density-based spatial clustering of applications with noise）,该算法由Martin Ester,Hans-Peter Kriegel等人于1996年提出的,该算法可以在噪声数据中找到孤立的数据点或各种形状和大小的簇。2014年,该算法在数据挖掘领域最高质量的会议（KDD）上获得了时间测试奖（一项对理论和实践上备受关注的算法的奖励）。由于DBSCAN算法需要输入Eps和minPts两个参数,而这两个参数通常需要人的主观意识来判定赋予,导致聚类精度直接被用户的先验知识所决定,且采用的是全局统一的参数,其在非均匀密度集中的聚类效果不理想,本文针对该算法的缺陷,提出了一种新的解决思路和方法。首先,本文利用核密度估计方法计算数据点的核概率密度估计值,并通过核概率密度估计值与Eps值之间的正相关关系,自适应地计算并为每个数据点匹配合适的Eps邻域搜索半径。为了评估改进算法的效果,本文采用了多种不同类型的数据集分别进行了对比实验分析,结果表明,本文方法具有良好的聚类效果,有效提升了聚类精度。最后,由于DBSCAN算法将聚类簇以外的数据点识别为噪声点,因此本文利用该算法特性于离群点检测,为了评估离群点检测的有效性,本文使用真实数据集和模拟数据集进行多次实验验证,通过比较当前常用的几种离群点检测算法,本文算法在离群点检测上具有良好的效果。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
•   1.1 研究背景和意义
•     1.1.1 分类
•     1.1.2 聚类
•     1.1.3 异常检测
•   1.2 国内外研究现状
•     1.2.1 DBSCAN研究现状
•     1.2.2 离群点检测算法研究现状
•       （1） 基于统计的离群点检测方法
•       （2） 基于聚类的离群点检测
•       （3） 基于距离的离群点检测
•       （4） 基于密度的离群点检测算法
•   1.3 本文主要研究内容和结构安排
•     1.3.1 主要研究内容
•     1.3.2 组织框架
•   1.4 本章小结
• 第二章 DBSCAN聚类与离群点检测方法分析
•   2.1 DBSCAN算法简介
•   2.2 DBSCAN相关概念
•   2.3 DBSCAN算法原理及伪代码
•     2.3.1 DBSCAN算法原理
•     2.3.2 DBSCAN算法伪代码描述
•   2.4 DBSCAN算法优缺点
•     2.4.1 算法优点
•     2.4.2 算法缺点
•   2.5 离群点检测概念
•   2.6 离群点产生的原因
•   2.7 离群点检测算法介绍
•     2.7.1 基于密度的LOF算法
•     2.7.2 LOF算法步骤描述
•     2.7.3 孤立森林Isolation Forest
•     2.7.4 算法伪代码
•   2.8 本章小结
• 第三章 改进的DBSCAN聚类算法
•   3.1 改进算法基本思想
•   3.2 相关理论
•     3.2.1 高斯核概率密度
•     3.2.2 核函数带宽选择
•   3.3 参数MINPTS选择
•   3.4 EPS的优化选择
•   3.5 改进算法分析
•     3.5.1 改进算法伪代码指数
•     3.5.2 算法复杂度分析
•   3.6 实验结果对比及分析
•     3.6.1 实验评价指数
•     3.6.2 实验结果
•     3.6.3 实验结果总结
•   3.7 本章小结
• 第四章 改进的DBSCAN离群点检测算法
•   4.1 基本思想
•   4.2 改进离群点算法流程图
•   4.3 改进离群点算法分析
•     4.3.1 改进离群点检测算法伪代码
•     4.3.2 算法复杂度分析
•   4.4 离群点检测质量评估方法
•   4.5 实验结果分析
•   4.6 实验数据集及结果分析
•     4.6.1 实验1
•     4.6.2 实验2
•   4.7 本章小结
• 第五章 总结与展望
•   5.1 总结
•   5.2 展望
• 参考文献
• 攻读硕士学位在校期间取得的研究成果
• 致谢

文章来源

类型: 硕士论文

作者: 朱露

导师: 孔兵

关键词: 算法,参数,高斯核概率,离群点检测

来源: 云南大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 云南大学

分类号: TP311.13;O212.1

总页数: 53

文件大小: 3177K

下载量: 63