NLOF:基于网格过滤的两阶段离群点检测算法  

NLOF:two-stage outlier detection algorithm based on grid filtering

作　　者：王立英 石磊[2,3] 伊静 宋天霞[1,2] Wang Liying;Shi Lei;Yi Jing;Song Tianxia(School of Information Science&Engineering,Shandong Normal University,Jinan 250014,China;Shandong Key Laboratory of Distributed Computer Software,Jinan 250014,China;Shandong Education Admissions Examination Institute,Jinan 250014,China;School of Computer,Shandong Jianzhu University,Jinan 250014,China)

机构地区：[1]山东师范大学信息科学与工程学院,济南250014 [2]山东省分布式计算机软件新技术重点实验室,济南250014 [3]山东教育招生考试院,济南250014 [4]山东建筑大学计算机学院,济南250014

出　　处：《计算机应用研究》2020年第4期990-993,998,共5页Application Research of Computers

基　　金：国家自然基金科学基金资助项目(61273148);国家青年自然科学基金资助项目(61502151);山东省社科规划项目(17CHLJ18,17CHLJ33,17CHLJ30);山东省自然科学基金资助项目(ZR2014FL010);山东省教育厅基金资助项目(J15LN34)。

摘　　要：现有的离群点检测算法因没有对原数据进行处理导致计算时间复杂度过高,检测效果不理想。提出一种基于网格过滤的两阶段离群点检测算法NLOF。首先使用网格过滤对原数据进行初步筛选,将密度小于特定阈值的数据放入候选异常子集中;然后为了进一步优化基于密度的算法,基于k邻域,根据邻域中数据点的个数与邻域所组成圆的面积之比,作为数据点密度计算的依据,进行离群点检测以获得更准确的离群点集。在多种公开数据集上进行实验,实验表明,该方法可以在异常检测中取得良好的性能,同时降低了算法的时间复杂度。The existing outlier detection algorithm does not process the original data,resulting in too high computational time complexity and unsatisfactory detection results.This paper proposed a two-stage outlier detection algorithm NLOF based on grid filtering.First it used grid filtering to screen the original data initially,put data with a density less than a certain threshold into a candidate exception subset;then in order to further optimize the density-based algorithm,based on the k-neighborhood,according to the ratio of the number of data points in the neighborhood to the area of the circle formed by the neighborhood,as the basis for calculating the data point density,outlier detection obtained a more accurate outlier set.Experiments was carried out on a variety of public datasets.Experiments show that this method can achieve good performance in anomaly detection and reduce the time complexity of the algorithm.

关 键 词：异常检测 网格过滤 局部密度 NLOF算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]