基于圖譜的多標記特征選擇算法*

嚴　鵬，李　云

南京郵電大學計算機學院，南京210023

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0543-11

?

基于圖譜的多標記特征選擇算法*

嚴鵬，李云+

南京郵電大學計算機學院，南京210023

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0543-11

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The Natural Science Foundation of Jiangsu Province of China under Grant Nos. BK20131378, BK20140885 (江蘇省自然科學基金); the Postdoctoral Science Foundation of Jiangsu Province under Grant No. 1401045C (江蘇省博士后科研資助計劃); the Science Foundation of Nanjing University of Posts and Telecommunications under Grant No. NY214034 (南京郵電大學科研基金).

Received 2015-05,Accepted 2015-07.

CNKI網絡優先出版: 2015-08-11, http://www.cnki.net/kcms/detail/11.5602.TP.20150811.1537.007.html

摘要：特征選擇在傳統的單標記問題中已經得到深入的研究，但是大多數傳統的特征選擇算法卻無法用于多標記問題。這是因為多標記問題中的每一個數據樣本都同時與多個類標相關聯，此時需要設計新的指標來book=544,ebook=98評價特征。并且由于多個類標之間通常存在一定的關聯性，在設計特征選擇算法時還需要對類標的結構進行建模以利用類標的關聯信息。采用譜特征選擇（spectral feature selection，SPEC）框架解決上述問題。SPEC所需的相似性矩陣和圖結構由樣本類標的Jaccard相似性來構建，它能反映類標間的關聯性。此外，所提出的方法屬于過濾器模型，它獨立于分類算法且不需要將多標記問題轉化為單標記問題來處理。在現實世界數據集上的實驗驗證了所提出算法的正確性和較好的性能。

關鍵詞：多標記學習；譜特征選擇；標記關聯性

1　引言

在傳統監督學習領域，每個樣本只屬于一個概念，即每個樣本只與一個類標相關聯。而在多標記學習中，每個樣本可以同時與多個類標相關聯。這些類標可能相互依賴也可能相互獨立，于是與多標記學習相關的算法通常需要能夠表示和利用類標間的關聯信息。例如，在Emotions數據集中，每首樂曲用72個節奏和音色的特征來描述，并被標有吃驚、愉快、放松、安靜、悲傷、生氣這6種類標中的一個或多個。多標記學習的任務，就是在已標記好的數據集上訓練分類器，使其能為未標記樣本添加正確的類標。很自然的，“放松”與“安靜”相比“放松”與“生氣”更可能被同時標記在同一首樂曲上，這就是類標間的關聯信息。

此外，多標記學習同樣會受到維度災難的困擾，冗余和不相關的特征會讓數據變得難以處理，并導致訓練得到的模型不可靠。因此，需要設計能夠有效處理多標記問題的特征選擇算法。與傳統的特征選擇算法相比，多標記特征選擇算法需要能更好地利用類標間的關聯信息。

然而，那些成熟的特征選擇算法通常是針對傳統的單標記問題或無監督學習問題而設計的。盡管可以先將多標記問題轉化為多個單標記問題，再用這些已有的算法去處理轉化后得到的單標記問題，但是這類基于轉化策略的方法在應用時卻會遇到許多新問題。例如，利用Binary Relevance Strategy[1]將多標記問題轉換成多個單標記分類問題，再直接利用傳統的特征選擇算法對每個單標記問題進行特征選擇。顯然，這一策略完全忽略了類標間的關聯性，并且當類標空間很稀疏時會導致類別不平衡的問題。為此，采用基于圖譜的特征選擇算法[2]來直接進行特征選擇而不需進行多標記問題的轉化。這一算法屬于過濾器模型，它不依賴于特定的分類算法或是某類問題轉化策略，但依然能有效利用類標間的關聯信息。

本文組織結構如下：第2章介紹多標記學習和特征選擇的相關工作，并討論一些現有的多標記特征選擇算法；第3章詳細介紹所提出的用于多標記問題的譜特征選擇算法；第4章給出在現實世界數據集上的實驗結果和相應的評價指標；第5章進行總結和討論。

2　相關工作

2.1多標記學習

多標記學習算法按照是否利用類標的關聯信息通常被分為3個階次[3]。一階算法為每個類標單獨構建一個分類器，這樣有q個候選類標的多標記問題就被轉化為q個二分類問題。典型的一階算法有Binary Relevance[1]、多標記k近鄰算法（multi-label k-nearest neighbor，ML-kNN）[4]等。二階算法考慮成對類標的關聯性，通常將多標記分類問題轉化為類標排序問題。典型的二階算法有Calibrated Label Ranking[5]和rank-支持向量機（rank-support vector machine，rank-SVM）[6]。二階算法在訓練時通常將類標兩兩組合，構建出q(q-1)/2個二分類問題，并對每個二分類問題進行學習而得到相應的分類器。在分類時根據q(q-1)/2個分類器的結果為每個類標進行投票。某個類標得票數越高，那么該類標就越可能和該樣本相關。高階算法為類標間的關聯性建立更復雜的模型，它們可能考慮所有類標對某一類標的影響或者隨機選取一個類標子集將其轉化為多類問題，例如Classifier Chain[7-8]和Random k-label Set[9-10]屬于高階算法。

2.2特征選擇

特征選擇是一種被廣泛采用的降維技術，它按照一定評價準則從原始特征空間中選取一個維度較低的子空間，使得后續的學習算法在該子空間上有更好的性能。根據評價準則，常規的特征選擇算法通常可歸納為3種模型：過濾器模型、封裝器模型和嵌入式模型[11-12]。屬于過濾器模型的特征選擇算法獨立于具體的分類算法，因此所使用的分類器的特性和偏差并不會對選擇結果產生影響。屬于過濾器模型的典型算法有Relief/ReliefF[13]、Fisher Score[14]和基于信息增益的算法等。封裝器模型可以看作分類算法的一部分，屬于封裝器模型的算法通常利用分類器的分類性能來評價候選特征。這類算法針對特定的分類器能取得很好的性能，但卻常受限于較大的計算開支和所使用的特定分類算法。嵌入式模型結合了過濾器模型和封裝器模型的特點。屬于嵌入式模型的算法首先獨立于分類算法產生若干候選特征子空間，再根據分類器在這些子空間上的分類性能，選取獲得最優性能的特征子空間作為最終結果。

2.3多標記特征選擇

近幾年，研究人員已提出了一些針對多標記問題的特征選擇算法。在這些算法中，第一個考慮類標關聯性的多標記特征選擇算法是由Zhang等人在文獻[15]中提出的。該算法首先用傳統的主成分分析方法（principle component analysis，PCA）和遺傳算法（genetic algorithm，GA）來生成特征，再由多標記樸素貝葉斯算法來衡量這些特征的分類性能。Doquire等人在文獻[16]中先將多標記問題轉化為多類問題，然后再采用傳統的特征選擇算法對轉化后的問題進行特征選擇。Gu等人在文獻[17]中改進了rank-SVM，并結合該分類算法進行特征選擇。Kong等人在文獻[18]中拓展了傳統的ReliefF和F-Statistic算法來處理多標記問題，并應用于圖像標注。但是，這些算法大都屬于封裝器模型，它們的使用受限于巨大的計算量和特定的分類器。例如文獻[15]中所介紹的算法需要利用多標記樸素貝葉斯算法的性能來評價特征，而文獻[16-17]中所介紹的算法需要依賴特定的問題轉化策略。

3　基于圖譜的多標記特征選擇

本文將研究基于圖譜的多標記特征選擇算法，該方法可以充分利用類標間的關聯信息，并且具有較小的計算復雜度。傳統的譜特征選擇算法首先根據訓練樣本的結構提取出這些數據的圖譜信息，再根據圖譜信息選取那些與其結構一致的特征。當處理多標記問題時，如果能在提取圖譜信息的同時提取類標的結構信息，那么在此基礎上進行特征選擇既利用了類標的關聯性又不需要將多標記問題轉化為單標記問題。已有一些算法采用類似的思想來處理多標記學習問題，例如文獻[19-20]所介紹的算法先從訓練數據中提取類標的結構信息，然后利用這些信息與原始的特征來學習多標記分類模型。

3.1譜特征選擇

譜特征選擇是一種通用的特征選擇算法框架，既可以用在監督學習領域也可以用在無監督學習領域。一些經典的特征選擇算法已被證明屬于譜特征選擇的框架，例如Relief、Fisher Score等[21]。在選取特征時，譜特征選擇算法以特征取值的分布是否與目標概念的結構相一致作為特征選擇的評價標準。例如在圖1中，每個圖形（三角和圓圈）表示一個樣本，不同的形狀表示這些樣本在同一特征上的不同取值，橢圓A和橢圓B表示目標概念的區域，同一區域內的樣本具有相同的類別（類別A或類別B）。在圖1的左半部分，具有相同類別的樣本在特征F1上取值相同，而具有不同類別的樣本在特征F1上取值不同，因此特征F1對類別A和類別B有很好的判別能力，此時稱特征F1的取值分布與目標概念結構一致。相反，特征F2的取值分布則與目標概念的結構不一致，F2對類別A和類別B不具有很好的判別能力（圖1右半部分）。因此譜特征選擇會選取F1而非F2。

Fig.1 Consistency of a feature and target concept圖1　特征與目標概念的一致性示意圖

本文用Fm(1≤m≤d)表示第m個特征，fm為所有樣本在第m個特征上的取值所構成的向量，則第i個樣本可以表示成xi=(f1i,f2i,…,fdi)。目標概念的結構由無向圖G(V,E)表示，其中V、E分別為圖的點集和邊集。圖的第i個結點vi?V對應于數據集中的第i個樣本xi，邊eii′?E的權重Wii′對應于第i個樣本和第i′個樣本的相似度Sii′(1≤i,i′≤n)。對于所給定的圖G，其鄰接矩陣W和度矩陣D為：

則相應的拉普拉斯矩陣L和正則化的拉普拉斯矩陣L為：

而譜特征選擇算法將選擇那些與目標概念結構一致的特征，即選擇那些使得式（3）取較小值的特征：

其中fmT為fm的轉置。又因為fm和L的范數會影響φ(Fm)的取值，所以還需對fm與L進行正則化，即：

其中‖·‖表示2-范數，且

譜特征選擇算法的偽代碼如算法1所示。

算法1譜特征選擇框架

輸入：X,Y,φ(×)

輸出：SFSPEC-排序后的特征列表

1.依據X、Y計算每兩個樣本間的相似度Sii′(1≤i,i′≤n)

2.依據相似度構建圖G并獲得式（1）、（2）中定義的W、D、L

3. For每個特征Fm(1≤m≤d) do

4.SFSPEC(m)?φ(Fm)

5. End for

6.將SFSPEC按升序排列

返回SFSPEC

3.2多標記問題目標概念的圖結構

如3.1節所述，譜特征選擇用無向圖來表示目標概念的結構，那么要將傳統的譜特征選擇應用于多標記學習，也需要用無向圖來表示多標記問題的目標概念結構。圖2作為圖1的拓展，給出了多標記問題的目標概念（類標）結構。F1表示數據的某一特征。每個圖形（叉、三角、圓圈和星）表示一個樣本，圖形的不同形狀表示這些樣本在特征F1上的不同取值。橢圓A、B、C表示3個不同的目標概念區域。多標記學習的目標就是將樣本正確分配到各個橢圓（類標）中。其中橢圓D是一個特殊的目標概念區域，落在D中的樣本表示其不與任何類標相關聯。顯然，多標記問題和傳統單標記問題的目標結構的主要區別在于：多標記問題的兩個不同概念（類標）間可能存在交集，即一個樣本可以同時屬于多個概念（與多個類標相關聯）。此外，落在兩個概念（類標）相交區域中的樣本越多，則這兩個概念（類標）同時出現的可能性就越大，它們越可能是相互依賴的。相反，如果交集區域中幾乎沒有樣本，那么相關的概念（類標）越可能是互斥的關系。例如在圖2中，A和B交集區域中存在少量樣本，因此一個樣本可能同時與A和B相關聯，而C與A和B間均不存在交集，它們可能為互斥的關系，即一個樣本與C相關聯則不會再與A或B相關聯。同時，圖2中與相同類標相關聯的樣本（落在同一區域中的樣本）在特征F1上取值相同，而與不同類標相關聯的樣本（落在不同區域的樣本）在特征F1上取值不同，因此特征F1對此結構圖中所描述的多標記問題具有很好的判別性。

Fig.2 Target concept of a multi-label learning problem圖2　多標記問題的目標概念結構圖

基于上述分析，譜特征選擇中使用到的目標概念的結構圖也能很好地描述類標間的關聯信息，那些取值分布與目標概念的結構一致的特征通常具有很好的判別性，因此，可以自然地對常規譜特征選擇算法進行拓展，以用于處理多標記學習的特征選擇問題。

3.3多標記問題樣本相似度的定義

要構建目標概念的結構圖，就需要計算樣本間的相似度。在傳統的譜特征選擇算法中，通常用式（5）或式（6）來定義樣本的相似度。式（5）用于監督學習，其中nc為屬于類別c的樣本的個數，式（6）是徑向基（radial basis function，RBF）核函數，通常用于無監督學習。

這兩種相似度的定義在多標記問題中均無法直接使用。對于式（5），因為多標記問題中每個樣本可以同時與多個類標相關聯，即同時屬于多個類別，所以無法確定nc的值。而對于式（6），它本身用于無監督學習，并沒有使用相應的監督信息（類標信息）。為了有效定義樣本的相似性，一種直觀的解決方案是對式（6）進行修改：

然而，RBF核函數中通常是依據類標集合在歐氏空間中的距離來度量樣本相似性的，這類距離并不能很好地度量類標集合之間的相似度。例如，假設類標集合為Y={y1,y2,y3}以及4個樣本(x1,y1)，(x2,y2)，(x3,y3)，(x4,y4)，其中y1=(1,1,1)，y2=(0,1,1)，y3=(1,0,0)，y4=(0,0,0)，那么依據式（7）有S12=S34=e-1/(2δ2)。但是這4個樣本的目標結構如圖3所示。因為樣本(x1,y1)與樣本(x2,y2)有兩個共同的類標y2和y3，它們落在了y2和y3的交集中，而樣本(x3,y3)和樣本(x4,y4)并沒有共同關聯的類標，它們屬于圖中兩個不相交的區域，由此直觀上可得出S12>S34=0。這與依據式（7）計算所得的結果并不一致。

Fig.3 Label structure of instances圖3　樣本的類標結構示例

因此，將利用Jaccard相似度（式（8））來度量兩個樣本間的相似度。依據式（8），Sii′?[0,1]，兩個樣本共同關聯的類標越多，Sii′越接近1。當每個樣本最多只能與1個類標相關聯時，多標記問題就退化為傳統的單標記多類問題，式（8）也相應地變為式（9），而它剛好是傳統單標記問題中所使用的相似度式（5）的特例。

3.4與wrapper-SPEC的聯系

傳統的譜特征選擇適用于單標記問題，可以將多標記問題經某種轉化策略轉化為若干單標記問題后，再對各單標記問題使用傳統的譜特征選擇。不過此時的特征選擇已經依賴于問題轉化策略，屬于封裝器模型，不妨稱這類算法為wrapper-SPEC。而由式（8）確定了樣本間的相似度后，可直接根據算法1對多標記數據進行特征選擇。此時算法不依賴于特定的分類算法或問題轉化策略，屬于過濾器模型，稱其為filter-SPEC。用filter-SPEC和wrapper-SPEC進行特征選擇和分類的過程見圖4和圖5。

Fig.4　Progress of feature selection and classification of filter-SPEC圖4　利用filter-SPEC進行特征選擇和分類

此外，filter-SPEC所選出的特征對經過轉化得到的單標記問題依然具有判別性，因此與wrapper-SPEC在每個單標記問題上所選出的特征密切相關。例如，圖6中的每個圖形（叉、三角、圓圈和星）表示一個樣本，不同形狀表示不同樣本對同一特征的不同取值，其分布與目標概念（類標）的結構一致，因此filter-SPEC會選出該特征。

Fig.5 Progress of feature selection and classification of wrapper-SPEC圖5　利用wrapper-SPEC進行特征選擇和分類

Fig.6 Target graph of a multi-label learning problem圖6　多標記問題的目標概念結構圖

而在wrapper-SPEC中，如果利用一階算法的轉化策略將多標記問題轉化為單標記問題（對每個類標分別進行處理），則圖6所介紹的多標記數據可轉化成3個單標記問題，即對A/-A、B/-B和C/-C的分類。同時，該策略可視為將圖6中的目標概念圖G分解，得到圖G1'、圖G2'和圖G3' 3個子目標概念圖，如圖7所示。此外，在wrapper-SPEC中，如果利用二階策略將原始多標記問題轉化為對A/B、A/C和B/C的二分類單標記問題，則該策略同樣可將圖G進行分解，得到如圖8所示的目標概念子圖。不難得到由filter-SPEC所選出的特征對轉化所得的單標記子問題仍然具有判別性。

在計算復雜度上，filter-SPEC的計算復雜度為Tfilter= O(n2(q+d))，采用一階轉化策略的wrapper-SPEC的計算復雜度為T1-order=O(n2(1+d)q)，采用二階轉化策略的wrapper- SPEC的計算復雜度為T2-order=O(n2(1+d)q(q-1))。顯然，Tfilter

Fig.7 Target graphs transformed by the first order strategy圖7　一階策略轉化后的目標結構

Fig.8 Target graphs transformed by the second order strategy圖8　二階策略轉化后的目標結構

4　實驗

為了驗證上述算法的有效性，在現實世界數據集上比較了filter-SPEC和其他封裝器模型算法的性能。對于filter-SPEC，分別使用式（7）（filter-SPEC-RBF）和式（8）（filter-SPEC-Jaccard）計算樣本相似度。對于封裝器模型，除了wrapper-SPEC外，還使用了具有代表性的Relief算法。雖然Relief在處理單標記問題時屬于過濾器模型，但應用于多標記問題時，它依賴于特定的問題轉化策略[18]，因此不妨稱用于多標記問題的Relief為wrapper-Relief。所有實驗在Matlab仿真環境下進行，使用Intel酷睿i7 2720QM CPU，4 GB內存。

4.1數據集

為了驗證算法的性能，在4個來自不同領域的基準數據集上進行了相關實驗。表1給出了實驗數據集的詳細信息。

Table 1 Summary of data sets表1　實驗數據信息

4.2多標記學習算法

為了驗證選擇出的特征的性能，分別采用ML-kNN 和Calibrated Label Ranking作為多標記分類算法。這兩種算法分別基于一階策略和二階策略將多標記問題轉化為單標記問題，如文獻[6，17，22-25]等一些多標記分類算法和特征選擇算法都是在它們的基礎上發展而來，因此具有一定代表性。

4.2.1ML-kNN

ML-kNN[4]屬于一階算法，它依次對多標記問題的每個類標進行分類，并最終給出與樣本相關的類標集合，即ML-kNN為h:X?2Y的一種實現。本文采用漢明損失衡量ML-kNN的性能，其定義見式（10）：

式（10）中p為測試樣本個數；q為類標個數；?為異或操作。漢明損失越小表明所用的特征選擇算法性能越優秀。實驗結果見圖9。

經過10次交叉驗證后的實驗結果如圖9所示，其中橫軸表示所選取的特征個數占原始特征維數的百分比，縱軸為漢明損失的值。其中水平線base為未進行任何特征選擇時ML-kNN的分類性能。實驗結果表明利用Jaccard相似度的filter-SPEC能取得最優性能，而wrapper-SPEC和使用RBF核函數的filter-SPEC性能較差。

Fig.9 Results of ML-kNN圖9　ML-kNN算法實驗結果

4.2.2Calibrated Label Ranking

Calibrated Label Ranking[5]屬于二階算法。它將多標記問題的類標兩兩組合轉化得到q(q-1)/2個單標記二分類問題，再根據這些單標記問題的分類結果對類標排序，某類標票數越多樣本越可能和該類標相關聯。顯然，該算法為h′:X′Y?R的一種實現。

因為該算法的輸出并不是具體的類標集合而是類標的排序，所以使用平均精確率而非漢明損失來衡量算法的性能，其定義為：

其中，rank(yj)為第j個類標在輸出中所排的位次，該指標的范圍是[0,1]，越接近1表明算法性能越好。

本實驗中使用SVM+RBF kernel作為轉換后單標記問題的分類器。在基準數據集上利用10次交叉驗證后的實驗結果如圖10所示，橫軸表示選取的特征個數與原始特征維數的百分比，縱軸為平均精確率。其中水平線base為未進行特征選擇時Calibrated Label Ranking的分類性能。實驗結果表明filter-SPEC、wrapper-Relief和wrapper-SPEC具有相似的分類性能。但耗時上，medical數據集上filter-SPEC所用的平均時間為53.880 7 s，而wrapper-Relief為91.831 5 s，wrapper-SPEC為132.513 2 s；在yeast數據集上，filter-SPEC、wrapper-Relief和wrapper-SPEC的平均耗時分別為81.816 1 s、90.579 3 s和138.429 8 s。emotions數據集上各算法耗時均小于3 s，tmc2007數據集上各算法均沒能在10 h內完成，故沒有列出詳細的運行時間。如上文所述，因為需要對轉化后的單標記問題依次進行特征選擇，wrapper-SPEC的計算復雜度大于filter-SPEC的計算復雜度。并且此處wrapper-Relief的計算復雜度為O((n2+nd)q(q-1))，也大于filter-SPEC的計算復雜度。因此filter-SPEC在計算復雜度上更具競爭力。

Fig.10 Results of Calibrated Label Ranking圖10　Calibrated Label Ranking實驗結果

4.3結果分析

已有文獻表明[2，11-12]，基于封裝器模型所選出的特征在分類性能上通常要優于基于過濾器模型所選出的特征，但封裝器模型受限于計算復雜度和所采用的分類算法。而上述實驗結果表明，在基準數據集上，本文改進的譜特征選擇算法（filter-SPEC）與依賴于問題轉化的多標記特征選擇算法（封裝器模型）相比，在更低的計算復雜度下卻取得了相似或更為優秀的分類性能。這主要是因為：一方面所構建的概念圖很好地反應了樣本結構和類標的關聯信息，從而保證了所選特征的分類性能；另一方面，在用filter-SPEC選出特征后依舊采用了一階和二階分類算法，這些算法仍是將多標記問題轉化為單標記問題后再進行分類，這一過程并不能很好地利用原始數據集上樣本的結構和類標的關聯信息，使得filter-SPEC所選特征和封裝器模型所選特征取得了相似的分類性能。

5　結束語

多標記學習的特征選擇問題開始引起來自多標記學習領域和特征選擇領域的研究人員的關注，盡管已經提出了一些用于多標記學習問題的特征選擇算法，但它們大都屬于封裝器模型，具有較高的時間復雜度。本文對傳統的譜特征選擇框架進行改進，以便能有效處理多標記問題的特征選擇。所提出的基于圖譜的特征選擇算法屬于過濾器模型，不依賴于具體的多標記分類算法或問題轉化策略。理論分析和實驗結果表明，本文算法具有與封裝器模型相似或更好的性能，且時間開銷較少。鑒于圖譜能很好地描述類標間的關聯信息，在未來工作中，將圖譜理論應用于多標記學習的整個過程中，而不僅限于特征選擇。

References:

[1] Zhou Zhihua, Zhang Minling. Multi-instance multi-label learning with application to scene classification[C]//Advances in Neural Information Processing Systems 19: Proceedings of the 20th Annual Conference on Neural Information Processing Systems, Vancouver, Canada, Dec 4-7, 2006. Cambridge, USA: MIT Press, 2007: 1609-1616.

[2] Zhao Zheng, Liu Huan. Spectral feature selection for supervised and unsupervised learning[C]//Proceedings of the 24th International Conference on Machine Learning, Corvallis, USA, 2007. New York, USA:ACM, 2007: 1151-1157.

[3] Zhang Minling, Zhou Zhihua.Areview on multi-label learning algorithms[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(8): 1819-1837.

[4] Zhang Minling, Zhou Zhihua. ML-KNN: a lazy learning approach to multi- label learning[J]. Pattern Recognition, 2007, 40(7): 2038-2048.

[5] Fürnkranz J, Hüllermeier E, Mencía E L, et al. Multilabel classification via calibrated label ranking[J]. Machine Learning, 2008, 73(2): 133-153.

[6] Elisseeff A, Weston J. A kernel method for multi-labelled classification[C]//Advances in Neural Information Processing Systems 14: Proceedings of the 2002 Annual Conference on Neural Information Processing Systems, Vancouver, Canada, Dec 9-14, 2002. Cambridge, USA: MITPress, 2003: 681-687.

[7] Read J, Pfahringer B, Holmes G, et al. Classifier chains for multi-label classification[J]. Machine Learning, 2011, 85(3): 333-359.

[8] 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, Beijing, Jul 24-28, 2011. New York, USA:ACM, 2011: 705-714.

[9] Tsoumakas G, Katakis I, Vlahavas I. Random k-labelsets for multilabel classification[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 23(7): 1079-1089.

[10] Tsoumakas G, Vlahavas I. Random k-labelsets: an ensemble method for multilabel classification[C]//LNCS 4701: Proceedings of the 18th European Conference on Machine Learning, Warsaw, Poland, Sep 17-21, 2007. Berlin, Heidelberg: Springer, 2007: 406-417.

[11] Tang Jiliang,Alelyani S, Liu Huan. Feature selection for classification: a review[J/OL]. (2014)[2015-03-01]. http://www. public.asu.edu/～jtang20/publication/feature_selection_for_ classification.pdf.

[12]Alelyani S, Tang Jiliang, Liu Huan. Feature selection for clustering: a review[J/OL]. (2013)[2015-03-01]. http://www.public.asu.edu/～jtang20/publication/FSClustering.pdf.

[13] Robnik-?ikonja M, Kononenko I. Theoretical and empirical analysis of ReliefF and RReliefF[J]. Machine Learning, 2003, 53(1/2): 23-69.

[14] Duda R O, Hart P E, Stork D G. Pattern classification[M]. Hoboken, USA: John Wiley & Sons, 2012.

[15] Zhang M L, Pe?a J M, Robles V. Feature selection for multilabel naive Bayes classification[J]. Information Sciences, 2009, 179(19): 3218-3229.

[16] Doquire G, Verleysen M. Feature selection for multi-label classification problems[C]//LNCS 6691: Proceedings of the 11th International Work- Conference on Artificial Neural Networks, Torremolinos- Málaga, Spain, Jun 8- 10, 2011. Berlin, Heidelberg: Springer, 2011: 9-16.

[17] Gu Quanquan, Li Zhenhui, Han Jiawei. Correlated multi-label feature selection[C]//Proceedings of the 20th ACM International Conference on Information and Knowledge Management, Glasgow, UK, Oct 24-28, 2011. New York, USA:ACM, 2011: 1087-1096.

[18] Kong Deguang, Ding C H Q, Huang Heng, et al. Multi-label ReliefF and F-statistic feature selections for image annotation[C]//Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition, Providence, USA, Jun 16-21, 2012. Piscataway, USA: IEEE, 2012: 2352-2359.

[19] Huang Shengjun, Zhou Zhihua. Multi-label learning by exploiting label correlations locally[C]//Proceedings of the 26th AAAI Conference on Artificial Intelligence, Toronto,Canada, 2012. Menlo Park, USA:AAAI, 2012: 949-955.

[20] Tsoumakas G, Katakis I, Vlahavas I. Effective and efficient multilabel classification in domains with large number of labels[C]//Proceedings of the ECML/PKDD 2008 Workshop on Mining Multidimensional Data, 2008: 30-44.

[21] Zhao ZA,Liu Huan.Spectralfeatureselectionfordatamining[M]. Boca Raton, USA: CRC Press, 2011.

[22] Madjarov G, Gjorgjevikj D, Delev T. Efficient two stage voting architecture for pairwise multi-label classification[C]// LNCS 6464: Proceedings of the 23rd Australasian Joint Conference on Artificial Intelligence, Adelaide, Australia, Dec 7-10, 2010. Berlin, Heidelberg: Springer, 2011: 164-173.

[23] Madjarov G, Gjorgjevikj D, D?eroski S. Two stage architecture for multi-label learning[J]. Pattern Recognition, 2012, 45(3): 1019-1034.

[24] Cheng Weiwei, Hüllermeier E, Dembczynski K J. Bayes optimal multilabel classification via probabilistic classifier chains[C]//Proceedings of the 27th International Conference on Machine Learning, Haifa, Israel, 2010: 279-286.

[25] Zhang Minling, Zhang Kun. Multi-label learning by exploiting label dependency[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, USA, Jul 25-28, 2010. New York, USA: ACM, 2010: 999-1008.

YAN Peng was born in 1990. He is an M.S. candidate at Nanjing University of Posts and Telecommunications. His research interests include machine learning and pattern recognition, etc.

嚴鵬（1990—），男，江蘇南京人，南京郵電大學碩士研究生，主要研究領域為機器學習，模式識別等。

LI Yun was born in 1974. He received the Ph.D. degree from Chongqing University in 2005. Now he is a professor at Nanjing University of Posts and Telecommunications, and the member of CCF. His research interests include machine learning and pattern recognition, etc.

李云（1974—），男，2005年于重慶大學獲得博士學位，現為南京郵電大學教授，CCF會員，主要研究領域為機器學習，模式識別等。

Spectral Theory Based Multi-Label Feature Selection?

YAN Peng, LI Yun+
School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China

+ Corresponding author: E-mail: liyun@njupt.edu.cn

YAN Peng, LI Yun. Spectral theory based multi-label feature selection. Journal of Frontiers of Computer Science and Technology, 2016, 10(4)：543-553.

Abstract:Feature selection has been deeply studied in traditional single label problem. When it comes to multi-label problem, most of traditional feature selection algorithms for single label problem are not able to be applied directly, since instances in multi-label problems are associated with several labels simultaneously, new criteria to evaluate features are needed. Because of the correlations among several labels, new methods to model labels structure are needed for using the correlation information when designing feature selection algorithm. This paper uses the spectral feature selection (SPEC) framework to handle multi-label problem and uses Jaccard similarity to construct the similarity matrix and the target graph in SPEC for multi-label problem. This method is under filter model, which is different from the wrapper model. The latter always transforms the multi-label problem into some single label problems, and traditional feature selection algorithm is applied to these single label problems. The experiments on real world data sets demonstrate the correctness and high performance of the proposed algorithm.

Key words:multi-label learning; spectral feature selection; label correlation

文獻標志碼：A

中圖分類號：TP181

doi:10.3778/j.issn.1673-9418.1505064