基于Spark框架的高效KNN中文文本分类算法

于苹苹+倪建成+姚彬修+李淋淋+曹博

摘 要：针对K-最近邻（KNN）分类算法时间复杂度与训练样本数量成正比而导致的计算量大的问题以及当前大数据背景下面临的传统架构处理速度慢的问题，提出了一种基于Spark框架与聚类优化的高效KNN分类算法。该算法首先利用引入收缩因子的优化K-medoids聚类算法对训练集进行两次裁剪；然后在分类过程中迭代K值获得分类结果，并在计算过程中结合Spark计算框架对数据进行分区迭代实现并行化。实验结果表明，在不同数据集中传统K-最近邻算法、基于K-medoids的K-最近邻算法所耗费时间是所提Spark框架下的K-最近邻算法的一个范围3.92～31.90倍，所提算法具有较高的计算效率，相较于Hadoop平台有较好的加速比，可有效地对大数据进行分类处理。

关键词：K-最近邻；聚类；收缩因子；K-medoids；Spark；并行化计算

中图分类号： TP391.1

文献标志码：A

文章编号：1001-9081（2016）12-3292-06