基于字典學(xué)習(xí)的PU分類(lèi)算法研究

廣東工業(yè)大學(xué) 劉芷菁

本文主要提出了一種基于字典學(xué)習(xí)的正例無(wú)標(biāo)記學(xué)習(xí)（Positive and Unlabeled learning，PU學(xué)習(xí)）的分類(lèi)方法。在PU學(xué)習(xí)中引入字典學(xué)習(xí)以此來(lái)構(gòu)建原始輸入的新的特征表示，然后結(jié)合基于RankSVM的模型來(lái)優(yōu)化分類(lèi)器的性能。

在傳統(tǒng)的二分類(lèi)問(wèn)題中，通常是利用正樣本和負(fù)樣本來(lái)訓(xùn)練分類(lèi)器。但對(duì)于PU學(xué)習(xí)來(lái)說(shuō)，則是利用正樣本和未標(biāo)記樣本來(lái)訓(xùn)練一個(gè)二元分類(lèi)器。如今，PU學(xué)習(xí)在機(jī)器學(xué)習(xí)中是一個(gè)熱門(mén)的話(huà)題并且應(yīng)用于多個(gè)領(lǐng)域，例如文檔分類(lèi)、文本分類(lèi)和信息檢索等。在文檔分類(lèi)問(wèn)題中，用戶(hù)通常會(huì)標(biāo)記出他們所感興趣的文檔，以滿(mǎn)足他們的需求，但不會(huì)關(guān)注他們不感興趣的文檔，這是用戶(hù)常見(jiàn)的閱讀習(xí)慣。因此，我們往往可以獲得由用戶(hù)標(biāo)記的文檔以及許多未標(biāo)記的文檔。我們可以利用這些已標(biāo)記的樣本和大量未標(biāo)記的樣本進(jìn)行訓(xùn)練得到一個(gè)分類(lèi)器，以此對(duì)樣本進(jìn)行預(yù)測(cè)。

盡管已經(jīng)提出了很多方法來(lái)解決PU學(xué)習(xí)的分類(lèi)問(wèn)題，但大多數(shù)方法都是將原始特征作為算法的輸入。眾所周知，字典學(xué)習(xí)可以從原始的訓(xùn)練樣本中構(gòu)建出有效的特征表示，以此提高分類(lèi)器的性能。我們可以將字典學(xué)習(xí)看成一種降維學(xué)習(xí)，即通過(guò)字典學(xué)習(xí)可以獲得降維數(shù)據(jù)，并且字典學(xué)習(xí)總是嘗試學(xué)習(xí)樣本背后的最簡(jiǎn)單特征，從而獲得樣本有效的特征表示。因此，字典學(xué)習(xí)也被廣泛應(yīng)用于分類(lèi)任務(wù)中。

1 研究?jī)?nèi)容

為了解決PU學(xué)習(xí)的分類(lèi)問(wèn)題，首先我們會(huì)從未標(biāo)記樣本中提取可靠的負(fù)樣本來(lái)組成負(fù)樣本集。接著，將提取的負(fù)樣本集和已標(biāo)記的正樣本集作為字典學(xué)習(xí)的輸入，以此來(lái)生成輸入樣本的有辨別性的特征表示。然后，基于RankSVM模型來(lái)訓(xùn)練一個(gè)分類(lèi)器。對(duì)于RankSVM來(lái)說(shuō)，其核心問(wèn)題是將排序問(wèn)題轉(zhuǎn)化為樣本對(duì)的分類(lèi)問(wèn)題。并且，RankSVM遵循正樣本的排序高于負(fù)樣本的排序的原則。但在PU學(xué)習(xí)中，由于未標(biāo)記樣本是由正樣本和負(fù)樣本組成，我們很難將未標(biāo)記樣本與正樣本或者負(fù)樣本來(lái)進(jìn)行排序。為了能夠?qū)⑽礃?biāo)記樣本也納入到模型的訓(xùn)練中，本方法對(duì)未標(biāo)記樣本引入了相似權(quán)重。相似權(quán)重可以用來(lái)衡量未標(biāo)記樣本與正類(lèi)和負(fù)類(lèi)之間的相似性。

假設(shè)X={x1,...,xm}代表訓(xùn)練樣本，PS和US分別代表正樣本集和未標(biāo)記樣本集，因此有X=PS + US。對(duì)于任意一個(gè)樣本xi(i=1,...,m)，它的樣本標(biāo)簽是yi(1, -1)。若yi=1，表示屬于正類(lèi)；若yi=-1，則表示xi屬于負(fù)類(lèi)。首先本方法會(huì)通過(guò)Spy技術(shù)和Rocchio技術(shù)分別從US中提取負(fù)樣本NS1和NS2，并將這兩種方法提取出來(lái)的負(fù)樣本的交集作為可靠的負(fù)樣本，即NS=NS1NS2。從US提取出可靠的負(fù)樣本后，可得到NS = US-NS。

對(duì)于任意樣本xi和xj，RankSVM旨在找到一個(gè)分類(lèi)函數(shù)：若xi具有較高的相關(guān)性而xj具有較低的相關(guān)性，則有F(xi)>F(xj)。接著引入分析字典P來(lái)獲得輸入樣本的具有區(qū)分性的特征表示。因此，將給定的輸入樣本xij(xij=xi-xj)作為分析字典P的輸入，以此獲得特征表示zij=Pxij。因此本方法可以定義為如下的優(yōu)化問(wèn)題：

約束條件：

表1 具體實(shí)驗(yàn)結(jié)果

其中xij=xi-xj, xik=xi-xk, xkj=xk-xj；D是合成字典，P分析字典；dv代表合成字典D的某一行；M是一個(gè)由相似權(quán)重組成的對(duì)角矩陣；G是一個(gè)矩陣，用來(lái)存儲(chǔ)xij, xik, xkj等新產(chǎn)生的樣本對(duì)。m-(xik)和m+(xkj)代表相似權(quán)重。對(duì)于任意一個(gè)樣本對(duì)xkj來(lái)說(shuō)，我們可以用以下的相似模型來(lái)表示：

m-(.)和m+(.)分別表示樣本對(duì)趨于正類(lèi)和負(fù)類(lèi)的相似性。一般有0≤ m-(.) ≤1和0≤ m+(.) ≤1。若{xkj, (0,1)}，則表示樣本對(duì)xkj屬于正類(lèi)；若{xkj, (1,0)}，則表示樣本對(duì)xkj屬于負(fù)類(lèi)。

通過(guò)迭代更新后，可以獲取最優(yōu)的ω和P，因此對(duì)于任意一個(gè)新的樣本，有以下的得分函數(shù) f：

將得分f(xi)與設(shè)置的最優(yōu)閾值ψ進(jìn)行比較可預(yù)測(cè)每個(gè)新樣本的標(biāo)簽：

對(duì)于一個(gè)新樣本，若F(xi)，則為正類(lèi)，否則為負(fù)類(lèi)。

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

為了驗(yàn)證本方法在PU分類(lèi)中的性能，本方法會(huì)選取PU學(xué)習(xí)中常用的數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，并選取多種現(xiàn)有的算法進(jìn)行對(duì)比實(shí)驗(yàn)，將F1得分作為評(píng)估準(zhǔn)則。

在PU學(xué)習(xí)中常用的數(shù)據(jù)集有20 Newsgroups、Reuters和WebKB。對(duì)于每一個(gè)數(shù)據(jù)集，選擇其中60%的樣本作為訓(xùn)練集，其余作為測(cè)試集。對(duì)于每個(gè)數(shù)據(jù)集，我們選擇其中一個(gè)類(lèi)別作為正類(lèi)，其余類(lèi)別作為負(fù)類(lèi)。在正類(lèi)中隨機(jī)選擇n%個(gè)樣本作為已標(biāo)記的正樣本集PS，正類(lèi)中的其余樣本以及其他類(lèi)別的樣本作為未標(biāo)記的樣本集US。因此，可以從20 Newsgroups、Reuters和WebKB分別獲取4個(gè)子樣本集。

為了充分說(shuō)明本方法的有效性，本文將本方法與其他PU學(xué)習(xí)的方法進(jìn)行了性能比較，以得分作為標(biāo)準(zhǔn)，具體實(shí)驗(yàn)結(jié)果可參見(jiàn)表1所示。

由實(shí)驗(yàn)結(jié)果可知，本方法的得分都比其他方法的得分高，這說(shuō)明字典學(xué)習(xí)用于分類(lèi)時(shí)可以大大提高的分類(lèi)的性能。

結(jié)束語(yǔ)：在本文中，我們提出了一種基于字典學(xué)習(xí)的PU分類(lèi)算法。本方法首先利用字典學(xué)習(xí)來(lái)產(chǎn)生具有區(qū)分度的特征表示。為了將未標(biāo)記樣本納入到模型的訓(xùn)練中，本方法基于RankSVM將相似權(quán)重結(jié)合起來(lái)，以此來(lái)訓(xùn)練一個(gè)分類(lèi)器。通過(guò)實(shí)驗(yàn)表明，本方法的分類(lèi)性能與其他方法相比有所提高。