基于密度的不确定数据离群点检测研究  

Density-based Outlier Detection on Uncertain Data

作　　者：洪沙[1] 林佳丽[1] 张月良[1] 

机构地区：[1]重庆大学软件学院,重庆401331

出　　处：《计算机科学》2015年第5期230-233,264,共5页Computer Science

基　　金：国家自然科学基金(61173131);重庆自然科学基金(CSTS2010BD2061)资助

摘　　要：针对不确定数据集进行离群点检测,设计了基于密度的不确定数据的局部离群因子(Uncertain Local Outlier Factor,ULOF)算法。通过建立不确定数据的可能世界模型来确定不确定对象在可能世界中的概率。结合传统的LOF算法推导出ULOF算法,根据ULOF值判断不确定对象的局部离群程度;然后对ULOF算法的效率性和准确性进行了详细分析,提出了基于网格的剪枝策略、k最近邻查询优化来减少数据的候选集;最后通过实验证明了ULOF算法对不确定数据检测的可行性和效率性,优化后的方法有效地提高了异常检测准确率,降低了时间复杂度,改善了不确定数据的异常检测性能。Based on local information, a new outlier detection algorithm was designed to calculate density-based uncertain local outlier factor （ULOF） for each point in an uncertain dataset. Firstly, by establishing the possible world model, we calculated the probability of possible word for uncertain data. Then we combined the traditional LOF algorithm to derivate the ULOF algorithm formula, and judged the degree outlier of each data according to the ULOF value. We also did a detailed analysis for efficiency and accuracy of ULOF algorithm. At the same time, we proposed gird-based pruning strategy and k-nearest neighborhood query optimization to reduce the candidate dataset. At last the results of several experiments on synthetic data demonstrate the feasibility and effectiveness of the proposed approach. Optimized NLOF algorithm can improve the outlier detection accuracy, reduce the time complexity and improve the performance of outlier detection on uncertain data.

关 键 词：不确定数据 局部离群点检测 可能世界模型 k最近邻 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]