亢瀏越,黃 睿,孫廣玲

(上海大學(xué)通信與信息工程學(xué)院,上海 200444)

在傳統(tǒng)的機(jī)器學(xué)習(xí)框架中,一個(gè)對(duì)象只與單一類別的標(biāo)簽相關(guān)聯(lián)[1].然而,在實(shí)際應(yīng)用中,對(duì)象往往不是具有唯一語(yǔ)義的.例如,一篇新聞報(bào)道可以同時(shí)屬于“經(jīng)濟(jì)”和“體育”類,一幅圖像可以同時(shí)標(biāo)注為“大海”和“天空”等.此時(shí),傳統(tǒng)的機(jī)器學(xué)習(xí)框架難以取得較好的分類效果.為了更好地描述數(shù)據(jù)對(duì)象,需要給每個(gè)對(duì)象賦予多個(gè)合適的類別標(biāo)簽,多標(biāo)簽學(xué)習(xí)也由此產(chǎn)生.目前,多標(biāo)簽學(xué)習(xí)已被廣泛應(yīng)用于文本分類[2-3]、圖像標(biāo)注[4-5]、音樂(lè)情感分類[6-7]等領(lǐng)域.

隨著多標(biāo)簽學(xué)習(xí)研究的不斷深入,涌現(xiàn)出大量多標(biāo)簽分類算法.這些算法大致可分為問(wèn)題轉(zhuǎn)換和算法改造兩大類.問(wèn)題轉(zhuǎn)換是將多標(biāo)簽分類轉(zhuǎn)換成多個(gè)單標(biāo)簽分類,再利用已有的單標(biāo)簽分類方法進(jìn)行處理.代表性算法有二元關(guān)聯(lián)(binary relevance,BR)法[4]、分類器鏈(classifier chain,CC)算法[8]、RAkEL(RAndom k-LabELsets)算法[9]等.算法改造是指通過(guò)改造單標(biāo)簽學(xué)習(xí)算法,使其能夠直接用于多標(biāo)簽學(xué)習(xí)問(wèn)題.代表性算法有多標(biāo)簽k 近鄰(multi-label k-nearest neighbor,ML-kNN)算法[10]、排序支持向量機(jī)(ranking support vector machine,Rank-SVM)算法[11]、反向傳播多標(biāo)簽學(xué)習(xí)(back-propagation multi-label learning,BP-MLL)法[12]等.

多標(biāo)簽流形學(xué)習(xí)(multi-label manifold learning,ML2)[13]是一種特殊的算法改造方法,先利用局部線性嵌入(local linear embedding,LLE)流形學(xué)習(xí)思想對(duì)類別標(biāo)簽的重要性進(jìn)行量化,將邏輯型類別標(biāo)簽映射為數(shù)值型類別標(biāo)簽,再采用多輸出支持向量回歸進(jìn)行分類.數(shù)值型標(biāo)簽可以指示同一樣本不同標(biāo)簽的重要性程度,還能指示同一標(biāo)簽對(duì)不同樣本的重要性程度.因此,數(shù)值型標(biāo)簽相比于邏輯標(biāo)簽攜帶了更多的語(yǔ)義信息,能更好地展現(xiàn)標(biāo)簽相關(guān)性.基于特征引導(dǎo)的標(biāo)簽信息富化(multi-label learning with feature-induced labeling information enrichment,MLFE)方法[14]思路與ML2類似,但是借助L1 正則化和交替方向乘子算法(alternating direction method of multiplier,ADMM)將邏輯型標(biāo)簽轉(zhuǎn)換為數(shù)值型標(biāo)簽.Liu等[15-16]利用矩陣完備化(matrix completion)思想進(jìn)行多標(biāo)簽學(xué)習(xí),并通過(guò)圖Laplacian構(gòu)建的數(shù)據(jù)局部流形對(duì)目標(biāo)函數(shù)進(jìn)行正則化,提出基于圖Laplacian 的矩陣完備化(matrix completion with graph Laplacian,MCLA)方法以及基于ADMM 優(yōu)化的圖Laplacian 矩陣完備化方法(LA-ADMM).Zhu 等[17]利用圖Laplacian 構(gòu)建標(biāo)簽的全局和局部流形,提出基于全局和局部標(biāo)簽相關(guān)性的多標(biāo)簽學(xué)習(xí)(multi-label learning with global and local label correlation,GLOCAL)方法.此外,流形學(xué)習(xí)也被用于多標(biāo)簽特征選擇.文獻(xiàn)[18]提出利用特征流形學(xué)習(xí)和稀疏正則化的多標(biāo)簽特征選擇方法,通過(guò)流形和L21 范數(shù)正則化獲得特征重要度系數(shù)矩陣.文獻(xiàn)[19]提出一種基于流形學(xué)習(xí)的約束Laplacian 分值多標(biāo)簽特征選擇方法,首先借鑒ML2方法將邏輯型標(biāo)簽轉(zhuǎn)換成數(shù)值型標(biāo)簽,再利用數(shù)值標(biāo)簽之間的相關(guān)性對(duì)Laplacian 分值表達(dá)式進(jìn)行修正.但是,這些多標(biāo)簽分類和特征選擇方法沒(méi)有考慮不同特征對(duì)不同類別標(biāo)簽的鑒別能力.事實(shí)上,不同類別標(biāo)簽往往具有獨(dú)特的屬性特征,這些特征與該標(biāo)簽關(guān)聯(lián)性最強(qiáng)、最具有判別能力,被稱為類屬特征(label-specific features).與一般特征選擇方法相比,類屬特征構(gòu)成的子集是隨著類別的不同而變化的.文獻(xiàn)[20]提出類屬特征多標(biāo)簽學(xué)習(xí)(multi-label learning with label specific features,LIFT)方法,利用類屬特征來(lái)表示樣本并預(yù)測(cè)類別標(biāo)簽;通過(guò)在正負(fù)訓(xùn)練樣本上分別進(jìn)行聚類,利用聚類分析的結(jié)果獲得每個(gè)標(biāo)簽的類屬特征并進(jìn)行分類.但這種方法只考慮了特征空間的轉(zhuǎn)換,并沒(méi)有考慮標(biāo)簽之間的關(guān)聯(lián)性.文獻(xiàn)[21]指出任何兩個(gè)強(qiáng)關(guān)聯(lián)的標(biāo)簽比弱關(guān)聯(lián)的標(biāo)簽共享更多的類別屬性,即所對(duì)應(yīng)數(shù)據(jù)的特征相似度更大,并在此基礎(chǔ)上提出一種學(xué)習(xí)類屬特征(learning label specific features,LLSF)方法.

受上述研究的啟發(fā),本工作基于LLSF 和ML2,提出一種基于類屬特征的多標(biāo)簽流形學(xué)習(xí)分類(label specific feature based multi-label manifold learning,LSF-ML2)方法.首先,計(jì)算樣本的類別標(biāo)簽相關(guān)性,并用于優(yōu)化類屬特征重要度矩陣,確定不同類別標(biāo)簽的類屬特征子集;再基于子集的特征流形構(gòu)建標(biāo)簽流形,使標(biāo)簽從邏輯型變?yōu)閿?shù)值型,從而更有效地體現(xiàn)標(biāo)簽關(guān)聯(lián)性;最后,通過(guò)多輸出支持向量回歸實(shí)現(xiàn)分類.

1 LSF-ML2 算法

本工作所提算法LSF-ML2主要包括如下步驟:(1)計(jì)算特征重要度矩陣;(2)根據(jù)特征重要度矩陣對(duì)原始數(shù)據(jù)線性加權(quán),獲得新數(shù)據(jù)集;(3)基于流形學(xué)習(xí)思想將邏輯型標(biāo)簽轉(zhuǎn)換為數(shù)值型標(biāo)簽,并采用多輸出回歸模型進(jìn)行分類.

給定訓(xùn)練數(shù)據(jù)集為XL=[x1,x2,···,xn]T∈Rn×d,相應(yīng)的邏輯型類別標(biāo)簽集為YL=[y1,y2,···,yn]T∈Rn×q.樣本xi∈Rd對(duì)應(yīng)的邏輯標(biāo)簽為yi∈{+1,?1}q,+1 表示樣本和標(biāo)簽相關(guān),?1 表示樣本和標(biāo)簽無(wú)關(guān).

定義 V=[v1,v2,···,vq] ∈Rd×q為類屬特征重要度矩陣,若第i 個(gè)特征是第j 個(gè)標(biāo)簽的類屬特征,則vij為非零實(shí)數(shù)值;反之,vij=0.矩陣V 反映了數(shù)據(jù)中每個(gè)特征對(duì)不同標(biāo)簽的重要程度,同時(shí)也反映了不同標(biāo)簽之間的關(guān)聯(lián)性.對(duì)于第i 個(gè)類別標(biāo)簽,相應(yīng)的vi=[vi1,vi2,···,vid]T可通過(guò)線性回歸模型求解,即

在多標(biāo)簽學(xué)習(xí)中,不同的類別標(biāo)簽之間往往存在一定的相關(guān)性.如果兩類標(biāo)簽的關(guān)聯(lián)性越強(qiáng),所對(duì)應(yīng)數(shù)據(jù)的類屬特征相似度越大.相反,如果兩類標(biāo)簽的關(guān)聯(lián)性較弱,所對(duì)應(yīng)數(shù)據(jù)的類屬特征相似度也較小.標(biāo)簽的關(guān)聯(lián)性由標(biāo)簽矢量的相關(guān)系數(shù)確定,對(duì)于標(biāo)簽yi與yj,有

式中:Cov(yi,yj)為yi與yj的協(xié)方差;D(yi)和D(yj)分別為yi,yj的方差.在引入成對(duì)標(biāo)簽相關(guān)性Cij后,式(1)進(jìn)一步寫(xiě)為

式中:Q ∈Rq×q,有Qij=1 ?Cij;Tr(·)是矩陣的跡;∥·∥1和∥·∥F分別為1-范數(shù)和F-范數(shù);權(quán)系數(shù)α,β ≥0.采用加速近端梯度(accelerated proximal gradient)方法求解.定義

具體步驟[15]如下.

(1) 初始化:令b0,b1←1,V0,V1←

(2) 迭代優(yōu)化至收斂.

式中:t 為迭代次數(shù);bt為線性聚合系數(shù);Rt為基于第t 次和t ?1 次迭代結(jié)果的聚合前向矩陣;?f(Rt)為f(Rt)的梯度;Lf為利普希茨系數(shù).由此,可獲得矩陣V.在此基礎(chǔ)上,確定新數(shù)據(jù)集S=[s1,s2,···,sn]T∈Rn×q為

式中:S是由類屬特征對(duì)數(shù)據(jù)集XL的原特征線性加權(quán)產(chǎn)生的新數(shù)據(jù)集.

由于邏輯型標(biāo)簽無(wú)法反映數(shù)據(jù)不同類別標(biāo)簽間的重要度差異,因此通過(guò)流形學(xué)習(xí),將邏輯標(biāo)簽轉(zhuǎn)化為實(shí)數(shù)值,體現(xiàn)不同類別標(biāo)簽的相對(duì)重要性[13].根據(jù)平滑性假設(shè),當(dāng)兩個(gè)樣本相距很近時(shí),其類別標(biāo)簽相似,即相鄰的點(diǎn)很可能屬于同一類別;相反,當(dāng)兩個(gè)樣本相距較遠(yuǎn)時(shí),其類別標(biāo)簽不同的可能性較大.也就是說(shuō),當(dāng)兩個(gè)樣本相鄰時(shí),它們所屬的類別矢量在標(biāo)簽空間的距離較近;當(dāng)兩個(gè)樣本相距較遠(yuǎn)時(shí),它們所屬的類別矢量在標(biāo)簽空間的距離也較遠(yuǎn).ML2利用LLE 思想,將特征空間的局部拓?fù)浣Y(jié)構(gòu)映射到類別標(biāo)簽的數(shù)值空間.借鑒該方法可獲取類屬特征子集的流形結(jié)構(gòu),若數(shù)據(jù)在局部范圍內(nèi)具有線性關(guān)系,樣本si可以表示為其鄰域樣本點(diǎn)的線性組合.令表示點(diǎn)間的連接權(quán)重,可通過(guò)最小化下式獲得該權(quán)重矩陣,

若sj不是si的K 近鄰中的點(diǎn),有wij=0.式(6)求解可轉(zhuǎn)化為標(biāo)準(zhǔn)最小二乘規(guī)劃問(wèn)題.W 確定后,可在類別標(biāo)簽空間中建立局部區(qū)域內(nèi)的線性關(guān)系.由于W 不變,使得類屬特征空間的樣本拓?fù)潢P(guān)系在類別標(biāo)簽的數(shù)值空間中得以保持.類別標(biāo)簽的流形結(jié)構(gòu)可表示為

式中:μi∈Rq為yi對(duì)應(yīng)的數(shù)值標(biāo)簽.同時(shí)添加如下約束使得數(shù)值標(biāo)簽?zāi)芡ㄟ^(guò)符號(hào)表征其是否與樣本關(guān)聯(lián),

式中:λ >0.在給定W 和式(8)約束的前提下對(duì)式(7)進(jìn)行最小化,可通過(guò)有約束的二次規(guī)劃方法完成,獲得實(shí)值標(biāo)簽.

最后,采用多輸出回歸的方法實(shí)現(xiàn)多標(biāo)簽分類.表1 對(duì)LSF-ML2進(jìn)行了總結(jié).

表1 LSF-ML2 算法Table 1 LSF-ML2 algorithm

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

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

為驗(yàn)證本工作所提算法的性能,分別在多標(biāo)簽數(shù)據(jù)集medical,corel5k,flags,20NG 上進(jìn)行實(shí)驗(yàn),表2 給出了所用數(shù)據(jù)集的統(tǒng)計(jì)信息描述.

表2 實(shí)驗(yàn)所用數(shù)據(jù)集Table 2 Experimental data sets

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

實(shí)驗(yàn)采用微平均(Micro F1)、基于樣本的F1-measure、基于樣本的準(zhǔn)確度、基于標(biāo)簽的F1-measure、基于標(biāo)簽的準(zhǔn)確度這5 個(gè)性能評(píng)價(jià)指標(biāo)[8,21-23].上述評(píng)價(jià)指標(biāo)分別從樣本和標(biāo)簽的角度衡量算法性能.各評(píng)價(jià)指標(biāo)的定義如下.

(1) 微平均(Micro F1):從單標(biāo)簽分類評(píng)價(jià)指標(biāo)擴(kuò)展而來(lái),將每個(gè)標(biāo)簽元素都當(dāng)成一個(gè)獨(dú)立的元素,不考慮標(biāo)簽之間的區(qū)別,該值越大表示分類性能越好.定義

式中:yij和分別是第i 個(gè)樣本的第j 個(gè)標(biāo)簽的真實(shí)值和預(yù)測(cè)值.

(2) 基于樣本的F1-measure:對(duì)每個(gè)樣本的精確度(precision)和召回率(recall)的調(diào)和平均,常用來(lái)評(píng)價(jià)多標(biāo)簽分類結(jié)果的好壞,該值越大表示分類效果越好.

(3)基于樣本的準(zhǔn)確度:以樣本為基礎(chǔ),估計(jì)正確預(yù)測(cè)的標(biāo)簽占預(yù)測(cè)標(biāo)簽與真實(shí)標(biāo)簽集合的比例,該值越大表示分類效果越好.

式中:yi和分別代表第i 個(gè)樣本的真實(shí)標(biāo)簽矢量和預(yù)測(cè)標(biāo)簽矢量.

(4)基于標(biāo)簽的F1-measure:對(duì)每個(gè)標(biāo)簽的精確度和召回率的調(diào)和平均,該值越大表示分類效果越好.

(5)基于標(biāo)簽的準(zhǔn)確度:以每個(gè)類別標(biāo)簽為基礎(chǔ),估計(jì)正確預(yù)測(cè)的標(biāo)簽占預(yù)測(cè)標(biāo)簽與真實(shí)標(biāo)簽集合的比例,該值越大表示分類效果越好.

式中:zi和分別代表第i 個(gè)標(biāo)簽的真實(shí)標(biāo)簽矢量和預(yù)測(cè)標(biāo)簽矢量.

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

為了驗(yàn)證本工作所提算法的有效性,將所提算法LSF-ML2與LLSF[21],ML2[13],MLkNN[10],MLFE[14]進(jìn)行了比較,其中LLSF,ML2和MLFE 的參數(shù)設(shè)置與原文獻(xiàn)相同.LLSF中α,β 和γ 的值分別設(shè)為0.1,0.1 和0.01,迭代100 次;ML2中λ,c1和c2分別設(shè)為1,1 和10;MLFE 中λ,c1和c2分別設(shè)為1,1 和2.c1和c2為多輸出支持向量回歸的懲罰因子.本工作所提算法LSF-ML2中的α,β,γ 以及迭代次數(shù)與LLSF 設(shè)置相同,λ,c1,c2與ML2設(shè)置相同,K 設(shè)為類別數(shù)加1.ML-kNN 的近鄰設(shè)置為8.實(shí)驗(yàn)采用5 倍交叉驗(yàn)證,即將數(shù)據(jù)集隨機(jī)分成5 等份,運(yùn)行5 次,每次以其中1 份作為測(cè)試集,剩下4 份作為訓(xùn)練集.將5 次運(yùn)行的測(cè)試集性能指標(biāo)進(jìn)行平均,作為最終評(píng)價(jià)結(jié)果.

表3 給出了不同算法的性能指標(biāo),表中實(shí)驗(yàn)結(jié)果均采用均值±方差(mean±std)的形式表示,并將性能最好的結(jié)果用黑體標(biāo)出.為衡量算法在N1個(gè)數(shù)據(jù)集N2個(gè)指標(biāo)上的性能,定義算法在第j 個(gè)指標(biāo)下的平均排序值為

表3 不同分類算法的性能比較(mean±std)Table 3 Performance comparison of different classification methods (mean±std)

表4 不同分類算法在所有數(shù)據(jù)集上的平均排序值Table 4 Average rankings of different classification on all data sets

可以看到,3 個(gè)基于流形學(xué)習(xí)的算法ML2,GLOCAL 和LSF-ML2在總體性能上具有優(yōu)勢(shì),其中GLOCAL 在數(shù)據(jù)集medical 的5 個(gè)指標(biāo)和flags 的3 個(gè)指標(biāo)上性能突出;但在數(shù)據(jù)集corel5k 和20NG 上性能基本處于末位,表現(xiàn)不佳.本工作所提算法LSF-ML2基于類屬特征進(jìn)行流形學(xué)習(xí),在全部數(shù)據(jù)集的實(shí)驗(yàn)中性能均較為穩(wěn)定地居于前3.在其余算法中,MLFE 也將邏輯標(biāo)簽實(shí)值化并采用多輸出支持向量回歸進(jìn)行分類,性能稍遜于ML2.LLSF 基于類屬特征進(jìn)行分類,在數(shù)據(jù)集medical 上性能較好,但總體上遜于MLFE.以上5 種算法都考慮了類別標(biāo)簽的相關(guān)性,因此性能均優(yōu)于忽略此相關(guān)性的ML-kNN.

為評(píng)估算法效率,表5 給出了各分類算法在不同數(shù)據(jù)集上花費(fèi)的運(yùn)算時(shí)間.該時(shí)間為5 次運(yùn)行的平均值.實(shí)驗(yàn)所用計(jì)算機(jī)配置為Intel Core i5-8250U,8 G 內(nèi)存,3.4 G 主頻.可以看出,隨著數(shù)據(jù)規(guī)模的增長(zhǎng),各算法的運(yùn)算時(shí)間都有相應(yīng)增加.ML-kNN 和LLSF 速度較快,其次是GLOCAL.雖然GLOCAL 采用流形學(xué)習(xí),但算法是針對(duì)標(biāo)簽構(gòu)建流形空間,因此運(yùn)算量低于需要計(jì)算特征空間流形結(jié)構(gòu)的LSF-ML2和ML2.同時(shí),由于LSF-ML2基于類屬特征進(jìn)行分類,因此相比ML2降低了運(yùn)算量.但對(duì)于規(guī)模較大的數(shù)據(jù)集,LSF-ML2無(wú)法滿足實(shí)時(shí)性.MLFE 雖然沒(méi)有計(jì)算流形結(jié)構(gòu),但在標(biāo)簽實(shí)值化過(guò)程中涉及L1 正則化目標(biāo)函數(shù)的優(yōu)化,較為費(fèi)時(shí),特別是針對(duì)較大數(shù)據(jù)集時(shí),所需時(shí)間急劇增加.

表5 不同分類算法的運(yùn)算時(shí)間Table 5 Running time of different classification methods s

3 結(jié)束語(yǔ)

本工作提出一種基于類屬特征的多標(biāo)簽流形學(xué)習(xí)分類方法LSF-ML2.基于類屬特征的思想,從數(shù)據(jù)的特征全集中挑選出類屬特征子集;基于類屬特征子集的特征流形構(gòu)建標(biāo)簽空間流形,將標(biāo)簽從邏輯型變?yōu)閿?shù)值型,最后通過(guò)多輸出支持向量回歸實(shí)現(xiàn)分類.LSF-ML2利用標(biāo)簽相關(guān)性,將數(shù)據(jù)的類屬特征空間和標(biāo)簽空間有機(jī)結(jié)合起來(lái).多標(biāo)簽數(shù)據(jù)分類實(shí)驗(yàn)結(jié)果表明,LSF-ML2性能優(yōu)于多種多標(biāo)簽分類方法.