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

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

0 概述

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

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

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

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

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

1 相關(guān)知識

1.1 CFKNN算法

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

算法1模糊隸屬度算法

輸入所選樣例集合S

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

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

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

3.對于?i,j,按式(1)計算μ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計算S中每一個樣例的類別隸屬度μij=μj(xi),構(gòu)成一個n行p列的矩陣μ

2.在S中找到x的K個近鄰

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

(2)

4.輸出j(x)

算法3CFKNN算法

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

輸出S?T

1.從T中的每類隨機選一個樣例加入S中

2.For x in T-S do

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

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

5.根據(jù)式(3)計算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并行計算框架

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

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

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

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

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

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

2.1 算法描述

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

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

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

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

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

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

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

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

(4)

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

本文基于并行計算框架的大規(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)并行計算T中每個樣例x的信息熵Entr(x)

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

算法5MR-CFKNN算法

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

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

1.ClassMapper

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

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

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

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

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

7.使用fKNN方法計算當(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方法對樣例進(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.對數(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.對數(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.計算當(dāng)前樣例與D中樣例的距離,Distance(dInsbroad.value(i),line)

9.End for

10.})

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

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

13.計算當(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 實驗結(jié)果與分析

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

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

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

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

表3 測試集基本信息

表4 實驗配置信息

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

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

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

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

(5)

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

(6)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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