基于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