Abstract: Mining outliers 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.

Key words: outlier detection, local density, strong k nearest neighbors, weak k nearest neighbors, Reverse k Nearest Neighbors (RkNN)

摘要： 已有的密度离群点检测算法LOF不能适应数据分布异常情况离群点检测，INFLO算法虽引入反向k近邻点集有效地解决了数据分布异常情况的离群点检测问题，但存在需要对所有数据点不加区分地分析其k近邻和反向k近邻点集导致的效率降低问题。针对该问题，提出局部密度离群点检测算法--LDBO，引入强k近邻点和弱k近邻点概念，通过分析邻近数据点的离群相关性，对数据点区别对待；并提出数据点离群性预判断策略，尽可能避免不必要的反向k近邻分析，有效提高数据分布异常情况离群点检测算法的效率。理论分析和实验结果表明，LDBO算法效率优于INFLO，算法是有效可行的。

关键词: 离群点检测, 局部密度, 强k近邻点, 弱k近邻点, 反向k近邻点集