VDOD:一种基于KD树的分布式离群点检测算法  

VDOD:Distributed Outlier Detection Algorithm Based on KD-tree

作　　者：李子茂[1] 骆庆 刘晶[1] LI Zimao;LUO Qing;LIU Jing(School of Computer Science,South-central University For Nationalities,Wuhan 430074)

机构地区：[1]中南民族大学计算机科学学院,武汉430074

出　　处：《计算机与数字工程》2018年第3期419-423,428,共6页Computer & Digital Engineering

基　　金：国家自然科学基金项目"多视图信息融合的乳腺肿块计算机辅助诊断关键技术研究"(编号:61302192);国家科技支撑计划项目子课题"民族特色农产品多语言网络交易展示平台关键技术集成与应用示范"(编号:2015BAD29B01)资助

摘　　要：针对大数据的数据量大、维数高的特征,论文提出了一种新型的分布式离群点检测算法-VDOD。在数据预处理阶段,提出了基于方差的数据划分方法,划分过程中建立KD树,通过KD树将数据均匀地分配到各个计算节点;在离群点检测阶段,通过R树进行批量过滤。最后,基于真实数据集和人工数据集验证了VDOD算法的有效性。实验结果表明,相对于现有算法,文中算法可以显著提高计算效率并大幅降低网络开销。A new distributed outlier detection algorithm,VDOD is proposed for large data of the large amount of data and high dimensional characteristics.In the data preprocessing stage,a data partitioning method based on variance is proposed.KD tree is established in the process of partitioning,and the data are evenly distributed to each computing node through KD tree.In the outlier detection stage,batch filtering is performed by R tree.Finally,the validity of the VDOD algorithm is verified based on the real data set and the artificial data set.The experimental results show that compared with the existing algorithms,the algorithm can significantly improve the computational efficiency and significantly reduce the network overhead.

关 键 词：分布式 离群点检测 大数据 KD树 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]