基于密度的局部离群点检测算法的研究与应用

摘要

近年来，随着传感器技术和数据库技术的迅猛发展，数据挖掘技术得到了广泛的应用，影响着人们生活的各个领域。数据挖掘技术就是从海量的、有噪声的数据集中提取新颖的、有价值的潜在知识。离群点检测作为数据挖掘的一个热门分支，主要致力于查找出相对于其他大量数据对象产生显著偏离，或不符合一般对象的行为特征的对象。目前，离群点检测主要应用于网络攻击行为检测，信用卡诈骗检测，极端天气预报，电信话费诈骗分析等领域。
　　离群点检测的应用越来越受到关注，现有的离群点检测算法遭遇到极大挑战。主要存在如下不足:(1)数据量越来越大，数据维数越来越高，甚至达到成百上千维，而现有的离群点挖掘算法主要针对中低维的小规模的数据集，难以有效地挖掘高维海量的数据集，并且检测出的离群点是全局的，而非局部的;(2)简单的将离群点看作是一种“非此即彼”的二元属性，未能对离群点的离群程度进行评估。
　　本文针对传统的基于密度的离群点检测算法LOF、ELSC存在的不足，主要局限在难以适应高维大数据量的挖掘，并且没有充分考虑数据对象与其邻域内对象的相对关系，挖掘过程中重复计算的步骤过多。从而提出了改进算法NELSC。本文的主要工作有:
　　(1)针对海量的大规模数据集，本文提出了基于DBSCAN算法的剪枝策略。根据DBSCAN算法对参数敏感的特点，通过使用多组不同的数据参数，得到不同的DBSCAN聚类结果，然后对结果进行分析整合，将簇数据剪枝，得到初步的离群数据集。使用多组不同的参数是为了避免误将簇边缘的数据对象错剪，这样可以最大程度地减小数据量，降低计算复杂度，同时又可以保证检测的精确度。
　　(2)针对传统算法对高维数据集检测低效的问题，文中提出基于信息熵的离群子空间策略，通过使用该策略，对不同的对象属性赋予不同的权值，根据不同属性权值生成不同的属性权向量，进而计算得到对象之间的熵权距离，有效地解决了高维数据挖掘中存在的“维度灾难”问题，实现了在高维空间中基于密度的局部离群点挖掘。
　　(3)在DBSCAN算法聚类的过程中和计算局部离群系数时，传统算法的邻域查询过程中对象p的邻域查询信息仅仅用来处理当前数据对象p，该邻域查询结束后就彻底丢弃这些信息，而实际上，这些信息对p的邻域中对象的邻域查询非常有用。根据该特点，文中采用了基于记忆效应的邻域查询优化策略，有效地缩小了邻域查询范围。
　　(4)理论证明和实验结果均表明本文改进算法的有效性和检测离群点的高效性。

目录

声明

摘要

第一章 绪论

1．1 课题研究背景

1．2 国内外研究现状

1．2．1 国外的研究现状

1．2．2 国内的研究现状

1．3 研究意义

1．4 论文所作的工作及组织结构

1．5 本章小结

第二章 离群点检测相关知识

2．1 数据挖掘概述

2．1．1 数据挖掘的定义

2．1．2 数据挖掘的过程

2．1．3 数据挖掘的功能

2．2 离群点概述

2．2．1 离群点定义

2．2．2 离群点产生原因

2．3 离群点的检测方法

2．3．1 基于分布的离群点检测方法

2．3．2 基于深度的离群点检测算法

2．3．3 基于聚类的离群点检测算法

2．3．4 基于距离的离群点检测算法

2．3．5 基于密度的离群点检测算法

2．4 离群点挖掘研究热点及发展趋势

2．4．1 高维大数据集中离群点的挖掘

2．4．2 时序离群点挖掘

2．4．3 web离群点挖掘

2．4．4 空间离群点挖掘

2．5 离群点检测方法的评价指标

2．6 本章小结

第三章 基于密度的局部离群点检测方法研究

3．1 传统的基于密度的局部离群点检测算法

3．1．1 LOF算法

3．1．2 ELSC算法

3．2 算法改进策略

3．2．1 基于记忆效应的邻域查询优化

3．2．2 基于DBSCAN算法的数据预处理

3．2．3 基于离群子空间的权值量化

3．3 改进算法NELSC

3．4 算法分析

3．5 本章小结

第四章 仿真实验以及实验结果分析

4．1 实验测试

4．1．1 实验数据预处理与数据规范化

4．1．2 实验数据集

4．1．3 实验和实验结果分析

4．2 本章小结

第五章 改进算法NELSC在广告定向投递中的应用

5．1 改进算法NELSC在广告定向投递中的应用

5．1．1 定向广告的产生背景

5．1．2 改进算法NELSC挖掘高收入目标客户

5．2 本章小结

第六章 总结与展望

6．1 本文工作总结

6．2 研究与展望

参考文献

在校期间参加的科研项目和发表的论文

致谢