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

来源：计算机应用杂志2016年第12期北京时间：

作者：于苹苹, 倪建成, 姚彬修, 李淋淋, 曹博

单位：1. 曲阜师范大学 信息科学与工程学院, 山东 日照 276826;2. 曲阜师范大学 软件学院, 山东 曲阜 273100

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

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

基金资助：国家自然科学基金资助项目（61402258）；山东省本科高校教学改革研究项目（2015M102）；校级教学改革研究项目（jg05021*）。