基于動態圖拉普拉斯的多標簽特征選擇

李永豪，胡亮，張平，高萬夫,3

（1.吉林大學計算機科學與技術學院，吉林 長春 130012；2.吉林大學符號計算與知識工程教育部重點實驗室，吉林 長春 130012；3.吉林大學化學學院，吉林 長春 130012）

1 引言

進入大數據時代后，萬物互聯產生了海量的數據，其中高維數據導致的維度詛咒問題非常引人注意，處理這些高維數據對現有的方法來說是一個巨大的挑戰[1-2]。更進一步地，在這些高維數據中存在的多標簽數據也越來越凸顯其現實應用價值[3-4]。與早期的單標簽數據不同，多標簽數據中每個樣例都可能與多個不同的標簽有關聯[5-7]。例如，各類音樂軟件中對歌曲進行分類時，同一首歌曲可能標記不同風格的標簽。如何有效地對各類多標簽數據進行分類逐漸成為研究的熱點[6]。然而，高維多標簽數據中存在大量特征，這些特征中包含的不相關信息嚴重削弱了多標簽學習算法的分類性能[1,8]。如何找到一個緊湊的、與標簽相關的特征子集是一個棘手而緊迫的問題。特征選擇算法可以從原始數據中獲得一個最優特征子集，它不僅實現了特征降維，而且保留了原始數據的直觀意義和物理解釋[9]。因此，特征選擇技術成為圖像、視頻、文本和基因等存在大量多標簽數據的領域的熱門預處理方法[10]。一般來說，多標簽特征選擇分為過濾式模型、包裝式模型和嵌入式模型[11-13]。過濾式模型與后續學習算法無關[14]，而包裝式模型依賴于學習算法。與過濾式和包裝式模型不同，嵌入式模型將特征選擇嵌入學習算法中。本文重點研究嵌入式模型。

在嵌入式模型的特征選擇方法中，基于圖的特征選擇方法備受關注。傳統的基于圖的特征選擇方法嚴格依賴于固定的圖拉普拉斯矩陣，其通常采用兩步策略[15-17]：1)構造對稱親和矩陣；2)利用對稱親和矩陣指導特征選擇過程，得到圖拉普拉斯矩陣。然而，這種策略忽略了圖拉普拉斯矩陣在算法執行過程中的動態變化。具體地，在特征選擇算法執行過程中，算法的每一次更新迭代應該依賴本次迭代的圖拉普拉斯矩陣。傳統基于圖的特征選擇算法在每次算法迭代過程中，并沒有選擇適合本次迭代的圖拉普拉斯矩陣，前一次更新造成的誤差會被后續的更新不斷放大。因此，特征選擇方法無法獲得令人滿意的分類性能。另外，在有監督的多標簽特征選擇方法中還存在一個問題，大多數基于圖的特征選擇方法利用邏輯標簽來指導特征選擇[18-19]，然而邏輯標簽不能很好地反映相應標簽的重要性，即邏輯標簽無法刻畫標簽本身的重要程度，而且多標簽數據涉及大量不同標簽，這些標簽之間相關性復雜，這些問題導致多標簽特征選擇方法無法獲得令人滿意的分類性能。本文針對上述問題，設計了一種動態圖拉普拉斯的多標簽特征選擇方法。首先，本文構造了一個穩健的低維空間；其次，利用基于低維空間的動態圖拉普拉斯矩陣指導特征選擇過程；最后，通過在不同領域數據上的實驗證明了所提方法的分類優勢。本文主要貢獻如下。

1) 設計了一種基于特征矩陣的穩健低維空間的動態變化圖拉普拉斯矩陣來指導特征選擇。

2) 在所獲得的圖拉普拉斯動態更新基礎上，為避免邏輯標簽造成的信息丟失，將邏輯標簽轉化為實值標簽。

3) 設計了一種基于動態圖拉普拉斯矩陣和實值標簽的多標簽特征選擇方法，針對該方法提出一種有效的優化方案，并證明了該方案的收斂性。

4) 通過在9個多標簽基準數據集上與3 個多標簽特征選擇方法的對比實驗驗證了該方法的分類優越性。

2 相關工作

2.1 相關符號

2.2 相關工作

在多標簽學習中，已有許多行之有效的方法處理來自不同領域的多標簽數據?；诓煌潭鹊臉撕炏嚓P性可以將這些方法分為一階策略、二階策略和高階策略[3]。一階策略利用傳統的單標簽方法處理多標簽數據，忽略了標簽相關性，其中代表性方法有二元關聯（BR,binary relevance）[20]等。由于注意到標簽相關性的重要性，研究者開始考慮二階策略，即利用標簽之間的成對關系，相關多標簽視頻標注（CMLVA,correlative multi-label video annotation）和校準標簽排名（CLR,calibrated label ranking）是二階策略的代表方法[21-22]。高階策略通?？紤]標簽子集或所有標簽的相關性，其優點是充分考慮了標簽相關性，缺點是時間復雜度高且計算量大，如LLSFC-DL（learning label-specific features and class-dependent label）[23]為高階策略。本文中采用二階策略。

近年來，圖模型在數據結構挖掘方面取得顯著成就，受到研究者的廣泛關注。典型的圖模型是流形學習，其目的是在高維空間嵌入低維空間時，保持數據的幾何結構[24]。許多方法都是從樣例的角度來考慮流形結構的，即如果Xi.與Xj.具有很強的相似性，那么Yi.與Yj.的相似性也會很強。Ren 等[25]提出了一種無監督特征選擇方法來保持實例關聯的局部和全局結構。Huang 等[26]提出了一種考慮樣例相關性的基于流形的約束拉普拉斯評分方法。Xu等[27]提出了一種半監督多標簽特征選擇方法，考慮保持特征空間與標簽空間的一致性。Chen 等[28]提出的半監督多標簽學習方法考慮了樣例關聯和標簽關聯。但是，這些利用圖模型的方法都嚴重依賴于固定的圖拉普拉斯矩陣，而忽略了特征選擇中圖拉普拉斯矩陣的動態變化，圖拉普拉斯矩陣的不同設定會對后續的更新策略產生不同的影響，尤其是前一次更新造成的誤差會被后續的更新不斷放大。上述方法也存在利用邏輯標簽來指導標簽分類的問題，邏輯標簽并不能很好地反映相應標簽的重要性，而且多標簽數據涉及大量標簽，導致標簽相關性更加復雜，因此特征選擇方法無法獲得令人滿意的分類性能[29]。

多標簽特征選擇方法廣泛采用了一些不同的標準，如基于互信息的方法和基于稀疏學習的方法[8]。本文回顧了幾種有代表性的多標簽特征選擇方法。Lee 等[30]采用可擴展的相關性評估標準來評估條件相關性，提出了一種新的多標簽特征選擇方法，即大標簽集的可擴展準則（SCLS,scalable criterion for large label set）。然而，SCLS 的特征和標簽組合呈指數式增長，可能導致性能下降。Jian 等[17]設計了一種基于稀疏化的多標簽信息特征選擇（MIFS,multi-label informed feature selection）方法，利用標簽的局部幾何結構和低秩潛在標簽矩陣來消除無關特征。MIFS 的形式為

其中，X∈?n×d，Y∈?n×l，W∈?d×c分別表示特征矩陣、標簽矩陣和權重矩陣；V∈?n×c和B∈?c×l分別表示潛在標簽矩陣和系數矩陣；L∈?n×n表示拉普拉斯矩陣；α、β和γ表示MIFS 方法的3 個正則化超參數；c表示標簽的聚類簇數。

Cai 等[31]提出了一種基于稀疏學習的特征選擇方法，該方法被稱為穩健的增光拉格朗日乘子特征選擇（RALM-FS,robust augmented Lagrange multiplier for feature selection）。RALM-FS 對權重矩陣施加l2,0范數，從而獲得目標函數如式(2)所示。

其中，1表示元素全為1 的列向量，b表示偏置列向量，q表示所選特征數目。

3 動態圖拉普拉斯多標簽特征選擇方法描述

3.1 設計方法

本節提出一種新的多標簽特征選擇算法，考慮到圖拉普拉斯的動態變化能夠提供更有效的指導，并且為避免邏輯標簽造成的性能退化，將邏輯標簽轉化為實值標簽，加強挖掘特征選擇過程中的標簽相關性，使用式(3)所示的學習框架。

其中，第一項表示損失函數；第二項和第三項表示對該損失函數進行正則化處理，幫助減少損失函數造成的損失；F∈?n×c表示重構的標簽矩陣。

通常，損失函數利用最小二乘回歸模型學習從特征空間到標簽空間的映射矩陣W，但這種模型對于數據中存在的異常值非常敏感，特別是基于圖模型的學習模型對異常值的抗干擾能力非常弱。為獲得一個更加穩健的損失函數，本文設計了如式(4)所示的形式。

其中，Θ(W,F)表示關于W和F的函數；W∈?d×c表示特征權重矩陣，用于度量特征矩陣X中每一個特征的重要性，即值越大，第i個特征的影響越大；表示l2,1范數，可以有效減少異常值的干擾[18]；Tr(WLF WT)的設計受文獻[32]啟發，即在多標簽學習中保持標簽的局部幾何結構是至關重要的，本文利用上述圖模型來保持標簽的局部幾何結構。與傳統的圖模型不同，本文設計的拉普拉斯矩陣LF與重構標簽矩陣F緊密相關，L F隨F的更新而變化。Tr(WLF WT)的構造過程如下

其中，(N)p(F·j)表示F·j的p個最近鄰集合，σ表示熱核函數的帶寬參數。根據文獻[29]可知，傳統的有監督多標簽方法利用邏輯標簽評價輸入數據與輸出數據之間的相關性，不能很好地反映相應標簽的重要性，因此將式(3)中的第二項設計為式(7)所示形式。

其中，α和β表示正則超參數；F∈?n×c與邏輯標簽矩陣Y同型，但F顯然是連續數值型的，這種連續性可以較好地刻畫標簽的重要程度。將F作為一個更新變量時，為了保證F和Y之間的結構一致性，本文采用常規的圖模型對F進行約束。根據W可度量特征矩陣X中每一個特征的重要性這一特性，本文方法能夠有效實現特征選擇。式(3)中的第三項被設計為可有效實現稀疏化的特征篩選。最終目標函數被構造為式(8)所示形式。

其中，γ表示稀疏化正則超參數，用于調整目標函數的稀疏程度；控制W的行稀疏性[18]。但是行稀疏性并不能總被保證[33]，同時，Y中僅包含0 和1 這2 種非負元素，因此需要避免F的元素負值化。根據上述原因，本文對W和F實施了非負約束，最終的目標函數構造如下

3.2 優化方案

本節設計了一套針對式(9)所示目標函數的簡單有效的優化方案。根據分析可以得出，目標函數關于W和F是聯合非凸的。由于l2,1范數的存在，導致目標函數存在非光滑性問題。因此，本節提出了一種交替迭代的方法來解決非凸問題，同時引入了一種松弛化方法來處理非光滑問題[18]，獲得了拉格朗日函數，如式(10)所示。

其中，L(W,F)表示關于W和F的拉格朗日函數；表示2 個與W和F同型的拉格朗日乘子，這2 項同時將非負約束條件整合到目標函數中，從而方便了優化方案的設計；D1和D2是2 個對角矩陣，其第i個對角元素分別為

其中，?是一個非負的極小常數。對式(10)分別求W和F的偏導數，可得

算法1 中核心步驟為第7)～8)行，這2 個步驟促使算法逐步收斂于最終狀態。第12)行中k的取值主要依據文獻參考經驗值，如MIFS 中所采納的k值。

3.3 收斂性證明

顯然，可以推導出式(20)。

4 實驗分析

為了驗證所提方法的分類效果，本文在9 個多標簽基準數據集上與3 個先進的多標簽特征選擇算法進行比較。所有實驗均在內存為16 GB 的3.4 GHz的英特爾酷睿i7-6700 計算機上進行。

4.1 數據集描述及實驗設置

本文實驗所用數據均來自MulanLibrary[37]。這些屬于不同領域的數據集已經被眾多文獻使用[11-15]。例如，Birds 數據集是野外條件下采集的鳥類聲音數據，其中包括645 個音頻記錄，與19 種未壓縮WAV 格式的鳥類聲音相關。Yeast 數據集來自生物領域，該數據集包含2 417 個數據樣例，每個樣例有103 個特征和14 個標簽。Enron 數據集屬于文本領域，是安然電子郵件語料庫的一個子集。數據集的參數如表1所示。

為了證明所提方法的有效性，將其與MIFS、RALM-FS 和SCLS 這3 種先進的方法進行比較。此外，一些參數需要提前設定。首先，在構造近鄰矩陣的熱核函數中，參數p和σ分別被設置為c?1和1。為了方便，涉及超參數的各個對比方法中的參數統一在網格{0.01,0.1,0.3,0.5,0.7,0.9,1.0}范圍下進行搜索。然后，在五折交叉驗證過程中記錄參數的最佳值。根據文獻，使用BR 模型[20]將多標簽問題轉化為幾個二進制問題，使用線性支持向量機（SVM,support vector machines）分類器和K 最近鄰（KNN，K-nearest neighbor）分類器（K=3）進行分類處理，本文采用相同的方式以確保公平性。所有方法的分類性能由2 個評價標準來評估，即基于F1 度量的Micro-F1 和Macro-F1[38]。

其中，z和i分別表示標簽數和第i個標簽，TP、FP和FN 分別表示真陽性、假陽性和假陰性。Micro-F1和Macro-F1 均是值越大表示相應的方法分類性能越好。為評估所提方法的分類性能，本文在9 個不同的多標簽數據集上進行實驗。根據一些經驗方法[17]，本文使用每個數據集中總特征的前20%來計算不同方法的平均結果和標準偏差。

4.2 實驗結果及分析

表2～表5 記錄了4 個多標簽特征選擇方法在9 個數據集上的實驗結果。表中每一行最優值用黑色粗體表示。最后一行計算每個特征選擇方法下所有數據集的平均值。從表2～表5 可以看出，與其他方法相比，所提方法在所有數據集下分類效果更好。在SVM 分類器的基礎上，分別使用評估指標Micro-F1 和Macro-F1 獲得所有算法的分類結果，如表2 和表3 所示。從表2 和表3 可以看出，與其他方法相比，所提方法的Micro-F1和Macro-F1在所有數據集平均值均為最優值，分別為0.315 和0.097。

表1 數據集參數

表2 特征選擇方法在SVM 分類器上的Micro-F1 結果

表3 特征選擇方法在SVM 分類器上的Macro-F1 結果

表4 征選擇方法在3NN 分類器上的Micro-F1 結果

表5 特征選擇方法在3NN 分類器上的Macro-F1 結果

在3NN 分類器上所有方法的Micro-F1 和Macro-F1 如表4 和表5 所示。從表4 可以看出，所提方法的Micro-F1 平均值為0.325，相對于MIFS、RALM-FS 和SCLS，分別提升了13.6%、21.3%和16.5%。從表5 可以看出，所提方法的Micro-F2 平均值為0.124，相對于MIFS、RALM-FS 和SCLS，分別提升了17.0%、27.8%和22.8%。綜上所述，所提方法在不同評估條件下均取得優異的分類表現。為了進一步展示所提方法的分類優勢，本文選取6 個代表性的數據集（Arts、Yeast、Enron、Science、Education 和Social）繪制折線分析圖，如圖1～圖4 所示。

通過分析圖1～圖4，可以直觀地看到所提方法相比其他3 個多標簽特征選擇方法具有最佳分類表現。隨著所選特征數目的增加，不同方法的分類性能都總體先增加，后趨于穩定。圖1～圖4 的曲線都是振蕩上升的，產生這種現象的原因如下。所提方法屬于序列前向搜索方式的嵌入式特征選擇，這種策略通過一定的標準對所有特征進行排序，然后選擇k個排名靠前的特征。圖1～圖4 中，橫軸表示所選排名靠前的特征的占比。舉例說明如下，通常選擇前k個特征導致的分類性能可能會高于選擇k?1 個特征，而低于k+1 個特征的性能，這是因為不同的特征子集的組合導致的分類性能是不同的，即前k個單獨排名靠前的特征聯合導致的分類性能可能低于相互有關聯的k個特征組成的子集的分類性能。因此，前k個特征導致的分類性能可能會低于k+1 個特征的性能，但隨著特征數目的增加，依然可以導致整體分類性能的提升。這也就導致了曲線振蕩上升的現象。同時，可以觀察到，圖1～圖4 中所提方法對應折線總是在最上部，說明所提方法取得了更優異的性能?？傮w來說，所提方法取得優于對比方法的分類性能，原因是其考慮了特征選擇過程中圖拉普拉斯矩陣的動態變化，保證每次更新過程中所利用的圖拉普拉斯優于上一次的更新，并考慮數值標簽刻畫標簽的重要程度，以便更好地選擇特征。

圖1 6 個數據集在Micro-F1(SVM)上的實驗結果

圖2 6 個數據集在Macro-F1(SVM)上的實驗結果

圖3 6 個數據集在Micro-F1(3NN)上的實驗結果

圖4 6 個數據集在Macro-F1(3NN)上的實驗結果

4.3 參數敏感性分析

為了研究3 個超參數(α,β,γ)在多標簽特征選擇過程中產生的影響，本文通過搜索網格{0.01,0.1,0.3,0.5,0.7,0.9,1.0}來調整這些超參數。然而，網格搜索策略時間成本過高，為此本文參考文獻[17]中的策略，即固定其他超參數，僅調整其中一個超參數。本文設定被固定的超參數值為0.5，選擇Education數據集通過SVM 分類器進行超參數敏感性分析，分析結果如圖5 所示。圖5 中，超參數α在選擇的特征數目相同的情況下，在網格范圍內波動幅度較小，僅在α=0.1～0.5 時會對模型的分類性能產生影響，根據文獻[15,17]，這種程度的影響在實驗中是可以接受的，即算法對超參數α的變化不敏感，而且隨著選擇的特征數目的增加，影響更小。超參數β在選擇特征數目相同的情況下，在網格范圍內波動幅度較大，即非常敏感，這種敏感程度對算法性能的影響是不能忽略的。因此，超參數β在實際應用中可使用更大范圍的網格進行搜索以獲得令人滿意的性能。相對于超參數α和β，超參數γ選擇的特征數目相同情況下，在給定的網格范圍內波動幅度最小，因此與超參數α一樣，算法對超參數γ的變化不敏感。

圖5 在Education 數據集上所提算法關于α,β 和γ 的Micro-F1 和Macro-F1 (SVM)

4.4 收斂性分析與時間復雜度

本節對所提方法的收斂性和時間復雜度進行分析。首先，通過6 個代表性的數據集（Arts、Yeast、Enron、Science、Education 和Social）對所提方法的收斂性進行驗證，實驗結果如圖6 展示。從圖6 可以看出，所提方法的迭代收斂速度很快。在前2～3 次迭代中目標函數的損失值快速下降，然后下降速度開始變緩。特別是數據集Yeast 和Enron，僅迭代2 次之后，已無法直接觀察到目標函數損失值的變化，但根據分析可知，后面的迭代結果依然接近給定的迭代停止觸發條件。同樣地，數據集Arts、Science、Education 和Social 上的目標函數損失值也隨著迭代次數的增加迅速減小，并最終趨于穩定。實驗結果證明所提方法在3.2 節中所設計的優化方案下可有效收斂，同時驗證了3.3 節理論證明的正確性。

圖6 所提方法的收斂曲線

下面分析所提方法和對比方法的時間復雜度。設p、d、n和c分別表示已選特征數量、特征總數、樣例數和標簽總數。、SCLS 的時間復雜度為O(dc+pd)；MIFS 在每次迭代的時間復雜度為O(ndl+n2)；由于涉及矩陣的逆運算，RALM-FS的時間復雜度為O(d3)；所提方法的時間復雜度為O(dn2+d2n)。

5 結束語

針對多標簽分類和特征選擇的結合這一開放性問題，本文提出了一種基于動態圖拉普拉斯矩陣的多標簽特征選擇方法。該方法不同于以往基于圖的多標簽特征選擇方法依賴于固定的圖拉普拉斯矩陣，而是利用特征選擇過程中可以動態變化的圖拉普拉斯矩陣。在圖拉普拉斯矩陣的動態變化過程中，由于邏輯標簽導致標簽信息丟失，而其對應的實值標簽能夠更好地反映相應標簽的重要性，因此在新設計的動態圖拉普拉斯矩陣變化下，本文將邏輯標簽重構為實數值標簽，同時，利用l2,1范數減少動態構造拉普拉斯矩陣時異常值產生的影響。最后，本文設計了一套針對所提方法的簡單有效的優化方案。為了驗證所提方法的優越性，將其與3 個多標簽特征選擇方法在9 個不同領域的多標簽數據集上進行實驗對比。實驗結果表明，所提方法性能顯著優于對比方法，且可得到高質量的特征子集。下一階段，將進一步研究在非凸優化問題下的多標簽特征選擇方法。由于非凸優化問題和多標簽問題在現實生活中廣泛存在，因此多標簽特征選擇具有巨大的研究價值。