基于非負(fù)矩陣分解與稀疏表示的多標(biāo)簽分類算法

包永春，張建臣，杜守信，張軍軍

（1.西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，西安 710048； 2.德州學(xué)院 計(jì)算機(jī)與信息學(xué)院，山東 德州 253023）（?通信作者電子郵箱 baoyongchun2014@163.com）

基于非負(fù)矩陣分解與稀疏表示的多標(biāo)簽分類算法

包永春1*，張建臣2，杜守信1，張軍軍1

（1.西安工程大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，西安 710048； 2.德州學(xué)院 計(jì)算機(jī)與信息學(xué)院，山東 德州 253023）（?通信作者電子郵箱 baoyongchun2014@163.com）

傳統(tǒng)的多標(biāo)簽分類算法是以二值標(biāo)簽預(yù)測(cè)為基礎(chǔ)的，而二值標(biāo)簽由于僅能指示數(shù)據(jù)是否具有相關(guān)類別，所含語(yǔ)義信息較少，無(wú)法充分表示標(biāo)簽語(yǔ)義信息。為充分挖掘標(biāo)簽空間的語(yǔ)義信息，提出了一種基于非負(fù)矩陣分解和稀疏表示的多標(biāo)簽分類算法（MLNS）。該算法結(jié)合非負(fù)矩陣分解與稀疏表示技術(shù)，將數(shù)據(jù)的二值標(biāo)簽轉(zhuǎn)化為實(shí)值標(biāo)簽，從而豐富標(biāo)簽語(yǔ)義信息并提升分類效果。首先，對(duì)標(biāo)簽空間進(jìn)行非負(fù)矩陣分解以獲得標(biāo)簽潛在語(yǔ)義空間，并將標(biāo)簽潛在語(yǔ)義空間與原始特征空間結(jié)合以形成新的特征空間；然后，對(duì)此特征空間進(jìn)行稀疏編碼來(lái)獲得樣本間的全局相似關(guān)系；最后，利用該相似關(guān)系重構(gòu)二值標(biāo)簽向量，從而實(shí)現(xiàn)二值標(biāo)簽與實(shí)值標(biāo)簽的轉(zhuǎn)化。在5個(gè)標(biāo)準(zhǔn)多標(biāo)簽數(shù)據(jù)集和5個(gè)評(píng)價(jià)指標(biāo)上將所提算法與MLBGM、ML2、LIFT和MLRWKNN等算法進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果表明，所提MLNS在多標(biāo)簽分類中優(yōu)于對(duì)比的多標(biāo)簽分類算法，在50%的案例中排名第一，在76%的案例中排名前二，在全部的案例中排名前三。

多標(biāo)簽分類；非負(fù)矩陣分解；稀疏表示；多輸出回歸；機(jī)器學(xué)習(xí)

0 引言

分類問(wèn)題是機(jī)器學(xué)習(xí)中一類十分重要的問(wèn)題。傳統(tǒng)的分類問(wèn)題一般為二分類或多類分類問(wèn)題。二分類是指一個(gè)對(duì)象屬于兩個(gè)類別中的一個(gè)，例如垃圾郵件分類；多類分類是指一個(gè)對(duì)象屬于多個(gè)類別中的一個(gè)，例如手寫(xiě)體數(shù)字識(shí)別。這些傳統(tǒng)的分類方法考慮的對(duì)象都只有一個(gè)標(biāo)簽，具有單一語(yǔ)義，通常把這種傳統(tǒng)的分類方法稱作單標(biāo)簽分類方法。不同于傳統(tǒng)的單標(biāo)簽分類方法，多標(biāo)簽分類［1］的對(duì)象通常同時(shí)和多個(gè)標(biāo)簽相關(guān)聯(lián)，同時(shí)屬于多個(gè)類別。這種對(duì)象在實(shí)際中也更為常見(jiàn)，在現(xiàn)實(shí)生活中，各種不同事物往往同時(shí)具有多種語(yǔ)義或可被同時(shí)歸為多種類別或同時(shí)具有多種類別標(biāo)簽，例如：一部電影，可同時(shí)被標(biāo)注為劇情、喜劇、奇幻等多個(gè)標(biāo)簽；一篇新聞報(bào)道，可同時(shí)被歸為經(jīng)濟(jì)、政治、文化等類別。隨著多標(biāo)簽分類技術(shù)的發(fā)展，多標(biāo)簽學(xué)習(xí)受到學(xué)界和業(yè)界的廣泛關(guān)注，已被成功應(yīng)用于多標(biāo)簽文本分類［2-3］、生物信息學(xué)［4-5］、圖像標(biāo)注［6-8］、視頻標(biāo)注［9］等不同領(lǐng)域。

隨著多標(biāo)簽分類技術(shù)的發(fā)展，大量多標(biāo)簽分類算法不斷涌現(xiàn)。目前已出現(xiàn)的多標(biāo)簽分類算法大致可分為問(wèn)題轉(zhuǎn)換型和算法適應(yīng)型兩種類型［10］。對(duì)于問(wèn)題轉(zhuǎn)換型算法，其策略是將多標(biāo)簽分類問(wèn)題轉(zhuǎn)換成一個(gè)或多個(gè)單標(biāo)簽分類問(wèn)題，從而可以更加方便地應(yīng)用現(xiàn)有傳統(tǒng)分類方法來(lái)解決問(wèn)題，如二元關(guān)聯(lián)（Binary Relevance， BR）算法［11］、分類器鏈（Classifier Chains， CC）算法［12］、成對(duì)比較排序（Ranking by Pairwise Comparison， RPC）算法［13］、標(biāo)準(zhǔn)標(biāo)簽排序（Calibrated Label Ranking， CLR）算法［14］等。對(duì)于算法適應(yīng)型方法，其策略是通過(guò)擴(kuò)展傳統(tǒng)單標(biāo)簽分類算法來(lái)直接處理多標(biāo)簽數(shù)據(jù)，如基于支持向量機(jī)的方法Rank-SVM（Ranking Support Vector Machine）［15］、基于實(shí)例（instance）的方法MLKNN（Multi-LabelK-Nearest Neighbor）［16］、基于神經(jīng)網(wǎng)絡(luò)的方法BP-MLL（Multi-Label Learning with BP neural network）［17］等。

然而，以上這些多標(biāo)簽分類算法存在一些類似的問(wèn)題，即這些算法都是以原始二值標(biāo)注的標(biāo)簽向量作為基礎(chǔ)，這種二值標(biāo)注的標(biāo)簽向量?jī)H能指示數(shù)據(jù)是否具有相關(guān)類別，所含語(yǔ)義信息較少，且不能精確反映數(shù)據(jù)中不同類別的相對(duì)重要程度。實(shí)際上，對(duì)于一個(gè)具有多個(gè)標(biāo)簽的對(duì)象，每個(gè)標(biāo)簽的相對(duì)重要程度是不同的。例如，在同一幅圖像中不同標(biāo)簽之間的相對(duì)重要性是不同的（雖然沒(méi)有直接標(biāo)注出每個(gè)標(biāo)簽的重要性，但是一般可以通過(guò)對(duì)圖像中對(duì)象位置（前景、背景）和所占圖像面積等觀察得到。一般來(lái)說(shuō)，對(duì)象在圖像中位置越靠前，所占面積越大，對(duì)應(yīng)標(biāo)簽就越重要），或者不同圖像中同一標(biāo)簽的所占重要性也是不相同的。如果能將樣本對(duì)象的二值標(biāo)簽通過(guò)某種方式改造為實(shí)值標(biāo)簽，將能豐富標(biāo)簽的語(yǔ)義信息，也能幫助更好地完成多標(biāo)簽分類任務(wù)。

在多標(biāo)簽分類中，樣本的標(biāo)簽之間存在相關(guān)性。例如，如果一部電影被標(biāo)志為“哈利波特”，那它很可能也會(huì)被標(biāo)記為“魔法”“英國(guó)”；如果一幅圖像被標(biāo)志為“熱帶”“森林”，那么它幾乎不可能同時(shí)被標(biāo)注為“南極”。這種相關(guān)性為多標(biāo)簽分類任務(wù)帶來(lái)了方便，如果能合理利用標(biāo)簽之間的相關(guān)性關(guān)系，將對(duì)多標(biāo)簽學(xué)習(xí)有很大幫助。同時(shí)，多標(biāo)簽數(shù)據(jù)集中標(biāo)簽規(guī)模通常很大，人類在進(jìn)行繁重的標(biāo)注工作時(shí)，難免會(huì)出現(xiàn)一些不正確的標(biāo)注。這些噪聲標(biāo)簽信息的存在，使得估計(jì)類標(biāo)簽之間的相關(guān)性變得困難，進(jìn)而對(duì)學(xué)習(xí)性能產(chǎn)生負(fù)面影響。此外，“維數(shù)災(zāi)難（curse of dimensionality）”問(wèn)題同樣存在于高維的標(biāo)簽空間中，為了能有效處理高維標(biāo)簽數(shù)據(jù)，在多標(biāo)簽學(xué)習(xí)過(guò)程中通常會(huì)對(duì)其進(jìn)行降維。

基于以上分析，針對(duì)原始二值標(biāo)簽所含語(yǔ)義信息較少的問(wèn)題，為了充分挖掘標(biāo)簽空間語(yǔ)義信息，本文提出了一種基于非負(fù)矩陣分解和稀疏表示的多標(biāo)簽分類算法（Multi-Label classification algorithm based on Non-negative matrix factorization and Sparse representation， MLNS）。該算法結(jié)合了非負(fù)矩陣分解（Non-negative Matrix Factorization， NMF）技術(shù)和稀疏表示技術(shù)，可以將二值標(biāo)簽向量轉(zhuǎn)換為實(shí)值標(biāo)簽向量，豐富標(biāo)簽語(yǔ)義信息，提高分類效果。具體來(lái)說(shuō)，首先通過(guò)非負(fù)矩陣分解，將原始的多標(biāo)簽信息映射到一個(gè)低維的潛在語(yǔ)義空間中，該潛在語(yǔ)義空間不僅保留了標(biāo)簽之間的相關(guān)性，而且極大減少了原始標(biāo)簽空間中的噪聲信息。然后，將分解后得到的低維標(biāo)簽向量與原始樣本特征向量結(jié)合，形成新的特征空間，在該特征空間中，通過(guò)稀疏表示技術(shù)挖掘樣本間的結(jié)構(gòu)信息，并利用這些樣本間結(jié)構(gòu)信息，將原來(lái)的二值標(biāo)簽向量變換為實(shí)值標(biāo)簽向量。最終，將多標(biāo)簽分類問(wèn)題轉(zhuǎn)化為多輸出回歸問(wèn)題。本文所提算法的主要工作如下：

1）利用稀疏表示技術(shù)，挖掘樣本間結(jié)構(gòu)信息，并依據(jù)此結(jié)構(gòu)信息，將二值標(biāo)簽向量轉(zhuǎn)化為實(shí)值標(biāo)簽向量，豐富標(biāo)簽語(yǔ)義信息。

2）利用對(duì)標(biāo)簽空間進(jìn)行非負(fù)矩陣分解，獲取標(biāo)簽之間的高階相關(guān)性，同時(shí)減少標(biāo)簽噪聲信息，降低標(biāo)簽空間維度。

3）將分解后得到的低維標(biāo)簽矩陣和原始特征矩陣結(jié)合，減少后續(xù)對(duì)樣本間結(jié)構(gòu)關(guān)系挖掘時(shí)的信息丟失。

1 相關(guān)工作

1.1 多標(biāo)簽學(xué)習(xí)

在多標(biāo)簽分類中，每個(gè)對(duì)象樣本（example）的樣本數(shù)據(jù)均由兩部分組成，即描述對(duì)象屬性的示例（instance）（由特征向量表示）和描述對(duì)象類別標(biāo)簽的標(biāo)簽（label）（由標(biāo)簽向量表示）。由多個(gè)描述對(duì)象的樣本數(shù)據(jù)構(gòu)成訓(xùn)練集（training set），在此訓(xùn)練集上，多標(biāo)簽分類的任務(wù)就是通過(guò)算法在訓(xùn)練集上的訓(xùn)練，得到一個(gè)分類模型，對(duì)于一個(gè)未知示例（unseen instance），該模型能夠根據(jù)未知示例的特征向量來(lái)預(yù)測(cè)該未知示例所擁有的標(biāo)簽集合。形式化地講，用代表原始維特征空間，表示用來(lái)描述樣本的屬性個(gè)數(shù)為；用代表與原始維特征空間相對(duì)應(yīng)的維標(biāo)簽空間，表示每個(gè)樣本可擁有個(gè)標(biāo)簽。假設(shè)代表由多個(gè)對(duì)象樣本構(gòu)成的訓(xùn)練集，其中樣本個(gè)數(shù)為，代表多標(biāo)簽樣本的特征向量，代表與當(dāng)前樣本相對(duì)應(yīng)的標(biāo)簽向量。對(duì)于一個(gè)樣本，如果該樣本擁有第個(gè)標(biāo)簽，則標(biāo)簽向量對(duì)應(yīng)第個(gè)位置為1，否則為0。多標(biāo)簽分類算法學(xué)習(xí)的目標(biāo)是：通過(guò)對(duì)樣本的特征空間（輸入空間）進(jìn)行挖掘，進(jìn)而學(xué)得從特征空間到標(biāo)簽空間（輸出空間）的映射，即，該映射關(guān)系即為分類器，通過(guò)應(yīng)用學(xué)得的映射關(guān)系，就能對(duì)未見(jiàn)示例進(jìn)行預(yù)測(cè)，判斷其所屬的標(biāo)簽集合。

在多標(biāo)簽分類中，隨著標(biāo)簽數(shù)量的增加，其標(biāo)簽輸出空間大小呈指數(shù)級(jí)增長(zhǎng)，即對(duì)擁有個(gè)類別標(biāo)簽的樣本集來(lái)說(shuō)，其輸出空間中標(biāo)簽子集規(guī)模為。為了應(yīng)對(duì)輸出空間如此巨大這種情況，提高多標(biāo)簽分類模型的健壯性和泛化性能，通常會(huì)利用標(biāo)簽之間的相關(guān)性。依照對(duì)標(biāo)簽之間相關(guān)關(guān)系利用程度的不同，可以把多標(biāo)簽分類算法分為三類：

1）一階算法（First-order algorithm）。這類算法沒(méi)有利用標(biāo)簽之間的相關(guān)性，通常是把原始的多標(biāo)簽分類問(wèn)題轉(zhuǎn)換為利用傳統(tǒng)分類算法進(jìn)行求解。此類算法通常為每個(gè)類別標(biāo)簽設(shè)計(jì)一個(gè)分類函數(shù)，如果訓(xùn)練樣本擁有標(biāo)簽，那么在學(xué)習(xí)與標(biāo)簽對(duì)應(yīng)的分類器時(shí)，該訓(xùn)練樣本可以視為關(guān)于標(biāo)簽的正樣本，反之被視為負(fù)樣本。這類算法的優(yōu)點(diǎn)是設(shè)計(jì)簡(jiǎn)單、思路清晰，方便理解，計(jì)算復(fù)雜度低；但由于此類算法在解決多標(biāo)簽分類任務(wù)的過(guò)程中，沒(méi)有利用標(biāo)簽之間的相關(guān)性關(guān)系，不利于分類精度的進(jìn)一步提高。BR算法和ML-KNN算法是一階算法的代表。

2）二階算法（Second-order algorithm）。這類算法利用兩兩標(biāo)簽之間的成對(duì)關(guān)系，通常就是利用樣本中相關(guān)標(biāo)簽和無(wú)關(guān)標(biāo)簽之間的排序關(guān)系［18-23］。具體來(lái)說(shuō)，如果訓(xùn)練集中某樣本擁有標(biāo)簽，但不擁有標(biāo)簽，那么算法模型對(duì)于該樣本關(guān)于標(biāo)簽產(chǎn)生的預(yù)測(cè)置信度值應(yīng)大于關(guān)于標(biāo)簽產(chǎn)生的預(yù)測(cè)置信度值。相較于一階算法，二階算法總體上會(huì)有更為優(yōu)異的表現(xiàn)；但是，通常僅考慮兩兩標(biāo)簽之間的關(guān)系，在實(shí)際應(yīng)用中有一定的局限性，因此考慮標(biāo)簽之間更高階關(guān)系的算法也大量出現(xiàn)。BP-MLL算法是二階算法的代表。

3）高階算法（High-order algorithm）。此類算法考慮更為高階的標(biāo)簽之間的任意關(guān)系，即當(dāng)前數(shù)據(jù)樣本集中當(dāng)前標(biāo)簽與其他剩余標(biāo)簽之間的相關(guān)關(guān)系或者此標(biāo)簽子集與其他任意標(biāo)簽子集之間的相關(guān)關(guān)系，這種對(duì)標(biāo)簽之間高階關(guān)系進(jìn)行建模的方式也更符合現(xiàn)實(shí)。但到目前為止，這類算法由于算法計(jì)算復(fù)雜度太高，存儲(chǔ)成本大，不能較好地推廣使用。CC算法及其擴(kuò)展算法是典型的高階算法。

1.2 非負(fù)矩陣分解

文獻(xiàn)［24］中給出了非負(fù)矩陣分解定義，其核心思想是對(duì)于任意一個(gè)給定的非負(fù)矩陣，利用非負(fù)矩陣分解（NMF）算法能夠?qū)⑵浞纸鉃閮蓚€(gè)規(guī)模更小的非負(fù)矩陣的乘積，其數(shù)學(xué)表達(dá)式為：

NMF算法由于算法本身的特點(diǎn)，能夠同時(shí)降低數(shù)據(jù)的維度和保留原始數(shù)據(jù)的主要特征，常被應(yīng)用到數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域。

1.3 稀疏表示

稀疏表示理論最早被應(yīng)用在信號(hào)處理領(lǐng)域［25］，主要是指信號(hào)中非零系數(shù)樣本數(shù)量遠(yuǎn)小于信號(hào)長(zhǎng)度，可以借助于少量的原子信號(hào)以線性的方式對(duì)原始信號(hào)進(jìn)行近似表示。人類視覺(jué)系統(tǒng)的感知過(guò)程為稀疏表示提供了依據(jù)，人類視覺(jué)系統(tǒng)上的神經(jīng)元只有極少數(shù)對(duì)于外界的不同刺激存在響應(yīng)。這種特性成為視覺(jué)系統(tǒng)對(duì)自然圖像高效編碼的策略，自然圖像能夠被結(jié)構(gòu)基元如邊緣和結(jié)構(gòu)等表示，得到的表示系數(shù)也是稀疏的［26］。

稀疏表示最初只是一種信號(hào)表示方式，用于解決信號(hào)處理領(lǐng)域的信號(hào)表示問(wèn)題。隨著稀疏表示在人臉識(shí)別［27］上的有效應(yīng)用，其在機(jī)器學(xué)習(xí)領(lǐng)域的應(yīng)用也變得更廣泛。宋相法等［28］提出了基于稀疏表示的多標(biāo)記學(xué)習(xí)算法，該算法利用訓(xùn)練集樣本對(duì)測(cè)試數(shù)據(jù)進(jìn)行稀疏重構(gòu)。關(guān)于稀疏表示，可以形式化為：

2 本文算法

2.1 符號(hào)說(shuō)明

2.2 標(biāo)簽空間分解

受文獻(xiàn)［29］啟發(fā)，本文提出了一種有效的將多標(biāo)簽輸出空間分解為低維潛在語(yǔ)義空間的方法。該低維空間保留了原始標(biāo)簽空間中大部分結(jié)構(gòu)信息，同時(shí)，又極大減少了空間中的噪聲和冗余信息。形式化地講，通過(guò)最小化以下重構(gòu)誤差，將多標(biāo)簽輸出空間分解為兩個(gè)低維非負(fù)矩陣和的乘積：

為了衡量原始待分解矩陣與分解后的兩個(gè)非負(fù)矩陣乘積之間的誤差，通常會(huì)定義損失函數(shù)，式（3）是基于歐氏距離的損失函數(shù)，最小化損失函數(shù)才能保證分解后的兩個(gè)矩陣的乘積盡可能逼近原始的待分解矩陣。因此，可以將非負(fù)矩陣的目標(biāo)函數(shù)優(yōu)化問(wèn)題描述為：

使用交替迭代法求解式（4）的乘性迭代規(guī)則可以描述為：

非負(fù)矩陣分解算法的具體步驟如算法1所示。

算法1 非負(fù)矩陣分解算法。

2.3 稀疏表示

2.4 二值標(biāo)簽映射為實(shí)值標(biāo)簽

2.5 多輸出回歸模型

通過(guò)上一步，將二值標(biāo)簽向量改造成實(shí)值標(biāo)簽之后，原來(lái)的多標(biāo)簽分類問(wèn)題就變成了多輸出回歸問(wèn)題，可以使用多輸出支持向量回歸（Multi-output Support Vector Regression， MSVR）［33］來(lái)建立模型。一般來(lái)說(shuō)，MSVR要最小化下面的目標(biāo)函數(shù)：

本文使用迭代加權(quán)最小二乘法（IteRative Weighted Least Square method，IRWLS）［34］對(duì)式（9）進(jìn)行求解。具體的，使用的一階泰勒展開(kāi)來(lái)構(gòu)造IRWLS過(guò)程，則經(jīng)過(guò)輪迭代后有：

通過(guò)以上步驟，最終完成了本文的MLNS多標(biāo)簽分類模型。在測(cè)試階段，即可通過(guò)該模型獲得測(cè)試樣本的預(yù)測(cè)輸出，其中為實(shí)值向量，表示預(yù)測(cè)該測(cè)試樣本具有每類標(biāo)簽的概率，而不再是簡(jiǎn)單地判斷有或無(wú)此類標(biāo)簽的問(wèn)題。本文采用閾值策略SCut設(shè)置閾值為，如果，則將標(biāo)簽設(shè)置為1，代表預(yù)測(cè)該測(cè)試樣本存在標(biāo)簽；否則為0，代表預(yù)測(cè)該測(cè)試樣本沒(méi)有該標(biāo)簽，完成對(duì)測(cè)試樣本的多標(biāo)簽分類。整體的MLNS如算法2所示。

算法2 MLNS算法。

下面對(duì)本文所提算法的復(fù)雜度進(jìn)行分析。MLNS在運(yùn)行過(guò)程中主要包括三個(gè)主要階段：非負(fù)矩陣分解、稀疏重構(gòu)和多輸出回歸。非負(fù)矩陣分解和稀疏重構(gòu)的時(shí)間復(fù)雜度為；在多輸出回歸中如果選擇多輸出支持向量回歸來(lái)實(shí)現(xiàn)分類，則時(shí)間復(fù)雜度為，因此總時(shí)間復(fù)雜度為。對(duì)于MLNS來(lái)說(shuō)，在空間開(kāi)銷方面，由于算法運(yùn)行過(guò)程中需要存儲(chǔ)、、、、、、、等矩陣，這些矩陣需要占用的內(nèi)存空間尺寸不超過(guò)、、、、、、、，因此總的算法空間復(fù)雜度為。由此可以看出，MLNS無(wú)論是時(shí)間復(fù)雜度（多項(xiàng)式的時(shí)間復(fù)雜度）還是空間復(fù)雜度都較小，在數(shù)據(jù)集樣本數(shù)不是特別大的情況下，由2.6 GHz處理器和4 GB內(nèi)存的單機(jī)即可完成實(shí)驗(yàn)。

3 實(shí)驗(yàn)和結(jié)果分析

3.1 數(shù)據(jù)集

本文實(shí)驗(yàn)共使用5個(gè)有代表性的數(shù)據(jù)集，涵蓋了4個(gè)領(lǐng)域：音頻、文本、圖像和生物學(xué)。所有這些數(shù)據(jù)資源都可以從MULAN和WEKA中收集到。表1給出了數(shù)據(jù)集的具體指標(biāo)：、和分別代表數(shù)據(jù)集的實(shí)例數(shù)、實(shí)例屬性維數(shù)和數(shù)據(jù)集標(biāo)簽個(gè)數(shù)；為平均標(biāo)簽個(gè)數(shù)；為標(biāo)簽密度。

表1 數(shù)據(jù)集屬性Tab. 1 Dataset properties

3.2 評(píng)價(jià)指標(biāo)

本文中，在5個(gè)多標(biāo)簽評(píng)價(jià)指標(biāo)上將MLNS和其他四個(gè)多標(biāo)簽學(xué)習(xí)方法進(jìn)行實(shí)驗(yàn)比較。這些評(píng)價(jià)指標(biāo)分為兩個(gè)類別：基于樣本的評(píng)價(jià)指標(biāo)和基于標(biāo)簽的評(píng)價(jià)指標(biāo)?；跇颖镜脑u(píng)價(jià)指標(biāo)是首先獲得算法在每個(gè)測(cè)試樣本上的度量值，然后返回算法在整個(gè)測(cè)試集的平均值。與基于樣本的評(píng)價(jià)指標(biāo)不同，基于標(biāo)簽的評(píng)價(jià)指標(biāo)首先獲得算法在每個(gè)標(biāo)簽上的度量值，然后返回所有標(biāo)簽上的宏/微觀平均F1值。

本文采用單誤差one?error、覆蓋度coverage、排序損失ranking loss、平均精度average precise和宏平均值Mac?F1進(jìn)行算法性能評(píng)價(jià)，其中Mac?F1是基于標(biāo)簽的度量，其余是基于樣本的評(píng)價(jià)指標(biāo)。設(shè)為多標(biāo)簽測(cè)試集，為標(biāo)簽屬于對(duì)應(yīng)實(shí)例的置信度。可以方便地轉(zhuǎn)變?yōu)闃?biāo)簽排名函數(shù)，即如果成立，則。5個(gè)評(píng)價(jià)指標(biāo)的定義如下。

1）單誤差one?error：

2）覆蓋度coverage：

3）排序損失ranking loss：

4）平均精度average precise：

3.3 對(duì)比算法

為了檢驗(yàn)MLNS的有效性，本文選擇了4種多標(biāo)簽分類算法MLBGM（Multi-Label classification Based on Gravitational Model）［35］、ML2（Multi-Label Manifold Learning）［36］、LIFT（multi-Label learning with label-specific FeaTures）［37］和MLRWKNN（Multi-Label classification based on the Random Walk graph and theK-Nearest Neighbor algorithm）［38］進(jìn)行對(duì)比實(shí)驗(yàn)。MLBGM算法通過(guò)運(yùn)用物理學(xué)經(jīng)典的引力模型并建立標(biāo)簽的正、負(fù)相關(guān)性矩陣來(lái)挖掘標(biāo)簽間不同的相關(guān)關(guān)系。實(shí)驗(yàn)中，本文使用MLBGM算法參數(shù)的默認(rèn)設(shè)置，即近鄰數(shù)。ML2是第一個(gè)嘗試在標(biāo)簽空間上探索流形的多標(biāo)簽分類算法。ML2的默認(rèn)參數(shù)取值分別為：，，。LIFT通過(guò)聚類的方式重新構(gòu)造標(biāo)簽相關(guān)特征集，以區(qū)分不同的標(biāo)簽，參數(shù)采用默認(rèn)設(shè)置為。MLRWKNN算法通過(guò)對(duì)測(cè)試實(shí)例的k近鄰樣本構(gòu)造隨機(jī)游走圖的頂點(diǎn)集和近鄰樣本標(biāo)簽間的相關(guān)邊集探索標(biāo)簽之間的依賴關(guān)系。實(shí)驗(yàn)中對(duì)于所有參數(shù)均采用默認(rèn)設(shè)置，即近鄰數(shù)，轉(zhuǎn)移概率，調(diào)整因子為最大樣本間歐氏距離。對(duì)于本文所提算法MLNS，參數(shù)設(shè)置為，，。

3.4 結(jié)果分析

本文實(shí)驗(yàn)硬件環(huán)境為：Intel Core i5-2400 CPU 3.10 GHz 4核，8 GB內(nèi)存。軟件環(huán)境為：Windows 10旗艦版，Eclipse 4.8.0，Matlab 2016a，jdk1.8.0_25-x64，Weka3.7.10，Mulan1.4.0。對(duì)于實(shí)驗(yàn)中的每個(gè)數(shù)據(jù)集，本文采用10折交叉驗(yàn)證方式。表2給出了不同算法在不同多標(biāo)簽數(shù)據(jù)集上的性能表現(xiàn)，具體來(lái)說(shuō)，表中記錄了不同算法在不同數(shù)據(jù)集上相應(yīng)評(píng)價(jià)指標(biāo)的平均值和標(biāo)準(zhǔn)差。對(duì)于每個(gè)評(píng)價(jià)指標(biāo)，“↓”表示值越小算法性能越好，“↑”表示值越大算法性能越好，最好的結(jié)果均做加粗處理。

表2 不同算法在多標(biāo)簽數(shù)據(jù)集上的性能（均值±標(biāo)準(zhǔn)差）Tab. 2 Performance of different algorithms on multi-label datasets （mean value±standard deviation）

本文使用基于算法排序的Friedman Test［39］來(lái)檢驗(yàn)算法是否具有統(tǒng)計(jì)意義上的顯著性差別。如果假設(shè)“所有算法的性能相同”被拒絕，則說(shuō)明算法的性能顯著不同。具體算法為：

從表3可以得到，“所有算法的性能相同”原假設(shè)在置信度水平為0.05的條件下被拒絕，因此進(jìn)行后續(xù)檢驗(yàn)Bonferroni-Dunn test［40］來(lái)進(jìn)一步區(qū)分各算法。一般認(rèn)為兩個(gè)算法的平均排序值之差超過(guò)一個(gè)臨界值域CD（Critical Difference）值時(shí)，則認(rèn)為兩個(gè)算法有顯著性不同。臨界值域CD可以表示如下：，其中，，顯著性水平0.05下的。MLNS及其對(duì)比算法的CD圖如圖1所示，橫軸數(shù)值代表每個(gè)算法在不同評(píng)價(jià)指標(biāo)下的平均排名，以實(shí)線相連的各算法在性能上沒(méi)有顯著差異。

表3 Friedman檢驗(yàn)和各項(xiàng)評(píng)價(jià)指標(biāo)的臨界值Tab. 3 Friedman test and critical value of each evaluation metric

通過(guò)上述實(shí)驗(yàn)結(jié)果的分析，可以得出以下結(jié)論：在one- error、coverage、ranking loss、average precise、Mac-F1這5個(gè)評(píng)價(jià)指標(biāo)上，本文所提MLNS平均排名值都是最優(yōu)的（平均排序越小，對(duì)應(yīng)算法性能越好），表明MLNS性能優(yōu)于其他對(duì)比算法。對(duì)于實(shí)驗(yàn)中的5個(gè)多標(biāo)簽數(shù)據(jù)集，在不同的5個(gè)評(píng)價(jià)指標(biāo)下，MLNS在50%的案例中排名第一，在76%的案例中排名前二，在全部的案例中排名前三，表明本文所提算法在完成多標(biāo)簽分類任務(wù)上具有優(yōu)于其他算法的性能，驗(yàn)證了本文所提算法通過(guò)將二值標(biāo)簽改造為實(shí)值標(biāo)簽再進(jìn)行多標(biāo)簽分類的有效性。在image數(shù)據(jù)集上，MLNS在所有評(píng)價(jià)指標(biāo)上的表現(xiàn)都是最好的，可以認(rèn)為MLNS更“偏好”圖像類數(shù)據(jù)集。

圖1 利用Bonferroni-Dunn test比較所提MLNS與其他算法Fig. 1 Comparison of proposed MLNS and other algorithms by Bonferroni-Dunn test

4 結(jié)語(yǔ)

為實(shí)現(xiàn)二值標(biāo)簽到實(shí)值標(biāo)簽的改造，提升多標(biāo)簽分類的效果，本文提出了一種新的多標(biāo)簽分類算法MLNS。該算法首先采用非負(fù)矩陣分解的方式來(lái)獲取標(biāo)簽的潛在語(yǔ)義信息，通過(guò)結(jié)合原始屬性特征構(gòu)造新的屬性特征，減少了標(biāo)簽變換中的信息損失；其次，基于稀疏表示學(xué)得示例樣本間的全局相似關(guān)系；然后，利用示例間關(guān)系，完成標(biāo)簽實(shí)值化改造；最后，將原始多標(biāo)簽分類問(wèn)題轉(zhuǎn)化為多輸出回歸問(wèn)題。實(shí)驗(yàn)結(jié)果表明，本文所提MLNS的性能優(yōu)于對(duì)比的其他多標(biāo)簽分類方法。接下來(lái)，我們將進(jìn)一步考慮將非負(fù)矩陣分解和多標(biāo)簽分類技術(shù)相結(jié)合構(gòu)造聯(lián)合優(yōu)化問(wèn)題的模型，以考慮更復(fù)雜的標(biāo)簽相關(guān)性。

[1] GIBAJA E， VENTURA S. A tutorial on multilabel learning ［J］. ACM Computing Surveys， 2015， 47（3）： Article No.52.

[2] LI C S， WEI F， YAN J C， et al. A self-paced regularization framework for multilabel learning ［J］. IEEE Transactions on Neural Networks and Learning Systems， 2018， 29（6）： 2660-2666.

[3] BURKHARDT S， KRAMER S. Online multi-label dependency topic models for text classification ［J］. Machine Learning， 2018， 107（5）： 859-886.

[4] BARUTCUOGLU Z， SCHAPIRE R E， TROYANSKAYA O G. Hierarchical multi-label prediction of gene function ［J］. Bioinformatics， 2006， 22（7）： 830-836.

[5] WEINER M F， LIPTON A M. The Dementias： Diagnosis，Treatment， and Research ［M］. 3rd ed. Washington， DC： American Psychiatric Association Publishing， 2003： 1-25.

[6] FU H Z， CHENG J， XU Y W， et al. Joint optic disc and cup segmentation based on multi-label deep network and polar transformation ［J］. IEEE Transactions on Medical Imaging， 2018， 37（7）： 1597-1605.

[7] ZHUANG N， YAN Y， CHEN S， et al. Multi-label learning based deep transfer neural network for facial attribute classification ［J］. Pattern Recognition， 2018， 80： 225-240.

[8] WU B Y， JIA F， LIU W， et al. Multi-label learning with missing labels using mixed dependency graphs ［J］. International Journal of Computer Vision，2018， 126（8）： 875-896.

[9] LIU A A， SHAO Z， WONG Y， et al. LSTM-based multi-label video event detection ［J］. Multimedia Tools and Applications， 2019，78（1）： 677-695.

[10] ZHANG M L， ZHOU Z H. A review on multi-label learning algorithms ［J］. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（8）： 1819-1837.

[11] BOUTELL M R， LUO J B， SHEN X P， et al. Learning multi-label scene classification ［J］. Pattern Recognition， 2004， 37（9）： 1757-1771.

[12] READ J， PFAHRINGER B， HOLMES G， et al. Classifier chains for multi-label classification ［J］. Machine Learning， 2011， 85（3）： 333-360.

[13] FüRNKRANZ J， HüLLEMEIER E. Pairwise preference learning and ranking ［C］// Proceedings of the 2003 European Conference on Machine Learning， LNCS 2837. Berlin： Springer， 2003： 145-156.

[14] FüRNKRANZ J， HüLLEMEIER E， LOZA MENCíA E， et al. Multilabel classification via calibrated label ranking ［J］. Machine Learning， 2008， 73（2）： 133-153.

[15] ELISSEEFF A， WESTON J. A kernel method for multi-labelled classification ［C］// Proceedings of the 2001 14th International Conference on Neural Information Processing Systems. Cambridge： MIT Press， 2001： 681-687.

[16] ZHANG M L， ZHOU Z H. ML-KNN： a lazy learning approach to multi-label learning ［J］. Pattern Recognition， 2007， 40（7）： 2038-2048.

[17] ZHANG M L， ZHOU Z H. Multilabel neural networks with applications to functional genomics and text categorization ［J］. IEEE Transactions on Knowledge and Data Engineering， 2006， 18（10）： 1338-1351.

[18] UEDA N， SAITO K. Parametric mixture models for multi-labeled text ［C］// Proceedings of the 2002 15th International Conference on Neural Information Processing Systems. Cambridge： MIT Press， 2002： 737-744.

[19] ZHU S H， JI X， XU W， et al. Multi-labelled classification using maximum entropy method ［C］// Proceedings of the 2005 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2005： 274-281.

[20] LOZA MENCíA E， FüRNKRANZ J. Efficient pairwise multilabel classification for large-scale problems in the legal domain ［C］// Proceedings of the 2008 Joint European Conference on Machine Learning and Knowledge Discovery in Databases， LNCS 5212. Berlin： Springer， 2008：50-65.

[21] HüLLERMEIER E， FüRNKRANZ J， CHENG W W， et al. Label ranking by learning pairwise preferences ［J］. Artificial Intelligence， 2008，172（16/17）： 1897-1916.

[22] GHAMRAWI N， McCALLUM A. Collective multi-label classification ［C］// Proceedings of the 2005 14th ACM International Conference on Information and Knowledge Management. New York： ACM， 2005： 195-200.

[23] ZHANG M L， ZHANG K. Multi-label learning by exploiting label dependency ［C］// Proceedings of the 2010 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2010： 999-1008.

[24] LEE D D， SEUNG H S. Algorithms for non-negative matrix factorization ［C］// Proceedings of the 2000 13th International Conference on Neural Information Processing Systems. Cambridge： MIT Press， 2000： 535-541.

[25] NYQUIST H. Certain topics in telegraph transmission theory ［J］.Proceedings of the IEEE， 2002， 90（2）： 280-305.

[26] OLSHAUSEN B A， FIELD D J. Sparse coding with an overcomplete basis set： a strategy employed by V1？ ［J］. Vision Research， 1997， 37（23）： 3311-3325.

[27] WRIGHT J， YANG A Y， GANESH A， et al. Robust face recognition via sparse representation ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2009， 31（2）： 210-227.

[28] 宋相法，焦李成.基于稀疏表示的多標(biāo)記學(xué)習(xí)算法［J］.模式識(shí)別與人工智能，2012，25（1）：124-129.（SONG X F， JIAO L C. A multi-label learning algorithm based on sparse representation ［J］. Pattern Recognition and Artificial Intelligence， 2012， 25（1）： 124-129.）

[29] PAPADIMITRIOU C H，RAGHAVAN P， TAMAKI H， et al. Latent semantic indexing： a probabilistic analysis ［J］. Journal of Computer and System Sciences， 2000， 61（2）： 217-235.

[30] DING C， LI T， PENG W， et al. Orthogonal nonnegative matrix tri-factorizations for clustering ［C］// Proceedings of the 2006 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2006： 126-135.

[31] TIBSHIRANI R. Regression shrinkage and selection via the lasso：a retrospective ［J］. Journal of the Royal Statistical Society， Series B （Statistical Methodology）， 2011， 73（3）： 273-282.

[32] BOYD S， PARIKH N， CHU E， et al. Distributed optimization and statistical learning via the alternating direction method of multipliers ［J］. Foundations and Trends in Machine Learning， 2010， 3（1）： 1-122.

[33] CHUNG W， KIM J， LEE H， et al. General dimensional multiple-output support vector regressions and their multiple kernel learning ［J］. IEEE Transactions on Cybernetics， 2015， 45（11）： 2572-2584.

[34] TUIA D， VERRELST J， ALONSO L， et al. Multioutput support vector regression for remote sensing biophysical parameter estimation ［J］. IEEE Geoscience and Remote Sensing Letters， 2011， 8（4）： 804-808.

[35] 李兆玉，王紀(jì)超，雷曼，等.基于引力模型的多標(biāo)簽分類算法［J］.計(jì)算機(jī)應(yīng)用，2018，38（10）：2807-2811， 2821.（LI Z Y， WANG J C， LEI M， et al. Multi-label classification algorithm based on gravitational model ［J］. Journal of Computer Application， 2018， 38（10）：2807-2811， 2821.）

[36] HOU P， GENG X， ZHANG M L. Multi-label manifold learning ［C］// Proceedings of the 2016 30th AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2016： 1680-1686.

[37] ZHANG M L， WU L. LIFT： multi-label learning with label-specific features ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2015，37（1）： 107-120.

[38] WANG Z W， WANG S K， WAN B T， et al. A novel multi-label classification algorithm based onK-nearest neighbor and random walk ［J］. International Journal of Distributed Sensor Networks， 2020， 16（3）： 1-17.

[39] DEM?AR J. Statistical comparisons of classifiers over multiple data sets ［J］. Journal of Machine Learning Research， 2006， 7： 1-30.

[40] DUNN O J. Multiple comparisons among means ［J］. Journal of the American Statistical Association， 1961，56（293）： 52-64.

Multi-label classification algorithm based on non-negative matrix factorization and sparse representation

BAO Yongchun1*， ZHANG Jianchen2， DU Shouxin1， ZHANG Junjun1

（1.School of Computer Science，Xi’an Polytechnic University，Xi’an Shaanxi710048，China；2.School of Computer and Information，Dezhou University，Dezhou Shandong253023，China）

Traditional multi-label classification algorithms are based on binary label prediction. However， the binary labels can only indicate whether the data has relevant categories， so that they contain less semantic information and cannot fully represent the label semantic information. In order to fully mine the semantic information of label space，a new Multi-Label classification algorithm based on Non-negative matrix factorization and Sparse representation （MLNS） was proposed. In the proposed algorithm，the non-negative matrix factorization and sparse representation technologies were combined to transform the binary labels of data into the real labels， thereby enriching the label semantic information and improving the classification effect. Firstly， the label latent semantic space was obtained by the non-negative matrix factorization of label space， and the label latent semantic space was combined with the original feature space to form a new feature space. Then， the global similarity relation between samples was obtained by the sparse coding of the obtained feature space. Finally，the binary label vectors were reconstructed by using the obtained similarity relation to realize the transformation between binary labels and real labels. The proposed algorithm was compared with the algorithms such as Multi-Label classification Based on Gravitational Model （MLBGM）， Multi-Label Manifold Learning （ML2）， multi-Label learning with label-specific FeaTures （LIFT） and Multi-Label classification based on the Random Walk graph and theK-Nearest Neighbor algorithm （MLRWKNN） on 5 standard multi-label datasets and 5 evaluation metrics. Experimental results show that， the proposed MLNS is better than the compared multi-label classification algorithms in multi-label classification， the proposed MLNS ranks top1 in 50% cases，top 2 in 76% cases and top 3 in all cases.

multi-label classification; non-negative matrix factorization; sparse representation; multiple output regression; machine learning

TP181

A

1001-9081（2022）05-1375-08

10.11772/j.issn.1001-9081.2021050706

2021?05?06；

2021?09?07；

2021?09?16。

西安市科技計(jì)劃項(xiàng)目（2020KJRC0027）。

包永春（1996—），男，山東菏澤人，碩士研究生，主要研究方向：機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、人工智能； 張建臣（1974—），男，山東微山人，副教授，碩士，主要研究方向：人工智能、大數(shù)據(jù)分析； 杜守信（1995—），男，山東菏澤人，碩士，主要研究方向：智能制造； 張軍軍（1994—）男，陜西咸陽(yáng)人，碩士，主要研究方向：人工智能、機(jī)器學(xué)習(xí)、深度學(xué)習(xí)。

This work is partially supported by Xi’an Science and Technology Program （2020KJRC0027）.

BAO Yongchun， born in 1996， M. S. candidate. His research interests include machine learning， data mining， artificial intelligence.

ZHAGN Jianchen， born in 1974， M. S.， associate professor. His research interests include artificial intelligence， big data analysis.

DU Shouxin， born in 1995， M. S. His research interests include intelligent manufacturing.

ZHANG Junjun， born in 1994， M. S. His research interests include artificial intelligence， machine learning， deep learning.