張永波， 游錄金， 陳杰新

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

0 引 言

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

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

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

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

1 SAML算法

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

圖1 MEFS算法

圖2 SAML算法

2 數(shù)據(jù)與實(shí)驗(yàn)設(shè)置

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

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

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

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

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

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

本文將模擬退火用于多標(biāo)記數(shù)據(jù)的特征選擇中，用卷積式模型的特征選擇技術(shù)，這樣可以克服有監(jiān)督的多標(biāo)記特征選擇中的很多問(wèn)題，比如復(fù)雜的多標(biāo)記交錯(cuò)帶來(lái)的問(wèn)題。在Yahoo網(wǎng)頁(yè)上的實(shí)驗(yàn)證明，基于模擬退火的卷積式特征選擇方法能夠有效提高多標(biāo)記學(xué)習(xí)的建模精度。進(jìn)一步的工作包括如何進(jìn)行高效的特征選擇，如何提高多標(biāo)記特征選擇的速度、如何通過(guò)更高級(jí)的技術(shù)來(lái)處理多標(biāo)記的問(wèn)題。今后將在更多的多標(biāo)記學(xué)習(xí)技術(shù)[17-18]和數(shù)據(jù)集上進(jìn)行研究，提高算法的適應(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]葛雷,李國(guó)正,尤鳴宇.多標(biāo)記學(xué)習(xí)的嵌入式特征選擇[J].南京大學(xué)學(xué)報(bào),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.