摘要： 异常检测是数据挖掘的一个重要组成部分，其中基于密度的方法LOF是目前常用的主要方法。然而LOF方法进行检测时需要设定参数k和MinPts，检测结果对参数非常敏感，容易造成检测错误。该文提出了一种基于Voronoi图的异常检测算法VOD，采用Voronoi图来确定对象间的邻近关系，解决了基于密度方法存在的问题，算法的时间复杂性从O(N2)降低到O(NlogN)。

关键词: 数据挖掘, 异常检测, 基于密度, Voronoi图

Abstract: Outlier detection is an integral part of data mining, and the density-based method LOF is the current state of the art in outlier detection. However, LOF is very sensitive to its parameter k and MinPts, which may result in wrong estimation. This paper proposes a new outlier detection algorithm based on Voronoi diagram called VOD. VOD measures the outlier factor automatically by Voronoi neighborhoods without parameter, which provides highly-accurate outlier detection and reduces the time complexity from O(N2) to O(NlogN).

Key words: data mining, outlier detection, density-based, Voronoi diagram

中图分类号: 

• TP311