基于最大相關最小冗余的多標記特征選擇

楊文元

?

基于最大相關最小冗余的多標記特征選擇

楊文元*

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

針對多標記學習中高維數據運行速度問題，提出一種基于最大相關最小冗余的特征選擇算法ML-MRMR。利用數據與標記的互信息，獲得了最大相關性最少冗余性特征集合。分析了所選特征百分比與精度關系。實驗結果表明，所提出算法在速度和精度上都具有明顯的優勢。

多標記學習；特征選擇；最大相關最小冗余；數據降維

引言

隨著計算機網絡和信息化的發展，網絡數據和資源呈海量特征，數據的標注結構復雜程度也在增加，傳統的單標記方法無法滿足對復雜數據進行分析處理的需求，以機器學習技術為基礎的多標記學習技術現已成為一個研究熱點，其研究成果廣泛地應用于各種不同的領域，如圖像視頻的語義標注、功能基因組、音樂情感分類以及營銷指導等[1, 2]。多標記學習的主要特點在于它能反映真實世界對象具有的多義性。因此，在最近十年來,多標記學習已逐漸吸引國內外許多一流的學術機構和科學研究者。

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

多標記學習的問題轉換和算法適應是另一個研究熱點[3, 8]。問題轉換方法是將多標記問題轉換為其它已知的學習問題進行求解，代表性學習算法有一階方法Binary Relevance[9]，該方法將多標記學習問題轉化為“二類分類”問題求解；二階方法[10]，該方法將多標記學習問題轉化為“標記排序”問題求解；高階方法[11]，該方法將多標記學習問題轉化為”多類分類”問題求解。算法適應直接執行多標記分類方法,是解決問題的完整形式，通過對常用監督學習算法進行改進，將其直接用于多標記數據的學習。代表性學習算法有一階方法ML-kNN[12]，該方法將k近鄰算法進行改造以適應多標記數據；二階方法Rank-SVM[13]和CML[5]，Rank-SVM將核學習算法SVM進行改造以適應多標記數據。

數據量增大的同時，數據的維度也越來越高，在多標記學習過程中，高維數據訓練和測試需要更多的計算時間和空間。因此，降低高維數據的維度是多標記學習中一個重要的研究課題。

特征提取和特征選擇是兩種主要的降維方法：特征提取通過某些原始特征映射到低維空間變換[14]，然后生成一些新的特性；特征選擇目的是找到一個給出一定的預先確定的標準的最優特征子集[15,16]。特征選擇不僅減少了許多特征個數，使得學習算法效率更高，而且可以提高多標記學習的性能，因為它可以避免過擬合現象。

在高維數據中，特征數量往往較多，但其中存在大量冗余或不相關的特征，特征選擇是從原始特征集中，按照某一評價準則選擇出一組具有良好區分特性的特征子集。特征選擇能剔除冗余或不相關的特征，從而達到減少特征個數、提高模型精確度、減少運行時間等目的，同時，選取出的特征更有利于理解模型與分析數據[17]。

針對對多標記學習中高維數據問題，本文基于FisherScore提出多Multi-label FisherScore (MLFS)算法，首先，對高維數據進行特征選擇，其次，分析精度與特征選擇率關系，最后，所提出的方法與現有的特征選擇算法相比，實驗結果表明，該算法具有明顯優勢。

1 特征選擇相關工作

按照特征選擇是否獨立學習算法，特征選擇技術可以分為封裝方法和過濾方法。封裝方法用學習算法評價特征的重要性[18]，即圍繞挖掘算法“封裝”特征選擇過程，如貝葉斯分類器、支持向量機和聚類[19, 20]。封裝方法的計算代價通常較高[21]，因為需要反復訓練學習算法，因而對多標記學習中的高維數據算處理可能不是有效的。過濾方法分析數據的內在特征，并在學習任務前根據某些準則選擇一定數據排名最高的特征[22]。是一個純粹的預處理工具，與學習算法無關，因此過濾方法比封裝方法更有效。

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

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

2 評價指標

根據多標記學習的兩個任務，即多標記分類和標記排名，評價指標也分為兩類：基于分類方法和基于排名方法[2,3]。

2.1 基于分類的評價指標

基于分類的評價指標有Average precision和Hamming loss，Average precision是一種最直觀的評價方式，評價樣本的預測標記排名中排在相關標記前面的也是相關標記的概率平均，計算公式如下所示[3]

Hamming loss通過計算多標記分類器預測出的標記結果與實際標記的差距來度量多標記分類器的性能，計算公式如下所示[3]

2.2 基于排名的評價指標

One-error，該方法評價每個樣本的預測標記排名中，排在第一位的標記不在該樣本的相關標記集中的概率評價，計算公式如下所示[3]

Coverage，該方法評價每個樣本的預測標記排名中需要在標記序列表中最少查找到第幾位才可以找出所有與該樣本相關的標記，計算公式如下所示[3]

Ranking loss，該方法評價所有樣本的預測標記排名中，不相關標記在相關標記前面的概率的平均，計算公式如下所示[3]。

3 最大相關最小冗余特征選擇

3.1 最大相關最小冗余

最大相關最小冗余是基于互信息的特征選擇方法，它根據最大統計依賴性準則來選擇特征[30]。從特征空間中尋找與目標類別有最大相關性且相互之間具有最少冗余性的m個特征，最大相關和最小冗余的定義為[30,31]：

(2)

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

對于多元變量Sm和目標類別c，互信息定義為

(4)

綜合公式（3）和（4），MRMR的特征選擇標準為

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

(6)

3.2 基于MRMR多標記特征選擇算法

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

算法：ML-MRMR

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

4 實驗及分析

實驗中，多標記學習的四個數據集來源于公開數據集，特征選擇運行速度明顯提高，同時精度等評價指標也提高。數據集的具體情況見表1所示。

表1 數據集基本描述

4.1 評價指標結果

對比的四個算法分別是不進行特征選擇NSF、Relieff、KruskalWallis、MRMR[27-29]，所有算法及評價基于ML-KNN[32]，采用十折交叉驗證，實驗結果見表2所示。

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

4.2 特征選擇百分比分析

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

圖1 Business精度與所選特征百分比關系

圖2 Computers精度與所選特征百分比關系

圖3 Reference精度與所選特征百分比關系

圖4 Science精度與所選特征百分比關系

表2 實驗結果

5 結語

本文針對多標記學習中高維數據的降維問題提出一種有效的降維技術，通過最大相關最小冗余找到一個最相關信息的特征子集，利用ML-MRMR去除冗余特征而選擇有效特征的新方法。對四個公開數據集，該方法與現有算法相比，實結果表明，該算法具有快速和精度高等明顯優勢。

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

[2] 李思男, 李寧, and 李戰懷, 多標記數據挖掘技術:研究綜述. 計算機科學, 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] 黃莉莉, 湯進, 孫登第, and 羅斌, 基于多標記ReliefF的特征選擇算法. 計算機應用, 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的彈性圖像特征選擇與分類. 哈爾濱工業大學學報, 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。

國家自然科學基金61379049。

楊文元（1967－)，男，博士，副教授，主要研究方向：機器學習、粒計算。

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