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

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

0 引言

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

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

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

1 傳統(tǒng)拉普拉斯特征選擇算法

拉普拉斯評分基于拉普拉斯特征映射和局部保持投影理論。假設Fr表示數(shù)據(jù)集中第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òu)建近鄰無向有權(quán)圖G(V,E)。各樣本作為節(jié)點表示圖節(jié)點集V，樣本間的近鄰關(guān)系表示圖中的邊形成邊集E。如果樣本xi是樣本xi′的最近鄰的k個樣本之一或xi′是xi最近鄰的k個樣本之一，則xi與xi′節(jié)點相連成邊。

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

1)不考慮標記信息，通過核函數(shù)構(gòu)造權(quán)重矩陣，如式(1):

(1)

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

(2)

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

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

(3)

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

(4)

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

(5)

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

(6)

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

2.1 樣本相似度的構(gòu)建

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

表1 一個多標記數(shù)據(jù)集例子

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

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

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

表3 Jaccard相關(guān)性下的樣本的相似度

受單標記類標記含義啟發(fā)，樣本x2和樣本x5在單標記y1下屬于0類，在多標記含義下樣本x2和樣本x5都不與y1標記關(guān)聯(lián)。

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

表4 共同關(guān)聯(lián)和共同不關(guān)聯(lián)下的樣本的相似度

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

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

由于傳統(tǒng)的拉普拉斯特征選擇算法只度量單個特征的可分性，而未考慮特征之間的冗余性和相關(guān)性，因此在計算了樣本在多個標記空間的相似度后，在評價特征的可分性上考慮特征之間的相關(guān)性。設多標記訓練集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)標記相關(guān)，則yij=1,否則yij=0。F={f1,f2,…,fn}表示描述樣本的特征向量，fir表示第r(1≤r≤n)特征上第i(1≤i≤m)個樣本的取值。

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

(7)

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

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

(8)

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

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

(9)

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

2.3 算法步驟

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

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

算法1 MLLAP算法。

輸入 多標記數(shù)據(jù)集T；

輸出 特征序列Fs。

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

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

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

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

步驟5 重復步驟4，直到Fu為空結(jié)束。

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

3 實驗設計與結(jié)果分析

3.1 實驗數(shù)據(jù)

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

3.2 實驗設置

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

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

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

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

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

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

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

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

本文選擇其他4個對比算法分別為：使用線性核和非線性核的基于最大依賴的多標記維數(shù)約簡方法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,平滑參數(shù)s=1。

3.3 實驗結(jié)果與分析

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

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

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

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

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

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

由表6～10發(fā)現(xiàn)：

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

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

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

從圖1～5可以發(fā)現(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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