許二戧，于化龍

(江蘇科技大學(xué) 計算機學(xué)院，江蘇 鎮(zhèn)江 212003)

0 引 言

眾所周知，在傳統(tǒng)的監(jiān)督學(xué)習(xí)框架中，數(shù)據(jù)集中的每個樣本通常只關(guān)聯(lián)于一個標(biāo)記，但在現(xiàn)實應(yīng)用場景中，一個樣本則通?？赡荜P(guān)聯(lián)多個標(biāo)記，此種類型數(shù)據(jù)被稱為多標(biāo)記數(shù)據(jù)。在近十幾年中，多標(biāo)記學(xué)習(xí)已逐漸發(fā)展成為機器學(xué)習(xí)領(lǐng)域的研究熱點之一，吸引了大量研究者的關(guān)注，并在多媒體內(nèi)容自動標(biāo)注[1]、信息檢索[2]、個性化推薦[3]、生物信息學(xué)[4]等多個領(lǐng)域得到了實際的應(yīng)用。

在多標(biāo)記數(shù)據(jù)中，普遍存在著類別不平衡的現(xiàn)象，其表現(xiàn)為在絕大多數(shù)或全部標(biāo)記中的正類樣本個數(shù)遠(yuǎn)少于負(fù)類樣本個數(shù)。類別不平衡問題往往會導(dǎo)致所訓(xùn)練的分類超平面產(chǎn)生嚴(yán)重偏倚，從而降低多標(biāo)記算法的最終分類性能。為解決上述問題，Charte等[5-6]將單標(biāo)記類別不平衡學(xué)習(xí)中的ROS、RUS及SMOTE等采樣技術(shù)擴展到多標(biāo)記數(shù)據(jù)中，分別提出了ML-ROS、ML-RUS、ML-SMOTE等算法；Zhang等[7]則在算法層面進(jìn)行了改進(jìn)，通過結(jié)合樣本相關(guān)性及集成學(xué)習(xí)技術(shù)提出了COCOA算法。但上述算法仍存在著分類性能差或時間復(fù)雜度高等諸多缺點。

極限學(xué)習(xí)機(extreme learning machine，ELM)是2006年黃廣斌等[8]提出的一種單隱層前饋神經(jīng)網(wǎng)絡(luò)訓(xùn)練方法，具有訓(xùn)練速度快、泛化性能好等優(yōu)點。ELM在回歸、聚類、二類分類和多類分類等領(lǐng)域都有不錯的表現(xiàn)[9]，但目前在多標(biāo)記領(lǐng)域的應(yīng)用仍相對較少，同時也未考慮到多標(biāo)記數(shù)據(jù)中的不平衡現(xiàn)象。

鑒于ELM技術(shù)的諸多優(yōu)點，擬結(jié)合其與類別不平衡學(xué)習(xí)中常用的閾值選擇技術(shù)，提出一種適用于多標(biāo)記不平衡數(shù)據(jù)的自適應(yīng)閾值極限學(xué)習(xí)機(PSO-based multi-label threshold adaptation extreme learning machine，MLTA-ELM)算法。首先，該算法通過建立ELM模型來獲得樣本標(biāo)記的預(yù)測輸出值；然后，選定合適的閾值組合對其進(jìn)行標(biāo)記判別。在進(jìn)行閾值選擇時，原有問題轉(zhuǎn)化為一個多變量優(yōu)化問題，故文中利用粒子群優(yōu)化算法作為閾值選擇器。當(dāng)然，也可以嘗試采用其他隨機優(yōu)化算法來替換PSO算法。最后，利用12個基準(zhǔn)的多標(biāo)記數(shù)據(jù)集對該算法的性能進(jìn)行了驗證，并與5種基準(zhǔn)或流行的算法進(jìn)行了比較。

1 相關(guān)工作

1.1 多標(biāo)記中的類別不平衡問題

在多標(biāo)記學(xué)習(xí)領(lǐng)域中，已存在多種成熟的算法，如ML-KNN[10]、IMLLA[11]、BP-MLL[12]、RAkEL[13]等，但大多算法仍主要關(guān)注于如何挖掘標(biāo)記間的相關(guān)性，而忽略了多標(biāo)記數(shù)據(jù)中往往存在類別不平衡問題這一特點。因此，下面將以標(biāo)記密度與不平衡比率這兩個評價指標(biāo)來簡單介紹多標(biāo)記數(shù)據(jù)中存在的類別不平衡問題。

標(biāo)記基數(shù)(label card，LCard)表示每個樣本所對應(yīng)正類標(biāo)的均數(shù)，而標(biāo)記密度(label density，LDen)則表示每個樣本所對應(yīng)正類標(biāo)在所有類標(biāo)中所占的比例，如一個多標(biāo)記數(shù)據(jù)集的LDen測度值為0.2，則表示每10個類標(biāo)中平均有2個被標(biāo)記為正類，上述測度可通過如下兩個公式計算得出：

(1)

(2)

其中，N表示樣本數(shù)；|Yi==1|表示第i個樣本所對應(yīng)類標(biāo)被標(biāo)記為1的數(shù)量；|y|表示類標(biāo)的個數(shù)。

表1統(tǒng)計了在后續(xù)實驗中使用的12個數(shù)據(jù)集的特征信息，從中可以看出：僅有flags數(shù)據(jù)集的標(biāo)記密度接近0.5，其余的均在0.33以下，且大部分在0.2左右。這說明多標(biāo)記數(shù)據(jù)集中的正類標(biāo)記所占比例均相對較低。

表1 所用數(shù)據(jù)集及其不平衡測度

(3)

對于多標(biāo)記數(shù)據(jù)集，不平衡比率的算術(shù)平均值ImRavg能夠直觀地反映出其類別偏倚的程度。從表1可明顯看出，所有數(shù)據(jù)集的不平衡比率均處于2.2～143之間，其中8個數(shù)據(jù)集不平衡比率大于5，6個數(shù)據(jù)集的不平衡比率在10以上。總體而言，類別不平衡普遍存在于多標(biāo)記數(shù)據(jù)中，且類標(biāo)越多，極度不平衡現(xiàn)象出現(xiàn)的可能性也通常越高。

1.2 極限學(xué)習(xí)機

極限學(xué)習(xí)機是一種單隱層前饋神經(jīng)網(wǎng)絡(luò)(single hidden-layer feedback network，SLFN)訓(xùn)練方法[8]。其完全摒棄了傳統(tǒng)的迭代誤差調(diào)整策略，改為隨機設(shè)置隱層權(quán)重與偏置，然后利用最小二乘的思想直接對輸出層權(quán)重矩陣進(jìn)行求解，只需要很少的訓(xùn)練時間，即可獲得同等或更優(yōu)的泛化性能。

不妨假設(shè)訓(xùn)練集包含N個樣本，且這些樣本能被分入m個類中，第i個訓(xùn)練樣本表示為(xi,ti)，其中xi是一個n維的輸入向量，而ti則對應(yīng)于一個m維的輸出向量。另假設(shè)ELM中包括L個隱藏層節(jié)點，該層上的權(quán)重w與偏置b在[-1,1]區(qū)間完全隨機生成，那么對于樣本xi，其對應(yīng)的隱藏層輸出可以表示為一個行向量h(xi)=[h1(xi),h2(xi),…,hL(xi)]。ELM的數(shù)學(xué)模型可以表示為：

Hβ=T

(4)

其中，H=[h(x1),h(x2),…,h(xN)]T為所有樣本對應(yīng)的隱藏層輸出矩陣；β為待求解的輸出層權(quán)重矩陣；T=[t1,t2,…,tN]為樣本類標(biāo)所對應(yīng)的期望輸出矩陣。

利用最小二乘法，β可通過下式進(jìn)行求解：

(5)

其中，H為H的Moore-Penrose廣義逆，可以保證所求得解為式4的最小范數(shù)最小二乘解。因此，極限學(xué)習(xí)機可通過一步計算得到，無需迭代，使得訓(xùn)練時間大幅縮短。

也可從優(yōu)化角度來描述和求解ELM。為最小化訓(xùn)練誤差且同時提升模型的泛化能力，需同時對‖Hβ-T‖2和‖β‖2做最小化處理，故該問題可描述為如下形式：

(6)

其中，ξi=[ξi,1,ξi,2,…,ξi,m]表示樣本xi在所有輸出節(jié)點上對應(yīng)的訓(xùn)練誤差向量；C表示懲罰因子，用于調(diào)控模型訓(xùn)練準(zhǔn)確性與泛化性二者之間的均衡關(guān)系。

式6可通過求解得到，給定一個具體樣例x，其對應(yīng)的實際輸出向量可由下式求得：

(7)

其中，f(x)=[f1(x),f2(x),…,fm(x)]表示樣例x的實際輸出向量，而該樣例的預(yù)測類標(biāo)為向量f(x)中元素最大的值對應(yīng)的類別。

2 文中算法

2.1 極限學(xué)習(xí)機的多標(biāo)記應(yīng)用

ELM的網(wǎng)絡(luò)結(jié)構(gòu)不僅適用于單標(biāo)記學(xué)習(xí)，也同樣可用于多標(biāo)記學(xué)習(xí)[9]。在多標(biāo)記學(xué)習(xí)中，式6、式7依然有效，輸出節(jié)點個數(shù)不再代表類別的個數(shù)，而是多標(biāo)記數(shù)據(jù)類標(biāo)的個數(shù)，即m個輸出節(jié)點代表每個樣例關(guān)聯(lián)m個標(biāo)記。

標(biāo)記判別時，單標(biāo)記中，單個樣例僅關(guān)聯(lián)一個標(biāo)記，僅需求出輸出向量f(x)中元素最大值的對應(yīng)標(biāo)記即可；而對于多標(biāo)記問題，單個樣本可能關(guān)聯(lián)多個標(biāo)記，此時，需要設(shè)定一個閾值函數(shù)th(x),并通過下式預(yù)測類標(biāo)：

(8)

因此，閾值函數(shù)th(x)的確定成為了解決該問題的關(guān)鍵。

2.2 閾值自適應(yīng)選取策略

類別不平衡問題中常用的閾值選擇方式有[14]：根據(jù)經(jīng)驗來設(shè)定閾值[15]，即th(x)等于一個常數(shù)θ；采用優(yōu)化技術(shù)來確定閾值[16]，即th(x)等于一個向量[θ1,θ2,…,θm]。對于多標(biāo)記分類問題，類標(biāo)空間維度往往較高，因而閾值選擇也會更加困難，故簡單的由經(jīng)驗來設(shè)定閾值的方式通常不會取得理想的分類效果，所以文中關(guān)注如何通過優(yōu)化技術(shù)來設(shè)定最優(yōu)閾值，則問題就轉(zhuǎn)變成了一個多變量的最優(yōu)化問題。

首先選取不平衡問題的常用性能度量指標(biāo)Macro F-measure(Macro-F)為優(yōu)化目標(biāo)。首先基于統(tǒng)計量求得在各個類標(biāo)上的分類性能，然后再將所有類上的測度均值作為最終結(jié)果。計算公式如下：

(9)

其中，|y|表示類標(biāo)數(shù)。

(10)

(11)

(12)

其中，TP表示真正類；FP表示假正類；TN表示真負(fù)類；FN表示假負(fù)類。

其次選用PSO粒子群優(yōu)化算法[17-18]。在PSO中，每個粒子有適應(yīng)性，能夠與環(huán)境及其他粒子進(jìn)行交流，并根據(jù)交流的過程學(xué)習(xí)來改變自己的結(jié)構(gòu)與行為，以此達(dá)到最優(yōu)。在PSO算法優(yōu)化過程中，每個粒子通過學(xué)習(xí)其自身經(jīng)驗(pbest)和種群其他成員的經(jīng)驗(gbest)，動態(tài)改變各自的位置和速度。其每輪的更新方式如下：

(13)

2.3 MLTA-ELM算法流程

綜上所述，下面給出了MLTA-ELM算法的整體流程。

輸入：多標(biāo)記訓(xùn)練樣本S:{(xi,Yi)|i=1,2,…,n}，隱層節(jié)點數(shù)L，懲罰因子C；

輸出：所訓(xùn)練的多標(biāo)記分類器MLTA-ELM。

步驟1：訓(xùn)練多標(biāo)記的ELM分類器。

(1)根據(jù)輸入節(jié)點數(shù)，隱層節(jié)點數(shù)L，懲罰因子C與多標(biāo)記類別個數(shù)，隨機生成網(wǎng)絡(luò)模型的隱藏層權(quán)重和偏置，設(shè)置激活函數(shù)為sigmoid函數(shù)；

(2)在訓(xùn)練集S上根據(jù)式6訓(xùn)練ELM分類器M；

(3)獲得訓(xùn)練集S在模型M上的實值輸出的矩陣f(x)。

步驟2：最優(yōu)閾值組合選取[θ1,θ2,…,θm]。

(1)種群初始化，包括初始位置、速度等；

(2)計算每個微粒的適應(yīng)度；

(3)計算粒子所經(jīng)歷的最好位置pbest，并計算群體中所有粒子經(jīng)歷的最好位置；

(4)根據(jù)式13進(jìn)行速度和位置更新；

(5)反復(fù)執(zhí)行步驟2～4，直到達(dá)到最大進(jìn)化迭代次數(shù)；

(6)最大適應(yīng)度對應(yīng)種群中的位置，即所求最優(yōu)閾值組合。

步驟3：標(biāo)記預(yù)測。

對于一個樣例x，首先通過步驟1獲得輸出矩陣f(x),將其與最優(yōu)閾值組合[θ1,θ2,…,θm]根據(jù)式8進(jìn)行比較，獲得判別標(biāo)記。

3 實驗與結(jié)果分析

3.1 數(shù)據(jù)集與實驗設(shè)置

實驗主要在12個基準(zhǔn)的多標(biāo)記數(shù)據(jù)集上完成，這些數(shù)據(jù)集涵蓋了文本、音頻、生物等不同場景。各數(shù)據(jù)集具有不同的樣本數(shù)、類標(biāo)數(shù)、標(biāo)記密度及不平衡比率。有關(guān)這些數(shù)據(jù)集的具體信息見表1。

硬件環(huán)境：Intel酷睿i7-555U處理器，CPU主頻3.1 GHz，內(nèi)存8 GB，硬盤1 TB，操作系統(tǒng)為Windows 8.1；編程環(huán)境為Matlab2015b。

為驗證提出算法的有效性與優(yōu)越性，將其與幾種經(jīng)典的多標(biāo)記不平衡分類算法進(jìn)行實驗比較，比較算法包括COCOA[7]、ML-SMOTE[5]、ML-ROS[6]、ML-RUS[6]以及標(biāo)準(zhǔn)ELM等。各類算法所特有的參數(shù)均按照代碼中的原始最優(yōu)設(shè)置而設(shè)定。COCOA算法中特有的參數(shù)K，ML-ROS、ML-RUS中的特有參數(shù)P，根據(jù)對應(yīng)參考文獻(xiàn)分別設(shè)置如下：K=min(q-1,10)，P=10%。在標(biāo)準(zhǔn)的ELM算法中，各類標(biāo)對應(yīng)的閾值均為缺省值0。同時，為了保證實驗的公正性，除COCOA采用對應(yīng)文獻(xiàn)自帶的分類器外，其他算法均采用ELM作為基分類器。ELM算法中的兩個參數(shù)，隱層節(jié)點數(shù)L及懲罰因子C，則通過內(nèi)部五折交叉驗證的grid search方法進(jìn)行選取，選取范圍為：L∈{50,100,…,1 000}，C∈{21,22,…,220}。此外，考慮到實驗中各種算法均存在一定的隨機性，故實驗結(jié)果以50次隨機5折交叉驗證所計算得到的均值形式給出。性能測度指標(biāo)分別采用Macro F-measure (Macro-F)及Micro F-measure (Micro-F)。

3.2 結(jié)果與討論

表2及表3分別給出了各算法在各個數(shù)據(jù)集上的Macro-F及Micro-F性能測度值。

表2 各算法在各數(shù)據(jù)集上的Macro-F結(jié)果

表3 各算法在各數(shù)據(jù)集上的Micro-F結(jié)果

從這些實驗結(jié)果中，可以得出如下結(jié)論：

(1)從兩種性能測度的結(jié)果來看，無論采用采樣技術(shù)、集成學(xué)習(xí)技術(shù)還是文中采用的閾值技術(shù)，均可或多或少地緩解樣本不平衡分布對分類器性能所產(chǎn)生的負(fù)面影響。這一結(jié)論主要體現(xiàn)在各類算法與基準(zhǔn)ELM分類器的結(jié)果比較上。

(2)在幾乎全部數(shù)據(jù)集上，MLTA-ELM與COCOA算法均顯著優(yōu)于ML-SMOTE、ML-ROS及ML-RUS算法。究其原因，前兩種算法屬于算法適應(yīng)型，其在算法模型上進(jìn)行了針對性的改動以適應(yīng)多標(biāo)記數(shù)據(jù)中的不平衡現(xiàn)象，而后三種算法則采用了采樣的策略，是立足于通過調(diào)整數(shù)據(jù)分布以彌補數(shù)據(jù)的不平衡分布，具有一定的隨機性，同時也容易出現(xiàn)過擬合與欠擬合的現(xiàn)象。

(3)相較于ML-ROS與ML-RUS，ML-SMOTE算法在絕大數(shù)據(jù)集上都有不同程度的性能提升，這是因為該算法不再簡單地對少數(shù)類樣本進(jìn)行復(fù)制，而是通過一定策略生成大量新樣本的方式來謀求訓(xùn)練樣本集類分布的平衡，因此采樣結(jié)果更具泛化性。這一結(jié)論也可通過比較ML-ROS、ML-RUS與基準(zhǔn)ELM算法的結(jié)果而得出：在不平衡比率較大的數(shù)據(jù)集上，ROS與RUS算法的性能往往低于基準(zhǔn)ELM算法，而ML-SMOTE相較于基準(zhǔn)ELM算法則通常會有一定的性能提升，這也再次證明了對多標(biāo)記數(shù)據(jù)進(jìn)行隨機采樣往往會造成過適應(yīng)，而ML-SMOTE算法則可有效規(guī)避該問題。

(4)與除COCOA算法外的其他多標(biāo)記不平衡學(xué)習(xí)算法相比，MLTA-ELM算法在性能上均有較大幅度的提升。具體而言，在兩個性能測度上，MLTA-ELM算法分別在8個和6個數(shù)據(jù)集上獲得了最優(yōu)的性能，充分說明了MLTA-ELM算法能夠根據(jù)不同的數(shù)據(jù)分布自適應(yīng)地選擇最優(yōu)閾值組合。至于為何其在Marco-F測度上的效果要更優(yōu)，相信原因在于PSO是以該測度為尋優(yōu)目標(biāo)相關(guān)。

(5)相比于COCOA算法，文中算法并未體現(xiàn)出顯著的優(yōu)勢。究其原因，不難發(fā)現(xiàn)：COCOA算法利用了標(biāo)記間的相關(guān)性信息；COCOA算法采用了集成學(xué)習(xí)模式來提升分類模型的泛化性與分類性能，而這也是文中算法所欠缺的。當(dāng)然，在實驗中也發(fā)現(xiàn)，文中算法的時間開銷往往遠(yuǎn)小于COCOA算法，尤其在類標(biāo)規(guī)模較大的數(shù)據(jù)集上，這一優(yōu)勢通常會體現(xiàn)得更加明顯。

3.3 參數(shù)分析

最后，分析參數(shù)對模型的重要程度。選取了標(biāo)記小于10的數(shù)據(jù)集scene和標(biāo)記大于100的數(shù)據(jù)集cal500。通過實驗獲取了不同參數(shù)L、C時對應(yīng)的模型指標(biāo)Macro-F。

(a)scene

(b)cal500 圖1 不同L與C下的Macro-F

由圖1可見，在不同參數(shù)L、C下，其結(jié)果會隨著參數(shù)的變化而較為平滑地上升或下降?？梢钥闯觯瑑蓚€數(shù)據(jù)集中，在選定的參數(shù)范圍內(nèi)，均存在最小值與最大值，且最大值不處于邊緣狀態(tài)，也就是說，該參數(shù)范圍是包含了最大值范疇的，也證明了該參數(shù)范圍是有效的。

此外，實驗分析了粒子群算法迭代次數(shù)與標(biāo)記個數(shù)的關(guān)系，理論上，標(biāo)記數(shù)的大小，表明標(biāo)記空間維度的大小，在高維空間中搜索的范圍會更大，需要的迭代次數(shù)也越多。通過圖2可以看出，在scene與cal500上的收斂迭代次數(shù)分別為20多次與60多次。由此可以得出，標(biāo)記數(shù)越大，其迭代次數(shù)會越大。

圖2 粒子群算法100次迭代過程的適應(yīng)度變化曲線

4 結(jié)束語

針對多標(biāo)記數(shù)據(jù)中廣泛存在的類別不平衡問題，提出了一種基于粒子群的多標(biāo)記自適應(yīng)閾值極限學(xué)習(xí)機(MLTA-ELM)算法。該算法以Macro F-measure為優(yōu)化目標(biāo)，將多標(biāo)記閾值選擇問題轉(zhuǎn)化為一個多維連續(xù)空間的優(yōu)化問題，并通過粒子群優(yōu)化算法進(jìn)行求解，以自適應(yīng)地構(gòu)建較優(yōu)的多標(biāo)記分類模型。在12個多標(biāo)記數(shù)據(jù)集上的實驗結(jié)果表明，與諸多同類算法相比，該算法極大地提升了多標(biāo)記分類的性能，可以滿足各種實際應(yīng)用的需求。但該算法未考慮類標(biāo)間的相關(guān)性，若將該信息融合進(jìn)分類模型，相信可以進(jìn)一步提升分類性能；由于引入了隨機優(yōu)化過程，故該算法的時間復(fù)雜度仍然較高。對于這些問題，該算法還有待進(jìn)一步的改進(jìn)。