基于指數(shù)損失間隔的多標(biāo)記特征選擇算法

李雨婷

(南京郵電大學(xué) 計算機學(xué)院、軟件學(xué)院、網(wǎng)絡(luò)空間安全學(xué)院，江蘇 南京 210023)

0 引 言

多標(biāo)記學(xué)習(xí)的概念來源于文檔分類[1-2]過程中遇到的多語義問題，經(jīng)過了十幾年的發(fā)展，多標(biāo)記學(xué)習(xí)也慢慢成為了國際機器學(xué)習(xí)領(lǐng)域的熱點話題。多標(biāo)記學(xué)習(xí)的研究成果也在實際問題中得到了較好的應(yīng)用，逐漸在圖像分割[3]、圖像標(biāo)注[4]、面部表情識別[5]、動作識別[6]、廣告推薦[7]、文本分類和生物信息學(xué)[8]等領(lǐng)域扮演重要的角色。

在機器學(xué)習(xí)領(lǐng)域，機器學(xué)習(xí)問題通?？煞譃楸O(jiān)督學(xué)習(xí)、無監(jiān)督學(xué)習(xí)[9]。在傳統(tǒng)的監(jiān)督學(xué)習(xí)中，每個樣本與一個標(biāo)記相關(guān)，而在多標(biāo)記學(xué)習(xí)中一個樣本可以有多個標(biāo)記。且標(biāo)記之間存在一定的關(guān)聯(lián)性，如何提取和利用標(biāo)記間的關(guān)聯(lián)性成為提高多標(biāo)記學(xué)習(xí)算法性能的關(guān)鍵。為此，可采用基于指數(shù)損失間隔的多標(biāo)記特征選擇算法進行特征選擇，該算法不僅不依賴于具體的轉(zhuǎn)換策略或分類算法，也可以有效地利用標(biāo)記間的關(guān)聯(lián)信息。

文中首先介紹了多標(biāo)記學(xué)習(xí)和特征選擇算法，以及一種多標(biāo)記數(shù)據(jù)樣本相似性的度量方法；然后提出一種基于指數(shù)損失間隔的多標(biāo)記特征選擇算法。該算法可使用樣本標(biāo)記的關(guān)聯(lián)性使特征空間與標(biāo)記空間的信息結(jié)合在一起，可得到標(biāo)記間的關(guān)聯(lián)信息，也獨立于特定的分類算法或轉(zhuǎn)換策略；最后通過現(xiàn)實世界數(shù)據(jù)集上的相關(guān)實驗及結(jié)果對算法進行驗證。

1 相關(guān)工作

1.1 多標(biāo)記學(xué)習(xí)

目前，根據(jù)多標(biāo)記學(xué)習(xí)算法是否利用標(biāo)簽之間的相關(guān)性，可以分為三個階次：常見的一階算法，如binary relevance，將候選標(biāo)記個數(shù)為Q個的多標(biāo)記問題轉(zhuǎn)變成為Q個獨立的二分類問題，再對每個二分類問題獨立求解。calibrated label ranking[4]是一種二階算法；此外，分類器鏈(classifier chain，CC)[10]算法屬于高階算法，也可用來處理多標(biāo)記問題。

1.2 特征選擇

特征選擇[11-12]是一種數(shù)據(jù)預(yù)處理技術(shù)，常用于去除數(shù)據(jù)中的噪音和冗余特征。相比其他的降維方法，特征選擇不改變數(shù)據(jù)的原有特征，使原始的數(shù)據(jù)特征被保留。

通常將特征選擇方法分為3種模型：封裝器模型、過濾器模型和嵌入式模型[13-14]。常用過濾器模型的特征選擇方法有ReliefF[15]、Fisher Score[16]算法等。這種特征選擇模型，獨立于具體的分類器，所以當(dāng)選擇不同的分類器時也不會對算法的結(jié)果產(chǎn)生影響，因此被廣泛應(yīng)用。封裝器模型直接針對給定的分類器進行優(yōu)化，所以對于不同的分類學(xué)習(xí)算法，其分類性能也有不同的差異，封裝器模型算法也因此受限于所選分類器的性能。而嵌入式模型算法獨立于具體的分類學(xué)習(xí)算法，且其算法計算量比封裝器模型小。

文中所提出的多標(biāo)記特征選擇算法屬于過濾器模型，該算法與具體的轉(zhuǎn)換策略[14]無關(guān)，可通過分類學(xué)習(xí)算法得到若干特征子空間，再根據(jù)分類性能來選擇最優(yōu)的特征子空間作為最終分類結(jié)果。

1.3 多標(biāo)記樣本的相似度

由于在多標(biāo)記學(xué)習(xí)中，不同數(shù)據(jù)集的標(biāo)記之間通常會有不同的關(guān)聯(lián)性，這里通過構(gòu)建概念結(jié)構(gòu)圖的方式去假設(shè)標(biāo)記的結(jié)構(gòu)。在傳統(tǒng)的單標(biāo)記問題中，樣本間的相似度[17-18]可通過式(1)計算：

(1)

其中nl表示屬于類別l的樣本個數(shù)。在多標(biāo)記的學(xué)習(xí)中，同一個樣本有可能屬于多個標(biāo)記，此時不能通過式(1)明確得到兩個樣本所屬的類別。在這里，利用式(2)[19]可以計算兩個多標(biāo)記樣本間的相似性s(i1,i2)，其中nq為與第q個標(biāo)記相關(guān)的樣本個數(shù)，式(2)也可看成是Jaccard[20]的另一種表現(xiàn)形式。數(shù)據(jù)集中不同標(biāo)記出現(xiàn)次數(shù)不相同，通過改變權(quán)重nq表示不同標(biāo)記對樣本相似度的影響。

(2)

如圖1中的上半部分，表示含有ABC三種標(biāo)記的結(jié)構(gòu)圖，圖中的三角形、星形、菱形、正方形表示不同的樣本，用不同的形狀來描述樣本在特征R1上的不同取值情況。與單標(biāo)記問題不同，多標(biāo)記問題中同一個樣本可以同時和多個標(biāo)記相關(guān)聯(lián)，例如圖1上半部分所示，特征R1取值為星形的樣本，既與標(biāo)記A相關(guān)聯(lián)，又與標(biāo)記B相關(guān)聯(lián)。將每種標(biāo)記當(dāng)成一個類別，多標(biāo)記問題變成了多類問題，將圖1上半部分的重疊區(qū)域進行分解，如圖1下半部分所示。

圖1 多標(biāo)記問題的分類

當(dāng)原始問題被轉(zhuǎn)換為二分類問題，如圖1下半部分所示，定義了新的類別D，變成了與A和B完全不同的類別，根據(jù)式(1)可知它們之間的相似度為0，但真實的樣本間相似度并不是0，因此文中所使用的方法對描述樣本間相似度的關(guān)系更有效。

2 基于指數(shù)損失間隔的多標(biāo)記特征選擇

圖2是通過式(2)來構(gòu)建的簡單無向圖，邊距越短，兩個樣本之間的相似度就越大。實心圓形表示樣本xi，空心圓形表示與樣本xi帶有相同標(biāo)記,且兩樣本間的相似度大于閾值smin的樣本，七角星表示與樣本xi的標(biāo)記不同，且樣本間相似度小于閾值smin的樣本。若給出樣本的相似度以及閾值smin，可在圖 2的標(biāo)記空間(a)中找出樣本xi的近鄰樣本，可通過近鄰樣本來預(yù)測樣本的標(biāo)記。

圖2(b)所示的是特征空間，通過特征選擇可以使得樣本間的距離發(fā)生變化，箭頭的方向表示通過特征選擇使樣本間的距離發(fā)生變化的方向。圖2(b)中由七角星到實心圓形的距離可能比空心圓形到實心圓形的距離更近，意味著樣本在特征空間和標(biāo)記空間上分布不一致。

特征空間和標(biāo)記空間的樣本分布不一致的特性，可能會導(dǎo)致樣本的分類錯誤。如果能找到如圖2(c)所示的特征子空間，使得樣本(特征子空間的樣本)在特征空間上的分布與標(biāo)記空間上的分布一致，就可用這部分特征來尋找第i個樣本的近鄰，從而使分類效果更好。

特征子空間的不同會對樣本間的距離產(chǎn)生不同的影響，從而影響損失函數(shù)值，找到合適的特征子空間，可以使損失函數(shù)最小，所以特征選擇的評價準則可以選擇損失函數(shù)來衡量。由此，提出了基于指數(shù)損失分類間隔的多標(biāo)記特征選擇算法。給定樣本(xi,yi)及相似度smin，可定義：

sim(i)={(xi',yi')|s(i,i')≥smin,

1≤i'≤n且i'≠i}

(3)

dissim(i)={(xi',yi')|s(i,i')

1≤i'≤且i'≠i}

(4)

(xi',yi')∈sim(i)

(5)

(xi',yi')∈dissim(i)

(6)

margin(i)=|‖xi-xnearhit(i)‖2-

‖xi-xnearmiss(i)‖2|

(7)

可以按照式(2)和閾值smin，對數(shù)據(jù)集進行劃分，劃分為與樣本xi具有相同標(biāo)記的樣本集合sim(i)和具有不同標(biāo)記的樣本集合dissim(i)，通過特征空間中的歐氏距離，分別在兩集合中找出與樣本xi具有相同類別的最近鄰nearhit(i)和不同類別的最近鄰nearmiss(i)，再通過nearmiss(i)、nearhit(i)來計算分類間隔margin(i)。在此基礎(chǔ)上，用nb(i)(near neighbor)表示xi的目標(biāo)近鄰樣本，并定義損失函數(shù)Lossxi(w)：

(8)

損失函數(shù)的第一項表示的是懲罰與樣本xi相距較遠的樣本，而并不是指所有的與xi具有相同標(biāo)記的樣本，第二項表示的是懲罰與樣本xi的相距較近且與xi標(biāo)記不同的樣本。w為特征的權(quán)重向量，調(diào)節(jié)參數(shù)λ>0，δ(i',j)見式(9)，指數(shù)損失見式(10)：

δ(i',j)=(1-s(i,.j))·EXP(xi)

(9)

EXP(xi)=exp(max(0,margin(i)+

‖wxi-wxi'‖2-‖wxi-wxj‖2))

(10)

在這里關(guān)注的是特殊區(qū)域里被懲罰的樣本且與樣本xi標(biāo)記不相似的樣本。該區(qū)域的樣本與樣本xi的距離小于樣本xi到其任何目標(biāo)近鄰的距離加上margin，對此時的樣本進行懲罰。若訓(xùn)練集中的樣本都有著損失低、分類間隔大的特點，就可以使得算法具有更好的推廣性能。

圖2 比較不同空間中的圖

為使得損失函數(shù)最小，可優(yōu)化函數(shù)式(11)，求得一組最優(yōu)特征權(quán)重w*，使nb(i)中的樣本到xi的距離均小于dissim(i)中的樣本到樣本xi的距離，使標(biāo)記空間中的樣本分布和特征空間一致。w*可以通過梯度下降法求得。具體見算法1。

(11)

(12)

其中，

(13)

‖xdi-xdj‖2)·(exp(margin(i)+‖xi-xi'‖2-‖xi-xj‖2))

(14)

算法1：GMBA_exp。

輸入：梯度下降算法的步長βi，近鄰數(shù)k，訓(xùn)練數(shù)據(jù)集Dtrain，閾值smin，調(diào)諧參數(shù)λ；

輸出：特征權(quán)重w。

1.初始化w=1

2.fori=1 ton：

3.從訓(xùn)練數(shù)據(jù)中得到sim(i)，dissim(i)，

nearhit(i)，nearmiss(i)，計算margin(i)

4.依據(jù)k求nb(i)

5.ford=1 toD：

7.end

8.w=w-(βi)/‖‖，其中βi為步長

9.end

10.輸出w

GMBA[19]算法與GMBA_exp算法，主要差別在于損失函數(shù)的形式上，GMBA[19]算法采用hinge損失[19]函數(shù)的形式。

3 實 驗

在算法的有效性驗證方面，先在數(shù)據(jù)集上將SPEC(spectral feature selection)[14]、GMBA[19](運用hinge損失算法)、GMBA_exp、多標(biāo)記ML_FScore(MLFS)[21]算法和ML_ReliefF(MLRF)[21]算法進行比較，MLFS、MLRF對應(yīng)的是傳統(tǒng)單標(biāo)記問題中經(jīng)典特征選擇算法Fisher Score[16]、Relief[15]的拓展。SPEC(spectral feature selection)[14]譜特征選擇，它不僅可以提取圖譜信息，也可以提取類標(biāo)間的結(jié)構(gòu)信息。五種特征選擇算法均屬于過濾器模型。

3.1 數(shù)據(jù)集及參數(shù)

實驗運行環(huán)境是Python 2.7，轉(zhuǎn)化策略選用BR[13]，KD樹、K近鄰算法從Scikit-learn[22]中組成基分類器。MLRF和GMBA[19]、GMBA_exp中的近鄰數(shù)均設(shè)置為3，GMBA[19]、GMBA_exp中smin和λ均設(shè)置為1，βi=0.9。從MULAN[23]上下載了四組來自不同領(lǐng)域的數(shù)據(jù)集，數(shù)據(jù)集的具體信息見表1。實驗時，將樣本方差為0的特征進行人工去除，并對數(shù)值型的特征進行歸一化,所有實驗結(jié)果均由10折交叉驗證獲得。

3.2 評價指標(biāo)

在BR[13]轉(zhuǎn)化策略下，將GMBA_exp與過濾器模型算法和封裝器模型算法進行比較，算法性能的評價指標(biāo)選[24]用F1_Macro(↑)及漢明損失(↓)，用↑表示指標(biāo)值越大越好，用↓表示指標(biāo)值越小越好，具體實驗結(jié)果見圖3～圖6(由于篇幅限制，在這里只顯示birds、emotions數(shù)據(jù)集的實驗結(jié)果)。水平線表示不用特征選擇算法時分類的結(jié)果。橫軸表示所選的特征個數(shù)占特征總數(shù)的百分比，縱軸為指標(biāo)值。

3.3 實驗結(jié)果分析

通過兩個不同的多標(biāo)記評價指標(biāo)，在四個多標(biāo)記數(shù)據(jù)集上進行實驗。實驗結(jié)果顯示，隨著所選特征的增加，評價指標(biāo)并不是單調(diào)增加或者單調(diào)減少，說明數(shù)據(jù)集中有的特征對分類性能的提高有負面影響。在多數(shù)情況下，文中提出的GMBA_exp算法相比其他算法具有更好的分類性能。此外，在與過濾器模型算法、封裝器模型算法的對比實驗中可以看出，在相同的BR[13]轉(zhuǎn)化策略下，GMBA_exp算法的分類性能最優(yōu)。

表1 數(shù)據(jù)集描述

4 結(jié)束語

實驗結(jié)果表明，GMBA_exp算法優(yōu)于其他算法。GMBA_exp和GMBA[19]算法都致力于尋找最優(yōu)的特征子空間，使得樣本在特征空間上的分布與標(biāo)記空間上的分布一致，在大多數(shù)情況下，GMBA_exp算法的效果要優(yōu)于GMBA[19]。綜上，文中提出的基于指數(shù)損失間隔的多標(biāo)記特征選擇算法能更好地描述標(biāo)記間的相關(guān)性，提高多標(biāo)記的分類性能。

與過濾器模型算法比較的實驗結(jié)果如圖3和圖4所示。

與封裝器模型算法比較的實驗結(jié)果如圖5和圖6所示。

圖3 BR轉(zhuǎn)化策略下F1_Macro(↑)(1)

圖4 BR轉(zhuǎn)化策略下Hamming loss(↓)(1)

圖5 BR轉(zhuǎn)化策略下F1_Macro(↑)(2)

圖6 BR轉(zhuǎn)化策略下Hamming loss(↓)(2)