胡敏杰，林耀進(jìn),王晨曦，唐 莉，鄭荔平

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

0 引言

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

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

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

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

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

第一步 構(gòu)建近鄰無(wú)向有權(quán)圖G(V,E)。各樣本作為節(jié)點(diǎn)表示圖節(jié)點(diǎn)集V，樣本間的近鄰關(guān)系表示圖中的邊形成邊集E。如果樣本xi是樣本xi′的最近鄰的k個(gè)樣本之一或xi′是xi最近鄰的k個(gè)樣本之一，則xi與xi′節(jié)點(diǎn)相連成邊。

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

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

(1)

2)對(duì)具有單一標(biāo)記的數(shù)據(jù)，常根據(jù)類(lèi)別個(gè)數(shù)來(lái)構(gòu)建相似矩陣，如式(2):

(2)

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

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

(3)

度矩陣詮釋了每個(gè)樣本周?chē)奂渌麡颖镜拿芗潭?，值越大說(shuō)明與之樣本靠近的其他樣本就越多。由度矩陣和鄰接矩陣得到相應(yīng)的Laplacian矩陣L和正則化的Laplacian矩陣L：

(4)

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

(5)

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

(6)

2 多標(biāo)記的拉普拉斯特征選擇算法

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

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

表1 一個(gè)多標(biāo)記數(shù)據(jù)集例子

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

表2 標(biāo)記y1下樣本的相似度

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

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

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

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

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

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

2.2 基于拉普拉斯評(píng)分的多標(biāo)記特征選擇算法

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

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

(7)

由此相應(yīng)的Laplacian矩陣L′和正則化的Laplacian矩陣L′為：

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

(8)

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

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

(9)

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

2.3 算法步驟

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

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

算法1 MLLAP算法。

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

輸出 特征序列Fs。

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

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

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

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

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

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

3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

3.2 實(shí)驗(yàn)設(shè)置

HL用來(lái)度量樣本在單一標(biāo)記上的錯(cuò)誤分類(lèi)情況，定義為：

其中Zi表示預(yù)測(cè)到的標(biāo)記集。

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

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

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

RL用來(lái)度量錯(cuò)誤標(biāo)記排在正確標(biāo)記之前的比例，定義為：

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

以上5種評(píng)價(jià)指標(biāo)中，AP指標(biāo)取值越大學(xué)習(xí)性能越優(yōu)，最優(yōu)值為1；HL、OE、CV和RL指標(biāo)取值越小越好，最優(yōu)值是0。

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

3.3 實(shí)驗(yàn)結(jié)果與分析

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

表6 各算法在AP評(píng)價(jià)指標(biāo)下的分類(lèi)性能比較

表7 各算法在CV評(píng)價(jià)指標(biāo)下的分類(lèi)性能比較

表8 各算法在HL評(píng)價(jià)指標(biāo)下的分類(lèi)性能比較

表9 各算法在OE評(píng)價(jià)指標(biāo)下的分類(lèi)性能比較

表10 各算法在RL評(píng)價(jià)指標(biāo)下的分類(lèi)性能比較

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

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

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

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

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

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

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

圖1 在評(píng)價(jià)指標(biāo)平均查準(zhǔn)率下各算法對(duì)數(shù)據(jù)集的分類(lèi)性能趨勢(shì)

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

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

圖2 在評(píng)價(jià)指標(biāo)覆蓋范圍下各算法對(duì)數(shù)據(jù)集的分類(lèi)性能趨勢(shì)

圖3 在評(píng)價(jià)指標(biāo)海明損失下各算法對(duì)數(shù)據(jù)集的分類(lèi)性能趨勢(shì)

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

表11給出了5個(gè)算法在5個(gè)評(píng)價(jià)指標(biāo)下的平均排序值。

表11 5個(gè)對(duì)比算法在5個(gè)評(píng)價(jià)指標(biāo)下的平均排序

圖4 在評(píng)價(jià)指標(biāo)單錯(cuò)誤下各算法對(duì)數(shù)據(jù)集的分類(lèi)性能趨勢(shì)

圖5 在評(píng)價(jià)指標(biāo)排位損失下各算法對(duì)數(shù)據(jù)集的分類(lèi)性能趨勢(shì)

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

總體來(lái)說(shuō)，MLLAP算法性能最好，在5個(gè)評(píng)價(jià)指標(biāo)下不僅平均分類(lèi)性能最優(yōu)，而且與其他4個(gè)對(duì)比算法存在顯著性優(yōu)異達(dá)65%。

圖6 在5個(gè)評(píng)價(jià)指標(biāo)下各算法的性能差異

4 結(jié)語(yǔ)

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