邊緣標記弱化的多標記特征選擇算法

王一賓，吳 陳，程玉勝，江健生

（1.安慶師范大學計算機與信息院，安慶，246133；2.安徽省高校智能感知與計算重點實驗室，安慶，246133）

引 言

特征選擇[1-6]作為一種降維手段被廣泛運用在多標記學習中[7]，許多學者對此進行了探究并取得了卓越的成果。例如，文獻[8]結(jié)合標記權(quán)重和分類間隔構(gòu)造出鄰域信息度量方法；文獻[9]提出一種基于互信息的過濾型特征選擇方法；文獻[10]通過對子空間學習的研究，提出了基于非負稀疏表示的多標記特征選擇方法等。然而現(xiàn)有的特征選擇算法多數(shù)是基于標記分布平衡這一假設(shè)，相對于標記不平衡問題卻鮮有考慮。如圖1 是數(shù)據(jù)集Arts 的標記分布圖，可以看出第5，8，11，13，16，21 和26 個標記分布較為均衡，其他標記則表現(xiàn)為不平衡分布，相似的情況在其他數(shù)據(jù)集中也有體現(xiàn)。而通過對標記分布問題的研究，可以充分挖掘標記空間內(nèi)的信息，加深各類標記對樣本的描述程度。

眾所周知，一個實例中是否存在該標記往往取決于實例的特征屬性。如有人出現(xiàn)“鼻塞”“流鼻涕”等癥狀時，或許是因為“流感”導致的，又或者是“鼻炎”所引發(fā)的，二者皆有可能，但如果還伴隨著“全身酸痛”和“發(fā)燒”等癥狀時，則是“流感”的緣故更大一些，稱此類現(xiàn)象為標記的不平衡性?，F(xiàn)實世界中普遍存在著標記的不平衡性現(xiàn)象，而對于此類現(xiàn)象的研究較為罕見，傳統(tǒng)的處理方式多半是對不平衡數(shù)據(jù)進行重采樣或抽樣處理，將其轉(zhuǎn)變成平衡數(shù)據(jù)再進行深究，造成的結(jié)果可能是原有數(shù)據(jù)集的屬性因此而改變且分類精度有所折損。如果在分類過程中加入不同標記信息，這樣不僅能保留原有數(shù)據(jù)集中特征空間的原始屬性，同時對分類器的分類精度也有大幅提高。目前對其的研究主要為：文獻[11]提出了一種類不平衡下異方差線性判別分析（Linear discriminant analysis，LDA）的動態(tài)線性模型；文獻[12]提出了一種解決二元分類中的類不平衡問題的啟發(fā)式方法；文獻[13]通過使用單類支持向量機（Support vector machine，SVM）和欠采樣技術(shù)來研究類不平衡和類重疊問題；文獻[14]通過二元混淆矩陣的分類性能來度量類不平衡的影響等?？梢?，現(xiàn)有的研究多數(shù)是針對單標記下的不平衡性問題，而對多標記下的不平衡性卻鮮有研究。

同時不難察覺，不同于只有單一語義的單標記學習，在多標記學習中，當特征空間的變化對標記空間中某類標記影響甚微或者無影響時，意味著該類標記與特征之間的關(guān)聯(lián)性較為微弱或無關(guān)，該類標記被稱之為邊緣標記。例如在標記空間中時常會出現(xiàn)某類單一標記全為0 或全為1 的情況，該類標記所含有用信息較少且冗余，有時甚至包含錯誤的信息，那么需對此類標記進行弱化處理，減少冗余無關(guān)信息，提高算法預測準確率。而對于標記空間中0 或1 標記約占1/2 概率的情況，即當標記分布大致均衡時，該類標記能提供更為豐富的有效信息，同時對其進行相應的強化處理可以高效突出有用信息，進一步提升分類的精度。

針對多標記下的標記分布不平衡問題，本文提出了邊緣標記弱化的多標記特征選擇算法(Weakening marginal labels,WML)：首先對標記空間進行處理，統(tǒng)計每個標記下正負類標記樣本出現(xiàn)的頻數(shù)，然后對正負類樣本頻數(shù)進行比值處理，構(gòu)造一個權(quán)值矩陣將比值結(jié)果存儲其中；然后運用賦權(quán)方法弱化標記空間中的邊緣標記，同時利用信息熵等相關(guān)知識來衡量標記與特征的關(guān)聯(lián)性；最后依據(jù)所構(gòu)模型提出本文算法。在多個數(shù)據(jù)集上的實驗結(jié)果表明本文算法在分類精度和穩(wěn)定性方面具有一定優(yōu)越性。

圖1 Arts 數(shù)據(jù)集標記分布圖Fig.1 Label distribution of Arts dataset

1 相關(guān)知識

1.1 多標記學習框架

表1 多標記數(shù)據(jù)集Table 1 Multi-label datasets

3.2 實驗結(jié)果

本文實驗均在Matlab2016a 中運行，具體硬件環(huán)境為Inter(R) Core(TM) i7-7700HQ CPU @2.80 GHz，8 GB 內(nèi)存，實驗使用的電腦系統(tǒng)為現(xiàn)今普遍的Windows 10 操作系統(tǒng)。同時也運用具有代表性且有說服力的ML-kNN[18]作為本文的基礎(chǔ)實驗分類器。

實驗所用算法包括：基于最大相關(guān)性的屬性約簡算法（Multi-label dimensionality reduction via dependence maximization，MDDM[19]），該算法利用兩種投影策略，根據(jù)原始特征與標記空間最大相關(guān)性將原始數(shù)據(jù)投影到較低維的特征空間；基于多變量互信息的多標記特征選擇算法（Pairwise multivariate mutual information, PMU[20]），該算法是通過選擇與標記空間互信息最大的特征生成特征子集；多標簽樸素貝葉斯分類的特征選擇算法(Feature selection for multi-label naive Bayes classification, MLNB[21])，此算法主要是以遺傳算法和主成分分析為基礎(chǔ)，進而采用貝葉斯分類法實現(xiàn)特征提??；基于標記相關(guān)性的多標記特征選擇算法（Multi-label feature selection with label correlation，MUCO[22]）。而MDDMspc與MDDMproj 兩種方法由于MDDM 在實驗過程中采取的參數(shù)并不相同而進行區(qū)分。

通過所做實驗可知，本文算法與MDDM，PMU 和MUCO 等方法得到一組用特征序列表示的結(jié)果，所以在實驗過程中將所選的特征子集個數(shù)按照MLNB 算法實驗進行相同的設(shè)置，本文在運行實驗過程中的基礎(chǔ)實驗分類器ML-kNN，而在實驗過程中設(shè)置的平滑系數(shù)為s=1 以及k=10。實驗結(jié)果如表2-6 所示。表中數(shù)值依據(jù)“↑”表示為其值若越大則越優(yōu)，“↓”為越小越優(yōu)，最優(yōu)結(jié)果已黑色加粗。與此同時，為了凸顯各算法間的性能差異，本文采用顯著性水平5%的成對T 檢驗[23]進行算法對比，并在表格中用·/○表示本文算法優(yōu)于/差于對比算法，底行括號中數(shù)字為最優(yōu)個數(shù)。

3.3 實驗結(jié)果分析

（1）表2中實驗結(jié)果表明：對于評價指標AP，通過對比MDDMspc，MDDMproj，PMU，MLNB 和MUCO 這5個算法，在8個數(shù)據(jù)集上能看出本文算法均取得最優(yōu)值，僅在Education上次于MUCO 算法0.008 6，表明本文算法性能較為突出，在9個數(shù)據(jù)集上的平均結(jié)果顯示本文算法排在第一，MUCO算法排在第二。

（2）表3 中實驗結(jié)果表明：對于評價指標RL，本文算法在9 個數(shù)據(jù)集中有6 個數(shù)據(jù)集結(jié)果優(yōu)于其他算法，MUCO 算法在數(shù)據(jù)集Education 和Society 上比本文算法分別提升0.003 4 和0.001 6，PMU 算法在Yeast 上僅比本文算法少0.004 4，依據(jù)平均結(jié)果得出，本文算法排列第一，性能也是最好。

（3）表4 中實驗結(jié)果表明：對于評價指標CV，其中有6 個數(shù)據(jù)集的值都是最小的，本文算法在Education 和Society 兩個數(shù)據(jù)集上比MUCO 算法增加0.124 7 和0.040 6，而在Yeast 數(shù)據(jù)集上比PMU 算法增加0.140 5，本文算法在和其他所有算法進行對比時，9 個數(shù)據(jù)集上有6 個占優(yōu)，在其他數(shù)據(jù)集上名列前三，而在CV 的平均結(jié)果名列第一。

表2 各算法在平均精度上的結(jié)果Table 2 Results of each algorithm in average precision（↑）

表3 各算法在排位損失上的結(jié)果Table 3 Results of each algorithm in ranking loss（↓）

表4 各算法在覆蓋率上的結(jié)果Table 4 Results of each algorithm in coverage（↓）

表5 各算法在1-錯誤上的結(jié)果Table 5 Results of each algorithm in One error（↓）

表6 各算法在海明損失上的結(jié)果Table 6 Results of each algorithm in Hamming loss（↓）

（4）表5 中實驗結(jié)果表明：對于評價指標OE，本文算法在7 個數(shù)據(jù)集上其結(jié)果都是最小，MUCO 算法在Education 數(shù)據(jù)集上只比本文算法減少了0.013 0，PMU 算法也只比本文算法在Yeast 數(shù)據(jù)集上減少0.009 8，充分表明了本文算法的優(yōu)越性，而且在各數(shù)據(jù)集的平均結(jié)果上同樣排名第一。

（5）表6 中實驗結(jié)果表明：在HL 上，本文算法在9 個數(shù)據(jù)集中有7 個占優(yōu)，這表明了本文算法的性能效果最好，而本文算法也僅在Education 和Society 數(shù)據(jù)集上稍遜色于MUCO 算法，同樣在平均結(jié)果上本文算法位居第一。

綜上所述，本文在9 個標記數(shù)據(jù)集和5 個評價指標上進行了大量實驗對算法WML 的有效性和合理性進行了驗證。在5個評價指標上，本文提出的WML算法在大多數(shù)數(shù)據(jù)集上都排列第一，在其他數(shù)據(jù)集也都位居前列，表明本文算法優(yōu)于當前多數(shù)的多標記特征選擇算法。而其原因在于本文算法充分考慮了標記分布不平衡問題，通過計算不同標記下正負標記的頻數(shù)作為該標記的權(quán)值，運用賦權(quán)方法弱化標記空間中的邊緣標記，同時利用信息熵等相關(guān)知識來衡量標記與特征的關(guān)聯(lián)性；即在保留原有數(shù)據(jù)集中特征空間的原始屬性的情況下，將標記空間的信息加入到了特征選擇過程中，從而選出了信息更豐富的特征。

3.4 統(tǒng)計假設(shè)檢驗及算法穩(wěn)定性分析

為了更好體現(xiàn)本文算法WML 在9 個數(shù)據(jù)集下和其他算法所對比的合理性，本文通過結(jié)合統(tǒng)計學等相關(guān)知識進行顯著性水平為5%的Nemenyi 檢驗[24]來驗證實驗結(jié)果。若對比算法之間在所有多標記數(shù)據(jù)集下進行對比的平均排序的差值低于臨界差(Critical difference，CD)，則認為這兩個對比算法之間不存在顯著性的差異，否則認為是有顯著性的差異。圖4 顯示了各算法的對比結(jié)果，依據(jù)式(17)計算CD=2.513 5(k=6,N=9)，在坐標軸上數(shù)字越小，算法性能在此方面則表示越好。圖中不同彩色實線相連接的算法表示兩者之間并不存在顯著性差異，反之則有顯著性差異。由CD 圖結(jié)果顯示，本文算法在各指標上排名均占優(yōu)，即有

圖4 各算法Nemenyi 檢驗的性能對比Fig.4 Performance comparison of Nemenyi test by different algorithms

為了對本文算法進行穩(wěn)定性分析[25]，本文采用雷達圖的形式來表示。由于在各數(shù)據(jù)集上預測分類時的實驗結(jié)果會有所偏差，出于對此的考慮，本文將實驗結(jié)果進行標準歸一化在[0.1,0.5]區(qū)間內(nèi)，然后利用歸一化處理后的實驗數(shù)值度量算法穩(wěn)定指數(shù)。圖5 給出了各算法的穩(wěn)定性。

圖5 各算法在9 個數(shù)據(jù)集和不同評價指標中的穩(wěn)定性Fig.5 Stability of each algorithm in nine datasets with different evaluation indexes

通過觀察圖5 可知：在評價指標AP 中，本文算法在穩(wěn)定指數(shù)值為[0.4,0.5]范圍內(nèi)均展現(xiàn)出十分穩(wěn)定的效果；在評價指標RL 中，本文算法同樣是相當穩(wěn)定的解決方案，各值均在[0.4,0.5]內(nèi)；在評價指標CV 中，本文算法在8 個數(shù)據(jù)集上對比其他算法得出了格外穩(wěn)定的結(jié)果；相似的結(jié)果在其他評價指標中也有體現(xiàn)。

4 結(jié)束語

由于不同標記所含信息量的不同，對樣本空間的描述程度有所偏差，對于該標記分布不平衡問題，本文通過聯(lián)合信息熵和互信息等相關(guān)知識，提出了一種邊緣標記弱化的多標記特征選擇算法。在保留原有數(shù)據(jù)集中特征空間的原始屬性的情況下，利用不同標記下的正負標記比率權(quán)值來提升標記對樣本描述程度的精確性，進而運用該賦權(quán)方法弱化標記空間中的邊緣標記，因為在特征選擇過程中加入了標記空間的信息，所以選出了含有更加豐富信息的特征。實驗結(jié)果表明，本文算法在現(xiàn)有的特征選擇算法中具有一定的優(yōu)越性。但是本文在進行特征選擇時僅考慮了標記空間信息，并未考慮到特征空間的信息以及高維特征間的相關(guān)性問題，因此對其有待進一步的研究。