一种基于Z曲线的新离群点挖掘算法  

New outlier detection based on Z curve

作　　者：唐志刚[1,2] 杨炳儒[1] 杨珺[1] 

机构地区：[1]北京科技大学信息工程学院知识工程研究所,北京100083 [2]南华大学数理学院,湖南衡阳421001

出　　处：《计算机应用研究》2010年第12期4427-4429,4432,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(69835001;60675030;60875029);国家教育部科技重点资助项目([2000]175)

摘　　要：提出一种基于密度的快速查找离群点的算法——基于Z曲线的离群点查找算法(ZOD),依据Z曲线的构造过程将空间分割成大小相等的网格,沿着曲线延伸方向对网格进行排序,将落在网格中的点映射到一维空间,从而克服了基于网格算法的"维灾"缺点;同时用局部偏离指数指示离群点的偏离程度,又具有识别精度高和偏离程度可度量的优点。理论分析表明,该算法性能优于著名的基于密度的算法;实验结果表明,该算法与其他高维离群点挖掘算法相比,在效率及有效处理的维数方面均有显著提高。This paper presented a new quick density-based approach to detect outliers,called outlier detecting based on Z curve （ ZOD）. According to the process of constructing of Z curves,divided space into grids of equal size,and sorted the gird along direction of the curve extends,mapped the point on the grid to one-dimensional space,thus overcame the ＂dimension disaster＂ shortcomings of algorithm based on grid. The algorithm indicated the degree of outlier with the local deviate factor,so identified the outlier exactly and the precision was measurable. Theoretical comparison shows that this method is more efficient than the well-known algorithm ABOD and LOF. The experimental results show that the efficiency of ZOD algorithm and the maximum number of dimensions processed increase obviously comparing with other high-dimensional outlier mining algorithms on simulation and real-life dataset.

关 键 词：数据挖掘 离群点 Z曲线 

分 类 号：TP182[自动化与计算机技术—控制理论与控制工程]