基于互信息的粒化特征加權多標簽學習k近鄰算法

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

計算機研究與發展 2017年5期

關鍵詞：分類特征

李峰苗奪謙張志飛張維

(同濟大學計算機科學與技術系上海 201804)(嵌入式系統與服務計算教育部重點實驗室(同濟大學) 上海 201804)(tjleefeng@163.com)

基于互信息的粒化特征加權多標簽學習k近鄰算法

李峰苗奪謙張志飛張維

(同濟大學計算機科學與技術系上海 201804)(嵌入式系統與服務計算教育部重點實驗室(同濟大學) 上海 201804)(tjleefeng@163.com)

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

互信息；特征權重；粒化；多標簽學習；k-近鄰

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

在面對復雜問題時，人類往往將復雜問題分解為多個簡單問題，再逐個解決.機器學習領域沿用了此方法，傳統機器學習中將多類分類問題拆分成多個二類分類問題.直觀上，多標簽學習問題也可以被拆分成多個獨立的二類分類問題，每一個標簽對應一個二類分類問題.但此方法破壞了標簽間的相關性，而多標簽數據中的標簽間往往存在一定的相關性，如一部“動作”電影，同時也是一部“冒險”電影的可能性，要比它同時是一部“愛情”電影的可能性要大.因此如何充分利用多標簽訓練數據中標簽間的相關性(label correlation)來幫助構建預測模型一直是多標簽學習中的研究熱點問題之一.

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

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

像傳統機器學習算法一樣，多標簽學習算法的分類預測效果依賴于輸入的特征，而且相較于傳統機器學習算法中只有一個類別，多標簽學習中的有多個標簽類別，特征與標簽的相關性更為復雜.不同的特征對同一標簽的分類有不同的重要度，同一特征對不同的標簽也有著不同的重要度.有的特征對某一類標簽分類很重要，對另一類標簽則不是那么重要，甚至完全不相關.所以不同的特征應該根據其對標簽分類的重要程度被給予相應的權重.但kNN算法在計算樣本間距離時，將所有特征給予同樣的重要度.不重要的特征被同等對待，會干擾近鄰的選擇，影響算法效果.

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

為了驗證所提算法的有效性，本文將GFWML-kNN與標準ML-kNN算法，以及其他經典的多標簽算法在多個真實世界多標簽數據集上進行了實驗對比，實驗結果表明本文所提算法能取得較好的學習效果.

1 研究現狀

多標簽學習已經受到了越來越多的關注，成為機器學習領域中的一個研究熱點.目前為止，一系列多標簽學習算法已經被提出.這些多標簽算法主要可以分為2類：問題轉換方法(problem transformation method， PTM)和算法適應方法(algorithm adaption method， AAM)[1].

問題轉換方法首先將多標簽數據集轉換成多個單標簽數據集，再采用已有的單標簽學習算法來處理每個標簽數據.問題轉換方法獨立于算法，讓數據去適應算法.經典的問題轉換方法有BR(binary relevance)[15]方法、LP (label powerset)方法等.

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

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

算法適應方法依賴于某一具體的機器學習算法，對該具體算法進行改進使其能直接處理多標簽數據，如決策樹[21]、支持向量機[22]、BP神經網絡[23]等算法.

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

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

2 基本知識

在介紹所提算法前，先簡要介紹互信息和多標簽學習的基本概念.

2.1 互信息

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

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

定義2.X和Y的聯合熵為

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

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

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

性質1. 條件熵可由熵、聯合熵改寫為

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

證明.

證畢.

定義4. 互信息能夠度量2個變量間的關聯程度，指出了一個變量通過另一個變量所獲得的知識，對于變量X和Y的互信息計算如下：

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

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

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

證明.

證畢.

2.2 多標簽學習

3 GFWML-kNN

針對以往基于kNN的多標簽學習算法不考慮特征重要性的差異，忽略標簽間的相關性以及避免標簽組合爆炸問題，本文提出基于互信息的粒化特征加權多標簽學習k近鄰算法.該算法首先基于粒計算的思想，用平衡k均值(balancedk-means)聚類算法[27]將標簽空間粒化成多個標簽粒，簡化標簽的組合；然后，對每個標簽粒，根據特征與標簽粒的互信息的大小，為特征賦予相應的權重系數，權重系數包含了標簽相關性的信息，為待測樣本找到更貼切的近鄰訓練樣本；最后，根據近鄰訓練樣本的標簽信息可以計算待測樣本的標簽后驗概率值，預測出待測樣本相應的標簽.

3.1 標簽粒化及特征加權

互信息能夠有效度量2個變量間的關聯性，用其度量標簽對特征的依賴度.互信息值越大，說明特征含有標簽分類的信息越多，該特征越重要，權重系數越高，因此特征的權重系數與其含有的標簽分類信息等價.

定義5. 特征fi對整個標簽空間L的重要度，即特征fi的權重系數ωi為

ωi=I(fi;L),

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

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

往往同一個特征對不同標簽粒的重要度不同，因此需對每一個標簽粒Ge，計算其對應的特征權重系數.

定義6. 對標簽粒Ge，特征fi的權重系數為

算法1. 標簽粒化過程.

輸入：標簽空間L、訓練集T={(X1,Y1),(X2,Y2),…,(Xn,Yn)}、標簽粒個數r、迭代次數iter;

輸出：r個標簽粒.

步驟1. 對每個標簽粒Gi和粒中心gi初始化，將Gi賦值為φ，從L中隨機選擇標簽到gi.

步驟2. 將標簽粒化到各個粒中：

WHILEiter>0

FORlj∈L

步驟2.1. 計算lj到每個粒中心gi在數據集T中的距離dij，令φ表示lj，將循環信號flag設為真；

步驟2.2. 對lj粒化：

WHILEflag

① 找到離φ最近的粒中心gk，將lj插入Gk中，根據距離大小對Gk中的標簽進行排序；

③ 將Gk中排序最后一個標簽賦值給φ，并把該標簽從Gk去除，把dkφ設為∞；

④ ELSE將循環信號flag設為假；

⑤ END IF

END WHILE

END FOR

重新計算各粒中心，迭代次數iter減1.

END WHILE

步驟3. 得到標簽粒G1,G2,…,Gr.

3.2 近鄰選擇

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

而往往不同特征含有的標簽分類信息不同，需將特征重要度的差異體現在距離中，計算出特征加權的距離.

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

性質3. 特征加權的歐氏距離與一般的歐氏距離有關系：

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

證明.

證畢.

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

3.3 標簽預測

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

算法2. 粒化特征加權的多標簽k近鄰算法.

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

輸出：X的標簽概率向量P、標簽向量Y′.

步驟1. 根據算法1對標簽空間L進行粒化，得到標簽粒Ge(1≤e≤r).

步驟2. 對每個標簽粒進行如下處理：

FORe=1 tor

步驟2.1. 根據式(9)得到關于標簽粒Ge的特征系數ωe；

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

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

FORlj∈Ge

步驟2.4. 根據經典ML-kNN算法[9]，統計出Ne(X)中擁有標簽lj的樣本個數CX(lj)，得到X含有標簽lj的概率預測值：

END FOR

步驟3. 將所有標簽的概率預測值組合后得到X所有的標簽概率：

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

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

4 數據實驗

4.1 數據集及實驗設置

為了驗證算法的有效性，本文選取了來自Mulan Library[29]的涵蓋多個領域的5個真實世界的多標簽數據集進行實驗，多標簽數據集對應的名稱、領域、樣本數量、特征維度、標簽空間中標簽數量、標簽基數等詳細信息如表1所示:

Table 1 Multi-Label Datasets Used in the Experiments表1 多標簽數據集

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

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

3) Yeast數據集[22]用于描述酵母菌的基因功能分類，其包含了2 417個樣本，每個樣本表示一個yeast基因，每個基因對應于一個103維的特征向量，標簽空間是14種可能的基因功能.

4) CAL500數據集[32]含有502首流行樂曲，以及174個風格、情緒、樂器等語義關鍵詞，每個樣本由68個特征表示.

5) Genbase數據集[33]是一個關于蛋白質功能分類的多標簽數據集，由662個蛋白質樣本組成，每個蛋白質由1 185個蛋白基序表示.標簽為27個蛋白家族功能類別，如抗氧化酶、結構蛋白、受體等.

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

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

4.2 評價指標

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

2) 1-錯誤率(one error,Onerror).計算算法預測的排序最靠前的標簽實際不是測試樣本的標簽的比率:

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

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

5) 平均準確率(average precision,Avgprec).用于評價給定一個測試樣本實際包含的標簽，平均有多少實際包含的標簽排序比其高:

前面4項評價指標的值越低說明算法效果越好，而平均準確率值越高則說明算法效果越好.

4.3 實驗結果

4.3.1 近鄰參數選擇

首先討論了近鄰數k的選擇以及驗證標簽空間的粒化沒有對標簽相關性造成過大的損失.以Emotions數據集為例，圖1～5給出了Emotions數據集的5項評價指標隨著近鄰數k增加的變化曲線.其中，k以步長2從2增加到20.圖1～5中，ML-kNN曲線表示經典的多標簽懶惰學習算法；FWML-kNN曲線表示未粒化的特征加權ML-kNN算法；GFWML-kN曲線表示粒化的特征加權ML-kNN算法.

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

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

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

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

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

在各項評價指標上，粒化和未粒化的特征加權ML-kNN以及經典的ML-kNN的性能均隨著近鄰數k的增加而快速提升，而后達到最優值后逐漸略微下降.其中，粒化和未粒化的特征加權ML-kNN的性能變化趨勢十分接近，且在各個近鄰數上基本都優于經典ML-kNN.當近鄰數k=10，性能最優，因此，本文近鄰數設為10.

GFWML-kNN算法取得的最優值除了在漢明損失Hamloss上比未粒化的特征加權多標簽學習懶惰算法略大一點，在1-錯誤率Onerror、排序損失Rankloss和平均精度Avgprec上均要優于未粒化的算法，兩者取得相同的覆蓋率Coverage最優值.綜上，GFWML-kNN算法的性能不但不差于未粒化的特征加權ML-kNN算法，反而略優，說明GFWML-kNN算法的粒化幾乎保留了標簽間的相關性，找到更合適的近鄰，提高了算法的性能.

4.3.2 實驗對比

實驗采用了十折交叉驗證(ten-fold cross-validation)方法，實驗結果用均值±標準差表示.表2～5表示了各個多標簽學習算法在多標簽數據集Emotions，Medical，Yeast，CAL500，Genbase上取得的實驗結果，其中各項評價指標的最優值用粗體標注，↓(↑)表示該項評價指標值越小(越大)算法效果越好.

Table 2 Experimental Results Obtained by Multi-label Algorithms (Mean±Std.deviation) on the Emotions Dataset表2 Emotions數據集的實驗結果(均值±標準差)