基于拉普拉斯評分的多標記特征選擇算法

胡敏杰，林耀進,王晨曦，唐 莉，鄭荔平

(閩南師范大學 計算機學院，福建 漳州 363000)(*通信作者電子郵箱zzhuminjie@sina.com)

0 引言

多標記學習是目前機器學習、模式識別和數據挖掘等領域的研究熱點之一[1-5]。多標記學習中每個樣本不僅由一組特征向量描述,還可能同時有多個語義，將多個語義設計成多個標記。例如：在圖像標注[1]中，一幅圖同時具有“沙漠”“藍天”“風景”等幾個語義信息；在文本分類學習[3]中，一篇文檔具有“上海世博會”“經濟”和“志愿者”等幾個主題；在音樂樂曲[4]中，一首樂曲可能同時具有 “放松”“幸福”“安靜”和“難過”等幾個情感語義。多標記學習中多個語義標記并不互斥，因此有別于單標記學習中的多個類別。多標記學習不僅需要了解利用多個標記之間的信息，同時仍然需要解決冗余特征、維數災難等問題。

一種常用的解決冗余特征和維數災難問題的有效方案是降維技術。目前多標記特征降維方案中主要是特征轉換和特征選擇。將原始高維特征空間變換或映射到低維空間來表示樣本，這一過程稱之為特征轉換，如基于最大依賴的多標記維數約簡方法(Multi-label Dimensionality reduction via Dependence Maximization, MDDM)[5]；在原始高維特征空間中利用一定的評價準則選擇一組能獲得相同甚至更高分類性能的原始特征集子集，這一過程稱之為特征選擇。相比重建了特征新空間的特征轉換方案，特征選擇對后續學習分析數據保留了特征的物理意義。特征選擇過程中常見的評價準則有信息度量[6-7]、依賴性度量[8]和譜圖理論[9-12]等。

基于拉普拉斯評分(Laplacian score)的特征選擇算法[9]是譜圖理論的特征選擇模型的典型算法之一。拉普拉斯特征評價算法對單個特征進行評判得分，選出有較高方差和較強局部幾何結構保持能力的特征。該算法簡單易理解，但該算法不但沒有考慮特征之間的關聯性且僅針對單一標記評價特征，而多標記學習面臨多個標記的評分。Alalga等[11]利用半監督對沒有標記的數據遠遠大于有標記的數據集進行軟約束的拉普拉斯特征選擇，利用部分樣本的標記信息構建有標記數據集中樣本間的關聯系數來約束核函數構建權重矩陣，該算法主要實現了在標記不易獲取僅部分樣本被標記的數據集中拉普拉斯特征選擇算法的實現；Yan等[12]利用樣本多個標記的Jaccard相似性來構建樣本的相似性矩陣，從而提出基于圖譜的多標記特征選擇算法，該算法不僅有效利用了類標間的關聯信息，且算法不依賴具體的多標記分類算法或問題轉化。以上兩種算法均僅考慮樣本的多個標記間共同關聯的相關性，且未考慮特征之間的相關性, 因此，本文在拉普拉斯評分的評價準則上不僅考慮特征之間的關聯性，同時考察樣本在多個標記間共同關聯和共同不關聯的相關性，重新構建基于多標記的拉普拉斯評分中的樣本相似性矩陣，從而提出了一種基于拉普拉斯評分的多標記特征算法。

1 傳統拉普拉斯特征選擇算法

拉普拉斯評分基于拉普拉斯特征映射和局部保持投影理論。假設Fr表示數據集中第r個特征，fir和fi′r分別表示第r個特征上的第i、i′(1≤i,i′≤m)個樣本的取值，xi、xi′分別表示第i、i′(1≤i,i′≤m)個樣本點,yi、yi′分別表示第i、i′(1≤i,i′≤m)個樣本的標記類別。算法思路如下：

第一步 構建近鄰無向有權圖G(V,E)。各樣本作為節點表示圖節點集V，樣本間的近鄰關系表示圖中的邊形成邊集E。如果樣本xi是樣本xi′的最近鄰的k個樣本之一或xi′是xi最近鄰的k個樣本之一，則xi與xi′節點相連成邊。

第二步 生成樣本間的相似矩陣S。根據數據是否攜帶標記信息，拉普拉斯特征選擇算法在構建樣本權重矩陣時分為兩種。

1)不考慮標記信息，通過核函數構造權重矩陣，如式(1):

(1)

2)對具有單一標記的數據，常根據類別個數來構建相似矩陣，如式(2):

(2)

其中：t是參數，一般取1；nk為類別為k的樣本個數。

第三步 生成拉普拉斯矩陣L。在無向有權圖G中，令鄰接矩陣Wii′=Sii′(1≤i,i′≤m),且W為對稱矩陣，則度矩陣D為:

(3)

度矩陣詮釋了每個樣本周圍聚集其他樣本的密集程度，值越大說明與之樣本靠近的其他樣本就越多。由度矩陣和鄰接矩陣得到相應的Laplacian矩陣L和正則化的Laplacian矩陣L：

(4)

第四步 拉普拉斯評分特征選擇。根據譜圖理論，Laplacian矩陣的特征值和特征向量能體現樣本分布的結構。因此拉普拉斯評分算法選取那些特征向量值的分布與樣本分布保持一致的可分性強的特征，即選擇那些使得式(5)取較小值的特征[9]:

(5)

其中：ur表示第r個特征fr的期望值，定義[9]如式(6):

(6)

2 多標記的拉普拉斯特征選擇算法

2.1 樣本相似度的構建

由于傳統拉普拉斯特征選擇算法適應單一標記的學習，而在多標記學習中每個樣本可能與多個語義標記關聯，因而無法按單一標記中通過類別個數來構建樣本的相似度。單標記學習中標記里的信息表示的是樣本屬于哪一類，而多標記學習中標記的信息表達的是與該標記是否相關。如表1中列舉有5個樣本x1、x2、x3、x4、x5和3個標記信息y1、y2、y3。

表1 一個多標記數據集例子

在表1中，1表示樣本與這個標記信息關聯，而0表示不關聯。如y1標記中樣本x1、x3、x4標記為1，表示樣本x1、x3、x4與標記y1相關聯，而樣本x2、x5標記為0表示與標記y1不關聯。若將標記信息里的0和1看成兩個類別，那么可以理解成在標記y1下樣本x1、x3、x4為同一類，而樣本x2、x5為另一類，因此可以依照傳統拉普拉斯評分算法中式(2)構建y1標記下的樣本相似矩陣，如表2所示。

表2 標記y1下樣本的相似度

以此類推，可以建立各標記下的樣本相似矩陣，如果各標記間相互獨立那么采用傳統拉普拉斯評分算法可求得各標記下的特征序列，然后對各標記下的特征序列融合以期求得最終的特征序列，但該方法并未探索樣本在整體標記空間中的相似程度。嚴鵬等[10]利用Jaccard相關性來衡量兩個樣本間在整體標記空間的相似程度，即對兩個樣本的標記集中用關聯標記的交集元素個數除以關聯標記的并集元素個數。如樣本x1與標記y1、y3關聯，樣本x2與標記y3關聯，因此樣本x1、x2關聯的標記交集為y3，關聯標記的并集為y1、y3，所以樣本x1和樣本x2相似度為1/2。依此嚴鵬等建立樣本在整體標記空間的相似矩陣如表3所示。

表3 Jaccard相關性下的樣本的相似度

受單標記類標記含義啟發，樣本x2和樣本x5在單標記y1下屬于0類，在多標記含義下樣本x2和樣本x5都不與y1標記關聯。

但嚴鵬等只對兩樣本關聯的標記尋求關系，而現實中兩樣本不與某些標記關聯也隱藏著一定的關系。如樣本x1和x2都不與標記y2關聯，都與標記y3關聯，將共同關聯和共同不關聯的都認可為樣本之間的相似度, 因此可設計一種新的多標記下拉普拉斯評分算法的樣本相似度S=(|Y|-|Y1⊕Y2|)/|Y|,其中Y1和Y2分別表示兩樣本的標記集。依此設計表1中樣本在整體標記空間的相似矩陣如表4所示。

表4 共同關聯和共同不關聯下的樣本的相似度

表2中樣本x2和x5在單標記y1下具有相似度為1/2,而表3中只考慮與標記共同關聯性，樣本x2和x5完全不相似，即相似度為0，但表4中同時考慮與標記共同關聯和共同不關聯性，樣本x2和x5具有1/3的相似度，由此表4更能保留說明樣本在整體標記空間的相似情況。

2.2 基于拉普拉斯評分的多標記特征選擇算法

由于傳統的拉普拉斯特征選擇算法只度量單個特征的可分性，而未考慮特征之間的冗余性和相關性，因此在計算了樣本在多個標記空間的相似度后，在評價特征的可分性上考慮特征之間的相關性。設多標記訓練集T={(xi,yi)|1≤i≤m}，其中，X={x1,x2,…,xm}表示樣本空間，樣本的標記集為Y={y1,y2,…,yi,…,ym}且yi={l1,l2,…,lq}表示由q個標記組成的標記向量(1≤i≤m)，若樣本xi(1≤i≤m)與lj(1≤j≤q)標記相關，則yij=1,否則yij=0。F={f1,f2,…,fn}表示描述樣本的特征向量，fir表示第r(1≤r≤n)特征上第i(1≤i≤m)個樣本的取值。

定義1 給定描述樣本的數據集和樣本的標記集Y={y1,…,yi,…,ym}，則樣本在整體標記空間的相似性矩陣S′和度矩陣D′分別為：

(7)

由此相應的Laplacian矩陣L′和正則化的Laplacian矩陣L′為：

定義2 給定描述樣本的數據集T和特征集F，當已知S′、D′、L′時，在整體標記空間下特征之間的相關性的目標函數為：

(8)

其中Fs′表示已選特征的子集。式(8)中分母通過各特征的均方差度量特征的區分能力，均方差越大，該特征集區分能力越強；式(8)的分子用歐氏距離計算各特征間的關聯性，分子越小特征子集對樣本分布結構保持能力越強, 使得式(8)獲較小值的特征子集能實現對樣本標記的識別力。因此式(8)的定義考慮了整體標記空間下特征間的相關性。

定義3 給定描述樣本的數據集和特征集，當已知S′、D′、φ(Fs′)時，候選特征中能加強現有特征子集Fs′對標記識別能力的特征定義為：

(9)

其中，Fu表示候選特征的集合，評估一個候選特征是否加入已選特征集中取決于該特征能否使得同類樣本取值接近而不同類樣本取值差異大。而對多個可加強已選特征集的候選特征，由式(9)可知，新加入的候選特征使φ(Fs′)越小越好，因此在多個具有提升已選特征子集能力的候選特征中選擇使φ(Fs′∪fi)-φ(Fs′)最小的一個特征, 因此式(9)的定義可以找到一組具有更強識別力的特征集。

2.3 算法步驟

本文提出了一種基于拉普拉斯評分的多標記特征選擇算法。該算法首先針對多標記學習中每個樣本可能具有的多個語義標記信息重新計算了樣本之間的相似度，從而構建了樣本在整體標記空間的相似矩陣；然后在建立的樣本相似矩陣上利用傳統的拉普拉斯評分算法找出特征集中最強識別力的一個特征；接著以該特征作為已選特征，根據定義2中式(8)和定義3中式(9)依次評價候選特征與已選特征的相關性與冗余性，選出識別力強于未組合時的最強一個特征，并加入已選特征集；最后對余下候選特征進行下一輪迭代，以期生成特征重要度排序集。

根據上述分析，一種基于拉普拉斯評分的多標記特征選擇算法(multi-label feature selection algorithm based on Laplacian score，MLLAP)的具體描述如算法1所示。

算法1 MLLAP算法。

輸入 多標記數據集T；

輸出 特征序列Fs。

步驟1 初始化已選特征集Fs=?，候選特征集Fu={f1,f2,…,fn}。

步驟2 依據定義1中式(7)計算兩個樣本間的相似度矩陣S′和度矩陣D′。

步驟3 根據式(5)求出最具有識別力的一個特征fi，更新Fs=Fs∪fi,Fu=Fu-{fi};

步驟4 根據式(8)和(9)依次判斷Fu中候選特征的得分L(i)=φ(Fs∪fi)-φ(Fs)，取每一輪最小值加入已選特征Fs。

步驟5 重復步驟4，直到Fu為空結束。

在算法1中，假設數據集中包含m個樣本和n個特征。MLLAP算法的時間代價主要在：步驟2中計算兩個樣本間的相似度矩陣，時間復雜度為O(m2);步驟4～步驟5依次評價候選特征的時間復雜度為O(nlogn); 該算法不依賴任何分類器。

3 實驗設計與結果分析

3.1 實驗數據

為了檢驗算法的有效性，本文在mulan數據庫(http://mulan.sourceforge.net/datasets.html)中選取6個多標記數據集進行驗證，各數據集描述信息見表5。

3.2 實驗設置

HL用來度量樣本在單一標記上的錯誤分類情況，定義為：

其中Zi表示預測到的標記集。

OE用來衡量在樣本的相關標記排序里排在第1位的標記不屬于樣本相關標記的樣本所占的比例：

其中:若l?Yi,則w(l)=1; 否則w(l)=0。

CV用來度量樣本在測試集上搜索與該樣本相關的標記所需的平均次數，定義為：

RL用來度量錯誤標記排在正確標記之前的比例，定義為：

AP用來統計在樣本的標記排序組里，排在該樣本正確標記前的標記仍為正確標記的平均比例，定義為：

以上5種評價指標中，AP指標取值越大學習性能越優，最優值為1；HL、OE、CV和RL指標取值越小越好，最優值是0。

本文選擇其他4個對比算法分別為：使用線性核和非線性核的基于最大依賴的多標記維數約簡方法MDDMspc[15]和MDDMproj[15]，基于貝葉斯分類器的多標記特征選擇算法(Feature selection for multi-label naive Bayes classification, MLNB)[16]和基于多元互信息的多標記分類特征選擇算法(Feature selection for multi-label classification using multivariate mutual information, PMU)[17]。采用多標記學習算法(Multi-label Learning based onkNN, ML-kNN)[18]來評估特征選擇后的性能，實驗中ML-kNN的近鄰k=10,平滑參數s=1。

3.3 實驗結果與分析

為了驗證所提算法的有效性，實驗中首先將所提MLLAP算法與MLNB、PMU、MDDMspc及MDDMproj算法誘導出來的特征子集的分類性能進行對比，并且分析各算法的分類性能隨特征數目增加而變化的情況；然后檢驗MLLAP算法與其他4個算法是否存在顯著性差異。由于所提MLLAP算法和PMU、MDDMspc及MDDMproj得到的是一組特征排序，因此實驗中選取特征排序的前k個特征作為特征子集，其中k為MLNB算法所得特征數。表6～10列出了5種對比算法在6個數據集5個評價指標下的實驗結果。

表6 各算法在AP評價指標下的分類性能比較

表7 各算法在CV評價指標下的分類性能比較

表8 各算法在HL評價指標下的分類性能比較

表9 各算法在OE評價指標下的分類性能比較

表10 各算法在RL評價指標下的分類性能比較

由表6～10發現：

1)MLLAP算法在6個數據集、5個評價指標共30個實驗結果上僅4個實驗數據略差，優勝率達86.66%。其中MLLAP算法完勝PMU、MDDMproj算法，與MLNB、MDDMspc算法相比，在2個數據集上各有2個指標稍差。

2)從平均分類精度來看，MLLAP算法在5個評價指標下均獲得最優，其中AP、CV、HL、OE指標中相比次優的MLNB算法分別高出4.3%、4.7%、1.5%、4.1%，RL指標中相比次優算法MDDMspc勝出5.3%。

上述實驗分析表明MLLAP算法生成的特征重要度排序中前k個特征誘導的分類性能平均上優于MLNB、PMU、MDDMproj及MDDMspc算法。為了更精確地了解MLLAP算法選取重要特征的能力，圖1～5從整體上對比各算法的分類性能隨選取特征數目的變化而變化的情況。

從圖1～5可以發現：

1)從圖1中AP指標、圖2中CV指標，圖5中RL指標來看，MLLAP算法的分類精度曲線走勢清晰地、顯著性地優于MLNB、MDDMproj及MDDMspc算法，與PMU算法相比，僅在Education數據集上對初始特征的選取略差，但特征選取達100左右時MLLAP算法的優勢立即體現出來。說明隨著特征的選取加入，MLLAP算法獲得的重要特征能力比其他4個算法強，能以合理或相同數量的特征就達到較好的分類性能。

2)從圖3中HL指標和圖4中OE指標來看，在Recreation、Science和Society數據集上MLLAP算法的分類精度曲線走勢整體上依然優于MLNB、MDDMproj、MDDMspc及PMU算法。對Arts和Education數據集來看，MLLAP算法的走勢圖與PMU算法在特征選取的初步不期伯仲，但在特征數量達到一定程度時，MLLAP算法的性能即體現出來。對Entertainment數據集來看，在OE指標下當特征數在200以內時,MLLAP算法明顯優勝于其他4個對比算法，但隨著特征數的增加，MLLAP算法與其他算法走勢曲線交融，因而也解釋了表4中MLLAP算法沒有最優的原因。

圖1 在評價指標平均查準率下各算法對數據集的分類性能趨勢

3)以圖1～5的Recreation數據集來看，MLLAP算法的走勢圖在各評價指標下以極少的特征數量就達到相當好的分類性能，但隨著選取特征的增加，分類性能相比自身出現回落，以MLNB算法選取的特征數為目標時，MLNB算法和MDDMspc算法的走勢圖出現重疊，從而不分伯仲，由此也解釋了表3～6中MLLAP算法在Recreation數據集上沒有最優的原因。

4)從圖1～5整體來看，MLLAP算法所選取的特征重要度排序是有效的，該算法能以較少的合理的特征數就達到很好的穩定的分類性能。

圖2 在評價指標覆蓋范圍下各算法對數據集的分類性能趨勢

圖3 在評價指標海明損失下各算法對數據集的分類性能趨勢

通過對比各個算法的k個特征誘導出來的分類精度及分類精度隨特征數增加而變化的情況，說明了MLLAP算法的有效性。為了更進一步突出MLLAP算法相比其他4個算法的優勢，本文先假設5個對比算法在5個評價指標下都性能相等，采用顯著性水平0.1的Friedman test[19]進行檢驗，經檢驗都拒絕了該假設，即5個對比算法在5個評價指標下是存在性能差異的。因此，進一步采用顯著性水平為0.1的Bonferroni-Dunn test[20]來分析具體差異情況，觀察本文MLLAP算法與其他MLNB、PMU、MDDMproj及MDDMspc算法在6個數據集上的平均排序是否高于臨界差(Critical Difference, CD)，若高于則認為MLLAP算法與其他算法之間有差異。

表11給出了5個算法在5個評價指標下的平均排序值。

表11 5個對比算法在5個評價指標下的平均排序

圖4 在評價指標單錯誤下各算法對數據集的分類性能趨勢

圖5 在評價指標排位損失下各算法對數據集的分類性能趨勢

從圖6發現：MLLAP算法在AP、HL和OE指標下與算法MLNB相當，比PMU、MDDMspc和MDDMproj算法存在顯著性優異；在CV和RL評價指標下，與算法PMU和MDDMspc性能相當，比MLNB和MDDMproj算法性能顯著提高；在5個評價指標下，MLLAP算法都優于MDDMproj算法。

總體來說，MLLAP算法性能最好，在5個評價指標下不僅平均分類性能最優，而且與其他4個對比算法存在顯著性優異達65%。

圖6 在5個評價指標下各算法的性能差異

4 結語

傳統拉普拉斯評分特征選擇算法只適應單標記學習任務，本文在多標記學習中考慮樣本之間與多個標記共同關聯和共同不關聯的關系構建樣本在整體標記空間的相似度矩陣，從而實現拉普拉斯評分算法在多標記數據集上的特征選擇，同時在傳統拉普拉斯評分的基礎上考慮了特征間的相關性及冗余性。本文算法直接關注傳統拉普拉斯評分算法在多標記學習中如何構建有效的樣本相似度矩陣，并未考慮多標記數據集中標記間的相關性，也未進一步探索所選特征具體由哪些類別標記決定，未來將致力于研究類屬屬性。