一種多標記數據的過濾式特征選擇框架

郭雨萌，李國正

(同濟大學電子與信息工程學院控制系，上海201804)

多標記數據[1]中每個樣本可以同時帶有多個類標，并且廣泛地出現在不同的應用領域，比如文本分類、媒體標注、信息檢索、生物信息學等。對于這種數據的分析需要利用多標記學習技術[2-3]。由于大量不同的多標記學習技術被提出，所以該技術仍是研究熱點，目前可以分為問題轉化和算法適應2種類型。在問題轉化類型中，BR(binary relevance)，CC(classifier chain)和RAkEL(random k-labelsets)分類器是典型代表。而在算法適應類型中，MLkNN(multi-label k nearest neighbor)、AdaBoost.MH(adaboost multi-class hamming trees)和RankSVM(rank support vector machine)屬于將一些先進的單標記分類器轉化為多標記分類器的一類。LEAD(multi-label learning by exploiting label dependency)和LIFT(multi-label learning with label-specific features)分類器則更進一步，考慮到特征子集和利用類標的層級結構去進行學習分類的一類。多標記學習技術發(fā)展的動力來自于實際應用問題，很具有研究價值。

雖然多標記學習技術還需要許多研究工作，但是很少的科研工作者將目光轉向數據集中一些不相關或冗余的特征。減少這些特征會在一定程度上提高多標記學習器的分類能力，因此對數據集進行特征選擇預處理是很有必要的。特征選擇[4-5]的目的是在高維數據中降低子集維度，主要有過濾式、包裝式和嵌入式等3種不同形式。過濾式與目標學習器無關，具有計算簡單，效率高的優(yōu)勢[6-7]。本文提出一種過濾式多標記特征選擇的框架，并以卡方檢驗[8]為特征評價的準則。

1 過濾式多標記特征選擇框架

過濾式方法的基本思想是使用一種獨立于分類器的評價指標來衡量某個特征的好壞，即選擇該特征優(yōu)先級。過濾式方法在計算效率上往往優(yōu)于其他2種特征選擇方法。

卡方檢驗可以用來度量特征t和類標c之間的相關程度。假設t和c之間符合具有一階自由度的CHI分布。t和c的CHI值由式(1)計算:

式中:χ2值表示CHI值，N表示數據集中樣本的總個數;A表示包含t且屬于分類c的樣本數;B為包含t但是不屬于c類的樣本數;C表示屬于c類但是不包含t的樣本數;D表示既不屬于c也不包含t的樣本數。可以看出N固定不變，A+C為屬于c類的樣本數，B+D為不屬于c類的樣本數，所以式(1)可以簡化為

當特征和類標相互獨立時，χ2(t，c)=0 。χ2(t，c)的值越大，特征t和類標c越相關。

本文提出的過濾式多標記特征選擇框架的基本思想是:首先單獨計算每個特征t與各個類標c的CHI值，然后再根據得分統(tǒng)計方式決定每個特征的最終得分，最后將特征按照最終得分進行降序排列，并進行前向搜索得到特征子集。

下面為通過計算每個特征t與各個類標c的CHI值，并根據得分統(tǒng)計方式得到最終得分的公式:

式中m為類標個數。式(2)表示特征與各類標的平均CHI值作為該特征的最終得分;式(3)表示選取特征與各類標CHI值中的最大值作為該特征的最終得分統(tǒng)計;式(4)表示選取特征與各類標CHI值中的最小值作為該特征的最終得分統(tǒng)計。

實驗數據來自于MULAN網站上公開的多標記數據集，數據集相關信息如表1所示。

表1 實驗數據集相關信息Table 1 The characteristics of datasets

實驗采用5種常用的多標記學習評價指標[9]，對多標記數據特征選擇之后的分類性能進行評價:排名損失、漢明損失、差一錯誤、覆蓋范圍、平均查準率。以上5種評價指標中，前4種評價指標的值越小，最后1種評價指標的值越大，表明性能越好。

實驗采用10輪10倍交叉驗證方法，即將實驗數據隨機平均分成10份，每次將1份作為驗證集，其余9份整體作為訓練集，不重復進行10次實驗，統(tǒng)計其平均結果，作為實驗最終結果。

通過將預處理后的多標記數據集利用卡方檢驗準則，可以分別得到每個特征t對應的各個類標c的CHI值。然后，按照不同的得分統(tǒng)計方式得到每個特征的最終得分，最后根據每個特征的最終得分，將全體特征做降序排列，使用前向搜索依次選取前n個特征(n=1，2，…)作為特征子集。

max指的是選取利用卡方檢驗準則得到的每個特征對應各個類標所有CHI值的最大值，作為該特征的最終得分，進行特征排序。

avg指的是選取利用卡方檢驗準則得到的每個特征對應各個類標所有CHI值的平均值，作為該特征的最終得分，進行特征排序。

min指的是選取利用卡方檢驗準則得到的每個特征對應各個類標所有CHI值的最小值，作為該特征的最終得分，進行特征排序。

在將處理好的特征進行排序后，多標記分類器將利用搜索到的特征子集去完成分類任務。為了更加客觀地測試特征子集的分類效果，實驗選取了3個多標記分類器，分別是 BR[10]、CC[11]和 MLkNN[12]。

3 實驗結果及分析

按照上節(jié)的實驗設置，在4個公開數據集上先進行特征選擇，再分類，實驗結果做如下分析。

3.1 Emotions數據集上的實驗結果分析

如圖1(其中橫軸坐標表示特征子集所含有的特征個數，縱軸坐標表示特征子集在相應指標下的實驗結果數值，之后分析相同)和表2所示，在BR分類器下，隨著特征個數增多到最后階段3種得分統(tǒng)計方式搜索到的特征子集性能較差。雖然開始在min下搜索到的特征子集相比于其他2種方式，在5種評價指標下性能較差，但是隨著特征個數的增加，min下的實驗結果漸漸超過avg和max，最終達到全局最優(yōu)，得到最優(yōu)特征子集。而且 avg和max下搜索得到的特征子集除了在差一錯誤評價指標下的實驗結果存在較明顯差異，在其余4種評價指標下預測結果差異較小。同時，可以看出在CC分類器下，整體趨勢與BR分類器下相似，但是后期波動較小。在MLkNN分類器下，整體趨勢與BR分類器下相似，但是后期波動較大。

圖1 Emotions數據集部分實驗結果Fig.1 Partial results of the experiment on the emotions dataset

表2 Emotions數據集實驗的最優(yōu)結果比較Table 2 Comparison of optimal results of the experiment on the emotions dataset

3.2 Medical數據集上的實驗結果分析

如圖2和表3所示，在BR分類器下，avg和max 2種得分統(tǒng)計方式搜索到的特征子集在5種評價指標下預測結果差異較小，幾乎重疊在一起。但是從全局最優(yōu)結果看，在排序損失和覆蓋范圍指標下，avg和max都能搜到最優(yōu)特征子集，而在漢明損失和差一錯誤指標下，avg結果最好，在平均查準率指標下，max結果最好。在min下搜索到的特征子集在5種評價指標下結果最差，而且收斂速度明顯慢于avg和max，特征選擇對于分類性能提升效果較差。同時，可以看出在CC分類器下，整體趨勢與BR分類器下相似。但是從全局最優(yōu)結果看，在5種指標下，max下搜索到最優(yōu)特征子集，結果最好。在MLkNN分類器下，整體趨勢與BR分類器下相似。

圖2 Medical數據集部分實驗結果Fig.2 Partial results of the experiment on the medical dataset

表3 Medical數據集實驗的最優(yōu)結果比較Table 3 Comparison of optimal results of the experiment on the medical dataset

3.3 Scene數據集上的實驗結果分析

如圖3和表4所示，在BR分類器下，3種得分統(tǒng)計方式搜索到的特征子集在5種評價指標下預測結果差異較小，幾乎重疊在一起。但是從全局最優(yōu)結果看，在排序損失指標下，3種得分統(tǒng)計方式達到相同結果，在漢明損失，覆蓋范圍和差一錯誤指標下，min結果最好，在平均查準率指標下，max結果最好。同時，可以看出在CC分類器下，整體趨勢與BR分類器下相似。但是從全局最優(yōu)結果看，在5種指標下，avg下搜索到最優(yōu)特征子集，結果最好。在MLkNN分類器下，整體趨勢與BR分類器相似。但是從全局最優(yōu)結果看，在5種指標下，min下搜索到最優(yōu)特征子集結果最好。

圖3 Medical數據集部分實驗結果Fig.3 Partial results of the experiment on the medical dataset

表4 Scene數據集實驗的最優(yōu)結果比較Table 4 Comparison of optimal results of the experiment on the scene dataset

續(xù)表1

3.4 Yeast數據集上的實驗結果分析

Yeast數據集部分實驗結果如圖4所示。

圖4 Yeast數據集部分實驗結果Fig.4 Partial results of the experiment on the yeast dataset

在BR分類器下，avg和max兩種得分統(tǒng)計方式搜索到的特征子集在排序損失、漢明損失和平均查準率指標下預測結果差異較小，幾乎重疊在一起，但是在差一錯誤和覆蓋范圍指標下，都出現不同程度的小幅震蕩。在min下搜索到的特征子集在5種評價指標下結果最差，而且收斂速度明顯慢于avg和max，特征選擇對于分類性能提升效果較差。從全局實驗結果看，avg下搜索到的特征子集，達到最優(yōu)結果。同時，可以看出在CC分類器下，3種取值方式搜索到的特征子集，在5種評價指標下的結果，都呈現出震蕩的形式，尤其是在差一錯誤指標下，震蕩幅度最大。雖然在震蕩中，但是隨著特征個數的增加，結果逐漸改善，說明特征選擇起到了很好的提高分類性能的作用。從全局實驗結果看，在排序損失和平均查準率指標下，avg下搜索到的特征子集表現最好，而且其余3種評價指標下，max下搜索到的特征子集表現最好。在MLkNN分類器下，整體趨勢與在BR分類器下相似。從全局實驗結果看，除了在排序損失和差一錯誤指標下，avg與max下搜索到的特征子集，達到相同最優(yōu)結果，其余3種評價指標下，max的結果最好。Scene數據集實驗的最優(yōu)結果比較如表5所示。

表5 Scene數據集實驗的最優(yōu)結果比較Table 5 Comparison of optimal results of the experiment on the scene dataset

3.5 實驗結果

從以上所有實驗結果可以看出，針對不同類型的多標記數據集，都有其特定的得分統(tǒng)計方式能很快地搜索到較優(yōu)的特征子集，然后趨于穩(wěn)定，說明特征選擇起到了很好的提高分類性能的作用。為了便于使展示圖片美觀易懂，畫圖時特征子集所含特征個數采用間隔選取再繪制(本身實驗數據是全的)，所有的同類型圖片都采用這個方法。

4 結束語

本文提出過濾式的多標記特征選擇框架，并使用卡方檢驗作為特征評價準則，在多個多標記數據集和分類評價準則上顯示特征選擇有助于提高多標記學習器的學習效果。本文通過對卡方檢驗得分的統(tǒng)計計算出每個特征的最終排序情況，選取了最大、平均、最小3種統(tǒng)計方式分別進行了實驗比較。實驗結果表明，利用本文框架采取不同的得分統(tǒng)計方式，對于不同類型的多標記數據集有不同效果。過濾式多標記特征選擇框架還有一些問題有待進一步解決，比如如何在得分統(tǒng)計中加入衡量類標間的關系，如何采取更有效得分統(tǒng)計方式將提升特征子集在分類器下的分類效果等。

[1]TSOUMAKAS G，KATAKIS I，VLAHAVAS I.Mining Multi-label Data[R].Data Minging and Knowledge Discovery Handbook，2010:667-685.

[2]TSOUMAKAS G，KATAKIS I.Multi-label classification:an overview[J].International Journal of Data Wareh-ousing and Mining，2007，40(3):1-13.

[3]ZHANG M L，ZHANG K.Multi-label learning by exploiting label dependency[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington，DC，USA，2010:999-1008.

[4]YANG Y，PEDERSEN J O.A comparative study on feature selection in text categorization[C]//Machine Learning International Workshop then Conference.Philadelphia，USA，1997:412-420.

[5]SWATI S，GHATOL A，ASHOK C.Feature selection for medical diagnosis:Evaluation for cardiovascular diseases[J].Expert Systems with Applications，2013，40(10):4146-4153.

[6]NEWTON S，EVERTON A C，MARIA C M，et al.A comparison of multi-label feature selection methods using the problem transformation approach[J].Electronic Notes in Theoretical Computer Science，2013，292:135-151.

[7]計智偉，胡珉，尹建新.特征選擇算法綜述[J].電子設計工程，2011，19(9):46-51.JI Zhiwei，HU Ming，YIN Jianxin.A survey of feature selection algorithm[J].Electronic Design Engineering，2011，19(9):46-51.

[8]邱云飛，王威，劉大有，等.基于方差CHI的特征選擇方法[J].計算機應用研究，2012，29(4):1301-1303.QIU Yunfei，WANG Wei，LIU Dayou，et al.CHI feature selection method based on variance[J].Application Research of Computers，2012，29(4):1301-1303.

[9]ZHANG M L，ZHOU Z H.A review on multi-label learning algorithms[J].IEEE Transactions on Knowledge and Data Engineering，2013，39(10):1-43.

[10]MATTHEW R B，LUO J B，SHEN X P，et al.Learning multi-label scene classification[J].Pattern Recognition，2004，37(9):1757-1771.

[11]READ J，PFAHRINGER B，HOLMES G，et al.Classifier chains for multi-label classification[J].Machine Learning，2011，85(3):333-359.

[12]ZHANG M L，ZHOU Z H.ML-kNN:a lazy learning approach to multi-label learning[J].Pattern Recognition，2007，40(7):2038-2048.