基于引力模型的多標簽分類算法

李兆玉，王紀超，雷 曼，龔 琴

(重慶郵電大學 通信與信息工程學院，重慶 400065)(*通信作者電子郵箱576233728@qq.com)

0 引言

傳統(tǒng)的監(jiān)督分類是機器學習領域中的一個重要組成部分，它的研究目的是將一條數據劃分到預先定義好的某一個類別當中。若預先定義好的類別只有一個，這樣的分類問題被稱為單標簽分類或二值分類。若存在多個類別，將數據劃分到其中之一，這樣的分類問題被稱為多類分類。多標簽分類是當前的研究熱點之一，并被廣泛應用于文本分類[1]、圖像標注[2]、蛋白質功能分析[3]等多個方面。

多標簽分類問題的形式化定義如下：

定義1 已知一個定義在實數域R上的d維特征空間，記作F；一個q維的標簽空間，記作L；包含m個訓練數據的訓練集合D。

D={(Xi,Yi)|1≤i≤m,Xi?F,Yi?L}

(1)

其中:Xi={xi1,xi2,…,xid}和Yi={yi1,yi2,…,yiq}分別為樣本i的特征部分和標簽部分。則多標簽分類可以描述為：通過對訓練集D的學習，獲得分類模型f:F→L，該模型能夠為待測數據Xt預測一個標簽集合Yt。

多標簽分類算法解決問題的思路可以概括為以下兩種：問題轉化方法和算法適應方法[4]。問題轉化方法是指將多標簽問題轉化為多個獨立的單標簽問題，利用單標簽分類器對每一個標簽進行預測，如二元關聯(Binary Relevance, BR)方法[5]、標簽冪集(Label Powerset, LP)方法[6]等。BR方法按照標簽個數，將多標簽數據集分割為q個單標簽數據集，然后采用單標簽方法進行分類。BR方法假設標簽間是相互獨立的，忽略了標簽間的相關性，浪費了多標簽數據的標簽信息。LP方法利用可能的標簽組合，將多標簽數據集分割為多個單標簽數據集，然后采用單標簽方法進行分類，但這樣往往造成了較高的復雜度。

算法適應方法是將單標簽算法進行改進，使單標簽算法能夠處理多標簽問題。典型的算法適應方法有ML-kNN(Multi-Labelk-Nearst Neibors)方法[7]、BPMLL(BP-Multi-Label Learning)方法[8]等。ML-kNN方法根據待測樣本k個近鄰的標簽信息對每個標簽采用最大后驗準則進行預測。BPMLL方法將BP神經網絡擴展為多個輸出，依據誤差度量函數對標簽進行排序獲得預測值。ML-kNN和BPMLL算法均沒有考慮標簽間的相關性，造成了標簽信息的浪費。

綜上所述，本文采用算法適應方法，對現有算法進行改進，提出了一種基于引力模型的多標簽分類算法，簡稱MLBGM。算法繼承了引力模型簡潔、易理解的特點并且考慮了標簽的相關性。關于標簽相關性，不僅考慮了標簽同時出現時代表的正相關關系，同時也發(fā)掘了標簽互斥所代表的負相關關系，充分利用了標簽間的相關關系。通過在不同數據集上進行的對比實驗結果表明，該算法在性能上優(yōu)于對比算法。

1 相關工作

1.1 引力模型

引力模型因其形式簡單且效果良好被廣泛應用于信息處理及國際貿易等領域。文獻[9]首次將引力模型用于聚類分析并與非引力方式的聚類方法進行了對比，結果表明引入引力模型后的方法取得了較好的結果。文獻[10]介紹了一種考慮引力坍縮的kNN分類器的改進算法，但該算法將所有數據粒子的質量設為一個統(tǒng)一的定值，一定程度上忽略了數據間的差異性。根據數據引力和引力場理論，Yang等[11]提出了一種基于數據引力的分類器(Data Gravitation Classifier, DGC)并將其用于入侵檢測系統(tǒng)(Intrusion Detection System, IDS)。該方法通過計算數據質心將多個數據組成的數據簇進行?；欢黄胶鈹祿乐赜绊戀|心的計算，降低分類效果?；贒GC算法，Peng等[12]提出一種通過縮放引力系數來處理不平衡數據的改進算法IDGC(Imbalanced Data Gravitation Classifier)，但IDGC算法并不適用于多標簽數據。Reyes等[13]對經典引力計算公式進行修改，提出了一種適用于多標簽數據的分類算法MLDGC(Multi-Label Data Gravitation Classifier)。該算法將每個樣本作為一個數據粒子，單獨計算每個粒子對待測樣本的引力來完成分類任務。但MLDGC沒有考慮標簽相關性，會造成標簽信息的丟失。本文提出的MLBGM對引力模型進行了改進，優(yōu)化了相互作用系數，并充分利用了標簽間不同的相關性。通過對比實驗結果表明，MLBGM在性能上優(yōu)于對比算法。

數據引力的計算由經典力學中萬有引力公式演變而來。原始引力模型計算粒子i、j間引力的方法可表示如下：

(2)

用于多標簽數據的數據引力定義如下。

定義2 粒子i與其近鄰集合中粒子j之間的引力為：

(3)

將式(2)中質量與引力系數的乘積定義為相互作用系數，記作Cj。數據粒子i與數據粒子j之間的引力與Cj成正比與dF(i,j)成反比。

1.2 標簽相關性

在多標簽分類中，一個樣本可以同時擁有多個標簽，并且這些標簽往往具有相關性。例如，一張圖片(如圖1)擁有標簽“藍天”。而標簽“藍天”與標簽“白云”有很強的相關性，利用標簽相關性有利于提高正確識別圖片中的“白云”的概率。這種標簽與標簽之間傾向于同時出現的關系通常稱為標簽間的正相關。

圖1 有“藍天”標簽的圖片Fig. 1 Picture with label “Blue Sky”

以往多標簽分類研究在考慮標簽相關性時，多采用計算標簽間正相關關系的方式來提升分類性能[14-16],然而標簽之間往往還存在著互斥現象。例如，一張圖片擁有標簽“大?！?，那么它將很有可能擁有標簽“輪船”，而擁有標簽“火車”的可能性則會很低(如圖2)。這種標簽間的排斥現象是相互的，這種互斥關系可以稱為標簽間的負相關關系。

圖2 標簽正、負相關性示意圖Fig. 2 Label positive and negative correlations

多標簽數據擁有不止一個類別標簽，因此含有豐富的標簽信息，利用標簽信息能夠提升分類效果。通過挖掘標簽間不同的相關關系對多標簽數據的標簽信息進行充分利用。

2 基于引力模型的多標簽分類算法

基于引力模型的多標簽分類算法首先將每一個樣本數據作為一個數據粒子，然后利用形式簡單的數據引力計算公式來計算粒子間的相互作用。最后，對待測樣本其近鄰集合的引力求和，構造分類函數。該算法形式簡單，在不過度增加算法復雜度的條件下，同時考慮了標簽間正、負相關性，有效利用了多標簽數據的標簽信息。

2.1 近鄰密度與近鄰權重

距離計算采用異構重疊歐氏度量(Heterogeneous Euclidean-Overlap Metric, HEOM)，該度量方法不僅能夠處理數值型數據，還能夠處理標稱型數據[17]。根據HEOM的計算方法，樣本i與樣本j之間的距離為：

(4)

當數據為離散型數據時：

(5)

當數據為連續(xù)型數據時：

(6)

其中:F為特征空間；xif代表樣本i的第f個特征；max(f)、min(f)分別為最大、最小的特征值。

根據異構重疊歐氏度量方法計算樣本i與訓練集中其他樣本的距離，將距離依照大小進行升序(降序)排序，選取距離最小的k個樣本作為樣本i的近鄰集合，記作δ(i)。

然后，應用引力模型將樣本數據轉化為數據粒子的形式。將每一個樣本數據都轉化為一個數據粒子，根據物理中常見的形式對數據粒子進行定義，則樣本i可以轉化為數據粒子i，記作(Xi,Yi,Ci)。其中：Ci為相互作用系數，Ci越大，樣本i與其他樣本之間的引力越大。Ci由近鄰密度di和近鄰權重wi組成,計算公式如下:

Ci=diwi

(7)

近鄰密度di表示粒子i的近鄰粒子的分布情況，di的值越大，則Ni中與粒子i標簽相似度高的粒子距離粒子i的距離越近。di的計算方式如下：

(8)

其中:dL(i,j)=|YiΔYj|/q，代表了粒子i與粒子j標簽部分的差異的大小;Δ表示求兩個集合的對稱差；q為標簽部分長度。

近鄰權重wi表示粒子i的近鄰粒子對分類結果的貢獻程度。由于多標簽數據標簽間的相關性對分類結果會產生影響，因此本文考慮了標簽間不同的相關關系并將相關性作為近鄰權重的一部分，則粒子i的近鄰粒子對粒子i第l個標簽的分類結果貢獻程度計算如下：

(9)

其中:Pil和Nil分別為粒子i的第l個標簽與其他標簽之間的正、負相關性系數；ui表示近鄰樣本標簽一致性的大小。

ui=pi(Fsim|Lsim)-pi(Fsim|Ldis)=

(10)

先驗概率pi(Ldis)、pi(Fdis)、pi(Fdis|Fdis)計算方法如下:

(11)

(12)

(13)

2.2 分類器的構建

通過上述分析，根據式(3)可以計算近鄰樣本與樣本i之間的引力?，F給出測試樣本i并為其預測第l個標簽，則分類函數為：

(14)

基于引力模型的多標簽分類算法在構造分類函數時采用了計算引力合力的方式，這里只計算力的數值大小，不考慮方向。則如果預測標簽yil為1時，合力為：

(15)

同理，如果標簽yil為0時，合力為：

(16)

由式(14)可知，當f+(i)>f-(i)時，yil=1；否則，yil=0。

2.3 算法描述

基于引力模型的多標簽分類算法可以分為兩個階段：

1)訓練階段。通過對訓練集數據的學習，獲得標簽間的相關性及引力計算所需的各種參數。采用基于近鄰的方式，避免求取相關性時對整個數據集的計算。在提升分類效果的同時，不過多地增加算法的復雜度。

2)測試階段。采用了形式簡單的數據引力的計算方法，且參數計算在訓練階段都已完成，所以測試階段具有較低的復雜度。

2.3.1 訓練階段

算法1 獲取正、負相關矩陣及引力計算參數。

輸入D為訓練集;k為近鄰個數。

輸出P為正相關矩陣;N為負相關矩陣;di為近鄰密度;ui為近鄰一致性系數。

初始化P、N矩陣；

fori=1 tom:

獲取樣本i的近鄰集合δ(i)；

//式(4)

計算di、ui；

//式(8)、式(10)

foryij=1,1≤j≤q:

cpij=0,cnij=0；

foryil=1,1≤l≤q:

ifj≠landp(j=1|l=1,Ni)>Pr:

cpij=cpij+1;

Pij=cpij/q;

foryil=1,1≤l≤q:

ifj≠landp(j=1|l=0,Ni)>1-Pr:

cnij=cnij+1;

Nij=cnij/q;

獲得正相關矩陣P和負相關矩陣N;

2.3.2 測試階段

算法2 對測試樣本進行標簽預測。

輸入t為測試樣本;k為近鄰個數;P為正相關矩陣;N為負相關矩陣;di為近鄰密度;ui為近鄰一致性系數。

輸出Yt為預測出的測試樣本的標簽向量。

獲取測試樣本的近鄰集合δ(i);

forl=1 toq:

分別計算f+(t)、f-(t);

//式(15)、式(16)

iff+(t)>f-(t):

yil=1;

else:

yil=0;

Yt={yt1,yt2,…,ytq};

3 實驗與分析

3.1 實驗設置

本文實驗基于一個針對多標簽學習的Java庫Mulan(http://mulan.sourceforge.net/)來實現對比算法。通過與不同算法的實驗結果進行對比，驗證本文算法的有效性。所有算法均在7個不同的多標簽數據集(見表1)上進行十折交叉驗證。

表1 實驗中使用的多標簽數據集Tab. 1 Multi-label dataset used in experiments

表2 不同算法的指標對比結果Tab. 2 Comparison of indicators of different algorithms

3.2 評價指標

由于單標簽分類的結果是單一標簽的預測值，而多標簽分類的結果為一個預測標簽集合，因此，原始單標簽的評價指標并不完全適用于多標簽分類。本文采用了漢明損失HammingLoss、微平均F1值MicroF1和子集準確率SubsetAccuracy來衡量分類效果。其中：HammingLoss和SubsetAccuracy是基于樣本(example-based)的評價指標；MicroF1是基于標簽(label-based)的評價指標?；跇颖镜脑u價指標通過分別評價每個樣本的分類效果，然后返回整體的評價結果；基于標簽的評價標準則是對每個標簽的分類效果進行評價，返回宏/微平均結果。3種評價指標計算方法如下：

(17)

(18)

(19)

3.3 實驗分析

將本文提出的MLBGM算法與MLkNN[7]、RAkEL[18]、HMC[19]、IBIR_ML[20]、BRkNN[21]這5個多標簽分類算法在3個評價指標上進行對比，結果如表2所示，其中k值為每種算法在不同數據集上的最佳近鄰數。

HammingLoss衡量了樣本標簽預測錯誤的比例[22]，從對比結果可以看出：MLBGM的HammingLoss相對更小，說明MLBGM對樣本標簽錯誤預測的比例更低。

MicroF1值是對單標簽評價指標F1值的擴展，F1值是對精確率(precision)與召回率(recall)的綜合考慮。更高的MicroF1值一般表示更好的分類效果，因此在該指標上的對比結果中，MLBGM同樣具有較好的效果。

SubsetAccuracy表示算法預測的標簽與真實標簽完全一致的樣本數占標簽總數的比例。SubsetAccuracy越大，則標簽完全預測正確的可能性越大。從對比結果可以看出：MLBGM算法在HammingLoss、MicroF1、SubsetAccuracy三個指標上均優(yōu)于對比算法。

實驗采用了7個不同的數據集與5個現有的多標簽分類算法在3個指標上進行了對比。實驗結果顯示，MLBGM與5種未考慮標簽負相關的對比算法相比，HammingLoss平均降低了15.62%，MicroF1平均提升了7.12%，SubsetAccurary平均提升了14.88%。MLBGM在大多數數據集的指標上都存在明顯優(yōu)勢，主要原因為MLkNN、RAkEL、HMC、BRkNN均沒有考慮標簽間的相關性，而IBLR_ML只考慮了標簽間的正相關關系，沒有考慮標簽互斥，沒有充分利用多標簽數據的標簽信息。綜上，MLBGM算法在基于樣本和基于標簽的評價指標上均取得了較好的結果，驗證了本文算法的有效性并且性能優(yōu)于對比算法。

4 結語

本文提出了一種基于引力模型的多標簽分類算法MLBGM。MLBGM充分利用了多標簽數據標簽間的相關性，能夠有效地對多標簽數據進行分類。算法運用物理學經典的引力模型并深入挖掘標簽間正、負兩種不同的相關性。在多個數據集上的對比實驗結果表明，本文算法能夠有效處理多標簽數據的分類問題并且分類效果優(yōu)于對比算法。后續(xù)研究將考慮標簽數量及標簽密度等因素對分類結果的影響，進一步提高算法性能。