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

发布时间：2018-04-24 23:25

本文选题：离群点检测 + 分布式计算　；参考：《计算机学报》2016年01期

【摘要】：离群点检测是数据管理领域中的热点问题之一,在许多方面都有着广泛应用,如信用卡诈骗、网络入侵检测、环境监测等.目前现有的离群点检测算法大多针对集中式的处理环境.但随着数据规模的不断增长,传统的集中式算法处理效率受限,无法满足用户日益增长的需求.针对上述问题,文中提出了一种新型的分布式离群点检测算法.首先,在数据存储阶段(即预处理),提出了BDSP(Balance Driven Spatial Partitioning)数据划分算法.该算法可以有效地均衡每个计算节点的工作负载,并实现良好的过滤效果.此外,为划分所得到的每个块设计了一种全新的编码方式,可以快速地确定块与块之间的相邻关系,降低网络开销.基于BDSP算法,提出了BOD(BDSP-based Outlier Detection)分布式离群点检测算法.该算法包括2个步骤:在每个计算节点本地,利用R树索引进行批量过滤,快速地计算离群点并得到本地候选集;利用BDSP中提供的块编码确定需要相互通信的节点,使用少量的网络开销得到最终结果.最后,通过大量实验验证了文中所提出的BDSP和BOD算法的有效性.实验结果表明,相对于现有算法,文中算法可以显著地提高计算效率并大幅降低网络开销.
[Abstract]:Outlier detection is one of the hot issues in the field of data management. It is widely used in many fields, such as credit card fraud, network intrusion detection, environmental monitoring and so on. At present, most of the existing outlier detection algorithms are focused on centralized processing environment. However, with the increasing of data scale, the efficiency of traditional centralized algorithms is limited, which can not meet the increasing needs of users. To solve the above problems, a new distributed outlier detection algorithm is proposed. Firstly, the BDSP(Balance Driven Spatial partitioning algorithm is proposed in the data storage stage (i.e. preprocessing). The algorithm can effectively balance the workload of each computing node and achieve a good filtering effect. In addition, a new coding method is designed for each block, which can quickly determine the relationship between blocks and reduce the network overhead. Based on BDSP algorithm, a distributed outlier detection algorithm based on BOD(BDSP-based Outlier Detection is proposed. The algorithm includes two steps: using R-tree index to filter outliers quickly and get local candidate set at each computing node local, and using block coding provided in BDSP to determine nodes that need to communicate with each other. Use a small amount of network overhead to get the final result. Finally, the effectiveness of the proposed BDSP and BOD algorithms is verified by a large number of experiments. Experimental results show that the proposed algorithm can significantly improve the computational efficiency and significantly reduce the network overhead compared with the existing algorithms.
【作者单位】：东北大学信息科学与工程学院;
【基金】：国家“九七三”重点基础研究发展规划项目基金(2012CB316201) 国家自然科学基金面上项目(61033007,61472070)资助
【分类号】：TP311.13

【相似文献】