基于方形对称邻域的局部离群点检测方法  

Square symmetric neighborhood based local outlier detection algorithm

作　　者：揭财明[1] 刘慧君[1] 朱庆生[1] 

机构地区：[1]重庆大学计算机学院,重庆400044

出　　处：《计算机应用研究》2012年第2期472-474,共3页Application Research of Computers

基　　金：国家自然科学基金资助项目(61073058)

摘　　要：针对NDOD(outlier detection algorithm based on neighborhood and density)算法在判断具有不同密度分布的聚类间过渡区域对象时存在的不足,以及为了降低算法时间复杂度,提出一种基于方形对称邻域的局部离群点检测方法。该算法改用方形邻域,吸收基于网格的思想,通过扩张方形邻域快速排除聚类点及避免"维灾";通过引入记忆思想,使得邻域查询次数及范围成倍地减小;同时新定义的离群度度量方法有利于提高检测精度。实验测试表明,该算法检测离群点的速度及精度均优于NDOD等算法。NDOD may result in wrong estimation when objects are in the location where the density distributions in multiple clusters are significantly different.To void this problem and reduce the computational complexity,this paper proposed a new density based algorithm named SSNOD（square symmetric neighborhood based local outlier detection algorithm）.By utilizing the grid-based idea,the algorithm partitioned dataset with square neighborhood and expaned neighborhood rapidly,it could get rid of non-outliers quickly and overcome ＂dimension curse＂.By absorbing memory idea,the times of neighborhood query and range were significantly decreased.Besides,computation accuracy could be improved within the novel metrics.Experimental result shows SSNOD is not only efficient in the computation but also more effective than NDOD in detection accuracy.

关 键 词：数据挖掘 离群检测 方形对称邻域 局部离群度 

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