李慧彥

摘要：研究并實現(xiàn)TJIT Spark的KNN算法的并行構(gòu)建。分析了MapReduce模型和Spark在處理迭代計算方面的優(yōu)劣，結(jié)合KNN算法的自身特點設(shè)計了對應(yīng)的Map算子和Reduce算子，實現(xiàn)了KNN算法的spark并行化。實驗結(jié)果表明，較傳統(tǒng)的KNN串行算法和MapReduce并行KNN算法，基于Spark的并行KNN分類算法具有較好的效率和較高的可擴展性。

關(guān)鍵詞：Spark；KNN：MapReduce

0引言

隨著信息技術(shù)的發(fā)展，在電子商務(wù)、科學(xué)研究和互聯(lián)網(wǎng)應(yīng)用等領(lǐng)域積累了海量的數(shù)據(jù)資源，而且數(shù)據(jù)量正呈現(xiàn)激增態(tài)勢。從海量的數(shù)據(jù)中尋獲有意義的信息以提供更佳體驗，必須采用有效的數(shù)據(jù)挖掘技術(shù)，其中K-Nearest Neighbor（KNN）算法是時下常用的一種數(shù)據(jù)挖掘算法，但KNN計算的時間復(fù)雜度較高，在大數(shù)據(jù)處理面前，則難掩效率遜色的不爭事實。目前，許多學(xué)者采用MapReduce進行KNN算法的并行化構(gòu)建，執(zhí)行效率則得到了顯著提高。MapReduce計算框架對迭代計算缺乏一種特性支持，即在并行計算的各個階段提供重要的數(shù)據(jù)共享時，Map函數(shù)需要將中間結(jié)果寫入到磁盤，而Reduce函數(shù)在進行讀取時將增加了磁盤IO。基于此，本文即主要結(jié)合KNN算法的自身特點展開了Spark技術(shù)在KNN算法上的應(yīng)用研究。

1Spark簡介

Spark是伯克利大學(xué)在2012年提出的一個基于內(nèi)存的分布式計算框架，其核心是彈性分布式數(shù)據(jù)集（ResilientDistributed Datasets，RDD），這是對集群上并行處理數(shù)據(jù)的分布式內(nèi)存的抽象。spark是一個大數(shù)據(jù)分布式編程框架，具有Map算子、Reduce算子以及計算框架，能夠?qū)崿F(xiàn)任務(wù)調(diào)度、RPC、序列化和壓縮，同時還可為運行在其上的上層組件提供API。由于引進RDD概念，Spark可以在計算中將中間輸出和結(jié)果分布式緩存在各個節(jié)點內(nèi)存中，并且允許用戶進行重復(fù)使用，省去了磁盤大量的IO操作，從而大幅縮短了訪問時間。

RDD可以看作是對各種數(shù)據(jù)計算模型的統(tǒng)一抽象，Spark的計算過程主要是RDD的迭代計算過程，具體如圖1所示。spark應(yīng)用在集群上以獨立的執(zhí)行器運行在不同的節(jié)點上，主程序中以SparkContext對象來設(shè)計展開總體調(diào)度。目前，YARN、Mesos、Standalone、EC2等都可以作為Spark的集群資源管理器，集群資源管理器的作用可描述為在不同Spark應(yīng)用間掌控處理資源分配。集群資源管理器主要用于資源的分配與管理，就是將各個節(jié)點上的內(nèi)存、CPU等資源分配給應(yīng)用程序以盡可能實現(xiàn)數(shù)據(jù)的本地化計算。運行架構(gòu)即如圖2所示。