基于標(biāo)簽共現(xiàn)關(guān)系的多標(biāo)簽特征選擇*

李雨晨,魏 巍,2,白偉明,王 達(dá)

(1.山西大學(xué)計算機與信息技術(shù)學(xué)院,山西 太原 030006;2.山西大學(xué)計算智能與中文信息處理教育部重點實驗室,山西 太原 030006)

1 引言

在經(jīng)典監(jiān)督學(xué)習(xí)中，每個樣本僅擁有一個標(biāo)簽，但是，在許多實際應(yīng)用中，一個樣本通常同時與多個概念相關(guān)聯(lián)[1,2]。例如，藝術(shù)界報道《冰雪奇緣》電影的新聞可以與藝術(shù)、動畫和電影這3個關(guān)鍵字相關(guān)聯(lián)；一幅關(guān)于小鹿的圖像可以與樹木、小鹿和綠色這3個關(guān)鍵字相關(guān)聯(lián)。由此可知，每個樣本可以擁有多個標(biāo)簽。這類關(guān)于多標(biāo)簽分類任務(wù)的研究正受到越來越多的關(guān)注[3 - 7]。

在許多實際應(yīng)用中，多標(biāo)簽數(shù)據(jù)通常具有成千上萬的特征，其中許多特征對于給定的學(xué)習(xí)任務(wù)而言是多余的或無關(guān)緊要的，并且高維數(shù)據(jù)可能會給學(xué)習(xí)算法帶來很多問題，例如計算量大、擬合過度和性能差等。因此，需要進(jìn)行特征選擇，以減輕維數(shù)的困擾[8]。

目前，多標(biāo)簽特征選擇已經(jīng)有了許多研究。Zhang等人[9]利用基于主成分分析的特征提取技術(shù)去除多標(biāo)記數(shù)據(jù)中的不相關(guān)和冗余特征，然后利用遺傳算法進(jìn)行特征選擇。Zhang等人[10]提出了具有標(biāo)簽特定特征的稱為LIFT的多標(biāo)簽學(xué)習(xí)方法。Xu等人[11]對LIFT進(jìn)行改進(jìn)，通過與模糊粗糙集結(jié)合構(gòu)造了多標(biāo)簽學(xué)習(xí)方法FRS-LIFT。后來，Weng等人[12]提出了一種稱為LF-LPLC(multi-label learning based on Label-specific Features and Local Pairwise Label Correlation)的多標(biāo)簽學(xué)習(xí)新方法，該方法主要關(guān)注了標(biāo)簽的功能和局部成對標(biāo)簽相關(guān)性。Kashef等人[13]借助Pareto優(yōu)勢概念從多目標(biāo)優(yōu)化域中選擇最顯著的特征。

近年許多研究人員將粗糙集理論[14]用于多標(biāo)簽學(xué)習(xí)[15]。Lee等人[16]基于互信息提出了適合多標(biāo)簽數(shù)據(jù)的方法，即通過信息增益的方法來度量多標(biāo)簽的特征選擇的重要度。除此之外，度量特征重要度的方法還有許多，比如模糊粗糙集運用模糊熵來進(jìn)行度量，鄰域粗糙集借助鄰域粒來進(jìn)行度量[17]。為了有效減少動態(tài)數(shù)據(jù)中的冗余計算，有效利用之前所獲得的有用信息，Liu等人[17]在鄰域粗糙集模型的基礎(chǔ)上，通過在線流特征選擇算法來處理特征動態(tài)增加的多標(biāo)簽數(shù)據(jù)。Qian等人[18]在鄰域粗糙集模型基礎(chǔ)上，提出了一種基于標(biāo)簽分布和特征互補的多標(biāo)簽特征選擇算法。Sun等人[19]針對多標(biāo)簽鄰域決策系統(tǒng)，提出了一種基于二值粒子群算法和基于勒貝格測度的多標(biāo)簽特征選擇方法。Qian等人[20]提出了一種基于互信息和標(biāo)簽增強的標(biāo)簽分布特征選擇算法。Liu等人[21]提出了一種新的流標(biāo)簽環(huán)境下的多標(biāo)簽特征選擇算法。

上述特征選擇算法均未充分考慮標(biāo)簽之間的關(guān)系，針對這一問題，本文設(shè)計了一種基于標(biāo)簽共現(xiàn)關(guān)系的多標(biāo)簽特征選擇LC-FS(multi-label Feature Selection based on Label Co-occurrence relationship)算法，主要工作如下所示：

(1)根據(jù)樣本標(biāo)簽集中標(biāo)簽共同出現(xiàn)和互斥出現(xiàn)的次數(shù)計算樣本在標(biāo)簽集下的相似度，進(jìn)而構(gòu)造樣本關(guān)于標(biāo)簽集的模糊關(guān)系；

(2)基于標(biāo)簽與特征最大相關(guān)和特征集最小冗余的原則，設(shè)計基于標(biāo)簽共現(xiàn)度的多標(biāo)簽特征選擇算法。

2 基本概念

2.1 多標(biāo)簽決策系統(tǒng)

給定一個多標(biāo)簽決策系統(tǒng)ML={U,A,L}，其中U={x1,x2,…,xn}為有n個樣本的非空集合，A={a1,a2,…,am}為有m個特征的特征集，L={l1,l2,…,lk}為有k個標(biāo)簽的標(biāo)簽集。每個樣本都有標(biāo)簽，因此都屬于L的子集，該子集可以描述為k維向量y=[y1,y2,…,yk]，其中yi=1表示樣本x含有標(biāo)簽li,yi=0表示樣本x不含有標(biāo)簽li，多標(biāo)簽學(xué)習(xí)的任務(wù)是學(xué)習(xí)一個函數(shù)Z:U→2L。

例如：表1是一個含有5個樣本、3個標(biāo)簽和3個特征的多標(biāo)簽數(shù)據(jù)集，x2={3.4,2.6,4.8,1,1,0}，說明樣本x2含有標(biāo)簽l1和l2，但是不含有l(wèi)3。由此可以看出，多標(biāo)簽數(shù)據(jù)集中的樣本可以有不止一個標(biāo)簽，這就使得多標(biāo)簽學(xué)習(xí)任務(wù)更加困難。

Table 1 A multi-label data set表1 一個多標(biāo)簽數(shù)據(jù)集

2.2 模糊熵和模糊互信息

對于一個非空的有限樣本集U={x1,x2,…,xn}，特征集合為A={a1,a2,…,am},R是定義在U上的一個模糊等價關(guān)系，模糊關(guān)系矩陣M(R)定義如式(1)所示：

(1)

其中，rij∈[0,1]表示xi和xj之間的關(guān)系值，其同樣可以記作R(xi,xj),xi,xj∈U。

模糊等價關(guān)系R滿足以下關(guān)系：

自反性：R(x,x)=1,?x∈U;

對稱性：R(x,y)=R(y,x),?x,y∈U;

傳遞性：R(x,z)≥miny{R(x,y),R(y,z)}。

給定一個任意的樣本集合U,R是定義在U上的一個模糊等價關(guān)系,對于?x,y∈U，關(guān)于等價關(guān)系的運算如下所示：

(1)R1=R2?R1(x,y)=R2(x,y);

(2)R=R1∪R2?R(x,y)=max{R1(x,y),R2(x,y)};

(3)R=R1∩R2?R(x,y)=min{R1(x,y),R2(x,y)};

(4)R1?R2?R1(x,y)≤R2(x,y)。

定義1樣本xi關(guān)于模糊等價關(guān)系R的模糊等價類定義如式(2)所示：

(2)

模糊等價類的基數(shù)可表示為：

(3)

定義2[22]給定近似空間〈U,R〉,A的模糊熵定義如式(4)所示：

(4)

定義3令A(yù)1和A2為A的2個子集，則模糊聯(lián)合熵的計算公式如式(5)所示：

(5)

其中,[xi]A1∩[xi]A2=min{[xi]A1,[xi]A2}。

定義4令A(yù)1和A2為A的2個子集，則模糊條件熵的計算公式如式(6)所示：

(6)

其中,FH(A2|A1)=FH(A1,A2)-FH(A1)。

定義5令A(yù)1和A2為A的2個子集，則A1和A2的模糊互信息計算公式如式(7)所示：

(7)

其中,FMI(A1;A2)=FH(A1)-FH(A1|A2)=FH(A2)-FH(A2|A1)。

3 基于標(biāo)簽共現(xiàn)關(guān)系的多標(biāo)簽特征選擇

3.1 基于標(biāo)簽共現(xiàn)關(guān)系的樣本相似性

對于某個樣本，2個標(biāo)簽同時出現(xiàn)或者同時不出現(xiàn)的次數(shù)可以說明這2個標(biāo)簽之間存在某種潛在聯(lián)系，在本文中，稱之為標(biāo)簽的共現(xiàn)度。由于在多標(biāo)簽數(shù)據(jù)中，許多標(biāo)簽都只是出現(xiàn)在少數(shù)樣本上，因此對于某個特定的樣本，2個標(biāo)簽同時不出現(xiàn)的次數(shù)遠(yuǎn)大于2個標(biāo)簽同時出現(xiàn)的次數(shù)，如果直接利用二者之和評價標(biāo)簽的共現(xiàn)度，將會導(dǎo)致2個標(biāo)簽同時出現(xiàn)的次數(shù)對共現(xiàn)度的影響很小。為此，需要一個參數(shù)α協(xié)調(diào)2個標(biāo)簽同時出現(xiàn)的次數(shù)與2個標(biāo)簽同時不出現(xiàn)的次數(shù)之間的關(guān)系。根據(jù)上述分析，給出標(biāo)簽共現(xiàn)度的定義。

定義6給定多標(biāo)簽決策系統(tǒng)ML={U,A,L}，標(biāo)簽li和lj的共現(xiàn)度定義如式(9)所示：

(8)

根據(jù)定義6，進(jìn)一步給出標(biāo)簽的重要度。

定義7給定多標(biāo)簽決策系統(tǒng)ML={U,A,L}，標(biāo)簽的重要度如式(9)所示：

(9)

定義8給定多標(biāo)簽決策系統(tǒng)ML={U,A,L}，樣本的相似性如式(10)所示：

(10)

其中，L(xi)表示樣本xi的標(biāo)簽集合。

將基于標(biāo)簽集的樣本相似性代入模糊粗糙集模型，可以得到特征與特征之間的相關(guān)性以及特征與標(biāo)簽集之間的相關(guān)性,如式(11)和式(12)所示：

(11)

(12)

3.2 基于最大相關(guān)最小冗余原則的特征選擇

本節(jié)將基于特征與標(biāo)簽最大相關(guān)、特征最小冗余的原則，給出面向多標(biāo)簽決策系統(tǒng)的基于最大相關(guān)最小冗余原則的多標(biāo)簽特征選擇算法。該算法主要包含2個步驟：

第1步，選擇與標(biāo)簽集具有最大相關(guān)性的候選特征。令S為已經(jīng)選擇的特征集，L為標(biāo)簽集，則特征集與標(biāo)簽集的相關(guān)性定義如式(13)所示：

(13)

根據(jù)式(13)容易得到，對于單個特征ai，其關(guān)于標(biāo)簽集的相關(guān)性為D(ai,L)=FMI(ai;L)。

第2步，選擇冗余度最小的特征子集。與標(biāo)簽集相關(guān)性最大的特征子集中可能會包括冗余特征(新選擇的特征ai與已選擇特征集中的某些特征之間有強相關(guān)性，或者與已選擇特征集中的某些特征組合后與已選擇特征集中的其他特征具有強相關(guān)性)。為了刻畫特征集中特征的冗余情況，給出特征集S冗余度定義，如式(14)所示：

(14)

結(jié)合了上述2個定義，給出基于最大相關(guān)最小冗余原則的特征選擇的特征評價指標(biāo)，如式(15)所示：

(15)

其中，Sk-1為選擇了k-1個特征的特征集合。

式(15)包含2部分，第1部分表示候選特征aj與標(biāo)簽集L之間的相關(guān)性，第2部分表示候選特征aj與所選特征Sk-1之間的冗余度。

基于標(biāo)簽共現(xiàn)關(guān)系的多標(biāo)簽特征選擇算法的具體描述如算法1所示。

算法1基于標(biāo)簽共現(xiàn)關(guān)系的多標(biāo)簽特征選擇算法(LC-FS)

輸入：多標(biāo)簽決策系統(tǒng)ML={U,A,L};/*包含n個樣本的非空集合U,m個特征的特征集A,k個標(biāo)簽的標(biāo)簽集L*/

輸出：特征集合S。

步驟1初始化S，令S=?,k=1；

步驟2通過式(8)計算標(biāo)簽間的共現(xiàn)度；

步驟3通過式(9)計算標(biāo)簽的重要度；

步驟4通過式(10)計算樣本的相似性；

步驟5 whileA≠?do

步驟6通過式(15)找到a∈A；

步驟7S=S∪{a}；

步驟8A=A-{a}；

步驟9k=k+1;

步驟10 endwhile

步驟11 returnS。

算法1有2個關(guān)鍵步驟。第1個步驟是分別在特征空間和標(biāo)簽空間中構(gòu)造模糊關(guān)系矩陣，時間復(fù)雜度均為O(|U|·|U|)。第2個步驟是搜索特征空間的過程，其時間復(fù)雜度為O(|S|·|A|)，其中，|S|是所選特征的數(shù)量，|A|是候選特征的數(shù)量。因此，該算法的時間復(fù)雜度為O(|U|·|U|+|S|·|A|)。

4 實驗分析

本節(jié)將通過實驗來驗證所提出算法LC-FS的性能。將多標(biāo)簽數(shù)據(jù)集網(wǎng)站MULAN(http://mulan.sourceforge.net)中的5個數(shù)據(jù)集(如表2所示)作為實驗數(shù)據(jù)集。在實驗中，將MLKNN分類器上得到的結(jié)果作為基準(zhǔn)，并將2種代表性算法MDMR(multi-label feature selection based on Max Dependency and Min Redundancy)和PMU[23]以及算法MLDFC(Multi-Label feature selection based on label Distribution and Feature Complementarity)[18]作為對比算法。MDMR和PMU算法中特征的評價函數(shù)都是采用香農(nóng)熵度量，MLDFC算法中特征的評價函數(shù)采用鄰域熵度量。本文算法基于標(biāo)簽共現(xiàn)關(guān)系來計算標(biāo)簽重要度時采用了模糊熵的方法。

Table 2 Multi-label data sets表2 多標(biāo)簽數(shù)據(jù)集

4.1 多標(biāo)簽學(xué)習(xí)評價指標(biāo)

實驗選取了4種常用的多標(biāo)簽性能評價指標(biāo)[24]。設(shè)T={(xi,xj)|1≤i≤N}是一個測試集，其中yi?L是真實標(biāo)簽集合，y′i∈L是學(xué)習(xí)算法的關(guān)于樣本xi的二進(jìn)制標(biāo)簽向量，在以下的公式中n表示樣本的個數(shù)，k表示標(biāo)簽的個數(shù)。

(1)AP(Average Precision)：表示預(yù)測標(biāo)簽集合中標(biāo)簽的排序等級比實際標(biāo)簽集合中某個特定標(biāo)簽更高的概率，也就是預(yù)測標(biāo)簽的平均精度，其計算方式如式(16)所示：

ri(γ)}|)/ri(γ)

(16)

其中,ri(l)代表樣本xi預(yù)測的標(biāo)簽l∈L的等級。

(2)CV(Coverage)：此度量表示覆蓋樣本標(biāo)記的平均距離,其計算方式如式(17)所示：

(17)

其中,rank(λ)表示標(biāo)簽根據(jù)預(yù)測概率的排序序號。例如：若λ1>λ2，則有rank(λ1)

(3)HL(Hamming Loss)：表示沒有被正確預(yù)測的標(biāo)簽比例，即屬于樣本的標(biāo)簽沒有被預(yù)測，不屬于該樣本的標(biāo)簽被預(yù)測的比例,其計算方式如式(18)所示：

(18)

其中,⊕表示異或操作。

(4)RL(Ranking Loss)：評估不相關(guān)標(biāo)簽比相關(guān)標(biāo)簽排序更高的次數(shù),其計算方式如式(19)所示：

(19)

對于以上4種評價指標(biāo)，平均精度(AP)、覆蓋距離(CV)、排序損失(RL)與每個樣本的標(biāo)簽排序性能有關(guān)，而漢明損失(HL)與每個樣本的標(biāo)簽集預(yù)測性能有關(guān)。

4.2 實驗結(jié)果

在實驗中，利用MLKNN分類器的分類結(jié)果，在4個評價指標(biāo)上比較特征選擇算法性能，其中近鄰個數(shù)K設(shè)置為10。在計算標(biāo)簽的共現(xiàn)度時，用到的參數(shù)α=10-t,t的取值為[2,8],t以步長1進(jìn)行遍歷，選取使平均精度最優(yōu)的α。驗證方法是10折交叉驗證法。

實驗結(jié)果如表3～表6所示，“↑”表示越大越好，“↓”表示越小越好，±表示方差，最后一列表示本文算法LC-FS的實驗結(jié)果，其中粗體表示最優(yōu)值，斜體表示次優(yōu)值。圖1為5個算法在不同的數(shù)據(jù)集上的精度對比，橫軸表示所選特征子集中的特征數(shù)量，縱軸表示特征子集對應(yīng)的分類精度值。

Table 3 Comparison of AP of different algorithms(↑)表3 不同算法在平均精度上的比較(↑)

Table 4 Comparison of CV of different algorithms(↓)表4 不同算法在覆蓋距離上的比較(↓)

Table 5 Comparison of HL of different algorithms(↓)表5 不同算法在漢明損失上的比較(↓)

Table 6 Comparison of RL of different algorithms(↓)表6 不同算法在排序損失上的比較(↓)

Figure 1 Comparison of AP of each algorithm on different data sets圖1 各算法在不同數(shù)據(jù)集上的精度對比

從實驗結(jié)果可以看出，本文算法LC-FS在5個數(shù)據(jù)集上的實驗效果都比較好。具體情況如下：

(1)在flags數(shù)據(jù)集上，基于LC-FS算法的特征選擇結(jié)果在3個評價指標(biāo)AP、CV、RL上都是最佳的。

(2)在birds數(shù)據(jù)集上，LC-FS算法有著最高的HL，最低的CV和RL，在AP上僅次于MLKNN。

(3)從評價指標(biāo)AP和CV的角度看，LC-FS算法的性能最好，在3個數(shù)據(jù)集上都得到了最優(yōu)值，還有一個次優(yōu)的結(jié)果。

(4)從評價指標(biāo)RL看，LC-FS算法的性能相對較差，得到了2個最優(yōu)的結(jié)果，不過RL值與最優(yōu)值差距也均在0.01內(nèi)，差距并不大。

綜上所述，LC-FS算法在上述對比指標(biāo)下均有不錯的表現(xiàn)。

5 結(jié)束語

本文提出了基于標(biāo)簽共現(xiàn)關(guān)系的多標(biāo)簽特征選擇算法LC-FS。在該算法中，首先通過標(biāo)簽的共現(xiàn)度評價標(biāo)簽的權(quán)重，進(jìn)而得到樣本在標(biāo)簽集下的相似性，然后基于模糊粗糙集模型計算特征與標(biāo)簽的相關(guān)性、特征集的冗余性，并利用最大相關(guān)最小冗余原則實現(xiàn)特征選擇。實驗結(jié)果驗證了本文算法的有效性。