陳永波，李巧勤，劉勇國

(電子科技大學 信息與軟件工程學院，四川 成都 610054)

0 引 言

多標簽分類[1-3]根據(jù)解決思路可分為算法轉換法和問題轉換法[4]。算法轉換法有多標簽可信度決策樹(multi-label credibility decision tree，ML-CDT)、多標簽k最近鄰(multi-label k-nearest neighbor，ML-KNN)、多標簽反向傳播(backpropagation for multi-label learning，BPMLL)等[5-7]。

問題轉換法有二元關聯(lián)(binary relevance，BR)、利用示例與特征分布的標簽特定特征算法(label-specific features by simultaneously exploring instance distributions and feature distributions, LETTER)、隨機子標簽集合(random k labelsets，RAkEL)等[8-10]。

多標簽分類任務，如文本分類，“政府”、“國家安全”和“選舉”等特征，區(qū)分政治和非政治文檔會提供信息。因此，標簽可能有自己特定特征，即類屬屬性。對于這類現(xiàn)象，Zhang等提出基于類屬屬性的多標簽分類算法(multi-label classification with label specific features，LIFT)，算法考慮標簽具有類屬屬性，提出新特征構造方法，產(chǎn)生新特征空間[11]。但LIFT算法在構造類屬屬性并生成新特征空間時，忽略數(shù)據(jù)間的相互作用，未同時利用樣本近鄰集合的特征和標簽信息，造成算法分類結果不佳。

針對LIFT算法的問題，本文提出基于引力模型的類屬屬性多標簽分類算法G-GMLIFT(global-gravitation model based label specific features)和L-GMLIFT(local-gravitation model based label specific features)，從全局和局部層面，通過引力模型，度量數(shù)據(jù)間的相互作用，同時利用樣本近鄰集合的特征和標簽信息，來提高分類性能。實驗結果表明，所提算法優(yōu)于對比算法，驗證了算法的有效性。

1 相關原理簡介

1.1 多標簽分類

1.2 引力模型

引力模型中多標簽數(shù)據(jù)集的數(shù)據(jù)粒子間的引力計算如下[12-14]

(1)

式中：Cj表示數(shù)據(jù)粒子j的相互作用系數(shù)。dF(i,j) 表示數(shù)據(jù)粒子i和j的距離。

引力模型將樣本i轉換為數(shù)據(jù)粒子i，記為 (xi,Yi,Ci)[13]，Ci表示相互作用系數(shù)，Ci越大，數(shù)據(jù)粒子i與其它數(shù)據(jù)粒子間的引力越大，以此反映數(shù)據(jù)粒子間的相互作用，Ci計算如下

(2)

式中：近鄰密度di表示數(shù)據(jù)粒子i的近鄰數(shù)據(jù)粒子的分布情況，值越大，近鄰中與數(shù)據(jù)粒子i具有相同標簽集的數(shù)據(jù)粒子越接近。近鄰權重wi表示數(shù)據(jù)粒子i的近鄰數(shù)據(jù)粒子對分類結果的貢獻程度，值越大，表示i的近鄰數(shù)據(jù)粒子越利于分類。

1.3 基于類屬屬性的多標簽分類算法

LIFT算法通過構建反映標簽特點的特定特征，以提高標簽分類的性能[11]。類屬屬性構建過程中，對于標簽lk，將原始訓練樣本劃分為正負類樣本Pk和Nk

Pk={xi|(xi,Yi)∈D,lk∈Yi}Nk={xi|(xi,Yi)∈D,lk?Yi}

(3)

ck=β×min(|Pk|,|Nk|)

(4)

式中： |·| 表示集合的大小，β∈[0,1] 表示控制聚類個數(shù)的參數(shù)。得到聚類中心，算法將d維空間X構造為2ck空間，方法如下

(5)

式中：d(,) 表示兩樣本間歐氏距離。

2 基于引力模型的類屬屬性多標簽分類算法

針對LIFT算法構建類屬屬性過程中未考慮數(shù)據(jù)間相互作用，基于引力模型提出G-GMLIFT和L-GMLIFT算法，從全局和局部計算相互作用系數(shù)，度量數(shù)據(jù)間的相互作用，利用近鄰樣本的特征和標簽信息，提高算法分類性能。

2.1 G-GMLIFT算法

G-GMLIFT算法分為兩步：①構造基于全局相互作用的類屬屬性空間；②形成基于全局相互作用的二元訓練集。

(1)基于全局相互作用的類屬屬性空間

G-GMLIFT算法使用全局相互作用系數(shù)G_Ci， 度量數(shù)據(jù)間的相互作用，計算如下

(6)

式中：全局近鄰密度G_di表示考慮所有訓練集樣本的前提下，數(shù)據(jù)粒子i的近鄰數(shù)據(jù)粒子的分布情況，值越大，近鄰中與數(shù)據(jù)粒子i具有相同標簽集的數(shù)據(jù)粒子越接近。全局近鄰權重G_wi表示在考慮所有訓練集樣本的前提下，數(shù)據(jù)粒子i的近鄰數(shù)據(jù)粒子對分類結果的貢獻程度，值越大，表示i的近鄰數(shù)據(jù)粒子越利于分類。G_di計算如下

(7)

式中：G_dF(i,j) 表示全局相互作用的數(shù)據(jù)粒子i和j的距離，N(i) 表示數(shù)據(jù)粒子i的近鄰，G_dL(i,j) 表示全局相互作用的數(shù)據(jù)粒子i和j標簽集間差異程度。G_dF(i,j) 采用異構重疊歐氏度量，計算如下[16]

(8)

當數(shù)據(jù)粒子為離散型數(shù)據(jù)時

(9)

當數(shù)據(jù)粒子為連續(xù)型數(shù)據(jù)時

(10)

F表示特征空間，xif表示數(shù)據(jù)粒子i的第f個特征，xjf表示數(shù)據(jù)粒子j的第f個特征， max(f) 和min(f) 分別表示特征f的最大特征值和最小特征值。根據(jù)異構重疊歐氏度量方法，計算數(shù)據(jù)粒子i與訓練集中其它數(shù)據(jù)粒子間距離，按照升序選取距離值最小的k個數(shù)據(jù)粒子作為數(shù)據(jù)粒子i近鄰N(i)。G_dL(i,j) 計算如下

(11)

式中：Yi和Yj表示數(shù)據(jù)粒子i和j的標簽集合，Δ表示對稱差，q表示標簽空間的大小。G_wi計算如下

(12)

(13)

(14)

(15)

全局近鄰權重G_wi計算后需進行歸一化處理。

G-GMLIFT算法中“全局”指在訓練集所有樣本中獲得樣本近鄰，并基于此計算G_di和G_wi。確定全局相互作用系數(shù)后，正負類樣本Pk和Nk計算如式(3)所示。

則基于全局相互作用系數(shù)的正負類樣本G_Pk和G_Nk

G_Pk=Pk·G_PCkG_Nk=Nk·G_NCk

(16)

式中：G_PCk和G_NCk分別表示正負類樣本Pk和Nk對應的全局相互作用系數(shù)，如式(6)所示。G_PCk和G_NCk不是分別計算，而是訓練集的所有樣本計算一次，得到每個樣本的全局相互作用系數(shù)后，正負類樣本Pk和Nk根據(jù)各自索引，確定對應的全局相互作用系數(shù)，即G_PCk和G_NCk。

ck=β×min(|G_Pk|,|G_Nk|)

(17)

式中： |·| 表示集合基數(shù)，β∈[0,1] 表示控制聚類個數(shù)的比率參數(shù)。獲得聚類中心后，將原始d維特征空間X映射到2ck空間，構造基于全局相互作用的類屬屬性空間，映射方法如下

(18)

構建基于全局相互作用的類屬屬性空間過程中，利用所有訓練集的特征和標簽信息，由此獲得相互作用系數(shù)，度量數(shù)據(jù)間相互作用。

(2)基于全局相互作用的二元訓練集

G-GMLIFT利用基于全局相互作用的類屬屬性空間，形成基于全局相互作用的二元訓練集，方法如下

G_Bk={G_Φk(xi),Yi(k)|(xi,Yi)∈D}

(19)

式中：如果lk屬于Yi，則Yi(k)=+1,lk不屬于Yi，則Yi(k)=-1。G_Bk是一個二元訓練集，任何一個二元分類器均可完成算法的訓練階段。在測試階段，給定一個樣本u，相關標簽集的預測方法如下

Y={lk|G_hk(G_Φk(u))>0, 1≤k≤q}

(20)

式中：G_hk表示在G_Bk上訓練過后的全局作用二元分類模型。

2.2 L-GMLIFT算法

本節(jié)提出G-GMLIFT的變體算法，即L-GMLIFT。與G-GMLIFT算法不同，L-GMLIFT使用局部相互作用系數(shù)，度量數(shù)據(jù)間的相互作用，計算如下

(21)

式中：L_di表示局部近鄰密度，計算方法與式(7)相同，L_wi表示局部近鄰權重，計算方法與式(12)相同。L-GMLIFT算法中“局部”是指在使用與G-GMLIFT相同的步驟即式(3)，獲得正負類樣本Pk和Nk后，再分別從正負類樣本Pk和Nk中，計算各自的近鄰集合，在此基礎上計算L_di和L_wi。

計算局部相互作用系數(shù)后，L-GMLIFT算法得到基于局部相互作用系數(shù)的正負類樣本L_Pk和L_Nk，計算方法如下

L_Pk=Pk·L_PCkL_Nk=Nk·L_NCk

(22)

式中：L_PCk和L_NCk，分別表示正負類樣本Pk和Nk所對應的局部相互作用系數(shù)，計算方法如式(21)所示。獲得基于局部相互作用系數(shù)的正負類樣本L_Pk和L_Nk后，L-GMLIFT算法與G-GMLIFT算法流程相同，避免重復，不做敘述。

2.3 算法偽代碼

由2.1節(jié)和2.2節(jié)可以發(fā)現(xiàn)，G-GMLIFT算法和L-GMLIFT算法的不同之處，在于求解近鄰集合的樣本范圍。G-GMLIFT算法是在所有樣本中求解近鄰集合獲得全局相互作用系數(shù)。L-GMLIFT算法是分別在正負類樣本中求解近鄰集合，獲得局部相互作用系數(shù)。考慮兩種算法的過程大部分相同，此處僅給出G-GMLIFT算法的偽代碼，如算法1所示。

算法1：G-GMLIFT算法偽代碼

Y=G-GMLIFT(D,β,σ)

輸入：

多標簽訓練集D

控制簇中心個數(shù)的比率參數(shù)β

二元分類器σ

未知樣本u

輸出：

未知樣本u的預測標簽集Y

過程：

(1)根據(jù)式(6)得到全局相互作用系數(shù)G_PCk和G_NCk

(2) for k=1 to q do

(3) 根據(jù)式(3)， 計算正負類樣本Pk和Nk

(4) 根據(jù)式(16)， 得到基于全局相互作用系數(shù)的正負類樣本G_Pk和G_Nk

(5) 根據(jù)式(17)設定簇中心數(shù)目， 在G_Pk和G_Nk上進行Kmeans聚類， 分別得到ck個聚類中心

(6) 根據(jù)式(18)， 計算標簽lk的映射G_Φk

(7) end for

(8) for k=1 to q do

(9) 根據(jù)式(19)，計算二元訓練集G_Bk

(10) 在Bk上應用二元分類器σ， 得到訓練后的全局作用二元分類模型G_hk

(11) end for

(12) 根據(jù)式(20)，得到預測的標簽集Y

算法1給出了G-GMLIFT算法的完整步驟。G-GMLIFT首先計算全局相互作用系數(shù)G_PCk和G_NCk(第(1)行)；再為每個標簽構建其對應的類屬屬性(第(2)～(7)行)；基于已經(jīng)構建的類屬屬性訓練出q個二元分類器，得到分類模型(第(8)～(11)行)；最后，根據(jù)分類模型去預測未知樣本，得到預測的標簽集(第(12)行)。

3 實 驗

本文通過6個數(shù)據(jù)集進行實驗驗證，以評估G-GMLIFT和L-GMLIFT算法性能。仿真實驗基于Win 10操作系統(tǒng)，處理器為Intel (R)，3.30 GHz，內存為8 GB的PC電腦開展，通過MATLAB語言編程實現(xiàn)。

3.1 數(shù)據(jù)集

為驗證所提算法的有效性，選取6個多標簽數(shù)據(jù)集，具體信息見表1。

3.2 實驗設置

仿真實驗均采用10重交叉驗證，實驗運行10次。實驗的參數(shù)設置，參照LIFT算法[11]。G-GMLIFT和L-GMLIFT算法的最近鄰居數(shù)量設定為10，控制簇中心個數(shù)的比率參數(shù)β設定為0.1，評價指標分別為Hamming Loss(漢明損失)、One-Error(1-錯誤率)、Ranking Loss(排序損

表1 數(shù)據(jù)集

失)、Average Precision(平均精確度)，使用LIBSVM作為二元分類器[17]。

本文算法與BR[8]、BPMLL[7]、ML-KNN[6]、BRkNN[18]、CLR[19]、IBLR-ML[20]、RAkEL[10]、LIFT[11]、LSFCC[21]共9種算進行對比。對比算法皆使用對應文中所給出的配置信息進行實驗。

3.3 實驗結果與分析

表2～表5為11種算法在6個數(shù)據(jù)集上的實驗結果，其中↓(↑)表示結果值越小(大)，算法的分類性能越好。此外，加粗表示性能最好的算法結果。

表2～表5的實驗結果可見，對于評價指標Hamming Loss和One-Error，G-GMLFIT和L-GMLIFT算法在6個數(shù)據(jù)集上進行實驗，其中5個數(shù)據(jù)集上達到最優(yōu)，1個數(shù)據(jù)集上達到次優(yōu)。對于評價指標Ranking Loss和Average Precision，G-GMLFIT和L-GMLIFT算法在6個數(shù)據(jù)集上進行實驗，全部達到最優(yōu)。

G-GMLFIT和L-GMLIFT在大部分數(shù)據(jù)集的指標上都存在明顯優(yōu)勢，主要原因為LIFT及其它多標簽分類算法未考慮數(shù)據(jù)間的相互作用，沒有同時充分利用近鄰集合的特征和標簽信息。G-GMLFIT和L-GMLIFT算法計算相互作用系數(shù)，以度量數(shù)據(jù)之間的相互作用，同時利用樣本近鄰集合的特征和標簽信息，并將其加入到類屬屬性的構造過程，可以提高分類的性能。

對于G-GMLIFT和L-GMLIFT算法，在所有數(shù)據(jù)集上，G-GMLIFT達到最優(yōu)的次數(shù)為10，而L-GMLIFT算法達到最優(yōu)的次數(shù)為13。主要原因是L-GMLIFT算法在同類樣本中，即同是正類或同是負類樣本中尋找最近鄰，同類樣本所包含的樣本性質相似，而G-GMLIFT算法是在所有樣本中尋找最近鄰，既包含同類也包含不同類樣本，不同類的樣本所包含樣本的性質存在差異。

4 結束語

本文針對基于類屬屬性的多標簽分類算法LIFT，在類屬屬性的構建過程中，未考慮數(shù)據(jù)間的相互作用的問題，提出了基于引力模型的多標簽分類算法G-GMLIFT和L-GMLIFT算法。所提算法分別從全局和局部層面，計算

表2 Hamming Loss的實驗結果

表3 One-Error的實驗結果

表4 Ranking Loss的實驗結果

表5 Average Precision的實驗結果

相互作用系數(shù)，來度量數(shù)據(jù)之間的相互作用，同時利用樣本近鄰集合的特征和標簽信息，并將其加入到類屬屬性的構造過程，以提高分類的性能。實驗結果表明，所提算法與LIFT算法及其它標簽分類算法相比，分類性能有所提升。

后續(xù)的工作中，將考慮在構建類屬屬性的同時，利用特征選擇方法，降低特征空間的冗余信息，進一步提升算法的分類性能。