基于MPI的ML-kNN算法并行

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

(1.重慶郵電大學 計算智能重慶市重點實驗室 重慶 400065； 2.浙江省通信產業服務有限公司溫州市分公司 浙江 溫州 325000； 3.云南省交通科學研究院 云南 昆明 650011)

0 引言

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

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

1 ML-kNN算法

(1)

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

2 ML-kNN的并行

2.1 數據集的劃分

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

2.2 先驗概率的計算

求取先驗概率的核心是對訓練集標簽信息的統計,即對于每個標簽統計其正類樣本和負類樣本的個數.首先將標簽信息以樣本為單位近似均勻劃分為p×q個子集,每個進程僅需統計其中的一個子集,再通過全歸約求和操作,每個進程即可得到整個訓練集標簽信息的統計結果.最后,對于每個進程,根據統計結果計算先驗概率,計算方法與串行的一致.

2.3 k近鄰的求取

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

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

(2)

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

2.4 后驗概率的求取

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

3 實驗與結果分析

3.1 性能指標

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

3.2 數據集

本文選用的數據集來源于Mulan官網的多標簽數據集.實驗將從樣本數量、特征數量兩個維度驗證并行算法的性能,故選取的數據集如表1所示. 此外,由于在實驗中調用了開源庫,為了避免開源庫對稀疏數據優化減少實際的計算量,從而產生實驗誤差,故對于稀疏表示的數據集EUR-Lex和rcv1v2,將其去稀疏化并轉化為完整表示的數據集.

表1 數據集信息

3.3 實驗環境

本實驗使用的MPI編程環境是由11臺服務器搭建的真實物理集群,串行實驗的運行環境和單服務器配置相同.服務器的處理器為Intel Xeon E5-2620，使用的操作系統為CentOS 6.5，MPI的版本為3.1.4，GCC版本為4.4.7.

3.4 實驗內容與結果分析

本實驗主要目的是驗證基于MPI并行化后的ML-kNN算法在大規模數據集上的適應能力，以及不同數據劃分方式對效率的影響,故實驗中不考慮k值對ML-kNN算法的影響,實驗中默認取值為10.首先,基于多標簽學習開源庫Mulan實現了傳統的ML-kNN算法，基于C++線性代數開源庫Armadillo實現了改進的ML-kNN算法,以測試串行的ML-kNN算法在不同數據集上的效率以及本文提出的改進算法對算法效率的影響.表2描述了基于Mulan的串行算法和基于Armadillo的改進算法在表1所述4個數據集上的運行時間.

表2 串行ML-kNN實驗結果

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

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

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

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

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

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

4 總結

本文提出了一種基于MPI編程模型的ML-kNN算法并行方法.在保證ML-kNN算法精度不受損的情況下,改進了ML-kNN算法并提升了算法的效率.實驗結果表明,本文提出的方法可以靈活針對數據集的特點改變數據集的切分方式,在大規模數據集上適應性更強.因此,本文的方法是可行且高效的.