基于局部密度的快速离群点检测算法

摘要

已有的密度离群点检测算法LOF不能适应数据分布异常情况离群点检测,INFLO算法虽引入反向k近邻点集有效地解决了数据分布异常情况的离群点检测问题,但存在需要对所有数据点不加区分地分析其k近邻和反向k近邻点集导致的效率降低问题.针对该问题,提出局部密度离群点检测算法--LDBO,引入强k近邻点扣弱k近邻点概念,通过分析邻近数据点的离群相关性,对数据点区别对待;并提出数据点离群性预判断策略,尽可能避免不必要的反向k近邻分析,有效提高数据分布异常情况离群点检测算法的效率.理论分析和实验结果表明,LDBO算法效率优于INFLO,算法是有效可行的.%Mining oufliers is to find exceptional objects that deviate from the most rest of the data set.Outlier detection based on density has attracted lots of attention,but the density-based algorithm named Local Outlier Factor (LOF) is not suitable for the data set with abnormal distribution,and the algorithm named INFLuenced Outlierness (INFLO) solves this problem by analyzing both k nearest neighbors and reverse k nearest neighbors of each data point at cost of inferior efficiency.To solve this problem,a local density-based algorithm named Local Density Based Outlier detection (LDBO) was proposed,which can improve outlier detection efficiency and effectiveness simultaneously.LDBO introduced definitions of strong k nearest neighbors and weak k nearest neighbors to realize outlier relation analysis of those data points located nearby.Furthermore,to improve the outlier detection efficiency,prejudgement was applied to avoid unnecessary reverse k nearest neighbor analysis as far as possible.Theoretical analysis and experimental results Indicate that LDBO outperforms INFLO in efficiency,and it is effective and feasible.