基于偏离特征的离群点挖掘方法研究

摘要

数据挖掘是一个多学科交叉领域，涵盖了机器学习、数据库、统计学、知识系统、人工智能、高性能计算等学科。从广义上讲，数据挖掘是运用适当的算法，对数据模式进行分析研究，以求从大量的模式中发现重要的知识。离群点挖掘是数据挖掘的一个重要研究方向，着重研究罕见稀有的事件，通过检测和分析，挖掘出隐含在其中的及其有价值的知识。离群点挖掘广泛的应用在日志分析、入侵检测、质量控制等现实生活领域，推动了科学进步，促进了社会发展。
　　在静态数据集环境中，本文从偏离特征（局部密度）的角度，提出了一种快速LOF检测算法。传统 LOF算法基于整个数据集来计算各个数据点的局部离群因子，计算量大，时间复杂度高。为了解决这个问题，提高检测效率，该算法将数据空间划分为网格，基于网格的质心来计算数据点的局部离群因子。由于网格的数量少于数据点的数量，在可接受的误差下，明显降低了时间复杂度，但该算法在低中维大数据集中比较有效，对高维数据的检测效果不理想。此外，该算法还可以有效地用于实时离群值检测，每次向数据集添加新数据点时，可以利用现有数据点的网格结构，仅需要识别数据点的网格位置，而不需要进一步的计算新数据点的局部离群因子。通过实验对比传统 LOF算法和本文提出的算法，结果表明在实现和传统 LOF算法基本相近的检测精度时，该算法明显减少了计算时间，提高了效率。
　　在时序数据流环境中，本文从偏离特征的角度，提出了一种快速的IncLOF检测算法。在检测数据流中的离群点时，传统IncLOF算法需要保存数据流中所有先前的数据点来计算新数据点的局部离群因子，由于内存的限制，这是不切实际的。为了去解决这个问题，该算法通过汇总、归并、插值修改措施，积累数据流的历史信息并保存在有限内存中，来计算新数据点的局部离群因子。通过实验对比本文提出的算法和传统IncLOF算法，结果表明在实现和传统IncLOF算法相近的检测精度时，该算法明显减少了计算时间和内存消耗，并且有很好的可扩展性。

目录

声明

第1章 绪论

1.1 课题的研究背景及意义

1.2 国内外研究现状

1.3 本文主要的研究内容

1.4 本文的组织结构

第2章 相关研究基础

2.1 离群点挖掘

2.2 离群点检测算法介绍

2.3 离群点分析研究内容

2.4 本章小结

第3章 静态数据集中离群点检测算法

3.1 研究概述

3.2 快速LOF检测算法

3.3 实验及结果分析

3.4 本章小结

第4章 时序数据流中离群点检测算法

4.1 研究概述

4.2 快速IncLOF检测算法

4.3 时间复杂度分析

4.4 海量数据流中参数b的范围

4.5实验结果及分析

4.6 本章小结

结论

参考文献

致谢