异构分布式环境中的并行离群点检测算法

摘要

离群点检测是数据挖掘领域研究的热点之一,主要目的是识别出数据集中异常但有价值的数据点.随着数据规模不断扩大,使得处理海量数据的效率降低,随即引入分布式算法.目前现有的分布式算法大都用于解决同构分布式的处理环境,但在实际应用中,由于参与分布式计算的处理机配置的差异,现有的分布式离群点检测算法不能很好地适用于异构分布式环境.针对上述问题,本文提出一种面向异构分布式环境的离群点检测算法.首先提出基于网格的动态数据划分方法(Gird-based Dynamic Data Partitioning,GDDP),充分利用各处理机的计算资源,同时根据数据点的空间位置信息进行数据划分,可有效减少网络通信.其次基于GDDP算法,提出了异构分布式环境中并行的离群点检测算法(GDDP-based Outlier Detection Algorithm,GODA).该算法包括2个阶段:在每个处理机本地,按照索引中数据点的顺序进行过滤,通过2次扫描得到离群点候选集;判断候选离群点需要进行网络通信的处理机,使用较低网络开销得出全局离群点.最后,通过大量实验验证了本文提出的GDDP和GODA算法的有效性.