李航，王進(jìn)，趙蕊

(1.重慶郵電大學(xué) 軟件工程學(xué)院，重慶 400065； 2. 重慶郵電大學(xué) 計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

基于Spark的多標(biāo)簽超網(wǎng)絡(luò)集成學(xué)習(xí)

李航1，王進(jìn)2，趙蕊2

(1.重慶郵電大學(xué) 軟件工程學(xué)院，重慶 400065； 2. 重慶郵電大學(xué) 計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

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

多標(biāo)簽學(xué)習(xí)；超網(wǎng)絡(luò)；標(biāo)簽相關(guān)性；Apache Spark；選擇性集成學(xué)習(xí)

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

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

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

多標(biāo)簽超網(wǎng)絡(luò)MLHN與協(xié)同演化多標(biāo)簽超網(wǎng)絡(luò)Co-MLHN[24]可以挖掘標(biāo)簽間的高階關(guān)系，它將傳統(tǒng)的超網(wǎng)絡(luò)轉(zhuǎn)為多標(biāo)簽超網(wǎng)絡(luò)，用超邊和超邊的權(quán)重來表示特征子集與標(biāo)簽之間的高階關(guān)系，利用了任意標(biāo)簽間的相關(guān)性，且計(jì)算復(fù)雜度隨標(biāo)簽數(shù)量的增加呈線性增長，但是其算法時(shí)間復(fù)雜度與樣本數(shù)量呈平方級關(guān)系，不能很好地處理規(guī)模較大的數(shù)據(jù)集,同時(shí)算法也未考慮到標(biāo)簽不平衡對性能的影響。

針對目前多標(biāo)簽超網(wǎng)絡(luò)存在的問題，本文基于MLHN的思想，提出了Spark平臺(tái)下的改進(jìn)多標(biāo)簽超網(wǎng)絡(luò)集成算法SEI-MLHN，有效且高效地解決了多標(biāo)簽學(xué)習(xí)問題。首先對多標(biāo)簽數(shù)據(jù)集進(jìn)行劃分；然后對劃分后的數(shù)據(jù)分別用基于Spark平臺(tái)的改進(jìn)超網(wǎng)絡(luò)算法SI-MLHN進(jìn)行訓(xùn)練，形成多個(gè)局部超網(wǎng)絡(luò)；最后對多個(gè)局部超網(wǎng)絡(luò)進(jìn)行選擇性集成完成對測試樣本的預(yù)測。其中，SI-MLHN利用MLHN的思想并在Spark平臺(tái)下進(jìn)行改進(jìn)，首先計(jì)算每個(gè)樣本的k近鄰，然后利用k近鄰對超網(wǎng)絡(luò)進(jìn)行演化學(xué)習(xí)，得到演化超網(wǎng)絡(luò)。

為了評估本文算法的性能以及對大規(guī)模數(shù)據(jù)集的適應(yīng)性，選用不同規(guī)模數(shù)據(jù)集來進(jìn)行對比實(shí)驗(yàn)，驗(yàn)證了本文算法具有良好性能以及具備處理大規(guī)模數(shù)據(jù)集的能力。本文的主要貢獻(xiàn)如下：

1)引入了代價(jià)敏感，使其能良好地適應(yīng)多標(biāo)簽不平衡數(shù)據(jù)，提升算法性能；

2)改良了超網(wǎng)絡(luò)演化學(xué)習(xí)過程，大幅度降低MLHN算法的計(jì)算復(fù)雜度；

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

4)基于Spark計(jì)算框架實(shí)現(xiàn)算法，使算法實(shí)現(xiàn)并行，提高算法運(yùn)行效率。

1 相關(guān)工作

雖然多標(biāo)簽學(xué)習(xí)已經(jīng)成功應(yīng)用于生物信息學(xué)、音頻分類[25]以及web挖掘[26]等多個(gè)領(lǐng)域，但是由于多標(biāo)簽分類器的輸出空間為指數(shù)級，以及現(xiàn)在大部分應(yīng)用的數(shù)據(jù)集規(guī)模日益增加，對多標(biāo)簽學(xué)習(xí)造成了很大的挑戰(zhàn)。

為了應(yīng)對分類器輸出空間數(shù)量巨大這個(gè)問題，現(xiàn)有的方法是利用標(biāo)簽相關(guān)性來促進(jìn)學(xué)習(xí)過程?；跇?biāo)簽關(guān)聯(lián)性，張敏靈和周志華[27-28]將現(xiàn)有的學(xué)習(xí)算法分為3類，分別為一階策略、二階策略以及高階策略。一階策略是簡單地將多標(biāo)簽學(xué)習(xí)轉(zhuǎn)為多個(gè)獨(dú)立的二分類問題來解決多標(biāo)簽學(xué)習(xí)問題，例如ML-KNN[29]、BR[30]等；二階策略通過利用標(biāo)簽之間的成對關(guān)系解決多標(biāo)簽學(xué)習(xí)問題，例如CLR[31]、BP-MLL[32]等；高階策略通過探索標(biāo)簽之間的高階關(guān)系來解決多標(biāo)簽學(xué)習(xí)問題，例如CC[33]、CNMF[34]等。對這3種策略進(jìn)行比較分析，一階策略的效率高且概念易理解，但忽略了標(biāo)簽相關(guān)性。二階策略在一定程度上解決了標(biāo)簽相關(guān)性，但忽略了現(xiàn)實(shí)世界中相關(guān)性超過二階的情況。高階策略具有比一階和二階更強(qiáng)的建模能力，但是其計(jì)算復(fù)雜度更高，可擴(kuò)展性更低。

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

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

綜上所述，為了解決上述問題，本文使用Spark計(jì)算框架作為平臺(tái)來實(shí)現(xiàn)多標(biāo)簽算法。

2 Spark下改進(jìn)多標(biāo)簽超網(wǎng)絡(luò)集成算法

MLHN可以高效地挖掘標(biāo)簽間的關(guān)聯(lián)性且學(xué)習(xí)復(fù)雜度與標(biāo)簽維度呈線性關(guān)系，因此本文基于MLHN算法提出了Spark平臺(tái)下的改進(jìn)多標(biāo)簽超網(wǎng)絡(luò)集成算法SEI-MLHN，高效地解決了多標(biāo)簽問題。首先，對多標(biāo)簽數(shù)據(jù)集進(jìn)行劃分，然后對劃分后的數(shù)據(jù)分別用SI-MLHN算法進(jìn)行訓(xùn)練，形成多個(gè)局部超網(wǎng)絡(luò)，最后對多個(gè)局部超網(wǎng)絡(luò)進(jìn)行選擇性集成完成對測試樣本的預(yù)測。其中，算法SI-MLHN利用MLHN的思想，在Spark平臺(tái)下進(jìn)行改進(jìn)，首先計(jì)算每個(gè)樣本的k近鄰，然后利用k近鄰對超網(wǎng)絡(luò)進(jìn)行演化學(xué)習(xí)，得到超網(wǎng)絡(luò)。本節(jié)中，將對算法MLHN，MLHN的改進(jìn)算法SI-MLHN，以及以SI-MLHN為基學(xué)習(xí)器進(jìn)行選擇性集成的算法SEI-MLHN依次進(jìn)行介紹。

2.1 多標(biāo)簽演化超網(wǎng)絡(luò)(MLHN)

多標(biāo)簽演化超網(wǎng)絡(luò)利用超邊集合以及超邊權(quán)重來表示樣本特征子集與多標(biāo)簽類別之間的高階關(guān)聯(lián)。通過演化學(xué)習(xí)，可以近似地表示訓(xùn)練樣本X和其標(biāo)簽Y之間的概率分布P(X,Y)，在MLHN中可以按式(1)進(jìn)行表示：

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

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

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

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

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

2.2 Spark下改進(jìn)多標(biāo)簽超網(wǎng)絡(luò)(SI-MLHN)

MLHN是一種有效的多標(biāo)簽學(xué)習(xí)算法，但是目前的MLHN算法計(jì)算復(fù)雜度高，且對多標(biāo)簽數(shù)據(jù)的不平衡特性沒有關(guān)注。本文一方面改進(jìn)了MLHN的訓(xùn)練過程，引入了代價(jià)敏感；另一方面通過并行計(jì)算來降低運(yùn)算時(shí)間，設(shè)計(jì)了Spark下改進(jìn)多標(biāo)簽超網(wǎng)絡(luò)，記作SI-MLHN。在本小節(jié)，將分別介紹SI-MLHN的多標(biāo)簽分類學(xué)習(xí)過程和演化學(xué)習(xí)過程。

2.2.1 SI-MLHN分類學(xué)習(xí)過程

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

式(4)：

式中：yni為樣本x的第i個(gè)標(biāo)簽;wji為超邊集合|E|中ej的第i個(gè)權(quán)重向量的值;I(xn,yni;ej)的計(jì)算方法如式(2);costi為第i個(gè)標(biāo)簽的代價(jià)值，計(jì)算方式如式(7)：

式中T為有m個(gè)樣本的訓(xùn)練集。

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

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

算法1 SI-MLHN分類學(xué)習(xí)過程

輸入訓(xùn)練集T,測試樣本xn,標(biāo)簽數(shù)q，近鄰數(shù)量k, SI-MLHN模型H,標(biāo)簽閾值ti;

輸出標(biāo)簽概率p,預(yù)測標(biāo)簽y*。

1)在訓(xùn)練集T中計(jì)算xn的k近鄰

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

3)從U中提取標(biāo)簽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中提取標(biāo)簽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演化學(xué)習(xí)過程

SI-MLHN利用超邊的頂點(diǎn)和權(quán)重向量來代表多標(biāo)簽數(shù)據(jù)標(biāo)簽間的高階關(guān)聯(lián)，其權(quán)重向量由超邊從訓(xùn)練集中演化學(xué)習(xí)而來，首先進(jìn)行了超邊初始化，然后進(jìn)行了超邊替代與梯度下降演化學(xué)習(xí)，并利用Spark進(jìn)行分布式并行計(jì)算，通過多個(gè)操作技巧，如cache、broadst，將變量緩存于內(nèi)存中，大量減少了網(wǎng)絡(luò)交換數(shù)據(jù)量和磁盤I/O操作，使算法更高效。

由于超邊頂點(diǎn)向量v為隨機(jī)的，為了更好地?cái)M合訓(xùn)練樣本，需要通過超邊替代來選擇適應(yīng)度高的超邊。如果新生成的超邊適應(yīng)值高于現(xiàn)有超邊，則替換該超邊。適應(yīng)值的計(jì)算方法如式(9)所示：

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

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

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

算法2 SI-MLHN演化學(xué)習(xí)算法

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

輸出SI-MLHN:H。

1)Tnor=T.map

2)每條樣本進(jìn)行歸一化

3) end map.cache

4)TnorBro= broadcast(Tnor)

5)Tkv=Tnor.map

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

7)end map.map

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

9)end map

10)TkvBro= broadcast(Tkv)

11)Hini=Tkv.flatmap

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

13)end flatmap.cache

15)對超邊進(jìn)行tr次替代

16)end map.cache

17)fort←1 totddo

19)Htmp=Tkv.map

21)end map.flatmap

22)對超邊進(jìn)行梯度計(jì)算

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

25).map

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

27)end map

28)end for

30)returnH

2.3 Spark下集成多標(biāo)簽超網(wǎng)絡(luò)(SEI-MLHN)

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

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

算法3 S-SOM

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

簇個(gè)數(shù)c，學(xué)習(xí)率η，迭代次數(shù)ti;

1)Tnor=T.map

2)每條樣本進(jìn)行歸一化

3)end map.cache

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

5)WBro =broadcast(W)

6)fort←1 toti

7)for eachTnor的分區(qū) do

8)for each 分區(qū)內(nèi)樣本 do

9)利用輸出層計(jì)算獲勝節(jié)點(diǎn)

11)end for

12)end for

13)更新優(yōu)勝鄰域

15)end for

完成訓(xùn)練集分簇后，利用算法2對簇構(gòu)建SI-MLHN超網(wǎng)絡(luò)。對于測試集，SEI-MLHN將進(jìn)行選擇性集成，偽代碼見算法4。

算法4 SEI-MLHN分類算法

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

7)end for

9)E*=F.reduceByKey()

10).map

11)從s*k近鄰中選取最近k，利用算法1進(jìn)行預(yù)測

12)end map

13)returnE*

2.4 時(shí)間復(fù)雜度分析

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

3 實(shí)驗(yàn)

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

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

表1 實(shí)驗(yàn)使用的多標(biāo)簽數(shù)據(jù)集

3.2 評價(jià)指標(biāo)

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

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

式中Δ表示兩個(gè)集合的對稱差。

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

3)Ranking Loss：用于考察樣本的預(yù)測標(biāo)簽排序集合中的錯(cuò)排情況。

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

5) Example BasedF1:

3.3 比較的算法和實(shí)驗(yàn)環(huán)境

在本文中，將SEI-MLHN與兩種系列的算法進(jìn)行比較實(shí)驗(yàn)，第1種系列是常用的多標(biāo)簽學(xué)習(xí)算法，如表2的前8種算法所示，它們均在表3所示的單節(jié)點(diǎn)環(huán)境中實(shí)現(xiàn)。第二種系列是在Spark平臺(tái)下實(shí)現(xiàn)的超網(wǎng)絡(luò)多標(biāo)簽學(xué)習(xí)算法，如S-CoMLHN以及SEI-MLHN的基學(xué)習(xí)器SI-MLHN，Spark集群環(huán)境如表4所示，其中S-CoMLHN是Co-MLHN在Spark平臺(tái)下的實(shí)現(xiàn)。

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

表2 實(shí)驗(yàn)中的比較算法

表3 實(shí)驗(yàn)單節(jié)點(diǎn)環(huán)境

表4 集群環(huán)境配置

3.4 實(shí)驗(yàn)結(jié)果

3.4.1 參數(shù)分析

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

(a)算法SEI-MLHN在各個(gè)數(shù)據(jù)集下對應(yīng)不同k值的Hamming Loss變化情況

(b)算法SEI-MLHN在各個(gè)數(shù)據(jù)集下對應(yīng)不同k值的Ranking Loss變化情況

(c)算法SEI-MLHN在各個(gè)數(shù)據(jù)集下對應(yīng)不同k值的One-error變化情況

(d)算法SEI-MLHN在各個(gè)數(shù)據(jù)集下對應(yīng)不同k值的Average Precision變化情況

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

(a)算法SEI-MLHN在各個(gè)數(shù)據(jù)集下對應(yīng)不同c值的Hamming Loss變化情況

(b)算法SEI-MLHN在各個(gè)數(shù)據(jù)集下對應(yīng)不同c值的Ranking Loss變化情況

(c)算法SEI-MLHN在各個(gè)數(shù)據(jù)集下對應(yīng)不同c值的One-error變化情況

(d)算法SEI-MLHN在各個(gè)數(shù)據(jù)集下對應(yīng)不同c值的Average Precision變化情況

(e)算法SEI-MLHN在各個(gè)數(shù)據(jù)集下對應(yīng)不同c值的Example Based F1變化情況

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

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

3.4.2 分類性能比較

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

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

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

3.4.3 運(yùn)行效率比較

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

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

由于不同的SparkTask數(shù)值會(huì)對算法的運(yùn)行時(shí)間產(chǎn)生影響，因此，為了測試SparkTask對算法SEI-MLHN運(yùn)行效率的影響，選擇了不同大小規(guī)模的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。圖6給出了隨不同的任務(wù)數(shù)，算法SEI-MLHN在各個(gè)數(shù)據(jù)集下的訓(xùn)練與測試時(shí)間的變化情況，時(shí)間以秒為單位。從圖6中觀察得到，對規(guī)模較小的多標(biāo)簽數(shù)據(jù)集，如emontions、yeast，不同的SparkTask數(shù)值對算法的運(yùn)行時(shí)間沒有較大的影響。而對于較大規(guī)模數(shù)據(jù)集mediamil，隨著SparkTask數(shù)值的增加，算法的訓(xùn)練時(shí)間與測試時(shí)間急速下降，最后趨于平穩(wěn)，但是當(dāng)SparkTask增加到一定數(shù)量時(shí)訓(xùn)練測試時(shí)間均增大，這是因?yàn)楫?dāng)數(shù)據(jù)集規(guī)模不夠大，SparkTask達(dá)到某個(gè)飽和點(diǎn)時(shí)，集群上各個(gè)節(jié)點(diǎn)的通信時(shí)間遠(yuǎn)遠(yuǎn)大于計(jì)算時(shí)間，算法的性能趨于平緩甚至變?nèi)酢?/p>

表5 比較算法在5個(gè)評價(jià)指標(biāo)上的實(shí)驗(yàn)結(jié)果(均值、排名)

續(xù)表5

續(xù)表5

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

表7 各多標(biāo)簽學(xué)習(xí)算法在不同數(shù)據(jù)集上的相對性能比較

(a)訓(xùn)練時(shí)間變化情況

(b)測試時(shí)間變化情況

(a)訓(xùn)練時(shí)間變化情況

(b)測試時(shí)間變化情況

4 結(jié)束語

本文基于MLHN提出了一種能有效利用標(biāo)簽相關(guān)性處理大數(shù)據(jù)集Spark平臺(tái)下的改進(jìn)多標(biāo)簽超網(wǎng)絡(luò)集成算法SEI-MLHN。該算法首先引入代價(jià)敏感，使其適應(yīng)不平衡數(shù)據(jù)集并提升算法性能。然后，在超網(wǎng)絡(luò)演化學(xué)習(xí)過程中利用抽樣信息，以及修改損失函數(shù)，降低算法時(shí)間復(fù)雜度。最后，進(jìn)行選擇性集成，提高算法性能。在11個(gè)不同規(guī)模的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明，該算法具有良好的分類性能、較低的時(shí)間復(fù)雜度以及良好的處理大規(guī)模數(shù)據(jù)集的能力。

在SEI-MLHN中，我們只考慮標(biāo)簽之間的相關(guān)性，即標(biāo)簽的同現(xiàn)。然而，標(biāo)簽之間的排他關(guān)系對于多標(biāo)簽分類也很重要。在未來，我們將研究如何利用超網(wǎng)絡(luò)標(biāo)簽之間的包含性和排他性。

[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年生,碩士研究生，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘。

王進(jìn)，男，1979 年生，教授，博士，主要研究方向?yàn)榇髷?shù)據(jù)并行處理與分布式計(jì)算、大規(guī)模數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)。曾主持多項(xiàng)國家和重慶市科研課題，發(fā)表學(xué)術(shù)論文50多篇，其中被SCI檢索10篇，授權(quán)專利13項(xiàng)。

趙蕊，男，1990年生，碩士研究生，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘。發(fā)表學(xué)術(shù)論文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

中文引用格式：李航，王進(jìn)，趙蕊.基于Spark的多標(biāo)簽超網(wǎng)絡(luò)集成學(xué)習(xí)J.智能系統(tǒng)學(xué)報(bào)， 2017, 12(5): 624-639.

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

2017-06-09. < class="emphasis_bold">網(wǎng)絡(luò)出版日期

日期：2017-08-31.

重慶市基礎(chǔ)與前沿研究計(jì)劃項(xiàng)目(cstc2014jcyjA40001，cstc2014jcyjA40022);重慶教委科學(xué)技術(shù)研究項(xiàng)目(自然科學(xué)類)(KJ1400436).

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