基于模擬退火的多標記數據特征選擇

張永波， 游錄金， 陳杰新

(1.浙江旅游職業學院圖書信息中心，浙江杭州311231；2.上海思備計算機有限公司，上海200030；3.寧波城市職業技術學院信息中心，浙江寧波315100)

0 引 言

若一個樣本和多個類標相關聯，則稱這樣的數據為多標記數據。在當前的數據分析領域，多標記數據分析任務有很多[1-8]。比如，在網頁分類中，不同的網頁屬于不同的主題，而且有多個類別，一個具有海灘和高山的圖片，可以分類為大海、高山、風景等不同的語義類?，F在常見的多標記學習算法中，一個個樣例與多個類標關聯在一起，多標記學習技術要為未知測試樣例預測其類標集合，一般情況下，類標集合大小并不知道的。多標記學習所使用的數據通常都是高維數據，由于多標記學習技術的復雜性，其降維和特征選擇方法的研究仍然很少。目前多標記學習技術大體可以分為兩類[1-2]：轉化問題方法，改寫算法方法。轉化問題方法獨立于算法，把多標記學習任務轉化為一個或多個但標記分類任務，如單標記學習打分、組合類標、繼承學習方法等；改寫算法方法通過擴展特定的學習算法(如Boosting，支持向量機，決策樹等)來直接處理多標記數據。

對于特征維數高影響學習器效果方面，近年發表的一個特征抽取方法是多標記最大依賴維數約簡(MDDM)算法[9-10]，這個方法采用希爾伯特-斯密特準則(Hilbert-Schmidt independence criterion，HSIC)作為依賴性的評測準則。這個算法的最大特色在于通過最大化數據集特征集合與類標的依賴性，這樣可以監督方式得到低維特征空間，已有的實驗結果顯示MDDM性能略優于局部投影追蹤(LPP)，主成份分析(PCA)，明顯優于多標記線性語義索引(MLSI)。多標記線性降維方法[11]將最小平方損以及其他損失函數如hinge loss和squared hinge loss用于多標記學習問題中，也取得了較好的效果。MDDM和多標記線性降維算法的一個問題就是無法得到低維的原始特征，不利于科學問題的理解。

特征選擇旨在去除不相關特征和冗余特征，力求以最少的特征來表達原始信息，并達到最優的預測或分類精度。特征選擇能夠明顯提高分類模型的可理解性并且建立一個能更好的預測未知樣本的分類模型，具有重要的現實意義，當前主要的特征選擇方法大致可分為3類：過濾式特征選擇方法(filter)[12]，封裝式特征選擇方法(wrapper)，嵌入式特征選擇方法(embedded)[13]。封裝式方法依賴于分類器，在封裝式方法中，學習算法被“包含”在特征選擇中。封裝式方法用學習器來評估用潛在的特征子集預測類標時精確度。雖然封裝式方法比較費時，但是選擇結果是建立在學習算法基礎上，所得結果對特定的學習技術是最優的，所以在科學數據分析中應用廣泛。在多標記特征選擇方面，文獻[12]使用了過濾式特征選擇技術，文獻[13]去年提出的嵌入式特征選擇方法(MEFS)，并結合到半監督多標記學習的特征選擇中[14]。在封裝式特征選擇中，遺傳算法被引入到特征選擇中取得了較好效果[15]。

本文將結合多種多標記學習算法，嘗試模擬退火的優化技術，提高封裝式特征選擇的效果，并與已有的多標記數據降維方法進行比較。

1 SAML算法

葛雷等采用嵌入式特征選擇進行多標記數據選擇，提出MEFS，本文算法結構與之類似，所以先給出MEFS算法如圖1所示[13]。張敏靈等采用遺傳算法對多標記數據進行特征選擇分析[15]，但是該算法僅僅結合MLNB-Basic算法，并且遺傳算法在優化方面有一定局限性，如果嘗試不同優化技術，進行特征子集的搜索，或許能進一步提高特征選擇效果。本文提出嘗試引入變異算子的模擬退火算法，得到最優特征子集，提出了基于模擬退火的多標記特征選擇算法，SAML(simulated annealing based feature selection for multi-label data)。如圖2所示，算法在特征選擇的過程中，以Average Precision結果作為特征子集的適應度函數。也即在訓練數據上進行特征選擇的過程中，在驗證集上通過ML-KNN[16]、MLNB-BASIC[15]等多標記學習技術建模所得測試結果的Average_Precision準則作為評估特征子集的適應度函數。Average_Precision準則詳見文獻[1]。

圖1 MEFS算法

圖2 SAML算法

2 數據與實驗設置

SAML將與MEFS[5]和MLNB[7]等兩個方法在YAHOO頁面分類數據集上進行比較。ML-KNN[8]和MLNB-Basic[7]作為多標記分類器，k設置為10[8]。為了比較SAML進行特征選擇的效果，用ORI表示原始空間下訓練的結果。

Yahoo(http://www.keel.ntt.co.jp/as/members/ueda/yahoo.tar.gz)網頁數據集是從“yahoo.com”網站收集的網頁面，有11個子數據集。每個數據集包含2000個訓練數據文本和3000個測試數據文本。本文使用2個子數據集，它們詳細情況如表1所示。這些數據集在先后用到很多的工作中，這些工作都用了這個數據集進行算法評測，所以這些數據都很權威。

表1 Yahoo數據集的描述

3 SAML特征選擇結果

選擇AveragePrecision作為SAML特征選擇的評價指標。選擇Yahoo數據集中Arts&Humanities和Business&Economy作為樣例，對SAML與MEFS,MLNB的特征選擇效果進行分析比較。Arts&Humanities和Business&Economy數據集上的結果分別列在表2-表5中，并用粗體表示最優結果。

從實驗結果中，我們可以看出SAML和MLNB稍優于MEFS，明顯優于ORI。同時，經過SAML進行特征選擇后，Hammingloss，Coverage以及AveragePrecision等指標都明顯提高。不同學習器效果略有不同，在ML-kNN上SAML所得結果明顯比MLNB有好的結果，而在MLNB-Basic作為分類器時，SAML跟MLNB則效果相當。綜合兩種分類器上的結果，得出SAML略好或相當于MLNB的結論。

表2 Arts&Humanities上ML-KNN的結果

表3 Business&Economy上ML-KNN的結果

表4 Arts&Humanities上MLNB-Basic的結果

表5 Business&Economy上MLNB-Basic的結果

4 結束語

本文將模擬退火用于多標記數據的特征選擇中，用卷積式模型的特征選擇技術，這樣可以克服有監督的多標記特征選擇中的很多問題，比如復雜的多標記交錯帶來的問題。在Yahoo網頁上的實驗證明，基于模擬退火的卷積式特征選擇方法能夠有效提高多標記學習的建模精度。進一步的工作包括如何進行高效的特征選擇，如何提高多標記特征選擇的速度、如何通過更高級的技術來處理多標記的問題。今后將在更多的多標記學習技術[17-18]和數據集上進行研究，提高算法的適應性和效率。

[1]Tsousmakas G,Zhang M L,Zhou Z H.Learning from multi-label data[C].Bled,Slovenia:ECML/PKDD'09,2009.

[2]Zhang M-L,Zhou Z-H.Multi-label learning by instance differentiation[C].Vancouver,Canada:Proceedings of the 22nd AAAI Conference on Artificial Intelligence,2007:669-674.

[3]Zhou Z-H,Zhang M-L.Multi-instance multi-label learning with application to scene classification[C].Sch?lkopf B,Platt J C,Hofmann T,et al.Vancouver,Canada:Advances in Neural Information Processing Systems.Cambridge,MA:MIT Press,2007:1609-1616.

[4]Zhang M-L,Zhou Z-H.A k-nearest neighbor based algorithm for multi-label classification[C].Beijing,China:Proceedings of the 1st IEEE International Conference on Granular Computing,2005:718-721.

[5]Zhang M-L,Zhou Z-H.Multilabel neural networks with applications to functional genomics and text categorization[J].IEEE Transactions on Knowledge and Data Engineering,2006,18(10):1338-1351.

[6]Jin R,Wang S,Zhou Z-H.Learning a distance metric from multiinstance multi-label data[C].Miami,FL:Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition,2009:896-902.

[7]Li Y-X,Ji S,Kumar S,et al.Drosophila gene expression pattern annotation through multi-instance multi-label learningb[J].ACM/IEEE Transactions on Computational Biology and Bioinformatics,2011,4(2):22-35.

[8]Li Y-X,Ji S,Ye J,et al.Drosophila gene expression pattern annota-tion through multi-instance multi-label learning[C].Pasadena,CA:Proceedings of the 21st International Joint Conference on Artificial Intelligence,2009:1445-1450.

[9]Zhang Y,Zhou Z-H.Multi-label dimensionality reduction via dependency maximization[C].Chicago,IL:Proceedings of the 23rd AAAI Conference on Artificial Intelligence,2008:1503-1505.

[10]Zhang Y,Zhou Z H.Multi-label dimensionality reduction via dependence maximization[J].ACM Transactions on Knowledge Discovery from Data,2010,4(3):14-24.

[11]Ji S W,Ye J P.Linear dimensionality reduction for Multi-Label classification[C].Pasadena,CA:Proceedings of the 21st International Conference on Artificial Intelligence,2009:1077-1082.

[12]LiuY-H,Li G-Z,Zhang H-Y,etal.Feature selectionforgenefunction prediction by using multi-label lazy learning[J].International Journal of Functional Informatics and Personalised Medicine,Inderscience,2008,1(3):223-233.

[13]葛雷,李國正,尤鳴宇.多標記學習的嵌入式特征選擇[J].南京大學學報,2009,45(5):671-676.

[14]Li G-Z,You M,Ge L,et al.Feature selection for semi-supervised multi-label learning with application to gene function analysis[C].Niagara Falls,NY:Proceedings of The First ACM International Conference On Bioinformatics and Computational Biology,2010:354-357.

[15]Zhang M L,Pena J M,Robles V,et al.Feature selection for multilabel naive Bayes classification[J].Information Sciences,2009,179(19):3218-3229.

[16]Zhang ML,ZhouZ H.ML-KNN:A lazylearning approachto multi-label learning[J].Pattern Recognition,2007,40(7):2038-2048.

[17]Zhang M L,Zhou Z-H.M3MIML:A maximum margin method for multi-instance multi-label learning[C].Pisa,Italy:Proceedings of the 8th IEEE International Conference on Data Mining,2008:688-697.

[18]Sun Y-Y,Zhang Y,Zhou Z-H.Multi-label learning with weak label[C].Atlanta,GA:Proceedings of the 24th AAAI Conference on Artificial Intelligence,2010:593-598.