基于MapReduce和Spark的大規(guī)模壓縮模糊K-近鄰算法

王謨瀚,翟俊海,b,齊家興

(河北大學(xué) a.數(shù)學(xué)與信息科學(xué)學(xué)院; b.河北省機(jī)器學(xué)習(xí)與計(jì)算智能重點(diǎn)實(shí)驗(yàn)室,河北 保定 071002)

0 概述

K-近鄰(K-Nearest Neighbor,K-NN)[1]是一種常用的分類方法,廣泛應(yīng)用于模式識(shí)別、數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)等領(lǐng)域。K-NN方法簡(jiǎn)單且易于編程實(shí)現(xiàn),但是其存在2個(gè)問(wèn)題,一是對(duì)測(cè)試樣例進(jìn)行分類時(shí)需要存儲(chǔ)訓(xùn)練集中的所有樣例,并計(jì)算測(cè)試樣例與訓(xùn)練集中所有樣例之間的距離,二是對(duì)于每一個(gè)測(cè)試樣例,用訓(xùn)練集中的樣例對(duì)它們進(jìn)行分類時(shí),每個(gè)訓(xùn)練樣例被認(rèn)為是同等重要的。

針對(duì)第一個(gè)問(wèn)題,HART[2]于1968年提出了壓縮近鄰(Condensed Nearest Neighbor,CNN)算法。但是,CNN算法對(duì)噪聲非常敏感,且其結(jié)果與樣例選擇順序有關(guān)。對(duì)此,研究人員提出了較多改進(jìn)算法,如RNN(Reduced Nearest Neighbor)[3]、ENN(Edited Nearest Neighbor)[4]和ICF(Iterative Case Filtering)[5]等。近年來(lái),針對(duì)K-NN對(duì)測(cè)試樣例進(jìn)行分類時(shí)需存儲(chǔ)訓(xùn)練集中所有樣例的問(wèn)題,學(xué)者們也提出了一些較好的解決方法。HOU等人[6]將哈希技術(shù)與決策樹(shù)相結(jié)合,提出基于樹(shù)的緊哈希方法,該方法可顯著提高近鄰樣例的搜索效率。梁聰?shù)热薣7]提出一種基于參考點(diǎn)的改進(jìn)K-NN分類算法。該算法依據(jù)點(diǎn)到樣本距離的方差選擇參考點(diǎn),并賦予參考點(diǎn)自適應(yīng)權(quán)重,與基本K-NN算法及kd-tree近鄰算法相比,其具有較高的分類精度及較低的時(shí)間復(fù)雜度?；谧V哈希技術(shù),WAN等人[8]提出針對(duì)高維數(shù)據(jù)的近似近鄰搜索算法。基于分布式哈希技術(shù),文慶福等人[9]提出一種近似近鄰搜索方法。ALVAR等人[10]使用局部敏感哈希技術(shù),提出針對(duì)大規(guī)模數(shù)據(jù)集的樣例選擇算法,該算法的時(shí)間復(fù)雜度達(dá)到線性級(jí)。針對(duì)投影哈希中投影誤差較大、二進(jìn)制編碼時(shí)原始信息丟失嚴(yán)重等問(wèn)題,楊定中等人[11]提出一種近似最近鄰搜索方法,該方法通過(guò)多階段量化策略降低編碼過(guò)程中的投影及量化誤差。羅辛等人[12]提出一種基于相似度支持度的最近鄰度量方法,其在保證分類精度的前提下降低了計(jì)算復(fù)雜度。喬玉龍等人[13]利用向量的方差和小波域中的逼近系數(shù)得出2個(gè)重要不等式,利用不等式排除不可能成為K-近鄰的向量,進(jìn)而降低了計(jì)算復(fù)雜度。受交叉驗(yàn)證思想的啟發(fā),ZHAI等人[14]提出交叉樣例選擇算法,該算法可解決大規(guī)模樣例的選擇問(wèn)題。SONG等人[15]將針對(duì)分類問(wèn)題的樣例選擇算法移植到回歸場(chǎng)景,提出一種針對(duì)K-NN回歸問(wèn)題的排序樣例選擇算法,其擴(kuò)大了樣例選擇的應(yīng)用范圍。

近年來(lái),大數(shù)據(jù)技術(shù)在很多領(lǐng)域得到廣泛關(guān)注與應(yīng)用,一些科研人員針對(duì)大數(shù)據(jù)的近鄰搜索問(wèn)題進(jìn)行了研究?；陂_(kāi)源大數(shù)據(jù)平臺(tái),MUJA等人[16]提出具有可擴(kuò)展性的最近鄰算法?；贛apReduce大數(shù)據(jù)計(jì)算平臺(tái),ZHAI等人[17]設(shè)計(jì)基于投票機(jī)制和隨機(jī)權(quán)網(wǎng)絡(luò)的大數(shù)據(jù)樣例選擇算法。基于Spark大數(shù)據(jù)計(jì)算平臺(tái),MAILLO等人[18]提出大數(shù)據(jù)K-近鄰搜索算法。SONG等人[19]對(duì)基于MapReduce的K-NN算法進(jìn)行了具體的理論分析。

針對(duì)第二個(gè)問(wèn)題,KELLER[20]于1985年提出了模糊K-NN算法。然而,模糊K-NN算法依然存在上述第一個(gè)問(wèn)題。為此,ZHAI等人[21]提出了壓縮模糊K-近鄰(Condensed Fuzzy K-NN,CFKNN)算法。但是,CFKNN算法僅適用于中小數(shù)據(jù)場(chǎng)景,在大數(shù)據(jù)環(huán)境中,CFKNN會(huì)出現(xiàn)計(jì)算效率低的問(wèn)題,甚至不可實(shí)現(xiàn)。此外,CFKNN的樣例選擇采用靜態(tài)機(jī)制,導(dǎo)致該算法的性能提升存在局限性。

為了解決上述問(wèn)題,本文基于MapReduce和Spark提出2種大規(guī)模壓縮模糊K-近鄰算法。將CFKNN算法擴(kuò)展到大數(shù)據(jù)環(huán)境,在MapReduce和Spark 2種并行計(jì)算框架上實(shí)現(xiàn)面向大規(guī)模數(shù)據(jù)環(huán)境的壓縮模糊K-近鄰算法,以降低CFKNN的計(jì)算復(fù)雜度并縮短算法的運(yùn)行時(shí)間。在樣例選擇過(guò)程中,對(duì)閾值進(jìn)行動(dòng)態(tài)調(diào)整,從而提高算法的動(dòng)態(tài)特性。

1 相關(guān)知識(shí)

1.1 CFKNN算法

設(shè)T是訓(xùn)練集,S是所選樣例的集合,C為訓(xùn)練集的類別屬性,訓(xùn)練集共分為p類。在初始時(shí),從訓(xùn)練集T中的每類隨機(jī)選擇一個(gè)樣例加入S,然后根據(jù)算法1計(jì)算S中樣例的模糊隸屬度,用算法2確定x的類別隸屬度,并通過(guò)類別隸屬度計(jì)算樣例x的信息熵。如果樣例x的信息熵大于所設(shè)閾值 ,則將樣例x加入到S中,否則丟棄x。當(dāng)訓(xùn)練集T為空時(shí),算法終止,輸出所選樣例集合S。CFKNN算法的偽代碼如算法3所示。

算法1模糊隸屬度算法

輸入所選樣例集合S

輸出樣例的隸屬度μij=μj(xi),1≤i≤n,1≤j≤p

1.對(duì)于?j,1≤j≤C,計(jì)算每一類的中心Cj

2.對(duì)于?i,j,計(jì)算xi到各類中心Cj的距離dij

3.對(duì)于?i,j,按式(1)計(jì)算μij=μj(xi),1≤i≤n,1≤j≤p

4.返回樣例隸屬度

(1)

算法2F-KNN算法

輸入所選樣例集合S{(xi,yi)|xi∈Rd;yi∈Y},1≤i≤n,樣例x

輸出樣例x隸屬于每一類的隸屬度μj(x),1≤j≤p

1.利用算法1計(jì)算S中每一個(gè)樣例的類別隸屬度μij=μj(xi),構(gòu)成一個(gè)n行p列的矩陣μ

2.在S中找到x的K個(gè)近鄰

3.利用式(2)確定x的類別隸屬度:

(2)

4.輸出j(x)

算法3CFKNN算法

輸入訓(xùn)練集T,參數(shù)k和α(假設(shè)T的樣本容量為n,T中的樣例共分為p類)

輸出S?T

1.從T中的每類隨機(jī)選一個(gè)樣例加入S中

2.For x in T-S do

3.根據(jù)算法1計(jì)算S中樣例的類別隸屬度

4.用算法2確定x的類別隸屬度(μ(x,C1),μ(x,C2),…,μ(x,CP))

5.根據(jù)式(3)計(jì)算x的熵Entr(x):

(3)

6.If Entr(x)>α

7.S=S∪{x}

8.End if

9.End for

10.Return S

1.2 MapReduce和Spark并行計(jì)算框架

MapReduce[22]是由Google公司提出的一種面向大規(guī)模數(shù)據(jù)的并行計(jì)算模型,MapReduce繼承了函數(shù)式編程語(yǔ)言LISP中map函數(shù)和reduce函數(shù)的思想,采用分治策略處理大數(shù)據(jù)。在初始階段,MapReduce自動(dòng)將大數(shù)據(jù)集劃分為若干子集部署到云計(jì)算節(jié)點(diǎn)上,map階段將數(shù)據(jù)變換為鍵值對(duì)數(shù)據(jù)。reduce階段在map階段的基礎(chǔ)上,對(duì)已經(jīng)歸納好的數(shù)據(jù)做進(jìn)一步處理,得到最終計(jì)算結(jié)果。通過(guò)map和reduce 2個(gè)階段,完成對(duì)大規(guī)模數(shù)據(jù)的并行化處理。

Spark[23]是處理大數(shù)據(jù)的快速通用引擎,2009年由加州大學(xué)伯克利分校對(duì)外開(kāi)源,隨后憑借其快速、通用以及可擴(kuò)展等優(yōu)勢(shì),迅速成為Apache頂級(jí)項(xiàng)目。Spark起初是為了克服Hadoop并行計(jì)算框架的不足而被提出,發(fā)展至今,Spark已經(jīng)成為包含SparkSQL、Spark Streaming、Spark GraphX和Spark MLlib等子項(xiàng)目在內(nèi)的生態(tài)系統(tǒng)。Spark將MapReduce基于磁盤(pán)的存儲(chǔ)和容錯(cuò)機(jī)制改為基于內(nèi)存的機(jī)制,提高了計(jì)算速度。通過(guò)將執(zhí)行模型抽象為有向無(wú)環(huán)圖(Directed Acyclic Graph,DAG),并根據(jù)彈性分布式數(shù)據(jù)集(Resident Distributed Dataset,RDD)間的寬依賴和窄依賴關(guān)系,串聯(lián)或并行執(zhí)行多個(gè)階段的任務(wù),無(wú)需將不必要的中間結(jié)果輸出到HDFS(Hadoop Distributed File System)上,以此提高計(jì)算效率。

RDD和算子是Spark的核心與基礎(chǔ)。RDD是Spark中的基本數(shù)據(jù)抽象,其為不可變、可分區(qū)、可并行計(jì)算的數(shù)據(jù)集合。在具體的邏輯實(shí)現(xiàn)上,RDD將數(shù)據(jù)分為若干分區(qū),分區(qū)以分布式方式保存在云節(jié)點(diǎn)上,既可以存儲(chǔ)在內(nèi)存中,也可以存儲(chǔ)在外存中。當(dāng)某些數(shù)據(jù)需要重復(fù)使用時(shí),RDD允許用戶顯式地將數(shù)據(jù)緩存在內(nèi)存中,從而有效提高了計(jì)算速度。在對(duì)RDD中的數(shù)據(jù)進(jìn)行處理時(shí),需要通過(guò)Spark算子來(lái)實(shí)現(xiàn)相應(yīng)的數(shù)據(jù)操作。一般根據(jù)是否會(huì)觸發(fā)Spark作業(yè)執(zhí)行將Spark算子分為如下兩類:

1)轉(zhuǎn)換算子,其對(duì)RDD進(jìn)行轉(zhuǎn)換操作,將一個(gè)RDD轉(zhuǎn)換為另一個(gè)RDD。轉(zhuǎn)換算子的轉(zhuǎn)換操作是延時(shí)加載的,它們不會(huì)直接返回計(jì)算結(jié)果,只記錄轉(zhuǎn)化動(dòng)作。

2)行動(dòng)算子,其觸發(fā)Spark作業(yè)執(zhí)行,得到Spark作業(yè)的計(jì)算結(jié)果。

2 大規(guī)模壓縮模糊K-近鄰算法

2.1 算法描述

通過(guò)對(duì)原始CFKNN算法進(jìn)行分析可以得出,該算法難以在大數(shù)據(jù)環(huán)境下進(jìn)行應(yīng)用的3個(gè)主要原因具體如下:

1)在確定T中樣例x的類別隸屬度時(shí),首先需要計(jì)算集合S的隸屬度矩陣m,然后尋找k個(gè)近鄰,計(jì)算樣例x的類別隸屬度。當(dāng)訓(xùn)練集T為大數(shù)據(jù)集時(shí),集合S中樣例增多,對(duì)T中的每個(gè)樣例尋找S中的k個(gè)近鄰并計(jì)算T中每個(gè)樣例的熵值時(shí),算法計(jì)算量很大,算法運(yùn)行時(shí)間超出可接受范圍。

2)當(dāng)訓(xùn)練集為大數(shù)據(jù)集時(shí),尋找k個(gè)近鄰的計(jì)算復(fù)雜度大幅增加。

3)對(duì)所選樣例集合S不能實(shí)時(shí)更新,進(jìn)而導(dǎo)致對(duì)當(dāng)前樣例x的隸屬度和信息熵計(jì)算不準(zhǔn)確,這是導(dǎo)致原始CFKNN算法無(wú)法在大數(shù)據(jù)環(huán)境下應(yīng)用的主要原因。

針對(duì)以上問(wèn)題,本文提出大規(guī)模壓縮模糊K-近鄰算法,該算法對(duì)原始CFKNN做出如下改進(jìn):

1)針對(duì)第一個(gè)問(wèn)題,大規(guī)模壓縮模糊K-近鄰算法在計(jì)算樣例x的類別隸屬度時(shí),先在S中尋找樣例x的k個(gè)近鄰,然后只計(jì)算k個(gè)樣例的類別隸屬度,從而大幅降低了由于計(jì)算S中所有樣例的隸屬度所引起的計(jì)算復(fù)雜度(對(duì)應(yīng)算法4第5行)。

2)利用并行計(jì)算框架,在每個(gè)計(jì)算節(jié)點(diǎn)上并行地尋找集合S中樣例x的k個(gè)近鄰,從而解決第二個(gè)問(wèn)題。

3)對(duì)于第三個(gè)問(wèn)題,本文在閾值設(shè)置上引入動(dòng)態(tài)機(jī)制,對(duì)閾值進(jìn)行動(dòng)態(tài)調(diào)整,將閾值α設(shè)置為迭代次數(shù)j的單調(diào)遞減函數(shù),如式(4)所示。其中,設(shè)置初始閾值initEntropy時(shí)考慮到對(duì)應(yīng)類別數(shù)的最大熵(對(duì)應(yīng)算法4第6行)。通過(guò)引入動(dòng)態(tài)閾值機(jī)制,使得本文算法訓(xùn)練出的分類器較原始CFKNN算法具有更好的分類精度。

(4)

其中,j為當(dāng)前迭代次數(shù),n為總迭代次數(shù)。

本文基于并行計(jì)算框架的大規(guī)模壓縮模糊K-近鄰算法偽代碼如算法4所示,算法流程如圖1所示。

算法4大規(guī)模壓縮模糊K-近鄰算法

輸入數(shù)據(jù)集T,近鄰數(shù)k,閾值α,迭代次數(shù)iterations

輸出數(shù)據(jù)子集S?T

1.for iteration in iterations do

2.初始化S,T

3.根據(jù)式(3)并行計(jì)算T中每個(gè)樣例x的信息熵Entr(x)

4.根據(jù)式(4)計(jì)算α(j,n)

5.if Entropy>α(j,n)

6.S=S∪{x}

7.End if

8.輸出S

9.End for

圖1 大規(guī)模壓縮模糊K-近鄰算法流程

2.2 基于MapReduce的壓縮模糊K-近鄰算法

在原始CFKNN算法中,當(dāng)T為大數(shù)據(jù)集時(shí),針對(duì)T中的每個(gè)樣例,在S中尋找其k個(gè)近鄰以及計(jì)算T中每個(gè)樣例熵值的過(guò)程,會(huì)大幅提高算法的計(jì)算量。因此,本文將此過(guò)程通過(guò)MapReduce框架進(jìn)行并行執(zhí)行。對(duì)于T中的樣例,并行尋找S中k個(gè)近鄰并計(jì)算熵值,從而大幅縮短算法的運(yùn)行時(shí)間。隨著T中樣例數(shù)量的增加,可以通過(guò)增加計(jì)算節(jié)點(diǎn)個(gè)數(shù),使得算法維持可接受的運(yùn)算時(shí)間并容易擴(kuò)展。大規(guī)模壓縮模糊K-近鄰算法在MapReduce中的計(jì)算,即基于MapReduce的壓縮模糊K-近鄰(MR-CFKNN)算法流程如算法5所示。該算法分為Mapper階段和Reducer階段2個(gè)部分,Mapper階段包含setup和map 2個(gè)方法,Reducer階段只包含reduce方法。在Mapper階段的setup方法中,首先對(duì)數(shù)據(jù)子集S進(jìn)行初始化(算法5第3行),map方法計(jì)算輸入的樣例t∈T在S中的k個(gè)近鄰(算法5第6行),由k個(gè)近鄰計(jì)算出t的熵值Entropy(算法5第7行),若Entropy大于熵的閾值α,則輸出樣例t。Reducer階段不做任何操作直接輸出所選樣例。

算法5MR-CFKNN算法

輸入數(shù)據(jù)集T,近鄰數(shù)k,閾值α

輸出數(shù)據(jù)子集S?T

1.ClassMapper

2.執(zhí)行setup()方法,對(duì)所需資源進(jìn)行初始化

3.初始化數(shù)據(jù)子集S?T

4.初始化參數(shù)k,initEntropy

5.使用map方法對(duì)樣例進(jìn)行格式化操作,map(sid id,instance t)

6.使用findKNN方法找到當(dāng)前樣例的k個(gè)近鄰,Array kNearestNeighbor=findKNN(t,S,k)

7.使用fKNN方法計(jì)算當(dāng)前樣例的熵,Entropy=fKNN(kNearestNeighbor,t)

8.If Entropy>α

9.context.write(NullWritable,t)

10.End if

11.Mapper end

12.Class Reducer

13.使用reduce方法對(duì)樣例進(jìn)行格式化,reduce(NullWritable,[t(1),t(2),…])

14.for t in[t(1),t(2),…] do

15.輸出所選樣例,context.write(NullWritable,t)

16.End for

17.Reducer end

2.3 基于Spark的壓縮模糊K-近鄰算法

算法6Spark-CFKNN算法

輸入數(shù)據(jù)集T,近鄰數(shù)k,閾值α,迭代次數(shù)iterations

輸出數(shù)據(jù)子集S?T

1.對(duì)數(shù)據(jù)集T進(jìn)行初始化RDD操作,valtrainInitRDD = sc.textFile(T)

2.得到初始樣例集合D,var dRDD = trainInitRDD.combineByKey().map().flatmap()

3.得到T與D的差集,var tRDD = trainInitRDD.subtract(dRDD)

4.for(i<-0 until iterations)do

5.對(duì)數(shù)據(jù)集D進(jìn)行廣播操作,var dInsbroad = sc.broadcast(dRDD.collect())

6.valdistanceRDD=tRDD.map(line => {

7.for(i<-0 until dInsbroad.value.length) do

8.計(jì)算當(dāng)前樣例與D中樣例的距離,Distance(dInsbroad.value(i),line)

9.End for

10.})

11.valtEntropyAndSelectRDD= distanceRDD.map(line=>{

12.計(jì)算當(dāng)前樣例的隸屬度,memShipDevide(trainInsMemberShipCalc(kNearestNeighbor))

13.計(jì)算當(dāng)前樣例的熵值,val Entropy=calcEntropy()

14.If Entropy>α

15.Sm=Sm∪{x}

16.Tm=Tm-{x}

17.End if

18.})

19.將當(dāng)前迭代所選樣例與D求并集,dRDD = dRDD.union(tEntropyAndSelectRDD)

20.將T與當(dāng)前迭代所選樣例做差集,tRDD = tRDD.subtract(tEntropyAndSelectRDD)

21.End for

3 實(shí)驗(yàn)結(jié)果與分析

p(x|ω1)～N(0,I)

表1 數(shù)據(jù)集基本信息

表2 高斯分布參數(shù)

本文從文件數(shù)目、同步次數(shù)、分類精度、所選樣例個(gè)數(shù)以及算法運(yùn)行時(shí)間等方面,將MR-CFKNN算法和Spark-CFKNN算法進(jìn)行對(duì)比。此外,分別將原始CFKNN算法和本文算法所篩選出的樣例作為訓(xùn)練集,使用KNN算法對(duì)測(cè)試集進(jìn)行分類并比較分類精度。在實(shí)驗(yàn)過(guò)程中,分別從4個(gè)大數(shù)據(jù)集中隨機(jī)選取部分樣例作為測(cè)試集,測(cè)試集基本信息如表3所示。實(shí)驗(yàn)所用的大數(shù)據(jù)平臺(tái)環(huán)境的配置信息如表4所示, 大數(shù)據(jù)平臺(tái)環(huán)境的節(jié)點(diǎn)規(guī)劃如表5所示。

表3 測(cè)試集基本信息

表4 實(shí)驗(yàn)配置信息

表5 大數(shù)據(jù)平臺(tái)環(huán)境的節(jié)點(diǎn)規(guī)劃

表6所示為原始CFKNN算法與本文大規(guī)模壓縮模糊K-近鄰算法在Guassian1數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。從表6可以看出,CFKNN算法只對(duì)所有訓(xùn)練樣例進(jìn)行1次迭代,MR-CFKNN算法和Spark-CFKNN算法分別進(jìn)行了3次、4次和5次迭代。表中所示的分類精度是分別將原始CFKNN算法、本文算法所篩選出的樣例集合作為訓(xùn)練集,使用KNN算法進(jìn)行分類精度測(cè)試的結(jié)果。大規(guī)模壓縮模糊K-近鄰算法的分類精度優(yōu)于原始CFKNN算法的主要原因有2點(diǎn):首先,CFKNN算法只對(duì)訓(xùn)練集進(jìn)行1次迭代,為了保證所選樣例更具代表性,同時(shí)考慮到閾值為固定值,所以CFKNN算法需要將閾值設(shè)置為中間數(shù)值,這會(huì)導(dǎo)致在算法運(yùn)行初期選入較多的非邊界樣例;其次,大規(guī)模壓縮模糊K-近鄰算法考慮算法運(yùn)行初期訓(xùn)練樣例的熵值普遍較高的情況,且隨著算法的不斷迭代,訓(xùn)練樣例的熵值逐漸接近真實(shí)值,所以其引入了動(dòng)態(tài)閾值策略,使閾值隨著迭代次數(shù)的增加而逐漸衰減,以此來(lái)克服原始CFKNN算法的缺點(diǎn)。以上2點(diǎn)使得大規(guī)模壓縮模糊K-近鄰算法的分類精度優(yōu)于原始CFKNN算法,說(shuō)明本文算法所篩選出的樣例更具代表性。

表6 3種算法的分類精度比較

加速比(SpeedUp)是衡量并行計(jì)算算法性能和效果的常用指標(biāo),傳統(tǒng)的加速比計(jì)算方式如式(5)所示,其中,Tbest為串行算法在一臺(tái)計(jì)算機(jī)上的最優(yōu)運(yùn)行時(shí)間,T(N)為并行算法在N臺(tái)計(jì)算機(jī)上的運(yùn)行時(shí)間。

(5)

由于本文大規(guī)模壓縮模糊K-近鄰算法改變了CFKNN算法對(duì)訓(xùn)練集只進(jìn)行1次迭代的計(jì)算方式,因此本文通過(guò)式(6)來(lái)計(jì)算Spark-CFKNN算法的加速比,以此為例來(lái)衡量通過(guò)大規(guī)模壓縮模糊K-近鄰算法取得的并行化效果,其中,Tsingle-best為Spark-CFKNN算法在單一節(jié)點(diǎn)上的最優(yōu)運(yùn)行時(shí)間。

(6)

表7所示為Spark-CFKNN算法在單一節(jié)點(diǎn)和7個(gè)節(jié)點(diǎn)上的運(yùn)行時(shí)間,從表7可以看出,本文算法大幅縮短了運(yùn)行時(shí)間,具有較高的加速比。

表7 Spark-CFKNN算法在Gaussian1數(shù)據(jù)集上的加速比

圖2所示為不同迭代次數(shù)下Spark-CFKNN和MR-CFKNN的分類精度。從圖2可以看出,Spark-CFKNN和MR-CFKNN的分類精度變化趨勢(shì)大致相同,說(shuō)明2個(gè)算法在實(shí)現(xiàn)細(xì)節(jié)上具有邏輯一致性,同時(shí)也沒(méi)有因?yàn)槠脚_(tái)間運(yùn)行機(jī)制的差異而對(duì)分類結(jié)果造成影響。此外,由圖2可知,分類精度和迭代次數(shù)并不成簡(jiǎn)單的正比關(guān)系,即分類精度并不會(huì)隨著迭代次數(shù)的增加而持續(xù)增長(zhǎng),當(dāng)達(dá)到一定迭代次數(shù)時(shí),分類精度會(huì)趨于恒定,這也說(shuō)明為了提高分類精度而持續(xù)增加迭代次數(shù)的做法不可行。

圖2 Gaussian1數(shù)據(jù)集上分類精度隨迭代次數(shù)的變化情況

根據(jù)吳信東等人[24]的研究成果,本文對(duì)2種大數(shù)據(jù)平臺(tái)在不同迭代次數(shù)下的文件數(shù)目、同步次數(shù)和算法運(yùn)行時(shí)間進(jìn)行對(duì)比,結(jié)果如表8～表12所示。由于文件數(shù)目和同步次數(shù)只與大數(shù)據(jù)平臺(tái)的調(diào)度機(jī)制有關(guān)而與數(shù)據(jù)集無(wú)關(guān),因此對(duì)該指標(biāo)進(jìn)行對(duì)比時(shí)不區(qū)分?jǐn)?shù)據(jù)集。

表8 不同迭代次數(shù)下文件數(shù)目和同步次數(shù)的比較

表9 2種平臺(tái)在Gaussian1數(shù)據(jù)集下的性能對(duì)比

表10 2種平臺(tái)在Gaussian2數(shù)據(jù)集下的性能對(duì)比

表11 2種平臺(tái)在Skin Segmentation數(shù)據(jù)集下的性能對(duì)比

表12 2種平臺(tái)在Healthy Older People數(shù)據(jù)集下的性能對(duì)比

文件數(shù)目主要指中間文件數(shù)目,因?yàn)樗惴ㄔ谶\(yùn)行過(guò)程中所產(chǎn)生的中間文件數(shù)量不僅會(huì)占用內(nèi)存空間,還會(huì)影響磁盤(pán)的I/O性能,最終導(dǎo)致算法運(yùn)行時(shí)間延長(zhǎng)。在MapReduce中,每次的shuffle操作會(huì)對(duì)map產(chǎn)生的中間結(jié)果進(jìn)行排序和歸并操作,MapReduce通過(guò)歸并和排序操作減少了中間結(jié)果傳輸?shù)臄?shù)據(jù)量,以此保證每一個(gè)map只產(chǎn)生一個(gè)中間數(shù)據(jù)文件,達(dá)到減少文件數(shù)目的目的。在Spark中,默認(rèn)沒(méi)有對(duì)中間數(shù)據(jù)進(jìn)行預(yù)排序和歸并操作,所以只能將不同分區(qū)的數(shù)據(jù)分別保存在單個(gè)文件中,分區(qū)個(gè)數(shù)即為中間文件數(shù)目。從表8可以看出,Spark-CFKNN的中間文件數(shù)目明顯高于MR-CFKNN,且分區(qū)數(shù)并不隨著迭代次數(shù)的增加而增加,原因是Spark-CFKNN通過(guò)增加分區(qū)數(shù)目降低了每個(gè)分區(qū)所需的內(nèi)存空間,減少了每個(gè)task的執(zhí)行時(shí)間,但同時(shí)也造成了中間文件數(shù)目過(guò)多的問(wèn)題,此外,Spark-CFKNN通過(guò)設(shè)置Spark的環(huán)境變量及對(duì)reparation算子進(jìn)行重分區(qū)操作,使得文件數(shù)目保持了恒定。

對(duì)于同步次數(shù),MapReduce為同步模型,即在所有的map操作結(jié)束后才能進(jìn)行reduce操作。而Spark通過(guò)RDD間的寬依賴、窄依賴關(guān)系以及管道化操作(pipeline),提高了其并行化程度及Spark中算法的局部性能。

算法的執(zhí)行時(shí)間T會(huì)受到輸入文件時(shí)間Tread、中間數(shù)據(jù)排序時(shí)間Tsort、中間數(shù)據(jù)傳遞時(shí)間Ttrans和輸出文件到HDFS時(shí)間Twrite的影響。因?yàn)閷?duì)每一輪的計(jì)算結(jié)果都進(jìn)行了廣播,2個(gè)算法的執(zhí)行時(shí)間差異主要受到MapReduce和Spark運(yùn)行機(jī)制及調(diào)度策略的影響,所以最終只考慮Tsort和Ttrans對(duì)T造成的影響。對(duì)于中間數(shù)據(jù)排序時(shí)間Tsort,由于MapReduce的shuffle過(guò)程會(huì)對(duì)中間結(jié)果進(jìn)行排序和歸并操作,因此若假設(shè)每個(gè)map任務(wù)有N條數(shù)據(jù),每個(gè)reduce任務(wù)有M條數(shù)據(jù),則MapReduce的中間數(shù)據(jù)排序時(shí)間TMR-sort=N·logaN+R=O(N·logaN)。而在Spark中,默認(rèn)沒(méi)有對(duì)中間數(shù)據(jù)進(jìn)行預(yù)排序的操作,因此,Spark的中間數(shù)據(jù)排序時(shí)間TSpark-sort=0。中間數(shù)據(jù)傳遞時(shí)間Ttrans主要指將map任務(wù)運(yùn)算的數(shù)據(jù)傳送到reduce任務(wù)所消耗的時(shí)間,Ttrans主要由map任務(wù)輸出的中間數(shù)據(jù)大小|D|和網(wǎng)絡(luò)傳輸速度Ct所決定?？梢钥闯?在網(wǎng)絡(luò)傳輸速度相同的情況下,Ttrans與中間數(shù)據(jù)大小|D|成正比。由此可知,在相同的迭代次數(shù)下,中間數(shù)據(jù)傳遞時(shí)間Ttrans主要受同步次數(shù)的影響。由于Spark引入了管道化操作(pipeline),因此可以減少同步次數(shù),提高并行化程度。由表8中的同步次數(shù)可以看出,隨著迭代次數(shù)的增加,相比MapReduce,Spark在中間數(shù)據(jù)傳遞時(shí)間Ttrans上的優(yōu)勢(shì)越來(lái)越明顯。

綜上,由于MR-CFKNN與Spark-CFKNN算法的程序設(shè)計(jì)不同,Spark-CFKNN雖然因?yàn)樵黾恿朔謪^(qū)數(shù)而導(dǎo)致Spark的文件數(shù)目遠(yuǎn)多于MapReduce,但因?yàn)?個(gè)大數(shù)據(jù)框架的調(diào)度機(jī)制存在差異,Spark通過(guò)引入管道化操作減少了同步次數(shù),使得中間數(shù)據(jù)傳輸時(shí)間隨著迭代次數(shù)的增加而越來(lái)越優(yōu)于MapReduce?；趦?nèi)存的Spark可以將算法運(yùn)行過(guò)程中重復(fù)用到的中間數(shù)據(jù)結(jié)果緩存到內(nèi)存中,減少因?yàn)橹貜?fù)計(jì)算所消耗的時(shí)間,最終使得Spark-CFKNN算法的運(yùn)行效率優(yōu)于MR-CFKNN算法。此外,從表9～表12可以看出,Skin Segmentation和Healthy Older People數(shù)據(jù)集在算法運(yùn)行時(shí)間上的差異小于Gaussian1和Gaussian2數(shù)據(jù)集,導(dǎo)致該現(xiàn)象的原因是因?yàn)榍皟烧叩臄?shù)據(jù)規(guī)模小于后兩者。

分別使用原始數(shù)據(jù)集和本文算法迭代5次的所選樣例集合做訓(xùn)練集,使用KNN算法對(duì)分類精度進(jìn)行測(cè)試,結(jié)果如表13所示。從表13可以看出,除了Healthy Older People數(shù)據(jù)集以外,在其余3個(gè)數(shù)據(jù)集上本文算法都實(shí)現(xiàn)了精度提升,表明該算法具有有效性。

表13 原始數(shù)據(jù)集和本文算法所選樣例集合的最優(yōu)分類精度對(duì)比

4 結(jié)束語(yǔ)

本文對(duì)CFKNN算法進(jìn)行改進(jìn),提出一種在大數(shù)據(jù)環(huán)境下具有良好可擴(kuò)展性的大規(guī)模壓縮模糊K-近鄰算法。該算法在樣例選擇的過(guò)程中引入動(dòng)態(tài)機(jī)制,使得所選樣例更具代表性。實(shí)驗(yàn)結(jié)果表明,與原始CFKNN算法相比,該算法具有更高的分類精度和加速比,將基于MapReduce和Spark的2種大規(guī)模壓縮模糊K-近鄰算法相比,兩者在樣例選擇個(gè)數(shù)和分類精度上相近,但在文件數(shù)目、同步次數(shù)和運(yùn)行時(shí)間上存在比較明顯的差異。下一步將對(duì)動(dòng)態(tài)選擇的閾值是否為最優(yōu)閾值以及樣例初始化是否影響算法性能等問(wèn)題進(jìn)行深入研究。