基于模擬退火的多標記數(shù)據(jù)特征選擇

張永波， 游錄金， 陳杰新

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

0 引 言

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

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

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

本文將結(jié)合多種多標記學(xué)習(xí)算法，嘗試模擬退火的優(yōu)化技術(shù)，提高封裝式特征選擇的效果，并與已有的多標記數(shù)據(jù)降維方法進行比較。

1 SAML算法

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

圖1 MEFS算法

圖2 SAML算法

2 數(shù)據(jù)與實驗設(shè)置

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

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

表1 Yahoo數(shù)據(jù)集的描述

3 SAML特征選擇結(jié)果

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

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

表2 Arts&Humanities上ML-KNN的結(jié)果

表3 Business&Economy上ML-KNN的結(jié)果

表4 Arts&Humanities上MLNB-Basic的結(jié)果

表5 Business&Economy上MLNB-Basic的結(jié)果

4 結(jié)束語

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

[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]葛雷,李國正,尤鳴宇.多標記學(xué)習(xí)的嵌入式特征選擇[J].南京大學(xué)學(xué)報,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.