Abstract: Outlier detection is a hot topic in the field of data management, which has been widely applied to many fields such as medical diagnosis, financial fraud, environment monitoring and many others. At present, along with the application of sensors in data acquisition, people have realized the universality of uncertain data in many fields. Compared with certain data, it is much more difficult to detect outliers on uncertain data sets. To solve the problems, a Fast Outlier Detection approach on Uncertain data sets（FODU） is proposed. Firstly, an index construction strategy inspired by hierarchical ideas is given, which not only overcomes the limitation of the traditional index structure on multi-dimensional data management, but also can prune the searching space quickly. Furthermore, to detect uncertain outliers efficiently, a new filtering algorithm is proposed. Utilizing batch filtering and single point filtering, this approach can reduce redundant calculations and improve inspection efficiency. Then, to avoid the expansion of the possible world, an approach to compute the abnormal probability of data objects is given. At last, the efficiency and effectiveness of the proposed approaches are verified through a series of simulation experiments. The experimental results show that compared with the previous approaches, the proposed algorithm can significantly improve the computation efficiency of outlier detection on uncertain data.

Key words: outlier detection, uncertain data, hierarchical partitioning, batch filtering

摘要： 离群点检测是数据管理领域中的热点问题之一，在医疗诊断、金融诈骗、环境监测等领域中具有广泛的应用。目前，随着传感器等设备在数据采集方面的应用，人们发现数据的不确定性普遍存在。与确定性数据相比，挖掘出不确定数据集中潜在的富有价值的信息变得十分困难。针对上述问题，提出了一种快速的不确定离群点检测算法FODU（Fast Outlier Detection approach on Uncertain data sets）。采用分层次划分思想给出了索引的构建策略，这种索引结构不仅克服了传统索引对多维数据管理的局限性，而且能够被快速地进行空间剪枝；为了快速地挖掘出不确定离群点，提出了高效的过滤方法。该方法通过批量过滤与单点过滤两个过程减少了大量的冗余计算，从而提高了检测效率，为了避免可能世界的空间膨胀，给出了数据对象离群概率值的计算方法。通过实验验证了所提算法的有效性，结果表明，相对于现有研究，该算法可以显著提高不确定离群点的检测效率。

关键词: 离群点检测, 不确定性数据, 分层次划分, 批量过滤