Efficient Pruning Schemes for Distance-Based Outlier Detection
N. Vu, und V. Gopalkrishnan. Machine Learning and Knowledge Discovery in Databases(2009)
Outlier detection finds many applications, especially in domains that have scope for abnormal behavior. In this paper, we
present a new technique for detecting distance-based outliers, aimed at reducing execution time associated with the detectionprocess. Our approach operates in two phases and employs three pruning rules. In the first phase, we partition the data intoclusters, and make an early estimate on the lower bound of outlier scores. Based on this lower bound, the second phase thenprocesses relevant clusters using the traditional block nested-loop algorithm. Here two efficient pruning rules are utilizedto quickly discard more non-outliers and reduce the search space. Detailed analysis of our approach shows that the additionaloverhead of the first phase is offset by the reduction in cost of the second phase. We also demonstrate the superiority ofour approach over existing distance-based outlier detection methods by extensive empirical studies on real datasets.
