許二戧，于化龍

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

0 引 言

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

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

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

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

1 相關工作

1.1 多標記中的類別不平衡問題

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

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

(1)

(2)

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

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

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

(3)

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

1.2 極限學習機

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

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

Hβ=T

(4)

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

利用最小二乘法，β可通過下式進行求解：

(5)

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

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

(6)

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

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

(7)

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

2 文中算法

2.1 極限學習機的多標記應用

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

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

(8)

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

2.2 閾值自適應選取策略

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

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

(9)

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

(10)

(11)

(12)

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

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

(13)

2.3 MLTA-ELM算法流程

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

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

輸出：所訓練的多標記分類器MLTA-ELM。

步驟1：訓練多標記的ELM分類器。

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

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

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

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

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

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

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

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

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

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

步驟3：標記預測。

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

3 實驗與結果分析

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

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

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

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

3.2 結果與討論

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

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

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

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

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

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

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

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

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

3.3 參數(shù)分析

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

(a)scene

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

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

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

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

4 結束語

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