基于Voronoi图的异常检测算法  

Outlier Detection Algorithm Based on Voronoi Diagram

作　　者：曲吉林[1] 寇纪淞[2] 李敏强[2] 安世虎[1] 

机构地区：[1]山东财政学院计算机与信息工程学院,济南250014 [2]天津大学系统工程研究所,天津300072

出　　处：《计算机工程》2007年第23期35-36,39,共3页Computer Engineering

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

关 键 词：数据挖掘 异常检测 基于密度 VORONOI图 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]