馬毓敏，王士同

江南大學(xué) 人工智能與計(jì)算機(jī)學(xué)院，江蘇 無錫 214122

1 引言

對(duì)于PU（positive-unlabeled）分類[1-2]問題，訓(xùn)練樣例集中的正例樣本相對(duì)比較容易獲得，而反例樣本的獲得比較困難，例如醫(yī)療診斷、地震監(jiān)測、生物信息學(xué)，在這些領(lǐng)域僅能觀測到一些標(biāo)記為正例的樣本以及大量可能包含正例樣本和負(fù)例樣本的未標(biāo)注樣本。為了使分類器的分類精度較高，反例樣本集合應(yīng)該是無偏的，即反例樣本集合應(yīng)該包含非正例的其他所有類別。因此，人們轉(zhuǎn)而研究基于正例和未標(biāo)注樣本的學(xué)習(xí)，其中未標(biāo)注樣例集合數(shù)量通常遠(yuǎn)遠(yuǎn)大于標(biāo)記的正例樣本數(shù)目。

解決PU 分類問題的傳統(tǒng)方法是簡單地將這些既包含正例樣本又包含負(fù)例樣本的數(shù)據(jù)視為負(fù)例樣本，這可能導(dǎo)致解決方案有偏差。為了減輕這種偏差，提出了幾種方法。Wang 等[3]稱PU 學(xué)習(xí)為部分監(jiān)督學(xué)習(xí)，提出使用間諜（spy）技術(shù)選擇可靠負(fù)例，利用期望最大化（expectation maximum，EM）和樸素貝葉斯（naive Bayes，NB）分類器的S-EM（spy-expectation maximum）實(shí)現(xiàn)分類；Liu 等[4]提出基于聚類的方法進(jìn)行分類，通過對(duì)正例進(jìn)行聚類，選擇不屬于任何簇的未標(biāo)注樣本作為可靠負(fù)例樣本，迭代訓(xùn)練SVM（support vector machine）；Xu 等[5]分別從正例和未標(biāo)注樣本中隨機(jī)抽取相同數(shù)量的樣本作為初始訓(xùn)練集，用于構(gòu)造SVM，將距離分割平面最遠(yuǎn)的未標(biāo)注樣本作為負(fù)例，通過自訓(xùn)練得到分類器。實(shí)驗(yàn)表明，未標(biāo)注樣本的利用能提高預(yù)測效果，但選擇初始訓(xùn)練集的方法會(huì)影響訓(xùn)練效果。Park 等[6]提出基于K-means 和投票機(jī)制的可靠負(fù)例選擇方法（reliable negative selection method based onK-means voting mechanism，SemiPU-clus）及關(guān)系預(yù)測框架，解決異質(zhì)信息網(wǎng)絡(luò)中的關(guān)系預(yù)測問題，性能優(yōu)于將無鏈接節(jié)點(diǎn)對(duì)完全視作負(fù)例的方法，但預(yù)測效果易受聚類結(jié)果影響；Sakai等[7]從理論上推導(dǎo)了PU 和半監(jiān)督AUC（area under receiver operating characteristic curve）優(yōu)化方法的泛化誤差范圍，提出了不依賴于數(shù)據(jù)分布的強(qiáng)大分布假設(shè)，僅基于正例和未標(biāo)注數(shù)據(jù)的AUC 優(yōu)化方法，然后將其與有監(jiān)督的AUC 優(yōu)化方法相結(jié)合擴(kuò)展到半監(jiān)督學(xué)習(xí)，再次證明了無標(biāo)簽數(shù)據(jù)有助于在沒有限制性分布假設(shè)的情況下以最佳參數(shù)收斂率來降低泛化誤差的上限，但對(duì)于新數(shù)據(jù)層出不窮的時(shí)代，其算法不適用于增量學(xué)習(xí)[8-9]；Ren 等[10]提出最大化AUC 框架揭露了PU 問題下將所有未標(biāo)注樣本視為負(fù)例樣本最大化AUC 與已知正負(fù)例分類情況下最大化AUC 線性相關(guān)，徹底擺脫了對(duì)未標(biāo)注樣本的負(fù)例選擇，但是其算法需要多次迭代增加了復(fù)雜度且算法不適用于增量學(xué)習(xí)。

為解決分類效果，本文提出了核最大化AUC 算法（kernel max AUC，KMAUC），一個(gè)基于AUC 的利用核函數(shù)實(shí)現(xiàn)高維映射的PU 學(xué)習(xí)框架，其中AUC 度量[11-12]用于指導(dǎo)學(xué)習(xí)過程。相比于傳統(tǒng)PU 分類算法需要經(jīng)過多次迭代才能求出局部最優(yōu)解，本文提出的KMAUC 算法具有可解析解，可以實(shí)現(xiàn)快速計(jì)算最大化AUC 評(píng)估值，在追求分類效果的同時(shí)兼顧了算法的復(fù)雜度，增強(qiáng)了算法的實(shí)用性。

針對(duì)傳統(tǒng)PU 分類問題對(duì)于增加數(shù)據(jù)集時(shí)，往往需要把新數(shù)據(jù)集和已有的數(shù)據(jù)集合并成更大規(guī)模的數(shù)據(jù)集，通過重新學(xué)習(xí)來發(fā)現(xiàn)整個(gè)數(shù)據(jù)集的分類，不具有增量學(xué)習(xí)的能力，僅適用于整批處理的方式，不能有效地處理不斷增加的數(shù)據(jù)集序列的問題，現(xiàn)有的方法提出了基于K鄰近域的增量算法[13]，但無法保證鄰域矩陣的連續(xù)性，還提出了基于K鄰近域的最小生成樹算法[14]，通過節(jié)點(diǎn)的更新來適應(yīng)新增點(diǎn)的加入，雖然保證了鄰域矩陣的連續(xù)，但節(jié)點(diǎn)的更新仍然需要大量的計(jì)算。針對(duì)此問題，本文進(jìn)一步提出了增量核最大化AUC 算法（increment kernel max AUC，IKMAUC），把新來的觀測數(shù)據(jù)融合到以前所獲得的信息中去，快速計(jì)算隱藏在高維空間樣本，不必重復(fù)計(jì)算原有的數(shù)據(jù)，實(shí)現(xiàn)快速增量學(xué)習(xí)。

綜上所述，本文提出的IKMAUC 算法具有兩大優(yōu)點(diǎn)：（1）避免了多重迭代的麻煩，從而實(shí)現(xiàn)快速計(jì)算；（2）增加訓(xùn)練樣本時(shí)還可以進(jìn)行增量計(jì)算，通過直接計(jì)算新增樣本的高維特征空間分布，避免對(duì)原始樣本的高維特征空間分布重新求解，利用Sherman-Morrison 公式對(duì)新增樣本數(shù)據(jù)的模型進(jìn)行迭代更新達(dá)到快速訓(xùn)練的效果。

2 最大化AUC

2.1 AUC 指標(biāo)

AUC 是衡量二分類模型優(yōu)劣的一種評(píng)價(jià)指標(biāo)，表示正例排在負(fù)例前面的概率。其他評(píng)價(jià)指標(biāo)有精確度、準(zhǔn)確率、召回率，而AUC 比這三者更為常用。因?yàn)橐话阍诜诸惸Ｐ椭校A(yù)測結(jié)果都是以概率的形式表現(xiàn)，如果要計(jì)算準(zhǔn)確率，通常都會(huì)手動(dòng)設(shè)置一個(gè)閾值來將對(duì)應(yīng)的概率轉(zhuǎn)化成類別，這個(gè)閾值也就很大程度上影響了模型準(zhǔn)確率的計(jì)算。不妨舉一個(gè)極端的例子：一個(gè)二類分類問題一共100 個(gè)樣本，其中99 個(gè)樣本為負(fù)例，1 個(gè)樣本為正例，在全部判負(fù)的情況下準(zhǔn)確率將高達(dá)99%，而這并不是希望的結(jié)果，在醫(yī)療檢測、地震監(jiān)測等情況中，往往就是這極少數(shù)的數(shù)據(jù)起著至關(guān)重要的作用。從準(zhǔn)確率上看模型的性能反應(yīng)極差，而AUC 能很好描述模型整體性能的高低。這種情況下，模型的AUC 值將等于0。AUC 越大代表模型的性能越好。AUC度量標(biāo)準(zhǔn)被定義為[15]：

其中，f（x）=wTx是評(píng)分函數(shù)，向量w參數(shù)化評(píng)分函數(shù)，xi與xj分別表示正例樣本、未標(biāo)注樣本特征向量。X+和X-分別表示正例樣品和負(fù)例樣品的分布，|X+|與|X-|分別表示正例和負(fù)例的樣本數(shù)。Ι（·）為指示函數(shù)，參數(shù)為真時(shí)其值為1，否則為0。AUC 反映了隨機(jī)抽取一個(gè)正例樣本的評(píng)分值大于隨機(jī)抽取一個(gè)負(fù)樣本的評(píng)分值的概率。

2.2 最大化PU 分類的AUC 公式

PU 問題無法直接將AUC 作為目標(biāo)函數(shù)，因?yàn)镻U 問題中沒有負(fù)標(biāo)簽，解決這個(gè)問題可以盲目地將所有未標(biāo)注的樣品視為負(fù)例樣品，稱為Blind AUC（BAUC），且BAUC 與AUC 之間的關(guān)系為（證明詳見參考文獻(xiàn)[10]）：

其中，π是正例樣本的百分比。

這個(gè)公式表明BAUC 線性地取決于AUC，最大化BAUC 就是最大化AUC。由于AUC 為不連續(xù)且非凸函數(shù)，因此在實(shí)際應(yīng)用時(shí)常常使用代理函數(shù)作為近似。典型的代理函數(shù)包括平方損失函數(shù)l（f）=（1-f）2（如OPAUC（one-pass AUC）[16]）、對(duì)數(shù)損失函數(shù)l（f）=ln（1+e-f）（如RankNet[17]）和指數(shù)損失函數(shù)l（f）=e-f（如RankBoost[18]）等?，F(xiàn)有的研究表明：平方損失函數(shù)、指數(shù)損失函數(shù)和對(duì)數(shù)損失函數(shù)等對(duì)AUC 優(yōu)化具有一致性。本文將使用平方損失函數(shù)，將評(píng)分函數(shù)f（x）=wTx帶入損失函數(shù)得：

其中，α＞0 是L2 正則化參數(shù)，是正則項(xiàng)，避免造成過擬合。式（2）具有兩個(gè)優(yōu)點(diǎn)：（1）最小二乘損失函數(shù)對(duì)AUC 優(yōu)化具有一致性；（2）由于其一階導(dǎo)數(shù)連續(xù)可以得到解析解。

2.3 最大化AUC 算法

本節(jié)介紹2.2 節(jié)提出的式（2）的優(yōu)化求解方式，一個(gè)很自然的想法是應(yīng)用最小二乘法，避免了多次迭代的繁雜，直接得到具有優(yōu)良特性的估計(jì)量且計(jì)算比較方便。為方便書寫，令式（2）為目標(biāo)函數(shù)L，把w看作是L的函數(shù)，通過最小化L確定這個(gè)函數(shù)就變成了一個(gè)求極值的問題。最大化AUC 公式的優(yōu)化過程如下：

L對(duì)w這個(gè)待估參數(shù)的偏導(dǎo)數(shù)：

由以上推導(dǎo)可以看出，通過直接對(duì)目標(biāo)函數(shù)求偏導(dǎo)可以直接得到w的解析解，帶入評(píng)分函數(shù)從而應(yīng)用于PU 分類中。

2.4 核最大化AUC 算法（KMAUC）

由于現(xiàn)實(shí)中數(shù)據(jù)集往往存在于低維空間不是線性可分的，最大化AUC 算法的分類效果并不理想，為了方便將不能用線性分割的數(shù)據(jù)轉(zhuǎn)化成可以線性分割的數(shù)據(jù)，只需將低維空間上的點(diǎn)映射到高維空間上就可以實(shí)現(xiàn)線性可分，在特征空間的線性運(yùn)算即為對(duì)應(yīng)原輸入空間的非線性算法。低維空間轉(zhuǎn)化為高維空間如圖1 所示。

Fig.1 Feature mapping圖1 特征映射

左面的圖為原空間，右面的圖為映射后的空間，從圖中也可以看出來，左面圖要用一個(gè)橢圓才能將兩個(gè)類別分割開來，而右面的圖用一個(gè)超平面就可以分割開，也如圖上的共識(shí)所示，原空間點(diǎn)左邊為（x1，x2），經(jīng)過某個(gè)函數(shù)或者某種計(jì)算方法，轉(zhuǎn)化為特征空間上點(diǎn)坐標(biāo)為（z1，z2，z3），因此將低維空間轉(zhuǎn)化到高維空間大概率可以對(duì)其中的點(diǎn)進(jìn)行線性分割。對(duì)于生活中觀察到的數(shù)據(jù)也是類似，若原始空間是有限維，即屬性數(shù)有限，那么一定存在一個(gè)高維特征空間使樣本線性可分。

本文提出了KMAUC 算法，利用核映射[19]φ將數(shù)據(jù)集從原始空間映射到高維空間，使得這個(gè)樣本在這個(gè)特征空間內(nèi)線性可分，解決數(shù)據(jù)集不是線性可分的情況。

由于高維特征空間樣本可能是無限維的，為了顯示地表示高維特征空間的樣本，可以借助核矩陣把高維特征空間的內(nèi)積運(yùn)算轉(zhuǎn)換為原始輸入空間中的核函數(shù)的計(jì)算求解，這種核函數(shù)技術(shù)不僅可以產(chǎn)生新的非線性算法，而且可以改進(jìn)一些傳統(tǒng)線性處理算法。核矩陣表示為：

其中，k（xi，xj）=＜φ（xi），φ（xj）＞，m為樣本數(shù)。

對(duì)核矩陣K做特征值分解（eigenvalue decomposition），K=VΛVT，其中Λ=diag（λ1，λ2，…，λm）為特征值構(gòu)成的對(duì)角矩陣，V為特征向量矩陣，可以得到高維特征空間的內(nèi)積，高維特征空間φ（X）可表示為：

高維特征空間中w的解析解為：

最后，KMAUC 算法的輸出函數(shù)為：

以上推導(dǎo)將最大化AUC 應(yīng)用到非線性數(shù)據(jù)集，在真實(shí)數(shù)據(jù)集上可以取得更好的效果。

2.4.1 算法過程

KMAUC 算法過程如下：

2.4.2 時(shí)間復(fù)雜度

KMAUC 算法的時(shí)間復(fù)雜度[20]主要分為兩步，分別對(duì)應(yīng)于算法過程的步驟1（計(jì)算高維特征空間樣本坐標(biāo)）與步驟2（計(jì)算權(quán)重w）。

步驟1計(jì)算高維特征空間樣本坐標(biāo)的時(shí)間復(fù)雜度主要分為兩步，分別對(duì)應(yīng)算法過程的步驟1.2、步驟1.3。在步驟1.2 中，若l為輸入樣本點(diǎn)維數(shù)，m為輸入樣本數(shù)，計(jì)算核矩陣需要進(jìn)行m2次的迭代，每次迭代的時(shí)間復(fù)雜度為O（l），則總的時(shí)間復(fù)雜度為O（lm2）；在步驟1.3 中，通常情況下對(duì)于m×m維核矩陣特征值分解的時(shí)間復(fù)雜度為O（m3）。

步驟2計(jì)算權(quán)重w的時(shí)間復(fù)雜度主要分兩步：（1）計(jì)算AN需要N次向量乘積的迭代，每次迭代的時(shí)間復(fù)雜度為O（m2），總的時(shí)間復(fù)雜度為O（m2N） ；（2）計(jì)算的時(shí)間復(fù)雜度為O（m3）。

綜上所述，KMAUC算法的時(shí)間復(fù)雜度為O（m2N+m3+lm2），通常情況下，N＞＞m＞＞l，因此KMAUC 算法的時(shí)間復(fù)雜度為O（m2N）。

3 增量學(xué)習(xí)

KMAUC 算法對(duì)模型更新時(shí)需要重新代入所有數(shù)據(jù)，不能很好地應(yīng)用在實(shí)際場景中。針對(duì)這一問題，增量學(xué)習(xí)方式應(yīng)運(yùn)而生。增量學(xué)習(xí)是指一個(gè)學(xué)習(xí)系統(tǒng)能不斷地從新樣本中學(xué)習(xí)新的知識(shí)，并能保存大部分以前已經(jīng)學(xué)習(xí)到的知識(shí)，減少計(jì)算量加速學(xué)習(xí)過程。

3.1 計(jì)算高維特征空間的增量樣本

隨著樣本個(gè)數(shù)的增加，核矩陣有所改變，新增核矩陣區(qū)域數(shù)據(jù)的出現(xiàn)會(huì)破壞原有核矩陣特征值分解結(jié)構(gòu)，若是直接對(duì)高維特征空間樣本特征值分解，其時(shí)間復(fù)雜度會(huì)隨著樣本個(gè)數(shù)的增加呈指數(shù)增加。為解決這一問題，本文利用新來的觀測數(shù)據(jù)子集包含的幾何信息融合到以前所獲得的信息中去，快速發(fā)現(xiàn)隱藏在高維空間的分布，保留原先計(jì)算出的特征空間樣本情況下，巧妙計(jì)算出新增數(shù)據(jù)，大大縮減計(jì)算時(shí)間，增量樣本計(jì)算方式如下：

第一次新增樣本時(shí)，樣本總數(shù)達(dá)到（m+1）個(gè)，核函數(shù)矩陣Km+1是（m+1）×（m+1）的方陣，它比初始核函數(shù)矩陣Km多一行一列，比較Km+1和Km的元素，可以看到Km+1能寫為如下分塊矩陣的形式：

往后再增加樣本時(shí)，都通過Schur Complement公式用相同的方法簡便運(yùn)算。

3.2 計(jì)算增量后權(quán)重w′

增量后權(quán)重w′可以保留增量前計(jì)算w所計(jì)算的數(shù)值A(chǔ)N與b，對(duì)于新增樣本部分發(fā)生的變化用ΔA與Δb表示，帶入計(jì)算表示為：

|X+|與|X|表示每次增量前訓(xùn)練樣本正例與未標(biāo)注樣本數(shù)，n+與n表示每次增量的正例與未標(biāo)注樣本數(shù)。

由于（AN+ΔA）-1的時(shí)間復(fù)雜度會(huì)隨著樣本個(gè)數(shù)的增加，計(jì)算所需的時(shí)間呈指數(shù)增加，本文利用Sherman-Morrison 公式迭代求解，快速計(jì)算矩陣的逆。具體求解過程如下：

3.3 核最大化AUC 公式算法（IKMAUC）

3.3.1 算法過程

IKMAUC 算法過程如下：

3.3.2 時(shí)間復(fù)雜度

IKMAUC 算法的時(shí)間復(fù)雜度主要分為兩步，分別對(duì)應(yīng)于算法過程的步驟1（計(jì)算增量樣本在高維特征空間的分布）與步驟2（計(jì)算增量后權(quán)重w′）。

步驟1計(jì)算高維特征空間樣本坐標(biāo)的時(shí)間復(fù)雜度主要分為三步，分別對(duì)應(yīng)算法過程的步驟1.2、步驟1.3 和步驟1.4。步驟1.2 計(jì)算加入新增樣本核矩陣可以保留之前m×m維核矩陣計(jì)算結(jié)果，只需要進(jìn)行（m+n++n）2-m2次迭代，每次迭代的時(shí)間復(fù)雜度為O（l），則總的時(shí)間復(fù)雜度化簡為O（l（n++n）2-2mnn+l）；步驟1.3 計(jì)算新增樣本高維空間分布的時(shí)間復(fù)雜度第一次主要求[φ（Xm）T]-1為O（m3），往后每次的時(shí)間復(fù)雜度主要為（m+n+n+）×（m+n+n+）維矩陣與（m+n+n+）×1 維的向量相乘，為O（m+n+n+）2，總的時(shí)間復(fù)雜度為O（（n+n+）（m+n+n+）2），由于n+n+＜＜m，因此計(jì)算新增樣本高維空間分布的時(shí)間復(fù)雜度為O（m3）。

步驟2計(jì)算增量后權(quán)重w′的時(shí)間復(fù)雜度主要有兩步，分別對(duì)應(yīng)算法過程的步驟2.2 和步驟2.3。步驟2.2 計(jì)算m×m維矩陣的時(shí)間復(fù)雜度為O（m3）；步驟2.3 計(jì)算求解需要經(jīng)過N′次迭代，每次迭代的時(shí)間復(fù)雜度主要為（m+n+n+）×（m+n+n+）維矩陣與（m+n+n+）×1 維的向量相乘，為O（m+n+n+）2，總的時(shí)間復(fù)雜度為O（N′（m+n+n+）2）。

綜上所述，IKMAUC 算法的時(shí)間復(fù)雜度為O（N′（m+n+n+）2+m3+l（n++n）2-2mnn+l），增量學(xué)習(xí)通常情況下，N＞＞N′＞＞m＞＞l＞＞n或n+，因此IKMAUC算法的時(shí)間復(fù)雜度為O（N′（m+n+n+）2）。而不做增量學(xué)習(xí)重新求解的時(shí)間復(fù)雜度為O（m2（N+N′）），可以看到具有增量學(xué)習(xí)的IKMAUC算法大大減少了訓(xùn)練時(shí)間。

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

本章進(jìn)行實(shí)驗(yàn)分析，通過與其他現(xiàn)有先進(jìn)算法對(duì)比，以驗(yàn)證所提出的KMAUC 算法與IKMAUC 算法的有效性。在實(shí)驗(yàn)過程中，訓(xùn)練集內(nèi)75%的隨機(jī)選擇的正例樣本數(shù)據(jù)是算法已知的，剩下的25%正例樣本與負(fù)例樣本歸為未標(biāo)注樣本。

驗(yàn)證所提出的KMAUC 算法比較涉及6種算法：選用高斯核函數(shù)的理想SVM（正負(fù)例樣本的真實(shí)的標(biāo)簽是已知的）、單類SVM（流行的分類算法）、Biased SVM（BSVM）、文獻(xiàn)[21]提出的先進(jìn)算法ERR（error minimization formulation）、最大化AUC 算法（本文2.2 節(jié)提出的算法）、本文提出的完整最大化核AUC 算法（KMAUC）。理想情況下的SVM 作為參考進(jìn)行比較，注意在理想SVM 情況下，所有樣本標(biāo)記全部已知，無需分為75%正例樣本以及剩下未標(biāo)注樣本。它是評(píng)估其他算法性能的標(biāo)準(zhǔn)。

為了更好評(píng)估算法的性能，實(shí)驗(yàn)使用機(jī)器學(xué)習(xí)領(lǐng)域中具有代表性的數(shù)據(jù)集UCI 進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)所用數(shù)據(jù)集如表1 所示。

Table 1 Introduction to datasets表1 數(shù)據(jù)集介紹

由于在機(jī)器學(xué)習(xí)領(lǐng)域中，不同評(píng)價(jià)指標(biāo)（即特征向量中的不同特征就是所述的不同評(píng)價(jià)指標(biāo)）往往具有不同的量綱和量綱單位，這樣的情況會(huì)影響到數(shù)據(jù)分析的結(jié)果，在數(shù)據(jù)利用核函數(shù)映射到高維空間之前需要對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，所有數(shù)據(jù)都?xì)w一化到[-1，1]，并將其標(biāo)準(zhǔn)化處理，消除奇異樣本數(shù)據(jù)導(dǎo)致的不良影響。

4.1 實(shí)驗(yàn)環(huán)境

本文所有實(shí)驗(yàn)均在同一環(huán)境下完成，采用在Windows 10 環(huán)境下搭建系統(tǒng)，計(jì)算機(jī)處理器配置為Intel?CoreTMi3-3240 CPU@3.40 GHz 3.40 GHz，內(nèi)存4 GB，算法在JetBrains PyCharm 下完成。

4.2 評(píng)估指標(biāo)

為保證實(shí)驗(yàn)結(jié)果真實(shí)準(zhǔn)確，每個(gè)數(shù)據(jù)集都進(jìn)行10 次實(shí)驗(yàn)，然后取其平均值作為最終結(jié)果。

對(duì)于第一組數(shù)據(jù)集arrhythmia，通過選擇不同的標(biāo)簽組作為正例和負(fù)例，得到了5種學(xué)習(xí)情景，如表2所示。在該數(shù)據(jù)集中，標(biāo)簽1 被選為健康，標(biāo)簽2 被選為疾病類型2，標(biāo)簽3 被選為疾病類型1。選擇這3個(gè)標(biāo)簽的原因是這些類的人數(shù)足夠大。5種學(xué)習(xí)情景的訓(xùn)練集的數(shù)據(jù)隨機(jī)選擇為大小分別為40、100、100、60、100，其余樣本用于測試。所有訓(xùn)練集中的正例樣本數(shù)為20，其余均為負(fù)數(shù)據(jù)。另外注意的是，數(shù)據(jù)中存在缺失值，本文對(duì)缺失值的處理方式是直接去掉有缺失值的特征。

第二組數(shù)據(jù)集是SPECTF Heart 數(shù)據(jù)集，本文選擇標(biāo)簽0 作為正例，1 作為負(fù)例。訓(xùn)練集的大小為80，正例為50%，負(fù)例也是50%，其余樣本用于測試。

第三組和第四組數(shù)據(jù)集是Hill_Valley_without_noise 數(shù)據(jù)集以及Hill_Valley_with_noise 數(shù)據(jù)集。對(duì)于這兩個(gè)數(shù)據(jù)集，本文均是隨機(jī)選擇50 個(gè)標(biāo)簽為1的正例樣本（Hill）和150 個(gè)標(biāo)簽為0 的負(fù)例樣本（Valley）來形成訓(xùn)練集，其余樣本用于測試。

本文選用AUC 作為衡量指標(biāo)。核函數(shù)選用高斯核函數(shù)，表示為：

其中，σ＞0 是高斯核的帶寬（width）。

4.3 參數(shù)設(shè)計(jì)

算法中包含兩個(gè)超參數(shù)α、σ。由于α僅用于限制w的大小，因此對(duì)這個(gè)超參數(shù)的性能不太敏感，在本文實(shí)踐中被選擇為小值。帶寬σ對(duì)性能很重要，控制了函數(shù)的徑向作用范圍，帶通越大高斯核函數(shù)的局部影響的范圍就越大。本文用小數(shù)初始化α與σ，例如α=0.01，σ=0.01，并以貪婪的方式增加每個(gè)超參數(shù)的值，直到訓(xùn)練集上的性能停止改善。由于算法復(fù)雜度低且參數(shù)較少，還可以用網(wǎng)格搜索方式，將α從2-4～210，σ從2-4～210依次遍歷，找到局部最優(yōu)參數(shù)。

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

KMAUC 算法與SVM（ideal）、單類SVM、Biased SVM、文獻(xiàn)[21]提出的先進(jìn)算法ERR、最大化AUC 比較，評(píng)估結(jié)果如表2 所示。

從表2 中可以看出，與傳統(tǒng)的知道訓(xùn)練集內(nèi)所有正例與負(fù)例標(biāo)簽的分類問題（理想SVM）相比，僅知道一部分正例標(biāo)簽與其他未標(biāo)注標(biāo)簽的PU 學(xué)習(xí)算法性能更差。因此，可以得出結(jié)論，PU 學(xué)習(xí)對(duì)數(shù)據(jù)集內(nèi)的不相關(guān)特征和噪聲更加敏感。直觀地，當(dāng)各種不確定性（未知標(biāo)簽、不相關(guān)特征和異常值）組合并相互關(guān)聯(lián)時(shí)，問題變得比這些分離問題的總和復(fù)雜得多。學(xué)習(xí)過程包含提出利用核函數(shù)映射到高維空間，性能得到明顯改善。如表2 中所示，單類SVM 分類效果非常不理想，因?yàn)樗耆蕾囉谟^察到的正例樣本來做出決策。對(duì)于數(shù)據(jù)集SPECTF Heart，其中特征的數(shù)量不大并且特征可能是線性分布或者特征之間距離較大，除了單類SVM 之外的所有算法傾向于實(shí)現(xiàn)相同的性能。對(duì)于其他數(shù)據(jù)集，加入高斯核函數(shù)處理后的數(shù)據(jù)性能明顯優(yōu)于未使用高斯核函數(shù)處理的數(shù)據(jù)。另外，對(duì)于文獻(xiàn)[21]提出的ERR 算法雖然在部分?jǐn)?shù)據(jù)集上得到了與KMAUC 算法相近的性能，但不能解決增量問題，面對(duì)層出不窮的數(shù)據(jù)時(shí)，具有局限性。最后可以看到，KMAUC 實(shí)現(xiàn)了與理想SVM（正例樣本與負(fù)例樣本完全已知）相近的性能，表明所提出的方法是處理現(xiàn)實(shí)問題的有力工具。

Table 2 AUC value comparison among 6 algorithms on UCI datasets表2 UCI數(shù)據(jù)集上6種算法的AUC 值比較 %

IKMAUC 算法與KMAUC 算法比較如表3 所示，本文分別從每個(gè)訓(xùn)練數(shù)據(jù)集選取5 個(gè)正例樣本與5個(gè)負(fù)例樣本組成正例未標(biāo)注樣本。

Table 3 Time and AUC value comparison among 2 algorithms on UCI datasets表3 UCI數(shù)據(jù)集上兩種算法的時(shí)間與AUC 值比較

可以明顯看出，IKMAUC 在保持精度的情況下大大減少了訓(xùn)練時(shí)間，表明應(yīng)用Sherman-Morrison 公式并直接計(jì)算新增樣本的高維特征空間分布，可以避免對(duì)原始樣本的高維特征空間分布重新求解，并直接利用先前計(jì)算的數(shù)據(jù)繼續(xù)運(yùn)算，從而達(dá)到快速訓(xùn)練的結(jié)果。

5 結(jié)束語

從正例和未標(biāo)注樣本（PU 問題）學(xué)習(xí)分類問題是一個(gè)非常具有挑戰(zhàn)性的問題。本文提出了一個(gè)強(qiáng)有力的算法來系統(tǒng)地解決PU 問題的挑戰(zhàn)性問題。利用AUC 與PU 問題下AUC 關(guān)聯(lián)，求解PU 問題下AUC 的最大化，借助核函數(shù)使得數(shù)據(jù)實(shí)現(xiàn)線性可分的效果。除此以外，本文提出的算法具有可解析解，能夠?qū)崿F(xiàn)快速增量，大大加快算法的學(xué)習(xí)能力。使用真實(shí)數(shù)據(jù)進(jìn)行的廣泛數(shù)值研究表明，與其他對(duì)比算法相比，所提方法具有有效性。在未來的進(jìn)一步發(fā)展中，可以進(jìn)一步優(yōu)化損失函數(shù)以及算法實(shí)現(xiàn)，以達(dá)到更好的學(xué)習(xí)效果。