基于專家特征的條件互信息多標記特征選擇算法

程玉勝，宋 帆，王一賓，2，錢 坤

（1.安慶師范大學計算機與信息學院，安徽安慶246011；2.安徽省高校智能感知與計算重點實驗室，安徽安慶246011）

0 引言

多標記學習［1］作為機器學習等領域的研究熱點之一，較之傳統的單標記學習中的一個對象只能局限于單個標記，多標記學習框架更具有實際性和廣泛性。在真實世界中，一個對象可能隸屬于多個標記［2］，此時，單個標記就難以表述對象的完整性。所以，多標記學習的研究對于多義性對象的學習建模更具有實際運用意義，近年來已成為一個新的研究熱點［3-4］。

在多標記學習問題中，由于數據的高維性會引起維數災難，導致分類器精度降低［5］。而特征選擇作為一種普遍的降維手段，對于分類器的分類精度和泛化性能起重要作用。特征選擇的首要目的是在樣本數據集中找到一個特征子集，且使得找到的特征子集蘊含盡可能多的區分類別信息，同時要考慮子集內部的冗余性盡量?。?］。而信息論中的互信息理論，作為不確定性的一種有效度量方式，被廣泛用于多標記特征選擇，因此許多學者在此方面進行了研究。例如Zhang等［7］提出的基于最大相關性的多標記維度約簡（Multi-label Dimensionality reduction via Dependence Maximization，MDDM）算法。Lee 等［8］通過多元互信息最大化已選特征與標記集合的相關性，提出了基于多變量互信息的多標記特征選擇算法PMU（Pairwise Multivariate mutual information）。Lin 等［9］提出了基于鄰域互信息的多標記特征選擇。劉景華等［10］通過互信息排序已選特征和標記的相關性，提出了基于局部子空間的多標記特征選擇算法（Multi-label Feature Selection algorithm based on Local Subspace，MFSLS）。

上述算法的多標記特征選擇算法判定特征是否冗余的標準單一，如信息熵方法僅考慮特征和標記間的相關性，未考慮特征和特征間的關系［11］；聯合互信息雖然考慮了整體互信息大小，但未考慮單個特征和標記間的相關性。這些算法都沒有提取關注專家特征，在整個特征集中進行特征選擇，因此時間復雜度很高，如PMU 算法在大數據集中執行時間很長，基于信息熵的多標簽特征選擇（Multi-Label Feature Selection based on Information Entropy，MLFSIE）算法雖然提高了執行速度，但未考慮特征間的冗余性。

除此之外，包括上述算法在內的大多數多標記特征選擇算法均未考慮到優先挑選出專家特征的現實意義，忽略了一個關鍵的問題：在現實生活中，人們針對分類問題時，通常根據專家經驗選取幾個或者多個最重要的特征，然后再通過相關評價準則建立特征向任務目標的映射進行多標記分類。例如，在醫院中專家醫師看病人的病情時，往往根據自己的多年臨床經驗先確定幾個最重要的病癥（即對結果不可或缺起到重要作用的特征（專家特征）），然后再在專家特征的基礎上進行各種身體檢查、血液化驗、分析病歷，最后分析匯總來確診。同時也要考慮某些看似不顯眼的癥狀（即與標記空間相關性較弱的特征），因為忽略某些重要性較次要的特征也會產生誤診的可能。

基于此，再結合信息論中的互信息［12-14］，本文提出一種基于專家特征的條件互信息多標記特征選擇算法（Multi-label Feature Selection algorithm based on Conditional Mutual Information of Expert Feature，MFSEF）。該算法在最小冗余最大相關性前提下，通過子空間劃分，考慮了重要性較次要的特征可能對分類性能產生的影響，受現實生活中實際問題的啟發，兼顧考慮了可能決定整體的預測方向的專家特征，從而提升多標記分類性能。首先通過瀑布圖聯合互信息選出幾個最關鍵的專家特征；再以該專家特征作條件，保持專家特征不變，與余下的特征作并集，構建融合一個新的特征空間，然后計算新特征與標記集合之間的互信息，再進行排序形成新的特征排序集合；借鑒MFSLS 的思想，最后進行特征選擇。實驗在7 個多標記數據集上測試，同其他常用的多標記特征選擇算法進行比較，通過4 個評價指標的結果可以看出，本文算法優于通用的多標記特征選擇算法。最后，還通過統計假設檢驗進一步證實了本文方法的合理性與穩定性。

1 理論介紹

1.1 多標記學習

由于真實世界的對象具有多義性，多標記學習框架作為一種多義性對象學習建模工具由此產生［15］。在該框架下，每個對象由一個示例描述，每個示例具有多個但有限的類別標記，學習的目的是為每個未知示例賦予正確的標記。在數學語言中，多標記問題可描述為：假定X={x1，x2，…，xn}Τ∈Rn*d表示有n 個樣本且每個樣本特征維度為d，Y={1，2，…，Q}表 示 樣 本 對 應 的 標 記 集 合［16］。T={(x1，Y1)，(x2，Y2)，…，（xm，Ym）}（xi∈X，Yi∈Y）表示訓練集，多標記學習目的是得到映射關系f：X →{-1，1}Q，從而對新樣本進行標記的預測。

1.2 條件互信息

定義1設集合A={a1，a2，…，am}，令p(ai)表示元素ai的先驗概率，則集合A的信息熵為：

信息熵可以度量集合不確定性的程度，信息熵越大表示集合的不穩定性越大。對于多標記特征選擇算法，常通過信息熵來選擇特征空間中與標記空間互信息較大的特征。

定義2設集合A={a1，a2，…，am}，B={b1，b2，…，bn}，則在給定集合A的條件下集合B的條件熵為：

條件熵可以度量在集合A 出現的條件下集合B 的不確定程度的大小。

定義3設集合A={a1，a2，…，am}，集合B={b1，b2，…，bn}，則集合A與B的聯合熵為：

信息熵、條件熵及聯合熵的關系為：

定義4給定集合A 和集合B，定義集合A 和B 之間的互信息為：

互信息被廣泛用于度量隨機變量間相關性的大小，即I(A；B)表示集合A 和集合B 間的相關性大小。I(A；B)越大，表示兩者間的相關性越大。另有I(A；B)=I(B；A)，且滿足：

當I(A；B)=0 時，集合A 和集合B 無相關性，集合A 和集合B之間未提供任何信息。

定 義5設 集 合A={a1，a2，…，am}，B={b1，b2，…，bn}，C={c1，c2，…，ct}，則在集合C 條件下集合A 和B 間的條件互信息［17］為：

聯合互信息可由式(6)和式(7)得出：

聯合互信息是考慮A、C 整體同B 之間的關系，由上式可知條件互信息和互信息之和為聯合互信息，根據式（5）得出聯合互信息為：

聯合互信息I(A，C；B)越大，則表示A、C 整體同B 間的相關性越強。另外關于條件互信息還可變形表示如下：

2 MFSEF

在通過互信息考慮特征與標記之間的相關性來進行多標記特征選擇中，先給定f表示描述樣本的特征，l表示樣本的類別標記，則I（f；l）雖然僅可以在單標記中描述在樣本中特征和類別標記之間的相關性程度，而在多標記中，一個樣本是由多個特征向量表示且隸屬于多個類別標記，故給出以下定義。

定 義6給 定 特 征f 和 標 記 空 間L={l1，l2，…，ln}，為特征f 和標記li的互信息，那么特征f和標記空間集L的互信息可定義為：

定義7給定一個特征子集為S={f1，f2，…，fm}，特征fi與特征子集空間的互信息定義為：

特征與標記集合之間的互信息大小描述了兩個集合間的相關性程度，特征和標記集合的互信息越大，表明該特征越重要；反之，表明該特征重要性越弱，當特征和標記集合的互信息為零時，表明該特征和每個類別標記相互獨立，此時特征和標記集合的互信息也取得最小值。

給定訓練樣本U={x1，x2，…，xn}和其構成樣本的特征集合F={f1，f2，…，fd}，以及標記空間集合L={l1，l2，…，lt}。

由于專家特征在現實生活中是通過人的經驗主觀性選定，而本文實驗所采用數據集為常用的多標記數據集，若單純地人為指定專家特征，可能會影響實驗的可靠性和有效性，故可事先通過數據集畫出對應的特征值瀑布圖，然后根據瀑布圖聯合互信息理論挑選出幾個特征作為專家特征。圖1 和圖2為常用多標記數據集所畫的部分代表性瀑布圖。

圖1 第600和601個樣本中所有特征對應的特征值構成的瀑布圖Fig.1 Waterfall plot of eigenvalues corresponding to all features in the 600th and 601th samples

其中圖1 展示了在第600 個樣本到第601 個樣本中，每個特征所對應的特征值大小的對比，由圖可看出：兩個樣本對應的前100個特征的特征值基本較小且小于0.5，兩樣本特征值基本相同，表明該段特征對標記的影響甚微；而在第200 到300 之間的特征所對應的特征值數值有大有小，分布極其不均衡，波動較大，說明該段特征對樣本類別的劃分起到決定性作用，即稱隸屬特征；在第100 和200 之間的特征所對應的特征值基本數值較大，且分布均衡，無較大波動，表明該段特征對標記的影響至關重要，即稱為專家特征。

在圖2 中展示了在所有樣本中，每個特征所對應的特征值大小的對比。針對100～200 的專家特征，明顯看出所有樣本的特征值基本較大接近1，這表明這部分特征對于標記的劃分不可或缺，但這部分特征值基本相同，表明全部樣本基本上均具有該特征，所以如果事先把這些特征挑選部分出來，作為條件與剩余特征相聯合，然后再針對剩余特征進行后續特征選擇操作，無疑可以避免重復計算，提高特征選擇速度，而且更符合現實生活中面對分類問題時，常優先選出專家特征的操作習慣，因此更具有實際應用價值。

圖2 全部樣本所有特征對應的特征值構成的整體瀑布圖Fig.2 Overall waterfall plot composed of eigenvalues corresponding to all features of all samples

先通過瀑布圖觀察出專家特征的大致分布，再通過互信息考慮特征空間和標記空間的相關性大小，由互信息大小降序挑選靠前的特征，最后綜合考慮兩要素選出若干個特征作為專家特征。本文實驗取前四個特征作專家特征，記作E={e1，e2，e3，e4}。

傳統的基于互信息的多標記特征選擇算法僅考慮特征空間F 與標記空間L 的相關性：F →L，本文以專家特征E 為條件，保持專家特征不變，將專家特征和每個原始特征作并集構建新的特征空間，再考慮其與標記空間的相關性：E ∪F →L。

圖3 專家特征聯合的圖解描述Fig.3 Graphical description of combining expert features

由定義6 可知特征和標記集合的互信息越大，表明該特征越重要；反之，表明該特征重要性越弱。故用互信息大小進行降序排列得到一組新的特征序列：

對于多標記特征選擇，由于每個標記隸屬于不同特征空間，因此對于特征和標記集合的相關性通過互信息大小進行計算時，相關性強的特征之間可能有比較大的冗余性，而相關性弱的特征也不一定對判別標記類別不起作用，也有可能某個相關性弱的特征往往對最后分類結果起決定性作用?？紤]到此情景，可以通過建立局部子空間模型來解決此問題［10］。文獻［18］中說明，當數據集的特征維度較小的時候，子空間個數可以劃分2、3、4，考慮到較多保留相關性強特征，同時兼顧對某些類別標記貢獻較大的但是特征與標記相關性較弱的特征，故每個特征子空間的采樣比例可以設置為由大到小，例如對于2 個子空間，采樣比例可為：｛0.6，0.4｝、｛0.7，0.3｝、｛0.9，0.2｝。又由文獻［10］中實驗證明3 個子空間的預測效果最好，故可以將已經通過專家特征進行互信息大小降序排列后的特征序列劃分為三個子空間，再通過｛0.6，0.3，0.1｝的采樣比例進行進一步的特征選擇。

局部子空間的詳細過程如下：

給定有d 維特征空間，三個子空間，故每個子空間特征維數為，由定義6 可計算出在子空間中每個特征和剩余特征的互信息大小：此時互信息越大，表明其特征的冗余性越高；反之，特征間互信息越小，冗余性越低。因此將通過定義6 新得到的三個子空間中的特征進行升序，三個子空間關于特征間的冗余性排列分別為：

再通過采樣比例分別在三個子空間中選擇冗余性比較小的特征，由于采樣比例為｛0.6，0.3，0.1｝，故三個子空間通過比例選擇出的特征個數分別為：

模擬現實世界中分類問題，引入專家特征作為條件，同原始特征作并集，通過信息論中的互信息理論背景，計算特征與標記空間的相關性大小，再結合局部子空間模型的劃分，最后實現特征選擇。這樣既考慮了多標記特征選擇在現實社會中的合理性和實用性，也避免了傳統特征選擇只是根據相關準則選擇較強的特征導致的特征間的冗余性，最后實驗結果也顯示了較好的分類性能。

算法1 MFSEF。

輸入 多標記數據集D，專家特征E；

輸出 特征子集Sub。

2） E={e1，e2，e3，e4}；

3） for each fi∈L

5） for each lj∈L

6） 通過定義6計算FMI(fi∪E；lj)

7） end

9） end

10）通過第8）步計算出來的特征空間和標記空間互信息大小，對特征進行一個降序，從而得到新特征序列S；

11）將特征集合S均分成3個子空間S1、S2和S3；

12）對三個子空間分別通過定義7 計算特征和特征的互信息大小，然后進行升序排列，再通過采樣比例｛0.6，0.3，0.1｝在三個子空間分別挑選出新的特征子集；

13）將四個專家特征和新得到的三個特征子集合并，按順序依次放入Sub。

3 實驗及其結果分析

3.1 實驗數據集

為驗證本文算法的有效性，選取了Entertainment、Recreation、Artificial、Reference、Health、Business、Computer共7個數據集，詳細信息見表1。

表1 多標記數據集Tab.1 Multi-label datasets

3.2 實驗環境及評價指標

本實驗代碼在Matlab 2016a 中運行；硬件環境為Intel Core i5-2525M 2.50 GHz CPU，8 GB 內 存；操 作 系 統 為Windows 10。實驗選取多標記常用的4種性能評價指標［19-20］，即平均精度（Average Precision，AP）、海明損失（Hamming Loss，HL）、排序損失（Ranking Loss，RL）和1-錯誤率（One Error，OE）來綜合評價多標記學習算法性能，且分別簡寫為：AP↑、HL↓、RL↓和OE↓，其中：↑代表指標數值越高越好，↓代表指標數值越低越好。設：多標記分類器h(?)，預測函數f(?，?)，排序函數rankf，多標記數據集D={(xi，Yi|1 ≤i ≤n)}。上述4種評價指標AP、HL、RL和OE形式化定義如下：

1）Average Precision：評估在特定標記y ∈Yi排列的正確標記的平均分數。

2）Hamming Loss：用于度量樣本在單個標記的真實標記和預測標記的錯誤匹配情況。

3）One Error：評估對象最高排位標記并未正確標記的次數情況。

4）Ranking Loss：用來考察樣本的不相關標記的排序低于相關標記的排序的情況。

3.3 算法選擇與相關參數設置

為驗證新提出的特征選擇算法性能，實驗將MFSEF 算法與4 個經典多標記特征選擇算法進行對比，分別是MDDMspc、MDDMproj、PMU及MFSLS。表2到表5中的第2列Original 表示在原始特征空間下僅通過基本的經典多標記分類器ML-kNN 的分類性能；MDDM 是基于最大相關性的多標記維度約簡算法，而MDDM 又可劃分為MDDMspc 和MDDMproj，PMU是通過多元互信息最大化已選特征與標記集合的相關性，提出基于多變量互信息的多標記特征選擇算法。其中MDDMspc 和MDDMproj 算法需先進行原始數據歸一化，再進行特征選擇，MFSLS 和PMU 是針對離散型數據進行處理，鑒于此，為了實驗的嚴謹和合理性，以MFSLS和PMU 離散化方法為基準，對本文實驗數據先兩折離散化。由文獻［18］可知，當選擇多標記數據集的特征維度不高時，將子空間劃分為3 個，特征采樣比例設置為｛0.6，0.3，0.1｝，專家特征個數k_1 設為4。另本實驗最后分類器采用ML-kNN，故相關參數選擇默認值，近鄰個數k取10，平滑參數s取1。

3.4 實驗結果

表2到表5給出了本文算法和其他4種算法在7個多標記數據集上實驗結果，最好的結果加粗表示；同時，每種方法在所有數據集上的平均排序結果列在最后一行；數據右下角括號數字表示6種算法分別在評價指標下的排序序號。

表2 各算法在7個數據集上的平均精度測試結果Tab.2 AP（↑）results of each algorithm on 7 datasets

表3 各算法在7個數據集上的海明損失測試結果Tab.3 HL（↓）results of each algorithm on 7 datasets

表4 各算法在7個數據集上的排序損失測試結果Tab.4 RL（↓）results of each algorithm on 7 datasets

表5 各算法在7個數據集上的1-錯誤率測試結果Tab.5 OE（↓）results of each algorithm on 7 datasets

實驗結果顯示：MFSEF 在Health、Recreation、Artificial、Reference、Entertainment、Business、Computer 等7 個多標記數據集上實驗結果的平均排序都占優，其中，對于AP指標，平均數值越大，算法性能越優，對于其他三個評價指標，平均數值越小，算法性能越優。從表2到表5可發現：

①在AP 指標中，MFSEF 僅在Business 數據集中AP 不是最優，排名第二。對比4種算法和原始特征空間，MFSEF 在其他數據集中AP值最大，即分類性能達到最優。

②在HL指標中，MFSEF 在Business和Artificial數據集中HL 值排名第二，對比4 種算法和原始特征空間，MFSEF 在其他數據集中HL值最小，即分類性能達到最優。

③在RL指標中，MFSEF在Health和Business數據集中分別排第二和第三，在其他5個數據集對比4種算法和原始特征空間，MFSEF的RL值最小，即分類性能達到最優。

④在OE 指標中，MFSEF 在Entertainment 數據集上排第三，在Business數據集和MFSLS對比算法并列排第二，在其他5 個數據集對比4 種算法和原始特征空間，MFSEF 的OE 值最小，即分類性能達到最優。

上述實驗分析充分表明，通過本文算法特征選擇后的特征子集在后續分類性能上，對比其他4 種算法和原始特征空間在7 個多標記數據集中多數占優，驗證了本文算法的有效性和魯棒性。

圖4是對比其他4種算法，隨著選擇后的特征數目的逐漸變多，其分類性能的變化情況。針對每一種算法，都有28 種對比結果。介于篇幅所限，本文只選取了Artificial 數據集的曲線圖進行分析，分別展示了在AP、HL、RL和OE四種評價指標時，5 種算法在特征數逐漸變大時分類性能的變化情況。對比原始特征空間和PMU、MDDMspc、MDDMproj、MFSLS 這4種算法的分類性能，在Artificial 數據集上，MFSEF 基本上占優?；旧显谇?0 個特征范圍類，本文算法在四個評價指標上均明顯優于其他對比算法，并且往往能通過較少的特征數更快地達到更好的分類性能。另外，在其他未展示的數據集上，本文算法的分類性能曲線變化也多數占優，這充分地表明MFSEF的有效性和合理性。

圖4 Artificial數據集的各個評價指標的性能變化Fig.4 Changes in performance of various evaluation indicators on Artificial dataset

3.5 統計假設檢驗

在上述實驗分析中，本文算法達到了顯而易見的效果，下面將運用統計學中統計假設檢驗［21］進一步說明本文算法的有效性和合理性。

統計假設檢驗：在上述7 個數據集上采用顯著性水平為5%的Nemenyi 檢驗［22-23］來對比MFSEF 算法與其他對比算法。如果兩個算法在所有數據集上的平均排序的差值小于或者等于臨界差值（Critical Difference，CD），那么這兩個算法之間沒有顯著性差異，反之存在顯著性差異。如圖5 所示，在最上行為臨界值CD=2.850 0時，若兩個算法之間沒有顯著性差異則用實線連接。在圖5 中，隨著坐標軸上的數值增大其算法性能依次降低。

圖5 展示了各算法在AP、RL、HL、OE 四個指標上的CD圖，從中可以看出，本文算法在4 個指標上性能均處于首位。具體在平均精度指標上，如圖5（a）、（b）、（d）所示，在Average Precision、Ranking Loss 和One Error 三 個 指 標 上，MLSEF 與MDDMspc、PMU、MDDMproj 均有顯著差異，且優于這三種算法；如圖5（c）在Hamming Loss 指標上，本文算法與MDDMproj和MDDMspc有顯著差異，且優于這兩種算法。與其他算法相比，在統計上，本文算法有45%的概率與其他算法無顯著性差異。

圖5 算法綜合性能比較Fig.5 Performance comparison of algorithms.

通過以上針對圖5 的分析，可知本文算法綜合性能最為優秀，在統計上也優于其他對比算法?；谝陨系膶嶒灲Y果和統計分析再次充分表明本文算法的優越性。

4 結語

與通過相關準則挑選特征和標記相關性強的多標記特征選擇算法相比，本文不僅考慮了重要性較次要的特征可能對分類性能產生的影響，還考慮了可能決定整體預測方向的最關鍵特征。模擬現實生活中的實際情況，通過經驗優先挑選出部分專家特征與剩余特征相聯合，利用條件互信息和聯合互信息理論得出一個與標記集合相關性由強到弱的特征序列，再通過劃分子空間去除冗余性較大的特征，最后保留專家特征和挑選出的新的特征作為最后的特征子集。在已公開的多個基準多標記數據集中的實驗結果表明，該算法在實驗中較其他對比的多標記特征選擇算法有一定優勢和較好的穩定性，且更具有實際應用價值。

本文算法在專家特征的選取上還可以進一步探討，目前只是通過瀑布圖聯合互信息理論模擬選出幾個專家特征，所以最后結果可能由于個人選取專家特征的不同，實驗結果和預期效果存在一定的誤差，但是針對具體問題分析數據，合理選擇專家特征，還是可以有效減少誤差。