孫霞,張敏超,馮筠,張蕾,何緋娟

(1.西北大學(xué)信息科學(xué)與技術(shù)學(xué)院,710127,西安;2.西安交通大學(xué)城市學(xué)院,710018,西安)

?

Hadoop框架下的多標(biāo)簽傳播算法

孫霞1,張敏超1,馮筠1,張蕾1,何緋娟2

(1.西北大學(xué)信息科學(xué)與技術(shù)學(xué)院,710127,西安;2.西安交通大學(xué)城市學(xué)院,710018,西安)

標(biāo)簽傳播算法的主要思想是利用已標(biāo)注數(shù)據(jù)的標(biāo)簽信息預(yù)測未標(biāo)注數(shù)據(jù)的標(biāo)簽信息。然而,傳統(tǒng)傳播算法沒有區(qū)別對(duì)待未標(biāo)注數(shù)據(jù)與已標(biāo)注數(shù)據(jù)相互之間的轉(zhuǎn)移信息,導(dǎo)致算法的收斂速度較慢,影響了算法的性能。針對(duì)傳統(tǒng)算法的不足,提出了差異權(quán)重標(biāo)簽傳播算法,算法按標(biāo)注信息的重要性賦予不同的權(quán)重。在解決了大規(guī)模特征矩陣相乘問題之后,將提出的差異權(quán)重標(biāo)簽傳播算法應(yīng)用到Hadoop框架下,采用分布式計(jì)算,實(shí)現(xiàn)了能夠處理大規(guī)模數(shù)據(jù)的多標(biāo)簽分類算法(HSML),并將提出的HSML算法與現(xiàn)有主流多標(biāo)簽分類算法進(jìn)行了性能比較。實(shí)驗(yàn)結(jié)果表明,HSML算法在多標(biāo)簽分類的各項(xiàng)性能評(píng)測指標(biāo)和執(zhí)行速度上都是有效的。

Hadoop;多標(biāo)簽分類;標(biāo)簽傳播算法

傳統(tǒng)分類學(xué)習(xí)問題研究如何將待分類樣本準(zhǔn)確地劃分到唯一的某一類中,即單標(biāo)簽分類。然而,真實(shí)世界的對(duì)象往往并不只具有唯一的語義。每個(gè)對(duì)象由多個(gè)類別標(biāo)注,學(xué)習(xí)的目標(biāo)是將所有合適的類別標(biāo)注賦予未見對(duì)象,即多標(biāo)簽分類學(xué)習(xí)。

多標(biāo)簽分類的研究對(duì)多義性對(duì)象學(xué)習(xí)模型的建立具有相當(dāng)重要的意義,現(xiàn)已逐漸成為國際機(jī)器學(xué)習(xí)界一個(gè)新的研究熱點(diǎn)[1-4]。目前,研究者針對(duì)多標(biāo)簽分類問題提出了基于問題轉(zhuǎn)化和基于算法轉(zhuǎn)化的兩大類解決方法。問題轉(zhuǎn)化法的主要思想是將多標(biāo)簽分類問題轉(zhuǎn)化為多個(gè)單標(biāo)簽分類,再利用已有的單標(biāo)簽分類方法完成分類任務(wù)。常見的問題轉(zhuǎn)化法是二元關(guān)系法(BR)[5]、標(biāo)簽冪集法(LP)[6]等。與問題轉(zhuǎn)化法不同,算法轉(zhuǎn)化法通過直接改進(jìn)已有的單標(biāo)簽分類算法進(jìn)行多標(biāo)簽分類。有多標(biāo)簽K近鄰(MLKNN)算法[7]、基于神經(jīng)網(wǎng)絡(luò)的反向傳播多標(biāo)簽分類算法(BPMLL)[8]、Rank-SVM多標(biāo)簽分類算法[9]等。

多標(biāo)簽學(xué)習(xí)所面臨的最大挑戰(zhàn)在于標(biāo)簽空間過大。若一個(gè)標(biāo)簽集合具有20個(gè)類別,則可能的類別標(biāo)簽集合數(shù)將超過一百萬(即220)。為了有效應(yīng)對(duì)標(biāo)注集合空間過大所造成的學(xué)習(xí)困難,本文提出了分布式學(xué)習(xí)框架下的多標(biāo)簽分類算法HSML。

1 差異權(quán)重的標(biāo)簽傳播算法

標(biāo)簽傳播算法(LPA)[10]是在2002年由Zhu等人提出的一種基于圖的半監(jiān)督學(xué)習(xí)方法,其主要思想是利用已標(biāo)注數(shù)據(jù)的標(biāo)簽信息來預(yù)測未標(biāo)注數(shù)據(jù)的標(biāo)簽信息。它首先用數(shù)據(jù)間的關(guān)系建立一個(gè)關(guān)系完全圖,圖中節(jié)點(diǎn)包含已標(biāo)注數(shù)據(jù)和未標(biāo)注數(shù)據(jù),連接兩個(gè)頂點(diǎn)的邊用相似度表示,頂點(diǎn)的標(biāo)簽信息通過轉(zhuǎn)移概率傳遞給其他相鄰頂點(diǎn),頂點(diǎn)間相似度越大,標(biāo)簽傳播的信息也就越多,反復(fù)迭代直到收斂。然而,在迭代過程中,傳統(tǒng)傳播算法沒有區(qū)別對(duì)待未標(biāo)注數(shù)據(jù)與已標(biāo)注數(shù)據(jù)相互之間的轉(zhuǎn)移信息,導(dǎo)致算法的收斂速度較慢,從而影響了算法的性能。針對(duì)傳統(tǒng)算法的不足,本文提出了差異權(quán)重的標(biāo)簽傳播算法。

1.1 算法思想

在傳播算法的每次迭代過程中,未標(biāo)注數(shù)據(jù)都被重新標(biāo)注。因此,將這些數(shù)據(jù)從未標(biāo)注數(shù)據(jù)集移到已標(biāo)注數(shù)據(jù)集中,與初始標(biāo)注數(shù)據(jù)集構(gòu)成新的標(biāo)注數(shù)據(jù)集,指導(dǎo)下次迭代,以達(dá)到提高分類準(zhǔn)確率的目的。初始標(biāo)簽矩陣F,記為

(1)

式中:FL為已標(biāo)注標(biāo)簽;FU為未標(biāo)注標(biāo)簽。標(biāo)簽之間的轉(zhuǎn)移概率矩陣為P,有

(2)

標(biāo)注轉(zhuǎn)移過程為:FL以PLL的轉(zhuǎn)移子陣向自身轉(zhuǎn)移,FL以PLU的轉(zhuǎn)移子陣向FU轉(zhuǎn)移,FU以PUU的轉(zhuǎn)移子陣向自身轉(zhuǎn)移,FU以PUL的轉(zhuǎn)移子陣向FL轉(zhuǎn)移。由于FL和FU所含的信息量不同,有標(biāo)簽數(shù)據(jù)向無標(biāo)簽數(shù)據(jù)轉(zhuǎn)移的信息要比無標(biāo)簽數(shù)據(jù)之間的相互轉(zhuǎn)移信息重要的多,更比無標(biāo)簽數(shù)據(jù)向有標(biāo)簽數(shù)據(jù)轉(zhuǎn)移的信息重要。若對(duì)這些不同子陣間的轉(zhuǎn)移不加以區(qū)分,會(huì)出現(xiàn)少量的真實(shí)信息被大量的虛假信息淹沒,導(dǎo)致分類效果降低。因此,對(duì)于PLU和PUL轉(zhuǎn)移子陣按信息的重要性賦予不同的權(quán)重。

1.2 算法描述

差異權(quán)重多標(biāo)簽傳播算法描述如下。

輸入:初始標(biāo)注訓(xùn)練集XL={(x1,y1),(x2,y2),…,(xl,yl)},未標(biāo)注訓(xùn)練集XU={x1,x2,…,xu}。

輸出:未標(biāo)注數(shù)據(jù)的標(biāo)簽FU。

步驟1 依據(jù)訓(xùn)練數(shù)據(jù)建立關(guān)系完全圖。

步驟4 根據(jù)已標(biāo)注數(shù)據(jù)初始化標(biāo)注矩陣F=(FL,FU),其中FU每個(gè)分量賦值1/C,依據(jù)已標(biāo)注數(shù)據(jù)的類標(biāo)注給相應(yīng)的FL賦值。

步驟6 從W中選出與xui最近鄰的K個(gè)已標(biāo)注樣本,如果這K個(gè)樣本中有K*個(gè)樣本的標(biāo)簽相同,則轉(zhuǎn)向步驟7,否則轉(zhuǎn)向步驟4中的下一個(gè)xui。

步驟9 把已標(biāo)注數(shù)據(jù)的概率分布設(shè)置為類的概率值。

步驟10 重復(fù)步驟4～9,直到F收斂。

2 HSML算法

若將一個(gè)有n(n>5)類別的多標(biāo)簽分類問題中大量的數(shù)據(jù)計(jì)算全部投入到單機(jī)上,可能造成計(jì)算時(shí)間過長或者內(nèi)存不足,從而引起分類失敗。為了有效應(yīng)對(duì)標(biāo)注集合空間過大所造成的學(xué)習(xí)困難,本文引入了Hadoop分布式框架[11-12]。Hadoop分布式框架分為Map和Reduce兩個(gè)部分,Map對(duì)一些獨(dú)立元素進(jìn)行相應(yīng)處理,Reduce是對(duì)處理結(jié)果的一個(gè)整合。本文把多標(biāo)簽學(xué)習(xí)問題分解成多個(gè)單標(biāo)簽學(xué)習(xí)問題,利用Map和Reduce構(gòu)建2n個(gè)單標(biāo)簽分類算法,最后整合各分類的結(jié)果,形成最終的多標(biāo)簽分類結(jié)果。

2.1 矩陣相乘

本文采用空間向量模型VSM表示每一個(gè)樣本。若每一個(gè)樣本用m維特征表示,則樣本集大小為n的訓(xùn)練數(shù)據(jù)可以表示成一個(gè)n×m矩陣,通常這樣的矩陣具有高維、稀疏的特點(diǎn),而高維、稀疏矩陣相乘存在耗時(shí)長、占用內(nèi)存高的問題,因此需要尋求高效解決矩陣相乘的方法。

傳統(tǒng)的矩陣運(yùn)算是矩陣A中的每一行分別與矩陣B中的每一列相乘。當(dāng)矩陣規(guī)模增大時(shí),受限于內(nèi)存大小,一臺(tái)服務(wù)器已經(jīng)無法處理。稀疏矩陣具有天然可分塊特性,出現(xiàn)了許多基于Hadoop的分塊矩陣計(jì)算方法。算法思想是:將矩陣A中的分塊分別與矩陣B相乘,通過Hadoop,每個(gè)分塊的矩陣相乘可在不同的計(jì)算節(jié)點(diǎn)完成,最后將結(jié)果組合,大大提高了計(jì)算速度。

最小粒度相乘算法具有不受限計(jì)算節(jié)點(diǎn)內(nèi)存限制的優(yōu)勢,成為矩陣相乘的主流算法。假設(shè)有兩個(gè)超大矩陣A和B,A是一個(gè)m×r矩陣,B是一個(gè)r×n矩陣,則A中的每個(gè)元素Aik與B中第k行元素Bkj依次相乘,計(jì)算結(jié)果分別為Cij中的一個(gè)組成部分;B中的每個(gè)元素Bkj與A中第j列元素Aik依次相乘,計(jì)算結(jié)果分別為Cij的一個(gè)組成部分。由于Aik×Bkj是獨(dú)立的,可由不同計(jì)算節(jié)點(diǎn)進(jìn)行運(yùn)算,最后依據(jù)(i,j)(記為key值)將運(yùn)算結(jié)果匯總相加,得到Cij。每個(gè)計(jì)算節(jié)點(diǎn)計(jì)算時(shí)只加載兩個(gè)數(shù)進(jìn)行相乘。理論上只要Hadoop的HDFS文件系統(tǒng)足夠大,就可以計(jì)算任意規(guī)模的矩陣相乘。然而在實(shí)際操作中,Map的每條輸入記錄只被處理一次便不再使用。因此,對(duì)于矩陣A中的每個(gè)元素,進(jìn)行乘法運(yùn)算之前,需要生成n個(gè)副本;對(duì)于矩陣B中每個(gè)元素,需要生成m個(gè)副本,并將相應(yīng)位置上的副本相對(duì)應(yīng)。例如,對(duì)于Aik需生成n個(gè)副本,與B中相應(yīng)元素對(duì)應(yīng)并以A中元素的行號(hào)、B中元素的列號(hào)作為key值,矩陣表示為

i-jAik-Bkj

(3)

這種方式勢必增加時(shí)間復(fù)雜度,降低可行性。因此,本文提出了改進(jìn)的基于Hadoop的最小粒度相乘算法。

2.2 改進(jìn)的最小粒度相乘算法

由于key值不具備明顯的區(qū)分度,且Map過程中內(nèi)存不保留矩陣元素,將數(shù)據(jù)組織成式(3)格式是極其困難的,在Map輸入前查詢數(shù)據(jù)庫所耗費(fèi)的時(shí)間也是難以接受的。不難發(fā)現(xiàn),最終結(jié)果CiJ是由r個(gè)值相加而成的,第k個(gè)組成成分為Aik-Bkj。為了使key值更具有區(qū)分度,將key值修改為

i-j-kAik,i-j-kBkj

(4)

這樣key值所代表的是兩個(gè)值相乘,得到了Cij中第k個(gè)組成元素。矩陣A與矩陣B在Map階段完成數(shù)據(jù)副本拷貝后,所有的Map數(shù)據(jù)記錄中i-j-k的key值有且至多有兩個(gè)。

由于矩陣A中每個(gè)元素理論上都需要被計(jì)算n遍,矩陣B中每個(gè)元素都需要被計(jì)算m遍,因此式(4)中有j=1,2,…,k,…,n;i=1,2,…,k,…,m。每個(gè)元素的副本拷貝都是獨(dú)立的,可由不同的Map進(jìn)行計(jì)算,故大大加快了拷貝的速度。

2.3 Hadoop下二元分類器構(gòu)建

HSML算法是對(duì)每個(gè)標(biāo)簽構(gòu)建一個(gè)二元分類器,最后再對(duì)整個(gè)結(jié)果進(jìn)行組合。Hadoop下的二元分類器構(gòu)建過程如圖1所示。

(1)首先對(duì)數(shù)據(jù)集進(jìn)行特征選擇。在后面的實(shí)驗(yàn)中,我們使用自建的數(shù)據(jù)集“Pubmed”,該數(shù)據(jù)集所處理的對(duì)象是文本數(shù)據(jù),因此選擇詞組作為文本特征。通過統(tǒng)計(jì)分析,僅提取DT+NN、JJ+NN、JJ+JJ+NN、JJ+JJ+NN+NNS、JJ+NN+NN、NN等形式的名詞詞組,其中DT是限定詞,JJ是形容詞,NN是單數(shù)名詞、NNS是復(fù)數(shù)名詞。然后,采用信息增益的方法計(jì)算詞特征權(quán)重,選擇大于閾值的那些詞表示數(shù)據(jù),同時(shí)提取標(biāo)注數(shù)據(jù)的標(biāo)簽特征屬性,分別得到特征向量矩陣和類別矩陣。

圖1 Hadoop下的二元分類器構(gòu)建過程

(2)第一個(gè)MapReduce階段是進(jìn)行矩陣計(jì)算,完成一次標(biāo)簽傳播過程。采用本文提出的改進(jìn)的最小粒度相乘算法,充分利用分布式計(jì)算特點(diǎn),實(shí)現(xiàn)了快速稀疏矩陣相乘。Reducer函數(shù)的輸出為式(4)的格式。

(3)第二個(gè)MapReduce階段是是采用1.2節(jié)提出的差異權(quán)重的標(biāo)簽傳播算法,對(duì)標(biāo)簽數(shù)據(jù)進(jìn)行重構(gòu)。有標(biāo)簽數(shù)據(jù)向無標(biāo)簽數(shù)據(jù)轉(zhuǎn)移的信息要比無標(biāo)簽數(shù)據(jù)之間相互轉(zhuǎn)移的信息重要,更比無標(biāo)簽數(shù)據(jù)向有標(biāo)簽數(shù)據(jù)轉(zhuǎn)移的信息重要,因此利用近鄰假設(shè),對(duì)各概率轉(zhuǎn)移子陣賦予不同的權(quán)重。在傳播算法過程中,未標(biāo)注數(shù)據(jù)被重新標(biāo)注,并將這些數(shù)據(jù)從未標(biāo)注數(shù)據(jù)集移到已標(biāo)注數(shù)據(jù)集中,與初始標(biāo)注數(shù)據(jù)集構(gòu)成新的標(biāo)注數(shù)據(jù)集,指導(dǎo)下次迭代。

(4)重復(fù)執(zhí)行上述兩個(gè)MapReduce過程,直到算法收斂。

(5)將最終結(jié)果表示成(標(biāo)簽,數(shù)據(jù)列表)二元組形式。

(6)對(duì)每個(gè)標(biāo)簽都執(zhí)行上述過程,最后整合結(jié)果完成多標(biāo)簽分類。

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

本實(shí)驗(yàn)平臺(tái)基本配置為HP臺(tái)式機(jī),Win7、Linux操作系統(tǒng),Intel酷睿i5處理器,2 GB內(nèi)存,1 TB硬盤,主要使用Matlab和Java編程語言實(shí)現(xiàn)。

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

實(shí)驗(yàn)釆用Emotions、Image、Yeast和Pubmed 4個(gè)數(shù)據(jù)集。前3個(gè)是公開數(shù)據(jù)集,可從數(shù)據(jù)堂[13]下載獲取,Pubmed是本文構(gòu)建的數(shù)據(jù)集。首先向PubMed數(shù)據(jù)庫提交“Lung Cancer”關(guān)鍵字,檢索并收集有關(guān)肺癌文獻(xiàn)摘要,然后提取文獻(xiàn)中的MeSH標(biāo)注作為該文獻(xiàn)的標(biāo)簽數(shù)據(jù)。實(shí)驗(yàn)中所使用的數(shù)據(jù)集基本信息如表1所示。

表1 數(shù)據(jù)集特征描述

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

本文采用的評(píng)價(jià)指標(biāo)有Hamming loss、One-error、Coverage、Ranking loss、Average-precision等。Hamming loss、One-error、Coverage、Ranking loss 4個(gè)評(píng)價(jià)指標(biāo)的值越小,說明多標(biāo)簽分類器的性能越好,而Average precision的值越大,說明多標(biāo)簽分類器的性能越好。

(1)Hamming loss度量多標(biāo)簽分類器預(yù)測出的標(biāo)簽與實(shí)際標(biāo)簽之間的差距,即

(5)

(2)One-error度量平均對(duì)每個(gè)樣本的預(yù)測標(biāo)簽排序中,排在第一位的標(biāo)簽不在該樣本的相關(guān)標(biāo)簽集中的概率,即

?Yi|

(6)

Coverage度量平均對(duì)每個(gè)樣本的預(yù)測標(biāo)簽排序中,需要在標(biāo)簽排序列表中最少查找到第幾位才可以找出所有與該樣本相關(guān)的標(biāo)簽,即

(7)

(3)Ranking loss度量所有樣本的預(yù)測標(biāo)簽排序中,不相關(guān)標(biāo)簽排在相關(guān)標(biāo)簽前面的平均概率

rankingloss(f)=

(8)

(4)Average precision度量所有樣本的預(yù)測標(biāo)簽排序中,排在相關(guān)標(biāo)簽前面的是相關(guān)標(biāo)簽的平均概率,即

(9)

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

表2對(duì)比了本文提出的HSML算法與現(xiàn)有主流多標(biāo)簽分類算法的性能。LIFT、ML-KNN以及BP-MLL算法源代碼可從文獻(xiàn)[14]下載獲取。

由表2可知,HSML算法在Hamming loss指標(biāo)上稍遜色于LIFT算法、在Coverage上分類性能比BP-MLL稍低以外,在其他指標(biāo)上均占優(yōu)勢。尤其是對(duì)于已標(biāo)注數(shù)據(jù)較少的數(shù)據(jù)集,HSML算法具有明顯優(yōu)勢,整體性能優(yōu)于其他3個(gè)算法,充分體現(xiàn)了半監(jiān)督算法對(duì)標(biāo)注數(shù)據(jù)量要求不高的優(yōu)點(diǎn)。

表2 4種多標(biāo)簽算法的分類性能

圖2展示了HSML在各數(shù)據(jù)集上的加速比,從而驗(yàn)證了該算法的執(zhí)行效率。

圖2 HSML在各數(shù)據(jù)集上的加速比

從圖2可以看出,當(dāng)機(jī)器數(shù)量越多時(shí),算法的加速比越大,算法的執(zhí)行效率越高。當(dāng)只有一臺(tái)主機(jī)時(shí),算法的加速均比小于1,這是因?yàn)镠adoop復(fù)制數(shù)據(jù)以及其它內(nèi)部操作消耗時(shí)間,默認(rèn)將數(shù)據(jù)備份2份的緣故。數(shù)據(jù)量越大,隨著主機(jī)數(shù)量增加,其加速比越大,這充分體現(xiàn)了HSML算法的優(yōu)勢,即更易處理大數(shù)據(jù)。

表3對(duì)比了各算法在Pubmed數(shù)據(jù)集上的訓(xùn)練與測試時(shí)間。從表3可知,HSML算法在Pubmed數(shù)據(jù)集上所花費(fèi)的時(shí)間最少。尤其是與ML-KNN算法相比,HSML算法無論是訓(xùn)練用時(shí)還是測試用時(shí)都明顯較少。這是由于ML-KNN是一種懶惰學(xué)習(xí)技術(shù),采用在線的方式對(duì)測試樣本的類標(biāo)注進(jìn)行預(yù)測,因此計(jì)算量大。

表3 各算法在Pubmed數(shù)據(jù)集上的訓(xùn)練與測試時(shí)間

綜上所述,HSML算法具有較好的性能,理論上在主機(jī)足夠多的情況下,能處理任意規(guī)模的大數(shù)據(jù)計(jì)算問題,充分發(fā)揮了Hadoop的優(yōu)越性。

4 總 結(jié)

傳統(tǒng)的標(biāo)簽傳播算法是一種基于流行假設(shè)的半監(jiān)督學(xué)習(xí)算法,通過迭代將標(biāo)注信息傳遞給鄰近節(jié)點(diǎn),由于沒有區(qū)別對(duì)待未標(biāo)注數(shù)據(jù)與已標(biāo)注數(shù)據(jù)相互之間轉(zhuǎn)移信息,導(dǎo)致算法的收斂速度較慢。本文在迭代過程中將標(biāo)注數(shù)據(jù)和未標(biāo)注數(shù)據(jù)的轉(zhuǎn)移概率按重要程度賦予相應(yīng)的權(quán)重,利用近鄰規(guī)則的Depuration數(shù)據(jù)剪輯技術(shù)把每次迭代后準(zhǔn)確標(biāo)注的未標(biāo)注數(shù)據(jù)加到標(biāo)注數(shù)據(jù),重構(gòu)標(biāo)注數(shù)據(jù),提出差異權(quán)重標(biāo)簽傳播算法,從而加快算法的收斂速度,提高算法性能。將多標(biāo)簽學(xué)習(xí)問題分解成多個(gè)單標(biāo)簽學(xué)習(xí)問題,造成標(biāo)簽空間過大。為了有效應(yīng)對(duì)這一挑戰(zhàn),在解決大規(guī)模矩陣相乘問題后,將提出的差別權(quán)重標(biāo)簽傳播算法應(yīng)用到Hadoop框架下,使算法能夠適應(yīng)大規(guī)模數(shù)據(jù)多標(biāo)簽分類問題。

[1] ZHANG Minling, ZHOU Zhihua. A review on multi-label learning algorithms [J]. IEEE Transactions on Knowledge & Data Engineering, 2014, 26(8): 1-59.

[2] XU Miao, LI Yufeng, ZHOU Zhihua. Multi-label learning with pro loss [C]∥Proceedings of the 27th AAAI Conference on Artificial Intelligence. Palo Alto, California, USA: AAAI, 2013: 998-1004.

[3] SUN Y Y, ZHANG Y, ZHOU Z H. Multi-label learning with weak label [C]∥24th AAAI Conference on Artificial Intelligence. Palo Alto, California, USA: AAAI, 2010:593-598.

[4] 孔祥南, 黎銘, 姜遠(yuǎn), 等. 一種針對(duì)弱標(biāo)記的直推式多標(biāo)記分類方法 [J]. 計(jì)算機(jī)研究與發(fā)展, 2010, 47(8): 1392-1399. KONG Xiangnan, LI Ming, JIANG Yuan, et al. A transductive multi-label classification method for weaklabeling [J]. Journal of Computer Research and Development, 2010, 47(8): 1392-1399.

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

[6] TSOUMAKAS G, VLAHAVAS I. Random k-labelsets: an ensemble method for multilabel classification [C]∥18th European Conference on Machine Learning. Berlin, Germany: Springer, 2007: 406-417.

[7] ZHANG Minling, ZHOU Zhihua. ML-kNN: a lazy learning approach to multi-label learning [J]. Pattern Recognition, 2007, 40(7): 2038-2048.

[8] ZHANG Minling, ZHOU Zhihua. Multilabel neural networks with applications to functional genomics and text categorization [J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(10): 1338-1351

[9] ELISSEEFF A, WESTON J. A kernel method for multi-labelled classification [C]∥Advances in Neural Information Processing Systems. Cambridge, MA, USA: MIT, 2002: 681-687.

[10]ZHU X J, GHAHRAMANI Z. Learning from labeled and unlabeled data with label propagation, CMU-CALD-02-107 [R]. Pittsburghers, USA: Carnegie Mellon University, 2002.

[11]Welcome to Apache [EB/OL]. [2013-10-14]. http:∥hadoop.apache.org.

[12]Hadoop 集群安裝 [EB/OL]. [2013-12-20]. http:∥blog.csdn.net/liou825/article/details/9320745.

[13]數(shù)據(jù)堂 [EB/OL]. [2014-04-01]. http:∥www.datatang.com/data/list.

[14]張敏靈個(gè)人主頁 [EB/OL]. [2014-04-01]. http:∥cse.seu.edu.cn/people/zhangml/Publication.htm.

[本刊相關(guān)文獻(xiàn)鏈接]

馬莉,唐善成,王靜,等.云計(jì)算環(huán)境下的動(dòng)態(tài)反饋?zhàn)鳂I(yè)調(diào)度算法.2014,48(7):77-82.[doi:10.7652/xjtuxb201407014]

陳秀真,李生紅,凌屹東,等.面向拒絕服務(wù)攻擊的多標(biāo)簽IP返回追蹤新方法.2013,47(10):13-17.[doi:10.7652/xjtuxb 201310003]

劉光輝,任慶昌,孟月波,等.自適應(yīng)先驗(yàn)馬爾可夫隨機(jī)場模型的圖像分割算法.2013,47(10):62-67.[doi:10.7652/xjtuxb201310011]

杜友田,辛剛,鄭慶華.融合異構(gòu)信息的網(wǎng)絡(luò)視頻在線半監(jiān)督分類方法.2013,47(7):96-101.[doi:10.7652/xjtuxb201307 018]

艾波,胡軍,張?jiān)缧?等.含缺陷蒸汽發(fā)生器管道爆破壓力預(yù)測的遺傳-神經(jīng)網(wǎng)絡(luò)算法.2011,45(9):84-89.[doi:10.7652/xjtuxb201109016]

徐勝軍,韓九強(qiáng),趙亮,等.用于圖像分割的局部區(qū)域能量最小化算法.2011,45(8):7-12.[doi:10.7652/xjtuxb201108 002]

溫超,耿國華,李展.構(gòu)建新包空間的多示例學(xué)習(xí)方法.2011,45(8):62-66.[doi:10.7652/xjtuxb201108011]

余思,桂小林,黃汝維,等.一種提高云存儲(chǔ)中小文件存儲(chǔ)效率的方案.2011,45(6):59-63.[doi:10.7652/xjtuxb201106 011]

(編輯 趙煒)

A Label Propagation Algorithm for Multi-Label Classification Using Hadoop Technology

SUN Xia1, ZHANG Minchao1, FENG Jun1, ZHANG Lei1, HE Feijuan2

(1. School of Information and Technology, Northwest University, Xi’an 710127, China; 2. Department of Computer Science, Xi’an Jiaotong University City College, Xi’an 710018, China)

A method of label propagation using Hadoop technology, named HSML, is proposed, to cope with the challenge of exponential-sized output space learning from multi-label data. Label propagation algorithms are graph-based semi-supervised learning methods, and use the label information of labeled data to predict the label information of unlabeled data. Traditional label propagation algorithms do not consider the posterior probability and distinguish information between labeled data and unlabeled data during the label propagation process, hence, the performance of traditional label propagation algorithms is affected. Therefore, a label propagation algorithm with different weights is proposed. After the multiplication problem of large-scale feature matrices is solved, the proposed algorithm is applied to the framework of Hadoop to deal with the problem of multi-label classification learning from big data. Experimental results and comparisons with some well-established multi-label learning algorithms, show that the performance of HSML is superior, and that the bigger test set is the faster HSML runs.

Hadoop; multi-label classification; label propagation algorithm

2014-11-18。

孫霞(1977—),女,副教授。

國家自然科學(xué)基金資助項(xiàng)目(61202184,61100166);陜西省教育廳資助項(xiàng)目(2013JK1152)。

10.7652/xjtuxb201505021

TP391

A

0253-987X(2015)05-0134-06