基于互信息的粒化特征加權(quán)多標(biāo)簽學(xué)習(xí)k近鄰算法

2017-05-13 03:50:52苗奪謙張志飛

計(jì)算機(jī)研究與發(fā)展 2017年5期

關(guān)鍵詞：分類特征

李峰苗奪謙張志飛張維

(同濟(jì)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系上海 201804)(嵌入式系統(tǒng)與服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室(同濟(jì)大學(xué)) 上海 201804)(tjleefeng@163.com)

基于互信息的?；卣骷訖?quán)多標(biāo)簽學(xué)習(xí)k近鄰算法

李峰苗奪謙張志飛張維

傳統(tǒng)基于k近鄰的多標(biāo)簽學(xué)習(xí)算法，在尋找近鄰度量樣本間的距離時(shí)，對所有特征給予同等的重要度.這些算法大多采用分解策略，對單個(gè)標(biāo)簽獨(dú)立預(yù)測，忽略了標(biāo)簽間的相關(guān)性.多標(biāo)簽學(xué)習(xí)算法的分類效果跟輸入的特征有很大的關(guān)系，不同的特征含有的標(biāo)簽分類信息不同，故不同特征的重要度也不同.互信息是常用的度量2個(gè)變量間關(guān)聯(lián)度的重要方法之一，能夠有效度量特征含有標(biāo)簽分類的知識量.因此，根據(jù)特征含有標(biāo)簽分類知識量的大小，賦予相應(yīng)的權(quán)重系數(shù)，提出一種基于互信息的?；卣骷訖?quán)多標(biāo)簽學(xué)習(xí)k近鄰算法(granular feature weightedk-nearest neighbors algorithm for multi-label learning, GFWML-kNN),該算法將標(biāo)簽空間粒化成多個(gè)標(biāo)簽粒，對每個(gè)標(biāo)簽粒計(jì)算特征的權(quán)重系數(shù),以解決上述問題和標(biāo)簽組合爆炸問題.在計(jì)算特征權(quán)重時(shí)，考慮到了標(biāo)簽間可能的組合，把標(biāo)簽間的相關(guān)性融合進(jìn)特征的權(quán)重系數(shù).實(shí)驗(yàn)表明：相較于若干經(jīng)典的多標(biāo)簽學(xué)習(xí)算法，所提算法GFWML-kNN整體上能取得較好的效果.

互信息；特征權(quán)重；?；?；多標(biāo)簽學(xué)習(xí)；k-近鄰

傳統(tǒng)機(jī)器學(xué)習(xí)以二類(binary-class)分類或者多類(multi-class)分類為主，每個(gè)樣本只有一個(gè)類別標(biāo)簽，稱作單標(biāo)簽學(xué)習(xí)(single-label learning).然而，現(xiàn)實(shí)世界中各領(lǐng)域都存在大量同時(shí)擁有多個(gè)標(biāo)簽的樣本[1-3].比如，一篇新聞報(bào)道可能同時(shí)跟多個(gè)話題有關(guān)[4]，如體育、娛樂、社會(huì)、經(jīng)濟(jì)；一張圖片可能同時(shí)包含多個(gè)語義信息[5]，如大海、沙灘、城市；一個(gè)基因可能同時(shí)具有多個(gè)功能[6]，如翻譯、轉(zhuǎn)錄；一個(gè)病人的病理圖像可能同時(shí)展現(xiàn)出了多個(gè)病理特性[7]，如角化過度、顆粒層消失.這些有多個(gè)標(biāo)簽的樣本稱為多標(biāo)簽數(shù)據(jù).多標(biāo)簽學(xué)習(xí)(multi-label learning)的任務(wù)就是通過學(xué)習(xí)標(biāo)簽已知的多標(biāo)簽數(shù)據(jù)來預(yù)測標(biāo)簽未知的樣本相關(guān)的多個(gè)標(biāo)簽[1-3].相較于單標(biāo)簽數(shù)據(jù)中樣本只有唯一確定的標(biāo)簽，多標(biāo)簽數(shù)據(jù)中的樣本可能同時(shí)擁有多個(gè)標(biāo)簽，從而導(dǎo)致了多標(biāo)簽數(shù)據(jù)的復(fù)雜多變.多標(biāo)簽數(shù)據(jù)的復(fù)雜性、多變性都增加了多標(biāo)簽學(xué)習(xí)算法預(yù)測的難度.

在面對復(fù)雜問題時(shí)，人類往往將復(fù)雜問題分解為多個(gè)簡單問題，再逐個(gè)解決.機(jī)器學(xué)習(xí)領(lǐng)域沿用了此方法，傳統(tǒng)機(jī)器學(xué)習(xí)中將多類分類問題拆分成多個(gè)二類分類問題.直觀上，多標(biāo)簽學(xué)習(xí)問題也可以被拆分成多個(gè)獨(dú)立的二類分類問題，每一個(gè)標(biāo)簽對應(yīng)一個(gè)二類分類問題.但此方法破壞了標(biāo)簽間的相關(guān)性，而多標(biāo)簽數(shù)據(jù)中的標(biāo)簽間往往存在一定的相關(guān)性，如一部“動(dòng)作”電影，同時(shí)也是一部“冒險(xiǎn)”電影的可能性，要比它同時(shí)是一部“愛情”電影的可能性要大.因此如何充分利用多標(biāo)簽訓(xùn)練數(shù)據(jù)中標(biāo)簽間的相關(guān)性(label correlation)來幫助構(gòu)建預(yù)測模型一直是多標(biāo)簽學(xué)習(xí)中的研究熱點(diǎn)問題之一.

眾所周知，k-近鄰算法[8](k-nearest neighbors,kNN)是一種無參懶惰學(xué)習(xí)算法，無需通過訓(xùn)練來構(gòu)建預(yù)測模型，待測樣本的預(yù)測結(jié)果直接由其k個(gè)距離最近的訓(xùn)練樣本來確定.kNN算法是機(jī)器學(xué)習(xí)領(lǐng)域最簡單有效的算法之一，經(jīng)常被用于分類或者回歸.因此，一些基于kNN算法的擴(kuò)展算法被提出用于多標(biāo)簽學(xué)習(xí)[9-12].像kNN算法一樣，這些擴(kuò)展算法也是懶惰學(xué)習(xí)算法，均需先查找樣本的k個(gè)最近鄰訓(xùn)練樣本，再采用不同的后續(xù)處理方式.最近鄰的選擇依據(jù)樣本間在特征空間上的距離，所選擇的k個(gè)最近鄰訓(xùn)練樣本直接決定算法效果.在處理多標(biāo)簽問題時(shí)，這些算法大多采用了前述的拆分策略，每個(gè)標(biāo)簽單獨(dú)求解，忽略了標(biāo)簽間的相關(guān)性.

標(biāo)簽組合是挖掘標(biāo)簽相關(guān)性的有效方式，但標(biāo)簽組合數(shù)跟標(biāo)簽數(shù)呈指數(shù)級的關(guān)系，其隨著標(biāo)簽數(shù)的增長而急劇增加，加劇了算法的復(fù)雜度，而且多標(biāo)簽數(shù)據(jù)的標(biāo)簽空間中有的標(biāo)簽相關(guān)性很大，有的則幾乎沒有相關(guān)性.因此相關(guān)性較大的標(biāo)簽應(yīng)該被放到同一類，分別考慮各類中的標(biāo)簽相關(guān)性.

像傳統(tǒng)機(jī)器學(xué)習(xí)算法一樣，多標(biāo)簽學(xué)習(xí)算法的分類預(yù)測效果依賴于輸入的特征，而且相較于傳統(tǒng)機(jī)器學(xué)習(xí)算法中只有一個(gè)類別，多標(biāo)簽學(xué)習(xí)中的有多個(gè)標(biāo)簽類別，特征與標(biāo)簽的相關(guān)性更為復(fù)雜.不同的特征對同一標(biāo)簽的分類有不同的重要度，同一特征對不同的標(biāo)簽也有著不同的重要度.有的特征對某一類標(biāo)簽分類很重要，對另一類標(biāo)簽則不是那么重要，甚至完全不相關(guān).所以不同的特征應(yīng)該根據(jù)其對標(biāo)簽分類的重要程度被給予相應(yīng)的權(quán)重.但kNN算法在計(jì)算樣本間距離時(shí)，將所有特征給予同樣的重要度.不重要的特征被同等對待，會(huì)干擾近鄰的選擇，影響算法效果.

互信息是常用的度量2個(gè)變量關(guān)聯(lián)度的方法，其能表示特征對標(biāo)簽分類的重要度.粒計(jì)算是解決復(fù)雜問題的有效方法，其模擬人類處理復(fù)雜問題的方式，將復(fù)雜問題化解成簡單問題[13-14].因此，我們提出了一種基于互信息的?；卣骷訖?quán)多標(biāo)簽學(xué)習(xí)k近鄰算法(granular feature weightedk-nearest neighbors algorithm for multi-label learning, GFWML-kNN)，該算法采用粒計(jì)算思想將標(biāo)簽空間?；啥鄠€(gè)標(biāo)簽粒，將相似的標(biāo)簽?；酵粯?biāo)簽粒中，使得不同粒中的標(biāo)簽間的相關(guān)性最小，粒內(nèi)的標(biāo)簽間相關(guān)性最大.這樣既將復(fù)雜問題分解成為了多個(gè)簡單問題，大大減少標(biāo)簽組合數(shù)，又最大限度地保留了標(biāo)簽間的相關(guān)性.對每個(gè)標(biāo)簽粒，根據(jù)特征包含的標(biāo)簽分類信息程度，對不同的特征給予不同的權(quán)重，將標(biāo)簽間的相關(guān)性融入特征的權(quán)重系數(shù).對特征進(jìn)行加權(quán)，尋找與待測樣本標(biāo)簽信息更接近的近鄰樣本，提高算法的精度.

為了驗(yàn)證所提算法的有效性，本文將GFWML-kNN與標(biāo)準(zhǔn)ML-kNN算法，以及其他經(jīng)典的多標(biāo)簽算法在多個(gè)真實(shí)世界多標(biāo)簽數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)對比，實(shí)驗(yàn)結(jié)果表明本文所提算法能取得較好的學(xué)習(xí)效果.

1 研究現(xiàn)狀

多標(biāo)簽學(xué)習(xí)已經(jīng)受到了越來越多的關(guān)注，成為機(jī)器學(xué)習(xí)領(lǐng)域中的一個(gè)研究熱點(diǎn).目前為止，一系列多標(biāo)簽學(xué)習(xí)算法已經(jīng)被提出.這些多標(biāo)簽算法主要可以分為2類：問題轉(zhuǎn)換方法(problem transformation method， PTM)和算法適應(yīng)方法(algorithm adaption method， AAM)[1].

問題轉(zhuǎn)換方法首先將多標(biāo)簽數(shù)據(jù)集轉(zhuǎn)換成多個(gè)單標(biāo)簽數(shù)據(jù)集，再采用已有的單標(biāo)簽學(xué)習(xí)算法來處理每個(gè)標(biāo)簽數(shù)據(jù).問題轉(zhuǎn)換方法獨(dú)立于算法，讓數(shù)據(jù)去適應(yīng)算法.經(jīng)典的問題轉(zhuǎn)換方法有BR(binary relevance)[15]方法、LP (label powerset)方法等.

BR[15]方法直接將多標(biāo)簽數(shù)據(jù)集中的每個(gè)標(biāo)簽拆分開來，形成|L|個(gè)獨(dú)立的單標(biāo)簽數(shù)據(jù)集，|L|表示標(biāo)簽的數(shù)量.BR方法雖然簡單，但其忽略標(biāo)簽間的相關(guān)性.考慮到標(biāo)簽的相關(guān)性，Read等人[16]提出了一種對BR方法的改進(jìn)算法，鏈?zhǔn)降姆诸?chain classifier, CC)算法用于多標(biāo)簽學(xué)習(xí).該算法同樣構(gòu)建|L|個(gè)二分類標(biāo)簽?zāi)Ｐ?，但其將先預(yù)測出的標(biāo)簽作為后待預(yù)測標(biāo)簽的輸入特征.CC雖然考慮到了標(biāo)簽間的相關(guān)性，而且算法較為簡單，但算法結(jié)果依賴于標(biāo)簽預(yù)測的順序，前面預(yù)測的標(biāo)簽誤差會(huì)傳遞到后面的標(biāo)簽中，如果前面的標(biāo)簽誤差較大，那么整體算法性能將大打折扣.因此一種集成的鏈?zhǔn)?ensembles of chain classifiers, ECC)[17]算法被提出用于解決此缺陷.PW(pairwise binary)[18]是另一種對BR改進(jìn)的方法.PW任意選取2個(gè)標(biāo)簽進(jìn)行組合，這對標(biāo)簽構(gòu)成一個(gè)二類分類問題，通過標(biāo)簽已知的數(shù)據(jù)集為每個(gè)二類分類問題訓(xùn)練一個(gè)分類模型，這樣將有|L|(|L|-1)/2個(gè)分類模型，致使PW方法計(jì)算代價(jià)過高.

LP方法則根據(jù)數(shù)據(jù)集中標(biāo)簽間組合的可能性，將多標(biāo)簽數(shù)據(jù)變成2|L|單標(biāo)簽數(shù)據(jù)，多標(biāo)簽問題變成多類分類問題.LP方法考慮到了標(biāo)簽間的相關(guān)性，但標(biāo)簽組合的爆炸性問題，極大增加了算法復(fù)雜度.因此，Tsoumakas等人[19]提出一種集成的隨機(jī)標(biāo)簽子集(ensembles of randomk-label subsets， RAkEL)方法，其從標(biāo)簽集中隨機(jī)選取k個(gè)標(biāo)簽，再研究其中可能的標(biāo)簽組合;Read等人[20]提出了EPS(ensembles of pruned sets)算法，用出現(xiàn)頻次較高的標(biāo)簽組合來表示出現(xiàn)頻次較低的標(biāo)簽組合，出現(xiàn)頻次較低的被去除.這樣既最大限度地保證了標(biāo)簽相關(guān)性，又降低了算法的復(fù)雜度.

算法適應(yīng)方法依賴于某一具體的機(jī)器學(xué)習(xí)算法，對該具體算法進(jìn)行改進(jìn)使其能直接處理多標(biāo)簽數(shù)據(jù)，如決策樹[21]、支持向量機(jī)[22]、BP神經(jīng)網(wǎng)絡(luò)[23]等算法.

Clare等人[21]利用多標(biāo)簽熵將傳統(tǒng)的C4.5決策樹算法用于多標(biāo)簽學(xué)習(xí)，稱作多標(biāo)簽C4.5，其允許葉子節(jié)點(diǎn)擁有多個(gè)標(biāo)簽.Elisseeff等人[22]將支持向量機(jī)(support vector machine, SVM)算法應(yīng)用于多標(biāo)簽學(xué)習(xí)中，提出了一種RankSVM算法.其對每個(gè)標(biāo)簽構(gòu)建一個(gè)SVM預(yù)測模型，利用排序損失考慮每個(gè)樣本的相關(guān)標(biāo)簽和不相關(guān)標(biāo)簽.BPMLL[23]算法將最流行的神經(jīng)網(wǎng)絡(luò)模型之一的BP神經(jīng)網(wǎng)絡(luò)的擴(kuò)展成多個(gè)輸出，以適應(yīng)多標(biāo)簽學(xué)習(xí)，并提出了一種排序的多標(biāo)簽的誤差度量函數(shù)，認(rèn)為待測樣本實(shí)際包含的標(biāo)簽應(yīng)該比不包含的標(biāo)簽排序靠前.Yu等人[24]提出了基于粗糙集的多標(biāo)簽學(xué)習(xí)分類算法和標(biāo)簽局部關(guān)系的粗糙集多標(biāo)簽學(xué)習(xí)分類算法.基于鄰域的思想，文獻(xiàn)[5]提出了一種基于鄰域粗糙集(neighborhood rough sets)的多標(biāo)簽分類算法，用于圖像語義標(biāo)注問題.

kNN算法無需提前訓(xùn)練模型，優(yōu)化參數(shù)，相較于其他算法，具有算法復(fù)雜度低且分類效果較好的優(yōu)勢.因此Spyromitros 等人[12]對BR方法和kNN算法結(jié)合的BRkNN算法進(jìn)行了擴(kuò)展，提出了一種懶惰的多標(biāo)簽分類算法，用測試樣本的k個(gè)近鄰訓(xùn)練樣本的標(biāo)簽近似估計(jì)它的標(biāo)簽.該方法提升了算法的運(yùn)行效率，但其也保留了BR方法的不足，即忽略了標(biāo)簽間的相關(guān)性.Zhang等人[9]將kNN算法和貝葉斯理論應(yīng)用于多標(biāo)簽學(xué)習(xí)中，提出了一種多標(biāo)簽懶惰學(xué)習(xí)算法(ML-kNN)，通過樣本的k個(gè)近鄰訓(xùn)練樣本的標(biāo)簽信息，用最大后驗(yàn)概率準(zhǔn)則預(yù)測它的標(biāo)簽.ML-kNN算法因其算法簡單、預(yù)測效果好，得到了廣泛的關(guān)注.但ML-kNN算法對每個(gè)標(biāo)簽獨(dú)立預(yù)測，未考慮到多個(gè)標(biāo)簽間的相關(guān)性.因此，文獻(xiàn)[25]提出了一種新型多標(biāo)記懶惰學(xué)習(xí)算法(IMLLA)，該算法同樣首先找出測試樣本的近鄰訓(xùn)練樣本，再利用訓(xùn)練數(shù)據(jù)的分布信息和標(biāo)簽間的相關(guān)性來進(jìn)行預(yù)測，考察了樣本多個(gè)標(biāo)簽之間的相關(guān)性.這些算法均沒有考慮特征對于標(biāo)簽分類的不同作用.因此本文提出一種基于互信息的粒化特征加權(quán)多標(biāo)簽學(xué)習(xí)k近鄰算法，以利用標(biāo)簽間的相關(guān)性，以及考慮特征對標(biāo)簽分類的重要度，并且不過多增加算法復(fù)雜度.

2 基本知識

在介紹所提算法前，先簡要介紹互信息和多標(biāo)簽學(xué)習(xí)的基本概念.

2.1 互信息

定義1. 熵[26-27]是度量隨機(jī)變量不確定性的重要工具，隨機(jī)變量X的熵為

其中，p(x) 表示x的概率密度.

定義2.X和Y的聯(lián)合熵為

其中，p(x,y) 是x和y的聯(lián)合概率密度.

定義3. 變量Y對于變量X條件熵為

其中，p(y|x) 是條件概率密度.

性質(zhì)1. 條件熵可由熵、聯(lián)合熵改寫為

H(Y|X)=H(X,Y)-H(X).

證明.

證畢.

定義4. 互信息能夠度量2個(gè)變量間的關(guān)聯(lián)程度，指出了一個(gè)變量通過另一個(gè)變量所獲得的知識，對于變量X和Y的互信息計(jì)算如下：

可以看出I(X;Y)=I(Y;X).當(dāng)X與Y相互獨(dú)立時(shí)互信息值為0.

性質(zhì)2. 互信息可以用熵和條件熵表示為

I(X;Y)=H(Y)-H(Y|X).

證明.

證畢.

2.2 多標(biāo)簽學(xué)習(xí)

3 GFWML-kNN

針對以往基于kNN的多標(biāo)簽學(xué)習(xí)算法不考慮特征重要性的差異，忽略標(biāo)簽間的相關(guān)性以及避免標(biāo)簽組合爆炸問題，本文提出基于互信息的?；卣骷訖?quán)多標(biāo)簽學(xué)習(xí)k近鄰算法.該算法首先基于粒計(jì)算的思想，用平衡k均值(balancedk-means)聚類算法[27]將標(biāo)簽空間?；啥鄠€(gè)標(biāo)簽粒，簡化標(biāo)簽的組合；然后，對每個(gè)標(biāo)簽粒，根據(jù)特征與標(biāo)簽粒的互信息的大小，為特征賦予相應(yīng)的權(quán)重系數(shù)，權(quán)重系數(shù)包含了標(biāo)簽相關(guān)性的信息，為待測樣本找到更貼切的近鄰訓(xùn)練樣本；最后，根據(jù)近鄰訓(xùn)練樣本的標(biāo)簽信息可以計(jì)算待測樣本的標(biāo)簽后驗(yàn)概率值，預(yù)測出待測樣本相應(yīng)的標(biāo)簽.

3.1 標(biāo)簽?；疤卣骷訖?quán)

互信息能夠有效度量2個(gè)變量間的關(guān)聯(lián)性，用其度量標(biāo)簽對特征的依賴度.互信息值越大，說明特征含有標(biāo)簽分類的信息越多，該特征越重要，權(quán)重系數(shù)越高，因此特征的權(quán)重系數(shù)與其含有的標(biāo)簽分類信息等價(jià).

定義5. 特征fi對整個(gè)標(biāo)簽空間L的重要度，即特征fi的權(quán)重系數(shù)ωi為

ωi=I(fi;L),

其中，I(fi;L)表示特征fi∈F與標(biāo)簽空間L的互信息.I(fi;L)由定義4可得:

目前粒計(jì)算中主要的粒化方法有粗糙集理論、模糊集理論、聚類分析等[13-14].本文考慮聚類分析中流行的k均值(k-means)聚類算法來粒化標(biāo)簽空間，為了防止?；瘯r(shí)出現(xiàn)標(biāo)簽不平衡問題，即有的標(biāo)簽粒中標(biāo)簽數(shù)過多，不能有效減少標(biāo)簽組合的數(shù)量，降低算法復(fù)雜度，因此采用平衡k均值(balancedk-means)聚類算法[27]，將標(biāo)簽均勻地分散到各個(gè)標(biāo)簽粒中，具體的標(biāo)簽?；^程如算法1所示.

往往同一個(gè)特征對不同標(biāo)簽粒的重要度不同，因此需對每一個(gè)標(biāo)簽粒Ge，計(jì)算其對應(yīng)的特征權(quán)重系數(shù).

定義6. 對標(biāo)簽粒Ge，特征fi的權(quán)重系數(shù)為

算法1. 標(biāo)簽粒化過程.

輸入：標(biāo)簽空間L、訓(xùn)練集T={(X1,Y1),(X2,Y2),…,(Xn,Yn)}、標(biāo)簽粒個(gè)數(shù)r、迭代次數(shù)iter;

輸出：r個(gè)標(biāo)簽粒.

步驟1. 對每個(gè)標(biāo)簽粒Gi和粒中心gi初始化，將Gi賦值為φ，從L中隨機(jī)選擇標(biāo)簽到gi.

步驟2. 將標(biāo)簽?；礁鱾€(gè)粒中：

WHILEiter>0

FORlj∈L

步驟2.1. 計(jì)算lj到每個(gè)粒中心gi在數(shù)據(jù)集T中的距離dij，令φ表示lj，將循環(huán)信號flag設(shè)為真；

步驟2.2. 對lj?；?/p>

WHILEflag

① 找到離φ最近的粒中心gk，將lj插入Gk中，根據(jù)距離大小對Gk中的標(biāo)簽進(jìn)行排序；

③ 將Gk中排序最后一個(gè)標(biāo)簽賦值給φ，并把該標(biāo)簽從Gk去除，把dkφ設(shè)為∞；

④ ELSE將循環(huán)信號flag設(shè)為假；

⑤ END IF

END WHILE

END FOR

重新計(jì)算各粒中心，迭代次數(shù)iter減1.

END WHILE

步驟3. 得到標(biāo)簽粒G1,G2,…,Gr.

3.2 近鄰選擇

以往的算法在尋找近鄰、度量樣本間的相似度和計(jì)算樣本間距離時(shí)，對所有特征給予相同的權(quán)重，不考慮特征間重要度的差異，這里以歐氏距離為例，歐氏距離是kNN算法中常用的一種樣本距離度量，樣本Xi與Xj的距離計(jì)算如下：

而往往不同特征含有的標(biāo)簽分類信息不同，需將特征重要度的差異體現(xiàn)在距離中，計(jì)算出特征加權(quán)的距離.

定義7. 對于標(biāo)簽粒Ge，基于特征的權(quán)重信息ωe得到樣本間特征加權(quán)的歐氏距離：

性質(zhì)3. 特征加權(quán)的歐氏距離與一般的歐氏距離有關(guān)系：

De(Xi,Xj)=d(ωeXi,ωeXj).

證明.

證畢.

在標(biāo)簽粒Ge上，樣本X得到一個(gè)與標(biāo)簽已知的訓(xùn)練樣本的加權(quán)歐氏距離集De={De(X,X1),De(X,X2),…,De(X,Xn)}.對距離集De中的距離值升序排列后，第k個(gè)距離值設(shè)為閾值t，獲得樣本X在標(biāo)簽粒Ge上訓(xùn)練集中的k個(gè)最近鄰訓(xùn)練樣本Ne(X)={Xi|De(X,Xi)≤t}.

3.3 標(biāo)簽預(yù)測

根據(jù)k個(gè)近鄰Ne(X)，基于經(jīng)典的ML-kNN算法[9]，預(yù)測標(biāo)簽未知的測試樣本X含有標(biāo)簽粒Ge中標(biāo)簽的概率值，將得到的各標(biāo)簽粒的結(jié)果最后組合得到測試樣本X的標(biāo)簽概率向量P=(p1,p2,…,pq)，由標(biāo)簽概率向量可以得到預(yù)測的標(biāo)簽向量Y′=(y1′,y2′,…,yq′).

算法2. ?；卣骷訖?quán)的多標(biāo)簽k近鄰算法.

輸入：測試樣本X、近鄰數(shù)k、訓(xùn)練集T={(X1,Y1),(X2,Y2),…,(Xn,Yn)}、標(biāo)簽粒個(gè)數(shù)r、迭代次數(shù)iter、標(biāo)簽空間L；

輸出：X的標(biāo)簽概率向量P、標(biāo)簽向量Y′.

步驟1. 根據(jù)算法1對標(biāo)簽空間L進(jìn)行?；?，得到標(biāo)簽粒Ge(1≤e≤r).

步驟2. 對每個(gè)標(biāo)簽粒進(jìn)行如下處理：

FORe=1 tor

步驟2.1. 根據(jù)式(9)得到關(guān)于標(biāo)簽粒Ge的特征系數(shù)ωe；

步驟2.2. 對訓(xùn)練樣本和測試樣本的特征進(jìn)行加權(quán)得到ωeXi(1≤i≤n)和ωeX；

步驟2.3. 根據(jù)式(10)計(jì)算測試樣本X與所有訓(xùn)練樣本Xi的加權(quán)距離，找到X的k個(gè)近鄰訓(xùn)練樣本Ne(X)；

FORlj∈Ge

步驟2.4. 根據(jù)經(jīng)典ML-kNN算法[9]，統(tǒng)計(jì)出Ne(X)中擁有標(biāo)簽lj的樣本個(gè)數(shù)CX(lj)，得到X含有標(biāo)簽lj的概率預(yù)測值：

END FOR

步驟3. 將所有標(biāo)簽的概率預(yù)測值組合后得到X所有的標(biāo)簽概率：

P=(p1,p2,…,pq).

步驟4. 由標(biāo)簽概率得到X的預(yù)測標(biāo)簽向量Y′=(y1′,y2′,…,yq′)，如果pj≥0.5，則yj′=1，否則yj′=0.

4 數(shù)據(jù)實(shí)驗(yàn)

4.1 數(shù)據(jù)集及實(shí)驗(yàn)設(shè)置

為了驗(yàn)證算法的有效性，本文選取了來自Mulan Library[29]的涵蓋多個(gè)領(lǐng)域的5個(gè)真實(shí)世界的多標(biāo)簽數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，多標(biāo)簽數(shù)據(jù)集對應(yīng)的名稱、領(lǐng)域、樣本數(shù)量、特征維度、標(biāo)簽空間中標(biāo)簽數(shù)量、標(biāo)簽基數(shù)等詳細(xì)信息如表1所示:

Table 1 Multi-Label Datasets Used in the Experiments表1 多標(biāo)簽數(shù)據(jù)集

1) Emotions數(shù)據(jù)集[30]包含了593個(gè)標(biāo)注了情感的歌曲樣本，每個(gè)樣本由72個(gè)特征來描述，即8韻律特征和64音色特征和6個(gè)可能的情感標(biāo)簽表示，每個(gè)標(biāo)簽代表了一個(gè)基于Tellegen-Watson-Clark模型的歌曲情感聚類.

2) Medical數(shù)據(jù)集[31]包含了978個(gè)病歷樣本，其含有1 449個(gè)特征，每個(gè)樣本的特征由診斷歷史記錄和觀察到的癥狀組成，標(biāo)簽則是45種ICD-9-CM疾病編碼.

3) Yeast數(shù)據(jù)集[22]用于描述酵母菌的基因功能分類，其包含了2 417個(gè)樣本，每個(gè)樣本表示一個(gè)yeast基因，每個(gè)基因?qū)?yīng)于一個(gè)103維的特征向量，標(biāo)簽空間是14種可能的基因功能.

4) CAL500數(shù)據(jù)集[32]含有502首流行樂曲，以及174個(gè)風(fēng)格、情緒、樂器等語義關(guān)鍵詞，每個(gè)樣本由68個(gè)特征表示.

5) Genbase數(shù)據(jù)集[33]是一個(gè)關(guān)于蛋白質(zhì)功能分類的多標(biāo)簽數(shù)據(jù)集，由662個(gè)蛋白質(zhì)樣本組成，每個(gè)蛋白質(zhì)由1 185個(gè)蛋白基序表示.標(biāo)簽為27個(gè)蛋白家族功能類別，如抗氧化酶、結(jié)構(gòu)蛋白、受體等.

Medical和Genbase數(shù)據(jù)集的特征值為離散型，而其他數(shù)據(jù)集的特征值為連續(xù)型.對于離散型的特征，可以很容易計(jì)算其與標(biāo)簽的互信息，而連續(xù)型的特征則比較困難.因此，我們對連續(xù)型特征采用二值等距區(qū)間離散化方法.

除了經(jīng)典的多標(biāo)簽懶惰學(xué)習(xí)算法ML-kNN[9]，還將本文所提算法與其他常見的多標(biāo)簽學(xué)習(xí)算法RankSVM[20],BPMLL[21]，BRkNN[12]進(jìn)行了對比.所有的實(shí)驗(yàn)在Matlab2012b上完成.為了取得最佳效果，根據(jù)相應(yīng)文獻(xiàn)的建議選取最優(yōu)的參數(shù)配置.ML-kNN算法中，近鄰數(shù)為10、平滑因子為1;RankSVM選用了度為8的多項(xiàng)式核函數(shù);BPMLL的隱藏層節(jié)點(diǎn)數(shù)為特征數(shù)的20%;BRkNN的近鄰數(shù)為10.根據(jù)表1統(tǒng)計(jì)的多標(biāo)簽數(shù)據(jù)集的標(biāo)簽數(shù)，實(shí)驗(yàn)中本文算法GFWML-kNN在數(shù)據(jù)集Emotions，Medical，Yeast，CAL500，Genbase的標(biāo)簽粒數(shù)分別為2，6，3，15，5.

4.2 評價(jià)指標(biāo)

1) 漢明損失(Hamming loss,Hamloss).度量算法預(yù)測出的標(biāo)簽信息與實(shí)際的標(biāo)簽信息的平均差異值:

2) 1-錯(cuò)誤率(one error,Onerror).計(jì)算算法預(yù)測的排序最靠前的標(biāo)簽實(shí)際不是測試樣本的標(biāo)簽的比率:

3) 覆蓋率(Coverage).計(jì)算要囊括測試樣本實(shí)際包含的所有標(biāo)簽所需最大排序距離:

4) 排序損失(ranking loss,Rankloss).評價(jià)有多少測試樣本實(shí)際不包含的標(biāo)簽比實(shí)際包含的標(biāo)簽排序高:

5) 平均準(zhǔn)確率(average precision,Avgprec).用于評價(jià)給定一個(gè)測試樣本實(shí)際包含的標(biāo)簽，平均有多少實(shí)際包含的標(biāo)簽排序比其高:

前面4項(xiàng)評價(jià)指標(biāo)的值越低說明算法效果越好，而平均準(zhǔn)確率值越高則說明算法效果越好.

4.3 實(shí)驗(yàn)結(jié)果

4.3.1 近鄰參數(shù)選擇

首先討論了近鄰數(shù)k的選擇以及驗(yàn)證標(biāo)簽空間的?；瘺]有對標(biāo)簽相關(guān)性造成過大的損失.以Emotions數(shù)據(jù)集為例，圖1～5給出了Emotions數(shù)據(jù)集的5項(xiàng)評價(jià)指標(biāo)隨著近鄰數(shù)k增加的變化曲線.其中，k以步長2從2增加到20.圖1～5中，ML-kNN曲線表示經(jīng)典的多標(biāo)簽懶惰學(xué)習(xí)算法；FWML-kNN曲線表示未?；奶卣骷訖?quán)ML-kNN算法；GFWML-kN曲線表示粒化的特征加權(quán)ML-kNN算法.

Fig. 1 Hamming loss of varying the number of nearest neighbors圖1 漢明損失隨著近鄰數(shù)增加的變化曲線

Fig. 2 One error of varying the number of nearest neighbors圖2 1-錯(cuò)誤率隨著近鄰數(shù)增加的變化曲線

Fig. 3 Coverage of varying the number of nearest neighbors圖3 覆蓋率隨著近鄰數(shù)增加的變化曲線

Fig. 4 Ranking loss of varying the number of nearest neighbors圖4 排序損失隨著近鄰數(shù)增加的變化曲線

Fig. 5 Average precision of varying the number of nearest neighbors圖5 平均準(zhǔn)確率隨著近鄰數(shù)增加的變化曲線

在各項(xiàng)評價(jià)指標(biāo)上，粒化和未?；奶卣骷訖?quán)ML-kNN以及經(jīng)典的ML-kNN的性能均隨著近鄰數(shù)k的增加而快速提升，而后達(dá)到最優(yōu)值后逐漸略微下降.其中，?；臀戳；奶卣骷訖?quán)ML-kNN的性能變化趨勢十分接近，且在各個(gè)近鄰數(shù)上基本都優(yōu)于經(jīng)典ML-kNN.當(dāng)近鄰數(shù)k=10，性能最優(yōu)，因此，本文近鄰數(shù)設(shè)為10.

GFWML-kNN算法取得的最優(yōu)值除了在漢明損失Hamloss上比未?；奶卣骷訖?quán)多標(biāo)簽學(xué)習(xí)懶惰算法略大一點(diǎn)，在1-錯(cuò)誤率Onerror、排序損失Rankloss和平均精度Avgprec上均要優(yōu)于未?；乃惴?，兩者取得相同的覆蓋率Coverage最優(yōu)值.綜上，GFWML-kNN算法的性能不但不差于未?；奶卣骷訖?quán)ML-kNN算法，反而略優(yōu)，說明GFWML-kNN算法的?；瘞缀醣Ａ袅藰?biāo)簽間的相關(guān)性，找到更合適的近鄰，提高了算法的性能.

4.3.2 實(shí)驗(yàn)對比

實(shí)驗(yàn)采用了十折交叉驗(yàn)證(ten-fold cross-validation)方法，實(shí)驗(yàn)結(jié)果用均值±標(biāo)準(zhǔn)差表示.表2～5表示了各個(gè)多標(biāo)簽學(xué)習(xí)算法在多標(biāo)簽數(shù)據(jù)集Emotions，Medical，Yeast，CAL500，Genbase上取得的實(shí)驗(yàn)結(jié)果，其中各項(xiàng)評價(jià)指標(biāo)的最優(yōu)值用粗體標(biāo)注，↓(↑)表示該項(xiàng)評價(jià)指標(biāo)值越小(越大)算法效果越好.

Table 2 Experimental Results Obtained by Multi-label Algorithms (Mean±Std.deviation) on the Emotions Dataset表2 Emotions數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果(均值±標(biāo)準(zhǔn)差)