基于MPI的近鄰距離加權(quán)偏標(biāo)記學(xué)習(xí)算法之并行實(shí)現(xiàn)

王 進(jìn), 高延雨, 鄧 欣, 陳喬松

(重慶郵電大學(xué) 計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室, 重慶 400065)

傳統(tǒng)的監(jiān)督學(xué)習(xí)方法[1]都是根據(jù)已有完整監(jiān)督信息的訓(xùn)練集(即訓(xùn)練集中的樣本都有精確的標(biāo)記信息)建立分類模型,然后通過(guò)得到的分類模型對(duì)待測(cè)樣本進(jìn)行分類.但是現(xiàn)實(shí)中受外部環(huán)境、物理特性和物理資源等各方面狀況的制約,有些場(chǎng)景很難得到完整的監(jiān)督信息,例如對(duì)畫(huà)作風(fēng)格進(jìn)行評(píng)定,不同的評(píng)定者因?yàn)橹R(shí)和經(jīng)驗(yàn)不同,對(duì)同一幅畫(huà)可能有不同的評(píng)定結(jié)果,最終只能確定其屬于哪幾種風(fēng)格,無(wú)法精確到具體的一種風(fēng)格.僅知道訓(xùn)練樣本標(biāo)記候選集的場(chǎng)景可以使用偏標(biāo)記的方法來(lái)進(jìn)行處理.

偏標(biāo)記學(xué)習(xí)[2-3]是一種重要的弱監(jiān)督學(xué)習(xí)框架,具體定義如下:訓(xùn)練集中的訓(xùn)練樣本對(duì)應(yīng)多個(gè)標(biāo)記,其中只有1個(gè)標(biāo)記是真實(shí)標(biāo)記,然后根據(jù)這樣的訓(xùn)練集進(jìn)行學(xué)習(xí)和對(duì)測(cè)試集的類別進(jìn)行預(yù)測(cè).目前,偏標(biāo)記學(xué)習(xí)已經(jīng)應(yīng)用于多媒體內(nèi)容分析[4]、網(wǎng)頁(yè)挖掘[5]和人臉識(shí)別[6]等多個(gè)領(lǐng)域.

為了解決偏標(biāo)記問(wèn)題,一種常用的方法是對(duì)候選標(biāo)記集合中的元素平等對(duì)待,將模型在各個(gè)候選標(biāo)記上的平均輸出作為模型輸出,如基于K近鄰的偏標(biāo)記學(xué)習(xí)算法PL-KNN[7](partial labelKnearest neighbor)、基于凸優(yōu)化的偏標(biāo)記學(xué)習(xí)算法CLPL[8](convex loss for partial labels)等,但該方法構(gòu)造之模型的性能受候選標(biāo)記集合中偽標(biāo)記的影響較大.IPAL[9](instance-based partial label learning)算法通過(guò)辨識(shí)消歧的方式克服了該缺陷,其分類性能優(yōu)于多數(shù)的偏標(biāo)記學(xué)習(xí)方法,該算法首先構(gòu)建樣本近鄰的相似度圖,然后通過(guò)迭代標(biāo)記傳播和CMN[10]方法對(duì)訓(xùn)練樣本消歧,即實(shí)現(xiàn)每個(gè)訓(xùn)練樣本只對(duì)應(yīng)1個(gè)標(biāo)簽,最后對(duì)測(cè)試樣本進(jìn)行預(yù)測(cè).

隨著大數(shù)據(jù)時(shí)代的到來(lái),大數(shù)據(jù)已經(jīng)應(yīng)用于網(wǎng)絡(luò)安全[11]、人工智能和機(jī)器學(xué)習(xí)等多個(gè)領(lǐng)域.但I(xiàn)PAL[9]算法需要求取每個(gè)樣本的K近鄰,耗時(shí)特別多,而且該方法在構(gòu)建近鄰樣本的相似度圖時(shí)將求取每個(gè)樣本近鄰權(quán)值的問(wèn)題轉(zhuǎn)化為了有約束的最小二乘法問(wèn)題,計(jì)算量較大,不適合處理大規(guī)模數(shù)據(jù).

為了解決上述問(wèn)題,筆者首先對(duì)IPAL算法求取近鄰樣本的方法進(jìn)行改進(jìn),使用近鄰樣本間的距離替代有約束的最小二乘問(wèn)題來(lái)求取近鄰樣本權(quán)值,提出基于近鄰距離加權(quán)的偏標(biāo)記算法WIPAL(weighted instance-based partial label learning).然后為了進(jìn)一步提升WIPAL算法的運(yùn)行速率,設(shè)計(jì)基于MPI的WIPAL算法的并行方法PWIPAL(parallel weighted instance-based partial label learning).通過(guò)試驗(yàn)對(duì)所提出的偏標(biāo)記算法進(jìn)行驗(yàn)證.

1 相關(guān)工作

MPI[12-14]是1個(gè)信息傳遞應(yīng)用程序接口,適用于MIMD(multiple instruction multiple data)程序,也適合于更嚴(yán)格形式的SPMD(single program multiple data)程序,主要包括進(jìn)程間通信、集合操作、進(jìn)程組、通信上下文、進(jìn)程拓?fù)浣Y(jié)構(gòu)、環(huán)境管理與查詢等內(nèi)容,進(jìn)程間通信可以細(xì)分為點(diǎn)到點(diǎn)通信、組歸約、廣播、散射、收集、全交換等類型.MPI[14]具有高性能、大規(guī)模、可移植性、可擴(kuò)展性等諸多優(yōu)點(diǎn),能夠被C語(yǔ)言、C++和Fortran等編程語(yǔ)言直接調(diào)用,但MPI沒(méi)有調(diào)試設(shè)施[15],因而開(kāi)發(fā)難度較大.

偏標(biāo)記學(xué)習(xí)[9]就是根據(jù)含有弱監(jiān)督信息的訓(xùn)練集得到1個(gè)多類分類器.IPAL算法是一種基于樣例的偏標(biāo)記學(xué)習(xí)算法,主要由訓(xùn)練部分和測(cè)試部分組成,訓(xùn)練部分主要包括訓(xùn)練集相似度圖的構(gòu)建、迭代標(biāo)記傳播,測(cè)試部分包括測(cè)試集相似度圖的構(gòu)建和測(cè)試樣本的預(yù)測(cè).

相似度圖的構(gòu)建:本部分構(gòu)建相似度圖G=(V,E),其中V為樣本,E用樣本之間的相似度表示.首先根據(jù)樣本之間的歐式距離求出訓(xùn)練集D中每個(gè)樣本的K近鄰,然后使用近鄰樣本重構(gòu)其對(duì)應(yīng)訓(xùn)練樣本的方式獲得近鄰樣本的權(quán)值,即

(1)

式中:xiα為xj的K近鄰樣本；wiα,j為樣本xiα與xj之間的相似度;N(xj)為樣本xj的K近鄰樣本索引集.

(2)

式中:yc為1個(gè)標(biāo)記;Si為樣本xi的候選標(biāo)記集.

(3)

每一次標(biāo)記傳播結(jié)束后,根據(jù)實(shí)例的候選標(biāo)記集合和計(jì)算式

(4)

最后每個(gè)樣本根據(jù)標(biāo)記置信度矩陣進(jìn)行消歧,即將偏標(biāo)記數(shù)據(jù)集轉(zhuǎn)化為單標(biāo)記數(shù)據(jù)集.在文獻(xiàn)[9]中IPAL算法采用了CMN(class mass normalization)策略,使消歧考慮了各類別的先驗(yàn)分布,如下:

(5)

測(cè)試階段:首先求得每個(gè)測(cè)試樣本的近鄰,然后根據(jù)最小重構(gòu)準(zhǔn)則求得每個(gè)測(cè)試樣本與其近鄰間的權(quán)重向量,算法根據(jù)測(cè)試樣本近鄰中的各類別對(duì)測(cè)試樣本進(jìn)行重構(gòu),重構(gòu)誤差最小的類別作為測(cè)試樣本的預(yù)測(cè)標(biāo)記,計(jì)算式為

(6)

2 IPAL算法的改進(jìn)

文獻(xiàn)[9]的算法IPAL在求取近鄰樣本的權(quán)值、構(gòu)建相似度圖的過(guò)程中,采用近鄰樣本重構(gòu)其對(duì)應(yīng)樣本的方法構(gòu)建目標(biāo)函數(shù),將其問(wèn)題轉(zhuǎn)化為了有約束的最小二乘問(wèn)題,但因訓(xùn)練集和測(cè)試集的每個(gè)樣本需要處理有約束的最小二乘問(wèn)題,耗時(shí)太多.為了解決該問(wèn)題,文中提出了一種基于近鄰距離加權(quán)的偏標(biāo)記學(xué)習(xí)方法WIPAL.

鑒于IPAL算法中求取樣本K近鄰時(shí)已經(jīng)求得了樣本與其對(duì)應(yīng)近鄰樣本之間的距離,根據(jù)樣本之間距離越近、其類別相同概率就越大的思想,文中充分利用其已獲得的近鄰樣本距離,將其近鄰樣本距離的倒數(shù)除以所有近鄰樣本的倒數(shù)之和所得的值作為近鄰樣本的權(quán)值,計(jì)算式為

(7)

式中Li,j為樣本xi和xj之間的距離.處理有約束的最小二乘問(wèn)題常采用迭代的方法,其時(shí)間復(fù)雜度為O(tpK(m+n)),式中p為樣本特征數(shù),K為近鄰樣本數(shù),m和n分別為訓(xùn)練集和測(cè)試集樣本數(shù),t為迭代次數(shù);基于近鄰距離求取近鄰權(quán)值的方法只需要對(duì)近鄰樣本的距離進(jìn)行遍歷就可獲得其近鄰權(quán)值,其時(shí)間復(fù)雜度為O(pK(m+n)).顯然該方法的運(yùn)算速度比文獻(xiàn)[9]中處理有約束最小二乘問(wèn)題獲得近鄰權(quán)值的方法快了很多.

3 并行算法PWIPAL

并行算法PWIPAL主要由讀入訓(xùn)練集和測(cè)試集、構(gòu)建訓(xùn)練集相似度圖、迭代標(biāo)記傳播、讀取測(cè)試集數(shù)據(jù)、構(gòu)建測(cè)試集相似度圖和測(cè)試樣本預(yù)測(cè)等組成.

3.1 讀入訓(xùn)練集和測(cè)試集

3.2 構(gòu)建訓(xùn)練集相似度圖

首先,開(kāi)設(shè)c個(gè)進(jìn)程,訓(xùn)練集特征D=[D0,D1,…,Dc-1],其中Di為第i個(gè)進(jìn)程存儲(chǔ)的訓(xùn)練集特征.每個(gè)進(jìn)程采用輪詢的通信方式將保存的訓(xùn)練集特征傳播給相鄰的進(jìn)程,具體通信方式見(jiàn)圖1,以4個(gè)進(jìn)程為例,圖1中方塊中的數(shù)字表示進(jìn)程號(hào),箭頭上的數(shù)字表示傳播的訓(xùn)練集特征對(duì)應(yīng)的進(jìn)程號(hào).

然后求取其進(jìn)程自身保存的訓(xùn)練集樣本特征與通信收到的訓(xùn)練集樣本的歐式距離,保存K個(gè)最近的距離和其對(duì)應(yīng)距離的索引,重復(fù)c-1次,每個(gè)進(jìn)程就獲得了訓(xùn)練集樣本相對(duì)于整個(gè)訓(xùn)練集的K近鄰,K近鄰的索引存入各自的N中,其中N=[N0,N1,…,Nc-1].接著每個(gè)進(jìn)程根據(jù)各自的樣本及該樣本對(duì)應(yīng)近鄰的距離,使用式(7)求得近鄰樣本的權(quán)值,將其存入W中.接著每個(gè)進(jìn)程分別對(duì)對(duì)應(yīng)的權(quán)值置信度矩陣進(jìn)行量綱一化處理,結(jié)果保存到H中,量綱一化的方式是每個(gè)樣本所對(duì)應(yīng)的近鄰的權(quán)值除以該樣本對(duì)應(yīng)的所有近鄰的權(quán)值之和,即

(8)

圖1 輪詢通信方式

3.3 迭代標(biāo)記傳播

3.3.1 迭代標(biāo)記傳播中計(jì)算改寫(xiě)

文獻(xiàn)[9]在標(biāo)記迭代傳播的部分中,為了更新樣本的標(biāo)記置信度,需要計(jì)算權(quán)值矩陣乘以標(biāo)記置信度矩陣,即式(3)中的HTF(t-1),原文中H是m×m的二維數(shù)組,其中H中每行最多有K個(gè)數(shù),其余全部是0,K為近鄰數(shù),因此HTF(t-1)中有多處0與數(shù)相乘,造成了極大的計(jì)算資源浪費(fèi).一般的實(shí)現(xiàn)代碼常使用稀疏矩陣來(lái)存儲(chǔ)和計(jì)算,文中采用與稀疏計(jì)算類似的方法,用H來(lái)存儲(chǔ)樣本近鄰的權(quán)值,這樣H中每一行都有數(shù)值,不再稀疏;然后HTF(t-1)即樣本的近鄰權(quán)值與近鄰對(duì)應(yīng)的標(biāo)記相乘然后求和,所以式(3)可改為

(9)

式中:hi,k為H中第i行第k列的元素;Ni,k為第i個(gè)樣本的第k個(gè)近鄰的索引.

3.3.2 并行迭代標(biāo)記傳播

首先,對(duì)于每個(gè)進(jìn)程(以第i個(gè)進(jìn)程為例)令訓(xùn)練集標(biāo)簽矩陣Pi=Yi,其中Yi為第i個(gè)進(jìn)程的訓(xùn)練集標(biāo)簽.對(duì)Pi進(jìn)行量綱一化處理,其方法與式(8)類似.令Fi=Pi,其中Fi為第i個(gè)進(jìn)程的迭代標(biāo)簽置信度矩陣.

替代是翻譯漢語(yǔ)文化負(fù)載詞的一種有效方法。許多漢語(yǔ)諺語(yǔ)和典故在英語(yǔ)讀者的認(rèn)知系統(tǒng)中不存在，但它們可能有相似的表達(dá)方式。因此，譯者可以找到一種相似的表達(dá)方式代替原有表達(dá)方式，從而達(dá)到更好的認(rèn)知效果。

然后,每個(gè)進(jìn)程根據(jù)式(9)和(4)進(jìn)行標(biāo)簽置信度矩陣F的更新,如第i進(jìn)程對(duì)Fi進(jìn)行更新,在更新過(guò)程中采用輪詢的通信方式,每個(gè)進(jìn)程將自身的標(biāo)簽矩陣發(fā)送給相鄰的進(jìn)程,重復(fù)c-1次,對(duì)于整個(gè)更新過(guò)程重復(fù)迭代T次.

3.4 構(gòu)建測(cè)試集相似度圖

此部分采用與3.2節(jié)相同的方式構(gòu)建相似度圖,在其過(guò)程中每個(gè)進(jìn)程保存了其樣本對(duì)應(yīng)的近鄰樣本的特征信息.

3.5 測(cè)試集樣本的預(yù)測(cè)

每個(gè)進(jìn)程采用輪詢的通信方式將各自的訓(xùn)練集標(biāo)簽信息發(fā)送給相鄰的進(jìn)程,進(jìn)而每個(gè)進(jìn)程獲得自身訓(xùn)練樣本對(duì)應(yīng)近鄰樣本的標(biāo)簽信息.接著每個(gè)進(jìn)程分別使用各自測(cè)試樣本的K近鄰中各類別的特征根據(jù)式(6)對(duì)測(cè)試樣本進(jìn)行重構(gòu),重構(gòu)誤差最小的類別作為測(cè)試樣本的真實(shí)類別.

通過(guò)對(duì)算法的分析得知并行算法PWIPAL算法的通信時(shí)間復(fù)雜度為O((2np+Tq)(c-1)/c),計(jì)算時(shí)間復(fù)雜度為O((n2p+nK(p+Tq)+mpK(n+1+q))/c),其中n和m為訓(xùn)練樣本數(shù)和測(cè)試樣本數(shù),p為特征數(shù),q為標(biāo)簽數(shù),K為近鄰數(shù),T為迭代數(shù),c為進(jìn)程數(shù);串行WIPAl算法的計(jì)算時(shí)間復(fù)雜度為O(n2p+nK(p+Tq)+mpK(n+1+q)).顯然當(dāng)n越來(lái)越大時(shí),計(jì)算量比通信量增長(zhǎng)速率高;當(dāng)n無(wú)限大時(shí)通信量忽略不計(jì),即開(kāi)設(shè)c個(gè)進(jìn)程,并行算法PWIPAL的運(yùn)行速率比串行算法WIPAL快c倍,而且并行算法每個(gè)進(jìn)程耗費(fèi)的內(nèi)存為串行算法的1/c,由此可見(jiàn),PWIPAl算法可以處理大規(guī)模數(shù)據(jù).

PWIPAL算法偽代碼見(jiàn)下面,其中,Dr和Yr分別為第r個(gè)進(jìn)程分到的訓(xùn)練集樣本特征和標(biāo)簽.

過(guò)程:

每個(gè)MPI進(jìn)程r∈0,1,…,c-1啟動(dòng)

讀取Dr,Yr

根據(jù)歐式距離和自身訓(xùn)練集特征獲得Dr中每個(gè)樣本的K近鄰

Forj=1 toc-1 do

采用輪詢通信方式,將Dr傳播給其他進(jìn)程,接收其他進(jìn)程傳遞的訓(xùn)練集特征

根據(jù)現(xiàn)有的K近鄰信息和收到的其他進(jìn)程訓(xùn)練集特征更新Dr中每個(gè)樣本的K近鄰

End for

根據(jù)式(9)計(jì)算Dr的近鄰權(quán)值矩陣Wr

根據(jù)式(8)對(duì)近鄰權(quán)值矩陣Wr進(jìn)行量綱一化處理

根據(jù)式(2)初始化標(biāo)簽置信度矩陣Pr

對(duì)Pr進(jìn)行量綱一化處理,令Fr(0)=Pr

Fort=1 toTdo

Fori=0 toc-1 do

輪詢通信方式將Fr傳播給其他進(jìn)程,獲得其他進(jìn)程的迭代標(biāo)簽置信度矩陣

根據(jù)式(9)和式(4)迭代更新Fr

End for

End for

根據(jù)式(5)和Fr對(duì)訓(xùn)練集樣本進(jìn)行消歧

Forj=1 toc-1 do

采用輪詢通信的方式,將Dr傳播給其他進(jìn)程,獲得其他進(jìn)程的訓(xùn)練集特征

End for

Fori=0 toc-1 do

通過(guò)輪詢通信的方式,將Yr傳播給其他進(jìn)程,同時(shí)獲得其他進(jìn)程的訓(xùn)練集標(biāo)簽

根據(jù)測(cè)試集樣本的近鄰索引,獲得每個(gè)測(cè)試樣本的近鄰標(biāo)簽

End for

關(guān)閉所有的MPI進(jìn)程

4 試驗(yàn)與結(jié)果

4.1 數(shù)據(jù)集

使用8個(gè)不同規(guī)模的UCI數(shù)據(jù)集和5個(gè)真實(shí)數(shù)據(jù)集進(jìn)行對(duì)比試驗(yàn),其中UCI數(shù)據(jù)集經(jīng)過(guò)人工處理轉(zhuǎn)換為偏標(biāo)記數(shù)據(jù)集.將UCI數(shù)據(jù)集構(gòu)造成偏標(biāo)記數(shù)據(jù)集的處理方法如下:根據(jù)文獻(xiàn)[5-6,8,16],使用參數(shù)p,r,ε控制生成的數(shù)據(jù)集,其中參數(shù)p控制數(shù)據(jù)集中偏標(biāo)記訓(xùn)練樣本的比例,參數(shù)r控制每個(gè)偏標(biāo)記樣本的偽標(biāo)記個(gè)數(shù),ε控制1個(gè)額外的偏標(biāo)記與真實(shí)標(biāo)記共同發(fā)生的概率.具體數(shù)據(jù)集信息見(jiàn)表1.

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

4.2 試驗(yàn)環(huán)境

文中的并行試驗(yàn)在由8臺(tái)服務(wù)器搭建的MPI集群上進(jìn)行,串行試驗(yàn)在集群中的1臺(tái)服務(wù)器上進(jìn)行,集群中每臺(tái)服務(wù)器的環(huán)境配置都如下:Cathe為15 MB,RAM為64 GB,Clock speed為2.0 Hz,CPU核心數(shù)為6,每個(gè)core支持雙線程.操作系統(tǒng)為Centos 6.5,MPI版本號(hào)為3.1.4,GCC版本為4.4.7.

4.3 評(píng)價(jià)指標(biāo)

文中將分類準(zhǔn)確率、程序運(yùn)行時(shí)間、加速比作為評(píng)價(jià)標(biāo)準(zhǔn).其中分類準(zhǔn)確率=預(yù)測(cè)正確的樣本數(shù)/測(cè)試樣本數(shù),加速比=串行運(yùn)行時(shí)間/并行運(yùn)行時(shí)間.

4.4 試驗(yàn)結(jié)果與分析

本部分首先使用4個(gè)小規(guī)模的UCI數(shù)據(jù)集和5個(gè)真實(shí)數(shù)據(jù)集來(lái)驗(yàn)證算法WIPAL的分類準(zhǔn)確率.將算法WIPAL與IPAL進(jìn)行對(duì)比,試驗(yàn)中WIPAL和IPAL的平衡系數(shù)α=0.95,近鄰數(shù)K=10,迭代次數(shù)T=100,求取K近鄰時(shí)均采用線性掃描的方式.IPAL中使用開(kāi)源庫(kù)ipopt來(lái)解決有約束的最小二乘問(wèn)題,HSL選擇版本MA27.表2為UCI數(shù)據(jù)集中WIPAL與算法IPAL關(guān)于分類準(zhǔn)確率的對(duì)比,其中ε=0表示不考慮偏標(biāo)記與真實(shí)標(biāo)記共同發(fā)生的概率.

表2 UCI數(shù)據(jù)集分類準(zhǔn)確率對(duì)比 %

由表2可見(jiàn)WIPAL算法的分類性能與算法IPAL相比有好有壞.表3為真實(shí)數(shù)據(jù)集中WIPAL與IPAL算法分類準(zhǔn)確率的對(duì)比,由表3可見(jiàn)WIPAL算法在數(shù)據(jù)集Lost和Soccer Player上分類準(zhǔn)確率性能優(yōu)于IPAL,在其他數(shù)據(jù)集中,其分類準(zhǔn)確率與算法IPAL相差很少.總體而言,WIPAL算法分類準(zhǔn)確率與IPAL相當(dāng).

表4為在UCI數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上算法WIPAl和IPAL關(guān)于運(yùn)行時(shí)間的對(duì)比,UCI數(shù)據(jù)集的參數(shù)為r=1,p=1,其運(yùn)行時(shí)間為十折交叉驗(yàn)證中一折的運(yùn)行時(shí)間.

表3 真實(shí)數(shù)據(jù)集分類準(zhǔn)確率對(duì)比 %

表4 運(yùn)行時(shí)間 s

由表4可見(jiàn)在相同數(shù)據(jù)集的情況下，WIPAL算法運(yùn)行時(shí)間較短,真實(shí)數(shù)據(jù)集的最后2個(gè)數(shù)據(jù)集中IPAL與WIPAL運(yùn)行時(shí)間相差比例較小是因?yàn)檫@兩個(gè)數(shù)據(jù)集比較大,IPAL和WIPAL計(jì)算每個(gè)樣本近鄰耗費(fèi)的時(shí)間占據(jù)了總運(yùn)行時(shí)間很大部分.為了測(cè)試并行算法PWIPAL的運(yùn)行效率,文中選取了4個(gè)樣本數(shù)規(guī)模從2萬(wàn)到90多萬(wàn)的UCI數(shù)據(jù)集,控制參數(shù)是r=1,p=1,通過(guò)設(shè)置不同的進(jìn)程數(shù)進(jìn)行對(duì)比試驗(yàn),其運(yùn)行時(shí)間為十折交叉驗(yàn)證中一折的運(yùn)行時(shí)間,見(jiàn)表5,其中c為進(jìn)程數(shù).

表5 算法PWIPAL不同進(jìn)程時(shí)的運(yùn)行時(shí)間和加速比

由表5可見(jiàn),對(duì)于數(shù)據(jù)集gas,當(dāng)進(jìn)程數(shù)由1增長(zhǎng)為64的過(guò)程中,算法PWIPAL的運(yùn)行時(shí)間逐漸縮短,由原來(lái)的18 677.41 s變?yōu)榱?89.82 s,加速比由1.00變?yōu)榱?7.91,根據(jù)數(shù)據(jù)集不變,進(jìn)程數(shù)增加時(shí)，算法PWIPAL的運(yùn)行時(shí)間和加速比可以看出對(duì)于相同的數(shù)據(jù)集,隨著開(kāi)設(shè)進(jìn)程數(shù)的增多,PWIPAL的運(yùn)行時(shí)間逐漸減少,加速比逐漸增多.根據(jù)數(shù)據(jù)集的不同規(guī)模可以看出,隨著數(shù)據(jù)集規(guī)模的變大,在相同進(jìn)程數(shù)時(shí)加速比在增多,例如當(dāng)進(jìn)程數(shù)為8時(shí),數(shù)據(jù)集的加速比按照數(shù)據(jù)集規(guī)模遞增的順序逐漸增大.表中數(shù)據(jù)集shuttle在64個(gè)進(jìn)程時(shí)運(yùn)行時(shí)間變多是由于此時(shí)單個(gè)進(jìn)程計(jì)算時(shí)間的減少量低于通信時(shí)間的增加量引起的.

5 結(jié) 論

首先對(duì)偏標(biāo)記算法IPAL進(jìn)行改進(jìn),提出了基于近鄰距離加權(quán)的WIPAL算法;然后為了處理大規(guī)模數(shù)據(jù),進(jìn)一步提出了WIPAL的并行方法PWIPAL.在不同數(shù)據(jù)集下將WIPAL與IPAL的運(yùn)行時(shí)間和分類準(zhǔn)確率進(jìn)行對(duì)比,得知WIPAL的分類準(zhǔn)確率與IPAL相當(dāng),但運(yùn)行效率要高于IPAL;然后在不同規(guī)模數(shù)據(jù)和不同進(jìn)程數(shù)的情況下對(duì)PWIPAL的運(yùn)行時(shí)間和加速比進(jìn)行對(duì)比,驗(yàn)證了該并行算法的高效性,其可用來(lái)處理大規(guī)模數(shù)據(jù).