陳思寶，徐丹洋，羅 斌

一種非負稀疏近鄰表示的多標簽學(xué)習(xí)算法

陳思寶，徐丹洋，羅 斌

(安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院 合肥 230601)

針對訓(xùn)練數(shù)據(jù)中的非線性流形結(jié)構(gòu)以及基于稀疏表示的多標簽分類中判別信息丟失嚴重的問題，該文提出一種非負稀疏近鄰表示的多標簽學(xué)習(xí)算法。首先找到待測試樣本每個標簽類上的k-近鄰，然后基于LASSO稀疏最小化方法，對待測試樣本進行非負稀疏線性重構(gòu)，得到稀疏的非負重構(gòu)系數(shù)。再根據(jù)重構(gòu)誤差計算待測試樣本對每個類別的隸屬度，最后實現(xiàn)多標簽數(shù)據(jù)分類。實驗結(jié)果表明所提出的方法比經(jīng)典的多標簽k近鄰分類(ML-KNN)和稀疏表示的多標記學(xué)習(xí)算法(ML-SRC)方法性能更優(yōu)。

多標簽學(xué)習(xí); 稀疏近鄰表示; LASSO稀疏最小化; 非負重構(gòu)

多標簽數(shù)據(jù)在現(xiàn)實世界中廣泛存在。與傳統(tǒng)的單標簽數(shù)據(jù)不同，多標簽數(shù)據(jù)可以同時包含多個標簽。例如一張圖片中存在房屋、樹木、湖泊等多個景物，每類景物作為一個標簽可以為這張圖片貼上多個標簽。每個標簽可以作為一個單獨的類別，因此，多標簽數(shù)據(jù)可以同時被劃分到多個類別中，且比單標簽數(shù)據(jù)分類更為復(fù)雜。

早期有關(guān)多標簽數(shù)據(jù)分類的研究主要集中在文本數(shù)據(jù)方面[1-2]。近十年來，隨著圖像檢索、數(shù)據(jù)挖掘、標簽推薦等方面的發(fā)展，多標簽學(xué)習(xí)逐漸成為一個熱門的研究方向。目前，研究者們已提出了一些有效的多標簽學(xué)習(xí)算法。如文獻[3]提出的ML-KNN算法將傳統(tǒng)的k-近鄰算法和貝葉斯理論相結(jié)合，來實現(xiàn)多標簽數(shù)據(jù)的分類；文獻[4]聯(lián)合多個分類器，提出一套針對多標簽數(shù)據(jù)分類的整體方案，成功地對音樂流派進行多標簽分類；文獻[5]提出基于核的多標簽分類算法Rank-SVM，實現(xiàn)了對基因數(shù)據(jù)集的有效分類。

另一方面，稀疏表示與壓縮感知[6]也受到廣泛重視。其中，文獻[7]利用訓(xùn)練樣本稀疏線性表示待測試樣本，提出稀疏表示分類方法(SRC)，實現(xiàn)了高效并且魯棒的人臉識別；文獻[8]對稀疏系數(shù)加入非負性約束，將非負稀疏表示分類(non-negative SRC, NSRC)應(yīng)用于人臉識別；文獻[9]采用近鄰數(shù)據(jù)進行稀疏線性重構(gòu)，提出基于稀疏近鄰表示的分類(sparse neighbor representation dassification, SNRC)方法。文獻[10]將SRC算法應(yīng)用于多標簽數(shù)據(jù)分類,提出基于稀疏表示的多標記學(xué)習(xí)算法(ML-SRC)。

ML-SRC算法首先利用全部訓(xùn)練樣本在LASSO[11]稀疏最小化約束下線性表示待測試樣本，然后對稀疏系數(shù)的元素進行篩選，大于0的稀疏系數(shù)所對應(yīng)的訓(xùn)練樣本被認為與待測試樣本有正相關(guān)而被保留下來，小于0的系數(shù)被直接置0；最后，通過計算待測試樣本對于每個標簽類別的隸屬度來實現(xiàn)多標簽分類。然而，該算法用全部訓(xùn)練數(shù)據(jù)組成字典，給后面稀疏系數(shù)的計算帶來巨大的計算量，并且當訓(xùn)練數(shù)據(jù)中存在非線性流形結(jié)構(gòu)時，所得到的稀疏重構(gòu)及分類效果會受到嚴重影響。此外，將小于0的稀疏系數(shù)強制改為0，丟棄了稀疏系數(shù)中的所有負數(shù)，僅保留非負稀疏系數(shù)進行多標簽分類，導(dǎo)致稀疏重構(gòu)系數(shù)中判別信息的嚴重丟失，從而使得分類效果下降。

本文針對上述兩個現(xiàn)象，提出一種非負稀疏近鄰表示的多標簽學(xué)習(xí)算法(ML-NSNRC)。

1 相關(guān)方法

1.1 基于稀疏表示的多標簽數(shù)據(jù)分類

假設(shè)訓(xùn)練集包含n個多標簽訓(xùn)練樣本yi∈Rd，i=1,2,…,n ，T={1,2,…,L}為其所對應(yīng)的標簽集合。所有訓(xùn)練樣本拼成矩陣形式D=[y1, y2,…,yn]∈Rd×n，d＜n。根據(jù)訓(xùn)練樣本包含的標簽信息，構(gòu)造訓(xùn)練樣本yi的標簽信息bi，若yi包含標簽l，則令bli=1，否則令bli=0。構(gòu)造訓(xùn)練樣本矩陣D對應(yīng)的標簽矩陣B=[b1, b2,…,bn]∈RL×n。多標簽學(xué)習(xí)的目標是學(xué)習(xí)一個多標簽分類器h:y→2L,來對待測試樣本y所包含的標簽進行估計。ML-SRC利用訓(xùn)練集D稀疏線性重構(gòu)待測試樣本y：

式中，s表示稀疏線性重構(gòu)系數(shù)；0λ＞為調(diào)節(jié)參數(shù)。

ML-SRC[10]算法采用函數(shù)(,)fly來計算待測試樣本屬于每個標簽的隸屬度:

1.2 稀疏近鄰表示分類算法

稀疏近鄰表示分類算法(SNRC)[9]在訓(xùn)練集中先找到待測試樣本在每個類別上的k-近鄰，然后用每個類別的k-近鄰樣本數(shù)據(jù)對待測試樣本進行稀疏線性重構(gòu)，并根據(jù)其在每個類別上k-近鄰的重構(gòu)誤差最小對待測試樣本分類。

SNRC通過優(yōu)化目標函數(shù)is得到待測試樣本y的稀疏線性重構(gòu)系數(shù)：

式中，ψi表示待測試樣本y在訓(xùn)練樣本集D的第i類訓(xùn)練樣本上的k-近鄰樣本集合；i=1,2,…,c；c表示訓(xùn)練樣本集中的類別總數(shù)；調(diào)節(jié)參數(shù)λ＞0。根據(jù)每個類別的重構(gòu)誤差最小對待測試樣本進行分類。SNRC采用近鄰數(shù)據(jù)進行稀疏線性重構(gòu),可有效地避免訓(xùn)練數(shù)據(jù)中非線性流形結(jié)構(gòu)帶來的影響。

2 非負稀疏近鄰分類

借鑒SNRC采用近鄰數(shù)據(jù)進行稀疏線性重構(gòu)，可有效地避免訓(xùn)練數(shù)據(jù)中非線性流形結(jié)構(gòu)給稀疏線性重構(gòu)帶來的影響。同時借鑒非負稀疏表示分類[8]在優(yōu)化過程中直接限制其稀疏系數(shù)為非負，可使待測試樣本用局部近鄰數(shù)據(jù)進行凸的稀疏線性重構(gòu)。由此，本文提出非負稀疏近鄰分類(NSNRC)方法。

2.1 NSNRC目標函數(shù)

NSNRC算法通過KNN方法得到待測試樣本y在訓(xùn)練樣本集D的第i類上的k-近鄰樣本集ψi。將ψi作為基，對稀疏系數(shù)加入非負約束，得到待測試樣本y在ψi上的非負稀疏解：

當訓(xùn)練樣本集D存在非線性流形時，iψ可看成符合局部線性流形的訓(xùn)練樣本子集。加入非負性限制后，對局部近鄰數(shù)據(jù)點進行凸性重構(gòu)，進一步挖掘局部結(jié)構(gòu)信息，從而提高重構(gòu)效果。

2.2 NSNRC的優(yōu)化算法

由于NSNRC的目標函數(shù)式(4)是一個凸函數(shù)，因此可以證明存在全局最優(yōu)解。一般，全局最優(yōu)解可通過二次規(guī)劃或梯度下降得到。然而，梯度下降收斂較慢，二次規(guī)劃實施又比較復(fù)雜，因此采用類似文獻[12]提出的乘法迭代更新公式來求式(4)中的最優(yōu)非負稀疏重構(gòu)系數(shù):式中，1表示一個全為1的向量。當si中每個初始元素全部為正時，si中的元素在式(5)更新下的結(jié)果均是非負的。

2.3 算法收斂性分析

本文利用輔助函數(shù)對NSNRC的優(yōu)化算法進行收斂性分析。

那么F( si)的輔助函數(shù)可定義為：

引理1證明：顯然G(si, si)=F(si)成立，只需要證明。其中：

與式(8)比較，結(jié)果為：

為了證明式(10)的半正定性，只需考慮矩陣：

的半正定性。當且僅當M半正定時，K?ψΤψ也為半正定：

式(12)中證明了M的半正定性，由此可知式(10)也是半正定的，進而可知，因此引理1成立。

引理 2 如果G是一個輔助函數(shù)，那么目標函數(shù)F在以下更新中是非增的

則引理2成立。

根據(jù)引理2，利用梯度下降使輔助函數(shù)的導(dǎo)數(shù)為0，推導(dǎo)稀疏系數(shù)的更新規(guī)則：

解得：

因此，非負稀疏近鄰分類方法的目標函數(shù)可通過迭代優(yōu)化算法式(5)來求解。

2.4 算法復(fù)雜度分析

本文提出的NSNRC算法計算復(fù)雜度可通過分析式得到。式(5)中(ψi)Τy和(ψi)Τψi的計算復(fù)雜度分別為Ο(kd)和Ο(k2d)，其中，d為數(shù)據(jù)維數(shù)，k為待測試樣本y的近鄰數(shù)。優(yōu)化算法每一步的計算復(fù)雜度為Ο(2k+k2+k)。因此，NSNRC的計算復(fù)雜度為O(kd+k2d+t(3k+k2))，其中，t為優(yōu)化迭代次數(shù)。采用快速迭代收縮門限算法(fast iterative shrinkage-thresholding algorithm, FISTA)方法對SRC算法求其稀疏解，根據(jù)文獻[13]可得其計算復(fù)雜度為O(tn2d)，其中，n為訓(xùn)練樣本集D的樣本總數(shù)。

3 基于非負稀疏近鄰表示的多標簽分類

雖然基于稀疏表示的多標簽分類方法可以達到不錯的分類效果，但仍存在以下不足：1) 在求解標簽隸屬度時，ML-SRC對稀疏解中的負值進行的置0操作勢必導(dǎo)致稀疏解包含的判別信息嚴重丟失，從而對多標簽分類的結(jié)果造成一定影響；2) MLSRC在所有訓(xùn)練數(shù)據(jù)集上對待測試樣本進行稀疏表示。當訓(xùn)練數(shù)據(jù)集中存在非線性流形時，如果仍在所有訓(xùn)練數(shù)據(jù)上進行稀疏表示則會產(chǎn)生嚴重影響。本文提出的非負稀疏近鄰分類方法可有效解決以上兩個不足。

根據(jù)NSNRC的優(yōu)化算法，得到最優(yōu)非負稀疏重構(gòu)系數(shù)的優(yōu)化迭代公式：

式中，0t≥。

根據(jù)所求得的非負稀疏解來計算待測試樣本y對每個標簽類別的重構(gòu)誤差：

3.1 標簽隸屬度計算

根據(jù)y對應(yīng)各標簽上每類的重構(gòu)誤差，提出一個實值函數(shù)(,)gly來表示待測試樣本y屬于標簽l的隸屬度：

根據(jù)求得的隸屬度預(yù)測待測試樣本y的標簽集h(y)={l| g(y,l)＞p(y),l∈T}，其中，p( y)為閾值函數(shù)。

3.2 ML-NSNRC的算法流程

在ML-NSNRC算法中，待測試樣本y被其在訓(xùn)練集中各標簽的每一類上的k-近鄰集稀疏重構(gòu)。再通過稀疏重構(gòu)誤差來計算待測試樣本y屬于每個標簽類的隸屬度進而確定y的標簽集。算法流程為：

1) 輸入，訓(xùn)練樣本矩陣D=[y1, y2,…,yn]∈Rd×n及其對應(yīng)的標簽集信息B∈RL×n，待測試樣本y∈Rd；

2) 輸出，待測試樣本y的隸屬度g(y,l)和標簽集。

分為以下3個步驟：

1) 利用l1范數(shù)對D中每一列歸一化，通過KNN方法得到待測試樣本y在訓(xùn)練集中各標簽的每一類上的K-近鄰集，從而得到Ψ；

3) 根據(jù)求得的非負稀疏系數(shù)，利用式(20)和式(21)計算待測試樣本屬于每個標簽的隸屬度，進而確定y的標簽集。

4 實驗分析

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

為了驗證所提出的ML-NSNRC多標簽學(xué)習(xí)算法的性能，本文選取3個常用的多標簽數(shù)據(jù)集：自然場景數(shù)據(jù)集[3]、Yeast基因數(shù)據(jù)集和scene數(shù)據(jù)集[14]進行多標簽分類實驗。

1) 自然場景數(shù)據(jù)集

在自然場景數(shù)據(jù)集下，多標簽學(xué)習(xí)算法通過已標記的訓(xùn)練圖像對測試圖像的標簽集進行預(yù)測。該數(shù)據(jù)集包含了2 000張自然場景的圖像，其中每張圖像的標簽都已經(jīng)過人工交互判斷標定，標簽包括沙漠、山、海洋、日落、樹木。該數(shù)據(jù)集中超過22%的風(fēng)景圖像同時屬于多個類別，其中每張圖像的平均標簽個數(shù)為1.24±0.44個，每張圖像可表示為一個294維的特征向量。

2) Yeast基因數(shù)據(jù)集

多標簽學(xué)習(xí)算法通過分析Yeast基因集中已知功能的Yeast基因，對待測試樣本中的Yeast基因的功能進行標注。Yeast基因的功能類別被分為4層，本文實驗采用的文獻[5]中的方案，即僅僅使用頂層的功能類別。最終該數(shù)據(jù)集包含2 417個基因，共有14個類別，每個基因由一個103維的特征向量表示，每個基因的平均標簽個數(shù)為4.24±1.57個。

3) scene數(shù)據(jù)集

scene數(shù)據(jù)集[14]的任務(wù)是通過已知標簽集的訓(xùn)練圖像來預(yù)測待分類樣本圖像的標簽集。該數(shù)據(jù)集包含2 407張圖像，其中每張圖像包含落日、海灘、山川、原野、落葉、都市這6個標簽中的一個或多個，每張圖像可表示為一個294維的特征向量。

4.2 ML-NSNRC中參數(shù)初始化的影響

本文所提出的ML-NSNRC迭代更新算法需要對稀疏系數(shù)進行初始化，不同初始稀疏系數(shù)會對迭代更新算法的收斂性產(chǎn)生影響。為了測試參數(shù)初始化帶來的影響，分別采用全部平均1/n、絕對標準正態(tài)隨機分布隨機數(shù)|(0,1)|N、(0,1)均勻分布隨機數(shù)、絕對最小二乘解以及最小二乘解正部對稀疏系數(shù)初始化。圖1顯示了在自然場景數(shù)據(jù)集下，對所提出的ML-NSNRC算法采用5種不同的初始化方法，其目標函數(shù)值的迭代更新趨勢可看出，不同的參數(shù)初始化對ML-NSNRC迭代更新算法并未造成較大的影響，而且所提出的優(yōu)化方法收斂速度非常快。為了簡化算法并節(jié)省時間，將稀疏系數(shù)s的每個元素初始值設(shè)為1/n。

圖1 不同稀疏系數(shù)初始化對ML-NSNRC收斂性的影響

4.3 ML-NSNRC中近鄰數(shù)k的影響

用k-近鄰來近似表示數(shù)據(jù)中非線性流形的局部結(jié)構(gòu)時，近鄰數(shù)k的選擇至關(guān)重要。不同數(shù)據(jù)分布形狀及不同的數(shù)據(jù)采集密度都需要設(shè)置不同的近鄰數(shù)k。在ML-NSNRC中，近鄰數(shù)k值受到庫中每類標簽正負樣本個數(shù)的影響，如訓(xùn)練樣本集中標簽l的正樣本數(shù)為n1,負樣本數(shù)為n2，其中n1＜＜n2，那么k必須小于等于n1。為了測試不同近鄰數(shù)k對所提出的ML-NSNRC的影響，分別取近鄰數(shù)k為5的正整數(shù)倍，在scene數(shù)據(jù)集上進行多標簽學(xué)習(xí)。圖2顯示了ML-NSNRC和ML-KNN的平均分類精度隨著不同近鄰數(shù)k的變化情況。為了便于比較，將相同實驗配置下的ML-SRC和ML-NSRC的平均分類精度用水平線表示。從圖中可知當k取20時ML-NSNRC的平均精度達到較好水平，當k取5時ML-KNN的平均精度達到較好水平。

圖2 近鄰數(shù)k對ML-NSNRC和ML-KNN平均精度的影響

4.4 多標簽數(shù)據(jù)分類結(jié)果與分析

利用文獻[3]中的多標簽算法評價標準驗證本文所提出的算法的有效性。評價標準包括漢明損失、1-錯誤率、排序損失、覆蓋率、平均精度這5個方面，其中，平均精度的值越大表示多標簽算法越好，而其他4個標準則是值越小表示算法越好。在實施ML-SRC時對稀疏系數(shù)限制為非負，提出非負稀疏表示的多標簽學(xué)習(xí)算法(ML-NSRC)。為了進一步驗證本文算法的性能，將所提出的ML-NSNRC與3種多標簽學(xué)習(xí)算法進行比較。這3種算法分別是基于k-近鄰和傳統(tǒng)貝葉斯的多標簽學(xué)習(xí)算法ML-KNN、基于稀疏表示的多標記學(xué)習(xí)算法ML-SRC和基于非負稀疏表示的多標簽學(xué)習(xí)算法ML-NSRC。其中ML-KNN和ML-SRC均是當前多標簽學(xué)習(xí)領(lǐng)域效果最好的方法之一。ML-NSNRC實驗中非負稀疏系數(shù)求解的迭代次數(shù)為100次，自然場景數(shù)據(jù)集下k取400，Yeast數(shù)據(jù)集下k取5，scene數(shù)據(jù)集下k取20。

表1是4種多標簽學(xué)習(xí)算法在自然場景數(shù)據(jù)集上的性能比較?？煽闯?，在自然場景數(shù)據(jù)集上，本文所提出的算法在1-錯誤率、覆蓋率、排序損失和平均精度上比其他3種算法表現(xiàn)更佳。其中，漢明損失比ML-KNN低19.4%，覆蓋率比ML-KNN低14.7%，平均精度比ML-KNN高4.3%。

表1 4種多標簽學(xué)習(xí)算法在自然場景數(shù)據(jù)集上的性能比較

表2是4種多標簽學(xué)習(xí)算法在Yeast基因集上的性能比較，其中ML-SRC和ML-NSRC采用了十折交叉驗證的方法?？芍赮east基因集上，本文所提出的算法在漢明損失、覆蓋率、排序損失和平均精度這4個性能指標上比其他3種算法更佳。其中，漢明損失比ML-KNN降低18.5%，排序損失比ML-KNN降低9%，平均精度比ML-KNN和ML-SRC提高1.6%。

表2 4種多標簽學(xué)習(xí)算法在Yeast數(shù)據(jù)集上的性能比較

表3是4種多標簽學(xué)習(xí)算法在scene數(shù)據(jù)集上的性能比較?？芍疚乃惴ㄔ诟黜椫笜松隙純?yōu)于其他3種算法。其中，本文算法的漢明損失比ML-KNN和ML-SRC分別降低18.2%和21.4%，覆蓋率比MLKNN降低32.6%，平均精度比ML-KNN和ML-SRC分別提高了4.3%和5.6%。

表3 4種多標簽學(xué)習(xí)算法在scene數(shù)據(jù)集上的性能比較

通過比較自然場景圖像數(shù)據(jù)集、Yeast基因數(shù)據(jù)集以及scene數(shù)據(jù)集上的實驗結(jié)果可知，本文所提出的ML-NSNRC算法在分類精確度上比ML-KNN、ML-SRC、ML-NSRC算法均有明顯提高，在其他4項指標上也表現(xiàn)出較好的水平。本文所提出的算法結(jié)合了非負稀疏表示的有效鑒別能力，和k-近鄰方法對非線性流形數(shù)據(jù)集的局部線性整理，可以有效解決多標簽數(shù)據(jù)分類問題。

5 結(jié) 束 語

本文提出了一種非負稀疏近鄰表示分類算法(NSNRC)，將其成功地應(yīng)用到多標簽數(shù)據(jù)分類中，并提出一種非負稀疏近鄰表示分類的多標簽學(xué)習(xí)算法ML-NSNRC。將待測試樣本在訓(xùn)練樣本每一類中的k-近鄰作為待測試樣本的訓(xùn)練樣本基，并在稀疏編碼過程中對稀疏系數(shù)加入非負性限制。該算法有效克服了非線性流形數(shù)據(jù)對算法的影響，并且得到了全為非負值的稀疏系數(shù)，從而為數(shù)據(jù)的標簽分類保留了更多的判別信息。提出一種快速優(yōu)化迭代求解算法，并給出其收斂到全局最優(yōu)的證明。在自然場景圖像、Yeast基因、scene這3個數(shù)據(jù)集上的實驗結(jié)果表明，所提出的算法在性能上優(yōu)于其他經(jīng)典算法，符合預(yù)期目標。下一階段需要尋求更優(yōu)的稀疏模型，進一步提高多標簽分類效果。

[1] SCHAPIRE R E, SINGER Y. Boostexter: a boosting-based system for text categorization[J]. Machine Learning, 2000, 39(2-3): 135-168.

[2] UEDA N, SAITO K. Parametric mixture models for multi-label text[J]. Advances in Neural Information Processing, 2003(15): 721-728.

[3] ZHANG M L, ZHOU Z H. ML-KNN: a lazy learning approach to multi-label learning[J]. Pattern Recognition, 2007, 40(7): 2038-2048.

[4] 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. New York: ACM, 2011: 705-714.

[5] ELISSEEFF A, WESTON J. A kernel method for multilabelled classification[J]. Advances in Neural Information Processing, 2002(14): 681-687.

[6] CANDèS E J, ROMBERG J, TAO T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2): 489-509.

[7] 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.

[8] JI Y, LIN T, ZHA H. Mahalanobis distance based nonnegative sparse representation for face recognition[C]// International Conference on Machine Learning and Applications. Miami, FL: IEEE, 2009: 41-46.

[9] HUI K, LI C, ZHANG L. Sparse neighbor representation for classification[J]. Pattern Recognition Letters, 2012, 33(5): 661-669.

[10] 宋相法, 焦李成. 基于稀疏表示的多標記學(xué)習(xí)算法[J].模式識別與人工智能, 2012, 25(1): 124-129. SONG Xiang-fa, JIAO Li-cheng. A multi-label learning algorithm based on sparse representation[J]. Pattern Recognition and Artificial Intelligence, 2012, 25(1): 124-129.

[11] TIBSHIRANI R. Regression shrinkage and selection via the lasso[J]. Journal of the Royal Statistical Society (Series B, Methodological), 1996, 58(1): 67-88.

[12] LEE D D, SEUNG H S. Algorithms for non-negative matrix factorization[J]. Advances in Neural Information Processing, 2001(2): 556-562.

[13] BECK A, TEBOULLE M. A fast iterative shrinkagethresholding algorithm for linear inverse problems[J]. SIAM Journal on Imaging Sciences, 2009, 2(1): 183-202.

[14] BOUTELL M R, LUO J, SHEN X, et al. Learning multi-label scene classification[J]. Pattern Recognition, 2004, 37(9): 1757-1771.

編 輯 葉 芳

A Non-Negative Sparse Neighbor Representation for Multi-Label Learning Algorithm

CHEN Si-bao, XU Dan-yang, and LUO Bin

(School of Computer Science and Technology, Anhui University Hefei 230601)

In order to avoid the influence of the nonlinear manifold structure in training data and preserve more discriminant information in the sparse representation based multi-label learning, a new multi-label learning algorithm based on non-negative sparse neighbor representation is proposed. First of all, the k-nearest neighbors among each class are found for the test sample. Secondly, based on non-negative the least absolute shrinkage and selectionator operator (LASSO)-type sparse minimization, the test sample is non-negative linearly reconstructed by the k-nearest neighbors. Then, the membership of each class for the test sample is calculated by using the reconstruction errors. Finally, the classification is performed by ranking these memberships. A fast iterative algorithm and its corresponding analysis of converging to global minimum are provided. Experimental results of multi-label classification on several public multi-label databases show that the proposed method achieves better performances than classical ML-SRC and ML-KNN.

LASSO sparse minimization; multi-label learning; non-negative reconstruction; sparse neighbor representation

TP391.4

A

10.3969/j.issn.1001-0548.2015.06.018

2014 ? 04 ? 22；

2015 ? 06 ? 12

國家863項目(2014AA015104)；國家自然科學(xué)基金(61202228，61472002)；安徽省高校自然科學(xué)研究重點項目(KJ2012A004)作者簡介：陳思寶(1979 ? )，男，副教授，主要從事模式識別和圖像處理方面的研究.