基于Spark的多標簽超網絡集成學習

李航，王進，趙蕊

(1.重慶郵電大學 軟件工程學院，重慶 400065； 2. 重慶郵電大學 計算智能重慶市重點實驗室，重慶 400065)

基于Spark的多標簽超網絡集成學習

李航1，王進2，趙蕊2

(1.重慶郵電大學 軟件工程學院，重慶 400065； 2. 重慶郵電大學 計算智能重慶市重點實驗室，重慶 400065)

近年來，多標簽學習在圖像識別和文本分類等多個領域得到了廣泛關注，具有越來越重要的潛在應用價值。盡管多標簽學習的發展日新月異，但仍然存在兩個主要挑戰，即如何利用標簽間的相關性以及如何處理大規模的多標簽數據。針對上述問題，基于MLHN算法，提出一種能有效利用標簽相關性且能處理大數據集的基于Spark的多標簽超網絡集成算法SEI-MLHN。該算法首先引入代價敏感，使其適應不平衡數據集。其次，改良了超網絡演化學習過程，并優化了損失函數，降低了算法時間復雜度。最后，進行了選擇性集成，使其適應大規模數據集。在11個不同規模的數據集上進行實驗，結果表明，該算法具有較好的分類性能，較低的時間復雜度且具備良好的處理大規模數據集的能力。

多標簽學習；超網絡；標簽相關性；Apache Spark；選擇性集成學習

多標簽學習在文本分類[1-2]、圖像注釋[3-4]和生物信息學[5]等多個應用領域得到了廣泛關注，也具有越來越重要的應用價值。在多標簽學習中，訓練集的一個樣本均對應一組標簽集合。假設X表示樣本空間,Y={1，2，…，q}表示所有可能的標簽集合，其中標簽的總數為q，T={(x1,Y1),(x2,Y2)，…,(xm,Ym)}為具有m個樣本的訓練集，其中xi∈X且Yi?Y。則多標簽分類的目標是輸出一個多標簽分類器h:x→2y，使得對每一個給定的實例x∈X，都能預測出合適的標簽集合Y*?Y。

多標簽學習的關鍵挑戰在于分類器預測的標簽空間數量為指數級(2q)。為了解決這個問題，有效地利用不同標簽之間的相關性以促進學習過程已成為多標簽學習的關鍵[6-7]。在過去幾年，許多利用標簽相關性的算法被提出，如校準標簽排序(CLR)[8]，隨機k標簽集(RAkEL)[9]和廣義k標簽集成(GLE)[10]均考慮了標簽之間的相關性，然而這些算法的計算復雜度隨標簽數量的增加而顯著增加。

另一方面，目前現實應用中的多標簽數據集的樣本、特征和標簽的數量遠遠超過常規大小，例如，視頻共享網站Youtube中有數百萬個視頻，而每個視頻可以被數百萬個候選類別標記。然而，大多數多標簽學習算法不能很好地適應數據集規模很大的應用。對近3年出現的多標簽學習方法[15-23]使用的訓練集的規模進行統計，可以看出訓練樣本數在50 000～100 000之間的數據集僅有5個，樣本數大于100 000的數據集僅有1個，大多數現有的多標簽學習算法僅適用于處理中小規模數據集。其次，文獻[19]雖然利用大規模數據集進行了實驗，但是它的計算復雜度高。

多標簽超網絡MLHN與協同演化多標簽超網絡Co-MLHN[24]可以挖掘標簽間的高階關系，它將傳統的超網絡轉為多標簽超網絡，用超邊和超邊的權重來表示特征子集與標簽之間的高階關系，利用了任意標簽間的相關性，且計算復雜度隨標簽數量的增加呈線性增長，但是其算法時間復雜度與樣本數量呈平方級關系，不能很好地處理規模較大的數據集,同時算法也未考慮到標簽不平衡對性能的影響。

針對目前多標簽超網絡存在的問題，本文基于MLHN的思想，提出了Spark平臺下的改進多標簽超網絡集成算法SEI-MLHN，有效且高效地解決了多標簽學習問題。首先對多標簽數據集進行劃分；然后對劃分后的數據分別用基于Spark平臺的改進超網絡算法SI-MLHN進行訓練，形成多個局部超網絡；最后對多個局部超網絡進行選擇性集成完成對測試樣本的預測。其中，SI-MLHN利用MLHN的思想并在Spark平臺下進行改進，首先計算每個樣本的k近鄰，然后利用k近鄰對超網絡進行演化學習，得到演化超網絡。

為了評估本文算法的性能以及對大規模數據集的適應性，選用不同規模數據集來進行對比實驗，驗證了本文算法具有良好性能以及具備處理大規模數據集的能力。本文的主要貢獻如下：

1)引入了代價敏感，使其能良好地適應多標簽不平衡數據，提升算法性能；

2)改良了超網絡演化學習過程，大幅度降低MLHN算法的計算復雜度；

3)利用選擇性集成，降低了時間復雜度，并提高分類性能;

4)基于Spark計算框架實現算法，使算法實現并行，提高算法運行效率。

1 相關工作

雖然多標簽學習已經成功應用于生物信息學、音頻分類[25]以及web挖掘[26]等多個領域，但是由于多標簽分類器的輸出空間為指數級，以及現在大部分應用的數據集規模日益增加，對多標簽學習造成了很大的挑戰。

為了應對分類器輸出空間數量巨大這個問題，現有的方法是利用標簽相關性來促進學習過程。基于標簽關聯性，張敏靈和周志華[27-28]將現有的學習算法分為3類，分別為一階策略、二階策略以及高階策略。一階策略是簡單地將多標簽學習轉為多個獨立的二分類問題來解決多標簽學習問題，例如ML-KNN[29]、BR[30]等；二階策略通過利用標簽之間的成對關系解決多標簽學習問題，例如CLR[31]、BP-MLL[32]等；高階策略通過探索標簽之間的高階關系來解決多標簽學習問題，例如CC[33]、CNMF[34]等。對這3種策略進行比較分析，一階策略的效率高且概念易理解，但忽略了標簽相關性。二階策略在一定程度上解決了標簽相關性，但忽略了現實世界中相關性超過二階的情況。高階策略具有比一階和二階更強的建模能力，但是其計算復雜度更高，可擴展性更低。

為了應對多標簽數據的不平衡性造成算法性能下降這個問題，常規解決方案是為每一個標簽訓練一個二分類器，并通過隨機或合成欠采樣/過采樣來處理這個二分類器[35-36]，但這些方法沒有很好地利用標簽間的關聯性。也有其他的解決方案，如張敏靈等[14]提出交叉耦合聚合算法COCOA，但是這種算法時間復雜度高，不適合處理大規模數據集。

為了應對數據集規模大這個問題，現有的解決方案是利用分布式存儲系統，提供一個基礎架構，從而實現高效和可擴展的大數據挖掘與分析。目前，為大數據分析開發了大量的計算框架[37-41]，其中，最經典的是MapReduce[37]。MapReduce簡單、通用且成熟，被廣泛使用，但是它只能進行Map和Reduce計算，不適合描述復雜數據處理過程，數據需要寫到磁盤，不能有效地執行迭代算法。為了克服MapReduce的缺點，大量的計算框架被設計出來，如Haloop[38]、Apache Mahout[39]、i2MapReduce[40]和Apache Spark[41]等。Haloop是Hadoop MapReduce框架的修改版本，它繼承了Hadoop的基本分布式計算模型和架構。Apache Mahout 是一個開源項目，主要用于創建可擴展的機器學習算法。i2MapReduce是MapReduce的一個增量處理擴展，并廣泛用于大數據挖掘。Apache Spark是一個開源的集群計算框架，用于大規模的交互計算。在上述框架中，Apache Spark利用內存計算，并保留MapReduce的可擴展性和容錯能力，對迭代算法非常有效。Spark執行速度比Hadoop MapReduce快100倍[41]，并且顯著快于其他計算框架。

綜上所述，為了解決上述問題，本文使用Spark計算框架作為平臺來實現多標簽算法。

2 Spark下改進多標簽超網絡集成算法

MLHN可以高效地挖掘標簽間的關聯性且學習復雜度與標簽維度呈線性關系，因此本文基于MLHN算法提出了Spark平臺下的改進多標簽超網絡集成算法SEI-MLHN，高效地解決了多標簽問題。首先，對多標簽數據集進行劃分，然后對劃分后的數據分別用SI-MLHN算法進行訓練，形成多個局部超網絡，最后對多個局部超網絡進行選擇性集成完成對測試樣本的預測。其中，算法SI-MLHN利用MLHN的思想，在Spark平臺下進行改進，首先計算每個樣本的k近鄰，然后利用k近鄰對超網絡進行演化學習，得到超網絡。本節中，將對算法MLHN，MLHN的改進算法SI-MLHN，以及以SI-MLHN為基學習器進行選擇性集成的算法SEI-MLHN依次進行介紹。

2.1 多標簽演化超網絡(MLHN)

多標簽演化超網絡利用超邊集合以及超邊權重來表示樣本特征子集與多標簽類別之間的高階關聯。通過演化學習，可以近似地表示訓練樣本X和其標簽Y之間的概率分布P(X,Y)，在MLHN中可以按式(1)進行表示：

式中：yi為樣本x的第i個標簽；wji為超邊集合|E|中ej的第i個權重向量的值；I(x,yi;ej)為超邊與樣本匹配函數，若匹配則取值為1，反之則為0，如式(2)所示：

式中：yji是超邊ej的第i個標簽，dis(xn;ej)為超邊ej與樣本x的歐氏距離，δ為匹配閾值。δ的計算方法如式(3):

式中：其中Gx為x的近鄰樣本集合，dim(x)為樣本x的特征維度。

為了對未知樣本進行預測，MLHN通常把標簽預測誤差和相關標簽不一致性最小化作為演化學習目標。通過超邊初始化、超邊替代和梯度下降演化學習來對訓練集進行學習，使超邊權重wji進行更新，流程如圖1所示。圖1中，超邊eh=(vh,yh,wh)，vh是超邊的頂點，為x的部分特征；yh為x的標簽；wh是xh對應yh的權重向量。

圖1 MLHN算法流程圖Fig.1 Basic flow chart of MLHN

2.2 Spark下改進多標簽超網絡(SI-MLHN)

MLHN是一種有效的多標簽學習算法，但是目前的MLHN算法計算復雜度高，且對多標簽數據的不平衡特性沒有關注。本文一方面改進了MLHN的訓練過程，引入了代價敏感；另一方面通過并行計算來降低運算時間，設計了Spark下改進多標簽超網絡，記作SI-MLHN。在本小節，將分別介紹SI-MLHN的多標簽分類學習過程和演化學習過程。

2.2.1 SI-MLHN分類學習過程

SI-MLHN算法關注了多標簽樣本中普遍存在的標簽類別不平衡現象。對于一個未知樣本xn，SI-MLHN將返回每個標簽的概率P(yni=1|xn)，如

式(4)：

式中：yni為樣本x的第i個標簽;wji為超邊集合|E|中ej的第i個權重向量的值;I(xn,yni;ej)的計算方法如式(2);costi為第i個標簽的代價值，計算方式如式(7)：

式中T為有m個樣本的訓練集。

由于SI-MLHN采用sigmoid函數返回了每個標簽與樣本相關的概率P(yni=1|xn)，故將相關標簽閾值ti設定為0.5，從而獲得每個樣本的標簽集合，如式(8)：

在多標簽學習中，一個樣本只包含標簽空間中的部分標簽。如果可以排除一些不可能的標簽，可以減少標簽預測的不確定性。因此，SI-MLHN借鑒了Co-MLHN算法的思想,將KNN引入算法，減少算法預測的不確定標簽，提高算法的性能。算法1為SI-MLHN分類學習過程的偽代碼。

算法1 SI-MLHN分類學習過程

輸入訓練集T,測試樣本xn,標簽數q，近鄰數量k, SI-MLHN模型H,標簽閾值ti;

輸出標簽概率p,預測標簽y*。

1)在訓練集T中計算xn的k近鄰

2)將模型H中是xn的近鄰且與xn匹配的超邊加入集合U中

3)從U中提取標簽yi=1的超邊到集合U1中

4)fori=1 toqdo

5)W1[i]←0

6)for eachej∈U1

7)W1[i]=W1[i]+wji×costi

8)end for

9)end for

10)從U中提取標簽yi=0的超邊到集U0中

11)fori=1 toqdo

12)W0[i]←0

13) for eachej∈U0

14)W0[i]=W0[i]+wji

15) end for

16)end for

17)fori=1 toqdo

19)p[i]=P(yi=1|xn)

20) ifP(yni=1|xn)≥ti

21)y*[i]=1

22)elsey*[i]=0

23)end if

24)end for

25)returnp,y*

2.2.2 SI-MLHN演化學習過程

SI-MLHN利用超邊的頂點和權重向量來代表多標簽數據標簽間的高階關聯，其權重向量由超邊從訓練集中演化學習而來，首先進行了超邊初始化，然后進行了超邊替代與梯度下降演化學習，并利用Spark進行分布式并行計算，通過多個操作技巧，如cache、broadst，將變量緩存于內存中，大量減少了網絡交換數據量和磁盤I/O操作，使算法更高效。

由于超邊頂點向量v為隨機的，為了更好地擬合訓練樣本，需要通過超邊替代來選擇適應度高的超邊。如果新生成的超邊適應值高于現有超邊，則替換該超邊。適應值的計算方法如式(9)所示：

式中：超邊ej的近鄰樣本個數為k，G為與超邊ej匹配的抽樣訓練集TS樣本集合，則將TS中樣本的數量設置為10倍的k，其中k個是超邊ej的近鄰樣本，其余的樣本則為訓練集樣本的隨機抽樣；q為標簽數量；yni為樣本(xn,yn)的第i個標簽；yi′為超邊ej的第i個標簽。由式(9)可以看出適應值代表了超邊標簽與匹配樣本標簽的相似度的平均值，相似度越高，則適應值越高。同時，式(4)也展示出，樣本與匹配超邊的標簽相似度越高，被正確分類的概率越大。

本文將預測誤差作為學習目標。損失函數如式(10)所示，P*(yni=1|xn)為SI-MLHN分類器對樣本(xn,yn)的第i個標簽的預測值，利用梯度下降調整超邊的權重，降低損失值。超邊權重更新為式(11)，并通過式(12)～(14)，計算Δwki，其中wki為第k條超邊第i個標簽的權重，η為學習速率。

算法2為SI-MLHN的演化學習流程偽代碼。由于本文采用歐氏距離作為距離度量，故需要先進行歸一化處理。

算法2 SI-MLHN演化學習算法

輸入訓練集T={(xn,yn)}(1≤n≤N)，標簽數q，每個樣本生成的超邊數e， 超邊替代迭代次數tr，隨機梯度下降迭代次數td，樣本的近鄰數量k;

輸出SI-MLHN:H。

1)Tnor=T.map

2)每條樣本進行歸一化

3) end map.cache

4)TnorBro= broadcast(Tnor)

5)Tkv=Tnor.map

6)每條樣本計算與TnorBro中樣本的歐式距離

7)end map.map

8)獲取距離最近的k個樣本

9)end map

10)TkvBro= broadcast(Tkv)

11)Hini=Tkv.flatmap

12)每條樣本生成e條超邊

13)end flatmap.cache

15)對超邊進行tr次替代

16)end map.cache

17)fort←1 totddo

19)Htmp=Tkv.map

21)end map.flatmap

22)對超邊進行梯度計算

23)end flatmap.reduceByKey(合并梯度值)

25).map

26)利用合并后梯度值更新超邊權重

27)end map

28)end for

30)returnH

2.3 Spark下集成多標簽超網絡(SEI-MLHN)

SI-MLHN為MLHN的Spark平臺下分布式并行改進方法，大幅縮短了訓練時間，但是其時間復雜度仍然隨著樣本數量的增加呈平方級增長，仍然無法很好適應大樣本數據。故本文利用選擇性集成，一方面降低時間復雜度，另一方面提高算法性能，提出了Spark下集成多標簽超網絡，記作SEI-MLHN。SEI-MLHN首先將訓練集進行分簇，并分別用SI-MLHN算法演化學習多個局部多標簽超網絡。對于未知樣本，首先獲得近鄰簇，然后利用局部超網絡選擇性集成對測試樣本進行預測，SEI-MLHN的流程見圖2。

圖2 SEI-MLHN流程圖Fig.2 Flow chart of SEI-MLHN

算法3 S-SOM

輸入訓練集T={(xn,yn)}(1≤n≤N)，類

簇個數c，學習率η，迭代次數ti;

1)Tnor=T.map

2)每條樣本進行歸一化

3)end map.cache

4)W=初始化輸出層(隨機抽取c個樣本)

5)WBro =broadcast(W)

6)fort←1 toti

7)for eachTnor的分區 do

8)for each 分區內樣本 do

9)利用輸出層計算獲勝節點

11)end for

12)end for

13)更新優勝鄰域

15)end for

完成訓練集分簇后，利用算法2對簇構建SI-MLHN超網絡。對于測試集，SEI-MLHN將進行選擇性集成，偽代碼見算法4。

算法4 SEI-MLHN分類算法

5)組成測試樣本與近鄰樣本對

7)end for

9)E*=F.reduceByKey()

10).map

11)從s*k近鄰中選取最近k，利用算法1進行預測

12)end map

13)returnE*

2.4 時間復雜度分析

SEI-MLHN利用SI-MLHN進行選擇性集成來提高學習器的穩定性和泛化能力。對于含有N個訓練樣本，樣本特征緯度為d，標簽數量為q的訓練集，SI-MLHN的訓練復雜度為O(N2d+enkN+kqN)，記為FSI(N,k,e,n,d,q)，其中e為每個訓練樣本產生的超邊數量，k為近鄰數量，n為訓練樣本的抽樣，在大規模數據集中n?N。對于未知樣本進行預測時，SI-MLHN首先在訓練集中尋找k個近鄰樣本，然后利用與之匹配的近鄰樣本產生的超邊進行預測。因此對有M個樣本的測試集，SI-MLHN的預測時間復雜度為O(MNd+eMN+kqM),記為FSI′(M,k,e,N,d,q)。SEI-MLHN對訓練集進行了分簇，并在預測時刪除了冗余學習器，因此其訓練時間復雜度為O(c·FSI(N′,k,e,n,d,q)),測試時間復雜度為O(s·FSI′(M,k,e,N′,d,q))，其中c為訓練集聚類簇數，s為鄰域簇的數量，N′為最大類簇中樣本的數量，N′的數量取決于c以及訓練數據的分布，一般接近于N/c。

3 實驗

3.1 數據集

為了對算法性能進行全面的評估，本文選擇了11個公開的常用多標簽數據集進行實驗，其中訓練樣本數小于5 000的數據集有6個，大于100 000的數據集有2個，如表1所示，表中的標簽基數是指每個樣本關聯標簽的平均數量。由于文本數據具有高維稀疏的特性，故在表1中對所有的文本數據集均使用Lee和Jiang[43]提出的模糊相關度量進行了變換，在模糊變換之后，每個文檔由模糊相關性向量表示，且維度與標簽維度相同。

表1 實驗使用的多標簽數據集

3.2 評價指標

假設X表示樣本空間，Y={1,2,…,q}表示所有可能的標簽集合，E={(xi,Yi)|1≤i≤M}為具有M個樣本的多標簽測試集，h為輸出的多標簽分類器，則測試樣本xi的預測結果為h(xi)。f(xi,y)是標簽y在樣本xi上排名質量的實值函數，例如對于任意y1∈Y以及y2∈Y而言，f(xi,y1)gt;f(xi,y2)成立。實值函數f(·,·)也可以轉為排序函數rankf(·,·)，即將所有的實值輸出f(xi,y)映射到集合Y上，使得f(xi,y1)gt;f(xi,y2)時，rankf(xi,y1)gt;rankf(xi,y2)也成立。基于上述描述，本文采用的多標簽性能評價指標如下。

1)Hamming Loss: 用于考察樣本在單個標簽上的誤分類情況。

式中Δ表示兩個集合的對稱差。

2)One-error：用于考察樣本測標簽排序集合中最前端的標簽誤分類的情況。

3)Ranking Loss：用于考察樣本的預測標簽排序集合中的錯排情況。

4)Average Precision：用于考察樣本的預測標簽集合中排在該樣本標簽之前的標簽分類正確的情況。

5) Example BasedF1:

3.3 比較的算法和實驗環境

在本文中，將SEI-MLHN與兩種系列的算法進行比較實驗，第1種系列是常用的多標簽學習算法，如表2的前8種算法所示，它們均在表3所示的單節點環境中實現。第二種系列是在Spark平臺下實現的超網絡多標簽學習算法，如S-CoMLHN以及SEI-MLHN的基學習器SI-MLHN，Spark集群環境如表4所示，其中S-CoMLHN是Co-MLHN在Spark平臺下的實現。

在實驗過程中比較算法的參數設置取自文獻[8-9,14,24,30,39,44]，詳細設置見表3，其中算法SI-MLHN中每個樣本生成超邊的數量e為10，超邊替代迭代次數tr為5，隨機梯度下降迭代次數td為5。

表2 實驗中的比較算法

表3 實驗單節點環境

表4 集群環境配置

3.4 實驗結果

3.4.1 參數分析

對于算法SEI-MLHN，近鄰個數k是關鍵參數之一，為了測試算法對k參數的敏感度，本節將k以5為步長，在5～40范圍內測試算法SI-MLHN的性能。如圖3所示，(c)、(e)隨k的增大波動較大，部分數據集kgt;10后趨于穩定，多數數據集隨k增大性能變差；(a)中對k值不敏感，幾乎沒有變化；(b)隨k值增大性能變好，且在kgt; 10后趨于平穩；在(d)中不同的數據集隨著k值的變化，性能既有增加的，也有降低的，但總體上在k=10時，能有較好的性能。這是由于k值直接關系著預測樣本的匹配超邊數量，當k太小時與之匹配的超邊數量太小，會漏掉一些相關標簽，k值太大則會引入噪聲標簽且會影響算法運行效率，故本文將k取為10。

(a)算法SEI-MLHN在各個數據集下對應不同k值的Hamming Loss變化情況

(b)算法SEI-MLHN在各個數據集下對應不同k值的Ranking Loss變化情況

(c)算法SEI-MLHN在各個數據集下對應不同k值的One-error變化情況

(d)算法SEI-MLHN在各個數據集下對應不同k值的Average Precision變化情況

(e)算法SEI-MLHN在各個數據集下對應不同k值的Example Based F1變化情況圖3 算法SEI-MLHN在各個數據集下對應不同k值的分類性能比較Fig.3 Performance comparison of SEI-MLHN under different values of k on Data Sets

(a)算法SEI-MLHN在各個數據集下對應不同c值的Hamming Loss變化情況

(b)算法SEI-MLHN在各個數據集下對應不同c值的Ranking Loss變化情況

(c)算法SEI-MLHN在各個數據集下對應不同c值的One-error變化情況

(d)算法SEI-MLHN在各個數據集下對應不同c值的Average Precision變化情況

(e)算法SEI-MLHN在各個數據集下對應不同c值的Example Based F1變化情況

(f)算法SEI-MLHN在各個數據集下對應不同c值的Train time變化情況圖4 算法SEI-MLHN在各個數據集下對應不同c值的分類性能比較Fig.4 Performance comparison of SEI-MLHN under different values of c on Data Sets

圖4中，(a)、(c)、(d)、(e)中算法SEI-MLHN在各個數據集中的性能幾乎不變或變化幅度非常小，說明Hamming Loss 、One-error、Average Precision 和Example BasedF1對c和s的變化不敏感，(b)中SEI-MLHN的性能在數據集nuswide-cVLADplus中隨c和s的增大有小幅度的優化，(f)中可以看出較小規模數據隨簇數c和s的增加訓練時間小幅增加，而對于大規模數據集，算法訓練時間大幅減少。故本文對樣本數量小于10 000的訓練集，c和s分別選取4和2；樣本數量在10 000到100 000之間的訓練集，c和s分別選取9和3；樣本數量大于100 000的訓練集，c和s分別選取25和5。

3.4.2 分類性能比較

在實驗中，所有的多標簽學習算法均采用相同的數據劃分，用50%的數據進行訓練，其余50%的數據進行測試。在計算評價指標時，評價指標取重復10次實驗的平均值。由于比較的部分算法無法在一周內對數據集nuswide-cVLADplus、nuswide-bow完成訓練預測，故在對算法性能進行比較與分析時只取其余9個數據集進行實驗，如表5所示。在表6中列出了本文算法在nuswide-bow、nuswide-cVLADplus數據集上的評價指標值。

表5為5個不同評價指標下各個多標簽學習算法在常規規模的數據集上的學習性能，表5中評價指標后的“↓”表示指標取值越小性能越佳，符號“↑”表示指標取值越大性能越佳,其中AveR表示該算法的平均排名。此外，表7對每個學習算法進行編號，例如BRSVM(A1)表示用A1代表算法BRSVM，再進一步給出了各多標簽學習算法之間的相對性能，具體為，給定算法A1和A2，A1gt;A2表示在給定的評價指標上，基于顯著度0.05的威爾科克森符號秩檢驗(Wilcoxon signed rank test)，算法A1的性能顯著優于A2。本文通過打分的方式對各學習算法的性能進行總體評價，若A1gt;A2，則A1的分數加1，A2的分數減1，通過比較每個算法的最終分數，可以對算法進行排序，其中A1分數高于A2，表示算法A1的總體性能優于A2。

從表7中可以發現，算法SEI-MLHN在除Ranking loss外的各項指標以及總分均顯著高于其余算法，表明它的分類性能在總體上優于其余算法。其次, 算法SI-MLHN在Example basedF1上明顯優于S-CoMLHN，說明SI-MLHN在一定程度上削弱了標簽不平衡的影響，雖然算法SI-MLHN在Hanmming Loss和Ranking loss上稍劣于S-CoMLHN，但從整體性能上進行比較，算法SI-MLHN仍優于S-CoMLHN。再次，算法COCOA考慮了標簽間的高階關系且削弱了不平衡性的影響，但在Hanmming Loss上的性能較差，導致總分稍低于S-CoMLHN，也說明其總體性能稍低于S-CoMLHN。最后，可以從表7中得出結論，本文所提出的算法SEI-MLHN具有很好的處理多標簽分類問題的能力。

3.4.3 運行效率比較

為了對算法S-CoMLHN、SI-MLHN以及SEI-MLHN的運行時間進行比較，本文用3個較大規模數據集(eurlex-sm、eurlex-dc、mediamill)和2個大規模數據集(nuswide-bow 、nuswide-cVLADplus)進行實驗，且令所有實驗的SparkTask為32。由于S-CoMLHN在24小時內無法完成2個大規模數據集的訓練和預測，故圖5中無對比結果。

從圖5(a)中觀察到，算法S-CoMLHN的訓練時間顯著高于SI-MLHN和SEI-MLHN，且在數據集nuswide-bow 和nuswide-cVLADplus上沒有得到有效結果，說明該算法不能很好地適應大規模數據。在數據集eurlex-sm、eurlex-dc-leaves、mediamill上，算法SEI-MLHN與SI-MLHN的訓練時間沒有較大的區別，但是當數據集規模增大時，算法SEI-MLHN的訓練時間明顯低于SI-MLHN，表明算法SEI-MLHN比SI-MLHN大大縮短了訓練時間。從圖5(b)中觀察到，在數據集eurlex-sm、eurlex-dc、mediamill上，S-CoMLHN、SI-MLHN以及SEI-MLHN的測試時間沒有較大的區別，但是當數據集規模增大后，S-CoMLHN無法得到有效結果，且算法SEI-MLHN的測試時間也明顯低于SI-MLHN，說明算法SEI-MLHN也縮短了算法的測試時間。從圖5中可以得到結論，算法SEI-MLHN具有較高的算法運行效率，且對大規模數據集具有良好的適應能力。

由于不同的SparkTask數值會對算法的運行時間產生影響，因此，為了測試SparkTask對算法SEI-MLHN運行效率的影響，選擇了不同大小規模的數據集進行實驗。圖6給出了隨不同的任務數，算法SEI-MLHN在各個數據集下的訓練與測試時間的變化情況，時間以秒為單位。從圖6中觀察得到，對規模較小的多標簽數據集，如emontions、yeast，不同的SparkTask數值對算法的運行時間沒有較大的影響。而對于較大規模數據集mediamil，隨著SparkTask數值的增加，算法的訓練時間與測試時間急速下降，最后趨于平穩，但是當SparkTask增加到一定數量時訓練測試時間均增大，這是因為當數據集規模不夠大，SparkTask達到某個飽和點時，集群上各個節點的通信時間遠遠大于計算時間，算法的性能趨于平緩甚至變弱。

表5 比較算法在5個評價指標上的實驗結果(均值、排名)

續表5

續表5

表6 SI-MLHN和SEI-MLHN在數據集nus-wide-full-cVLADplus和nuswide-bow上的性能指標(均值±方差)

表7 各多標簽學習算法在不同數據集上的相對性能比較

(a)訓練時間變化情況

(b)測試時間變化情況

(a)訓練時間變化情況

(b)測試時間變化情況

4 結束語

本文基于MLHN提出了一種能有效利用標簽相關性處理大數據集Spark平臺下的改進多標簽超網絡集成算法SEI-MLHN。該算法首先引入代價敏感，使其適應不平衡數據集并提升算法性能。然后，在超網絡演化學習過程中利用抽樣信息，以及修改損失函數，降低算法時間復雜度。最后，進行選擇性集成，提高算法性能。在11個不同規模的數據集上進行實驗，結果表明，該算法具有良好的分類性能、較低的時間復雜度以及良好的處理大規模數據集的能力。

在SEI-MLHN中，我們只考慮標簽之間的相關性，即標簽的同現。然而，標簽之間的排他關系對于多標簽分類也很重要。在未來，我們將研究如何利用超網絡標簽之間的包含性和排他性。

[1]GAO S, WU W, LEE C H, et al. A MFoM learning approach to robust multiclass multi-label text categorization[C]//Proceedings of the 21st International Conference on Machine Learning. Canada: ACM Press, 2004: 42.

[2]JIANG J Y, TSAI S C, LEE S J. FSKNN: multi-label text categorization based on fuzzy similarity and k nearest neighbors[J]. Expert systems with applications, 2012, 39(3): 2813-2821.

[3]BOUTELL M R, LUO J, SHEN X, et al. Learning multi-label scene classification ☆[J]. Pattern recognition, 2004, 37(9):1757-1771.

[4]QI G J, HUA X S, RUI Y, et al. Correlative multi-label video annotation[C]//In Proceedings of the 15th ACM International Conference on Multimedia. Germany: ACM Press, 2007: 17-26.

[5]CESA-BIANCHI N, RE M, VALENTINI G. Synergy of multi-label hierarchical ensembles, data fusion, and cost-sensitive methods for gene functional inference[J]. Machine learning, 2012, 88(1): 209-241.

[6]ZHANG M L, ZHANG K. Multi-label learning by exploiting label dependency[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. USA: ACM Press, 2010: 999-1008.

[7]TSOUMAKAS G, KATAKIS I, VLAHAVAS I. Mining multi-label data[M]. New York: Springer US, 2009: 667-685.

[8]FüRNKRANZ J, HüLLERMEIER E, MENCíA E L, et al. Multilabel classification via calibrated label ranking[J]. Machine Learning, 2008, 73(2):133-153.

[9]TSOUMAKAS G, KATAKIS I, VLAHAVAS I. Randomk-Labelsets for Multilabel Classification[J].IEEE transactions on knowledge amp; data engineering, 2010, 23(7): 1079-1089.

[10]LO H Y, LIN S D, WANG H M. Generalizedk-labelsets ensemble for multi-label and cost-sensitive classification[J]. Knowledge amp; data engineering IEEE transactions on, 2014, 26(7):1679-1691.

[11]HE H, GARCIA E A. Learning from imbalanced data[J]. IEEE transactions on knowledge and data engineering, 2009, 21(9):1263-1284.

[12]XIOUFIS E S, SPILIOPOULOU M, TSOUMAKAS G, et al. Dealing with concept drift and class imbalance in multi-label stream classification[C]//IJCAI 2011 Proceedings of the International Joint Conference on Artificial Intelligence. Barcelona, Spain, 2011:1583-1588.

[13]CHARTE F, RIVERA A, del JESUS M J, et al. A first approach to deal with imbalance in multi-label datasets[C]//In Proceedings of the International Conference on Hybrid Artificial Intelligence Systems. Springer Berlin Heidelberg, USA, 2013: 150-160.

[14]ZHANG M L, LI Y K, LIU X Y. Towards class-imbalance aware multi-label learning[C]//Proceedings of the 24th International Joint Conference on Artificial Intelligence. Argentina: AAAI Press, 2015: 4041-4047.

[15]LIU H, LI X, ZHANG S. Learning instance correlation functions for multilabel classification[J]. IEEE transactions on cybernetics, 2017, 47(2): 499-510.

[16]ZHANG M L, WU L. Lift: multi-label learning with label[J]. Pattern analysis amp; machine intelligence IEEE transactions on, 2015, 37(1):107-20.

[17]ALALI A, KUBAT M. PruDent: A pruned and confident stacking approach for multi-label classification[J]. IEEE transactions on knowledge amp; data engineering, 2015, 27(9):1-1.

[18]WU Q, TAN M, Song H, et al. ML-forest: a multi-label tree ensemble method for multi-label classification[J]. IEEE transactions on knowledge and data engineering, 2016, 28(10):1-1.

[19]HUANG J, LI G, HUANG Q, et al. Learning label-specific features and class-dependent labels for multi-label classification[J].IEEE transactions on knowledge and data engineering, 2016, 28(12):3309-3323.

[20]WU Q, YE Y, ZHANG H, et al. ML-Tree: a tree-structure-based approach to multilabel learning.[J]. IEEE trans neural netw learn syst, 2014, 26(3):430-443.

[21]CHARTE F. LI-MLC: A Label Inference Methodology for Addressing High Dimensionality in the Label Space for Multilabel Classification[J]. IEEE trans. neural networks and learning systems, 2014, 25(10): 1842-1854.

[23]LO H Y, LIN S D, WANG H M. Generalizedk-labelsets ensemble for multi-label and cost-sensitive classification[J]. Knowledge and data engineering IEEE transactions on, 2014, 26(7):1679-1691.

[24]SUN K W, LEE C H, WANG J. Multilabel classification via co-evolutionary multilabel hypernetwork[J]. IEEE transactions on knowledge and data engineering, 2016, 28(9):1-1.

[25]LO H Y, WANG J C, WANG H M, et al. Cost-sensitive multi-label learning for audio tag annotation and retrieval[J]. IEEE transactions on multimedia, 2011, 13(3): 518-529.

[26]OZONAT K, YOUNG D. Towards a universal marketplace over the web: statistical multi-label classification of service provider forms with simulated annealing[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2009:1295-1304.

[27]ZHANG M L, ZHOU Z H. A review on multi-label learning algorithms[J]. IEEE transactions on knowledge and dada engineering, 2014, 26( 8): 1819-1837.

[28]ZHANG M L, ZHANG K. Multi-label learning by exploiting label dependency[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. USA: ACM Press, 2010: 999-1008.

[29]ZHANG M L, ZHOU Z H. ML-KNN: A lazy learning approach to multi-label learning[J]. Pattern recognition, 2007, 40(7):2038-2048.

[30]BOUTELL M R, LUO J, SHEN X, et al. Learning multi-label scene classification[J]. Pattern recognition, 2004, 37(9):1757-1771.

[31]ELISSEEFF A, WESTON J. A kernel method for multi-labelled classification[C]//In NIPS’01 Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic. Vancouver, British Columbia, Canada: MIT Press, 2001:681-687.

[32]ZHANG M L, ZHOU Z H. Multilabel neural networks with applications to functional genomics and text categorization[J]. IEEE transactions on knowledge and data engineering, 2006, 18(10): 1338-1351.

[33]READ J, PFAHRINGER B, HOLMES G, et al. Classifier chains for multi-label classification[J]. Machine learning, 2011, 85(3): 254-269.

[34]YI L, RONG J, LIU Y. Semi-supervised Multi-label Learning by Constrained Non-negative Matrix Factorization.[C]//In AAAI’06 Proceedings of the 21st national conference on Artificial intelligence. Boston: AAAI Press,2006:421-426.

[35]LIU X Y, LI Q Q, ZHOU Z H. Learning imbalanced multi-class data with optimal dichotomy weights[C]//Proceedings of the 2013 IEEE 13th International Conference on Data Mining. USA: IEEE Press, 2013: 478-487.

[36]TAHIR M A, KITTLER J, MIKOLAJCZYK K, et al. Improving multilabel classification performance by using ensemble of multi-label classifiers[C]//Proceedings of the International Workshop on Multiple Classifier Systems. Egypt: Springer Berlin Heidelberg, 2010: 11-21.

[37]DEAN J, GHEMAWAT S. MapReduce: Simplified data processing on large clusters[C]//In OSDI’04 Proceedings of the 6th conference on Symposium on Opearting Systems Design amp; Implementation. Berkeley, USA, 2004: 10-10.

[38]ZAHARIA M, CHOWDHURY M, FRANKLIN M J, et al. Spark: cluster computing with working sets[C]//In HotCloud’10 Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing. Berkeley, USA, 2010: 10-10.

[39]MIKA P. Flink: semantic web technology for the extraction and analysis of social networks[J]. Web semantics science services and agents on the world Wide Web, 2005, 3(2/3): 211-223.

[40]BU Y, HOWE B, BALAZINSKA M, et al. HaLoop: efficient iterative data processing on large clusters[J]. Proceedings of the Vldb endowment, 2010, 3(1/2): 285-296.

[41]ZAHARIA M, CHOWDHURY M, DAS T, et al. Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing[C]//In Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. San Jose: USENIX Association, 2012: 2.

[42]VESANTO J, ALHONIEMI E. Clustering of the self-organizing map[J]. IEEE transactions on neural networks, 2000, 11(3): 586-600.

[43]LEE S J, JIANG J Y. Multilabel text categorization based on fuzzy relevance clustering[J]. IEEE transactions on fuzzy systems, 2014, 22(6): 1457-1471.

[44]CHENG W, HüLLERMEIER E. Combining instance-based learning and logistic regression for multilabel classification[J]. Machine learning, 2009, 76(2):211-225.

李航, 女，1995年生,碩士研究生，主要研究方向為機器學習與數據挖掘。

王進，男，1979 年生，教授，博士，主要研究方向為大數據并行處理與分布式計算、大規模數據挖掘與機器學習。曾主持多項國家和重慶市科研課題，發表學術論文50多篇，其中被SCI檢索10篇，授權專利13項。

趙蕊，男，1990年生，碩士研究生，主要研究方向為機器學習與數據挖掘。發表學術論文2篇，均被EI檢索。

Multi-labelhypernetworkensemblelearningbasedonSpark

LI Hang1， WANG Jin2， ZHAO Rui2

(1.College of Software Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China; 2. Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

Multi-label learning has attracted a great deal of attention in recent years and has a wide range of potential real-world applications, including image identification and text categorization. Although great effort has been expended in the development of multi-label learning, two main challenges remain, i.e., how to utilize the correlation between labels and how to tackle large-scale multi-label data. To solve these challenges, based on the multi-label hypernetwork (MLHN) algorithm, in this paper, we propose a Spark-based multi-label hypernetwork ensemble algorithm (SEI-MLHN) that effectively utilizes label correlation and can deal with large-scale multi-label datasets. First, the algorithm introduces cost sensitivity to enable it to adapt to unbalanced datasets. Secondly, it improves the hypernetwork evolution learning process, optimizes the loss function, and reduces the inherent time complexity. Lastly, it uses selective ensemble learning to enable it to adapt to large-scale datasets. We conducted experiments on 11 datasets wit different scales. The results show that the proposed algorithm demonstrates excellent categorization performance, low time complexity, and the capability to handle large-scale datasets.

multi-label learning; hypernetwork; label correlations; Apache Spark; selective ensemble learning

10.11992/tis.201706033

http://kns.cnki.net/kcms/detail/23.1538.TP.20170831.1058.018.html

TP181

A

1673-4785(2017)05-0624-16

中文引用格式：李航，王進，趙蕊.基于Spark的多標簽超網絡集成學習J.智能系統學報， 2017, 12(5): 624-639.

英文引用格式：LIHang，WANGJin，ZHAORui.Multi-labelhypernetworkensemblelearningbasedonSparkJ.CAAItransactionsonintelligentsystems, 2017, 12(5): 624-639.

2017-06-09. < class="emphasis_bold">網絡出版日期

日期：2017-08-31.

重慶市基礎與前沿研究計劃項目(cstc2014jcyjA40001，cstc2014jcyjA40022);重慶教委科學技術研究項目(自然科學類)(KJ1400436).

李航.E-mail:1326202954@qq.com.