BOD:一种高效的分布式离群点检测算法

作     者：王习特 申德荣 白梅 聂铁铮 寇月 于戈 WANG Xi-Te;SHEN De-Rong;BAI Mei;NIE Tie-Zheng;KOU Yue;YU Ge

作者机构：东北大学信息科学与工程学院沈阳110004 

基　　金：国家"九七三"重点基础研究发展规划项目基金(2012CB316201) 国家自然科学基金面上项目(61033007 61472070)资助 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2016年第39卷第1期

页      码：36-51页

摘      要：离群点检测是数据管理领域中的热点问题之一,在许多方面都有着广泛应用,如信用卡诈骗、网络入侵检测、环境监测等.目前现有的离群点检测算法大多针对集中式的处理环境.但随着数据规模的不断增长,传统的集中式算法处理效率受限,无法满足用户日益增长的需求.针对上述问题,文中提出了一种新型的分布式离群点检测算法.首先,在数据存储阶段(即预处理),提出了BDSP(Balance Driven Spatial Partitioning)数据划分算法.该算法可以有效地均衡每个计算节点的工作负载,并实现良好的过滤效果.此外,为划分所得到的每个块设计了一种全新的编码方式,可以快速地确定块与块之间的相邻关系,降低网络开销.基于BDSP算法,提出了BOD(BDSP-based Outlier Detection)分布式离群点检测算法.该算法包括2个步骤:在每个计算节点本地,利用R树索引进行批量过滤,快速地计算离群点并得到本地候选集;利用BDSP中提供的块编码确定需要相互通信的节点,使用少量的网络开销得到最终结果.最后,通过大量实验验证了文中所提出的BDSP和BOD算法的有效性.实验结果表明,相对于现有算法,文中算法可以显著地提高计算效率并大幅降低网络开销.

主 题 词：离群点检测 分布式计算 大数据 数据划分 数据管理 大规模数据 

学科分类：0810[工学-土木类] 0808[工学-自动化类] 0839[0839] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 081202[081202] 

核心收录：

D　O　I：10.11897/sp.j.1016.2016.00036

馆 藏 号：203213054...