代價敏感數據的多標記特征選擇算法

黃琴，錢文彬，王映龍，吳兵龍

（1. 江西農業大學 計算機與信息工程學院，江西 南昌 330045; 2. 江西農業大學 軟件學院，江西 南昌 330045）

隨著物聯網及信息技術的發展，數據資源呈海量特征。在數據量不斷增大的同時，數據標注結構的復雜度也在增加，傳統的單標記學習已不能滿足現實應用的需求，因此多標記學習的重要性逐漸突顯。在多標記學習中，每個樣本在一個特征向量下，可能同時隸屬于多個類別標記。近年來，多標記學習問題已成為機器學習、數據挖掘和模式識別等領域的研究熱點之一[1-4]。

波蘭數學家Pawlak教授于1982年提出的粗糙集理論是一種用于處理不精確、不完全和不相容知識的數學工具[5]，近年來，該理論在機器學習和數據挖掘領域得到了廣泛的應用[6-7]。屬性約簡，又稱特征選擇，是粗糙集理論的核心內容之一，其目的是在保持分類能力不變的條件下，刪除不相關或冗余特征。與單標記學習一樣，多標記學習也面臨著“維數災難”的挑戰。高維數據不僅影響算法的執行效率，也降低了分類器的分類性能，而特征降維技術是解決維數災難的有效方法。目前，針對單標記數據特征降維技術的研究較為廣泛，而針對多標記數據特征降維技術的研究相對較少。因此，基于多標記學習特征選擇的研究具有重要的理論和應用意義。另外，在現實應用領域中，數據特征的獲取往往需要花費一定的代價，為此從代價敏感的視角研究多標記特征選擇問題顯得尤為重要。

1 相關工作

近年來，在多標記特征提取方面已經取得一些有意義的研究成果。如Sun等[8]提出的多標記降維方法(LDA)，其直接將單標記特征降維的方法應用于多標記特征降維中，忽略了標記之間的相關性。Zhang等[9]采用核矩陣進行映射降維，設計了一種最大化依賴度的多標記特征降維方法(MDDM)。Yu等[10]提出了一種有監督的多標記潛在語義索引降維方法(MLSI)。多標記特征提取能夠實現特征降維的效果，但由于其忽略了標記之間的關聯以及損失了原始特征的物理含義，這對多標記學習問題的研究造成了較大的困難。

多標記特征選擇通過設計特征度量準則從原始特征中剔除冗余或不相關特征，得到一組相對最優的特征子集，從而可有效降低特征空間的維數，提升算法的分類性能。特征選擇的結果能夠保持原始特征的物理含義，使得多標記學習的研究更容易理解。目前許多研究人員針對多標記特征選擇開展研究，段潔等[11]重新定義了多標記鄰域粗糙集的下近似和依賴度的計算方法，在此基礎上，設計了一種基于鄰域粗糙集的特征選擇算法(ARMLNRS)。王晨曦等[12]從每個標記對樣本不同分組的角度出發，提出了基于信息粒化的多標記特征選擇算法(MFIG)。Lin等[13]在樂觀、中立和悲觀這3種不同的視角下，通過3種基于鄰域互信息準則進行特征選擇。劉景華等[14]通過引入局部子空間模型，構建了一種基于局部子空間的多標記特征選擇算法(MFSLS)。上述算法的計算復雜度相對較大。后來Lee等[15]通過特征信息熵之差最大化和正向搜索的方法選擇特征子集，設計時間復雜度較低的特征選擇算法，但其沒有給出和分析的信息熵閾值對特征子集的影響。張振海等[16]利用信息增益下的閾值選擇設計了一種多標記特征選擇算法(MLFSIE)。綜上所述，這些多標記特征選擇算法并未考慮到特征的代價敏感問題。

在許多實際應用領域中，獲取和采集數據是需要花費代價的，因此從代價敏感的視角研究多標記學習具有重要的意義。針對當前多標記特征選擇算法的計算復雜度較大且未考慮特征代價的問題，提出了一種面向代價敏感數據的多標記特征選擇算法。首先，該方法計算出特征與標記集合之間的信息增益，在此基礎上重新定義了特征重要度的計算方法，并根據服從正態分布的特征重要度與特征代價的標準差之間的差值，提出了一種合理的閾值選擇方法，從而實現對冗余或不相關特征的剔除，同時能得到總代價較低的特征子集。為了驗證算法的有效性，利用Mulan平臺上的真實多標記數據集進行實驗比較和分析，通過實驗結果進一步驗證算法的有效性和可行性。

2 基本知識

2.1 多標記學習

2.2 信息熵

基于條件信息熵下的特征選擇是研究者從信息觀視角對高維數據進行特征選擇，該方法可有效地度量信息的不確定性程度。

為了使得各個特征與標記之間的信息增益值在同一量綱下比較，需先對信息增益的值進行歸一化處理：

3 代價敏感下的多標記學習

3.1 基于特征代價的信息熵模型

在機器學習和數據挖掘領域，代價敏感學習是十大最具有挑戰性問題之一[17]。因此，將特征代價引入到多標記特征選擇具有重要的意義。

為了獲取合理的閾值，使得信息增益的值服從正態分布：

在計算測試代價下的標記集合下特征重要度之前，需先將特征代價進行歸一化處理：

3.2 基于特征代價的信息熵模型可行性分析

證明由信息論理論結合定義4和定義5可推導出，，且。當時，，信息增益的值最大；當時，，此時信息增益的值最小，同時可知，信息增益值具有非負性。

證明由性質1可得，若單個標記與特征的相關性越大，則信息增益值越大，即越大。由定義6可知，越大，則的值越大，而特征代價的值是固定的，此時可得越大，即標記在特征上的信息增益隨單個標記在特征上的信息增益的增大而增大。由性質1可知，標記與特征之間信息增益越大，則其相關程度也越大。由此可得，標記集合在特征上的信息增益具有單調性。

證明由性質2和定義7可知，特征代價的標準差的值是固定的，的值越越大，即閾值的值越大。

4 多標記特征選擇算法

4.1 算法描述

根據上述分析可知，在多標記學習算法中，一個特征不僅與某一標記具有相關性，也可能同時與多個標記具有相關性，因此需要計算單個特征與標記集合之間的相關性。在此基礎上，從代價敏感學習的視角，提出了一種基于測試代價的特征重要度；然后根據服從正態分布的特征重要度以及特征代價的標準差設計出一種合理的閾值選擇方法；最后，通過計算的閾值刪除冗余或不相關的特征。

本文提出的代價敏感數據的多標記特征選擇算法(CSMLFSIE)具體步驟如下：

算法 代價敏感數據的多標記特征選擇算法(CSMLFSIE)

輸出 特征子集 Red。

6)輸出特征子集 Red，算法結束。

4.2 時間復雜度分析

代價敏感數據的多標記特征選擇算法中：步驟1)初始化一個變量存放特征選擇后的特征子集，其時間復雜度為；步驟2)中①需利用基數排序[18]計算等價類, 則整個條件特征集每個特征的信息熵的時間復雜度為，步驟2)中②計算每個特征的條件信息熵的時間復雜度為，可知步驟2)的時間復雜度最壞為；步驟3)分別計算每個標記與每個特征之間的信息增益，其時間復雜度為；步驟4)中①計算標記集合下每個特征重要度，其時間復雜度為，步驟4)中②計算閾值的時間復雜度為，因此步驟4)的時間復雜度最壞為；步驟5)根據閾值進行特征選擇其時間復雜度為。因此本文算法的時間復雜度為。

為了分析本文算法在計算復雜度上的優越性，將本文算法分別與CSMLPA[19]算法和MLDM算法進行比較。CSMLPA算法是基于文獻[20]的正區域模型設計的，并且考慮了測試代價的多標記特征選擇算法，算法采用的是向前啟發式搜索策略，其計算復雜度主要消耗在計算加入單個特征到特征子集后的正域大小，時間復雜度為。MLDM算法是基于文獻[21]的差別矩陣方法改進的多標記特征選擇算法，該算法主要耗時在對實例進行兩兩比較，其時間復雜度為。本文算法與CSMLPA算法和MLDM算法相比，時間復雜度由非線性和降低至線性。由此可知，本文算法在計算復雜度上具有顯著的優越性。

5 實驗結果與分析

為了驗證本文的CSMLFSIE算法的性能，從Mulan數據集中選取了Emotions、Birds和Yeast這3個真實數據集進行實驗測試和分析。實驗將算法CSMLFSIE與MLFSIE、CSMLPA、MLPA和MLDM進行對比分析，其中，MLFSIE[16]是一類基于信息熵的多標記特征選擇算法，CSMLPA算法是基于文獻[20]的正區域模型設計的考慮了測試代價的多標記特征選擇算法，MLPA是一種利用文獻[20]中的正區域模型改進的多標記特征選擇算法，MLDM算法是基于文獻[21]的差別矩陣方法改進的多標記特征選擇算法。最后通過IBLRML多標記分類器驗證上述算法特征選擇結果的分類性能。

實驗過程中首先采用以上5種特征選擇算法分別對3個數據集進行特征降維，然后使用分類算法對降維后的數據集采用10倍交叉驗證法驗證算法的有效性。本實驗的測試環境：CPU為Inter(R) Core(TM) i5-4590s (3.0 GHz)，內存 8.0 GB，算法編程語言為Python和Java，使用的開發工具分別是記事本和Eclipse 4.7。

5.1 數據集

實驗中選取的3個真實數據集的相關信息如表1所示，表中Yeast[22]數據集描述的是酵母菌的基因功能分類，Emotions[23]數據集是來自于某音樂學院的音頻剪輯，Birds[24]數據集通過鳥叫聲的記錄來區分鳥的種類。其中，Yeast數據集涉及的是生物信息領域，而Emotions和Birds數據集涉及的是音頻信息領域。表1中對數據集中的實例個數、特征數、標記數、標記基數和總代價進行了描述，其中，標記基數用于統計訓練集中實例的平均標記個數，總代價是指利用正態分布函數為數據集中的所有特征生成的代價總和。

表1 多標記數據集Table 1 Multi-label datasets

5.2 評價指標

文中選用了代價約簡率以及平均分類精度(average precision，AP)、漢明損失 (Hamming loss，HL)、覆蓋率 (Coverage)、1 錯誤率 (one error，OE)、排序損失(ranking loss，RL)這5種多標記評價性能指標來評價算法性能。給定一組多標記對象集合，，表示對象大小，表示多標記分類器預測測試對象具有的標記集合，表示多標記分類{器預測測試對}象具有的標記集合，，，表示所有標記集合，表示測試對象實際的標記集合，表示的補集，為標記的排序。

2) 平均分類精度(AP)是指在標記預測序列中，排在相關標記之前的標記仍是相關標記的比率：

3) 漢明損失(HL)是指預測出的標記與實際標記的平均差異值：

4) 覆蓋率(Coverage)是指所有對象實際包含的所有標記所需最大的排序距離：

5) 1錯誤率(OE)是指預測出的標記排序最靠前的標記不在實際對象中的比率：

6) 排序損失(RL)是指預測出的標記中實際不包含的標記比實際包含的標記排序高的比率：

平均分類精度越大說明分類性能越好，代價約簡率、漢明損失、覆蓋率、1錯誤率、排序損失越小說明分類性能越好。

5.3 實驗結果及比較

由于本文所選擇的3個多標記數據集的特征值都包含連續型數據，但CSMLFSIE算法處理的是離散型特征變量，因此對于多標記數據集的處理需要對特征值進行離散化處理。在實驗過程中發現，的步長取值為5時，降維后的特征子集的分類性能差別較為明顯。因此，本文將以步長5從5增加到50進行實驗分析與比較。下面以Emotions數據集為例，討論離散化參數的選擇對多標記分類性能的影響，圖1～5給出了Emotions數據集的5項評價指標隨著離散化參數的值增加的變化曲線。CSMLFSIE曲線、MLFSIE曲線、CSMLPA曲線、MLPA曲線和MLDM曲線分別為這幾種多標記特征選擇算法的性能。

由圖1～5可知，CSMLFSIE和MLFSIE算法的5項分類性能隨離散化參數增加變化較為平緩，CSMLPA、MLPA和MLDM算法的5項分類性能隨離散化參數增加變化較為顯著，其中，變化較顯著的是MLPA算法，5項分類性能隨離散化參數取值的增加變化趨勢較明顯。針對CSMLPA算法，當的取值在[5，10]這個區間時，HL、OE、Coverage和RL的值隨離散化參數的取值增加而增大，同時，AP的值隨離散化參數的取值增加而減小，5項多標記性能指標的值變化較為明顯。當的取值在[40，50]區間時，HL、OE、Coverage、RL和AP這5項多標記分類性能指標的值變化較小。針對MLDM算法，當離散化參數值從5變化至20時，HL、OE、Coverage和RL的值呈上升趨勢，AP的值呈下降趨勢，降維后的特征子集的分類性能變化較顯著。當離散化參數取值從25變化至35時，HL、OE、Coverage、RL和AP的5項性能指標的值變化較為平緩，由此可知，降維后的特征子集的分類性能在這個區間的穩定性較強。另外，通過實驗結果可知，當離散化參數的值為25時，CSMLFSIE和MLFSIE算法所取得的特征子集的分類性能最優；CSMLPA和MLDM算法在離散化參數為5時，其降維后的特征子集分類性能最優；當時，MLPA算法得到的特征子集的分類性能最優。

圖1 漢明損失隨著離散化參數增加的變化曲線Fig. 1 Variation of Hamming loss with increase in the discretization parameter

圖2 1錯誤率隨著離散化參數增加的變化曲線Fig. 2 Variation of one error rate with increase in the discretization parameter

圖3 覆蓋率隨著離散化參數增加的變化曲線Fig. 3 Variation of coverage with increase in the discretization parameter

圖4 排序損失隨著離散化參數增加的變化曲線Fig. 4 Variation of ranking loss with increase in the discretization parameter

圖5 平均精度隨著離散化參數增加的變化曲線Fig. 5 Variation of average precision with increase in the discretization parameter

綜上所述，與其他4種算法相比，隨離散化參數增加，CSMLFSIE算法的5項分類性能變化最為平緩，即離散化參數的變化對CSMLFSIE算法影響最小，因此CSMLFSIE算法的穩定性和健壯性更優。

5.3.2 實驗對比

實驗過程中將訓練數據集和測試數據集相結合，采用10倍交叉驗證法來驗證算法的有效性，實驗結果采用評價指標的平均值和標準差表示。另外，由于Mulan數據集自身并不含測試代價，因此本文采用正態分布函數為每個特征生成測試代價，其中，正態分布函數的取值以100為期望，以30為標準差。

表2～4中表示在正態分布函數下，用5種多標記特征選擇算法分別對Yeast、Emotions和Birds這3個數據集進行特征降維，并用IBLR-ML分類算法驗證降維后的特征子集的分類性能，同時，與原始數據集的分類性能進行對比。表2～4中給出的數據是AP取最優值時，所對應的PC、HL、OE、Coverage、RL和k的值。另外，各項評價指標的最優值用黑體標注，↓表示該項指標值越小算法的分類性能越好，↑表示該項指標的值越大算法的分類性能越好。

表2 Yeast數據集的實驗結果比較Table 2 The comparisons of Yeast datasets

表3 Emotions數據集的實驗結果比較Table 3 The comparisons of Emotions datasets

表4 Birds數據集的實驗結果比較Table 4 The comparisons of Birds datasets

由表2～4中的5種多標記分類性能評價指標的結果可以看出，CSMLFSIE算法總體優于其他4種算法，較為明顯的有Coverage、HL和AP這3項性能指標。同時，通過CSMLFSIE算法進行特征降維后，特征子集的分類性能優于原始數據集，其中，最為突出的是在PC這項指標上。另外，由表2～4可知，各個算法分類性能最優時，所對應的離散化參數k的取值也存在差異。由表2中的Yeast數據集可知，由本文CSMLFSIE算法降維后的特征子集的分類性能較優，其降維后的特征子集PC的值與MLFSIE、CSMLPA、MLPA和MLDM算法相比，分別減少了0.92%、14%、13.47%和12.68%；同時，AP分別提高了0.13%、2.54%、2.54% 和 3.26%，且 OE、Coverage和RL值相對較優。另一方面，CSMLFSIE算法降維之后的特征子集與原始數據集相比，PC的值為2.34%，比原始數據集減少了97.66%，且其他5項分類性能評價指標的值更優，其中，AP的值提高了0.37%，HL、OE、Coverage、RL值分別降低了0.02%、0.66%、3.6%和0.16%。

針對Emotions數據集，由本文CSMLFSIE算法選擇的特征子集的分類性能總體較優，根據表3中各項性能指標的結果可知，除HL和OE性能指標之外，其他3項多標記分類性能指標的值最優，且總測試代價PC的值最小。CSMLFSIE 算法與MLPA算法相比，PC的值同為6.47%，但AP的值卻提高了6.26%，同時，HL、OE、Coverage和RL的值都顯著降低。由此可知，CSMLFSIE算法要優于MLPA算法。CSMLFSIE算法與MLFSIE算法相比，PC的值減少了12.49%，另外，Coverage、RL和AP這3項性能指標相對更優，因此CSMLFSIE算法總體優于MLFSIE算法。此外，CSMLFSIE算法與CSMLPA和MLDM算法相比，PC的值分別減少了15.36%和10.61%，其HL、OE、Coverage、RL和AP這5項性能指標的值更優。

從表4中的Birds數據集可以看出，CSMLFSIE算法選擇后的特征子集的分類性能與Raw Data相比，除HL這項性能指標之外，其他4項性能指標的值都更優，PC的值也減少了88.65%，因此CSMLFSIE算法選擇后的特征子集的分類性能總體優于Raw Data。CSMLFSIE算法與MLFSIE算法相比，Coverage、RL和AP的值較優，PC的值減少了35.89%。CSMLFSIE算法與CSMLPA算法相比，PC的值減少了10.18%，AP的值由59.05%提高至61.71%，HL、OE、Coverage和RL的值分別降低了0.08%、2.18%、21.21%和0.79%。CSMLFSIE算法與MLPA算法和MLDM算法相比，AP的值分別提高了4.25%、4.37%，HL、OE、Coverage和RL的值有所下降，但PC的值分別增加了8.88%、8.7%。由此可知，由CSMLFSIE算法選擇的特征子集的分類性能總體較優。

另外，由表2～4可知，針對CSMLPA算法，3個數據集的離散化參數k取值為5時，其降維后特征子集的分類性能最優；針對CSMLFSIE算法進行離散化處理時，參數值為45時，Yeast數據集和Birds數據集降維后的特征子集的分類效果較佳，而對于Emotions數據集來說，離散化參數取25較優；針對MLFSIE算法和MLPA算法，在3個數據集降維后的特征子集的分類性能最優時，所對應的離散化參數的取值也不同；針對MLDM算法，對于Yeast數據集和Emotions數據集，離散化參數取5時，降維后的特征子集的分類性能較優，在Birds數據集中，離散化參數取值為25較好。由此可知，各個算法的分類性能與離散化參數k的取值相關，降維后的特征子集影響著分類器的分類性能。

綜上所述，原始數據集中存在大量冗余和不相關特征，且這些特征直接影響了分類器的分類性能，綜合各項性能評價指標可知，CSMLFSIE算法總體優于其他4種算法，達到了較好的特征降維的效果。

6 結束語

傳統的基于多標記的特征選擇算法往往忽略了每個特征獲取和采集所需花費的代價問題，為此，本文提出了一種代價敏感數據的多標記特征選擇算法，該算法利用信息熵分析特征與標記之間的相關性，利用均勻分布函數和正態分布函數為特征生成測試代價，從代價敏感的研究視角，構建一種新特征重要度準則。然后，根據服從正態分布的特征重要度和特征代價的標準差設置閾值，通過閾值剔除冗余和不相關特征。通過對3個真實數據集實驗結果的分析與比較，驗證了本文算法的有效性和高效性。但是，該算法并未充分考慮標記之間的相關性以及誤分類代價的問題，這也是我們下一步的研究工作。