一種并行化的分類算法研究

李慧彥

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

關(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ì)。從海量的數(shù)據(jù)中尋獲有意義的信息以提供更佳體驗(yàn)，必須采用有效的數(shù)據(jù)挖掘技術(shù)，其中K-Nearest Neighbor（KNN）算法是時(shí)下常用的一種數(shù)據(jù)挖掘算法，但KNN計(jì)算的時(shí)間復(fù)雜度較高，在大數(shù)據(jù)處理面前，則難掩效率遜色的不爭(zhēng)事實(shí)。目前，許多學(xué)者采用MapReduce進(jìn)行KNN算法的并行化構(gòu)建，執(zhí)行效率則得到了顯著提高。MapReduce計(jì)算框架對(duì)迭代計(jì)算缺乏一種特性支持，即在并行計(jì)算的各個(gè)階段提供重要的數(shù)據(jù)共享時(shí)，Map函數(shù)需要將中間結(jié)果寫(xiě)入到磁盤(pán)，而Reduce函數(shù)在進(jìn)行讀取時(shí)將增加了磁盤(pán)IO?；诖?，本文即主要結(jié)合KNN算法的自身特點(diǎn)展開(kāi)了Spark技術(shù)在KNN算法上的應(yīng)用研究。

1Spark簡(jiǎn)介

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

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