Outlier Detection Based on Voronoi Diagram

Outlier mining is an important branch of data mining and has attracted much attention recently. The density-based method LOF is widely used in application. However, selecting MinPts is non-trivial, and LOF is very sensitive to its parameters MinPts. In this paper, we propose a new outlier detection method based on Voronoi diagram, which we called Voronoi based Outlier Detection (VOD). The proposed method measures the outlier factor automatically by Voronoi neighborhoods without parameter, which provides highly-accurate outlier detection and reduces the time complexity from O(n(2)) to O(nlogn).