基于動(dòng)態(tài)圖拉普拉斯的多標(biāo)簽特征選擇

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

（1.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長春 130012；2.吉林大學(xué)符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室，吉林 長春 130012；3.吉林大學(xué)化學(xué)學(xué)院，吉林 長春 130012）

1 引言

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

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

1) 設(shè)計(jì)了一種基于特征矩陣的穩(wěn)健低維空間的動(dòng)態(tài)變化圖拉普拉斯矩陣來指導(dǎo)特征選擇。

2) 在所獲得的圖拉普拉斯動(dòng)態(tài)更新基礎(chǔ)上，為避免邏輯標(biāo)簽造成的信息丟失，將邏輯標(biāo)簽轉(zhuǎn)化為實(shí)值標(biāo)簽。

3) 設(shè)計(jì)了一種基于動(dòng)態(tài)圖拉普拉斯矩陣和實(shí)值標(biāo)簽的多標(biāo)簽特征選擇方法，針對該方法提出一種有效的優(yōu)化方案，并證明了該方案的收斂性。

4) 通過在9個(gè)多標(biāo)簽基準(zhǔn)數(shù)據(jù)集上與3 個(gè)多標(biāo)簽特征選擇方法的對比實(shí)驗(yàn)驗(yàn)證了該方法的分類優(yōu)越性。

2 相關(guān)工作

2.1 相關(guān)符號(hào)

2.2 相關(guān)工作

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

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

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

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

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

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

3 動(dòng)態(tài)圖拉普拉斯多標(biāo)簽特征選擇方法描述

3.1 設(shè)計(jì)方法

本節(jié)提出一種新的多標(biāo)簽特征選擇算法，考慮到圖拉普拉斯的動(dòng)態(tài)變化能夠提供更有效的指導(dǎo)，并且為避免邏輯標(biāo)簽造成的性能退化，將邏輯標(biāo)簽轉(zhuǎn)化為實(shí)值標(biāo)簽，加強(qiáng)挖掘特征選擇過程中的標(biāo)簽相關(guān)性，使用式(3)所示的學(xué)習(xí)框架。

其中，第一項(xiàng)表示損失函數(shù)；第二項(xiàng)和第三項(xiàng)表示對該損失函數(shù)進(jìn)行正則化處理，幫助減少損失函數(shù)造成的損失；F∈?n×c表示重構(gòu)的標(biāo)簽矩陣。

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

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

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

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

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

3.2 優(yōu)化方案

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

其中，L(W,F)表示關(guān)于W和F的拉格朗日函數(shù)；表示2 個(gè)與W和F同型的拉格朗日乘子，這2 項(xiàng)同時(shí)將非負(fù)約束條件整合到目標(biāo)函數(shù)中，從而方便了優(yōu)化方案的設(shè)計(jì)；D1和D2是2 個(gè)對角矩陣，其第i個(gè)對角元素分別為

其中，?是一個(gè)非負(fù)的極小常數(shù)。對式(10)分別求W和F的偏導(dǎo)數(shù)，可得

算法1 中核心步驟為第7)～8)行，這2 個(gè)步驟促使算法逐步收斂于最終狀態(tài)。第12)行中k的取值主要依據(jù)文獻(xiàn)參考經(jīng)驗(yàn)值，如MIFS 中所采納的k值。

3.3 收斂性證明

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

4 實(shí)驗(yàn)分析

為了驗(yàn)證所提方法的分類效果，本文在9 個(gè)多標(biāo)簽基準(zhǔn)數(shù)據(jù)集上與3 個(gè)先進(jìn)的多標(biāo)簽特征選擇算法進(jìn)行比較。所有實(shí)驗(yàn)均在內(nèi)存為16 GB 的3.4 GHz的英特爾酷睿i7-6700 計(jì)算機(jī)上進(jìn)行。

4.1 數(shù)據(jù)集描述及實(shí)驗(yàn)設(shè)置

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

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

其中，z和i分別表示標(biāo)簽數(shù)和第i個(gè)標(biāo)簽，TP、FP和FN 分別表示真陽性、假陽性和假陰性。Micro-F1和Macro-F1 均是值越大表示相應(yīng)的方法分類性能越好。為評(píng)估所提方法的分類性能，本文在9 個(gè)不同的多標(biāo)簽數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。根據(jù)一些經(jīng)驗(yàn)方法[17]，本文使用每個(gè)數(shù)據(jù)集中總特征的前20%來計(jì)算不同方法的平均結(jié)果和標(biāo)準(zhǔn)偏差。

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

表2～表5 記錄了4 個(gè)多標(biāo)簽特征選擇方法在9 個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。表中每一行最優(yōu)值用黑色粗體表示。最后一行計(jì)算每個(gè)特征選擇方法下所有數(shù)據(jù)集的平均值。從表2～表5 可以看出，與其他方法相比，所提方法在所有數(shù)據(jù)集下分類效果更好。在SVM 分類器的基礎(chǔ)上，分別使用評(píng)估指標(biāo)Micro-F1 和Macro-F1 獲得所有算法的分類結(jié)果，如表2 和表3 所示。從表2 和表3 可以看出，與其他方法相比，所提方法的Micro-F1和Macro-F1在所有數(shù)據(jù)集平均值均為最優(yōu)值，分別為0.315 和0.097。

表1 數(shù)據(jù)集參數(shù)

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

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

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

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

在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%。綜上所述，所提方法在不同評(píng)估條件下均取得優(yōu)異的分類表現(xiàn)。為了進(jìn)一步展示所提方法的分類優(yōu)勢，本文選取6 個(gè)代表性的數(shù)據(jù)集（Arts、Yeast、Enron、Science、Education 和Social）繪制折線分析圖，如圖1～圖4 所示。

通過分析圖1～圖4，可以直觀地看到所提方法相比其他3 個(gè)多標(biāo)簽特征選擇方法具有最佳分類表現(xiàn)。隨著所選特征數(shù)目的增加，不同方法的分類性能都總體先增加，后趨于穩(wěn)定。圖1～圖4 的曲線都是振蕩上升的，產(chǎn)生這種現(xiàn)象的原因如下。所提方法屬于序列前向搜索方式的嵌入式特征選擇，這種策略通過一定的標(biāo)準(zhǔn)對所有特征進(jìn)行排序，然后選擇k個(gè)排名靠前的特征。圖1～圖4 中，橫軸表示所選排名靠前的特征的占比。舉例說明如下，通常選擇前k個(gè)特征導(dǎo)致的分類性能可能會(huì)高于選擇k?1 個(gè)特征，而低于k+1 個(gè)特征的性能，這是因?yàn)椴煌奶卣髯蛹慕M合導(dǎo)致的分類性能是不同的，即前k個(gè)單獨(dú)排名靠前的特征聯(lián)合導(dǎo)致的分類性能可能低于相互有關(guān)聯(lián)的k個(gè)特征組成的子集的分類性能。因此，前k個(gè)特征導(dǎo)致的分類性能可能會(huì)低于k+1 個(gè)特征的性能，但隨著特征數(shù)目的增加，依然可以導(dǎo)致整體分類性能的提升。這也就導(dǎo)致了曲線振蕩上升的現(xiàn)象。同時(shí)，可以觀察到，圖1～圖4 中所提方法對應(yīng)折線總是在最上部，說明所提方法取得了更優(yōu)異的性能?？傮w來說，所提方法取得優(yōu)于對比方法的分類性能，原因是其考慮了特征選擇過程中圖拉普拉斯矩陣的動(dòng)態(tài)變化，保證每次更新過程中所利用的圖拉普拉斯優(yōu)于上一次的更新，并考慮數(shù)值標(biāo)簽刻畫標(biāo)簽的重要程度，以便更好地選擇特征。

圖1 6 個(gè)數(shù)據(jù)集在Micro-F1(SVM)上的實(shí)驗(yàn)結(jié)果

圖2 6 個(gè)數(shù)據(jù)集在Macro-F1(SVM)上的實(shí)驗(yàn)結(jié)果

圖3 6 個(gè)數(shù)據(jù)集在Micro-F1(3NN)上的實(shí)驗(yàn)結(jié)果

圖4 6 個(gè)數(shù)據(jù)集在Macro-F1(3NN)上的實(shí)驗(yàn)結(jié)果

4.3 參數(shù)敏感性分析

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

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

4.4 收斂性分析與時(shí)間復(fù)雜度

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

圖6 所提方法的收斂曲線

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

5 結(jié)束語

針對多標(biāo)簽分類和特征選擇的結(jié)合這一開放性問題，本文提出了一種基于動(dòng)態(tài)圖拉普拉斯矩陣的多標(biāo)簽特征選擇方法。該方法不同于以往基于圖的多標(biāo)簽特征選擇方法依賴于固定的圖拉普拉斯矩陣，而是利用特征選擇過程中可以動(dòng)態(tài)變化的圖拉普拉斯矩陣。在圖拉普拉斯矩陣的動(dòng)態(tài)變化過程中，由于邏輯標(biāo)簽導(dǎo)致標(biāo)簽信息丟失，而其對應(yīng)的實(shí)值標(biāo)簽?zāi)軌蚋玫胤从诚鄳?yīng)標(biāo)簽的重要性，因此在新設(shè)計(jì)的動(dòng)態(tài)圖拉普拉斯矩陣變化下，本文將邏輯標(biāo)簽重構(gòu)為實(shí)數(shù)值標(biāo)簽，同時(shí)，利用l2,1范數(shù)減少動(dòng)態(tài)構(gòu)造拉普拉斯矩陣時(shí)異常值產(chǎn)生的影響。最后，本文設(shè)計(jì)了一套針對所提方法的簡單有效的優(yōu)化方案。為了驗(yàn)證所提方法的優(yōu)越性，將其與3 個(gè)多標(biāo)簽特征選擇方法在9 個(gè)不同領(lǐng)域的多標(biāo)簽數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對比。實(shí)驗(yàn)結(jié)果表明，所提方法性能顯著優(yōu)于對比方法，且可得到高質(zhì)量的特征子集。下一階段，將進(jìn)一步研究在非凸優(yōu)化問題下的多標(biāo)簽特征選擇方法。由于非凸優(yōu)化問題和多標(biāo)簽問題在現(xiàn)實(shí)生活中廣泛存在，因此多標(biāo)簽特征選擇具有巨大的研究價(jià)值。