基于Spark平台的并行KNN异常检测算法

作者：冯贵兰; 周文刚

来源：计算机科学, 2018, 45(S2): 349-366.

• Spark平台
• 并行
• K近邻
• 异常检测

随着大数据时代的到来,异常检测受到了广泛关注。针对传统KNN异常检测算法处理速度和计算资源的瓶颈,以及Hadoop平台上的MapReduce不能友好支持迭代计算和基于内存计算等问题,提出了一种基于Spark平台的并行KNN异常检测算法。该算法首先对数据集进行分区和广播,然后用map函数计算数据集在每个分区的K近邻,使用reduce函数归并map函数的输出计算全局K近邻得到异常度,将异常度前n个对象视为异常。与传统KNN异常检测算法相比,在保证检测精度的前提下该算法的性能与计算资源呈近似线性关系;与其他并行异常检测算法相比,该算法无需额外扩展数据,支持迭代,而且通过在内存中缓存中间结果来减少I/O花销。实验结果证明,该算法可以提高KNN算法在大规模数据上的异常检测效率。

• 单位
  中国民航飞行学院; 现代教育技术中心