一種非負稀疏近鄰表示的多標簽學習算法

陳思寶，徐丹洋，羅 斌

一種非負稀疏近鄰表示的多標簽學習算法

陳思寶，徐丹洋，羅 斌

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

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

多標簽學習; 稀疏近鄰表示; LASSO稀疏最小化; 非負重構

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

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

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

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

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

1 相關方法

1.1 基于稀疏表示的多標簽數據分類

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

式中，s表示稀疏線性重構系數；0λ＞為調節參數。

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

1.2 稀疏近鄰表示分類算法

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

SNRC通過優化目標函數is得到待測試樣本y的稀疏線性重構系數：

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

2 非負稀疏近鄰分類

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

2.1 NSNRC目標函數

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

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

2.2 NSNRC的優化算法

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

2.3 算法收斂性分析

本文利用輔助函數對NSNRC的優化算法進行收斂性分析。

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

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

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

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

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

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

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

則引理2成立。

根據引理2，利用梯度下降使輔助函數的導數為0，推導稀疏系數的更新規則：

解得：

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

2.4 算法復雜度分析

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

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

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

根據NSNRC的優化算法，得到最優非負稀疏重構系數的優化迭代公式：

式中，0t≥。

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

3.1 標簽隸屬度計算

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

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

3.2 ML-NSNRC的算法流程

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

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

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

分為以下3個步驟：

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

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

4 實驗分析

4.1 實驗數據簡介

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

1) 自然場景數據集

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

2) Yeast基因數據集

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

3) scene數據集

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

4.2 ML-NSNRC中參數初始化的影響

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

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

4.3 ML-NSNRC中近鄰數k的影響

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

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

4.4 多標簽數據分類結果與分析

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

表1是4種多標簽學習算法在自然場景數據集上的性能比較。可看出，在自然場景數據集上，本文所提出的算法在1-錯誤率、覆蓋率、排序損失和平均精度上比其他3種算法表現更佳。其中，漢明損失比ML-KNN低19.4%，覆蓋率比ML-KNN低14.7%，平均精度比ML-KNN高4.3%。

表1 4種多標簽學習算法在自然場景數據集上的性能比較

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

表2 4種多標簽學習算法在Yeast數據集上的性能比較

表3是4種多標簽學習算法在scene數據集上的性能比較。可知本文算法在各項指標上都優于其他3種算法。其中，本文算法的漢明損失比ML-KNN和ML-SRC分別降低18.2%和21.4%，覆蓋率比MLKNN降低32.6%，平均精度比ML-KNN和ML-SRC分別提高了4.3%和5.6%。

表3 4種多標簽學習算法在scene數據集上的性能比較

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

5 結 束 語

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

[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] 宋相法, 焦李成. 基于稀疏表示的多標記學習算法[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)；國家自然科學基金(61202228，61472002)；安徽省高校自然科學研究重點項目(KJ2012A004)作者簡介：陳思寶(1979 ? )，男，副教授，主要從事模式識別和圖像處理方面的研究.