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

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

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

1 引言

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

在許多實(shí)際應(yīng)用中，多標(biāo)簽數(shù)據(jù)通常具有成千上萬的特征，其中許多特征對(duì)于給定的學(xué)習(xí)任務(wù)而言是多余的或無關(guān)緊要的，并且高維數(shù)據(jù)可能會(huì)給學(xué)習(xí)算法帶來很多問題，例如計(jì)算量大、擬合過度和性能差等。因此，需要進(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]對(duì)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)簽的功能和局部成對(duì)標(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)簽的特征選擇的重要度。除此之外，度量特征重要度的方法還有許多，比如模糊粗糙集運(yùn)用模糊熵來進(jìn)行度量，鄰域粗糙集借助鄰域粒來進(jìn)行度量[17]。為了有效減少動(dòng)態(tài)數(shù)據(jù)中的冗余計(jì)算，有效利用之前所獲得的有用信息，Liu等人[17]在鄰域粗糙集模型的基礎(chǔ)上，通過在線流特征選擇算法來處理特征動(dòng)態(tài)增加的多標(biāo)簽數(shù)據(jù)。Qian等人[18]在鄰域粗糙集模型基礎(chǔ)上，提出了一種基于標(biāo)簽分布和特征互補(bǔ)的多標(biāo)簽特征選擇算法。Sun等人[19]針對(duì)多標(biāo)簽鄰域決策系統(tǒng)，提出了一種基于二值粒子群算法和基于勒貝格測度的多標(biāo)簽特征選擇方法。Qian等人[20]提出了一種基于互信息和標(biāo)簽增強(qiáng)的標(biāo)簽分布特征選擇算法。Liu等人[21]提出了一種新的流標(biāo)簽環(huán)境下的多標(biāo)簽特征選擇算法。

上述特征選擇算法均未充分考慮標(biāo)簽之間的關(guān)系，針對(duì)這一問題，本文設(shè)計(jì)了一種基于標(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ù)計(jì)算樣本在標(biāo)簽集下的相似度，進(jìn)而構(gòu)造樣本關(guān)于標(biāo)簽集的模糊關(guān)系；

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

2 基本概念

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

給定一個(gè)多標(biāo)簽決策系統(tǒng)ML={U,A,L}，其中U={x1,x2,…,xn}為有n個(gè)樣本的非空集合，A={a1,a2,…,am}為有m個(gè)特征的特征集，L={l1,l2,…,lk}為有k個(gè)標(biāo)簽的標(biāo)簽集。每個(gè)樣本都有標(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í)一個(gè)函數(shù)Z:U→2L。

例如：表1是一個(gè)含有5個(gè)樣本、3個(gè)標(biāo)簽和3個(gè)特征的多標(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ù)集中的樣本可以有不止一個(gè)標(biāo)簽，這就使得多標(biāo)簽學(xué)習(xí)任務(wù)更加困難。

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

2.2 模糊熵和模糊互信息

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

(1)

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

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

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

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

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

給定一個(gè)任意的樣本集合U,R是定義在U上的一個(gè)模糊等價(jià)關(guān)系,對(duì)于?x,y∈U，關(guān)于等價(jià)關(guān)系的運(yù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)于模糊等價(jià)關(guān)系R的模糊等價(jià)類定義如式(2)所示：

(2)

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

(3)

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

(4)

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

(5)

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

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

(6)

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

定義5令A(yù)1和A2為A的2個(gè)子集，則A1和A2的模糊互信息計(jì)算公式如式(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)系的樣本相似性

對(duì)于某個(gè)樣本，2個(gè)標(biāo)簽同時(shí)出現(xiàn)或者同時(shí)不出現(xiàn)的次數(shù)可以說明這2個(gè)標(biāo)簽之間存在某種潛在聯(lián)系，在本文中，稱之為標(biāo)簽的共現(xiàn)度。由于在多標(biāo)簽數(shù)據(jù)中，許多標(biāo)簽都只是出現(xiàn)在少數(shù)樣本上，因此對(duì)于某個(gè)特定的樣本，2個(gè)標(biāo)簽同時(shí)不出現(xiàn)的次數(shù)遠(yuǎn)大于2個(gè)標(biāo)簽同時(shí)出現(xiàn)的次數(shù)，如果直接利用二者之和評(píng)價(jià)標(biāo)簽的共現(xiàn)度，將會(huì)導(dǎo)致2個(gè)標(biāo)簽同時(shí)出現(xiàn)的次數(shù)對(duì)共現(xiàn)度的影響很小。為此，需要一個(gè)參數(shù)α協(xié)調(diào)2個(gè)標(biāo)簽同時(shí)出現(xiàn)的次數(shù)與2個(gè)標(biāo)簽同時(shí)不出現(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個(gè)步驟：

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

(13)

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

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

(14)

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

(15)

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

式(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個(gè)樣本的非空集合U,m個(gè)特征的特征集A,k個(gè)標(biāo)簽的標(biāo)簽集L*/

輸出：特征集合S。

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

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

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

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

步驟5 whileA≠?do

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

步驟7S=S∪{a}；

步驟8A=A-{a}；

步驟9k=k+1;

步驟10 endwhile

步驟11 returnS。

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

4 實(shí)驗(yàn)分析

本節(jié)將通過實(shí)驗(yàn)來驗(yàn)證所提出算法LC-FS的性能。將多標(biāo)簽數(shù)據(jù)集網(wǎng)站MULAN(http://mulan.sourceforge.net)中的5個(gè)數(shù)據(jù)集(如表2所示)作為實(shí)驗(yàn)數(shù)據(jù)集。在實(shí)驗(yàn)中，將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]作為對(duì)比算法。MDMR和PMU算法中特征的評(píng)價(jià)函數(shù)都是采用香農(nóng)熵度量，MLDFC算法中特征的評(píng)價(jià)函數(shù)采用鄰域熵度量。本文算法基于標(biāo)簽共現(xiàn)關(guān)系來計(jì)算標(biāo)簽重要度時(shí)采用了模糊熵的方法。

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

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

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

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

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

(16)

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

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

(17)

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

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

(18)

其中,⊕表示異或操作。

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

(19)

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

4.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

5 結(jié)束語

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