蔡志鈴，祝 峰

閩南師范大學 粒計算重點實驗室，福建 漳州 363000

非負稀疏表示的多標簽特征選擇*

蔡志鈴，祝 峰+

閩南師范大學 粒計算重點實驗室，福建 漳州 363000

+Corresponding author:E-mail:w illiam fengzhu@gmail.com

CAIZhiling,ZHUW illiam.M ulti-label feature selection via non-negative sparse representation.Journal of FrontiersCom puter Scienceand Technology,2017,11(7)：1175-1182.

在多標簽學習中，數(shù)據(jù)降維是一項重要而又具有挑戰(zhàn)性的任務(wù)。特征選擇是一種高效的數(shù)據(jù)降維技術(shù)，它通過保持最大相關(guān)信息選取一個特征子集。通過對子空間學習的研究，提出了基于非負稀疏表示的多標簽特征選擇方法。該方法可以看成是矩陣分解問題，其融合了非負約束問題和L2,1-范數(shù)最小優(yōu)化問題。設(shè)計了一種高效的矩陣更新迭代算法求解新問題，并證明其收斂性。最后，對6個實際的數(shù)據(jù)集進行了測試，實驗結(jié)果證明了算法的有效性。

1 引言

高維數(shù)據(jù)中存在著許多冗余或不相關(guān)的特征，從而面臨著維數(shù)災(zāi)難問題。一方面需要較高的計算時間和空間；另一方面容易給分類帶來不利之處，例如過擬合。因此數(shù)據(jù)降維是機器學習中一項重要而又具有挑戰(zhàn)性的任務(wù)。數(shù)據(jù)降維主要分為特征提取和特征選擇，前者是把原始特征近似投影到一個較低維的特征空間[1]，后者是通過某種規(guī)則選取一個比較小的特征子集[2]。與特征提取不同，特征選擇可以保留原始特征的物理意義，因此受到許多學者的廣泛關(guān)注。考慮其是否依賴分類算法，特征選擇一般分為包類算法[3]和過濾式算法[4]。包類算法把分類算法嵌入到特征選擇中，雖然可以提高分類精度，但需要更高的計算時間。過濾式算法獨立于分類算法，可以看作對數(shù)據(jù)的預(yù)處理。此外，對于是否考慮標簽信息，特征選擇可以簡單地分為有監(jiān)督和無監(jiān)督。無監(jiān)督的特征選擇算法是在標簽缺失的情況下利用數(shù)據(jù)特征本身建立特征選擇規(guī)則[5]。有監(jiān)督的特征選擇算法則是利用標簽信息評價特征的重要度，例如 fisher score[6]、（m inimal-redundancy-maximalrelevance criterion，mRMR）[7]等。

多標簽學習是處理每個樣本同時屬于多個標簽的數(shù)據(jù)[8]。與傳統(tǒng)的單標簽學習一樣，多標簽學習同樣面臨著維數(shù)災(zāi)難問題，而且更復(fù)雜。因此，為了提高學習算法的效果，許多學者致力于研究多標簽數(shù)據(jù)特征選擇方法，去除不相關(guān)或冗余特征。許多研究者首先將多標簽數(shù)據(jù)轉(zhuǎn)換成單標簽數(shù)據(jù)，然后使用現(xiàn)有的單標簽特征選擇算法進行處理[9-10]。常用的數(shù)據(jù)轉(zhuǎn)換方法有二元關(guān)系法（binary relevance，BR）[11]、標簽冪集法（labelpowerset，LP）[12]等。近幾年有些學者提出了利用特征與標簽之間的多元互信息評價特征重要度，然后用特征排序算法或貪婪算法進行特征選擇，如PMU（multivariatemutual information for multi-label feature selection）[13]、FIMF（fastmulti-label feature selection based on information-theoretic feature ranking）[14]和 MDMR（multi-label feature selection based onmax-dependency andmin-redundancy）[15]等。

本文融合求解非負約束問題和L2,1-范數(shù)最小優(yōu)化問題，提出了一種新的基于非負稀疏表示的多標簽特征選擇方法。首先，利用特征子空間和標簽空間的線性關(guān)系構(gòu)造誤差項，并對系數(shù)矩陣加以非負約束；其次，引入指示矩陣刻畫特征子空間，放松指示矩陣為非負約束并加入稀疏表示項L2,1-范數(shù)，將離散問題轉(zhuǎn)換為連續(xù)問題，定義特征重要度的評價準則；再次，設(shè)計一種高效的矩陣更新迭代算法求解該問題，并證明了其收斂性；最后，實驗結(jié)果表明本文算法對多標簽數(shù)據(jù)具有很好的特征選擇性能。

本文組織結(jié)構(gòu)如下：第2章介紹一些相關(guān)工作；第3章提出新的多標簽特征選擇算法；第4章進行實驗結(jié)果分析；第5章進行總結(jié)和展望。

2 相關(guān)工作

一般的多標簽問題會給學習任務(wù)帶來很大的困難，主要采用3種不同的設(shè)計策略：一階策略、二階策略和高階策略。其中一階策略是一種直接的策略，將多標簽學習分解成一些二類單標簽問題。對每個標簽單獨考慮，而不考慮標簽之間的相關(guān)性。在每個標簽的二分類問題中，樣本如果含有此標簽，則稱為正樣本，反之為負樣本。然而，這種策略會導致數(shù)據(jù)分布不平衡和樣本的稀疏性。為了克服類別分布不平衡，Zhang等人提出了一種適用于多標簽數(shù)據(jù)的K近鄰多標簽學習算法（multi-label K-nearestneighbor，ML-K NN）[16]。它同樣是把多標簽分類問題分解成多個二類分類問題。首先，利用訓練集的每個樣本分別找對應(yīng)的k個鄰居，計算先驗概率和后驗概率。然后，對每個未知的樣本找到它的k個鄰居，利用貝葉斯公式，通過已求得的先驗概率和后驗概率判定未知樣本是否含有此標簽。

子空間學習是較為流行的一種特征降維方法之一，被廣泛應(yīng)用于機器學習等領(lǐng)域。子空間學習把原始高維數(shù)據(jù)轉(zhuǎn)換到一個低維的子空間，在低維空間保持原始數(shù)據(jù)的結(jié)構(gòu)或特性進行學習。子空間學習常常被用于特征提取中，如主成分分析（principal component analysis，PCA）[17]、線性判別分析（linear discriminantanalysis，LDA）[18]等。近年來也有學者將子空間學習用于特征選擇中[19]，取得了很好的效果。

3 非負稀疏表示的特征選擇

本文引入子空間學習，提出了基于非負稀疏表示的多標簽特征選擇方法。融合求解非負約束問題和L2,1-范數(shù)最小優(yōu)化問題，設(shè)計了一種高效的矩陣更新迭代算法，并證明其收斂性。

3.1 問題描述

為了表示 XI，引入指示矩陣來代替所選擇特征的指標集。不失一般性，可以定義指示矩陣W如下：

這里指示矩陣W的行數(shù)等于所有原始特征的個數(shù)，其列數(shù)等于被選擇出來的特征個數(shù)。例如d=5，I={1,3,5}，則：

基于指示矩陣W，目標函數(shù)可化為：

原始問題是離散問題，這里放松了條件，將原來的離散問題轉(zhuǎn)化成連續(xù)問題來求解。記W=(w1,，則||wi||2可以作為第i個特征的權(quán)重。為此，設(shè)置正則項R(W)為L2,1-norm范數(shù)||W||2,1。最后目標函數(shù)如下：

其中，λ作為參數(shù)調(diào)節(jié)誤差項和正則項之間的比重；||W||2,1限定矩陣W的行稀疏。

3.2 問題優(yōu)化

根據(jù)文獻[20]，L2,1-norm最小優(yōu)化問題可以通過迭代問題求解如下：

為求解非負約束問題，構(gòu)造拉格朗日函數(shù)如下：

其中，α、β是拉格朗日乘子，目的是保證W、H非負。令L對W和H的導數(shù)為0：

根據(jù)Kuhn-Tucker條件，對于任意的i、j，有αijWij=0和βijHij=0。由此，可以得到更新規(guī)則：

3.3 算法與時間復(fù)雜度分析

根據(jù)以上優(yōu)化分析，非負稀疏表示的多標簽特征選擇（multi-label feature selection based non-negative sparse representation，MNMFS）算法如下。

算法1MNMFS算法

輸入：數(shù)據(jù)矩陣 X∈?n×d，標簽矩陣Y∈?n×m，特征選擇個數(shù)k，參數(shù)λ。

輸出：選擇的特征指標集I，其中|I|=k。

1.初始化W和H；

2.迭代

2.2固定D和H，更新W，其中

2.3固定D和W，更新H，其中

3.直到收斂；

4.記W=(w1,w2…,wd)T，降序排列||wi||2，i=1,2,…,d ，選擇前k個為特征指標集I。

通常情況下，m＜n，m＜d，k＜n和k＜d。根據(jù)算法得出，在每一步迭代中，更新D的復(fù)雜度是O(dk)，更新W的復(fù)雜度是O(d2n)，更新H的復(fù)雜度是O(kdn)。因此總的時間復(fù)雜度是O(td2n)，其中t是迭代次數(shù)。因為t值較小，所以時間依賴于數(shù)據(jù)的特征維數(shù)d和數(shù)據(jù)的樣本個數(shù)n。

3.4 收斂性分析

首先，介紹幾個定義和重要引理。

定義1（輔助函數(shù)）[21]函數(shù) Z(v,v′)稱為函數(shù)F(v)的輔助函數(shù)，如果它滿足如下條件，對于任意的v和v′，有：

引理1[21]如果Z(v,v′)是F(v)的一個輔助函數(shù)，那么F(v)在如下更新下單調(diào)遞減：

引理2[22]對于任意矩陣，且 A 、B 是對稱矩陣，那么下面的不等式成立：

那么函數(shù)

是F(W)的輔助函數(shù)，并且Z(W,W′)對于W 是凸函數(shù)，其全局最優(yōu)解為：

證明首先證明Z(W,W′)是F(W)的輔助函數(shù)。

利用引理2，有：

這就證明了對任意的W 、W′，都有F(W)≤Z(W,W′)。

另外，顯然有Z(W,W)=F(W)。

因此證明了Z(W,W′)是F(W)的一個輔助函數(shù)。

為了得到Z(W,W′)的最小值，計算Z(W,W′)對Wij的一階偏導數(shù)：

同時，Z(W,W′)的二階偏導數(shù)，即它的Hassian矩陣為：

其中，當x=y時，σxy=1；否則σxy=0。顯然Hassian矩陣的所有值非負，因此輔助函數(shù)Z(W,W′)是一個凸函數(shù)，并在時對應(yīng)的W為它的全局最優(yōu)值。

根據(jù)引理1可以得到：

4 實驗

對本文算法和現(xiàn)有的幾種多標簽特征選擇算法在6個公開的現(xiàn)實數(shù)據(jù)集上做了大量的實驗。實驗結(jié)果表明，本文算法在多標簽數(shù)據(jù)集上有較好的特征選擇性能。

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

用6個來自3種不同應(yīng)用領(lǐng)域的真實數(shù)據(jù)集驗證本文多標簽特征選擇算法。這6個數(shù)據(jù)集分別是Society、Health、Arts、Recreation、Scene和 Yeast。其中Society、Health、Arts和Recreation數(shù)據(jù)集屬于網(wǎng)頁類數(shù)據(jù)集，Scene數(shù)據(jù)集屬于圖像類數(shù)據(jù)集，Yeast數(shù)據(jù)集屬于基因類數(shù)據(jù)集。數(shù)據(jù)集從Mulanlibrary（http://mulan.sourceforge.net/datasets-m lc.htm l）下載獲得，在表1中列出這些數(shù)據(jù)集的詳細信息。

Table 1 Data information表1 數(shù)據(jù)信息

4.2 實驗設(shè)置

實驗用ML-KNN作為評價分類算法，其中鄰域個數(shù)K=10，平滑指數(shù)s=1。選擇現(xiàn)有的多標簽特征選擇算法（PMU,MDMR,FIMF）作為對比算法，分別考慮它們的5個評價指標Average precision、Coverage、Hamm ing loss、One-error和 Ranking loss。對比算法的實驗設(shè)置均按照默認設(shè)置，除了FIMF在數(shù)據(jù)集Scene上設(shè)置Q=6，是因為數(shù)據(jù)集Scene只有6個標簽。對于本文算法，設(shè)置參數(shù)λ=1，迭代次數(shù)為50。由于算法對矩陣初始化有一定敏感性，采用10次實驗，取結(jié)果的平均值。另外，對數(shù)據(jù)集Society、Health、Arts、Recreation、Scene，分別在選擇特征數(shù)為{30:5:70}時對所有算法進行實驗。對數(shù)據(jù)集Yeast，因為特征數(shù)較少，所以設(shè)定選擇的特征個數(shù)為{10:5:50}。

4.3 實驗結(jié)果分析

本文根據(jù)實驗設(shè)置，對不同算法和數(shù)據(jù)集做了大量的實驗。圖1分別表示各個數(shù)據(jù)集在選擇不同特征個數(shù)情況下，所有算法的平均分類精度，其中水平線表示原始的平均分類精度。從圖中首先可以得出，特征選擇不僅縮短了分類學習的運行時間和空間，有時候還提高了分類學習性能。這是因為特征選擇刪除了一些不相關(guān)或冗余的特征，解決了維數(shù)災(zāi)難，在一定程度上避免過擬合。然后還可以得出，本文算法在大多數(shù)情況下優(yōu)于對比的多標簽特征選擇算法。

此外，為了更加細致地分析每個算法的效果，將ML-KNN作為分類算法，表2～表6分別列出來了所有算法在所有數(shù)據(jù)集上對不同評價指標的性能。這里每個算法對實驗設(shè)置的特征選擇個數(shù)都做了實驗，分別取每個算法中最好的結(jié)果。表中對不同的評價指標，用符號↑表示該指標值越大，性能越優(yōu)；用符號↓表示該指標值越小，性能越優(yōu)；用黑體標注對比算法中最優(yōu)性能的結(jié)果。從表中可以得出，在90種對比情況下，本文算法僅有8種情況性能略低于不同的對比算法。在Scene數(shù)據(jù)集中，本文算法在Average precision、Hamm ing loss、One-error評價指標中性能較低于PMU算法。但從其他數(shù)據(jù)集上看，本文算法性能較優(yōu)于PMU算法。總體上，本文多標簽特征選擇算法在以上數(shù)據(jù)集有比較好的適用性，性能要優(yōu)于對比的多標簽特征選擇算法。

Fig.1 Comparison on average precision of differentalgorithms圖1 不同算法的平均分類精度比較

Table2 Performanceof average precision表2 平均精度↑

Table3 Performanceof coverage表3 覆蓋率↓

Table4 Performanceof Hamm ing loss表4 漢明損失↓

Table5 PerformanceofOne-error表5 One-錯誤率↓

Table 6 Performance of Ranking loss表6 排序損失↓

5 結(jié)束語

多標簽學習是處理一個樣本同時含有多個標簽的數(shù)據(jù)。同傳統(tǒng)的單標簽學習一樣，也面臨著維數(shù)災(zāi)難。本文提出了一種基于非負稀疏表示的多標簽特征選擇算法。通過引入子空間學習，對特征子空間加以非負和稀疏表示。融合非負約束問題和L2,1-范數(shù)最小優(yōu)化問題，設(shè)計了一種新的矩陣更新迭代算法求解該問題。最后，為了驗證算法的有效性，在3種不同領(lǐng)域的真實數(shù)據(jù)集上做了大量的實驗。實驗結(jié)果表明，本文多標簽特征選擇算法優(yōu)于現(xiàn)有的幾種多標簽特征選擇算法。

算法的原始問題是離散問題，本文在轉(zhuǎn)化成連續(xù)問題求解時，只考慮指示矩陣的非負約束和行稀疏性，而沒有考慮其存在的正交性。在以后的研究工作中將考慮正交約束，提高算法的性能，并把非負稀疏分析用于其他弱監(jiān)督學習和無監(jiān)督學習中，以解決更多問題。

[1]Zhang Yin,Zhou Zhihua.Multilabel dimensionality reduction via dependence maxim ization[J].ACM Transactions on Know ledge Discovery from Data,2010,4(3):14.

[2]CaiDeng,Zhang Chiyuan,He Xiaofei.Unsupervised feature selection formulti-cluster data[C]//Proceedings of the 16th ACM SIGKDD International Conference on Know ledge Discovery and Data M ining,Washington,Jul 25-28,2010.New York:ACM,2010:333-342.

[3]Maldonado S,Weber R.A w rappermethod for feature selection using support vectormachines[J].Information Sciences,2009,179(13):2208-2217.

[4]Yu Lei,Liu Huan.Feature selection for high-dimensional data:a fast correlation-based filter solution[C]//Proceedings of the 20th International Conference on Machine Learning,Washington,Aug 21-24,2003.Menlo Park,USA:AAAI,2003:856-863.

[5]Wang Shiping,Pedrycz W,Zhu Qingxin,et al.Unsupervised feature selection via maximum projection and m inimum redundancy[J].Know ledge-Based Systems,2015,75:19-29.

[6]Duda R O,Hart PE,Stork D G.Pattern classification[M].New York:JohnWiley&Sons,Inc,2012.

[7]Peng Hanchuan,Long Fuhui,Ding C.Feature selection based on mutual information criteria ofmax-dependency,maxrelevance,and m in-redundancy[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(8):1226-1238.

[8]Zhang M inling,Zhou Zhihua.A review onmulti-label learningalgorithms[J].IEEE Transactions on Know ledge and Data Engineering,2014,26(8):1819-1837.

[9]Yang Yiming,Pedersen JO.A comparative study on feature selection in text categorization[C]//Proceedings of the 14th International Conference on Machine Learning,Nashville,USA,Jul 8-12,1997.Menlo Park,USA:AAAI,1997,97:412-420.

[10]Diplaris S,TsoumakasG,M itkas PA,etal.Protein classification w ith multiple algorithms[C]//LNCS 3746:Proceedings of the 10th Panhellenic Conference on Advances in Informatics,Volos,Greece,Nov 11-13,2005.Berlin,Heidelberg:Springer,2005:448-456.

[11]BoutellM R,Luo Jiebo,Shen Xipeng,etal.Learningmultilabel scene classification[J].Pattern Recognition,2004,37(9):1757-1771.

[12]Read J,Pfahringer B,Holmes G.Multi-label classification using ensembles of pruned sets[C]//Proceedings of the 8th International Conference on Data M ining,Pisa,Italy,Dec 15-19,2008.Washington:IEEE Computer Society,2008:995-1000.

[13]Lee J,Kim DW.Feature selection formulti-label classification usingmulti-variatemutual information[J].Pattern Recognition Letters,2013,34(3):349-357.

[14]Lee J,Kim DW.Fastmulti-label feature selection based on information-theoretic feature ranking[J].Pattern Recognition,2015,48(9):2761-2771.

[15]Lin Yaojin,Hu Qinghua,Liu Jinghua,etal.Multi-label feature selection based onmax-dependency andm in-redundancy[J].Neurocomputing,2015,168:92-103.

[16]Zhang M inling,Zhou Zhihua.ML-K NN:a lazy learning approach to multi-label learning[J].Pattern Recognition,2007,40(7):2038-2048.

[17]Jolliffe I.Principal component analysis[M].Secaucus,USA:Springer-Verlag,2002.

[18]Fisher R A.The use ofmultiplemeasurements in taxonomic problems[J].Annalsof Eugenics,1936,7(2):179-188.

[19]Wang Shiping,Pedrycz W,Zhu Qingxin,et al.Subspace learning for unsupervised feature selection viamatrix factorization[J].Pattern Recognition,2014,48(1):10-19.

[20]Nie Feiping,Huang Heng,CaiXiao,etal.Efficientand robust feature selection via joint L2,1-norms m inim ization[C]//Advances in Neural Information Processing Systems 23:Proceeding of the 24th Annual Conference on Neural Information Processing Systems,Vancouver,Canada,Dec 6-9,2010.Red Hook,USA:Curran Associates,2010:1813-1821.

[21]Lee D D,Seung H.Algorithms for non-negativematrix factorization[C]//Advances in Neural Information Processing Systems 14:Proceeding of the 15th Conference on Neural Information Processing Systems,Vancouver,Canada,Dec 3-8,2001.Cambridge,USA:M ITPress,2001:556-562.

[22]Ding C,Li Tao,Jordan M I.Convex and sem i-nonnegative matrix factorizations[J].IEEETransactions on Pattern Analysisand Machine Intelligence,2010,32(1):45-55.

CAIZhiling was born in 1989.He is an M.S.candidate at M innan Normal University.His research interests includemachine learning and datam ining.

蔡志鈴（1989—），男，福建漳州人，閩南師范大學碩士研究生，主要研究領(lǐng)域為機器學習，數(shù)據(jù)挖掘。

祝峰（1962—），男，江西玉山人，2006年于奧克蘭大學計算機科學專業(yè)獲得博士學位，現(xiàn)為閩南師范大學教授，主要研究領(lǐng)域為數(shù)據(jù)挖掘，人工智能。

M ulti-Label Feature Selection via Non-Negative Sparse Representation*

CAIZhiling,ZHUWilliam+
Lab of Granular Computing,M innan NormalUniversity,Zhangzhou,Fujian 363000,China

Dimensionality reduction isan importantand challenging task inmulti-label learning.Feature selection is a highly efficient technique for dimensionality reduction bymaintainingmaximum relevant information to find an optimal feature subset.Firstof all,this paper proposes amulti-label feature selectionmethod based on non-negative sparse representation by studying the subspace learning.Thismethod can be treated as amatrix factorization problem,which is combined w ith non-negative constraintproblem and L2,1-norm minimization problem.Then,thispaper designs a kind of efficient iterative update algorithm to tackle the new problem and proves its convergence.Finally,theexperimental resultson six real-world data setsshow theeffectivenessof the proposed algorithm.

multi-label learning;feature selection;non-negativematrix factorization;L2,1-norm

m wasborn in 1962.He

the Ph.D.degree in computer science from University of Auckland in 2006.Now he is a professor atM innan Normal University.His research interests include datam ining and artificial intelligence.

A

：TP18

*The NationalNatural Science Foundation of ChinaunderGrantNos.61379049,61379089(國家自然科學基金面上項目).Received 2016-05,Accepted 2016-07.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-07-14,http://www.cnki.net/kcms/detail/11.5602.TP.20160714.1616.010.htm l

關(guān)鍵詞：多標簽學習；特征選擇；非負矩陣分解；L2,1-范數(shù)