摘要: 异常检测是数据挖掘的一个重要组成部分,其中基于密度的方法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
中图分类号:
曲吉林;寇纪淞;李敏强;安世虎. 基于Voronoi图的异常检测算法[J]. 计算机工程, 2007, 33(23): 35-36,3.
QU Ji-lin; KOU Ji-song; LI Min-qiang; AN Shi-hu. Outlier Detection Algorithm Based on Voronoi Diagram[J]. Computer Engineering, 2007, 33(23): 35-36,3.