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

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