基于最大相關(guān)最小冗余的多標(biāo)記特征選擇

楊文元

?

基于最大相關(guān)最小冗余的多標(biāo)記特征選擇

楊文元*

(閩南師范大學(xué)福建省粒計(jì)算重點(diǎn)實(shí)驗(yàn)室，福建漳州363000)

針對(duì)多標(biāo)記學(xué)習(xí)中高維數(shù)據(jù)運(yùn)行速度問題，提出一種基于最大相關(guān)最小冗余的特征選擇算法ML-MRMR。利用數(shù)據(jù)與標(biāo)記的互信息，獲得了最大相關(guān)性最少冗余性特征集合。分析了所選特征百分比與精度關(guān)系。實(shí)驗(yàn)結(jié)果表明，所提出算法在速度和精度上都具有明顯的優(yōu)勢(shì)。

多標(biāo)記學(xué)習(xí)；特征選擇；最大相關(guān)最小冗余；數(shù)據(jù)降維

引言

隨著計(jì)算機(jī)網(wǎng)絡(luò)和信息化的發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)和資源呈海量特征，數(shù)據(jù)的標(biāo)注結(jié)構(gòu)復(fù)雜程度也在增加，傳統(tǒng)的單標(biāo)記方法無法滿足對(duì)復(fù)雜數(shù)據(jù)進(jìn)行分析處理的需求，以機(jī)器學(xué)習(xí)技術(shù)為基礎(chǔ)的多標(biāo)記學(xué)習(xí)技術(shù)現(xiàn)已成為一個(gè)研究熱點(diǎn)，其研究成果廣泛地應(yīng)用于各種不同的領(lǐng)域，如圖像視頻的語義標(biāo)注、功能基因組、音樂情感分類以及營銷指導(dǎo)等[1, 2]。多標(biāo)記學(xué)習(xí)的主要特點(diǎn)在于它能反映真實(shí)世界對(duì)象具有的多義性。因此，在最近十年來,多標(biāo)記學(xué)習(xí)已逐漸吸引國內(nèi)外許多一流的學(xué)術(shù)機(jī)構(gòu)和科學(xué)研究者。

多標(biāo)記問題定義和評(píng)價(jià)指標(biāo)是一個(gè)研究熱點(diǎn)。由于多標(biāo)記學(xué)習(xí)輸出空間的類別標(biāo)記集合數(shù)隨著標(biāo)記空間的增大而成指數(shù)規(guī)模增長，當(dāng)標(biāo)記空間具有k個(gè)類別標(biāo)記時(shí)，則可能的類別標(biāo)記集合數(shù)為2k，為了有效應(yīng)對(duì)標(biāo)記集合空間過大所造成的學(xué)習(xí)困難，學(xué)習(xí)系統(tǒng)需要充分利用標(biāo)記之間的相關(guān)性來輔助學(xué)習(xí)過程的進(jìn)行，基于考察標(biāo)記之間相關(guān)性的不同方式，有一階策略、二階策略、高階策略等多標(biāo)記學(xué)習(xí)問題求解策略[3]。在多標(biāo)記學(xué)習(xí)問題中，由于每個(gè)對(duì)象可能同時(shí)具有多個(gè)類別標(biāo)記，因此傳統(tǒng)監(jiān)督學(xué)習(xí)中常用的單標(biāo)記評(píng)價(jià)指標(biāo)，如精度（accuracy）、查準(zhǔn)率（precision）、查全率（recall）等，無法直接用于多標(biāo)記學(xué)習(xí)系統(tǒng)的性能評(píng)價(jià)。因此，研究者們相繼提出了一系列多標(biāo)記評(píng)價(jià)指標(biāo)，總的來看可分為兩種類型，即“基于樣本”的評(píng)價(jià)指標(biāo)[4-6]以及“基于類別”的評(píng)價(jià)指標(biāo)[7]。

多標(biāo)記學(xué)習(xí)的問題轉(zhuǎn)換和算法適應(yīng)是另一個(gè)研究熱點(diǎn)[3, 8]。問題轉(zhuǎn)換方法是將多標(biāo)記問題轉(zhuǎn)換為其它已知的學(xué)習(xí)問題進(jìn)行求解，代表性學(xué)習(xí)算法有一階方法Binary Relevance[9]，該方法將多標(biāo)記學(xué)習(xí)問題轉(zhuǎn)化為“二類分類”問題求解；二階方法[10]，該方法將多標(biāo)記學(xué)習(xí)問題轉(zhuǎn)化為“標(biāo)記排序”問題求解；高階方法[11]，該方法將多標(biāo)記學(xué)習(xí)問題轉(zhuǎn)化為”多類分類”問題求解。算法適應(yīng)直接執(zhí)行多標(biāo)記分類方法,是解決問題的完整形式，通過對(duì)常用監(jiān)督學(xué)習(xí)算法進(jìn)行改進(jìn)，將其直接用于多標(biāo)記數(shù)據(jù)的學(xué)習(xí)。代表性學(xué)習(xí)算法有一階方法ML-kNN[12]，該方法將k近鄰算法進(jìn)行改造以適應(yīng)多標(biāo)記數(shù)據(jù)；二階方法Rank-SVM[13]和CML[5]，Rank-SVM將核學(xué)習(xí)算法SVM進(jìn)行改造以適應(yīng)多標(biāo)記數(shù)據(jù)。

數(shù)據(jù)量增大的同時(shí)，數(shù)據(jù)的維度也越來越高，在多標(biāo)記學(xué)習(xí)過程中，高維數(shù)據(jù)訓(xùn)練和測(cè)試需要更多的計(jì)算時(shí)間和空間。因此，降低高維數(shù)據(jù)的維度是多標(biāo)記學(xué)習(xí)中一個(gè)重要的研究課題。

特征提取和特征選擇是兩種主要的降維方法：特征提取通過某些原始特征映射到低維空間變換[14]，然后生成一些新的特性；特征選擇目的是找到一個(gè)給出一定的預(yù)先確定的標(biāo)準(zhǔn)的最優(yōu)特征子集[15,16]。特征選擇不僅減少了許多特征個(gè)數(shù)，使得學(xué)習(xí)算法效率更高，而且可以提高多標(biāo)記學(xué)習(xí)的性能，因?yàn)樗梢员苊膺^擬合現(xiàn)象。

在高維數(shù)據(jù)中，特征數(shù)量往往較多，但其中存在大量冗余或不相關(guān)的特征，特征選擇是從原始特征集中，按照某一評(píng)價(jià)準(zhǔn)則選擇出一組具有良好區(qū)分特性的特征子集。特征選擇能剔除冗余或不相關(guān)的特征，從而達(dá)到減少特征個(gè)數(shù)、提高模型精確度、減少運(yùn)行時(shí)間等目的，同時(shí)，選取出的特征更有利于理解模型與分析數(shù)據(jù)[17]。

針對(duì)對(duì)多標(biāo)記學(xué)習(xí)中高維數(shù)據(jù)問題，本文基于FisherScore提出多Multi-label FisherScore (MLFS)算法，首先，對(duì)高維數(shù)據(jù)進(jìn)行特征選擇，其次，分析精度與特征選擇率關(guān)系，最后，所提出的方法與現(xiàn)有的特征選擇算法相比，實(shí)驗(yàn)結(jié)果表明，該算法具有明顯優(yōu)勢(shì)。

1 特征選擇相關(guān)工作

按照特征選擇是否獨(dú)立學(xué)習(xí)算法，特征選擇技術(shù)可以分為封裝方法和過濾方法。封裝方法用學(xué)習(xí)算法評(píng)價(jià)特征的重要性[18]，即圍繞挖掘算法“封裝”特征選擇過程，如貝葉斯分類器、支持向量機(jī)和聚類[19, 20]。封裝方法的計(jì)算代價(jià)通常較高[21]，因?yàn)樾枰磸?fù)訓(xùn)練學(xué)習(xí)算法，因而對(duì)多標(biāo)記學(xué)習(xí)中的高維數(shù)據(jù)算處理可能不是有效的。過濾方法分析數(shù)據(jù)的內(nèi)在特征，并在學(xué)習(xí)任務(wù)前根據(jù)某些準(zhǔn)則選擇一定數(shù)據(jù)排名最高的特征[22]。是一個(gè)純粹的預(yù)處理工具，與學(xué)習(xí)算法無關(guān)，因此過濾方法比封裝方法更有效。

許多特征選擇方法使用兩個(gè)特征之間的依賴度來評(píng)價(jià)特征，而不是使用獨(dú)立特征和特征子集之間的特性。利用相似性矩陣并引入矩陣分解技術(shù)進(jìn)行特征選擇，它提供了一個(gè)整批處理模式搜索特征。例如，Nie等人提出了一個(gè)健壯的特征選擇標(biāo)準(zhǔn)，使用結(jié)合L2,1范數(shù)最小化損失函數(shù)和正則化[23]。Farahat等人提出了一種矩陣分解標(biāo)準(zhǔn)特征選擇，提供了一個(gè)高效的貪婪算法[24]。楊等人提出了一個(gè)有效的多任務(wù)特征選擇的在線學(xué)習(xí)算法，在節(jié)約時(shí)間復(fù)雜性和內(nèi)存花費(fèi)上顯示其巨大的優(yōu)勢(shì)[25]。Song等人構(gòu)建一個(gè)用于特征選擇使用Hilbert-Schmidt獨(dú)立性標(biāo)準(zhǔn)的框架，是基于好特性應(yīng)該是與標(biāo)記高度相關(guān)的假設(shè)。趙等人介紹了相似性特征選擇標(biāo)準(zhǔn)，包含許多廣泛使用的標(biāo)準(zhǔn)[26]。

本文提出基于最大相關(guān)最小冗余的特征選擇算法，作對(duì)比的典型特征算法主要是：Relieff特征選擇的策略是隨機(jī)選擇實(shí)例,并根據(jù)最近鄰的特征相關(guān)性設(shè)置權(quán)重，Relieff是特征選擇中是最成功的策略之一[27]；Kruskal-Wallis則使用樣本間總體方差方差進(jìn)行測(cè)試[28]，已成為MATLAB函數(shù)kruskalwallis。

2 評(píng)價(jià)指標(biāo)

根據(jù)多標(biāo)記學(xué)習(xí)的兩個(gè)任務(wù)，即多標(biāo)記分類和標(biāo)記排名，評(píng)價(jià)指標(biāo)也分為兩類：基于分類方法和基于排名方法[2,3]。

2.1 基于分類的評(píng)價(jià)指標(biāo)

基于分類的評(píng)價(jià)指標(biāo)有Average precision和Hamming loss，Average precision是一種最直觀的評(píng)價(jià)方式，評(píng)價(jià)樣本的預(yù)測(cè)標(biāo)記排名中排在相關(guān)標(biāo)記前面的也是相關(guān)標(biāo)記的概率平均，計(jì)算公式如下所示[3]

Hamming loss通過計(jì)算多標(biāo)記分類器預(yù)測(cè)出的標(biāo)記結(jié)果與實(shí)際標(biāo)記的差距來度量多標(biāo)記分類器的性能，計(jì)算公式如下所示[3]

2.2 基于排名的評(píng)價(jià)指標(biāo)

One-error，該方法評(píng)價(jià)每個(gè)樣本的預(yù)測(cè)標(biāo)記排名中，排在第一位的標(biāo)記不在該樣本的相關(guān)標(biāo)記集中的概率評(píng)價(jià)，計(jì)算公式如下所示[3]

Coverage，該方法評(píng)價(jià)每個(gè)樣本的預(yù)測(cè)標(biāo)記排名中需要在標(biāo)記序列表中最少查找到第幾位才可以找出所有與該樣本相關(guān)的標(biāo)記，計(jì)算公式如下所示[3]

Ranking loss，該方法評(píng)價(jià)所有樣本的預(yù)測(cè)標(biāo)記排名中，不相關(guān)標(biāo)記在相關(guān)標(biāo)記前面的概率的平均，計(jì)算公式如下所示[3]。

3 最大相關(guān)最小冗余特征選擇

3.1 最大相關(guān)最小冗余

最大相關(guān)最小冗余是基于互信息的特征選擇方法，它根據(jù)最大統(tǒng)計(jì)依賴性準(zhǔn)則來選擇特征[30]。從特征空間中尋找與目標(biāo)類別有最大相關(guān)性且相互之間具有最少冗余性的m個(gè)特征，最大相關(guān)和最小冗余的定義為[30,31]：

(2)

其中: S表示特征集合; c表示目標(biāo)類別; I( xi; c)表示特征i 和目標(biāo)類別 c之間的互信息； I( xi，xj) 是特征i與特征 j 之間的互信息．給定兩個(gè)隨機(jī)變量x和y，它們之間的互信息根據(jù)其概率密度函數(shù) p( x) 、p( y) 和 p( x，y) 分別定義為

對(duì)于多元變量Sm和目標(biāo)類別c，互信息定義為

(4)

綜合公式（3）和（4），MRMR的特征選擇標(biāo)準(zhǔn)為

公式（5）表示應(yīng)該選擇與類別最大相關(guān)而與候選特征最小冗余的特征．假定已確定一個(gè)有 m個(gè)特征的數(shù)據(jù)集 Sm，下一步需要從數(shù)據(jù)集{S－Sm}中選擇使得式( 4) 最大化的第 m + 1個(gè)特征為

(6)

3.2 基于MRMR多標(biāo)記特征選擇算法

依據(jù)上述公式可以實(shí)現(xiàn)單標(biāo)記特征選擇算法MRMR[30]，沒有考慮多個(gè)類別同時(shí)存在的情況，不適于多標(biāo)記數(shù)據(jù)的特征選擇。為克服這一缺陷，本文將MRMR算法擴(kuò)展到多標(biāo)記問題中，提出一種多標(biāo)記數(shù)據(jù)特征選擇算法：ML-MRMR算法。算法如下：

算法：ML-MRMR

輸入：數(shù)據(jù)矩陣，標(biāo)記矩陣，特征選擇百分比k 輸出：特征選擇集 1: 初始化矩陣Matrix_rank2: for i =1 to multi-label 3: rank= MRMR(train_data, train_target(i)) //由公式（1）到（6）計(jì)算4: Matrix_rank=Matrix_rank+ rank 5: end for 6: ，從而選擇得到特征向量I

4 實(shí)驗(yàn)及分析

實(shí)驗(yàn)中，多標(biāo)記學(xué)習(xí)的四個(gè)數(shù)據(jù)集來源于公開數(shù)據(jù)集，特征選擇運(yùn)行速度明顯提高，同時(shí)精度等評(píng)價(jià)指標(biāo)也提高。數(shù)據(jù)集的具體情況見表1所示。

表1 數(shù)據(jù)集基本描述

4.1 評(píng)價(jià)指標(biāo)結(jié)果

對(duì)比的四個(gè)算法分別是不進(jìn)行特征選擇NSF、Relieff、KruskalWallis、MRMR[27-29]，所有算法及評(píng)價(jià)基于ML-KNN[32]，采用十折交叉驗(yàn)證，實(shí)驗(yàn)結(jié)果見表2所示。

平均精度（Ave. Prec.）越大表明算法越好，其他四個(gè)指標(biāo)Coverage、Hamming loss、One-error、Ranking Loss是越小表明算法越好，從表中可以看出，ML-MRMR特征選擇算法明顯好于其他算法。特別值得提到的是ML-MRMR的算法的所有指標(biāo)都好于NSF，其原因是通過最大相關(guān)最小冗余的選擇，過濾掉了冗余特征而保留優(yōu)化的特征子集，有效提高精度和降低誤差，并提升了高維數(shù)據(jù)的多標(biāo)記學(xué)習(xí)速度，整體提高學(xué)習(xí)模型的性能。

4.2 特征選擇百分比分析

所選特征百分比與學(xué)習(xí)精度關(guān)系，圖1-4顯示基于相似矩陣的ML-MRMR特征選擇算法的學(xué)習(xí)精度大于未作特征選擇的學(xué)習(xí)精度，當(dāng)全部選擇時(shí)則兩者精度一樣。ML-MRMR特征選擇算法在選擇20-60%特征達(dá)到最高精度，增加特征后精度反而有所下降，這是表明全部特征中存在一定的冗余特征，反而影響精度。

圖1 Business精度與所選特征百分比關(guān)系

圖2 Computers精度與所選特征百分比關(guān)系

圖3 Reference精度與所選特征百分比關(guān)系

圖4 Science精度與所選特征百分比關(guān)系

表2 實(shí)驗(yàn)結(jié)果

5 結(jié)語

本文針對(duì)多標(biāo)記學(xué)習(xí)中高維數(shù)據(jù)的降維問題提出一種有效的降維技術(shù)，通過最大相關(guān)最小冗余找到一個(gè)最相關(guān)信息的特征子集，利用ML-MRMR去除冗余特征而選擇有效特征的新方法。對(duì)四個(gè)公開數(shù)據(jù)集，該方法與現(xiàn)有算法相比，實(shí)結(jié)果表明，該算法具有快速和精度高等明顯優(yōu)勢(shì)。

[1] G. Tsoumakas and I. Katakis, Multi-Label Classification: An Overview. 2007.

[2] 李思男, 李寧, and 李戰(zhàn)懷, 多標(biāo)記數(shù)據(jù)挖掘技術(shù):研究綜述. 計(jì)算機(jī)科學(xué), 2013(04): p. 14-21.

[3] M. L. Zhang and Z. H. Zhou, A Review on Multi-Label Learning Algorithms. Ieee Transactions on Knowledge and Data Engineering, 2014. 26(8): p. 1819-1837.

[4] R. E. Schapire and Y. Singer, BoosTexter: A boosting-based system for text categorization. Machine Learning, 2000. 39(2-3): p. 135-168.

[5] N. Ghamrawi and A. McCallum, Collective multi-label classification, in Proceedings of the 14th ACM international conference on Information and knowledge management. 2005, ACM: Bremen, Germany. p. 195-200.

[6] S. Godbole and S. Sarawagi, Discriminative Methods for Multi-labeled Classification, in Advances in Knowledge Discovery and Data Mining, H. Dai, R. Srikant, and C. Zhang, Editors. 2004, Springer Berlin Heidelberg. p. 22-30.

[7] G. Tsoumakas and I. Vlahavas, Random k-Labelsets: An Ensemble Method for Multilabel Classification, in Machine Learning: ECML 2007, J. Kok, et al., Editors. 2007, Springer Berlin Heidelberg. p. 406-417.

[8] T. Grigorios and K. Ioannis, Multi-Label Classification: An Overview. International Journal of Data Warehousing and Mining (IJDWM), 2007. 3(3): p. 1-13.

[9] M. R. Boutell, J. B. Luo, X. P. Shen, and C. M. Brown, Learning multi-label scene classification. Pattern Recognition, 2004. 37(9): p. 1757-1771.

[10] J. Furnkranz, E. Hullermeier, E. L. Mencia, and K. Brinker, Multilabel classification via calibrated label ranking. Machine Learning, 2008. 73(2): p. 133-153.

[11] G. Tsoumakas and I. Vlahavas, Random k-labelsets: An ensemble method for multilabel classification, in Machine Learning: ECML 2007, Proceedings, J.N. Kok, et al., Editors. 2007, Springer-Verlag Berlin: Berlin. p. 406-417.

[12] M. L. Zhang and Z. H. Zhou, ML-KNN: A lazy learning approach to multi-label leaming. Pattern Recognition, 2007. 40(7): p. 2038-2048.

[13] A. Elisseeff and J. Weston, A kernel method for multi-labelled classification, in Advances in Neural Information Processing Systems 14, Vols 1 and 2, T.G. Dietterich, S. Becker, and Z. Ghahramani, Editors. 2002, M I T Press: Cambridge. p. 681-687.

[14] I. Guyon and A. Elisseeff, Feature extraction: foundations and applications, Vol. 207. 2006: Springer.

[15] I. Guyon and A. Elisseeff, An introduction to variable and feature selection. Journal of Machine Learning Research, 2003. 3: p. 1157-1182.

[16] Y.M. Yang and J.O. Pedersen. A comparative study on feature selection in text categorization. in International Conference on Machine Learning. 1997.

[17] 黃莉莉, 湯進(jìn), 孫登第, and 羅斌, 基于多標(biāo)記ReliefF的特征選擇算法. 計(jì)算機(jī)應(yīng)用, 2012(10): p. 2888-2890+2898.

[18] H. Liu and L. Yu, Toward integrating feature selection algorithms for classification and clustering. IEEE Transactions on Knowledge and Data Engineering, 2005. 17(4): p. 491-502.

[19] J. Weston, S. Mukherjee, O. Chapelle, M. Pontil, T. Poggio, and V. Vapnik. Feature selection for SVMs. in Advances in Neural Information Processing Systems. 2000.

[20] M. Dash, K. Choi, Peter Scheuermann, and Huan Liu. Feature selection for clustering - a filter solution. in IEEE International Conference on Data Mining. 2002.

[21] R. Kohavi and G.H. John, Wrappers for feature subset selection. Artificial Intelligence, 1997. 97(1-2): p. 273-324.

[22] L. Yu and H. Liu. Feature selection for high-dimensional data: a fast correlation-based filter solution. in Proceedings of the Twentieth International Conference on Machine Learning. 2003.

[23] F.P. Nie, H. Huang, X. Cai, and C. Ding. Efficient and robust feature selection via joint $_2,1$-norms minimization. in Advances in Neural Information Processing Systems. 2010.

[24] A.K. Farahat, A. Ghodsi, and M.S. Kamel, Efficient greedy feature selection for unsupervised learning. Knowledge and information systems, 2013. 35: p. 285-310.

[25] H.Q. Yang, M.R. Lyu, and I.King, Efficient online learning for multitask feature selection. ACM Transactions on Knowledge Discovery from Data, 2013. 7(2): p. 1-27.

[26] Z. Zhao, L. Wang, H. Liu, and J.P. Ye, On similarity preserving feature selection. Knowledge and Data Engineering, IEEE Transactions on, 2013. 25(3): p. 619-632.

[27] H. Liu and H. Motoda, Computational Methods of Feature Selection, 2008: Chapman & Hall.

[28] L. J. Wei, Asymptotic Conservativeness and Efficiency of Kruskal-Wallis Test for K Dependent Samples. Journal of the American Statistical Association, 1981. 76(376): p. 1006-1009.

[29] H. Long Peng, F. Ding C., Feature Selection Based on Mutual Information: Criteria of Max-Dependency, Max-Relevance, and Min-Redundancy. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005. 27(8): p. 1226-1238.

[30] H.C Peng, F.H Long, and C. Ding, Feature selection based on mutual information: criteria of max-dependency, max-relevance, and min-redundancy. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005. Vol. 27(No. 8): p. pp.1226-1238.

[31] 丁建睿, 黃劍華, 劉家鋒, and 張英濤, 基于mRMR和SVM的彈性圖像特征選擇與分類. 哈爾濱工業(yè)大學(xué)學(xué)報(bào), 2012(05): p. 81-85.

[32] ZHANG ML, ZHOU ZH.ML-KNN: A lazy learning approach to multi-label learning. Pattern Recognition, 2007. 40: p. 2038-2048.

Feature Selection via Max-Relevanceand Min-Redundancy in Multi-label Learning

YANG Wenyuan*

(Lab of Granular Computing, Minnan Normal University, Zhangzhou, Fujian 363000, China)

High dimensional data affects the speed of multi-label learning. This paper proposes the ML-MRMR algorithm for multi-label feature selection. By using the mutual information of data and labels, the features of maximum correlation and minimum redundancy obtained. The relationship between precision and selected percent of features is also analyzed. Experimental results show that the ML-MRMR algorithm is better than existing ones in terms of speed and precision.

multi-label learning; feature selection; max-relevance and min-redundancy; dimensionality reduction

1672-9129(2016)02-0021-05

TP181

A

2016-09-13；

2016-09-24。

國家自然科學(xué)基金61379049。

楊文元（1967－)，男，博士，副教授，主要研究方向：機(jī)器學(xué)習(xí)、粒計(jì)算。

(*通信作者電子郵箱yangwy@mnnu.edu.cn)