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

摘 要：針對(duì)K-最近鄰（KNN）分類算法時(shí)間復(fù)雜度與訓(xùn)練樣本數(shù)量成正比而導(dǎo)致的計(jì)算量大的問題以及當(dāng)前大數(shù)據(jù)背景下面臨的傳統(tǒng)架構(gòu)處理速度慢的問題，提出了一種基于Spark框架與聚類優(yōu)化的高效KNN分類算法。該算法首先利用引入收縮因子的優(yōu)化K-medoids聚類算法對(duì)訓(xùn)練集進(jìn)行兩次裁剪；然后在分類過程中迭代K值獲得分類結(jié)果，并在計(jì)算過程中結(jié)合Spark計(jì)算框架對(duì)數(shù)據(jù)進(jìn)行分區(qū)迭代實(shí)現(xiàn)并行化。實(shí)驗(yàn)結(jié)果表明，在不同數(shù)據(jù)集中傳統(tǒng)K-最近鄰算法、基于K-medoids的K-最近鄰算法所耗費(fèi)時(shí)間是所提Spark框架下的K-最近鄰算法的一個(gè)范圍3.92～31.90倍，所提算法具有較高的計(jì)算效率，相較于Hadoop平臺(tái)有較好的加速比，可有效地對(duì)大數(shù)據(jù)進(jìn)行分類處理。

關(guān)鍵詞：K-最近鄰；聚類；收縮因子；K-medoids；Spark；并行化計(jì)算

中圖分類號(hào)： TP391.1

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-9081（2016）12-3292-06