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

鄭 海 錢 萌

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

一、引言

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

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

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

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

二、相關(guān)知識

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

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

定義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相互獨立，I(X;Y)數(shù)值越大則表示兩者之間的相關(guān)性越強(qiáng)。另外，I(X;Y)還滿足下式：

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

（一）RBF核函數(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)致無法得出計算結(jié)果。為解決該問題，只需找到一個合適的函數(shù)，使其滿足K(xi,yj)=φ(xi)·φ(yj)，這就可以用原空間中的內(nèi)積函數(shù)進(jìn)行高維度的內(nèi)積運(yùn)算。這就避免了維度災(zāi)難帶來的計算難題，還能使得特征空間中的特征變得可分。核函數(shù)就是這一思想的體現(xiàn)。在本文算法中，是利用徑向基核函數(shù)（RBF）核函數(shù)對特征空間進(jìn)行處理，接下來將介紹RBF核函數(shù)：

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

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

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

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

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

（三）KF-LW模型。在本文所提出的基于核函數(shù)和標(biāo)記權(quán)重的多標(biāo)記特征選擇算法中。首先，針對每個標(biāo)記，統(tǒng)計含有每個標(biāo)記的樣本數(shù)量，對標(biāo)記進(jìn)行賦權(quán)重；然后，用RFB核函數(shù)將特征空間映射到一個更高維的特征空間，在這個新的特征空間中，計算特征與標(biāo)記空間之間的互信息，根據(jù)計算所得的信息熵值對特征進(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)計每個標(biāo)記下，含有該標(biāo)記的樣本數(shù)量；根據(jù)式（5）計算每個標(biāo)記賦權(quán)重；e n d根據(jù)式（4）將原始特征空間映射到高維空間中；f o r i=1:m根據(jù)式（3）計算特征與標(biāo)記空間之間的互信息；e n d根據(jù)互信息值對特征進(jìn)行排序；選取前k k個特征作為最終的特征子集

四、實驗結(jié)果及分析

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

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

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

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

表3 在1-錯誤上五個特征選擇算法的排名

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

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

分析實驗結(jié)果可知：

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

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

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

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

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

五、結(jié)語

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