Spark下的并行多标签最近邻算法

Parallel multi-label K-nearest neighbor algorithm based on Spark

随着大数据时代的到来,大规模多标签数据挖掘方法受到广泛关注。多标签最近邻算法MLKNN是一种简单高效、应用广泛的多标签分类方法,其分类精度在很多应用中都高于其他常见的多标签学习方法。然而随着需要处理的数据规模越来越大,传统串行ML-KNN算法已经难以满足大数据应用中时间和存储空间上的限制。结合Spark的并行机制和其基于内存的迭代计算特点,提出了一种基于Spark并行框架的ML-KNN算法SML-KNN。在Map阶段分别找到待预测样本每个分区的K近邻,随后Reduce阶段根据每个分区的近邻集合确定最终的K近邻,最后并行地对近邻的标签集合进行聚合,通过最大化后验概率准则输出待预测样本的目标标签集合。串行和并行环境下的对比实验结果表明,SML-KNN在保证分类精度的前提下性能与计算资源呈近似线性关系,提高了ML-KNN算法对大规模多标签数据的处理能力。

With the advent of big data era, applications of large-scale multi-label data mining have attracted extensive attention. The Multi-Label K-Nearest Neighbor （ML-KNN） is a simple, efficient and widely used method which outperforms other traditional multi-label learning algorithms in many realworld applications. However, as an increasing number of data need to be dealt with, the ML-KNN algorithm is unable to meet the requirements of time and memory space. Combined with the parallel mechanism and iterative computation in the memory of Spark, we propose an algorithm based on Spark distributed in-memory computing platform, named SML-KNN. First, in the stage of map,we try to find the K nearest neighbors for each partition of the samples to be tested. Then in the reduce stage, we determine the final K nearest neighbors according to the K nearest neighbors of each partition. Finally, we cluster the label sets of the K nearest neighbors in parallel, and output the target label sets using the maximum posterior probability （MAP） principle. The experiments in stand-alone and cluster environments show that in the premise of ensuring the classification accuracy, the performance of the SML-KNN has an approximate linear relationship with computing resources, and the proposed algorithm can enhance the processing ability of the ML-KNN when dealing with large scale multi-label data.