基于MPI的ML-kNN算法并行

王 進(jìn)， 晏世凱， 高延雨， 金理雄， 胡明星， 鄧 欣， 陳喬松

(1.重慶郵電大學(xué) 計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室 重慶 400065； 2.浙江省通信產(chǎn)業(yè)服務(wù)有限公司溫州市分公司 浙江 溫州 325000； 3.云南省交通科學(xué)研究院 云南 昆明 650011)

0 引言

大數(shù)據(jù)[1]指的是數(shù)據(jù)規(guī)模龐大到無法通過目前的技術(shù)、方法和理論,在可以容忍的時(shí)間內(nèi)對(duì)其進(jìn)行獲取、管理、處理的數(shù)據(jù),其具有數(shù)據(jù)體量大、數(shù)據(jù)類型多樣、價(jià)值密度低等特點(diǎn).隨著大數(shù)據(jù)時(shí)代的到來,傳統(tǒng)的串行計(jì)算方法已經(jīng)不能滿足數(shù)據(jù)挖掘工作者的需要,在并行框架下進(jìn)行大規(guī)模數(shù)據(jù)挖掘已成為一種趨勢(shì).目前,機(jī)器學(xué)習(xí)算法常用的并行框架有Hadoop[2]、Spark[3]以及MPI(message passing interface)[4]. 文獻(xiàn)[5]分別實(shí)現(xiàn)了Hadoop和Spark版本的Apriori算法,實(shí)驗(yàn)結(jié)果表明Spark較Hadoop在I/O上時(shí)間開銷更低，效率更高,文獻(xiàn)[6]將SVM和kNN分別在Spark和MPI/OpenMP上并行,證明了MPI/OpenMP比Spark具有更高效率.

在數(shù)據(jù)的規(guī)模不斷增大的同時(shí),數(shù)據(jù)的表現(xiàn)形式也愈加豐富,而傳統(tǒng)的監(jiān)督學(xué)習(xí)認(rèn)為每個(gè)樣本只有一個(gè)標(biāo)簽,不能準(zhǔn)確地表述事物的復(fù)雜語(yǔ)義.多標(biāo)簽學(xué)習(xí)[7]認(rèn)為每個(gè)樣本可能包含一個(gè)或多個(gè)標(biāo)簽,具有多個(gè)標(biāo)簽的樣本能夠更好地表現(xiàn)事物語(yǔ)義信息的多樣性.多個(gè)標(biāo)簽的引入雖然增強(qiáng)了樣本的表達(dá)能力,卻也不可避免地使相應(yīng)的學(xué)習(xí)任務(wù)變得更加困難.與單標(biāo)簽學(xué)習(xí)相比,多標(biāo)簽學(xué)習(xí)中標(biāo)簽集合的數(shù)目隨標(biāo)簽個(gè)數(shù)的增加呈指數(shù)級(jí)增長(zhǎng),導(dǎo)致了其輸出空間較大,從而增加了學(xué)習(xí)的難度.ML-kNN(multi-labelk-nearest neighbor)[8]是一種基于kNN(k-nearest neighbor)和貝葉斯理論的多標(biāo)簽學(xué)習(xí)算法,算法分別統(tǒng)計(jì)待預(yù)測(cè)樣本k近鄰中每個(gè)標(biāo)簽的信息,并利用最大后驗(yàn)概率準(zhǔn)則進(jìn)行預(yù)測(cè). ML-kNN也是多標(biāo)簽學(xué)習(xí)算法中的第一個(gè)惰性學(xué)習(xí)算法[8],其同時(shí)繼承惰性學(xué)習(xí)和貝葉斯方法的優(yōu)勢(shì)[7]：決策的邊界可以通過調(diào)整待預(yù)測(cè)樣本的鄰居個(gè)數(shù)而調(diào)整；計(jì)算每個(gè)類別的先驗(yàn)概率可有效緩解不平衡問題.此外,ML-kNN還具有算法簡(jiǎn)潔、分類準(zhǔn)確率高等特點(diǎn),因而被廣泛使用.然而,當(dāng)數(shù)據(jù)規(guī)模龐大時(shí),ML-kNN算法由于自身的時(shí)間復(fù)雜度較高而不能高效地對(duì)其進(jìn)行處理,本文基于MPI編程模型將ML-kNN并行化,以提升ML-kNN的效率,節(jié)約硬件成本.這也是首次將MPI并行計(jì)算框架應(yīng)用到了多標(biāo)簽學(xué)習(xí)領(lǐng)域,通過與傳統(tǒng)的串行ML-kNN的對(duì)比實(shí)驗(yàn),驗(yàn)證了本文提出方法的可行性和有效性.值得一提的是,在對(duì)數(shù)據(jù)集的劃分時(shí),本文提出的方法不僅可以將數(shù)據(jù)集以樣本為單位劃分,也能以特征為單位劃分,這使得在處理高維數(shù)據(jù)的時(shí)候,本文的方法具有更大的優(yōu)勢(shì).

1 ML-kNN算法

(1)

設(shè)訓(xùn)練集樣本個(gè)數(shù)為m,特征空間維度為d,標(biāo)簽空間維度為n, ML-kNN算法訓(xùn)練階段的時(shí)間復(fù)雜度為O(m2d+nmk),測(cè)試階段的時(shí)間復(fù)雜度為O(md+nk)[7].

2 ML-kNN的并行

2.1 數(shù)據(jù)集的劃分

設(shè)特征空間X是d維實(shí)數(shù)向量空間Rd,標(biāo)簽集合Y可以映射到一個(gè)n維實(shí)數(shù)向量空間Rn,訓(xùn)練集D由m個(gè)樣本組成,則訓(xùn)練集D中樣本特征的集合可由m行d列的矩陣Mm×d表示,樣本標(biāo)簽的集合可由m行n列的矩陣Lm×n表示.對(duì)于矩陣M,將其以樣本和特征為單位近似均勻劃分成p×q個(gè)子矩陣.為了闡述的方便,定義每個(gè)子矩陣為一個(gè)特征數(shù)據(jù)塊,在同一列的特征數(shù)據(jù)塊組成一個(gè)特征數(shù)據(jù)列,在同一行的特征數(shù)據(jù)塊組成一個(gè)特征數(shù)據(jù)行.對(duì)于每一個(gè)特征數(shù)據(jù)塊,為其分配一個(gè)獨(dú)有的進(jìn)程,并將該特征數(shù)據(jù)塊和標(biāo)簽矩陣L傳入該進(jìn)程.

2.2 先驗(yàn)概率的計(jì)算

求取先驗(yàn)概率的核心是對(duì)訓(xùn)練集標(biāo)簽信息的統(tǒng)計(jì),即對(duì)于每個(gè)標(biāo)簽統(tǒng)計(jì)其正類樣本和負(fù)類樣本的個(gè)數(shù).首先將標(biāo)簽信息以樣本為單位近似均勻劃分為p×q個(gè)子集,每個(gè)進(jìn)程僅需統(tǒng)計(jì)其中的一個(gè)子集,再通過全歸約求和操作,每個(gè)進(jìn)程即可得到整個(gè)訓(xùn)練集標(biāo)簽信息的統(tǒng)計(jì)結(jié)果.最后,對(duì)于每個(gè)進(jìn)程,根據(jù)統(tǒng)計(jì)結(jié)果計(jì)算先驗(yàn)概率,計(jì)算方法與串行的一致.

2.3 k近鄰的求取

由于在數(shù)據(jù)分割時(shí),不僅將訓(xùn)練集以樣本為單位進(jìn)行了劃分,還將訓(xùn)練集以特征為單位進(jìn)行了劃分,使得原始的ML-kNN算法中的歐氏距離在并行中不適用,同時(shí)為了充分利用矩陣運(yùn)算的優(yōu)勢(shì)提升效率,故將歐氏距離在求取k近鄰的情況下等價(jià)為

?(a-b)(a-b)T?aaT-2abT+bbT?bbT-2abT,

(2)

其中：a為當(dāng)前樣本的特征向量；b為目標(biāo)樣本的特征向量.改進(jìn)后的距離公式允許特征向量a、b同時(shí)截?cái)酁槎鄠€(gè)子向量，并分別計(jì)算距離后再累加.利用此性質(zhì),k近鄰的求取步驟如下：首先，將每個(gè)特征數(shù)據(jù)列對(duì)應(yīng)的進(jìn)程劃分為一個(gè)獨(dú)立的通信域,通信域內(nèi)互相廣播傳遞計(jì)算距離所需的特征數(shù)據(jù)塊,進(jìn)而利用公式(2)求取該特征子集下的樣本與樣本間的距離.其次，在所有通信域完成距離計(jì)算后,對(duì)于每個(gè)特征數(shù)據(jù)行對(duì)應(yīng)的所有進(jìn)程進(jìn)行歸約求和操作,歸約求和的結(jié)果將以樣本為單位近似均勻地分配到特征數(shù)據(jù)行對(duì)應(yīng)的各個(gè)進(jìn)程.由公式(2)的性質(zhì)可知,部分特征下的距離在歸約求和之后即為在所有特征下完整的距離.最后，由于每個(gè)進(jìn)程中均有部分歸約求和的結(jié)果,且歸約求和的結(jié)果為該進(jìn)程中分配的樣本到其他樣本的完整距離,故對(duì)于每個(gè)進(jìn)程,利用所分配樣本的距離信息進(jìn)行k近鄰的求取.

2.4 后驗(yàn)概率的求取

求取后驗(yàn)概率的核心是近鄰標(biāo)簽信息的統(tǒng)計(jì),即對(duì)某個(gè)樣本統(tǒng)計(jì)其近鄰中含有標(biāo)簽l(l∈Y)的個(gè)數(shù)以及不含有標(biāo)簽l的個(gè)數(shù).由于在k近鄰的求取步驟中,每個(gè)進(jìn)程已將分配到的樣本子集的k近鄰求出,故只需在此基礎(chǔ)上對(duì)近鄰的標(biāo)簽信息做統(tǒng)計(jì),然后將統(tǒng)計(jì)結(jié)果進(jìn)行全歸約求和操作,每個(gè)進(jìn)程即可得到整體的近鄰標(biāo)簽信息統(tǒng)計(jì)結(jié)果.最后,對(duì)于每個(gè)進(jìn)程,根據(jù)總的標(biāo)簽信息統(tǒng)計(jì)結(jié)果計(jì)算出后驗(yàn)概率.

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

3.1 性能指標(biāo)

基于MPI將ML-kNN算法并行化并未對(duì)其精度產(chǎn)生任何影響,故本實(shí)驗(yàn)僅從效率的角度考慮運(yùn)行時(shí)間和加速比兩項(xiàng).運(yùn)行時(shí)間指的是訓(xùn)練模型和分類的總時(shí)間,不包括讀取數(shù)據(jù)集的時(shí)間. 加速比用于度量并行算法運(yùn)行時(shí)間和串行算法運(yùn)行時(shí)間的關(guān)系,其公式為Speedup=base_line/parallel_time,其中：base_line為串行程序運(yùn)行時(shí)間；parallel_time為并行程序運(yùn)行時(shí)間.加速比Speedup越大,并行的效果越好.

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

本文選用的數(shù)據(jù)集來源于Mulan官網(wǎng)的多標(biāo)簽數(shù)據(jù)集.實(shí)驗(yàn)將從樣本數(shù)量、特征數(shù)量?jī)蓚€(gè)維度驗(yàn)證并行算法的性能,故選取的數(shù)據(jù)集如表1所示. 此外,由于在實(shí)驗(yàn)中調(diào)用了開源庫(kù),為了避免開源庫(kù)對(duì)稀疏數(shù)據(jù)優(yōu)化減少實(shí)際的計(jì)算量,從而產(chǎn)生實(shí)驗(yàn)誤差,故對(duì)于稀疏表示的數(shù)據(jù)集EUR-Lex和rcv1v2,將其去稀疏化并轉(zhuǎn)化為完整表示的數(shù)據(jù)集.

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

3.3 實(shí)驗(yàn)環(huán)境

本實(shí)驗(yàn)使用的MPI編程環(huán)境是由11臺(tái)服務(wù)器搭建的真實(shí)物理集群,串行實(shí)驗(yàn)的運(yùn)行環(huán)境和單服務(wù)器配置相同.服務(wù)器的處理器為Intel Xeon E5-2620，使用的操作系統(tǒng)為CentOS 6.5，MPI的版本為3.1.4，GCC版本為4.4.7.

3.4 實(shí)驗(yàn)內(nèi)容與結(jié)果分析

本實(shí)驗(yàn)主要目的是驗(yàn)證基于MPI并行化后的ML-kNN算法在大規(guī)模數(shù)據(jù)集上的適應(yīng)能力，以及不同數(shù)據(jù)劃分方式對(duì)效率的影響,故實(shí)驗(yàn)中不考慮k值對(duì)ML-kNN算法的影響,實(shí)驗(yàn)中默認(rèn)取值為10.首先,基于多標(biāo)簽學(xué)習(xí)開源庫(kù)Mulan實(shí)現(xiàn)了傳統(tǒng)的ML-kNN算法，基于C++線性代數(shù)開源庫(kù)Armadillo實(shí)現(xiàn)了改進(jìn)的ML-kNN算法,以測(cè)試串行的ML-kNN算法在不同數(shù)據(jù)集上的效率以及本文提出的改進(jìn)算法對(duì)算法效率的影響.表2描述了基于Mulan的串行算法和基于Armadillo的改進(jìn)算法在表1所述4個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間.

表2 串行ML-kNN實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果表明: 1) 當(dāng)數(shù)據(jù)集的規(guī)模上升至十萬(wàn)級(jí)、特征維度上百時(shí),串行的ML-kNN算法很難在可接受的時(shí)間內(nèi)將數(shù)據(jù)處理下來. 2) 改進(jìn)后的ML-kNN算法具有更高的效率,在數(shù)據(jù)規(guī)模較大時(shí)有更明顯的效果,其原因在于改進(jìn)后的ML-kNN算法編寫時(shí)使用了C++線性代數(shù)開源庫(kù)Armadillo,在k近鄰的求取時(shí)能夠更加充分地利用緩存,而k近鄰的求取是ML-kNN算法時(shí)間開銷最大的部分,故提升效果較為明顯.此外,C++語(yǔ)言更偏向于底層,相比Java語(yǔ)言效率更高.

其次,本實(shí)驗(yàn)測(cè)試了并行后的ML-kNN算法在使用不同的計(jì)算資源情況下的性能.表3和表4描述了并行算法在表1所述的4個(gè)數(shù)據(jù)集上的運(yùn)行時(shí)間以及加速比.其中p和q分別為特征數(shù)據(jù)塊的列數(shù)和行數(shù),Speedup為并行ML-kNN算法相對(duì)改進(jìn)后的串行ML-kNN算法的加速比.由于本實(shí)驗(yàn)是考察算法在不同計(jì)算資源上的性能,為了保持統(tǒng)一,故將數(shù)據(jù)集均以樣本為單位切分.

表3 并行后的ML-kNN在NUS-WIDE-bow和mediamill上的結(jié)果

表4 并行后的ML-kNN在EUR-Lex和rcv1v2上的結(jié)果

實(shí)驗(yàn)結(jié)果表明: 1) 程序的運(yùn)行時(shí)間會(huì)隨著計(jì)算資源的增加而減少,這種減少的程度會(huì)隨著計(jì)算資源的增加逐漸變緩.其原因是,隨著節(jié)點(diǎn)數(shù)的增加,通信需要的時(shí)間將逼近甚至超過計(jì)算所需時(shí)間. 2) 通過對(duì)比表3和表4可知,當(dāng)數(shù)據(jù)集特征維度較高時(shí),僅以樣本為單位劃分?jǐn)?shù)據(jù)集對(duì)整體效率的提升不大,其原因?qū)⒃诤罄m(xù)實(shí)驗(yàn)中進(jìn)行分析. 3) 根據(jù)Amdahl定律[9],最理想的并行結(jié)果為加速比等于所用核心個(gè)數(shù).而本實(shí)驗(yàn)中出現(xiàn)加速比大于所使用核心個(gè)數(shù)的原因是,在串行代碼中,計(jì)算樣本間的距離采用的是向量的運(yùn)算,當(dāng)訓(xùn)練集數(shù)據(jù)量較大時(shí),隨之增長(zhǎng)的計(jì)算量會(huì)造成在cache中大量的數(shù)據(jù)替換,導(dǎo)致cache命中率降低,從而運(yùn)行效率較低.而在并行算法中,為了進(jìn)一步提升算法的效率,使用了矩陣運(yùn)算替換部分向量計(jì)算,減少了計(jì)算量,增加了cache命中率,因而能夠充分利用緩存進(jìn)一步提升效率.值得一提的是,如果直接在串行算法中使用矩陣運(yùn)算替換向量運(yùn)算可能會(huì)導(dǎo)致單機(jī)內(nèi)存不足的問題.以NUS-WIDE-bow數(shù)據(jù)集為例,如果直接使用矩陣運(yùn)算的方式計(jì)算訓(xùn)練集的近鄰矩陣,需要占用大約195 G的內(nèi)存. 4) 基于Mulan的串行ML-kNN算法和本文提出的并行ML-kNN算法在表1所述4個(gè)數(shù)據(jù)集上的輸出結(jié)果是一致的,驗(yàn)證了本文對(duì)ML-kNN算法的改進(jìn)以及并行化并未影響ML-kNN算法的精度.

最后,本實(shí)驗(yàn)測(cè)試了在計(jì)算資源相同的情況下,不同數(shù)據(jù)切分方式對(duì)并行ML-kNN算法性能的影響.實(shí)驗(yàn)結(jié)果表明: 在計(jì)算資源一定的情況下,相比單一的以樣本為單位劃分?jǐn)?shù)據(jù)集,本文提出方法不僅可以將數(shù)據(jù)集以樣本為單位劃分,也能以特征為單位劃分,這使得在處理高維數(shù)據(jù)的時(shí)候,本文方法具有更大的優(yōu)勢(shì).

4 總結(jié)

本文提出了一種基于MPI編程模型的ML-kNN算法并行方法.在保證ML-kNN算法精度不受損的情況下,改進(jìn)了ML-kNN算法并提升了算法的效率.實(shí)驗(yàn)結(jié)果表明,本文提出的方法可以靈活針對(duì)數(shù)據(jù)集的特點(diǎn)改變數(shù)據(jù)集的切分方式,在大規(guī)模數(shù)據(jù)集上適應(yīng)性更強(qiáng).因此,本文的方法是可行且高效的.