李閃閃，田文泉，潘正高

宿州學(xué)院信息工程學(xué)院，安徽宿州，234000

在標(biāo)記學(xué)習(xí)中，研究對象往往具有多重語義，即一個對象包含多個屬性[1]。例如在自然風(fēng)景圖像標(biāo)注中，可以同時存在“藍(lán)天”“白云”“大?！薄吧碁钡榷鄠€元素，通過對標(biāo)注信息的分析可以完成圖像分類的工作。隨著數(shù)據(jù)采集技術(shù)的發(fā)展，各種類型的數(shù)據(jù)資源正在迅速增長，以數(shù)據(jù)為基礎(chǔ)的多標(biāo)記研究面臨著維數(shù)災(zāi)難的問題。數(shù)據(jù)的增長會增加計算時間、空間的消耗，同時無關(guān)數(shù)據(jù)的加入會降低分類算法的性能，因此,如何保證精度的同時有效去除多余特征是大家研究的重點。

在多標(biāo)記學(xué)習(xí)中存在多種算法，如經(jīng)典的ML-KNN(Multi-Label K Nearest Neighbors)算法[2]，考慮近鄰樣本的類別信息，根據(jù)最大化后驗概率完成對多標(biāo)記的分類預(yù)測，使分類器性能得到有效地提高。為了將標(biāo)記間的相關(guān)性考慮進(jìn)來，Elisseeff等提出Rank-SVM(Ranking Support Vector Machine)算法[3]，利用最大間隔策略構(gòu)建多標(biāo)記分類器。以上算法能夠取得良好的實驗效果，但伴隨數(shù)據(jù)維數(shù)的增長，算法所消耗的時間也會增加。因此在多標(biāo)記學(xué)習(xí)中引入數(shù)據(jù)降維，通過對數(shù)據(jù)進(jìn)行處理，減少特征數(shù)目同時提高系統(tǒng)性能的方法?，F(xiàn)有降維算法可以分為兩種[4]：一是基于特征選擇的屬性約簡方法，考慮特征之間的相關(guān)性，生成特征間冗余性較小的特征子集。二是基于特征提取的屬性約簡方法，根據(jù)對特征進(jìn)行變換，把原始高維空間數(shù)據(jù)映射至新的低維空間，改變數(shù)據(jù)原有結(jié)構(gòu)，保留數(shù)據(jù)信息。在多標(biāo)記學(xué)習(xí)中，通過特征降維方法可以剔除冗余、重復(fù)的特征，減少數(shù)據(jù)的計算量，并提高算法整體的準(zhǔn)確度。

數(shù)據(jù)降維可以有效提高數(shù)據(jù)的實用價值，因此采用奇異值分解[5](Singular Value Decomposition,SVD)對多標(biāo)記特征進(jìn)行維度約簡處理，提出基于SVD與核極限學(xué)習(xí)機的多標(biāo)記維度約簡算法(Multi-label dimension reduction learning algorithm based on singular value decomposition and kernel extreme learning machine,MLDR-SK)。首先,采用SVD對原始數(shù)據(jù)進(jìn)行奇異值計算，選擇前k個奇異值，實現(xiàn)特征降維。然后,將降維之后的數(shù)據(jù)作為輸入，通過特征和標(biāo)記信息訓(xùn)練核極限學(xué)習(xí)機模型。最后,根據(jù)模型推測給定數(shù)據(jù)，在6個公開基準(zhǔn)數(shù)據(jù)集上進(jìn)行對比，記錄4種算法基于5種不同評價指標(biāo)的實驗情況。實驗結(jié)果表明,算法在多標(biāo)記分類中能夠發(fā)揮較好的效果。

1 SVD算法

假設(shè)有包含m個樣本，n個特征的訓(xùn)練矩陣A∈Rm×n，則存在一個分解滿足：

(1)

從而將原始矩陣A分解為U、Σ、VT三個矩陣的乘積，將此定義為奇異值分解[6]。式(1)中U和V視作酉矩陣，即滿足UTU=I,VTV=I，Σ則視作m×n的非負(fù)實數(shù)對角矩陣，除對角線元素之外，其余元素均為0，具體可以描述如下：

U=[u1,u2,…um]∈Rm×m

V=[v1,v2,…vn]∈Rn×n

Σ=diag[σ1,σ2,…,σk],k=min(m,n)

根據(jù)主成分思想，奇異值越大，其包含的信息就越多。實際上，在某個奇異值(第k個)之后，剩余的奇異值均很小。 也就是說，在此數(shù)據(jù)集中，只有前k個特征較為重要，其余特征都是次要特征。因此，奇異值分解，可以用于數(shù)據(jù)的降維或是去噪處理，實現(xiàn)數(shù)據(jù)中重要特征的提取。

2 多標(biāo)記學(xué)習(xí)

2.1 多標(biāo)記學(xué)習(xí)相關(guān)定義

在多標(biāo)記學(xué)習(xí)框架下，假設(shè)樣本空間X=Rp中，存在一個輸入輸出對D={(xi,Yi)|1≤i≤n}，其中每一個xi=[xi1,xi2,…,xip]表示第i個樣本中的p維的特征向量，而Yi=[yi1,yi2,…,yiq]表示與xi相對應(yīng)的一組標(biāo)記向量，yij表示第i個樣本的第j個標(biāo)記，yij=1表示輸入樣本中存在對應(yīng)標(biāo)記，yij=0表示輸入樣本中不存在對應(yīng)標(biāo)記。例如，一個問題中存在的類別標(biāo)記有天空、草地、風(fēng)箏、兒童，則此時yi表示一個四維的行向量(yi1，yi2，yi3，yi4)，如果輸入樣本圖片中僅包含天空和草地，那么Yi=(1， 1， 0， 0)。

多標(biāo)記學(xué)習(xí)的根本任務(wù)即在已知多標(biāo)記數(shù)據(jù)集D時，構(gòu)建多標(biāo)記分類器[1]f:X→2Y，令輸入的待分類樣本屬性xi∈X，該分類器f能夠推出屬于該樣本的類別標(biāo)記集合f(x)?Y。

2.2 多標(biāo)記學(xué)習(xí)評價指標(biāo)

多標(biāo)記學(xué)習(xí)框架中，廣為使用的評價指標(biāo)主要包括平均查準(zhǔn)率(Average Precision，AP)、排位損失(Ranking Loss,RL)、覆蓋率(Coverage,CV)、一錯誤率(One-Error,OE)、漢明損失(Hamming Loss,HL)等，其具體描述如下：

平均查準(zhǔn)率(Average Precision,AP)用于評估在所有樣本預(yù)測標(biāo)記的排位序列中，排在相關(guān)標(biāo)記之前的標(biāo)記仍是相關(guān)標(biāo)記的情形。該指標(biāo)取值越大，分類性能越好，其定義如下[1]：

(2)

覆蓋率(Coverage,CV)用于評測在樣本預(yù)測標(biāo)記的排位序列中，平均需要移動多少步才能覆蓋樣本的所有相關(guān)標(biāo)記。該指標(biāo)取值越小，分類性能越好，其定義如下[1]：

(3)

漢明損失(Hamming Loss,HL)用于評定樣本的預(yù)測標(biāo)記中分類錯誤的情況。該指標(biāo)取值越小，分類性能越好，其定義如下[1]：

(4)

排位損失(Ranking Loss,RL)用于評定在所有樣本的類別標(biāo)記排位序列中排序不正確的情形，即對不相關(guān)標(biāo)記的排位在相關(guān)標(biāo)記之前的統(tǒng)計。該指標(biāo)的取值越小，分類性能越好，其定義如下[1]：

(5)

一錯誤率(One-Error,OE)用于評定在一系列樣本的預(yù)測標(biāo)記排位中，排在最前面的標(biāo)記不屬于該樣本的相關(guān)標(biāo)記集合的次數(shù)統(tǒng)計。該指標(biāo)取值越小，分類性能越好，其定義如下[1]：

3 基于SVD與核極限學(xué)習(xí)機的多標(biāo)記算法

3.1 基于SVD的數(shù)據(jù)降維處理

已知矩陣R，R是m×n階矩陣，采用SVD分解方法將矩陣R分解成3個矩陣的乘積，如公式(7)所示：

Rm×n=Um×r·Sr×r·Vr×n

(7)

其中，U視作m×r的正交矩陣，V視作r×n的正交矩陣，S視作對角矩陣，而對角線上的元素則是奇異值。第一個奇異值最大，代表包含信息最多的方向，隨著奇異值大小的改變，數(shù)據(jù)中包含有用信息的含量也在發(fā)生變化。因此，使用前k個奇異值可以有效描述樣本數(shù)據(jù)集，實現(xiàn)數(shù)據(jù)集的降維。

在SVD數(shù)據(jù)特征降維中，矩陣奇異值特征能夠?qū)崿F(xiàn)對高維特征的局部特征提取及維數(shù)約簡[6]。同時奇異值分解具有全局最優(yōu)下的數(shù)據(jù)處理能力，因為特征值最大的前20%到30%可以有效保留數(shù)據(jù)集的大部分信息，所以本文針對多標(biāo)記數(shù)據(jù)集采用SVD實現(xiàn)對數(shù)據(jù)的降維處理，計算多標(biāo)記特征數(shù)據(jù)的特征值，保留特征值最大的前20%，實現(xiàn)SVD對多標(biāo)記數(shù)據(jù)的降維。

原始數(shù)據(jù)集R是m×n階矩陣，進(jìn)行特征降維之后變成RD，RD是m×k階矩陣，其中k?n。

3.2 核極限學(xué)習(xí)機多標(biāo)記分類算法

在多標(biāo)記學(xué)習(xí)中，多標(biāo)記數(shù)據(jù)集D={(xi,Yi)|1≤i≤n}，n是每個數(shù)據(jù)集中的樣本數(shù)量，對于每一個樣本xi=[xi1,xi2,…,xip]都是P維的特征向量，利用SVD進(jìn)行特征降維，降維后的樣本為Xi′=[Xi1,Xi2,…,Xiq] ，q代表降維后的維度數(shù)(q

在極限學(xué)習(xí)機中，矩陣可以表示為：

H·β=T

(8)

其中，H是隱含層節(jié)點的輸出，β是輸出權(quán)重，T為輸出期望。

β=H-1·T

(9)

極限學(xué)習(xí)機的輸出模型可以描述為：

(10)

β為權(quán)值向量，h(xi)則是將原始數(shù)據(jù)xi從輸入空間映射至L維特征空間的向量。

按照Karush-Kuhn-Tucker (KKT)條件，能夠計算出輸出權(quán)值β，描述如下：

(11)

其中，C是正則參數(shù)，標(biāo)記分布輸出函數(shù)可表示為：

(12)

通過把核函數(shù)思想引入至極限學(xué)習(xí)機(ELM)[7]，以核矩陣Ω代替ELM中隨機矩陣H，能夠在ELM的基礎(chǔ)上增強模型的穩(wěn)定性。利用mercer條件可定義核矩陣：

ΩELM=h(xi)·h(xj)=K(xi,xj)

(13)

K(xi,xj)是核函數(shù)，核極限學(xué)習(xí)機的逼近函數(shù)可表示為：

(14)

算法結(jié)合公式(8)和(14)，首先，通過訓(xùn)練數(shù)據(jù)集已知標(biāo)簽，獲得輸出權(quán)值β，然后，將測試集特征映射到ΩELM中，估測輸出標(biāo)記。

3.3 基于SVD與核極限學(xué)習(xí)機的多標(biāo)記學(xué)習(xí)算法

輸入：多標(biāo)記訓(xùn)練集D={(xi,Yi)|1≤i≤n}；

輸出：預(yù)測標(biāo)記ypred。運算經(jīng)過如下10個步驟：

?。菏褂肧VD對多標(biāo)記數(shù)據(jù)集D作降維預(yù)處理，得出數(shù)據(jù)集D′；

ⅱ：初始化正則參數(shù)C，核參數(shù)σ；

ⅲ：for 訓(xùn)練集

ⅴ：end

ⅶ：計算核矩陣Ωtest；

ⅷ：end

ⅸ：測試集預(yù)測標(biāo)記輸出f(xtest)=Ωtestβ；

ⅹ：ypred=f(xtest)；

4 實驗及結(jié)果分析

4.1 實驗數(shù)據(jù)

為了分析算法的實驗性能，共計選取6個公開基準(zhǔn)多標(biāo)記數(shù)據(jù)集，數(shù)據(jù)集信息如表1所示。所選數(shù)據(jù)集均是取自http://mulan.sourceforge.net/datasets.html。

表1 多標(biāo)記數(shù)據(jù)集

4.2 實驗環(huán)境與實驗對比方案

實驗代碼均在Windows 10 、Matlab2016a 中運行，硬件環(huán)境Inter i5-4200 CPU 8G 內(nèi)存。為了分析算法的實驗性能，選擇5種典型評價指標(biāo)，分別是：平均查準(zhǔn)率(AP)、漢明損失(HL)、覆蓋率(CV)、一錯誤率(OE)、排位損失(RL)作為算法的性能評價指標(biāo)。通過這5種評價指標(biāo)來共同評價ML-KNN[2]、Rank-SVM[3]、ML-RBF[8]、MLDR-SK四種算法的性能，最終得出各算法的整體效能評估結(jié)果。如表2—6所示，用黑體突出標(biāo)識，作為此實驗結(jié)果的最優(yōu)數(shù)值，采用統(tǒng)計分析的方法對各種算法進(jìn)行排序。

4.3 實驗結(jié)果與穩(wěn)定性分析

表2—6分別給出在Birds、Emotion、Flags、Natural Scene、Scene和Recreation數(shù)據(jù)集上的算法實驗結(jié)果。各評價指標(biāo)之后的向上“↑”代表該指標(biāo)的數(shù)值越大，實驗性能越優(yōu)；向下“↓”則代表該指標(biāo)的數(shù)值越小，實驗性能越優(yōu)。

表2 漢明損失測試結(jié)果↓

表3 排位損失測試結(jié)果↓

表4 一錯誤率測試結(jié)果↓

表5 覆蓋率測試結(jié)果↓

表6 平均查準(zhǔn)率測試結(jié)果↑

基于表2—6的實驗結(jié)果進(jìn)行分析，實驗結(jié)論如下：

(1)本文算法MLDR-SK在5種評價指標(biāo)上均能取得較好的實驗結(jié)果，在不同評價指標(biāo)的平均值上排名均最優(yōu)。

(2)算法在OE和AP評價指標(biāo)上數(shù)值優(yōu)于各對比算法，同時在其他幾個數(shù)據(jù)集上也能取得較好的效果，說明算法能有效提高多標(biāo)記學(xué)習(xí)精度。

(3)在Emotion數(shù)據(jù)集，本文算法在HL、RL以及CV等指標(biāo)上性能略低于ML-KNN算法，仍優(yōu)于其他對比算法，綜合排名仍為第一。

(4)算法在多種不同的數(shù)據(jù)集上，均有較好的實驗結(jié)果。在特征數(shù)目較大的數(shù)據(jù)集上通過特征降維，對降維之后的數(shù)據(jù)進(jìn)行分類，能取得較理想的效果。

MLDR-SK算法對比現(xiàn)有多個算法，均能取得較好的效果，說明本文算法MLDR-SK是有效的，可以用于多標(biāo)記學(xué)習(xí)，提高分類算法的精度。

穩(wěn)定性分析：為了驗證實驗不同學(xué)習(xí)算法的穩(wěn)定性，利用蜘蛛網(wǎng)圖對不同評價指標(biāo)進(jìn)行穩(wěn)定指數(shù)表示。圖1顯示了6個數(shù)據(jù)集上4個算法的穩(wěn)定性。

從圖1可知，圖1(a)顯示的是在Hamming Loss評價指標(biāo)中，MLDR-SK在3個數(shù)據(jù)集上的平均精度的穩(wěn)定指數(shù)值是4，在其他三個數(shù)據(jù)集上效果低于ML-RBF和ML-KNN。圖1(b)顯示的是在One-Error評價指標(biāo)中，MLDR-SK在6個數(shù)據(jù)集上性能較優(yōu)，穩(wěn)定指數(shù)值在均為4，算法穩(wěn)定性指標(biāo)均優(yōu)于其他算法。圖1(c)顯示的是在Ranking Loss評價指標(biāo)中，MLDR-SK在4個數(shù)據(jù)集上的平均精度的穩(wěn)定指數(shù)值在均為4，其中兩個數(shù)據(jù)集上算法穩(wěn)定性低于ML-KNN、Rank-SVM，但是穩(wěn)定性數(shù)值仍高于其他對比算法。圖1(d)顯示的是在Coverage評價指標(biāo)中，MLDR-SK在3個數(shù)據(jù)集上的穩(wěn)定指數(shù)值在均為4。圖1(e)顯示的是在Average Precision評價指標(biāo)中，算法在各數(shù)據(jù)集上表現(xiàn)比較穩(wěn)定，穩(wěn)定性指標(biāo)均較優(yōu)。

圖1 具有不同評估指標(biāo)的6個基準(zhǔn)數(shù)據(jù)集測試獲得的穩(wěn)定性指數(shù)值

圖1所示的結(jié)果表明，MLDR-SK相比于現(xiàn)有多種算法具有較好的穩(wěn)定性，雖然在個別數(shù)據(jù)集上略低于對比算法，但是穩(wěn)定指數(shù)值波動不大且整體較優(yōu)，說明算法MLDR-SK可以有效提高精確度，適合多標(biāo)記學(xué)習(xí)。

5 結(jié) 語

多標(biāo)記學(xué)習(xí)是一種能夠解決標(biāo)記多義性的機器學(xué)習(xí)范式，本文提出基于SVD的多標(biāo)記降維MLDR-SK算法。通過SVD計算多標(biāo)記特征數(shù)據(jù)的奇異值，保留奇異值最大的前20%進(jìn)行計算，實現(xiàn)特征數(shù)據(jù)降維。將降維之后的特征數(shù)據(jù)作為輸入，幫助訓(xùn)練核極限學(xué)習(xí)機模型，完成對未知標(biāo)記數(shù)據(jù)的預(yù)測。通過6個常見的多標(biāo)記數(shù)據(jù)集，使用3種主流多標(biāo)記分類算法進(jìn)行對比實驗，采用5種多標(biāo)記分類評價指標(biāo)對實驗結(jié)果進(jìn)行評價，結(jié)果表明MLDR-SK算法在多標(biāo)記分類中可以有效提高精確度。