一種KD樹集成偏標(biāo)記學(xué)習(xí)算法

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

1K：檢索KD的最近K個(gè)樣本

2x*：未見示例

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

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

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

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

按照標(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)樣本為空檢測(cè)；

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

(6)

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

(7)

(8)

其中γ為平衡因子。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

圖1 r=1時(shí)p取0.1～0.7的分類精度

圖2 r=2時(shí)p取0.1～0.7的分類精度

圖3 r=3時(shí)p取0.1～0.7的分類精度

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

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

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

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

表4 各算法在真實(shí)數(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í)數(shù)據(jù)集上都具有較好的表現(xiàn)力。從整體上看，PL-EKT算法在UCI數(shù)據(jù)集中比其他算法分類精度高，且魯棒性相對(duì)較好；在真實(shí)數(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í)算法有較好的泛化性能。實(shí)驗(yàn)結(jié)果表明，該算法在真實(shí)數(shù)據(jù)集上有較好的表現(xiàn)。但同時(shí)也存在一些不足的地方，在UCI數(shù)據(jù)集Glass上算法的魯棒性不夠，劃分子數(shù)據(jù)集仍會(huì)存在樣本均衡的問題等，有待進(jìn)一步改進(jìn)。