基于密度的不确定离群点检测研究.pdf

摘 要
近年来，随着不确定数据挖掘方法在气象、经济、军事、移动电信等领域的广泛应
用，不确定数据的研究已成为当前数据挖掘理论体系的研究热点。然而传统的数据挖掘
技术难以有效解决不确定数据带来的随机性和复杂性，有待开发新型的数据处理与挖掘
分析技术。离群点检测作为一项能揭示罕有现象和事件、发现有趣模式的技术，在信用
卡欺骗、网络入侵、气候异常变化、外来物种检测等应用中具有很高的应用价值。因此，
在不确定数据集上进行离群点检测有着十分重要的意义。
本文首先介绍了确定数据集上离群点检测的理论、方法与不确定数据产生的原因、
管理、类型、可能世界模型及其挑战。其次，针对在不确定数据集上进行离群点检测问
题，本文设计了基于密度计算不确定对象的局部离群因子(Uncertain Local Outlier
Factor：ULOF)的算法。该方法是建立在不确定数据技术中最常用的可能世界模型基础
上的，先计算数据集中可能世界的概率，由于可能世界中每个对象都是确定存在的，因
此可以使用传统方法计算对象的局部离群因子（Local Outlier Factor：LOF）的方法来计
算可能世界中对象的 LOF 值，最后根据这些结果来计算数据集中不确定对象的 ULOF
值，该值越大表明相应对象的离群程度越高，由此判定不确定数据集中的离群点。
本文对算法的时间复杂度与特性进行分析，并对该算法提出了三个优化方法：基于
动态规划(Dynamic Programming)的方法、基于剪枝(Prunning)的方法与基于网格(Grid)
的方法，以提高算法的效率，减少计算的复杂度。
基于密度的不确定离群点检测算法通过计算可能世界概率与对象的得分来确定一
个对象的“环境”，这个环境决定着该对象的不确定离群因子（ULOF），使得该算法更
合理地考虑了影响对象离群度的因素。
最后，通过合成数据的实验验证了本文提出的优化方法能准确且有效地找到不确定
数据上的离群点，同时降低了时间开销，还通过真实植物数据的实验验证了本文算法的
有效性和应用价值。

关键词：不确定数据；局部离群点；可能世界模型；动态规划；网格
Abstract
In recent years, with the uncertainty of data mining methods are widely used in many
fields, such as meteorology, economic, military, mobile telecommunication, the uncertain
data research has become the focus of current data mining theoretical system. However,
traditional data mining techniques can not solve the the problems of randomness and
complexity caused by uncertain data effectively. We need to develop new techniques of data
processing and mining about uncertain data. Outlier detection is a technology which can
reveal rare phenomenons and events, find interesting patterns, and have a high applied value
in many fields, such as the detecting of credit card fraud, network intrusion, abnormal climate,
and alien species. Therefore, outlier detection on the uncertain data is meaningful.
First, this thesis introduces outlier’s detection theories, methods over the certain data.
Produced reasons, management, types, and possible world model over uncer