基于流形學(xué)習與L2，1范數(shù)的無監(jiān)督多標簽特征選擇

馬盈倉,張 要,2，張 寧，朱恒東

(1.西安工程大學(xué) 理學(xué)院,陜西 西安 710600;2.山東華宇工學(xué)院 基礎(chǔ)教學(xué)部，山東 德州 253034)

0 引 言

嵌入式多標簽特征選擇方法是目前性能良好并廣泛使用的一類特征選擇方法。多標簽特征選擇又稱為多標簽特征子集選擇，是指適用于多標簽數(shù)據(jù)集的特征選擇算法，是從原始特征中選擇出一些最有效的特征以降低數(shù)據(jù)集維度的過程。在學(xué)習算法中，多標簽特征選擇不僅能夠縮短訓(xùn)練時間、降低成本要求，還能減少過擬合、避免維數(shù)災(zāi)難等[1-3]，是模式識別中關(guān)鍵的數(shù)據(jù)預(yù)處理步驟。與傳統(tǒng)的特征選擇相比，多標簽特征選擇往往更為復(fù)雜，既要考慮數(shù)據(jù)與數(shù)據(jù)間的關(guān)系、數(shù)據(jù)與標簽間的關(guān)系，還要考慮標簽與標簽間的關(guān)系?，F(xiàn)有的特征選擇方法大致可分為過濾式[4-6]、封裝式[7-8]、嵌入式[9-11]等3類，其中嵌入式是過濾式與封裝式的折中體現(xiàn)?；跇撕炐畔⒌挠袩o，也可將特征選擇方法分為有監(jiān)督[12-13]、半監(jiān)督[14-15]、無監(jiān)督[16-17]等。然而，現(xiàn)有的嵌入式多標簽特征選擇方法，大多是基于最小二乘、邏輯回歸、信息熵等，且隸屬于有監(jiān)督或半監(jiān)督多標簽特征選擇方法。

文獻[18]將傳統(tǒng)的邏輯模型擴展到多標簽分類中，使其能夠適用于多標簽數(shù)據(jù)集，同時也能進行多標簽特征選擇；文獻[19]利用標簽ω拖動思想，提出了一種包含標簽信息的最小二乘多標簽特征選擇方法；文獻[20]針對標簽不平衡分布問題，提出了一種邊緣標記弱化的多標簽特征選擇算法；文獻[21]提出了一種新的擴展自適應(yīng)最小絕對收縮選擇算子特征選擇方法(EALasso)。文獻[22]提出了一種具有多重正則化的多標簽特征選擇方法(MDFS)。該方法不僅考慮了特征與標簽的局部相關(guān)性，還通過L2,1范數(shù)約束目標函數(shù)。文獻[23]將矩陣分解問題、非負約束問題和L2,1范數(shù)最小化問題相結(jié)合，構(gòu)成了基于非負稀疏表示的多標簽特征選擇方法；文獻[24]利用L2,1范數(shù)約束相關(guān)熵與流形學(xué)習，構(gòu)造了一種基于相關(guān)熵和流形學(xué)習的多標簽特征選擇模型；文獻[25]提出了一種基于光譜分析的半監(jiān)督特征選擇算法。然而，這些經(jīng)典算法僅針對帶標簽數(shù)據(jù)集設(shè)計。文獻[26]為了解決多標簽問題，將多標簽學(xué)習分解為多個獨立的單標簽問題，沒有考慮到不同標簽之間的相關(guān)性；文獻[27]通過L1范數(shù)與標簽流形學(xué)習共同約束邏輯回歸的系數(shù)矩陣，解決特征選擇問題；文獻[28]提出了一種適用于大規(guī)模數(shù)據(jù)集的凸半監(jiān)督多標簽特征選擇算法。

上述多標簽特征選算法都是有監(jiān)督或半監(jiān)督的，或多或少都需要用到數(shù)據(jù)的標簽，從而忽略了大量的廉價的無標簽數(shù)據(jù)。此外，還有一些無監(jiān)督特征選擇算法。文獻[29]提出了一種基于自編碼器的無監(jiān)督特征選擇模型。該模型考慮了非負性、正交性和稀疏性，充分利用了其內(nèi)部特征。文獻[30]提出了無監(jiān)督稀疏圖嵌入特征選擇方法；文獻[31]利用酉不變性的深度隨機游走學(xué)習鑒別特征，提出了一種有效的數(shù)據(jù)表示方法來解決大規(guī)模的特征表示問題。但這些無監(jiān)督模型大多適用于單標簽數(shù)據(jù)。針對嵌入式無監(jiān)督多標簽特征選擇的挑戰(zhàn)，本文將L2,1范數(shù)回歸與流形學(xué)習結(jié)合，構(gòu)成了新的無監(jiān)督多標簽特征選擇模型，設(shè)計了一種高效的收斂性算法(UMLFS)，并通過在多個經(jīng)典數(shù)據(jù)集上的對比實驗證明其可行性。

1 模型建立

1.1 L2,1范數(shù)回歸模型

給定多標簽數(shù)據(jù)集X，其特征矩陣記為X=[x1,x2,…,xn]T，X∈Rn×d，根據(jù)問題特征作如下假設(shè)：擬合偽標簽為F∈Rn×m(未知)，且在L2,1范數(shù)距離上有F=XW，其中W∈Rd×m是特征權(quán)重矩陣，能夠體現(xiàn)特征的重要性，并且L2,1范數(shù)可以有效地約束權(quán)重矩陣W的行間稀疏、行內(nèi)穩(wěn)定，更有利于特征選擇。從而有

(1)

式中：β為懲罰因子；R(W)為懲罰函數(shù)，表示對W的相應(yīng)約束懲罰。

1.2 特征流形正則化

隨著學(xué)者們的不斷研究、擴展，將流形學(xué)習推廣到維數(shù)簡約[32]、協(xié)同聚類算法[33]、特征選擇算法等各領(lǐng)域。

對與UMLFS算法，由于是無監(jiān)督的，無法利用標簽信息，所以就更應(yīng)該使用特征流形約束權(quán)重矩陣的學(xué)習，同時數(shù)據(jù)特征的拉普拉斯圖矩陣，也能提供一個很好的參數(shù)調(diào)節(jié)過程，從而避免了所有特征的約束參數(shù)都一樣的可能。根據(jù)問題特征再假設(shè)：

令X=[f1,f2,…,fd]，W=[W1,W2,…,Wd]T,其中fi是數(shù)據(jù)矩陣的第i列，表示數(shù)據(jù)的第i個特征向量，Wi是權(quán)重矩陣的第i行，表示第i個特征向量所對應(yīng)的權(quán)重。由于權(quán)重矩陣W可以體現(xiàn)特征的權(quán)重，所以，若fi與fj距離相近，那么Wi與Wj的距離也應(yīng)該相近。從而可以通過特征間相似性指導(dǎo)權(quán)重矩陣的學(xué)習，構(gòu)建特征流形學(xué)習模型，其表達式如下：

tr(WTLW)

(2)

式中：L∈Rd×d為特征相似矩陣；Lij為L的第i行、第j列元素，表示特征fi與fj的相似度。文中是通過帶平方約束的Pearson相關(guān)系數(shù)計算L的，其公式為

(3)

1.3 偽標簽約束

在多標簽學(xué)習中，學(xué)者們普遍認為標簽矩陣是數(shù)據(jù)矩陣的一種映射，所以兩者的結(jié)構(gòu)極其相似。而在本文中，偽標簽是真實標簽的一種替換，理論上，其應(yīng)該具有真實標簽的所有屬性。令偽標簽矩陣F=[F1,F2,…,Fn]T，真實標簽矩陣Y=[Y1,Y2,…,Yn]T，Y∈Rn×m，根據(jù)問題再假設(shè)：

1) 若樣本xi與xj的相似度較高，那么真實標簽Yi與Yj的相似度也應(yīng)該較高;

2) 偽標簽矩陣F基本與真實標簽矩陣Y等價。

由于在本研究中只存在數(shù)據(jù)信息，所以可以用數(shù)據(jù)樣本的相似矩陣約束偽標簽矩陣的學(xué)習，從而提高偽標簽矩陣的精確度。其公式為

tr(FTΛF)

(4)

式中：Λ∈Rn×n為數(shù)據(jù)樣本的相似矩陣；Λij為Λ的第i行、第j列元素，表示樣本xi與xj之間的相似度。與特征相似矩陣L類似，樣本相似矩陣Λ同樣是通過帶平方約束的Pearson相關(guān)系數(shù)計算的，即

(5)

(6)

式中：B(*)為關(guān)于變量*的目標函數(shù)；α與β是正則項參數(shù)。

2 問題求解

2.1 問題優(yōu)化

由于L2,1范數(shù)的非光滑性，根據(jù)文獻[34]，當(XW-F)i≠0時，其中i=1,2,…,n?！琗W-F‖2,1關(guān)于W或F的導(dǎo)函數(shù)也可以看作是tr((XW-F)TH(XW-F))關(guān)于W或F的導(dǎo)函數(shù)。其中H∈Rn×n是對角矩陣，H的第i個對角元素為

(7)

使用L2,1范數(shù)的優(yōu)化問題求B(W,F)的近似解：

(8)

對于式(8)，可以先給定W、H，計算出F；再利用F、H，更新W；最后通過W、F，更新H。

2.2 給定H、W求解F

(9)

求出B(F)關(guān)于F的導(dǎo)函數(shù)，并使導(dǎo)函數(shù)為0，即

(10)

從而可以計算出F，即

F=(H+βΛ)-1HXW

(11)

2.3 給定H、F求解W

(12)

求出B(W)關(guān)于W的導(dǎo)函數(shù)，并使導(dǎo)函數(shù)為0，即

(13)

從而可以計算出W，即

W=(XTHX+αL)-1XTHF

(14)

通過以上問題優(yōu)化與求解，基于流形學(xué)習與L2,1范數(shù)的無監(jiān)督多標簽特征選擇(unsupervised multi-label feature selection based on manifold learning andL2,1norm， UMLFS)算法如下：

算法1：UMLFS算法

輸入：數(shù)據(jù)矩陣X∈Rn×d，正則化參數(shù)α與β，選取特征個數(shù)k，迭代次數(shù)t。

1) 根據(jù)式(3)計算特征相似矩陣L;

2) 根據(jù)式(5)計算樣本相似矩陣Λ;

3) 令t=0，初始化對角矩陣Ht為單位矩陣;

4) 初系數(shù)矩陣Wt為元素全為1的矩陣。

重復(fù)：

根據(jù)式(11)計算Ft,

t=t+1,

根據(jù)式(14)更新Wt,

根據(jù)式(7)更新Ht。

直到收斂為止。

5) 計算并排序‖Wi‖2(i=1,2,…,d)，找出前k個最大的賦給I。

輸出：特征選擇結(jié)果I。

算法1主要更新W與F，每次迭代的時間復(fù)雜度是O(2d2n)，一共迭代了t次，所以算法1的總時間復(fù)雜度為O(2td2n)。t的值一般較小，所以對算法1的時間復(fù)雜度影響不大。然而，算法1的時間復(fù)雜度受數(shù)據(jù)的維數(shù)d和數(shù)據(jù)集樣本個數(shù)n的影響較大。

2.4 收斂性分析

證明算法1的收斂性。令Q=XW-F，則

(15)

由算法1的t次迭代可知，當固定W時，有

B(W,Ft+1)≤B(W,Ft)

(16)

當固定F時，有

B(Wt+1,F)≤B(Wt,F)

(17)

從而有

B(Qt+1)≤B(Qt)

(18)

由此，可以推出

(19)

所以可以轉(zhuǎn)換為

(20)

其中Qi表示Q的第i行向量。式(20)可以進一步轉(zhuǎn)化為

(21)

(22)

對式(22)求和，可得到

(23)

從而推出

(24)

綜上所述，算法1的收斂性得到證明。

圖1為UMLFS算法在Yeast和Bibtex實驗數(shù)據(jù)集上的收斂結(jié)果，其中參數(shù)設(shè)置為α=1，β=1。

(a) Yeast

(b) Bibtex圖 1 UMLFS算法對Yeast和Bibtex數(shù)據(jù)集的收斂性Fig.1 Convergence results of UMLFS algorithm for Yeast and Bibtex data set

3 實 驗

選取5個經(jīng)典數(shù)據(jù)集，與4個經(jīng)典的有監(jiān)督多標簽特征選擇算法SCLS[35]、MDMR[36]、PMU[37]、FIMF[38]共同進行實驗，并選擇MLKNN[39]作為多標簽分類算法的代表進行評價。

3.1 數(shù)據(jù)集與參數(shù)設(shè)置

實驗中采用的5個經(jīng)典數(shù)據(jù)集，來自4個不同的領(lǐng)域，包括圖像數(shù)據(jù)集Image、Scene，音樂數(shù)據(jù)集Emotion，文本數(shù)據(jù)集Bibtex及生物數(shù)據(jù)集Yeast。這些數(shù)據(jù)均來自木蘭圖書館(http://mulan.sourceforge.net/datasets.html)。各數(shù)據(jù)集的具體參數(shù)如表1所示。

表 1 數(shù)據(jù)集信息Tab.1 Data set information

實驗環(huán)境為：Microsoft Windows7系統(tǒng)處理器為Intel(R) Core(TM) i5-4210U CUP @ 1.70 GHz 2.40 GHz，內(nèi)存4.00 GB；采用Matlab R2016a編程軟件。

將MLKNN算法的平滑參數(shù)設(shè)置為S=1，近鄰參數(shù)設(shè)置為K=10。應(yīng)用等寬區(qū)間對數(shù)據(jù)集進行離散化處理[40]，使其適用于MDMR、FIMF等算法，并將FIMF算法的參數(shù)設(shè)置為Q=10,b=2。以上是算法的默認參數(shù)。利用“網(wǎng)格搜索”策略，調(diào)整所有的多標簽特征選擇算法的正則化參數(shù)，設(shè)置為(0.001，0.01，0.1，1，10，100，1 000)，將選擇的特征個數(shù)設(shè)置為(10，15，20，25，30，35，40，45，50)。

由于對比算法都是有監(jiān)督的多標簽特征選擇算法，所以實驗本身對UMLFS算法是嚴格的。

3.2 評價指標

1) 漢明損失LH：分錯標簽的占比，值越小越好。

(25)

式中：h(ci)Δyi為h(ci)和yi的對稱差，LH(C)∈[0,1]。

2) 排序損失LR：反序標簽對的占比，值越小越好。

(26)

3) 1-錯誤率RE：在“真實標簽”中不存在“預(yù)測到的最相關(guān)的標簽”的樣本占比，值越小越好。

(27)

4) 覆蓋率CV：要想覆蓋真實的標簽相關(guān)集，“排序后的標簽”平均需要移動多少步，值越小越好。

(28)

式中：CV(C)∈[0,m-1]。

5) 平均精度PA：相關(guān)性高于特定標簽的標簽，在排名中的占比，值越大越好。

(29)

3.3 實驗結(jié)果與分析

在5個經(jīng)典數(shù)據(jù)集上，將UMLFS算法與4個對比算法進行了對比實驗。利用漢明損失、排序損失、1-錯誤率、覆蓋率、平均精度等5個評價指標評價各算法的性能；同時，以最優(yōu)得1分、次優(yōu)得0.5分、其他為0分(共7.5分)計分，根據(jù)各算法在對應(yīng)指標上的性能分配，給出了各算法的得分情況。實驗結(jié)果如表2～6所示，表中分別用粗體和下劃線標出最優(yōu)結(jié)果和次優(yōu)結(jié)果，并且表中展示的都是對應(yīng)算法在最優(yōu)參數(shù)下的最優(yōu)結(jié)果。

表 2 各數(shù)據(jù)集不同算法的漢明損失對比Tab.2 Hamming loss comparison of different algorithms under each data set

表 3 各數(shù)據(jù)集不同算法的排序損失對比Tab.3 Ranking loss comparison of different algorithms under each data set

表 4 各數(shù)據(jù)集不同算法的1-錯誤率對比Tab.4 One-error comparison of different algorithms under each data set

表 5 各數(shù)據(jù)集不同算法的覆蓋率對比Tab.5 Coverage comparison of different algorithms under each data set

表 6 各數(shù)據(jù)集不同算法的平均精度對比Tab.6 Average precision comparison of different algorithms under each data set

從表2～6可以看出：UMLFS算法雖然在Yeast數(shù)據(jù)集上排序損失指標的最優(yōu)結(jié)果略不如MDMR算法和PMU算法，在1-錯誤率指標的最優(yōu)結(jié)果僅次于SCLS算法，在平均精度指標的最優(yōu)結(jié)果僅次于MDMR算法，但在其他各指標的最優(yōu)結(jié)果仍優(yōu)于其他對比算法，并且在Emotion、Scene、Bibtex、Image數(shù)據(jù)集上的各指標的最優(yōu)結(jié)果都明顯優(yōu)于所有對比算法。

(a) Yeast (b) Bibtex (c) Image圖 3 3種數(shù)據(jù)集不同算法間的排序損失比較Fig.3 Ranking loss comparison between different algorithms on three data set

(a) Yeast (b) Bibtex (c) Image圖 4 3種數(shù)據(jù)集不同算法間的1-錯誤率比較Fig.4 One-error comparison between different algorithms on three data set

(a) Yeast (b) Bibtex (c) Image圖 5 3種數(shù)據(jù)集不同算法間的覆蓋率比較Fig.5 Coverage comparison between different algorithms on three data set

(a) Yeast (b) Bibtex (c) Image圖 6 3種數(shù)據(jù)集不同算法間的平均精度比較Fig.6 Average precision comparison between different algorithms on three data set

可見，UMLFS算法除在Yeast數(shù)據(jù)集上的性能略不理想外，在其他理想數(shù)據(jù)集上各指標的性能都是最優(yōu)的。從得分情況(表2～6)可以看出，UMLFS算法的分值最低為4，最高為5，始終優(yōu)于對比算法。所以，UMLFS算法在解決無監(jiān)督多標簽特征選擇問題上是有效的。

為了能更直觀地對比各算法的漢明損失、排序損失、1-錯誤率、覆蓋率、平均精度等指標的性能，以及選擇的特征個數(shù)對算法的影響，圖2～6以選擇的特征個數(shù)為橫坐標，以各指標的結(jié)果值為縱坐標，展示了數(shù)據(jù)集Yeast、Bibtex和Image的實驗結(jié)果。

從圖2～6可以看出，UMLFS算法在Bibtex數(shù)據(jù)集上的漢明損失、排序損失、1-錯誤率、覆蓋率等指標明顯低于對比算法的對應(yīng)指標，而平均精度明顯高于對比算法平均精度；UMLFS算法在Image數(shù)據(jù)集上各指標相對于對比算法的結(jié)果，形成了一層包絡(luò)，較優(yōu)于對比算法。雖然表2～6中UMLFS算法在Yeast數(shù)據(jù)集上的一些指標的最優(yōu)結(jié)果不如MDMR算法和SCLS算法，但由圖2～6可以清楚地看出，UMLFS算法各指標的整體結(jié)果還是較優(yōu)的。可見，UMLFS算法整體上優(yōu)于各對比算法，說明UMLFS算法能夠更好地利用數(shù)據(jù)信息進行特征選擇，以及UMLFS算法在解決無監(jiān)督多標簽特征選擇問題上的可行性。

關(guān)于參數(shù)α、β的變化對UMLFS算法性能的影響，做了針對性的實驗。固定選擇的特征個數(shù)為50，利用“網(wǎng)格搜索”的策略，對參數(shù)α與β進行調(diào)整，其中搜索值分別設(shè)置為0.001、0.01、0.1、1、10、100、1 000。計算UMLFS算法平均精度評價指標的性能變化，結(jié)果如圖7所示。

(a) Yeast (b) Bibtex (c) Image圖 7 不同參數(shù)α、β對于UMLFS算法平均精度的影響Fig.7 Effect of different parameters α and β on average precision of UMLFS algorithm

從圖7可以看出，對于不同的數(shù)據(jù)集，參數(shù)的敏感程度不同。如在Image數(shù)據(jù)集上，參數(shù)α與β的變化對UMLFS算法的影響程度較大；而在Yeast和Bibtex數(shù)據(jù)集上，UMLFS算法對參數(shù)的變化不敏感。這可能與特征相似矩陣和樣本相似矩陣的學(xué)習方法不能適用于所有數(shù)據(jù)集有關(guān)。

圖8展示了各算法間的顯著性差異和排名。在圖8中，以排名為橫坐標，從左到右，算法的性能依次變好。同時，圖8還以平均秩圖的形式展示了Bonferroni-Dunn測試結(jié)果，并將無顯著差異(p<0.1)的算法組連接，如果平均排名達到差異的臨界值，則有顯著差異[41]。從圖8可以看出：UMLFS算法的漢明損失、平均精度等指標，雖然與SCLS算法和MDMR算法無顯著性差異，但與PMU算法和FIMF算法之間存在顯著差異；在覆蓋率指標上雖然與SCLS算法、FIMF算法和MDMR算法無顯著差異，但與PMU算法存在顯著差異。而且UMLFS算法在各指標的排名始終在最右側(cè)的第1位。因此，與對比算法相比，UMLFS算法的性能表現(xiàn)更好。

(a) 漢明損失

(b) 覆蓋率

(c) 平均精度圖 8 Bonferroni-Dunn檢驗結(jié)果的平均秩圖的形式Fig.8 The form of average rank graph of Bonferroni-Dunn test results

4 結(jié) 語

使用帶平方約束的Pearson相關(guān)系數(shù)學(xué)習特征和樣本的基層流形結(jié)構(gòu)；分別用特征流形和樣本流形約束特征權(quán)重矩陣和偽標簽矩陣；結(jié)合L2,1范數(shù)構(gòu)建了無監(jiān)督多標簽特征選擇模型(UMLFS)。該模型在多個數(shù)據(jù)集上與多個經(jīng)典的有監(jiān)督多標簽特征選擇模型進行對比實驗，結(jié)果表明UMLFS算法的有效性。學(xué)得一個精確的基層結(jié)構(gòu)，才能更好地進行特征選擇。所以，下一步將繼續(xù)研究相似矩陣的學(xué)習，并對UMLFS算法進行改進，使其能夠更好地適用于無監(jiān)督多標簽特征選擇。