一種新的多標記特征提取方法

張居杰，方 敏，郭 錦

(1. 西安電子科技大學 計算機學院，陜西 西安 710071; 2. 西北工業(yè)大學 計算機學院，陜西 西安 710072; 3. 西安工業(yè)大學 電子信息工程學院，陜西 西安 710021)

?

一種新的多標記特征提取方法

張居杰1，方 敏1，郭 錦2,3

(1. 西安電子科技大學 計算機學院，陜西 西安 710071; 2. 西北工業(yè)大學 計算機學院，陜西 西安 710072; 3. 西安工業(yè)大學 電子信息工程學院，陜西 西安 710021)

針對已有多標記特征提取方法并未充分利用特征信息的問題，提出了基于希爾伯特-施密特獨立標準和主成分分析的多標記特征提取方法．該方法通過使標記與降維后特征之間希爾伯特-施密特范數(shù)達到最大，以充分利用標記知識;同時利用主成分分析，以盡量減少特征提取過程中的協(xié)方差信息損失．通過在Yahoo數(shù)據(jù)集上的實驗表明，該算法的性能優(yōu)于主成分分析和當前3種主要的多標記特征提取方法，驗證了該算法的有效性．

多標記分類;特征提取;希爾伯特-施密特獨立標準;主成分分析

由于多標記分類問題在圖像標注、文本分類、基因功能分析和音樂理解等方面的應用中廣泛出現(xiàn)，多標記學習目前已成為機器學習領(lǐng)域中的一個研究熱點[1-3]． 傳統(tǒng)的分類問題(二分類或者多分類)中一個示例通常只與一個標記相關(guān)，而多標記學習問題中每一個示例可與多個標記相關(guān)聯(lián)．多標記分類問題與傳統(tǒng)的二分類或者多分類的主要區(qū)別是，多標記分類問題中可利用標記之間的關(guān)系提高分類性能[1]．而與傳統(tǒng)分類問題類似，多標記學習問題也面臨著高維特征帶來的挑戰(zhàn)．目前，多標記問題的特征降維已經(jīng)成為多標記學習研究中的一個熱點．

特征降維主要有兩方面的作用：首先，高維特征容易導致過擬合，即在訓練集上能得到較好的分類效果，而在測試數(shù)據(jù)集上卻無法得到理想的分類效果．通過降低特征維度，能夠解決過擬合問題，從而提高后續(xù)訓練模型的預測能力；其次，利用高維特征進行運算消耗的時間更多、存儲量更大，無法進行高效的訓練和測試．因此，為能夠進行更快速的訓練和測試，需要降低特征維度．特征降維方法可以分為兩類: 特征提取和特征選擇．與特征選擇相比，利用某種變換方法，特征提取能夠得到更有用的低維特征．目前，已有很多傳統(tǒng)的特征提取方法，如主成分分析(Principal Component Analysis，PCA)[4]、線性判別分析(Linear Discriminant Analysis，LDA)[5]等．但是，對多標記學習問題中的特征提取方法的研究才剛剛開始．

文獻[6]將無監(jiān)督的潛在語義索引(Latent Semantic Indexing，LSI)[7]與標記信息結(jié)合，提出了多標記潛在語義索引(Multi-label Latent Semantic Indexing，MLSI)．其利用加權(quán)的方式將特征信息和標記信息構(gòu)建目標函數(shù)．該方法考慮了同時利用特征信息和標記信息，但降維的效果對權(quán)重因子很敏感，很難找到一個恰當?shù)臋?quán)重因子．文獻[8]在最小二乘法的基礎(chǔ)上設(shè)計了一種多標記特征提取方法，然而由于其主要目標是分類，并不是為特征降維而設(shè)計，這種方法很容易產(chǎn)生過擬合問題．文獻[9]中的方法直接將LDA方法應用于多標記特征降維問題上，并沒有有效利用標記關(guān)系．而標記關(guān)系在多標記分類中起著很重要的作用[10-13]．文獻[14]提出了多標記線性判別分析(Multi-label Linear Discriminant Analysis，MLDA)方法，在LDA的基礎(chǔ)上利用了多個標記之間的關(guān)系，但其性能受制于標記的數(shù)目．文獻[15]基于希爾伯特-施密特獨立標準(Hilbert-Schmidt Independence Criterion，HSIC)[16]提出了基于最大化依賴的多標記維度約簡方法(Multi-label Dimensionality reDuction via Maximum dependence，MDDM)．MDDM通過使得標記核矩陣和特征提取后對應的示例核矩陣之間的希爾伯特-施密特范數(shù)(Hilbert-Schmidt norm)最大，以最大化兩者之間的依賴關(guān)系，得到有效的線性投影矩陣．然而，該矩陣并沒有充分獲取特征信息，也沒有考慮特征之間的內(nèi)在聯(lián)系．

上述幾種多標記特征提取方法并沒有充分利用特征和標記中的信息．為此，筆者提出了基于希爾伯特-施密特獨立標準(Hilbert-Schmidt Independence Criterion，HSIC)和主成分分析的多標記特征提取方法．一方面，按照MDDM的思想，基于HSIC，使得降維后的特征與標記之間的依賴關(guān)系最大化; 另一方面，基于PCA，利用特征之間的聯(lián)系，盡可能地減少降維過程中的協(xié)方差信息損失．在Yahoo數(shù)據(jù)集的11個子數(shù)據(jù)集上對所提出的算法進行了驗證．

1 基于HSIC和PCA的多標記特征提取算法

Gretton等提出來的HSIC，通過計算兩組變量協(xié)方差算子的希爾伯特-施密特范式，來衡量兩組變量之間的獨立性[16]．基于數(shù)據(jù)集D，HSIC的經(jīng)驗估計可表示為

HSIC已經(jīng)成功應用于特征選擇[17]、有監(jiān)督特征提取[18]和無監(jiān)督特征提取[19]等．MDDM將其應用于多標記特征提取．對于示例核矩陣K采用了線性核，忽略掉常數(shù)項 (N-1)-2，得到的目標函數(shù)為

其中，P∈Rd×t，是線性變換矩陣，t

PCA通過對樣本協(xié)方差矩陣進行分析，挖掘特征之間的相關(guān)性，尋找一組能最大程度保留協(xié)方差中的信息的主成分．PCA要優(yōu)化的目標是:

其中，·F表示矩陣的Frobenius范式．

目前，PCA已經(jīng)得到了廣泛的應用[4]．

現(xiàn)有的多標記特征提取方法并不能充分利用特征信息，為此，文中提出的方法希望既能夠有效利用標記信息，又能夠充分利用特征信息．一方面，為利用標記信息，新算法基于HSIC，采用了與MDDM相同的目標函數(shù)式(2)，即希望 X P 與標記Y之間的依賴性達到最大;另一方面，為盡可能減少降維過程中特征信息的損失，采用PCA的目標函數(shù)式(3)．將兩者結(jié)合成一個目標函數(shù)，即

式(4)既能夠最大化降維后的特征X P與標記Y之間的依賴性，又能夠使特征信息的損失達到最小．

為求解式(4)，令

算法的流程中，maxitr表示最大迭代次數(shù)，ε為誤差．在第步中給定Pm，可將其代入式(5)獲得λm+1(P)．第～步，固定λm(P)，求解Pm．式(5)可寫作 tr(PTXTH L H X P)-．則可通過優(yōu)化下式求解Pm，即

根據(jù)式(6)，為獲得Pm，可對XT(H L H+λm(P) H) X進行SVD分解，XT(H L H+ λm(P) H) X= U Σ UT，其中，U UT= UTU= Id，Σ為一對角矩陣，Σ= diag{σ1，σ2，…，σd}且 σ1≥ σ2≥ …≥ σd．則Pm由U的前t列構(gòu)成．

該算法收斂性的證明方法可見文獻[20]．實驗過程中發(fā)現(xiàn)，該算法收斂很快，其與MDDM的主要區(qū)別是，該算法既能夠充分利用標記知識，又能充分保留特征的協(xié)方差信息．此外，由式(6)可發(fā)現(xiàn)，下面形式的目標函數(shù)可認為是上述算法求解過程中的一個步驟:

即式(7)的解只是式(4)解的一個中間解．而且式(7)中λ對特征提取效果很重要，往往需要反復地調(diào)參才能找到一個合適的值，而式(4)并不需要這樣的調(diào)參過程．

2 算法驗證

為驗證文中提出算法的有效性，將文中算法與MLSI、MLDA、MDDM以及PCA進行了比較，降維后的

表1 實驗中數(shù)據(jù)集的相關(guān)信息

圖1 各算法在Yahoo子數(shù)據(jù)集上隨降維維度變化的性能對比

分類模型采用LIBSVM工具包里的默認支持向量機(Support Vector Machine，SVM)[21]．按照文獻[14]中設(shè)置MLSI的權(quán)重因子為0.5．MDDM和文中所提出算法中的標記核矩陣采用線性核函數(shù)進行計算．實驗采用的數(shù)據(jù)集為Yahoo數(shù)據(jù)集的11個子數(shù)據(jù)集[15]，表1給出了它們的相關(guān)信息．所有數(shù)據(jù)集均有 5 000 個樣本，其中 2 000 個用作訓練，3 000 個用作測試[15]．表1中，d表示特征維度，C表示標簽數(shù)目．

實驗中設(shè)置t值是以2為間隔，從2逐漸增加到60．測試基于幾種降維算法的SVM模型的預測性能，性能評估采用漢明距離(Hamming loss)[1]．圖1給出了各算法在Yahoo的11個子數(shù)據(jù)集上隨t變化時的實驗結(jié)果．

從圖1中可以看出，雖然PCA并沒有利用標記信息，但其可有效利用特征中的協(xié)方差信息，取得了適中的性能，這也表明了有效利用特征協(xié)方差信息的重要性．MLDA的性能最差，這是由于其性能受標記數(shù)目的影響，當 t?L 時，其能取得尚可的性能;但是隨著t趨近甚至大于L時，其性能甚至可能變差．MLSI的性能有時比PCA的性能好，有時比PCA的性能差，這是因為MLSI嚴重依賴權(quán)重因子，而且簡單地將特征信息和標記信息進行簡單的相加，其并不是利用標記知識的好方式．

與前述3種算法相比，MDDM和文中提出的算法的性能在11個Yahoo子數(shù)據(jù)集上都能取得更好的性能，這是由于HSIC能夠充分挖掘標記和特征之間的關(guān)聯(lián)關(guān)系; 而相比MDDM，新算法能獲得相當或者更優(yōu)的效果，這是由于在充分利用標記知識的同時，保留了特征內(nèi)部的協(xié)方差信息，更加充分地利用了特征．

3 結(jié) 束 語

為有效提高多標記特征提取方法的性能，充分利用特征和標記中的信息，文中提出的算法一方面利用HSIC能充分挖掘兩組變量關(guān)系的能力，使提取的特征與標記之間的依賴性達到最大; 另一方面PCA能利用不相關(guān)的特征進行數(shù)據(jù)重建的能力，使提取過程中特征的協(xié)方差矩陣中的信息損失最小．將兩者結(jié)合進一個目標函數(shù)中，并給出了一種有效的優(yōu)化方法獲得最優(yōu)投影矩陣．實驗結(jié)果表明，與現(xiàn)有的多標記特征提取方法相比，文中提出的特征提取方法能取得更優(yōu)的性能．

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

[2]TSOUMAKAS G, KATAKIS I. Multi-label Classification: an Overview [J]. International Journal of Data Warehousing and Mining, 2007, 3(3): 1-13.

[3]ZHANG J J, FANG M, LI X. Multi-label Learning with Discriminative Features for Each Label [J]. Neurocomputing, 2015, 154: 305-316.

[4]JOLLIFFE J T. Principal Component Analysis [M]. Berlin: Springer, 2001: 1-9.

[5]HASTIE T, TIBSHIRANI R, FRIEDMAN J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction [M]. 2nd Edition. New York: Springer, 2009: 106-113.

[6]YU K, YU S, TRESP V. Multi-label Informed Latent Semantic Indexing [C]//Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2005: 258-265.

[7]DEERWESTER S C, DUMAIS S T, FUMAS G W, et al. Indexing by Latent Semantic Analysis [J]. Journal of the American Society for Information Science, 1990, 41(6): 391-407.

[8]JI S, TANG L, YU S, et al. A Shared-subspace Learning Framework for Multi-label Classification [J]. ACM Transactions on Knowledge Discovery from Data, 2010, 4(2): 1-29.

[9]PARK C H, LEE M. On Applying Linear Discriminant Analysis for Multi-label Problems [J]. Pattern Recognition Letters, 2008, 29(7): 878-887.

[10]YU Y, PEDRYCZ W, MIAO D. Multi-label Classification by Exploiting Label Correlations [J]. Expert Systems with Applications, 2014, 41(6): 2989-3004.

[11]XU J. Multi-label Core Vector Machine with a Zero Label [J]. Pattern Recognition, 2014, 47(7): 2542-2557.

[12]LI P, LI H, WU M. Multi-label Ensemble Based on Variable Pairwise Constraint Projection [J]. Information Sciences, 2013, 222: 269-281.

[13]ENRIQUE SUCAR L,BIELZA C, MORALES E F, et al. Multi-label Classification with Bayesian Network-based Chain Classifiers [J]. Pattern Recognition Letters, 2014, 41(1): 14-22.

[14]WANG H, DING C, HUANG H. Multi-label Linear Discriminant Analysis [C]//Lecture Notes in Computer Science: 6316 LNCS, PART 6. Berlin: Springer Verlag, 2010: 126-139.

[15]GRETTON A, BOUSQUET O, SMOLA A, et al. Measuring Statistical Dependence with Hilbert-Schmidt Norms [C]//Lecture Notes in Artificial Intelligence: 3734 LNAI. Berlin: Springer Verlag, 2005: 63-77.

[16]ZHANG Y, ZHOU Z H. Multi-label Dimensionality Reduction via Dependence Maximization [C]//Proceedings of the National Conference on Artificial Intelligence: 3. Menlo Park: AAAI, 2008: 1503-1505.

[17]SONG L, SMOLA A, GRETTON A, et al. Feature Selection via Dependence Maximization [J]. Journal of Machine Learning Research, 2012, 13: 1393-1434.

[18]CHANG B, KRUGER U, KUSTRA R, et al. Canonical Correlation Analysis Based on Hilbert-Schmidt Independence Criterion and Centered Kernel Target Alignment [C]//30th International Conference on Machine Learning: 2. Princeton: IMLS, 2013: 975-983.

[19]WANG M, SHA F, JORDAN M I. Unsupervised Kernel Dimension Reduction [C]//Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Red Hook: Curran Associates Incorporated, 2010: 2379-2387.

[20]WANG H, YAN S, XU D, et al. Trace Ratio vs. Ratio Trace for Dimensionality Reduction [C]//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE, 2007: 108-115.

[21]CHANG C C, LIN C J. LIBSVM: a Library for Supporting Vector Machines [J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(3): 1-27.

(編輯：齊淑娟)

New method for multi-label feature extraction

ZHANGJujie1，F(xiàn)ANGMin1，GUOJin2,3

(1. School of Computer Science and Technology, Xidian Univ., Xi’an 710071, China; 2. School of Computer Science and Engineering, Northwestern Polytechnical Univ., Xi’an 710072, China; 3. College of Electronical and Information Engineering, Xi’an Technological Univ., Xi’an 710021, China)

Existing multi-label feature extraction methods are limited by not fully exploiting feature information. To tackle this problem， this paper proposes a new method for multi-label feature extraction. First, it maximizes the Hilbert-Schmidt independence criterion (HSIC) between labels and the features after reducing dimensionality to exploit label information, while it minimizes the information loss using principal component analysis (PCA). Experiments across Yahoo demonstrate the effectiveness and superiority of the proposed method to PCA and 3 state-of-art multi-label feature extraction methods.

multi-label classification; feature extraction; Hilbert-Schmidt independence criterion; principal component analysis

2015-09-07

時間：2016-04-01

國家自然科學基金資助項目(61472305, 61070143)；陜西省科學研究發(fā)展計劃資助項目(2015GY027)；航空科學基金資助項目(20151981009)

張居杰(1987-)，男，西安電子科技大學博士研究生，E-mail：jujiezhang@stu.xidian.edu.cn．

方 敏(1965-)，女，教授，E-mail：mfang@mail.xidian.edu.cn．

http://www.cnki.net/kcms/detail/61.1076.tn.20160401.1622.022.html

10.3969/j.issn.1001-2400.2016.06.011

TP391.4

A

1001-2400(2016)06-0062-06