基于類屬特征的多標簽流形學習分類方法

亢瀏越,黃 睿,孫廣玲

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

在傳統的機器學習框架中,一個對象只與單一類別的標簽相關聯[1].然而,在實際應用中,對象往往不是具有唯一語義的.例如,一篇新聞報道可以同時屬于“經濟”和“體育”類,一幅圖像可以同時標注為“大海”和“天空”等.此時,傳統的機器學習框架難以取得較好的分類效果.為了更好地描述數據對象,需要給每個對象賦予多個合適的類別標簽,多標簽學習也由此產生.目前,多標簽學習已被廣泛應用于文本分類[2-3]、圖像標注[4-5]、音樂情感分類[6-7]等領域.

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

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

受上述研究的啟發,本工作基于LLSF 和ML2,提出一種基于類屬特征的多標簽流形學習分類(label specific feature based multi-label manifold learning,LSF-ML2)方法.首先,計算樣本的類別標簽相關性,并用于優化類屬特征重要度矩陣,確定不同類別標簽的類屬特征子集;再基于子集的特征流形構建標簽流形,使標簽從邏輯型變為數值型,從而更有效地體現標簽關聯性;最后,通過多輸出支持向量回歸實現分類.

1 LSF-ML2 算法

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

給定訓練數據集為XL=[x1,x2,···,xn]T∈Rn×d,相應的邏輯型類別標簽集為YL=[y1,y2,···,yn]T∈Rn×q.樣本xi∈Rd對應的邏輯標簽為yi∈{+1,?1}q,+1 表示樣本和標簽相關,?1 表示樣本和標簽無關.

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

在多標簽學習中,不同的類別標簽之間往往存在一定的相關性.如果兩類標簽的關聯性越強,所對應數據的類屬特征相似度越大.相反,如果兩類標簽的關聯性較弱,所對應數據的類屬特征相似度也較小.標簽的關聯性由標簽矢量的相關系數確定,對于標簽yi與yj,有

式中:Cov(yi,yj)為yi與yj的協方差;D(yi)和D(yj)分別為yi,yj的方差.在引入成對標簽相關性Cij后,式(1)進一步寫為

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

具體步驟[15]如下.

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

(2) 迭代優化至收斂.

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

式中:S是由類屬特征對數據集XL的原特征線性加權產生的新數據集.

由于邏輯型標簽無法反映數據不同類別標簽間的重要度差異,因此通過流形學習,將邏輯標簽轉化為實數值,體現不同類別標簽的相對重要性[13].根據平滑性假設,當兩個樣本相距很近時,其類別標簽相似,即相鄰的點很可能屬于同一類別;相反,當兩個樣本相距較遠時,其類別標簽不同的可能性較大.也就是說,當兩個樣本相鄰時,它們所屬的類別矢量在標簽空間的距離較近;當兩個樣本相距較遠時,它們所屬的類別矢量在標簽空間的距離也較遠.ML2利用LLE 思想,將特征空間的局部拓撲結構映射到類別標簽的數值空間.借鑒該方法可獲取類屬特征子集的流形結構,若數據在局部范圍內具有線性關系,樣本si可以表示為其鄰域樣本點的線性組合.令表示點間的連接權重,可通過最小化下式獲得該權重矩陣,

若sj不是si的K 近鄰中的點,有wij=0.式(6)求解可轉化為標準最小二乘規劃問題.W 確定后,可在類別標簽空間中建立局部區域內的線性關系.由于W 不變,使得類屬特征空間的樣本拓撲關系在類別標簽的數值空間中得以保持.類別標簽的流形結構可表示為

式中:μi∈Rq為yi對應的數值標簽.同時添加如下約束使得數值標簽能通過符號表征其是否與樣本關聯,

式中:λ >0.在給定W 和式(8)約束的前提下對式(7)進行最小化,可通過有約束的二次規劃方法完成,獲得實值標簽.

最后,采用多輸出回歸的方法實現多標簽分類.表1 對LSF-ML2進行了總結.

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

2 實 驗

2.1 數據集

為驗證本工作所提算法的性能,分別在多標簽數據集medical,corel5k,flags,20NG 上進行實驗,表2 給出了所用數據集的統計信息描述.

表2 實驗所用數據集Table 2 Experimental data sets

2.2 評價指標

實驗采用微平均(Micro F1)、基于樣本的F1-measure、基于樣本的準確度、基于標簽的F1-measure、基于標簽的準確度這5 個性能評價指標[8,21-23].上述評價指標分別從樣本和標簽的角度衡量算法性能.各評價指標的定義如下.

(1) 微平均(Micro F1):從單標簽分類評價指標擴展而來,將每個標簽元素都當成一個獨立的元素,不考慮標簽之間的區別,該值越大表示分類性能越好.定義

式中:yij和分別是第i 個樣本的第j 個標簽的真實值和預測值.

(2) 基于樣本的F1-measure:對每個樣本的精確度(precision)和召回率(recall)的調和平均,常用來評價多標簽分類結果的好壞,該值越大表示分類效果越好.

(3)基于樣本的準確度:以樣本為基礎,估計正確預測的標簽占預測標簽與真實標簽集合的比例,該值越大表示分類效果越好.

式中:yi和分別代表第i 個樣本的真實標簽矢量和預測標簽矢量.

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

(5)基于標簽的準確度:以每個類別標簽為基礎,估計正確預測的標簽占預測標簽與真實標簽集合的比例,該值越大表示分類效果越好.

式中:zi和分別代表第i 個標簽的真實標簽矢量和預測標簽矢量.

2.3 實驗結果分析

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

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

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

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

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

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

表5 不同分類算法的運算時間Table 5 Running time of different classification methods s

3 結束語

本工作提出一種基于類屬特征的多標簽流形學習分類方法LSF-ML2.基于類屬特征的思想,從數據的特征全集中挑選出類屬特征子集;基于類屬特征子集的特征流形構建標簽空間流形,將標簽從邏輯型變為數值型,最后通過多輸出支持向量回歸實現分類.LSF-ML2利用標簽相關性,將數據的類屬特征空間和標簽空間有機結合起來.多標簽數據分類實驗結果表明,LSF-ML2性能優于多種多標簽分類方法.