盧勇全， 劉振丙,2， 顏振翔， 方旭升

(1.桂林電子科技大學(xué) 電子工程與自動化學(xué)院,廣西 桂林 541004；2.桂林電子科技大學(xué) 計算機與信息安全學(xué)院,廣西 桂林 541004)

偏標(biāo)記學(xué)習(xí)從本質(zhì)上看是屬于多類分類問題的特例。多類分類問題可以轉(zhuǎn)換為構(gòu)建多個二分類問題來解決。然而現(xiàn)有的一對多或一對一方式構(gòu)建二類基分類器的算法中，很少考慮各個類別樣本數(shù)目之間的極度不平衡問題，偏標(biāo)記學(xué)習(xí)在處理標(biāo)簽問題上已經(jīng)是個難題，加上類不平衡問題，則更加難以解決，且偏標(biāo)記樣本真實標(biāo)簽不可知，故該方法不能直接在偏標(biāo)記學(xué)習(xí)中使用。做交叉驗證時，有可能將類別少的數(shù)據(jù)集作為測試使用，從而導(dǎo)致此類別訓(xùn)練樣本缺失，若運用標(biāo)簽劃分數(shù)據(jù)集，則可能存在某類樣本數(shù)為0的情況，忽略此極有可能導(dǎo)致算法崩潰。如Lost[4]數(shù)據(jù)集中存在一類僅有4個樣本的數(shù)據(jù)，在算法中若不對此情況進行處理，會導(dǎo)致實驗失敗。鑒于此，提出一種KD樹集成偏標(biāo)記學(xué)習(xí)算法(ensemble K-dimension tree for partial label learning，簡稱PL-EKT)，將樣本候選標(biāo)簽所攜帶的信息和樣本特征綜合利用，構(gòu)建多個二分類樣本集，采用集成學(xué)習(xí)中Stacking的方法處理偏標(biāo)記學(xué)習(xí)問題。

1 相關(guān)工作

偏標(biāo)記學(xué)習(xí)的難度主要是由偏標(biāo)記數(shù)據(jù)集的偽標(biāo)簽造成的[7]，為此，學(xué)者們提出了一系列算法。最為直觀的方法是對偏標(biāo)記的偽標(biāo)簽進行操作，將樣本的偽標(biāo)簽去掉，也稱為消岐操作，即辨識消岐和平均消岐[8]。辨識消岐是將偏標(biāo)記的真實標(biāo)記作為隱變量，采用迭代的方式優(yōu)化內(nèi)嵌隱變量的目標(biāo)函數(shù)實現(xiàn)消岐[8]。平均消岐是賦予偏標(biāo)記對象的各個候選標(biāo)記相同的權(quán)重，通過綜合學(xué)習(xí)模型在各候選標(biāo)記上的輸出實現(xiàn)消岐[8]。在辨識消岐中，通過基于極大似然準(zhǔn)則的方法優(yōu)化參數(shù)，解決偏標(biāo)記學(xué)習(xí)問題。文獻[9]提出一種基于最大間隔偏標(biāo)記學(xué)習(xí)算法(PL-SVM)，通過模型在Si和非Si上的最大輸出差異進行優(yōu)化。文獻[10]提出了一種新的基于最大間隔的偏標(biāo)記學(xué)習(xí)算法(M3PL)，直接優(yōu)化真實標(biāo)記與其他標(biāo)記的差異。在平均消岐中，文獻[11]提出一種代表性的惰性學(xué)習(xí)算法PL-KNN，類似KNN算法，通過距離度量的方式，根據(jù)示例的K個近鄰樣本進行投票預(yù)測。文獻[12]提出了基于凸優(yōu)化的偏標(biāo)記學(xué)習(xí)算法CLPL，算法將問題轉(zhuǎn)化為多個二分類問題，通過在二類訓(xùn)練集上優(yōu)化特定的凸損失函數(shù)求解偏標(biāo)記學(xué)習(xí)問題。

在解決偏標(biāo)記學(xué)習(xí)問題上，也有非消岐策略的方法。如文獻[13]提出的編碼解碼策略的輸出糾錯編碼算法PL-ECOC，通過特定編碼和解碼方式實現(xiàn)二分類過程。在編碼階段，通過隨機生成的列編碼來劃分樣本正負集，從而構(gòu)建二分類器；在解碼階段，讓未見示例在二分類器上輸出特定長度的碼字，將最接近的類別作為測試樣本的預(yù)測輸出。PALOC算法[14]、CORD算法[15]通過集成多個分類器，運用模型投票的方法來解決偏標(biāo)記學(xué)習(xí)問題。

KD樹(K-dimension tree)是平衡二叉樹，通過利用已有數(shù)據(jù)對K維空間進行切分[16-17]。KD樹在進行檢索時，以目標(biāo)點為圓心，以目標(biāo)點到葉子節(jié)點樣本實例的距離為半徑，得到一個超球體，最近鄰的點一定在這個超球體內(nèi)部。然后返回葉子節(jié)點的父節(jié)點，檢查另一個子節(jié)點包含的超矩形體是否與超球體相交，若相交，就尋找是否有與該子節(jié)點更近的近鄰，有的話就更新最近鄰節(jié)點；若不相交，直接返回父節(jié)點，在另一個子樹繼續(xù)搜索最近鄰節(jié)點。當(dāng)回溯到根節(jié)點時，保存的最近鄰節(jié)點就是最終的最近鄰節(jié)點。

集成學(xué)習(xí)通過聯(lián)合幾個模型來提高機器學(xué)習(xí)效果[18]。與單一模型相比，這種方法可以很好地提升模型的預(yù)測性能。其中Stacking是一種通過元分類器或元回歸器來綜合幾個分類模型和回歸模型的集成學(xué)習(xí)技術(shù)?；Ｐ突谡麄€數(shù)據(jù)集進行訓(xùn)練，元模型再將基模型的輸出作為特征進行訓(xùn)練。

2 KD樹集成偏標(biāo)記學(xué)習(xí)

在訓(xùn)練階段，通過充分利用樣本的候選標(biāo)簽和樣本特征所隱藏的信息，將樣本分成正負類。其中，1表示正類，0表示負類。劃分正負類數(shù)據(jù)集后，由于偏標(biāo)記樣本屬多分類，一般情況下屬于某一類樣本的數(shù)量并不多，大部分是其他類別的樣本。在初級模型訓(xùn)練階段，為了使樣本數(shù)量均衡，以小的樣本數(shù)量為標(biāo)準(zhǔn)，允許在2倍內(nèi)波動，當(dāng)出現(xiàn)某一類樣本極少時，利用KD樹搜索找出特征相似的樣本進行補充，保證正負兩類樣本趨于均衡。完成數(shù)據(jù)集的劃分后，先訓(xùn)練出初級分類模型，再利用初級分類模型對樣本進行預(yù)測并投票，將初級分類器的預(yù)測值加入到原樣本中形成新樣本。運用集成學(xué)習(xí)的Stacking方法，再次進行分類模型的訓(xùn)練，最終完成模型的訓(xùn)練。PL-EKT算法實現(xiàn)過程如下。

輸入：D偏標(biāo)記樣本集

輸出：根據(jù)式(8)，返回x*的預(yù)測標(biāo)簽y*

1K：檢索KD的最近K個樣本

2x*：未見示例

3 輸出y*：樣本x*的預(yù)測標(biāo)簽

5 訓(xùn)練初級分類器Hab←β(D)

6 根據(jù)式(6)預(yù)測標(biāo)簽，根據(jù)式(7)形成新特征并加入

在預(yù)測階段，利用初級分類模型對未見樣本進行投票，將投票結(jié)果作為新特征加入未見示例中，最后將加入了新特征的未見示例進行最終預(yù)測。

按照標(biāo)簽1、0，根據(jù)

(1)

(2)

(3)

Dab={T(x1)∪T(x2)…∪T(xk)}

(4)

(5)

其中l(wèi)max和lmax為設(shè)置的樣本數(shù)目閾值范圍。

數(shù)據(jù)集均衡化過程如下：

1)根據(jù)式(1)劃分樣本；

2)根據(jù)式(2)處理劃分樣本集公共部分，構(gòu)建KD樹；

5)樣本為空檢測；

6)若劃分結(jié)果不滿足式(5)，則返回第2)步。

(6)

實現(xiàn)消岐操作。利用Hab構(gòu)建樣本新特征，

(7)

(8)

其中γ為平衡因子。

3 實驗

3.1 實驗設(shè)置

本次實驗分別在UCI人工數(shù)據(jù)集和真實數(shù)據(jù)集2類不同數(shù)據(jù)集上進行實驗。表2為2組人工UCI偏標(biāo)記數(shù)據(jù)集的特性，表3為4組真實偏標(biāo)記數(shù)據(jù)集的特性。

表2 UCI數(shù)據(jù)集特性

表3 真實數(shù)據(jù)集特性

3.2 實驗結(jié)果

在UCI數(shù)據(jù)集中，研究提出的算法與各類算法分別在r=1,2,3，步長p從0.1～0.7變化時的分類準(zhǔn)確率。采用10倍交叉驗證結(jié)果做顯著程度為0.05的成對t檢驗，實驗結(jié)果如圖1～3所示。

圖1 r=1時p取0.1～0.7的分類精度

圖2 r=2時p取0.1～0.7的分類精度

圖3 r=3時p取0.1～0.7的分類精度

通過觀察實驗結(jié)果，可得出如下結(jié)論：

1)在vehicle數(shù)據(jù)集上各算法魯棒性均較好，但在glasss數(shù)據(jù)集上，在不同參數(shù)下，各算法分類結(jié)果波動較大，魯棒性不足。

2)在vehicle數(shù)據(jù)集上，除了在個別步長時劣于PL-ECOC算法，PL-EKT算法性能優(yōu)于其他算法。

在真實數(shù)據(jù)集上，采用10倍交叉驗證結(jié)果做顯著程度為0.05的成對t檢驗。表4給出了各算法在真實數(shù)據(jù)集上分類精度。

表4 各算法在真實數(shù)據(jù)集上分類精度

從表4可看出：

1)在Lost數(shù)據(jù)集上，PL-EKT算法性能比其他3種算法表現(xiàn)好。

2)在MSRCv2數(shù)據(jù)集上，PL-EKT算法與PL-ECOC算法基本持平，但優(yōu)于其他算法。

3)在BirdSong和Soccer Play數(shù)據(jù)集上，PL-EKT算法劣于PL-ECOC算法，優(yōu)于其他算法。

PL-EKT偏標(biāo)記學(xué)習(xí)算法在2組UCI人工數(shù)據(jù)集和4組真實數(shù)據(jù)集上都具有較好的表現(xiàn)力。從整體上看，PL-EKT算法在UCI數(shù)據(jù)集中比其他算法分類精度高，且魯棒性相對較好；在真實數(shù)據(jù)集上，PL-EKT算法相比于其他算法也擁有較好的效果，僅在Birdsong數(shù)據(jù)集上劣于PL-ECOC算法。

4 結(jié)束語

為了充分利用候選標(biāo)記來劃分樣本，提出了KD樹集成偏標(biāo)記學(xué)習(xí)算法，通過KD樹均衡訓(xùn)練集，使得偏標(biāo)記學(xué)習(xí)算法有較好的泛化性能。實驗結(jié)果表明，該算法在真實數(shù)據(jù)集上有較好的表現(xiàn)。但同時也存在一些不足的地方，在UCI數(shù)據(jù)集Glass上算法的魯棒性不夠，劃分子數(shù)據(jù)集仍會存在樣本均衡的問題等，有待進一步改進。