基于字典學習的PU分類算法研究

廣東工業大學 劉芷菁

本文主要提出了一種基于字典學習的正例無標記學習（Positive and Unlabeled learning，PU學習）的分類方法。在PU學習中引入字典學習以此來構建原始輸入的新的特征表示，然后結合基于RankSVM的模型來優化分類器的性能。

在傳統的二分類問題中，通常是利用正樣本和負樣本來訓練分類器。但對于PU學習來說，則是利用正樣本和未標記樣本來訓練一個二元分類器。如今，PU學習在機器學習中是一個熱門的話題并且應用于多個領域，例如文檔分類、文本分類和信息檢索等。在文檔分類問題中，用戶通常會標記出他們所感興趣的文檔，以滿足他們的需求，但不會關注他們不感興趣的文檔，這是用戶常見的閱讀習慣。因此，我們往往可以獲得由用戶標記的文檔以及許多未標記的文檔。我們可以利用這些已標記的樣本和大量未標記的樣本進行訓練得到一個分類器，以此對樣本進行預測。

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

1 研究內容

為了解決PU學習的分類問題，首先我們會從未標記樣本中提取可靠的負樣本來組成負樣本集。接著，將提取的負樣本集和已標記的正樣本集作為字典學習的輸入，以此來生成輸入樣本的有辨別性的特征表示。然后，基于RankSVM模型來訓練一個分類器。對于RankSVM來說，其核心問題是將排序問題轉化為樣本對的分類問題。并且，RankSVM遵循正樣本的排序高于負樣本的排序的原則。但在PU學習中，由于未標記樣本是由正樣本和負樣本組成，我們很難將未標記樣本與正樣本或者負樣本來進行排序。為了能夠將未標記樣本也納入到模型的訓練中，本方法對未標記樣本引入了相似權重。相似權重可以用來衡量未標記樣本與正類和負類之間的相似性。

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

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

約束條件：

表1 具體實驗結果

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

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

通過迭代更新后，可以獲取最優的ω和P，因此對于任意一個新的樣本，有以下的得分函數 f：

將得分f(xi)與設置的最優閾值ψ進行比較可預測每個新樣本的標簽：

對于一個新樣本，若F(xi)，則為正類，否則為負類。

2 實驗結果

為了驗證本方法在PU分類中的性能，本方法會選取PU學習中常用的數據集作為實驗數據，并選取多種現有的算法進行對比實驗，將F1得分作為評估準則。

在PU學習中常用的數據集有20 Newsgroups、Reuters和WebKB。對于每一個數據集，選擇其中60%的樣本作為訓練集，其余作為測試集。對于每個數據集，我們選擇其中一個類別作為正類，其余類別作為負類。在正類中隨機選擇n%個樣本作為已標記的正樣本集PS，正類中的其余樣本以及其他類別的樣本作為未標記的樣本集US。因此，可以從20 Newsgroups、Reuters和WebKB分別獲取4個子樣本集。

為了充分說明本方法的有效性，本文將本方法與其他PU學習的方法進行了性能比較，以得分作為標準，具體實驗結果可參見表1所示。

由實驗結果可知，本方法的得分都比其他方法的得分高，這說明字典學習用于分類時可以大大提高的分類的性能。

結束語：在本文中，我們提出了一種基于字典學習的PU分類算法。本方法首先利用字典學習來產生具有區分度的特征表示。為了將未標記樣本納入到模型的訓練中，本方法基于RankSVM將相似權重結合起來，以此來訓練一個分類器。通過實驗表明，本方法的分類性能與其他方法相比有所提高。