多標簽學習中基于互信息的快速特征選擇方法

徐洪峰 孫振強

摘 要：針對傳統的基于啟發式搜索的多標記特征選擇算法時間復雜度高的問題，提出一種簡單快速的多標記特征選擇（EF-MLFS）方法。首先使用互信息（MI）衡量每個維度的特征與每一維標記之間的相關性，然后將所得相關性相加并排序，最后按照總的相關性大小進行特征選擇。將所提方法與六種現有的比較有代表性的多標記特征選擇方法作對比，如最大依賴性最小冗余性（MDMR）算法和基于樸素貝葉斯的多標記特征選擇（MLNB）方法等。實驗結果表明，EF-MLFS方法進行特征選擇并分類的結果在平均準確率、覆蓋率、海明損失等常見的多標記分類評價指標上均達最優;該方法無需進行全局搜索，因此時間復雜度相較于MDMR、對偶多標記應用（PMU）等方法也有明顯降低。

關鍵詞： 多標簽學習;特征選擇;互信息;標記相關性

中圖分類號：TP181

文獻標志碼：A

Abstract：Concerning the high time complexity of traditional heuristic search-based multi-label feature selection algorithm， an Easy and Fast Multi-Label Feature Selection （EF-MLFS） method? was proposed. Firstly， Mutual Information （MI） was used to measure the features and the correlations between the labels of each dimension; then， the obtained correlations were added up and ranked; finally， feature selection was performed according to the total correlation. The proposed method was compared to six existing representative multi-label feature selection methods such as Max-Dependency and Min-Redundancy （MDMR） algorithm， Multi-Label Naive Bayes （MLNB） method. Experimental results show that the average precision， coverage， Hamming Loss and other common multi-label classification indicators are optimal? after feature selection and classificationby using EF-MLFS method. In addition， global search is not required in the method， so the time complexity is significantly reduced compared with MDMR and Pairwise Mutli-label Utility （PMU）.

Key words：? multi-label learning; feature selection; mutual information; label correlation

0 引言

在傳統的監督學習任務中，每個樣本被默認為只具有一種語義信息，也就是只包含一種分類標簽。然而，這樣的假設往往與現實世界的真實情況不符，例如，在圖片分類任務中，一張沙灘風景圖片往往同時包含“大海”“輪船”“落日”等景物，由此可見，使用單一標記無法充分表達其語義信息，同樣使用傳統的單標記分類方法將很難對這種情況進行準確的分類。多標記學習（Multi-label Learning）[1]應運而生，并在信息檢索[2]、生物信息[3]、藥物研發[4]以及傳統中醫診斷[5-6]等領域取得了出色的成果。

與傳統監督學習相比，多標記學習的輸入輸出空間維度更大。在大多數情況下，相較于單標記數據集，為了支持多個標記的學習任務，多標記數據的特征往往更加冗余和稀疏。然而，過高的特征維度將會導致維度災難的發生，這將使得多標記學習任務效率變得低效和困難。因此，有效地解決多標記學習任務中的維度災難問題變得十分關鍵。

特征選擇方法是直接從原始特征空間選擇特征子集，因此保留了原始特征的物理含義，具有極強的可解釋性和易操作性，尤其在高維數據集和有限數據集的數據預處理任務中具有十分重要的地位。特征選擇方法根據一定的評價標準，從原始特征空間中選擇一組最優特征子集，從而降低特征維度，提高分類性能。目前比較常見的評價標準有：依賴性度量、距離度量和信息度量。同時，區分多標記學習任務與傳統學習框架的特點就是其不同標記之間往往具有相關性，而對這些相關性的有效利用將會有效降低學習任務的難度。根據朱越等[1]的研究，目前標記相關性可以分為一階相關性、二階相關性和三階相關性。

目前，大部分的研究工作均為對特征選擇過程中使用的“最大相關性，最小冗余性”標準中的相關性和冗余性進行相關分析，從而導致了計算資源的浪費。本文在進行一系列實驗時觀察到，大多數多標記數據集由于其特征空間的高維性和稀疏性，其特征與特征之間的冗余程度往往很小。因此在多標記特征選擇問題當中，冗余性的加入往往無法提升特征選擇的效果，反而會增加不必要的計算資源的浪費。本文提出了一種簡單快速的多標記特征選擇（Easy and Fast Multi-Label Feature Selection， EF-MLFS）方法，是一種只利用特征標記相關性的極簡且效果很好的特征選擇算法。

1 相關工作

在多標記特征選擇發展的幾十年里，涌現出了許多杰出的工作。為了更好地區分每種方法的相似和不同之處，相關學者對已有的特征選擇方法進行了分類，目前廣泛認可的分類方法有兩種：第一種分類方法從特征選擇的策略角度出發，將特征選擇方法分為封裝（wrapper）方法[7]、過濾（filter）方法[8]和嵌入（embedded）方法[9];第二種分類方法從標記利用角度出發，將特征選擇方法分為有監督（supervised）[7]、無監督（unsupervised）[10]和半監督（semi-supervised）[11]特征選擇方法。

本文主要利用互信息（Mutual Information， MI）和標記相關性（Label Correlation）

進行特征選擇。在利用信息論進行特征選擇的眾多方法中，最經典的兩種方法被稱為互信息特征選擇（MI Feature Selection， MIFS）[11]和 最大相關最小冗余性（maximum Relevance Minimum Redundancy， mRMR）[12]。在MIFS方法中利用互信息估計某一維特征的信息量，并利用“貪心”搜索方法選擇最優特征子集;在mRMR方法中選擇出的特征子集具有“最大相關性，最小冗余性”的特點。除此之外，還有許多學者利用信息論進行特征選擇的優秀工作，例如Lin等[13]提出最大獨立性最小冗余性（Max-Dependency and Min-Redundancy， MDMR）算法;Lee等[14]利用多元互信息提出一種對偶多標記應用宋國杰等[8]提出一種基于最大熵原理特征選擇方法;朱顥東等[15]提出一種優化的互信息特征選擇算法等。

除此之外，近幾年利用標記信息進行特征選擇的方法也不斷涌現。例如，Wang等[16]通過最大化非獨立分類信息進行特征選擇;Brown等[17]提出一種針對信息論的聯合特征選擇框架;蔡亞萍等[18]提出一種利用局部標記相關性的特征選擇方法;楊明等[19]提出一種結合標記相關性的半監督特征選擇方法;Braytee等[20]提出一種基于非負矩陣分解的特征選擇方法;Liu等[21]提出一種基于標記相關性的加權特征選擇方法;Monard等[22]提出了一種根據原始標記相關性進行標記空間重構的方法。

2 相關知識

2.1 互信息與最大相關最小冗余性（mRMR）

信息論[23]已經被廣泛應用于諸多領域。作為信息理論的重要組成部分，互信息是一種衡量相關性的有效手段，描述了兩組變量之間信息共享的程度。例如，兩組隨機變量A和B之間的互信息可以定義如下：

其中： p（a，b）為A、B的聯合概率分布。

mRMR作為特征選擇的經典算法，已經演變出許多變種。

mRMR的作者認為“前m個最好的特征不一定是最好的m個特征”，因為前m個特征可能存在大量相關信息，這些特征之間具有高度相關性，所以作者提出mRMR框架，并將其形式化描述為：

2.2 評價指標

考慮與其他方法的比較，本文中選取了海明損失、One-Error、覆蓋率、排序損失和平均準確率作為評價指標。

本文將統一使用yi∈L表示真實標記， y′i表示對特征向量xi的預測標簽，N表示樣本數量，m表示標記維度。

其中：為異或運算。該指標計算的是在所有N*m個預測標記中犯錯的比例，其值在0～1，指標值越小越好。該指標計算預測結果中最可能的標記預測錯誤的比例，其值在0～1，指標值越小越好。該指標反映的是在預測的標記序列中，要覆蓋所有的相關標記需要的搜索深度，其值越小表示所有相關標記均被排在比較靠前的位置。

4）排序損失（Ranking Loss， RL）：其中： yi和i分別表示xi的相關標記集和無關標記集，該指標計算相關與無關標記對出現錯誤的比例，指標值越小越好。該指標衡量的是按照預測值排序的標記序列中，被排在相關標記之前的標記仍是相關標記的情況，指標值越大越好在多標記特征選擇問題中，“最大相關性，最小冗余性”是一個經典且證實有效的特征選擇標準目前該標準的優化算法仍然是建立在最大相關性和最小冗余性的基礎上。

但對主要多標記數據集上進行實驗時發現，特征間的冗余性或許并不是特征選擇過程中所必須考慮到的因素，而特征與標記相關性衡量可能對特征選擇結果起到決定性作用。同時，忽略特征間冗余性的影響，將會大幅簡化算法運算過程，從而提高算法性能。根據“奧卡姆剃刀”原則忽略特征冗余度的影響，不僅未降低算法性能，反而在大多數數據集上大幅提升了特征選擇的效果。

在多數的多標記數據集中，標記特征相關性往往可以提供重要信息，利用這些信息將有效降低學習任務的難度，同時提升學習結果的魯棒性。

在多標記數據集中，特征往往是連續或高度離散的，同時十分稀疏。因此，無論是使用互信息，還是用歐氏距離的方法衡量特征間的冗余度，其結果可以發現特征與特征間的冗余性幾乎為零，其效果往往微乎其微甚至對特征標記相關性的使用產生負面影響。同時，多標記的監督學習中最重要的就是對標簽的有效利用，

因此本文從最簡單設想切入，利用互信息來衡量特征標記相關性，同時忽略掉冗余性的影響，最后依據特征標記相關性的大小來進行特征選擇。

首先，使用互信息計算每一維特征標記之間的相關性矩陣R：其中：Ri， j為相關性矩陣的每一個元素; fi表示第i維特征向量;lj表示第j維標記向量。假設所選數據集中有N維特征向量，K維標記向量，則矩陣R為一個N*K的矩陣。該矩陣中蘊含的就是特征標記相關性信息，數值越大代表特征與標記之間的相關性越強。如果某一維度特征與所有標記相關性的總和最大，則它就是最重要的特征，根據重要性進行排序，將會得到一個特征重要性的有序向量。

根據以上假設，本文將矩陣R按列相加，得到特征重要性向量I：最后根據向量I的大小從大到小進行排序并記錄相應的特征維度標記，得到最后的特征重要性排序向量I-Rank。

4 實驗與分析

為了評測EF-MLFS算法的性能，本文將在6個真實數據集上與其他6種特征選擇算法進行對比實驗。

實驗采用多標記最近鄰（Multi-Label K Nearest Neighbors， ML-KNN）[24]作為分類算法對特征選擇后的數據集進行評估，并將近鄰數量k設置為15。

對比算法的參數設置依照原論文給出的推薦參數進行設置。ML-KNN相關代碼可以在LAMDA實驗室主頁進行下載（http：//lamda.nju.edu.cn/CH.MainPage.ashx）。

4.1 實驗數據及設置

本實驗數據主要來自于公開多標記數據集網站MULAN（http：//mulan.sourceforge.net），其中Arts、Business、Education、Health、Science五個網頁數據集屬于Yahoo數據集，每個數據集含5000個樣本，提取的特征表示不同的詞在文本中的頻率，標記表示文本的類別信息;Yeast為生物數據集，包含2417個樣本，其特征維度是103。表1列出了所使用數據集的詳細信息。同時，為比較EF-MlFS算法的性能，實驗將與基于樸素貝葉斯的多標記特征選擇（Multi-Label Naive Bayes， MLNB）[25]、PMU[14]、

MDDMspc（Mutli-label Dimensionality Reduction via Dependecnce Maximization with Uncorrelated Feature Constraint）[26]

、MDDMproj（Multi-label Dimension Reduction via Dependence Maximization with Uncorrelated Projection Constraint）[26]、MDMR[13]以及COMI（Convex Optimization and MI）[27]6種多標記特征選擇算法在上述評價指標上進行比較，其中COMI方法[27]為Lim等于2017年提出的一種基于互信息與凸優化的方法，該方法改進了以往基于啟發式搜索的特征選擇策略，在mRMR方法的基礎上利用互信息計算相關性與冗余性，是目前基于互信息進行特征選擇的眾多方法中比較有代表性的一種。

4.2 實驗結果與分析

為對比各算法所能達到的最好分類效果，本文實驗將最優特征子集維度從1調整至最大并繪制得分曲線，雖然MLNB算法最大特征數量與其他算法不同，但仍具有可比性。

1）實驗曲線在前幾個特征呈明顯上升或下降趨勢，在達到最優值后呈相反趨勢變化，說明特征選擇算法對大多數數據集有效，并且可以選擇出效果明顯好于使用所有特征進行分類的特征子集。

2）EF-MLFS方法在Arts、Business、Education、Health、Science、Yeast共6個數據集上的5種評價指標均可以達到最優的效果，同時在Arts與Health等文本數據集上效果也非常顯著，說明本文方法泛化效果與選擇結果均優于其他方法。

3）MDDM是一種基于矩陣分解的方法，因此其在時間性能上有明顯優勢?？紤]到EF-MLFS方法幾乎不需要任何復雜的矩陣運算，大部分時間消耗來自于計算特征-標記相關性矩陣，因此EF-MLFS方法相較于MDMR、MLNB、PMU三種方法在時間性能上均有三個量級的提升效果。

4）EF-MLFS方法具有最高的性能時間比，可以在提高性能的前提下，大幅提高算法效率。

5）COMI方法雖然也是一種基于互信息的多標記特征選擇方法，但原文中并未對其數據預處理進行詳細描述，同時其特征選擇過程中涉及到全局優化的過程，雖然較傳統的啟發式搜索方法在時間性能上有較大提升，但在性能和時間上均未達到最優效果。因此EF-MLFS方法雖然簡單，但是仍可達到較優的性能。

總體來講，EF-MLFS算法在上述對比指標下均有不錯的表現，尤其EF-MLFS算法是一種快速有效的特征選擇方法，該方法具有更強的魯棒性和更好的泛化性，可以適應多個應用場景并找到最優特征子集。同時，上述實驗也驗證了第3章中關于特征空間冗余性的假設。

5 結語

本文在針對經典特征選擇框架“最大相關性，最小冗余性”進行研究時發現，在大多數公開的多標記數據集中，冗余性的加入并不能有效提高多標記特征選擇的效果，反而會加大特征選擇過程的運算量，降低選擇效率。因此，根據“奧卡姆剃刀”的核心原則“如無必要，勿增實體”的思想，將冗余性去掉，只利用特征標記相關性進行多標記特征選擇，并得到了很好的結果。

但是，本文仍有諸多不足之處，需要在未來的工作當中進行改進。例如，如何有效定量驗證數據當中冗余性是否必要，如何更加準確地衡量特征標記相關性，以及如何更加有效地挖掘特征標記相關性當中蘊含的信息。同時針對標記相關性的研究工作也日益增多，對如何有效利用標記之間的相關性也是未來的研究方向。

參考文獻（References）

[1] 朱越， 姜遠， 周志華. 一種基于多示例多標記學習的新標記學習方法[J]. 中國科學： 信息科學， 2018， 48（12）： 1670-1680. （ZHU Y， JIANG Y， ZHOU Z H. Multi-instance multi-label new label learning[J]. Scientia Sinica （Information）， 2018， 48（12）： 1670-1680.）

[2] SCHAPIRE R E， SINGER Y. BoosTexter： a boosting-based system for text categorization[J]. Machine Learning， 2000， 39（2/3）： 135-168.

[3] DIPLARIS S， TSOUMAKAS G， MITKAS P A， et al. Protein classification with multiple algorithms[C]// Proceedings of the 2005 Panhellenic Conference on Informatics， LNCS 3746. Berlin： Springer， 2005： 448-456.

[4] 彭利紅， 劉海燕， 任日麗， 等. 基于多標記學習預測藥物靶標相互作用[J]. 計算機工程與應用， 2017， 53（15）： 260-265. （PENG L H， LIU H Y， REN R L， et al. Predicting drug-target interactions with multi-label learning[J]. Computer Engineering and Applications， 2017， 53（15）： 260-265.）

[5] LIU G P， LI G Z， WANG Y L， et al. Modelling of inquiry diagnosis for coronary heart disease in traditional Chinese medicine by using multi-label learning[J]. BMC Complementary and Alternative Medicine， 2010， 10（1）： No.37.

[6] DAI L， ZHANG J， LI C， et al. Multi-label feature selection with application to TCM state identification[J/OL]. Concurrency and Computation： Practice and Experience， 2018： No.e4634. [2019-01-10]. https：//onlinelibrary.wiley.com/doi/abs/10.1002/cpe.4634.

[7] GUYON I， ELISSEEFF A. An introduction to variable and feature selection[J]. Journal of Machine Learning Research， 2003， 3： 1157-1182.

[8] 宋國杰， 唐世渭， 楊冬青， 等. 基于最大熵原理的空間特征選擇方法[J]. 軟件學報， 2003， 14（9）： 1544-1550. （SONG G J， TANG S W， YANG D Q， et al. A spatial feature selection method based on maximum entropy theory[J]. Journal of Software， 2003， 14（9）： 1544-1550.）

[9] GUYON I， WESTON J， BARNHILL S， et al. Gene selection for cancer classification using support vector machines[J]. Machine Learning， 2002， 46（1/2/3）： 389-422.

[10] DY J G. BRODLEY C E. Feature selection for unsupervised learning[J]. Journal of Machine Learning Research， 2004，5： 845-889.

[11] BATTITI R. Using mutual information for selecting features in supervised neural net learning[J]. IEEE Transactions on Neural Networks， 1994， 5（4）： 537-550.

[12] PENG H， LONG F， DING C. Feature selection based on mutual information criteria of max-dependency， max-relevance， and min-redundancy[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2005， 27（8）： 1226-1238.

[13] LIN Y， LIU J， LIU J， et al. Multi-label feature selection based on max-dependency and min-redundancy[J]. Neurocomputing， 2015， 168： 92-103.

[14] LEE J， KIM D. Feature selection for multi-label classification using multivariate mutual information[J]. Pattern Recognition Letters， 2013， 34（3）： 349-357.

[15] 朱顥東， 陳寧， 李紅嬋. 優化的互信息特征選擇方法[J]. 計算機工程與應用， 2010， 46（26）： 122-124. （ZHU H D， CHEN N， LI H C. Optimized mutual information feature selection method[J]. Computer Engineering and Applications， 2010， 46（26）： 122-124.）

[16] WANG J， WEI J， YANG Z， et al. Feature selection by maximizing independent classification information[J]. IEEE Transactions on Knowledge and Data Engineering， 2017， 29（4）： 828-841.

[17] BROWN G， POCOCK A， ZHAO M， et al. Conditional likelihood maximization： a unifying framework for information theoretic feature selection[J]. Journal of Machine Learning Research， 2012， 13： 27-66.

[18] 蔡亞萍， 楊明. 一種利用局部標記相關性的多標記特征選擇算法[J]. 南京大學學報（自然科學版）， 2016， 52（4）： 693-704. （CAI Y P， YANG M. A multi-label feature selection algorithm by exploiting label correlations locally[J]. Journal of Nanjing University （Natural Science Edition）， 2016， 52（4）： 693-704.）

[19] 楊明， 蔡亞萍. 一種結合標記相關性的半監督多標記特征選擇及分類方法： CN201610256462.9[P]. 2016-09-28[2019-01-10]. （YANG M， CAI Y P. A semi-supervised multi-label feature selection and classification method combined with marker correlation： CN201610256462.9[P]. 2016-09-28[2019-01-10].）

[20] BRAYTEE A， LIU W， CATCHPOOLE D R， et al. Multi-label feature selection using correlation information[C]// Proceedings of the 2017 ACM Conference on Information and Knowledge Management. New York： ACM， 2017： 1649-1656.

[21] LIU L， ZHANG J， LI P， et al. A label correlation based weighting feature selection approach for multi-label data[C]// Proceedings of the 2016 International Conference on Web-Age Information Management， LNCS 9659. Cham： Springer， 2016： 369-379.

[22] SPOLAR N， MONARD M C， TSOUMAKAS G. A systematic review of multi-label feature selection and a new method based on label construction[J]. Neurocomputing， 2016， 180： 3-15.

[23] SHANNON C E. A mathematical theory of communication[J]. Bell System Technical Journal， 1948， 27（4）： 623-656.

[24] ZHANG M， ZHOU Z. ML-KNN： a lazy learning approach to multi-label learning[J]. Pattern Recognition， 2007， 40（7）： 2038-2048.

[25] ZHANG M， PEA J M， ROBLES V. Feature selection for multi-label naive Bayes classification[J]. Information Sciences， 2009， 179（19）： 3218-3229.

[26] ZHANG Y， ZHOU Z H. Multi-label dimensionality reduction via dependence maximization[C]//? Proceedings of the 23rd National Conference on Artificial Intelligence. Menlo Park， CA： AAAI Press， 2008， 3： 1503-1505.

[27] LIM H， LEE J， KIM D. Optimization approach for feature selection in multi-label classification[J]. Pattern Recognition Letters， 2017， 89： 25-30.