基于Lasso和模糊互信息多標記特征選擇算法

孟金彪　錢萌　李存志　翟靜波

摘要：本文提出一種基于Lasso和模糊互信息多標記特征選擇算法。本文所提的算法在6個多標記數據集上進行了測試，實驗結果和統計假設檢驗說明本文算法是有效的。

[關鍵詞]多標記學習 模糊互信息 Lasso算法 特征選擇

多標記學習廣泛應用于機器學習、人工智能等方面。在多標記學習中，數據集往往具有高維性和高冗余性等特點，從而導致維數災難。特征選擇作為一種有效的降維方式，其通過刪除冗余或不相關特征來提高分類模型精度的目的。

目前，眾多學者已提出多種效果較優的特征選擇算法。例如Lee等提出了基于多變量互信息的多標記特征選擇算法（PMU）。Lin等提出了基于鄰域互信息的多標記特征選擇算法。

然而，上述特征選擇算法在選擇特征子集時都有計算開銷過大的問題。為解決該問題，近年來，一種基于線性回歸模型的降維方法一Lasso算法，其因高效的性能在特征選擇領域得到了廣泛的關注。Lasso通過對變量進行選擇和壓縮來降低原始特征空間的維度，該算法的基本思想是在構建線性回歸模型時，其回歸系數絕對值之和小于一個閾值的約束條件下，使絕對值較小的回歸系數自動壓縮為0，從而得到可解釋的模型。另外，在常見的特征選擇算法中，主要利用傳統熵方法來判斷特征與標記空間之間的相關性。但傳統信息熵不具有補的性質，因此，用模糊信息替代傳統信息熵。在選擇特征子集的過程中，為了提高分類性能的同時并縮減算法計算開銷過大的問題，本文首先利用Lasso算法對特征空間降維，求解出每個特征在每個標記下的回歸系數，系數為0所對應的特征都視其為冗余特征并將其刪除，得出新的特征空間。然后結合模糊信息熵對新的特征空間中所有特征分別計算其與標記空間的模糊互信息，根據模糊互信息的大小對特征依次進行排序，得出最終特征子集。通過實驗結果表明本文算法是有效的。

1 模糊信息熵

定義1假設樣本空間的描述記為論域U，論域∪可根據某種特征屬性進行劃分，假設根據特征屬性F={2....對論域U進行劃分記U1F=X={xX2....}，則模糊信息熵定義如下：

其中E（X）為模糊熵，公式（2）示在論域U中等價類X;的概率，

表示在論域U中的X;的互補概率。定義2類似的，模糊互信息定義為：

2 結合Lasso與模糊互信息的特征選擇算法

2.1 基于Lasso算法的特征降維

Lasso算法是一種同時進行特征選擇和正則化的線性回歸分析方法，其基本思想是在回歸系數絕對值之和小于一個閾值的條件下，使殘差平方和最小化，將相關性較低的變量的系數壓縮為0，然后刪除這些特征變量，從而達到降低特征空間維度的目的。另外，Lasso算法還能有效的防止過擬合問題。針對多標記學習，Lasso構造的函數如下：

式（3）中，r是控制稀疏矩陣W=[W，....]*R的參數，Lasso回歸是一個凸優化問題，但由于其是通過1范式構造的懲罰函數，因此稀疏矩陣不能直接求解。本論文中，將用交替方向乘子法（ADMM）來將式（3）轉換為2個子問題求解，式（3）可以利用拉格朗日形式L（W，H，S）重新構造為：

其中，F是拉格朗日乘子矩陣，ADMM通過迭代以下公式來優化式（4）：

通過將式（4）轉化為求解式（5）和式（6）2個子問題，式（4）可以簡單的通過嶺回歸來解決，式（6）可通過軟閾值算子求得，收斂后，可通過H求得W。求得稀疏矩陣W后，找出W（i，j）=o其中ie...[.2..}，.在原特征空間中刪除第i個特征達到降低特征空間維度的目的。

2.2 基于Lasso和模糊互信息多標記特征選擇算法

在本文所提出的結合Lasso與模糊互信息的特征選擇算法中，利用Lasso算法快速有效的刪除冗余特征達到維度約簡的目的。為防止過擬合，Lasso算法通過采用正則化方法自動削弱不重要的特征變量，再結合模糊互信息這種度量方式來對維度約簡后的特征的重要度進行重新排序。首先，構造一個mXn的零矩陣，利用公式（3）計算出每個特征在每個標記下的回歸系數，通過回歸系數絕對值之和小于一個閾值的約束條件下，使絕對值較小的回歸系數自動壓縮為0，在矩陣V中找出系數為0所對應的特征視其為冗余特征并將其從原特征空間中刪除最終得到一個新的特征空間。然后，在新的特征空間中根據公式（2）計算所有特征與標記空間的模糊互信息，所得的值越大就表示其特征越重要。最后，按照模糊互信息的大小對特征重新排序得到最終的特征子集。

3 實驗數據及其結果分析

3.1 實驗數據及評價指標

本文采用了Artifcial、Computer、Education、Society、Science、Business這6個數據集來驗證本文算法的有效性。數據均來自于htp：//mulan.sourceforge.net/datasets.html.

本文采取海明損失，1-錯誤，排位損失，平均準確率這4個評價指標作為性能評價指標對實驗結果的有效性進行驗證。

3.2 實驗結果及分析

實驗代碼均在Matlab2012b中運行，對維度約簡后的特征空間以ML一kNN作為分類器進行訓練和測試，對比算法有PMU、MDDM、MFNMI。kNN參數值設定為默認值，即平滑系數s=1，k=10。Lasso中兩個閾值分別為γ=0.01，rho=1。表1中↑表示指標數值越大越好，↓表示指標數值越小越好。最佳實驗結果用黑體字表示。各個數據集使用Lasso算法后的特征大小分別為339，437，353，409，382，330，所有算法的特征子集大小都與Lasso算法所選的特征子集大小相等。

實驗結果分析：

（1）由表2可發現：在6個數據集上，本文提出的算法MF-LFMI在4個數據集上AveragePrecision值最大，即性能最優。

（2）表3實驗結果表明：有4個數據集的海明損失值取得最小值。Computer數據集在本文算法NMI-LMF上取得的HammingLoss值排在第2位，與最優的HammingLoss值僅相差0.0004，性能較優。其它評價指標結論類似，略。

4 結束語

本文引入Lasso算法，通過其選擇出與標記空間強相關的特征而降低特征維度以解決計算開銷過大的問題。另外，為彌補傳統信息熵不具有補的性質，用模糊互信息替代傳統信息熵評估候選特征的重要度。不足之處在于利用模糊互信息對降維后的特征進行重要度排序時并未考慮特征之間依賴性，這將是本文下一步的研究方向。

參考文獻

[1]Lee J，Kim D W. Feature selection for multi-label classification using multivariate mutual information [J]. Pattern RecognitionLetters （S01 67-8655）， 2013，34 （3）： 349-357.

[2]Lin Y，Hu Q，Liu J，et al. Multi- label feature selection based on neighborhood mutual information [J].Applied Soft Computing （S1568-4946），2016，38 （C）： 244-256.

[3]程玉勝，張佑生，胡學鋼?；谶吔缬虻闹R粗糙熵與粗集粗糙熵[J].系統仿真學報，2007，19（09）：2008-2011.

[4]Sun L，Kudo M，Kimura K. Multi-label classification with meta-label-specific features[C]// International Conference on Pattern Recognition.IEEE，2017：1612-1617.

[5]ZhangY，ZhouZH.Multi-LabelDimensionality Reduction via Dependence Maximization[C]//AAAI Conference on Artificial Intelligence，AAAI2008，Chicago，I1linois，Usa，July.DBLP，2008：1503-1505.

[6]Zhang ML，ZhouZH.ML-KNN：A lazy learning approach to multi-label learning[J].PatternRecognition（S0031-3203），2007，40（7）：2038-2048.