鄭 海 錢 萌

（1.安慶師范大學(xué)計(jì)算機(jī)與信息學(xué)院；2.安徽省高校智能感知與計(jì)算重點(diǎn)實(shí)驗(yàn)室 安徽安慶 246011）

一、引言

近年來，多標(biāo)記學(xué)習(xí)得到了廣泛的關(guān)注。傳統(tǒng)監(jiān)督學(xué)習(xí)基本都是處理二分類問題，然而，在現(xiàn)實(shí)生活中，樣本往往具有多義性，樣本不僅由一組特征向量描述，同時(shí)還與多個(gè)標(biāo)記類別相關(guān)，多標(biāo)記學(xué)習(xí)框架[1]應(yīng)運(yùn)而生，且應(yīng)用到了文本分類[2]和圖像識(shí)別[3,4,5]等多個(gè)領(lǐng)域。例如，一幅有關(guān)動(dòng)物的圖片中，可能同時(shí)有“狗”“骨頭”“草坪”等標(biāo)記。

多標(biāo)記數(shù)據(jù)的高維性易造成維度災(zāi)難[6,7]，維度災(zāi)難可能會(huì)導(dǎo)致算法運(yùn)行時(shí)間長(zhǎng)，分類精度低等問題。特征提取和特征選擇是解決高維度問題的兩種有效方式。特征選擇[8,9]是根據(jù)某些準(zhǔn)則在原始特征空間選取一組重要的特征子集，并根據(jù)特征子集對(duì)未知樣本進(jìn)行標(biāo)記預(yù)測(cè)。例如Lee等[10]提出了基于多變量互信息的多標(biāo)記特征選擇算法（PMU），該算法利用信息熵度量特征對(duì)標(biāo)記空間的重要程度。Lin等[11]提出了基于鄰域互信息的多標(biāo)記特征選擇(MFNMI)，該算法為避免傳統(tǒng)信息熵計(jì)算混合數(shù)據(jù)時(shí)造成信息損失，提出了鄰域信息熵概念，并以此度量特征對(duì)標(biāo)記空間的重要度。

然而，上述多標(biāo)記特征選擇算法在選擇特征子集時(shí)，都未考慮標(biāo)記對(duì)樣本的區(qū)分度。不同標(biāo)記對(duì)樣本的區(qū)分度是不同的，因此，考慮標(biāo)記對(duì)樣本的區(qū)分度可能有利于提高多標(biāo)記學(xué)習(xí)。例如，林夢(mèng)雷[12]等提出的基于標(biāo)記權(quán)重的多標(biāo)記特征選擇算法，該算法首先利用樣本在整個(gè)特征空間的分類間隔對(duì)標(biāo)記進(jìn)行加權(quán)，然后在整個(gè)標(biāo)記集合下，特征對(duì)樣本的可分性為特征賦予權(quán)重，根據(jù)該權(quán)重衡量特征對(duì)標(biāo)記集合的重要程度。魏葆雅[13]等提出基于標(biāo)記重要性的多標(biāo)記特征選擇算法，該算法首先用核函數(shù)將特征空間映射到一個(gè)更高維的特征空間，在這個(gè)更高維的特征空間中，特征具有可分性，且利用標(biāo)記對(duì)樣本的可分性對(duì)標(biāo)記賦權(quán)值；然后，在新映射的特征空間中計(jì)算樣本的分類間隔，并以此作為特征權(quán)重度量特征的重要程度。以上這些算法的實(shí)驗(yàn)結(jié)果表明在考慮標(biāo)記重要度時(shí)，其分類性能有所提高。

另外，核函數(shù)是一種能有效解決解決在高維空間運(yùn)算時(shí)遇到的維數(shù)災(zāi)難問題的方法，其核心思想是對(duì)原始數(shù)據(jù)通過某種非線性映射嵌入到更高維的特征空間中，在這個(gè)新的特征空間中根據(jù)某個(gè)線性分類器將特征區(qū)分開，核函數(shù)能夠簡(jiǎn)化運(yùn)算，有效解決非線性問題和高維數(shù)災(zāi)難等問題。為此，本文提出了一種基于核函數(shù)和標(biāo)記權(quán)重的多標(biāo)記特征選擇算法，首先，針對(duì)標(biāo)記空間中的所有標(biāo)記，分別統(tǒng)計(jì)貼有不同標(biāo)記的樣本數(shù)量。若對(duì)于某個(gè)標(biāo)記，貼有該標(biāo)記的樣本數(shù)量明顯高于含有其他標(biāo)記的樣本數(shù)量，則表明該標(biāo)記的權(quán)重越大。然后，用RFB核函數(shù)[14]將特征空間映射到一個(gè)更高維的特征空間，在這個(gè)新的特征空間中，計(jì)算特征與標(biāo)記空間之間的互信息，根據(jù)計(jì)算所得的信息熵值對(duì)特征進(jìn)行排序。最后，在多個(gè)多標(biāo)記數(shù)據(jù)集上進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明該算法是有效的。

二、相關(guān)知識(shí)

定義1[15]隨機(jī)變量X={x1,x2,...,xq}，隨機(jī)變量X的不確定期望為，隨機(jī)變量X的信息熵為

H(X)是隨機(jī)變量的信息熵，信息熵是度量隨機(jī)變量不確定性的程度，隨機(jī)變量不確定性程度越大則信息熵值就會(huì)越大。

定義2[15]隨機(jī)變量X={x1,x2,...,xq}，Y={y1,y2,...yn}，變量X和Y之間的互信息定義為：

I(X;Y)是用于衡量變量X和Y之間的相關(guān)性，若I(X;Y)=0，則表示變量X和Y相互獨(dú)立，I(X;Y)數(shù)值越大則表示兩者之間的相關(guān)性越強(qiáng)。另外，I(X;Y)還滿足下式：

三、基于核函數(shù)和標(biāo)記權(quán)重的特征選擇模型

（一）RBF核函數(shù)。在實(shí)際情況中，分類函數(shù)是非線性的，無法將原始特征空間中的數(shù)據(jù)集進(jìn)行區(qū)分開。因此，通常需要用一種非線性映射的方法將原始特征空間映射到高維空間中,使得特征在高維空間中線性可分。

假設(shè)f∈Rm經(jīng)過非線性函數(shù)φ(f)轉(zhuǎn)化為φ(fi)∈Rd,d>m，其中，fi所屬的m維空間為變換前的特征空間，φ(fi)為變換后的特征空間。假設(shè)算法中的各矢量間的相互作用在高維空間中進(jìn)行內(nèi)積運(yùn)算，可能由于維數(shù)過高導(dǎo)致無法得出計(jì)算結(jié)果。為解決該問題，只需找到一個(gè)合適的函數(shù)，使其滿足K(xi,yj)=φ(xi)·φ(yj)，這就可以用原空間中的內(nèi)積函數(shù)進(jìn)行高維度的內(nèi)積運(yùn)算。這就避免了維度災(zāi)難帶來的計(jì)算難題，還能使得特征空間中的特征變得可分。核函數(shù)就是這一思想的體現(xiàn)。在本文算法中，是利用徑向基核函數(shù)（RBF）核函數(shù)對(duì)特征空間進(jìn)行處理，接下來將介紹RBF核函數(shù)：

徑向基核函數(shù)（RBF）：

RBF核函數(shù)可以將特征空間映射到更高維的特征空間中，另外，函數(shù)的復(fù)雜程度直接受核函數(shù)參數(shù)的個(gè)數(shù)的影響，而RBF所需的參數(shù)個(gè)數(shù)少。而且RBF核函數(shù)具有局部性核函數(shù)的學(xué)習(xí)能力[16,17]。因此，本文利用RBF核函數(shù)對(duì)特征空間進(jìn)行處理。

（二）標(biāo)記權(quán)重。在已有的多標(biāo)記特征選擇算法表明考慮標(biāo)記空間隱藏的信息能有效提高多標(biāo)記學(xué)習(xí)精度。每個(gè)標(biāo)記對(duì)樣本的重要性都不同，為此，在本文算法中，根據(jù)每個(gè)標(biāo)記下所含該標(biāo)記的樣本數(shù)量對(duì)標(biāo)記進(jìn)行賦予權(quán)重。

給定樣本X={x1,x2,...,xq}，標(biāo)記空間L={y1,y2,...ym}，對(duì)于標(biāo)記yi的權(quán)重計(jì)算如下：

式（5）中，q表示樣本大小，計(jì)算每個(gè)標(biāo)記下含有該標(biāo)記的樣本數(shù)量所占比例，以此給該標(biāo)記賦予權(quán)重，不含該標(biāo)記的權(quán)重都視為1。

（三）KF-LW模型。在本文所提出的基于核函數(shù)和標(biāo)記權(quán)重的多標(biāo)記特征選擇算法中。首先，針對(duì)每個(gè)標(biāo)記，統(tǒng)計(jì)含有每個(gè)標(biāo)記的樣本數(shù)量，對(duì)標(biāo)記進(jìn)行賦權(quán)重；然后，用RFB核函數(shù)將特征空間映射到一個(gè)更高維的特征空間，在這個(gè)新的特征空間中，計(jì)算特征與標(biāo)記空間之間的互信息，根據(jù)計(jì)算所得的信息熵值對(duì)特征進(jìn)行排序；最后，選取特征總數(shù)的百分之二十的數(shù)量構(gòu)成最終特征子集。

根據(jù)上述描述，基于核函數(shù)和標(biāo)記權(quán)重的多標(biāo)記特征選擇算法(Multi-feature selection based on kernel function and label weighting)描述如下：

A l g o r i t h m：K F-L W輸入:X:樣本集;特征集合：F={f 1 },f 2,...,f m，標(biāo)記空間：Y={y 1,y 2,...y n}，k k：特征子集大小輸出S:已選特征子集1)2)3)4)5)6)7)8)9)1 0)1 1)S=?；重復(fù);f o r i=1:n統(tǒng)計(jì)每個(gè)標(biāo)記下，含有該標(biāo)記的樣本數(shù)量；根據(jù)式（5）計(jì)算每個(gè)標(biāo)記賦權(quán)重；e n d根據(jù)式（4）將原始特征空間映射到高維空間中；f o r i=1:m根據(jù)式（3）計(jì)算特征與標(biāo)記空間之間的互信息；e n d根據(jù)互信息值對(duì)特征進(jìn)行排序；選取前k k個(gè)特征作為最終的特征子集

四、實(shí)驗(yàn)結(jié)果及分析

（一）實(shí)驗(yàn)數(shù)據(jù)集。為了驗(yàn)證KF-LW算法的有效性，本文選取了6個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證，所有數(shù)據(jù)集均能從http://mulan.sourceforge.net/datasets.html.下載，表1為各數(shù)據(jù)集的詳細(xì)信息。

表1 多標(biāo)記數(shù)據(jù)集

（二）實(shí)驗(yàn)結(jié)果及分析。本文的實(shí)驗(yàn)是分別選取了KELM和MLKELM作為分類器，正則化系數(shù)為1，核函數(shù)選擇RBF。本文選擇 One Error(OE),Coverage(CV)，Ranking Loss(RL)和Average Precision(AP)這4個(gè)評(píng)價(jià)指標(biāo)[11]檢測(cè)分類性能。對(duì)比算法有基于多變量互信息的多標(biāo)記特征選擇算法（PMU）、基于最大相關(guān)性降低多標(biāo)記維度（MDDMopt，MDDMproj）[16]。實(shí)驗(yàn)對(duì)比過程中，對(duì)比算法與本文算法均采取相同分類器。所有算法都選取特征總數(shù)的20%作為最終特征子集數(shù)。表中↑表示指標(biāo)數(shù)值越大越好，↓表示指標(biāo)數(shù)值越小越好，黑體字表示各數(shù)據(jù)集在各個(gè)算法上取得的最好結(jié)果，各實(shí)驗(yàn)結(jié)果后面“（）”內(nèi)的值表示各數(shù)據(jù)集在各算法上的排序。

表2 在平均精度上五個(gè)特征選擇算法的排名

表3 在1-錯(cuò)誤上五個(gè)特征選擇算法的排名

表4 在排位損失上五個(gè)特征選擇算法的排名

表5 在覆蓋率上五個(gè)特征選擇算法的排名

分析實(shí)驗(yàn)結(jié)果可知：

1）表2實(shí)驗(yàn)結(jié)果表明：在6個(gè)數(shù)據(jù)集上，KF-LW在5個(gè)數(shù)據(jù)集上獲得最大Average Precision值，即性能最優(yōu)。在Health數(shù)據(jù)集上，算法MFNMIpes獲得最優(yōu)Average Precision值，KF-LW(KELM)取得的Average Precision值與最優(yōu)僅相差0.0006。在8個(gè)數(shù)據(jù)集上的平均排序結(jié)果可以看出，KF-LW(KELM)排第一。

2）在表3中，本文算法與MFNMIopt、MFNMIpes和PMU這幾個(gè)對(duì)比算法的實(shí)驗(yàn)結(jié)果表明，有4個(gè)數(shù)據(jù)集上KF-LW(KELM)算法的One-Error值都是最小的，這表明算法KF-LW的性能很好，在One-Error指標(biāo)上，KF-LW(KELM)排名第1。

3）從表4所有算法的Ranking Loss值可看出：本文算法KF-LW與幾個(gè)對(duì)比算法相比，在6個(gè)數(shù)據(jù)集上KF-LW取得的Ranking Loss值都最小。其中，KF-LW(KELM)算法在4個(gè)數(shù)據(jù)集上取得最優(yōu)值，KF-LW(MLKELM)算法在2個(gè)數(shù)據(jù)集上取得最優(yōu)值。在6個(gè)數(shù)據(jù)集上的綜合排位中，KF-LW(KELM)排在第1。

4）根據(jù)表5可看出：本文所提的算法KF-LW在6個(gè)數(shù)據(jù)集的 Coverage值最小。在 Artificial、Education、Health 和Business這4數(shù)據(jù)集上，算法KF-LW(MLKELM)的Coverage值均排第一位，在Computer和Science這兩個(gè)數(shù)據(jù)集上，KF-LW(KELM)的Coverage值排在第一位。

5）從以上實(shí)驗(yàn)結(jié)果和算法的排序可看出，本文所提算法在Average Precision、Ranking Loss和Coverage這三個(gè)評(píng)價(jià)指標(biāo)上效果都優(yōu)于對(duì)比算法。綜合排位中，本文算法均排在第一位，這進(jìn)一步表明本文算法的有效性。

五、結(jié)語(yǔ)

本文所提的基于核函數(shù)和標(biāo)記權(quán)重的多標(biāo)記特征選擇算法，利用核函數(shù)將原特征空間映射到高維空間，使得特征具有可分性，并根據(jù)標(biāo)記空間的信息對(duì)標(biāo)記進(jìn)行權(quán)重賦值，最后根據(jù)信息熵度量特征與標(biāo)記空間之間的相關(guān)性，實(shí)驗(yàn)結(jié)果表明KF-LW能有效提高分類器預(yù)測(cè)的分類性能。