張　敏　余圣波

(重慶大學(xué)計算機學(xué)院軟件理論與技術(shù)重慶市重點實驗室　重慶 400044)

?

基于樣本差異的多標(biāo)簽分類器評價標(biāo)準(zhǔn)預(yù)估

張敏余圣波

(重慶大學(xué)計算機學(xué)院軟件理論與技術(shù)重慶市重點實驗室重慶 400044)

評價標(biāo)準(zhǔn)是分類器的重要指標(biāo)。對于多標(biāo)簽學(xué)習(xí)，常用的評價標(biāo)準(zhǔn)有Hamming Loss、One-error、Coverage、Ranking loss和Average precision。多標(biāo)簽分類器給出分類結(jié)果的同時并未給出評價標(biāo)準(zhǔn)值，通常采用事后驗算的方法評估評價標(biāo)準(zhǔn)。這樣往往不能及時有效地發(fā)現(xiàn)評價標(biāo)準(zhǔn)值變化之類的問題，同時評估評價標(biāo)準(zhǔn)值需對測試樣本進行標(biāo)記。針對這一問題，分別從樣本分布差異和樣本實例間差異提出兩種評價標(biāo)準(zhǔn)預(yù)估方法。分析上述兩種方法的特點，提出第三種評價標(biāo)準(zhǔn)預(yù)估方法。實驗表明，這三種評價標(biāo)準(zhǔn)預(yù)估方法具有良好效果，可用于遷移學(xué)習(xí)等。

多標(biāo)簽學(xué)習(xí)評價標(biāo)準(zhǔn)樣本分布樣本實例線性擬合

0　引　言

多標(biāo)簽學(xué)習(xí)是機器學(xué)習(xí)和數(shù)據(jù)挖掘技術(shù)中的一個研究熱點。與單標(biāo)簽學(xué)習(xí)相比，多標(biāo)簽分類中的樣本可以同時歸屬多個類別。多標(biāo)簽學(xué)習(xí)是一種更符合真實世界客觀規(guī)律的方法，其廣泛地應(yīng)用于各種不同的領(lǐng)域，如圖像視頻的語義標(biāo)注[1-3]、功能基因組[4，5]、音樂情感分類[6]以及營銷指導(dǎo)[7]等。多標(biāo)簽學(xué)習(xí)主要有兩個任務(wù)：多標(biāo)簽分類和標(biāo)簽排序[8]，前者的任務(wù)就是要為每一個樣本盡可能地標(biāo)注出所有與其相關(guān)的標(biāo)簽，從而達到一個多標(biāo)簽自動分類的目的；后者則是對于待測樣本按標(biāo)簽與其相關(guān)程度由高至低輸出全部標(biāo)簽。

現(xiàn)有的多標(biāo)簽數(shù)據(jù)的學(xué)習(xí)方法主要分為兩大類：問題轉(zhuǎn)換法和算法適應(yīng)法[9]。問題轉(zhuǎn)換的方法就是通過改造數(shù)據(jù)將多標(biāo)簽學(xué)習(xí)問題轉(zhuǎn)化為其他已知的單標(biāo)簽學(xué)習(xí)問題進行求解，該方法不受特定算法的限制，目前已成熟的單標(biāo)簽分類算法有支持向量機、k近鄰方法、貝葉斯方法和提升方法等。算法適應(yīng)方法是通過直接改造現(xiàn)存的單標(biāo)簽學(xué)習(xí)算法，使之能夠適應(yīng)多標(biāo)簽數(shù)據(jù)的處理，該類方法代表性的學(xué)習(xí)算法有ML-kNN(Multi-Label k-Nearest Neighbor)[10]、RankSVM(Ranking Support Vector Machine)[11]、AdaBoost.MH(multiclass,multi-label version of AdaBoost based on Hamming loss)[12]和BoosTexter (A Boosting-based System for Text Categorization)[13]等。在本文中，使用ML-kNN分類算法得到多標(biāo)簽評價標(biāo)準(zhǔn)值。ML-kNN是kNN算法的擴展，其性能優(yōu)于BoosTexter、AdaBoost.MH和 RankSVM。

多標(biāo)簽學(xué)習(xí)的評價指標(biāo)不同于傳統(tǒng)的單標(biāo)簽學(xué)習(xí)，單標(biāo)簽學(xué)習(xí)常用的評價標(biāo)準(zhǔn)有準(zhǔn)確度、精度、召回率和F值[14]。對于多標(biāo)簽學(xué)習(xí)，常用的評價標(biāo)準(zhǔn)有Hamming loss、One-error、Coverage、Ranking loss和Average precision。其中，Hamming loss主要衡量預(yù)測所得標(biāo)簽和樣本實際標(biāo)簽不一致的程度，結(jié)果越小越好；One-error描述樣本預(yù)測隸屬度最高的標(biāo)簽不在實際標(biāo)簽的概率，結(jié)果越小越好；Coverage描述了在標(biāo)簽排序函數(shù)中，從隸屬度最高的標(biāo)簽開始，平均需要跨越多少個標(biāo)簽才能覆蓋樣本所擁有的全部標(biāo)簽，結(jié)果越小越好；Ranking loss衡量樣本所屬標(biāo)簽隸屬度低于非其所屬標(biāo)簽隸屬度的概率，結(jié)果越小越好；Average precision描述了對樣本預(yù)測標(biāo)簽的平均準(zhǔn)確率，結(jié)果越大越好。

目前要得到多標(biāo)簽學(xué)習(xí)評價標(biāo)準(zhǔn)有兩個常用方法。一個常用的方法是觀察訓(xùn)練樣本集中的評價標(biāo)準(zhǔn)值，訓(xùn)練樣本集中的評價標(biāo)準(zhǔn)值與測試樣本集中的評價標(biāo)準(zhǔn)值無明確關(guān)系，但是通過對訓(xùn)練樣本集中的評價標(biāo)準(zhǔn)值的觀察，估計測試樣本集中的評價標(biāo)準(zhǔn)值有一定意義。對于Hamming loss、One-error、Coverage和Ranking loss，這些評價標(biāo)準(zhǔn)關(guān)于測試樣本集的值往往高于或等于這些評價標(biāo)準(zhǔn)在訓(xùn)練樣本集中的估計值，那么關(guān)于訓(xùn)練樣本集的這些評價標(biāo)準(zhǔn)值過高，其在測試樣本集中的評價標(biāo)準(zhǔn)估計值也不會低。對于Average precision評價標(biāo)準(zhǔn)，其關(guān)于測試樣本集的估計值往往低于或等于其在訓(xùn)練樣本集中的估計值，那么Average precision在訓(xùn)練樣本集中的估計值太低，其在測試樣本集中的估計值也不會高。另一個常用的方法是標(biāo)記測試樣本，與分類結(jié)果對比，得到測試樣本的評價指標(biāo)值，然后利用統(tǒng)計學(xué)的知識，將計算出來的評價指標(biāo)值推廣到一般情況。這種方法需要標(biāo)記測試樣本，標(biāo)記樣本有時候會比較昂貴，但其得到的評價指標(biāo)估計值比較客觀。可以看出，想得到關(guān)于測試樣本集的確切評價指標(biāo)值，往往需要對測試樣本進行標(biāo)記，那么是否可以不對測試樣本進行額外的標(biāo)記就估計出關(guān)于測試樣本的評價指標(biāo)值呢？

本文提出基于測試樣本與訓(xùn)練樣本差異來估計關(guān)于測試樣本的評價指標(biāo)的方法。樣本差異可以從宏觀和微觀兩個角度來考慮，樣本分布差異是樣本差異的宏觀體現(xiàn)，樣本實例間差異是樣本差異的微觀體現(xiàn)。這樣可以通過收集到的測試樣本與訓(xùn)練樣本的對比估計出評價指標(biāo)值，從而避免標(biāo)記樣本的昂貴成本，使得多標(biāo)簽分類器可以在給出分類結(jié)果的同時給出評價標(biāo)準(zhǔn)估計值，可以應(yīng)用于遷移學(xué)習(xí)等領(lǐng)域。

1　基于樣本分布差異的多標(biāo)簽評價標(biāo)準(zhǔn)預(yù)估

1.1MMD統(tǒng)計量

通常情況下，分類器都假設(shè)樣本分布在整個分類過程中不會發(fā)生變化。當(dāng)訓(xùn)練樣本集和測試樣本集的分布有差異時，由訓(xùn)練樣本集得到的分類器不再適用于測試樣本集。如單標(biāo)簽貝葉斯分類器，當(dāng)訓(xùn)練樣本集和測試樣本集的分布有差異時，先驗概率發(fā)生變化，此時由訓(xùn)練樣本集得到的貝葉斯分類器不適用于測試樣本集。那么如何衡量兩組樣本的分布差異呢？

設(shè)有一組訓(xùn)練樣本集記為A(x1,x2,…,xm)，其服從分布p；一組測試樣本記為B(y1,y2,…,yn)，其服從分布q。如何判斷p和q是否相同，過去主要采用參數(shù)統(tǒng)計的方法，首先需要確定它們的分布模型，之后通過參數(shù)假設(shè)的方法推斷它們是否包含相同的參數(shù)。文獻[15]提出了將分布嵌入再生核希爾伯特空間的方法。文獻[16]提出了衡量兩組樣本差異的核方法，即最大均值差異MMD(Maximum Mean Discrepancy)的度量方法。其中：

(1)

式中，F(xiàn)為將測量空間映射到實數(shù)域的一類函數(shù)，k(·)為核函數(shù)。

(2)

式中，K為一常數(shù)，且|k(x,y)|≤K,x∈A,y∈B。

1.2MMD與評價標(biāo)準(zhǔn)的關(guān)系

為了確定MMD統(tǒng)計量與多標(biāo)簽評價標(biāo)準(zhǔn)Hamming loss、One-error、Coverage、Ranking loss和Average precision 的關(guān)系，使用參數(shù)估計的方法估計評價標(biāo)準(zhǔn)。從評價標(biāo)準(zhǔn)和MMD統(tǒng)計量的實驗數(shù)據(jù)可以看出，MMD與Hamming loss、One-error、Coverage、Ranking loss和Average precision有良好的線性關(guān)系。然而，針對不同的評價標(biāo)準(zhǔn)，相關(guān)性程度也不相同?？蓪⑹褂肕MD估計多標(biāo)簽評價標(biāo)準(zhǔn)值問題假設(shè)為：

(3)

其中H1、O1、C1、R1和A1分別為Hamming loss、One-error、Coverage、Ranking loss和Average precision的估計值。C11、C12、C13、C14和C15為參數(shù)列表；f11、f12、f13、f14和f15為線性函數(shù)。為了確定參數(shù)估計中的相關(guān)參數(shù)和使得評價標(biāo)準(zhǔn)與評價標(biāo)準(zhǔn)估計值的誤差最小，使用最小二乘法。下面以評價指標(biāo)Hamming loss為例進行求解，其他指標(biāo)的求解過程與Hamming loss相似。設(shè)有z1組實驗數(shù)據(jù)(mmdi,hlossi),i=1,…,z1，它們相互獨立，其中mmdi和hlossi分別為第i次實驗得到的MMD統(tǒng)計值和Hamming loss值。記:

則殘差平方和為：

Q1=‖Y-X×C11‖2=(Y-X×C11)′(Y-X×C11)

2　基于樣本實例間差異的多標(biāo)簽評價標(biāo)準(zhǔn)預(yù)估

2.1MMR統(tǒng)計量

MMD關(guān)注的是訓(xùn)練樣本集和測試樣本集的分布差異，是一個宏觀的統(tǒng)計量。樣本差異可以從宏觀和微觀兩個角度進行考慮。樣本實例間差異是樣本差異的微觀體現(xiàn)。為此，提出基于樣本實例間差異的多標(biāo)簽評價標(biāo)準(zhǔn)估計。

k近鄰算法kNN(k-nearest neighbor)是一種基于樣本實例的單標(biāo)簽分類器。k近鄰算法意味著每個樣本都可以用與它最近的k個鄰居來表示，其基本思想是：找到離該樣本最近的k個鄰居，如果這k個鄰居大多數(shù)屬于某一個類別，那么這個樣本也應(yīng)該屬于這個類別。k近鄰分類算法的數(shù)學(xué)模型如下：設(shè)一組訓(xùn)練樣本集記為A(x1,x2,…,xm)，一組測試樣本集記為B(y1,y2,…,yn)，為了求得B中每個樣本yi的標(biāo)簽，對每個測試樣本做如下處理：求得訓(xùn)練樣本集A中與yi最接近的k個樣本，然后由這k個樣本投票得到y(tǒng)i的標(biāo)簽。對k近鄰算法的一個明顯改進是對k個近鄰進行距離加權(quán)。離測試樣本越近的訓(xùn)練樣本，其權(quán)值越大。可以看出，在k近鄰算法中，若近鄰與測試樣本的平均距離越小，則分類結(jié)果的可信度越高。使用kNN算法得到一個分類結(jié)果，該分類結(jié)果的可信度可以由k近鄰組成的鄰域大小做出估計。此處，選擇k=1的特殊情況。如果對測試樣本B中的每一個樣本yi，與其在A中的最近鄰樣本xj的距離d(yi,xj)足夠小，那么以xj的標(biāo)簽作為yi的標(biāo)簽有較高的可信度；反之，與其在A中的最近鄰樣本xj的距離d(yi,xj)比較大，那么以xj的標(biāo)簽作為yi的標(biāo)簽具有較低的可信度。

由此假設(shè)，B中樣本與A中樣本的最小距離影響kNN算法分類結(jié)果可信度。通過觀察B中每個樣本到A中樣本的最小距離，可以得到B中樣本的kNN分類結(jié)果可信度。由這個估計得到對多標(biāo)簽分類器評價標(biāo)準(zhǔn)的估計。本文提出了MMR(Mean Maximum Resemblance)統(tǒng)計量，MMR為B中樣本到A中樣本最小距離的均值。

MMR(A,B)=mean(minx∈Ad(x,y))

(4)

MMR的計算方法如下：

Step1對yi∈B,i=1,2,…,n，計算其與訓(xùn)練樣本集的最小距離:

md(yi)=minxj∈Ad(xj,yi)

=minxj∈A(xj-yi)×(xj-yi)′j=1,2,…,m

(5)

Step2求均值：

(6)

Step3標(biāo)準(zhǔn)化：

(7)

在Step3中使用最大跨度作為標(biāo)準(zhǔn)化分母，使得MMR盡量不受訓(xùn)練樣本集的影響。MMR越大，表示測試樣本集與訓(xùn)練樣本集實例間的差異越大，隨之關(guān)于測試樣本集的Hamming loss值、One-error值、Coverage值和Ranking loss值越大，Average precision值越?。籑MR越小，表示測試樣本集與訓(xùn)練樣本集實例間的差異越小，隨之關(guān)于測試樣本集的Hamming loss值、One-error值、Coverage值和Ranking loss值越小，Average precision值越大。

MMR性質(zhì)：MMR(A,B)=0，當(dāng)且僅當(dāng)對于測試樣本集中的每一個實例，在訓(xùn)練樣本集中都可以找到與之相同的實例，使得它們的距離為0，即MMR(A,B)=0。MMR(A,B)不是一個對稱的統(tǒng)計量，即MMR(A,B)≠MMR(B,A)。一個特例是A真包含B時，有MMR(A,B)=0，MMR(B,A)≠0。MMR的計算時間復(fù)雜度為O(mn+m2)。

2.2MMR與評價標(biāo)準(zhǔn)的關(guān)系

為了確定MMR和多標(biāo)簽評價標(biāo)準(zhǔn)的關(guān)系，使用參數(shù)估計的方法估計評價標(biāo)準(zhǔn)。從多標(biāo)簽評價標(biāo)準(zhǔn)和MMR統(tǒng)計量的實驗數(shù)據(jù)可以看出，Hamming loss、One-error、Coverage、Ranking loss、Average precision和MMR統(tǒng)計量也有良好的線性關(guān)系。然而，對于不同的評價標(biāo)準(zhǔn)，相關(guān)性程度也不同。因此，跟利用MMD統(tǒng)計量估計評價標(biāo)準(zhǔn)類似，可將評價標(biāo)準(zhǔn)估計問題假設(shè)為：

(8)

其中H2、O2、C2、R2和A2分別為Hamming loss、One-error、Coverage、Ranking loss和Average precision的估計值；C21、C22、C23、C24和C25為參數(shù)列表；f21、f22、f23、f24和f25為線性函數(shù)。為了確定參數(shù)估計中的相關(guān)參數(shù)和使得評價標(biāo)準(zhǔn)與評價標(biāo)準(zhǔn)估計值的誤差最小，亦使用最小二乘法。下面以Hamming loss為例進行求解，其他評價指標(biāo)的求解過程與Hamming loss相似。設(shè)有z2組實驗數(shù)據(jù)(mmrj,hlossj),j=1,2,…,z2，它們相互獨立，其中mmrj和hlossj分別為第j次實驗得到的MMR統(tǒng)計值和Hamming loss值。記:

則殘差平方和為：

Q2=‖Y-X×C21‖2=(Y-X×C21)′(Y-X×C21)

3　基于MMD和MMR的多標(biāo)簽評價標(biāo)準(zhǔn)預(yù)估

MMD關(guān)注的是訓(xùn)練樣本集和測試樣本集的分布差異，是一個宏觀的統(tǒng)計量；MMR關(guān)注的是訓(xùn)練樣本集中的實例和測試樣本集中的實例之間的差異，是一個微觀的統(tǒng)計量。它們可以相互補充，共同估算出關(guān)于測試樣本集的評價標(biāo)準(zhǔn)值。

由利用MMD線性擬合評價標(biāo)準(zhǔn)和MMR線性擬合評價標(biāo)準(zhǔn)，可以得出Hamming loss、One-Error、Coverage、Ranking loss和Average precision分別與MMD和MMR的相關(guān)方程及參數(shù)。利用這些參數(shù)，可以得出這些評價標(biāo)準(zhǔn)與MMD和MMR的相關(guān)方程。由于MMD和MMR都與這些評價標(biāo)準(zhǔn)有良好的線性關(guān)系，故將使用MMD和MMR預(yù)估多標(biāo)簽評價標(biāo)準(zhǔn)問題假設(shè)為：

(9)

其中H3、O3、C3、R3和A3分別為Hamming loss、One-error、Coverage、Ranking loss和Average precision的估計值。c311、c312、c313、c321、c322、c323、c331、c332、c333、c341、c342、c343、c351、c352和c353為參數(shù)列表；f31、f32、f33、f34和f35為線性函數(shù)。下面以Hamming loss為例進行參數(shù)求解，其他評價標(biāo)準(zhǔn)的參數(shù)求解過程與Hamming loss相似。

(10)

線性方程f31的詳細表達式如下：

H3=c311+c312×MMD+c313×MMR

(11)

4　實驗及分析

4.1實驗說明

在實驗中共使用兩組數(shù)據(jù)集，分別描述如下：

UJIndoorLoc數(shù)據(jù)集是一個基于WLAN/WiFi指紋的多建筑多層室內(nèi)定位數(shù)據(jù)集。 該數(shù)據(jù)集有兩組數(shù)據(jù)，分別叫做UJI_training和UJI_test。UJI_training含有19 937個訓(xùn)練樣本，UJI_test含有1111個測試樣本。

Turkiye學(xué)生評價數(shù)據(jù)集由 Gazi University提供。該數(shù)據(jù)集有兩組數(shù)據(jù)，分別叫做Tu_training和Tu_test。Tu_training收集于2013年，有5820個學(xué)生評價數(shù)據(jù)；Tu_test收集于2014年，有5820個學(xué)生評價數(shù)據(jù)。這兩組數(shù)據(jù)有差異。

共進行16次試驗，分別記為Task1，Task2，…，Task16。采用ML-kNN多標(biāo)簽分類器得出關(guān)于測試樣本集的評價標(biāo)準(zhǔn)值。

4.2樣本差異與MMD、MMR的關(guān)系

Task1～Task6使用相同的訓(xùn)練樣本集，得到相同的分類器。從UJI_training set中隨機抽取1200個樣本作為Task1至Task6的訓(xùn)練樣本集。從UJI_test set中進行兩次隨機抽取200個樣本分別作為Task1和Task2的測試樣本集。從UJI_training set中(除Task1的訓(xùn)練樣本集)進行兩次隨機抽取200個樣本分別作為Task3和Task4的測試樣本集。從Task1和Task3的測試樣本集中各隨機抽取100個樣本，再將它們合并，作為Task5的測試樣本集；從Task2和Task4的測試樣本集中各隨機抽取100個樣本，再將它們合并，作為Task6的測試樣本集。然后，得到MMD值和MMR值，使用ML-kNN得到Hamming loss、One-error、Coverage、Ranking loss和Average precision的值。實驗結(jié)果如表1所示。從表1可以看出，UJI_training set和UJI_test set存在差異。不同地點采取的數(shù)據(jù)可能存在差異。

表1　Task1～Task6實驗結(jié)果

Task7-Task12使用相同的訓(xùn)練樣本集，得到相同的分類器。從Tu_training set中隨機抽取1200個樣本作為Task7至Task12的訓(xùn)練樣本集，從Tu_test set中進行兩次隨機抽取200個樣本分別作為Task7和Task8的測試樣本集。從Tu_training set(除Task7的訓(xùn)練樣本集)中進行兩次隨機抽取200個樣本分別作為Task9和Task10的測試樣本集。從Task7和Task9的測試樣本集中分別隨機抽取100個樣本，再將它們合并，作為Task11的測試樣本集。從Task8和Task10的測試樣本集中分別隨機抽取100個樣本，再將它們合并，作為Task12的測試樣本集。然后，得到它們的MMD值、MMR值和多標(biāo)簽評價標(biāo)準(zhǔn)值，實驗結(jié)果如表2所示。從表2可以看出，Tu_training set和Tu_test set兩組數(shù)據(jù)存在差異。Tu_training set采集于2013年，Tu_test set采集于2014年。

表2　Task7～Task12實驗結(jié)果

從表1和表2可以看出，MMD能正確反映兩組樣本分布的差異， MMD值越小，表示訓(xùn)練樣本集和測試樣本集的分布差異越小，從而Hamming loss、One-error、Coverage、Ranking loss的值越小，Average precision的值越大。MMD值越大，表示訓(xùn)練樣本集和測試樣本集的分布差異越大，從而Hamming loss、One-error、Coverage、Ranking loss的值越大，Average precision的值越小。MMR能正確地反映兩組樣本實例間的差異，MMR越大，表示訓(xùn)練樣本集實例和測試樣本集實例之間的差異越大，從而Hamming loss、One-error、Coverage、Ranking loss的值越大，Average precision的值越小。MMR越小，表示訓(xùn)練樣本集實例和測試樣本集實例之間的差異越小，從而Hamming loss、One-error、Coverage、Ranking loss的值越小，Average precision的值越大。

4.3評價標(biāo)準(zhǔn)估計

Task13采用UJIndoorLoc數(shù)據(jù)庫。從UJI_training set中隨機抽取801個樣本作為Task13的訓(xùn)練樣本集。為保證數(shù)據(jù)的平衡性，從UJI_training set(除Task13的訓(xùn)練樣本集)中隨機抽取1111個樣本和UJI_test set作為一個新的測試樣本集，記為Test samples1。從Test samples1中隨機抽取90個樣本作為Task13的測試樣本集。重復(fù)20次，然后得到MMD值、MMR值和多標(biāo)簽評價標(biāo)準(zhǔn)值。利用4-折交叉驗證得到評價標(biāo)準(zhǔn)的估計值。

Task14采用UJIndoorLoc數(shù)據(jù)庫。從UJI_training set中隨機抽取1200個樣本作為Task14的訓(xùn)練樣本集。為保證數(shù)據(jù)的平衡性，從UJI_training set(除Task14的訓(xùn)練樣本集)中隨機抽取1111個樣本和UJI_test set作為一個新的測試樣本集，記為Test samples2。從Test samples2中隨機抽取250個樣本作為Task14的測試樣本集。重復(fù)20次，然后得到MMD值、MMR值和多標(biāo)簽評價標(biāo)準(zhǔn)值。利用4-折交叉驗證得到評價標(biāo)準(zhǔn)的估計值。

評價標(biāo)準(zhǔn)估計的實驗結(jié)果如表3所示，其中EM(D)為使用MMD估計評價標(biāo)準(zhǔn)的誤差均值，EM(R)為使用MMR估計評價標(biāo)準(zhǔn)的誤差均值，EM(D,R)為使用MMD和MMR估計評價標(biāo)準(zhǔn)的誤差均值。

表3　Task13～Task14實驗結(jié)果

從表3和表4可以看出，針對不同的評價標(biāo)準(zhǔn)，MMD的表現(xiàn)不同。其中，對于Hamming loss、One-error、Ranking loss和Average precision，MMD的表現(xiàn)良好。對于Coverage，MMD的表現(xiàn)要比其他評價標(biāo)準(zhǔn)差。針對不同的評價標(biāo)準(zhǔn)，MMR的表現(xiàn)也不同。對于Hamming loss、One-error、Ranking loss和Average precision，MMR的表現(xiàn)良好。對于Coverage，MMR的表現(xiàn)要比其他評價標(biāo)準(zhǔn)差。綜合使用MMD和MMR估計評價標(biāo)準(zhǔn)的誤差均值一般在單獨使用MMD和MMR估計評價標(biāo)準(zhǔn)的誤差均值之間。對比表3和表4可以看出，訓(xùn)練樣本集和測試樣本集中的樣本數(shù)目越多，估計評價指標(biāo)的誤差均值越小。

Task15采用Turkiye Student Evaluation Data Set。從Tu_training set中隨機抽取801個樣本作為Task15的訓(xùn)練樣本集。將Tu_training set(除Task15的訓(xùn)練樣本集)和Tu_test set作為一個新的測試樣本集，記為Test samples3。從Test samples3中隨機抽取90個樣本作為Task15的測試樣本集。重復(fù)20次，然后得到MMD值、MMR值和多標(biāo)簽評價標(biāo)準(zhǔn)值。利用4-折交叉驗證得到評價標(biāo)準(zhǔn)的估計值。

Task16采用Turkiye Student Evaluation Data Set。從Tu_training set中隨機抽取1200個樣本作為Task16的訓(xùn)練樣本集。 將Tu_training set(除Task16的訓(xùn)練樣本集)和Tu_test set作為一個新的測試樣本集，記為Test samples4。從Test samples4中隨機抽取250個樣本作為Task16的測試樣本集。重復(fù)20次，然后得到MMD值、MMR值和多標(biāo)簽評價標(biāo)準(zhǔn)值。利用4-折交叉驗證得到評價標(biāo)準(zhǔn)的估計值。評價標(biāo)準(zhǔn)估計的實驗結(jié)果如表4所示。

表4　Task15-Task16實驗結(jié)果

表4得出的信息與表3得出的信息相同。針對不同的評價標(biāo)準(zhǔn)，MMD和MMR的表現(xiàn)不同。其中，對于Hamming loss、One-error、Ranking loss和Average precision，MMD和MMR的表現(xiàn)良好；對于Coverage，MMD和MMR的表現(xiàn)要比其他評價標(biāo)準(zhǔn)差。綜合使用MMD和MMR估計評價標(biāo)準(zhǔn)的誤差均值一般在單獨使用MMD和MMR估計評價標(biāo)準(zhǔn)的誤差均值之間。訓(xùn)練樣本集和測試樣本集中的樣本數(shù)目越多，估計評價指標(biāo)的誤差均值越小。

通過上述實驗結(jié)果可以看出，使用MMD線性估計評價標(biāo)準(zhǔn)和使用MMR線性估計評價標(biāo)準(zhǔn)的效果良好。綜合使用MMD和MMR線性估計評價標(biāo)準(zhǔn)的效果良好。因此，使用這三種方法估計評價標(biāo)準(zhǔn)是有一定意義的。MMD度量訓(xùn)練樣本集和測試樣本集之間的分布差異，MMR度量訓(xùn)練樣本集實例和測試樣本集實例之間的差異，與分類器無關(guān)，因此適用于所有的分類器。但由于分類器的性能不同，評價標(biāo)準(zhǔn)估計誤差會有一定的波動。

5　結(jié)　語

目前并沒有專門針對多標(biāo)簽分類器評價標(biāo)準(zhǔn)進行良好估計的方法。本文針對這一問題，提出多標(biāo)簽學(xué)習(xí)評價標(biāo)準(zhǔn)估計方法。從樣本分布差異得出MMD線性估計評價標(biāo)準(zhǔn)的方法，從樣本實例間差異得出MMR線性估計評價標(biāo)準(zhǔn)的方法。MMD著眼于兩組樣本的分布差異，是一個宏觀的統(tǒng)計量；MMR著眼于兩組樣本實例間的差異，是一個微觀的統(tǒng)計量。接著綜合使用MMD和MMR線性估計多標(biāo)簽分類器的評價標(biāo)準(zhǔn)，其誤差均值在單獨使用MMD線性估計評價標(biāo)準(zhǔn)和MMR線性估計評價標(biāo)準(zhǔn)的誤差均值之間。實驗表明，這三種估計方法具有良好的效果，可用于遷移學(xué)習(xí)等。

[1] Zhang M L, Zhou Z H. ML-kNN:A lazy learning approach to multi-label learning [J]. Pattern Recognition, 2007,40(7):2038-2048.

[2] Xu X S, Jiang Y, Peng L, et al. Ensemble approach based on conditional random field for multi-label image and video annotation[C] // Proceedings of the 19th ACM International Conference on Multimedia, Scottsdale, USA, 2011:1377-1380.

[3] Wang J D, Zhao Y H, Wu X Q, et al. A transductive multi-label learning approach for video concept detection [J]. Pattern Recogintion,2011, 44(10-11):2274-2286.

[4] Nicolo C B, Claudio G, Luca Z. Hierarchical classification:combining Bayes with SVM [C] //Proceedings of the 23rd International Conference on Machine learning, Pittsburgh, USA, 2006:177-184.

[5] Li G Z, You M Y, Ge L, et al. Feature selection for semi-supervised multi-label learning with application to gene function analysis [C] //Proceedings of the 1st ACM International Conference on Bioinformatics and Computational Biology, Niagara Falls, USA, 2010:354-357.

[6] Sanden C, Zhang J Z. Enhancing multi-label music genre classification through ensemble techniques [C] //Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’ 11), Beijing,China, 2011:705-714.

[7] Zhang Y, Burner S, Street W N. Ensemble pruning via semi-definite programming [J]. Journal of Machine Learning Research, 2006,7(7):1315-1338.

[8] Tsoumakas G, Katakis I, Vlahavas I. Mining multi-label data[M]2nd ed. Data Mining and Knowledge Discovery Handbook, Springer, 2010:667-685.

[9] Grigorios T, Ioannis K. Multi-label classification:an overview [J]. International Journal of Data Warehousing and Mining, 2009,3(3):1-13.

[10] Zhang M L, Zhou Z H. A k-nearest neighbor based algorithm for multi-label classification [C] //Proceedings of the 2005 IEEE International Conference on Granular Computing. Beijing:IEEE, 2005,2:718-721.

[11] Elisseeff A, Weston J. A kernel method for multi-labelled classification [C] //Proceedings of the Advances in Neural Information Processing Systems. Cambridge:MIT Press,2002:681-687.

[12] Schapire R E, Singer Y. Improved boosting algorithm using confidence-rated predictions [J]. Machine Learning,1999,37(3):297-336.

[13] Schapire R E, Singer Y,Carbonell J,et al. BoosTexter:a boosting based system for text categorization [J]. Machine Learning,2000,39(2-3):135-168.

[14] Sebastiani F. Machine learning in automated text categorization[J]. ACM Computer Surveys, 2002,34 (1) :1-47.

[15] Alex S, Arthur G, Le S, et al. A hilbert space embedding for distributions[C] //Proceedings of the 18th International Conference on Algorithmic Learning Theory, 2007:13-31.

[16] Arthur G, Karsten M B, Malte R, et al. A kernel method for the two-sample-problem[C] //Proceedings of the Advances in Neural Information Processing Systems 19, 2007:513-520.

[17] 陳昊. 加權(quán)K-NN及其應(yīng)用[D]．保定：河北大學(xué),2005.

ESTIMATING EVALUATION METRICS OF MULTI-LABEL CLASSIFIERS BASED ON SAMPLES DIFFERENCE

Zhang MinYu Shengbo

(Software Theory and Technology Chongqing Key Lab,College of Computer Science,Chongqing University,Chongqing 400044,China)

Evaluation metrics play an important role in classifiers.Popular evaluation metrics used in multi-label learning include Hamming loss,One-error,Coverage,Ranking loss and Average precision.While the classification results are obtained from multi-label classifier,the values of evaluation metrics will be derived later,usually the evaluation metrics are assessed in the way of checking afterwards.However this sometimes cannot find the problem of the variation in values of evaluation metrics timely and effectively,meanwhile it is necessary to mark the test samples when estimating the values of evaluation metrics.To solve this problem,this paper put forward two methods of estimating the evaluation metrics based on the difference in sample sets distribution and on the difference between instances in sample sets respectively.After analysing the characteristics of above two methods,we propose the third estimating method for evaluation metrics.Experiments show that the proposed three methods all have good effects.They can be used in transfer learning and others.

Multi-label learning Evaluation metricsSamples distributionSamples instancesLinear fitting

2015-04-22。中央高?；究蒲袠I(yè)務(wù)費專項資金項目(CDJZR12180005)；重慶自然科學(xué)基金項目(CSTC2011BB2063)。張敏，講師，主研領(lǐng)域：機器學(xué)習(xí)。余圣波，碩士。

TP3

A

10.3969/j.issn.1000-386x.2016.09.064