犅犗犇一种高效的分布式离群点检测算法.PDFVIP

第 卷 第 期 计 算 机 学 报 ３９ １ 　 　　 　　 　　 　　 Ｖｏｌ．３９ Ｎｏ．１ 年 月 ２０１６ １ ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ Ｊａｎ．２０１６ 　 犅犗犇：一种高效的分布式离群点检测算法 王习特 申德荣 白 梅 聂铁铮 寇 月 于 戈 　 　 　 　 　 （东北大学信息科学与工程学院 沈阳 １１０００４） 　 　 摘 要 离群点检测是数据管理领域中的热点问题之一，在许多方面都有着广泛应用，如信用卡诈骗、网络入侵检 　 　 测、环境监测等 目前现有的离群点检测算法大多针对集中式的处理环境 但随着数据规模的不断增长，传统的集 ． ． 中式算法处理效率受限，无法满足用户日益增长的需求 针对上述问题，文中提出了一种新型的分布式离群点检测 ． 算法 首先，在数据存储阶段（即预处理），提出了 （ ）数据划分算法 该算法 ． ＢＤＳＰＢａｌａｎｃｅＤｒｉｖｅｎＳａｔｉａｌＰａｒｔｉｔｉｏｎｉｎ ． ｐ ｇ 可以有效地均衡每个计算节点的工作负载，并实现良好的过滤效果 此外，为划分所得到的每个块设计了一种全新 ． 的编码方式，可以快速地确定块与块之间的相邻关系，降低网络开销 基于 算法，提出了 （ ． ＢＤＳＰ ＢＯＤ ＢＤＳＰｂａｓｅｄ ）分布式离群点检测算法 该算法包括 个步骤：在每个计算节点本地，利用 树索引进行批量过 ＯｕｔｌｉｅｒＤｅｔｅｃｔｉｏｎ ． ２ Ｒ 滤，快速地计算离群点并得到本地候选集；利用 ＢＤＳＰ中提供的块编码确定需要相互通信的节点，使用少量的网络 开销得到最终结果 最后，通过大量实验验证了文中所提出的 和 算法的有效性 实验结果表明，相对于 ． ＢＤＳＰ ＢＯＤ ． 现有算法，文中算法可以显著地提高计算效率并大幅降低网络开销． 关键词 离群点检测；分布式计算；大数据；数据划分；数据管理；大规模数据 　 中图法分类号 号 ／ ＴＰ３０１ 犇犗犐 １０．１１８９７ＳＰ．Ｊ．１０１６．２０１６．０００３６ 　　　 ： 犅犗犇 犃狀犈犳犳犻犮犻犲狀狋犃犾狅狉犻狋犺犿犳狅狉犇犻狊狋狉犻犫狌狋犲犱犗狌狋犾犻犲狉犇犲狋犲犮狋犻狅狀 犵 ＷＡＮＧＸｉＴｅ ＳＨＥＮＤｅＲｏｎ ＢＡＩＭｅｉ ＮＩＥＴｉｅＺｈｅｎ ＫＯＵＹｕｅ ＹＵＧｅ