基于標簽相關性的K 近鄰多標簽學習

錢 龍，趙 靜，韓京宇，毛 毅

（南京郵電大學 計算機學院，南京 210023）

0 概述

多標簽學習廣泛存在于真實世界中。在文檔分類問題［1-3］中，每篇文檔可能隸屬于多個預定義的主題，如“經濟”與“文化”；在場景分類［4］問題中，每個場景圖片可能屬于多個語義類別，如“海灘”和“城市”；在ECG 心電異常檢測［5］問題中，每個病人可能同時具有多種心臟疾病，如“完全性左束支阻滯”“前壁心肌梗死”以及“下壁心肌梗死”。對于上述多標簽學習問題，訓練集中的每條樣本對應一組標簽，學習系統通過對訓練集進行學習從而完成對未知樣本標簽集的預測。

如果限定每個樣本只對應一個標簽，那么傳統的二分類以及多分類問題均可看作多標簽學習問題的特例。相較二分類以及多分類問題，多標簽學習的難點在于隨著標簽數量的增加，待預測的標簽組合數量呈指數級增長［6］，從而導致分類器的計算成本過高，例如，一個具有20 個標簽的數據集，每條樣本對應的標簽組合一共有220種，且各個標簽組合對應的訓練樣本數不平衡［7］，會進一步增加學習的難度。在解決此類問題時，一種直觀的做法是將其轉換為多個獨立的二分類問題來求解［8］，其中，每個二分類問題對應一個可能的標簽。然而，此種做法忽略了樣本標簽間的相關性［9-11］，因此，其泛化性能往往并不理想。例如，在ECG 心電異常檢測問題中［5］，如果已知一個病人具有下壁心肌梗死疾病，則該病人具有前壁心肌梗死疾病的可能性將大于完全性左束支阻滯疾病［5］。因此，有效利用標簽間的相關性是解決多標簽學習問題的關鍵。

根據多標簽學習中考慮的標簽關聯程度，可以將現有方法分為一階策略、二階策略和高階策略3 類［12］：一階策略是將每個標簽看成是獨立不相關的，不考慮標簽間的相關性；二階策略利用了標簽成對的關聯信息；高階策略考慮每個標簽對其他標簽的影響。LP 算法［13］將多標簽問題轉換為多分類問題，雖然其考慮了標簽間的相關性，但標簽組合的爆炸提高了算法的復雜度。TSOUMAKAS 等［14］提出Random k-Labelsets 算法，該算法將集成學習與LP算法［13］相結合，將原始的標簽集分成若干子標簽集，使用LP 技術訓練相應的分類器，但是，該算法對于標簽子集的選擇是隨機的，沒有充分利用標簽集間的相關性。READ 等［15］提出了分類器鏈（Classifier Chain，CC）算法，該算法將先預測出的標簽作為后續待預測標簽的輸入特征，CC 算法雖然考慮到了標簽間的相關性，但其結果依賴于標簽預測的順序，前面預測的標簽誤差會傳遞到后面的標簽中，如果前面的標簽誤差較大，將會導致算法整體分類性能不佳。YANG 等［16］提出深度森林的多標簽學習（Multilabel Learning with Deep Forest，MLDF）算法，MLDF算法通過設計多層結構來學習標簽之間的相關性，使得深度森林模型適用于多標簽分類場景。

本文提出一種雙模態、閾值自調節的多標簽學習K 近鄰算法，該算法的核心思想是根據標簽相關性的雙模態來構建預測模型，其中，一種模態是某些標簽和其他標簽具有多階相關性，另一種模態是某些標簽和其他標簽是獨立的。使用Fp_growth［17］算法挖掘標簽集的頻繁項，明確數據集本身固有的標簽高階關系，然后基于本文算法為高階標簽關系建模，評估樣本標簽集合是每一種頻繁項的可能性，如果標簽高階關系模型不能預測出樣本的標簽集合，說明該樣本具有的標簽間相關性并不強，則使用一階策略完成該樣本標簽集的預測。在此基礎上，提出一種閾值自學習算法，該算法采用通用的Beta 分布［18］描述閾值分布，基于每個頻繁項和標簽在原始特征空間上選擇出對應的特征子空間，針對特征子空間中的每條樣本，根據相應的評分模型獲取相應的概率，用于更新Beta 分布的參數α和β，使得閾值更加準確地擬合樣本分布，從而提高模型的預測性能。

1 問題描述與解決方案

1.1 問題描述

設D={(xi，Yi)|1≤i≤m}(xi∈X，Yi?Y)為給定的多標簽數據集，其中，X=Rd表示d維的樣本空間，Y={l1，l2，…，lq}表示所有可能的標簽，q是標簽數量，xi是第i條訓練樣本實例，Yi∈Y為樣本xi對應的標簽集。

本文目的是基于標簽相關性的雙模態分別構建2 個分類器：

1）第一個分類器是h1(x)，該分類器輸出一個實值函數f：X×P→R，對于給定樣本x及頻繁項Pj(1≤j≤k)，分類器h1(x)輸出的函數值量化樣本x與頻繁項Pj相關性得分的大小，頻繁項由Fp_growth［17］算法挖掘得到，P={P1，P2，…，Pk}為頻繁項集，k為頻繁項個數。分類器h1(·)可由f(·，·)求得：

其中：CT(Pt)是頻繁項Pt對應的閾值，本文稱為關聯閾值。

2）第二個分類器是h2(x)，該分類器輸出一個實值函數g：X×Y→R，對于給定樣本x和標簽lj(1≤j≤q)，分類器h2(x)輸出的函數值可以量化樣本x與標簽lj相關性得分的大小。分類器h2(·)可由g(·，·)求得：

其中：IT(lt)是標簽lt對應的閾值，本文稱為獨立閾值。

當頻繁項相關性得分大于對應的關聯閾值且該頻繁項得分是所有頻繁項中的最大值時，樣本的標簽集就是該頻繁項。當通過多標簽分類器h1(x)預測樣本的標簽為空集時，說明樣本的標簽集并不在頻繁項集中，驗證了樣本標簽間的相關性并不大，此時再使用分類器h2(x)預測樣本的標簽集，從而兼顧標簽間多種可能的相關性。

定義1（特征子空間）在多標簽任務中，給定標簽lj(1≤j≤q)和頻繁項Pj(1 ≤j≤k)，可以在原始樣本空間中獲得對應的特征子空間：

定義2（頻繁項）給定一個標簽組合ls(ls?Y)和最小支持度θ(1<θ≤|D|)，如果標簽組合ls在數據集D中出現的頻數大于等于最小支持度θ，則該標簽組合ls就是一個頻繁項Pj(1≤j≤k)。

1.2 解決方案框架

本文提出一種基于標簽相關性的多標簽學習K 近鄰算法，其架構如圖1 所示。首先，使用頻繁項挖掘算法Fp_growth［17］挖掘給定數據集的頻繁項集；然后，為頻繁項相關性得分和標簽相關性得分建模，基于這2 種評分模型使用閾值自學習算法為每一個頻繁項和標簽學習對應的關聯閾值和獨立閾值。至此，多標簽學習分類模型構建完畢，最終使用預測算法完成測試樣本預測。

圖1 本文算法結構框架Fig.1 The structure framework of this algorithm

2 訓練與預測

2.1 相關性得分建模

本文對標簽高階關系和單標簽分別進行建模，建模方法與ML-kNN 算法［19］相比，ML-kNN 算法將標簽與其他標簽之間看作是相互獨立的，實現了單標簽的建模與模型求解，忽略了標簽之間的相關性，本文在ML-kNN 單標簽建模算法的基礎上，實現高階標簽關系建模與模型求解，兼顧了標簽間多種可能的相關性。

標簽高階關系通常以頻繁項的形式呈現，對頻繁項相關性得分進行建模，形式化表示為：

其中：p(Pj)是頻繁項Pj的先驗概率；表示在樣本t的標簽集是頻繁項Pj的條件下，樣本t的k 近鄰樣本中恰有個樣本的標簽集是頻繁項Pj的概率。

st(Pj)計算過程如算法1 所示。

對標簽相關性得分進行建模，形式化表示為：

使用貝葉斯準則，式（7）可以重寫為：

st(lj)的計算過程見文獻［19］。以上2 種評分模型求解算法的時間復雜度類似，以算法1 的時間復雜度為例進行分析，該算法是對標簽高階關系建模以評估樣本標簽集是該頻繁項的可能性，核心步驟是計算先驗p(Pj)和似然，這2 個概率的計算都是基于訓練集T中樣本數的統計而進行的，需要遍歷整個訓練集T，因此，該算法的時間復雜度為O(N)。

2.2 閾值自學習算法

對于某個樣本t，通過上述相關性得分建模算法，便可得到模型對各個頻繁項的相關性得分以及模型對各個標簽的相關性得分。在多標簽分類中，每個實例對應的標簽數是不同的，大多數情況下采取的做法是設置全局閾值，將標簽相關性得分大于全局閾值的標簽篩選出來。本文采取一種更加靈活的方法，為每個頻繁項自動地學習得到適用于樣本特征的關聯閾值，為每個標簽自動地學習得到適用于樣本特征的獨立閾值。關聯閾值記為：

本文采用通用的Beta 分布來描述關聯閾值CT(Pj)(Pj∈P，CT(Pj)∈[0，1])的閾值分布。Beta 分布的參數α和β可以基于可用樣本通過貝葉斯推斷估計出。f(CT(Pj)：α，β)是關聯閾值服從的Beta 分布的密度函數，α和β決定了密度函數的形狀。本文利用關聯閾值自學習算法求解關聯閾值CT(Pj)，關聯閾值自學習算法描述如下：

獨立閾值自學習算法描述如下：

值得注意的是，以上提到的2 種閾值自學習算法都是增量式學習算法，當有新的訓練樣本時，可以基于已有的閾值直接進行更新，而無需重新學習。

例1假設一個頻繁項P1，在訓練集中有3 個樣本t1、t2、t3的標簽集是該頻繁項，對t1、t2、t3計算頻繁項相關性得分，分別為，假設頻繁項P1的關聯閾值Beta 分布的初始參數為α0=1，β0=1，則Beta 分布參數的更新如下：

α1=1+100×0.28=29，β1=1+100×0.72=73

α2=29+100×0.25=54，β2=73+100×0.75=148

α3=54+100×0.44=98，β3=148+100×0.56=204

最終，頻繁項P1的關聯閾值為：

2.3 預測算法

預測的思路是首先基于標簽高階關系模型，評估樣本標簽集合屬于每一種頻繁項的可能性，如果標簽高階關系模型不能預測出樣本的標簽集合，說明該樣本具有的標簽間相關性并不強，則將問題轉換為多個獨立的二分類問題進行解決，從而兼顧標簽間多種可能的相關性。預測算法描述如下：

3 實驗結果與分析

3.1 實驗數據集

為了驗證本文算法的有效性，選取來自Mulan Library［21］庫中的2 組經典多標簽數據集進行實驗，多標簽數據集對應的名稱、領域、樣本數、特征數、標簽空間中標簽數等詳細信息如表1 所示。

表1 多標簽數據集統計信息Table 1 Multi-label dataset statistics

Emotions［22］數據集包含593 個標注了情感的歌曲樣本，每個樣本由72 個特征描述，即8 個韻律特征和64 個音色特征。每個樣本對應6 個情感標簽，每個標簽代表一個基于模型的歌曲情感聚類。

Scene［23］數據集包含2 407 個自然場景的圖片樣本，每個樣本由294 個特征描述，對應一個294 維的特征向量，具體的屬性向量生成過程可參見文獻［23］，標簽空間是6 種可能的自然場景。

3.2 實驗設置

實驗設置具體如下：

1）實驗平臺。實驗中所有代碼都由Python 編寫，模型基于sklearn 搭建。設備系統為Windows10，配備NVIDIA GEFORCE GTX 950M 顯卡，內存為16 GB。

2）數據預處理。本文算法對樣本進行預測需要找出樣本在訓練集上相似度最高的k個樣本，基于這k個樣本的標簽集預測測試樣本的標簽組合。為了度量樣本之間的相似性，本文采用樣本間的歐氏距離作為樣本相似性的度量標準，為了消除特征之間的量綱影響，對數據特征進行歸一化處理。

3）評價指標。本文算法可以直接預測出測試樣本的標簽集，因此，基于多標簽排序［24］的評價指標并不適用于本文算法，考慮到本文算法的特殊性，從多標簽分類層面對預測結果進行評估，采用Precision(P)、Recall(R)、F1-Measure(F1)［25］作為算法性能的評價指標。Precision、Recall 的計算依賴于分類結果的混淆矩陣，F1-Measure 的計算又是基于Precision、Recall。分類結果的混淆矩陣如表2 所示。

表2 分類結果的混淆矩陣Table 2 Confusion matrix of classification results

各評價指標的計算公式如下：

P指標用于衡量預測出的正樣本中確實是正樣本的比率，R指標用于衡量正樣本中有多少比例被預測出，F1 是P和R的調和平均，用于衡量算法在整體上的性能效果。

3.3 結果分析

3.3.1 本文算法與各基準方法性能比較

各方法在實驗數據集上的性能比較結果如表3、表4 所示。從表3、表4 可以看出，本文算法在2 個數據集上的F1 指標都取得了最優值，在Emotions 數據集上，本文算法的F1 比CC、LP、RAKEL、MLDF 分別提高1.4、5.8、1.4、6.6 個百分點，在Scene 數據集上，本文算法的F1 相比CC、LP 分別提升1.3 和8.4 個百分點。相較其他基準方法對標簽高階關系建模，本文算法通過數據挖掘來明確數據集本身固有的高階標簽關系并進行建模，其考慮標簽間真實存在的相關性，因此，取得了較好的分類性能。

表3 多標簽學習方法在Emotions 數據集上的性能比較Table 3 Performance comparison of multi-label learning methods on Emotions dataset

表4 多標簽學習方法在Scene 數據集上的性能比較Table 4 Performance comparison of multi-label learning methods on Scene dataset

3.3.2 關聯閾值和獨立閾值的有效性分析

為了驗證關聯閾值CT和獨立閾值IT的有效性，本文采用3 種策略分別進行實驗：

1）只使用關聯閾值對測試樣本進行預測。

2）只使用獨立閾值對測試樣本進行預測。

3）結合2 個閾值對測試樣本進行預測。

3 種策略的判別能力如表5、表6 所示。由表5、表6 可以看出，策略3 的分類性能優于策略1 和策略2。對比2 組實驗數據不難發現，在Emotions 數據集上，只使用關聯閾值就可以取得較好的分類性能，在Scene 數據集上，只使用關聯閾值則分類性能不理想。在Emotions 數據集上，從策略1 到策略3 分類性能提升不是很明顯，但是在Scene 數據集上，從策略1到策略3 的分類性能提升效果非常顯著。

表5 不同策略在Emotions 數據集上的性能比較Table 5 Performance comparison of different strategies on Emotions dataset

表6 不同策略在Scene 數據集上的性能比較Table 6 Performance comparison of different strategies on Scene dataset

出現上述2 種情況，最主要的原因是2 組數據集標簽間相關性的強弱不同。具體來說，Emotions 數據集上因為標簽間的相關性很強，測試樣本的標簽集總是以頻繁項的形式呈現，因此，通過關聯閾值預測就可以將絕大部分的測試樣本標簽集確定，剩余的樣本需借助獨立閾值去獲取樣本的標簽集，即從策略1 到策略3 分類效果的性能提升不是很明顯，驗證了本文對標簽高階關系建模的有效性。在Scene數據集上，由于標簽間的相關性較弱，存在挖掘出的頻繁項不能覆蓋所有標簽的情況，通過使用關聯閾值進行預測，該標簽的分類指標必然為0，將大幅影響整體分類效果。在實際的預測過程中，只有很少部分的測試樣本標簽集是頻繁項，值得注意的是，在數據集上雖然挖掘出頻繁項，但一種標簽組合是否屬于頻繁項由它在數據集上出現的頻數以及設置的閾值參數共同決定，在Scene 數據集上，頻繁項的個數很少，通過本文算法驗證了Scene 數據集標簽間的相關性較弱，對于測試樣本，大部分都采用策略2 完成標簽集的獲取，因此，從策略1 到策略3 分類效果有了很大的提升。

4 結束語

已有多標簽學習算法大多將多標簽學習問題轉化為多個獨立的二分類問題，以對每個標簽進行單獨求解，該過程通常忽略了標簽間的相關性。本文提出一種基于標簽相關性的多標簽學習K 近鄰算法，該算法充分挖掘標簽間的相關性，對標簽高階關系進行建模，基于標簽高階關系模型分析樣本的標簽集合，如果標簽高階關系模型不能預測出樣本的標簽集合，說明該樣本標簽間的相關性并不強，此時使用一階策略完成該樣本標簽集的預測工作，從而消除僅依靠單階或多階模型進行預測時存在的弊端。在2 個經典數據集上的實驗結果表明，該算法具有較高的F1-Measure 值，其能取得較好的分類效果。下一步將在確定對應于每個頻繁項或標簽的近鄰樣本時，采用不同大小的近鄰參數K，從近鄰樣本中提取出更為有效的信息來輔助分類過程，從而提高本文算法的分類性能。