李兆玉，王紀(jì)超，雷 曼，龔 琴

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

0 引言

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

多標(biāo)簽分類問題的形式化定義如下：

定義1 已知一個定義在實數(shù)域R上的d維特征空間，記作F；一個q維的標(biāo)簽空間，記作L；包含m個訓(xùn)練數(shù)據(jù)的訓(xùn)練集合D。

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

(1)

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

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

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

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

1 相關(guān)工作

1.1 引力模型

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

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

(2)

用于多標(biāo)簽數(shù)據(jù)的數(shù)據(jù)引力定義如下。

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

(3)

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

1.2 標(biāo)簽相關(guān)性

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

圖1 有“藍天”標(biāo)簽的圖片F(xiàn)ig. 1 Picture with label “Blue Sky”

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

圖2 標(biāo)簽正、負相關(guān)性示意圖Fig. 2 Label positive and negative correlations

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

2 基于引力模型的多標(biāo)簽分類算法

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

2.1 近鄰密度與近鄰權(quán)重

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

(4)

當(dāng)數(shù)據(jù)為離散型數(shù)據(jù)時：

(5)

當(dāng)數(shù)據(jù)為連續(xù)型數(shù)據(jù)時：

(6)

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

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

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

Ci=diwi

(7)

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

(8)

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

近鄰權(quán)重wi表示粒子i的近鄰粒子對分類結(jié)果的貢獻程度。由于多標(biāo)簽數(shù)據(jù)標(biāo)簽間的相關(guān)性對分類結(jié)果會產(chǎn)生影響，因此本文考慮了標(biāo)簽間不同的相關(guān)關(guān)系并將相關(guān)性作為近鄰權(quán)重的一部分，則粒子i的近鄰粒子對粒子i第l個標(biāo)簽的分類結(jié)果貢獻程度計算如下：

(9)

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

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

(10)

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

(11)

(12)

(13)

2.2 分類器的構(gòu)建

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

(14)

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

(15)

同理，如果標(biāo)簽yil為0時，合力為：

(16)

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

2.3 算法描述

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

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

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

2.3.1 訓(xùn)練階段

算法1 獲取正、負相關(guān)矩陣及引力計算參數(shù)。

輸入D為訓(xùn)練集;k為近鄰個數(shù)。

輸出P為正相關(guān)矩陣;N為負相關(guān)矩陣;di為近鄰密度;ui為近鄰一致性系數(shù)。

初始化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;

獲得正相關(guān)矩陣P和負相關(guān)矩陣N;

2.3.2 測試階段

算法2 對測試樣本進行標(biāo)簽預(yù)測。

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

輸出Yt為預(yù)測出的測試樣本的標(biāo)簽向量。

獲取測試樣本的近鄰集合δ(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 實驗設(shè)置

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

表1 實驗中使用的多標(biāo)簽數(shù)據(jù)集Tab. 1 Multi-label dataset used in experiments

表2 不同算法的指標(biāo)對比結(jié)果Tab. 2 Comparison of indicators of different algorithms

3.2 評價指標(biāo)

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

(17)

(18)

(19)

3.3 實驗分析

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

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

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

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

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

4 結(jié)語

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