粗糙互信息的不平衡多標記特征選擇算法

陳 飛，史金成

（銅陵學院數學與計算機學院，安徽銅陵244061）

多標記學習作為一種流行的機器學習方法，得到了眾多學者的關注與研究[1-3]。現實世界中也有大量多標記對象，例如一副自然風景圖可以標上“藍天”、“白云”、“沙漠”、“小草”等標記，一篇新聞可以屬于“經濟”、“文化”和“政治”等。為了盡可能地對樣本進行準確標記，就需要對大量特征進行描述。大量的特征雖然會提高描述的準確性，但特征的增多會產生冗余特征或者不相關特征，這些特征會降低分類器的精度，增加算法運行時間。因此降低多標記的特征維數有重要的意義[4]。

目前，特征降維大致有兩類方法：特征提取和特征選擇。特征提取方法主要是通過特征之間的映射得到一組新的特征子集，但是在映射過程中會改變原始的特征信息，從而丟失一些原始信息，如線性判別分析[5]、依賴度最大化的多標記維數約簡[6]等。特征選擇方法利用一定的度量關系或評價指標得出一組特征序列或者特征子集，保持了原有特征空間的信息。目前，多數學者利用信息增益（Information Gain,IG）或互信息（Mutual Information,MI）作為評價指標對特征子集進行選擇，并提出了多種行之有效的算法[7-9]。

在多標記學習框架之下，標記并不是均勻分布的，有些標記出現的頻率高，能描述大部分樣本，稱之為高密度標記；有些標記出現的頻率低，只能描述少部分樣本，稱之為低密度標記。這些低密度標記往往是由少數特征所決定的，這些特征可能與標記空間整體的相關性不高，但卻可能是某些低密度標記的關鍵特征，如果僅僅考量與標記空間整體的相關性，那么這些特征會被刪去從而影響分類器的分類精度。若將標記空間進行劃分，考慮部分標記空間甚至單個標記與特征的相關性，無疑會提高算法的有效性。

針對上述問題，本文提出了一種基于粗糙互信息的不平衡多標記特征選擇算法，根據標記密度的高低劃分標記空間，引入模糊熵修正傳統的互信息，并以此來度量特征與標記的相關性，再對不同空間得到的特征序列進行差異性比例的采樣，最終將這些特征作為特征子集進行相關訓練與測試。

1 多標記學習

1.1 多標記學習框架

在多標記學習中，每個實例樣本都同時擁有多個特征和多種標記，學習的目的是將未知的實例對應上盡可能多的正確標記[10]。假設F是由n個特征組成的特征集合F={f1,f2,f3,…,fn}，L是由m個標記組成的標記集合，L={l1,l2,l3,…,lm}，則含有a個樣本的多標記數據集可表示成

1.2 粗糙互信息

定義1[11]設論域U、屬性P對應的劃分為U/P=X={x1,x2,x3,…,xn}，其中xi為等價類，則基于粗糙集等價類所表達的信息量為

其中|*|表示集合元素的基數，并且有0≤I(xi)＜1。

定義2[11]設論域U，屬性P對論域U的劃分為U/P=X={x1,x2,x3,…,xn}，則P的信息熵為

其中c表示求補，并且0≤E(X)＜1-。

定義3[11]設多標記特征空間中某個劃分為X={x1,x2,x3,…,xn}，標記空間中劃分為Y={y1,y2,y3,…,ym}，根據定義1，可得多標記條件下自信息量為

由特征空間和標記空間聯合組成的空間記為

符號集(X,Y)上的條件熵[11]可以定義為

符號集(X,Y)上的每個元素(xi,yj)的聯合熵[11]定義為

符號集(X,Y)上的粗糙互信息定義為

由文獻[12]可知，粗糙互信息、條件熵和自信息量之間存在著如下關系：

進一步地，通過聯合熵能得出如下關系：

式（10）是本文的主要計算公式。

2 粗糙互信息不平衡多標記特征選擇算法

在多標記學習框架之下，標記空間中標記并不是均勻分布的。如果僅僅單一考量與標記空間整體的相關性，那么少數低密度標記的關鍵特征可能會被忽略掉，進而影響分類精度。因此，本文算法將標記空間進行劃分，通過對不同標記空間得到的相關性特征序列進行差異化采樣，并對采樣的特征進行并集運算得出最終的特征子集，以此來進行訓練和測試。在有效降低特征維數的前提下，既保留了對標記空間有著強相關的特征，又提高了分類器精度。具體算法步驟如下。

第一步：劃分空間。根據每個標記出現的頻率從高到低進行排序，前50%的標記劃分為高密度空間，后50%的標記劃分為低密度空間。

第二步：計算相關性。利用式（10）計算每個標記與特征的相關性，得出每個標記相應的特征序列。

第三步：差異化采樣。高密度標記空間中標記取前k1個重要特征，低密度標記空間取前k2個重要特征，k1＞k2。

第四步：對得到的不同特征序列進行并集運算得出最終特征子集。

3 實驗設計與結果分析

3.1 實驗數據集

為了驗證本文算法的有效性，選擇了5個公開數據集進行對比實驗，相關信息如下頁表1所示，實驗數據均來自http：//mulan.sourceforge.net/datasets.html。

3.2 評價指標

本文將平均查準率（AveragePrecision,AP），排位缺失（Ranking Loss,RL），海明缺失（Hamming Loss,HL）和單錯誤（One Error,OE）作為性能評價指標[9]，其中AP值越大表明分類效果越好，RL、HL和OE值則是越小分類效果越好。

3.3 實驗結果分析

實驗采樣3組，采樣數目分別是k1=20、k2=15（第1組），k1=30、k2=15（第2組），k1=30、k2=20（第3組）。在5個數據集上的特征選擇數目見表2，分類器采用ML-kNN[13]。為了證明算法的有效性，對比了MDDM算法[6]（Multi-label Dimensionality Reduction via Dependence Maximization）和PMU算法[14]（Pairwise Multivariate Mutual Information）。MDDM算法根據映射方法又分為MDDMproj算法和MDDMspc算法。由于MDDM和PMU算法是得到一組特征序列，實驗中選取前n個特征作為特征子集，n的取值與k1=30，k2=20特征數目保持一致。分類器ML-kNN的參數值設置為默認參數值。

從表2可以看出，本文算法可以大大減少特征數目，特征選擇后的數目均不到原始特征數目的25%，在Rec數據集上更是減少到了原始的13.2%。

表1 數據集基本信息

表2 FSIM算法不同采樣情況的特征選擇數目

表3列出了在4種不同的評價指標下，不同算法的實驗結果。“↑”表示指標的取值越大越好，“↓”表示指標的取值越小越好，“Average”行數據表示的是每個算法在當前指標下的平均值，“Original”列數據表示未進行特征選擇的實驗結果。

表3 不同算法在四種評價指標上的結果

從表3可以看出，在5個數據集的20個結果中，僅有Computer數據集的OE指標劣于未進行特征選擇的結果，其余均優于原始結果。同時，本文算法在3組實驗中有17個是最優的。在k1=30，k2=20的取值條件下：RL指標中有4個數據集的結果是最優的；在Computer數據集上最優結果也為本算法；AP和HL指標中有3個數據集結果最優；OE指標中，雖然有3個數據集的最優結果不是本文算法，但在Rec和Health數據集中，本文算法在k1=30，k2=20的取值條件下與最優結果的誤差不到4%；在Computer數據集中與最優結果更是僅有1%左右的誤差。以上實驗結果證明了本文算法的有效性。

4 總結

本文提出的基于粗糙互信息的不平衡多標記特征選擇算法，用粗糙互信息代替傳統互信息減少了計算復雜度，同時考慮到標記的不平衡分布對標記空間進行劃分，在不改變標記空間中的標記分布的情況下，對特征進行差異化采樣，保證了每個標記的重要特征不丟失。但算法仍存在問題，采樣數目是人為設定的，后期將考慮如何自適應采樣數目。