基于核函數和標記權重的多標記特征選擇

鄭 海 錢 萌

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

一、引言

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

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

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

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

二、相關知識

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

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

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

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

三、基于核函數和標記權重的特征選擇模型

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

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

徑向基核函數（RBF）：

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

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

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

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

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

根據上述描述，基于核函數和標記權重的多標記特征選擇算法(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，標記空間：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 o r i=1:n統計每個標記下，含有該標記的樣本數量；根據式（5）計算每個標記賦權重；e n d根據式（4）將原始特征空間映射到高維空間中；f o r i=1:m根據式（3）計算特征與標記空間之間的互信息；e n d根據互信息值對特征進行排序；選取前k k個特征作為最終的特征子集

四、實驗結果及分析

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

表1 多標記數據集

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

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

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

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

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

分析實驗結果可知：

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

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

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

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

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

五、結語

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