基于單類支持向量機與KNN 的兩階段不平衡數(shù)據(jù)分類*

劉 陽 江 峰

（青島科技大學(xué)信息科學(xué)與技術(shù)學(xué)院 青島 266061）

1 引言

在實際的分類任務(wù)中存在大量的不平衡數(shù)據(jù)。所謂不平衡數(shù)據(jù)就是存在類別不平衡（class-imbalance）問題的數(shù)據(jù)集，即數(shù)據(jù)集中某一類的樣本數(shù)量要遠遠多于或少于其它類樣本數(shù)量。通常將數(shù)量占多數(shù)的類稱為多數(shù)類，數(shù)量占少數(shù)的類稱為少數(shù)類。在傳統(tǒng)的機器學(xué)習(xí)分類算法中，分類器通常會盡量減少分類新樣本時的整體錯誤率，但是，這種做法僅僅在不同類別的樣本被分類錯誤的代價完全相等時才有效［1］。然而，在實際應(yīng)用中少數(shù)類所包含的信息往往更有價值，因此，少數(shù)類樣本被預(yù)測錯誤的代價往往更高。

對于以整體分類準(zhǔn)確率最大化為目標(biāo)而設(shè)計的傳統(tǒng)分類算法而言，這些算法在不平衡數(shù)據(jù)集上進行訓(xùn)練時，可能會對數(shù)量上占優(yōu)勢的多數(shù)類樣本存在明顯的偏好，從而忽略了對少數(shù)類樣本的學(xué)習(xí)。不僅不同類別樣本之間的數(shù)量差距會給不平衡數(shù)據(jù)集上的機器學(xué)習(xí)帶來困難，少數(shù)類與多數(shù)類樣本存在類別分布重合（overlapping），或者是數(shù)據(jù)集中存在噪聲等異常樣本時，同樣會嚴(yán)重影響所訓(xùn)練的分類器的性能。此外，數(shù)據(jù)集中少數(shù)類樣本的稀疏性（sparsity）也是一個需要引起注意的問題［2］，當(dāng)某個數(shù)據(jù)集中的少數(shù)類樣本分布在多個簇中，該數(shù)據(jù)集將會具有更高的分類難度。

近年來，針對不平衡數(shù)據(jù)分類的研究引起了廣泛關(guān)注。眾多研究者提出了不同的不平衡數(shù)據(jù)分類方法。這些方法大體上可以分為三大類：1）數(shù)據(jù)預(yù)處理層面的方法；2）特征層面的方法；3）分類算法層面的方法。目前，在分類算法層面，典型的方法有代價敏感學(xué)習(xí)法、集成學(xué)習(xí)法、單類學(xué)習(xí)法等。與代價敏感學(xué)習(xí)和集成學(xué)習(xí)不同，單類學(xué)習(xí)是一種特殊的分類算法，其所使用的訓(xùn)練樣本只包括某一種類別的信息，它根據(jù)所獲得的目標(biāo)數(shù)據(jù)估計其邊界，從而做出正確的分類［3］。OC-SVM 算法是一種典型的單類學(xué)習(xí)方法，其目標(biāo)是在特征空間中求解一個最優(yōu)超平面，實現(xiàn)目標(biāo)數(shù)據(jù)與坐標(biāo)原點的最大分離。OC-SVM 算法只需要一類數(shù)據(jù)樣本作為訓(xùn)練集，可以避免對少數(shù)類學(xué)習(xí)不足的問題，有效減少時間開銷，同時具有訓(xùn)練、預(yù)測速度快和分類錯誤率低等優(yōu)點，適用于少數(shù)類樣本非常少或類別不平衡程度很高的極端情況。因此，OC-SVM 算法正逐漸成為不平衡分類領(lǐng)域的研究熱點。

現(xiàn)有的OC-SVM 算法在處理不平衡數(shù)據(jù)時通常只是將所有樣本劃分成多數(shù)類樣本與少數(shù)類樣本，實際上，除了多數(shù)類樣本與少數(shù)類樣本之外，可能還存在一些樣本屬于邊界樣本或離群樣本。對于邊界樣本和離群樣本，利用OC-SVM算法所構(gòu)建的多數(shù)類檢測器與少數(shù)類檢測器在對邊界樣本和離群樣本的預(yù)測上存在著分歧。然而，現(xiàn)有的OC-SVM 算法卻直接忽視了邊界樣本與離群樣本的存在，當(dāng)多數(shù)類檢測器與少數(shù)類檢測器在預(yù)測某個樣本上存在分歧時，只是簡單地將該樣本歸為多數(shù)類（或少數(shù)類）。因此，OC-SVM 算法在對邊界樣本和離群樣本進行分類時不可避免地會出現(xiàn)預(yù)測偏差，從而影響到不平衡數(shù)據(jù)上的整體分類性能。

針對現(xiàn)有的OC-SVM算法所存在的問題，本文將提出一種基于OC-SVM 與KNN 的兩階段分類算法TSC-OSK。TSC-OSK 算法通過采用OC-SVM 算法與KNN 算法進行兩個階段的分類來解決傳統(tǒng)OC-SVM 算法不能有效處理邊界樣本與離群樣本的問題，避免了邊界樣本與離群樣本對OC-SVM算法性能的影響，并且繼承了OC-SVM算法在處理不平衡數(shù)據(jù)上的良好性能。

2 TSC-OSK算法的設(shè)計與實現(xiàn)

2.1 OC-SVM算法

OC-SVM（One-Class Support Vector Machine）算法在文獻［4］中提出，是基于支持邊界的單類學(xué)習(xí)算法。OC-SVM 算法的原理是尋找一個能大體上將所有訓(xùn)練集中的樣本點與坐標(biāo)原點在特征空間分離開的超平面，并且最大化分離超平面到坐標(biāo)原點的距離。OC-SVM 的決策函數(shù)與支持向量機類似，為

其中，ω表示垂直于超平面的法向量，ρ代表截距［5］，通過求解以下二次規(guī)劃問題獲得：

需要特別指出的是，這里的v∈(0，1)的作用是控制支持向量在訓(xùn)練樣本中所占的比重［3］。ξi則是為了使該算法具有魯棒性而引入的松弛變量。再引入拉格朗日乘子α與核函數(shù)k 將上述二次規(guī)劃問題轉(zhuǎn)化為求解如下對偶問題：

將OC-SVM算法應(yīng)用于不平衡數(shù)據(jù)的分類時，如果用不平衡數(shù)據(jù)集中的多數(shù)類樣本作為訓(xùn)練集求解得到相應(yīng)的決策函數(shù)，那么在對待測樣本進行分類時，將待測樣本數(shù)據(jù)代入該決策函數(shù)，若函數(shù)值等于+1，OC-SVM 算法就將該樣本分類為多數(shù)類；若函數(shù)值等于-1，OC-SVM 算法就將該樣本分類為少數(shù)類。與之相對，如果用少數(shù)類樣本作為訓(xùn)練集求解得到相應(yīng)的決策函數(shù)，那么在對待測樣本進行分類時，將待測樣本數(shù)據(jù)代入該決策函數(shù)，若函數(shù)值等于+1，OC-SVM 算法就將該樣本分類為少數(shù)類；若函數(shù)值等于-1，OC-SVM 算法就將該樣本分類為多數(shù)類。

OC-SVM 算法只需要一類數(shù)據(jù)樣本作為訓(xùn)練集，可以避免對少數(shù)類學(xué)習(xí)不足的問題，有效減少時間開銷。同時OC-SVM算法具有訓(xùn)練、決策速度快、分類錯誤率低等優(yōu)點。但在實際應(yīng)用時，數(shù)據(jù)集不同類別之間可能存在類別分布重合，OC-SVM算法僅學(xué)習(xí)一類數(shù)據(jù)樣本信息，無法對處于類別分布重合區(qū)域的邊界樣本做出正確的分類。同時，不平衡數(shù)據(jù)集中可能會存在離群點或噪聲。OC-SVM 算法易受噪音的影響，其魯棒性較差［6］，并且OC-SVM算法對訓(xùn)練集中的離群點非常敏感，離群點會降低OC-SVM算法的分類性能［7］。

2.2 TSC-OSK算法

針對OC-SVM 算法在處理不平衡數(shù)據(jù)上的不足，本文提出一種基于OC-SVM 和KNN 算法的兩階段分類算法TSC-OSK，TSC-OSK 算法的主要執(zhí)行步驟如下：

TSC-OSK算法

輸入：不平衡的訓(xùn)練集IT，測試集Test

輸出：預(yù)測結(jié)果

1.將不平衡訓(xùn)練集IT劃分為多數(shù)類樣本子集S1與少數(shù)類樣本子集上S2；

2.在多數(shù)類樣本子集S1上利用OC-SVM 算法構(gòu)建一個多數(shù)類檢測器ND1；

3.在少數(shù)類樣本子集S2上利用OC-SVM 算法構(gòu)建一個少數(shù)類檢測器ND2；

4.對Test中的每個待測樣本t，反復(fù)執(zhí)行下列語句：

4.1 利用多數(shù)類檢測器ND1對樣本t進行分類，并令r1表示ND1對樣本t的預(yù)測結(jié)果；

4.2 利用少數(shù)類檢測器ND2對樣本t進行分類，并令r2表示ND2對樣本t的預(yù)測結(jié)果；

4.3 將預(yù)測結(jié)果r1與r2組合在一起，并根據(jù)不同的組合，分別進行如下處理：

（1）如果r1= 1 且r2=-1，則令prediction（t）=-1（即將樣本t預(yù)測為多數(shù)類）；

（2）如果r1=-1 且r2=1，則令prediction（t）= 1（即將樣本t預(yù)測為少數(shù)類）；

（3）如果r1=-1 且r2=-1，則令O=O∪{t}（即將樣本t看作是一個離群樣本，并添加到離群樣本集O中）；

（4）如果r1=1 且r2=1，則令B=B∪{t}（即將樣本t 看作是一個邊界樣本，并添加到邊界樣本集B中）。

5.對于O中的每個離群樣本x，在訓(xùn)練集IT上構(gòu)建一個KNN 分類器，利用該分類器對x進行精煉分類，并將該分類結(jié)果賦值給prediction（x）；

6.對于B中的每個邊界樣本y，在訓(xùn)練集IT上構(gòu)建一個KNN 分類器，利用該分類器對y進行精煉分類，并將該分類結(jié)果賦值給prediction（y）；

7.返回Test中每個樣本t的預(yù)測結(jié)果prediction（t）；

在TSC-OSK 算法的主要步驟中，第1 步到第3步為第1 階段的分類器的構(gòu)建。首先將訓(xùn)練集IT劃分為多數(shù)類樣本子集和少數(shù)類樣本子集，并采用OC-SVM 算法分別在多數(shù)類樣本子集和少數(shù)類樣本子集上進行擬合，從而構(gòu)建出“多數(shù)類檢測器”與“少數(shù)類檢測器”。具體定義如下：

定義1（多數(shù)類檢測器與少數(shù)類檢測器）。給定一個不平衡數(shù)據(jù)集IT，令S1?IT和S2?IT分別表示IT 中的多數(shù)類樣本子集和少數(shù)類樣本子集，其中，S1∩S2=?，S1∪S2=IT。我們將OC-SVM 算法在子集S1上訓(xùn)練得到的分類器ND1稱為多數(shù)類檢測器，并且將OC-SVM 算法在子集S2上訓(xùn)練得到的分類器ND2稱為少數(shù)類檢測器。

TSC-OSK 算法的主要步驟中的第4 步為TSC-OSK 算法的第1 階段分類。利用前3 步訓(xùn)練出的多數(shù)類檢測器和少數(shù)類檢測器，分別對測試樣本進行第1 階段的分類。對于一個待測樣本t，分別使用多數(shù)類檢測器和少數(shù)類檢測器來對其進行檢測。將多數(shù)類檢測器與少數(shù)類檢測器對t的分類結(jié)果組合在一起，可以形成表1中的四種組合。

表1 多數(shù)類檢測器與少數(shù)類檢測器對樣本t分類結(jié)果的組合

我們可以把表1中的四種組合分成兩大類：

1）多數(shù)類檢測器與少數(shù)類檢測器對樣本t的預(yù)測結(jié)果不存在分歧，我們可以直接給出樣本t 最終的分類結(jié)果，即在第一階段就可以完成對樣本t 的預(yù)測。具體而言，如果多數(shù)類檢測器將t 預(yù)測為1并且少數(shù)類檢測器將t 預(yù)測為-1 時（直觀地說，多數(shù)類檢測器認為t是一個多數(shù)類樣本并且少數(shù)類檢測器認為t 不是一個少數(shù)類樣本），則t 最終被歸為多數(shù)類；如果多數(shù)類檢測器將t 預(yù)測為-1 并且少數(shù)類檢測器將t預(yù)測為1時，則t最終被歸為少數(shù)類。

2）多數(shù)類檢測器與少數(shù)類檢測器對樣本t的預(yù)測結(jié)果存在分歧，需要對t 進行第二階段的分類。具體而言，如果多數(shù)類檢測器和少數(shù)類檢測器都將t 預(yù)測為-1 時，則t 被認為是一個離群樣本；如果多數(shù)類檢測器和少數(shù)類檢測器都將t 預(yù)測為1 時，則t被認為是一個邊界樣本。

定義2（離群樣本與邊界樣本）。給定一個不平衡數(shù)據(jù)集IT，令ND1和ND2分別表示OC-SVM 算法在IT 上所構(gòu)建的多數(shù)類檢測器與少數(shù)類檢測器。對于任意一個待測樣本t，如果ND1和ND2都將t預(yù)測為-1時（即ND1認為t不是一個多數(shù)類樣本并且ND2認為t 不是一個少數(shù)類樣本），則我們稱t 是一個離群樣本；如果ND1和ND2都將t 預(yù)測為1 時（即ND1認為t 是一個多數(shù)類樣本并且ND2認為t 是一個少數(shù)類樣本），則我們稱t是一個邊界樣本。

從定義2 可以看出，離群樣本是被多數(shù)類檢測器和少數(shù)類檢測器都排斥在外的樣本，而邊界樣本則是被多數(shù)類檢測器和少數(shù)類檢測器都接納的樣本。離群樣本通常是偏離于大多數(shù)樣本的一小部分樣本，而邊界樣本則往往分布在多數(shù)類檢測器和少數(shù)類檢測器決策邊界的重疊區(qū)域，在特征空間中呈現(xiàn)線性不可分的狀態(tài)。離群樣本的出現(xiàn)可能是因為分類器出現(xiàn)了過擬合，生成的決策邊界喪失了一定的魯棒性，也可能是因為數(shù)據(jù)本身存在異常（即噪聲）。異常數(shù)據(jù)的影響在不平衡學(xué)習(xí)中非常顯著，在不平衡數(shù)據(jù)集上，大多分類器都是噪聲敏感的［8］。另外，邊界樣本的出現(xiàn)可能是因為訓(xùn)練集中存在類別分布重合，導(dǎo)致生成的少數(shù)類檢測器和多數(shù)類檢測器的決策邊界發(fā)生了重合，而待測樣本又分布在決策邊界重合的區(qū)域。已有的研究工作表明，分類器劃分錯誤往往集中在數(shù)據(jù)的邊界區(qū)域［9］。對類別分布重合問題的處理方法目前主要有兩個策略，分別是合并策略和精煉策略［10］。合并策略是將重疊的類別合并為一個新類別，并忽略原來類別的邊界之間的差別。精煉策略則是對重疊的類別進行單獨處理，從而對重疊類別的邊界進行精煉［11］。

TSC-OSK 算法的主要步驟中的第5 步和第6步為TSC-OSK 算法的第2 階段分類。由于數(shù)據(jù)集整體上多數(shù)類樣本和少數(shù)類樣本的數(shù)量不平衡，因此第一階段分類形成的邊界樣本和離群樣本也可能存在類別不平衡問題。在少數(shù)類樣本絕對數(shù)量過少的情況下，傳統(tǒng)的分類算法可能難以學(xué)習(xí)形成有效的分類邊界。已有的研究工作［12］表明，KNN算法雖然非常簡單，但在面對類別分布重合與噪聲數(shù)據(jù)時可能比其他各種復(fù)雜的分類器更加魯棒，隨著類別分布重合程度的增高，k值更小的KNN 分類器其效果相比k 值較大的KNN 分類器表現(xiàn)更好。因此，本文采用KNN 算法進行TSC-OSK 算法的第二個階段的分類，即利用KNN 算法來對第一個階段所產(chǎn)生的邊界樣本和離群樣本進行精煉分類。而精煉分類的結(jié)果就作為TSC-OSK 算法對邊界樣本和離群樣本最終的分類結(jié)果。

3 實驗

3.1 實驗設(shè)置

為了驗證本文提出的兩階段分類算法TSCOSK在不平衡數(shù)據(jù)集上的分類性能，我們選用Kaggle 數(shù)據(jù)庫中的Personal Loan 數(shù)據(jù)集，UCI數(shù)據(jù)庫中的Page Blocks 數(shù)據(jù)集［13］，KEEL 數(shù)據(jù)庫中的abalone19、yeast3、segment0、vowel0 等數(shù)據(jù)集［14］進行實驗。實驗數(shù)據(jù)集的具體信息見表2。其中IR 為多數(shù)類與少數(shù)類樣本數(shù)量的比值，反映了數(shù)據(jù)集的不平衡程度。

表2 數(shù)據(jù)集主要特征

為保證實驗的客觀有效，我們采用10 折交叉驗證法來構(gòu)建訓(xùn)練集、測試集。對于每個數(shù)據(jù)集：將數(shù)據(jù)集劃分成10 個大小相似的互斥子集，輪流將其中1 個子集作為測試集，余下9 個子集的并集作為訓(xùn)練集，從而獲得10 組訓(xùn)練集和測試集；用這10 組訓(xùn)練集和測試集進行10 次實驗，取這10 次結(jié)果的平均值作為該數(shù)據(jù)集上的實驗結(jié)果。

為了能更客觀地反映TSC-OSK 算法的性能，我們將TSC-OSK 算法與以下方法進行對比：1）KNN 算法；2）OC-SVM 擬合多數(shù)類；3）OC-SVM 擬合少數(shù)類；4）Borderline-SMOTE+KNN；5）EasyEnsemble+SVM。其中，OC-SVM 擬合多數(shù)類與OC-SVM 擬合少數(shù)類表示采用OC-SVM 算法分別在訓(xùn)練集中的多數(shù)類樣本子集上和少數(shù)類樣本子集上進行擬合，從而構(gòu)建出兩個分類器對測試集進行預(yù)測；Borderline-SMOTE+KNN 表示先用Borderline-SMOTE 算法對訓(xùn)練集進行平衡化處理，在平衡化的訓(xùn)練集上使用KNN 算法構(gòu)建分類器對測試集進行預(yù)測；EasyEnsemble+SVM 表示用EasyEnsemble算法將訓(xùn)練集中的多數(shù)類樣本分為多個組，分別與少數(shù)類樣本組成多個平衡數(shù)據(jù)集，進而在這些平衡數(shù)據(jù)集上訓(xùn)練基分類器為SVM 算法的集成分類器對測試集進行預(yù)測。實驗中，KNN 算法，Borderline-SMOTE+KNN，TSC-OSK 算法所用到的KNN算法的k值均設(shè)置為3。

3.2 評價指標(biāo)

為了準(zhǔn)確評估分類器在不平衡數(shù)據(jù)集上的分類性能，學(xué)者們提出了一系列基于如表3 所示的混淆矩陣的評價指標(biāo)，例如，KS 曲線、G-Mean、ROC曲線等。

表3 混淆矩陣

本文選擇G-Mean［15］和AUC［16］作為衡量分類器在不平衡數(shù)據(jù)集上的整體分類性能的指標(biāo)。G-Mean綜合考慮了分類器對多數(shù)類樣本和少數(shù)類樣本的分類準(zhǔn)確率。ROC 曲線是一個由“真正率（True Positive Rate，TPR）-偽正率（False Positive Rate，F(xiàn)PR）”所刻畫的二維圖［17］，能夠比較全面地描述分類器的性能，是目前評價不平衡數(shù)據(jù)集分類器性能的常用方法之一，AUC 為ROC 曲線下面積。G-Mean 和AUC 的值越高，說明分類器的分類性能越強。其中：

同時，計算實驗結(jié)果中少數(shù)類樣本的F1-Measure 值，用來衡量分類器對不平衡數(shù)據(jù)集中的少數(shù)類樣本的分類性能。F1-Measure 是查準(zhǔn)率（Precision）和查全率（Recall）的調(diào)和平均值，F(xiàn)1-Measure值越高，說明分類器對少數(shù)類樣本的分類能力越強。其中：

3.3 實驗結(jié)果

各個方法在各個數(shù)據(jù)集上的實驗結(jié)果如表4～表6。

表4 不同方法的G-mean值

由表4可以看出：在yeast3數(shù)據(jù)集上，TSC-OSK算法的G-Mean 值僅低于EasyEnsemble+SVM 方法。在segment0 數(shù)據(jù)集和vowel0 數(shù)據(jù)集上，TSC-OSK 算 法、KNN 算 法 和Borderline-SMOTE+KNN 方法均取得了最高的G-Mean 值。而在其余三個數(shù)據(jù)集上，TSC-OSK 算法均取得了最高的G-Mean值。

由表5可以看出：在yeast3數(shù)據(jù)集上，TSC-OSK算法的AUC 值僅低于EasyEnsemble+SVM 方法。在vowel0 數(shù)據(jù)集上，TSC-OSK 算法與KNN 算法和Borderline-SMOTE+KNN方法均取得了最高值。在其余4個數(shù)據(jù)集上，TSC-OSK 算法均取得了最高的AUC值。

表5 不同方法的AUC值

由表6 可以看出：在abalone19 數(shù)據(jù)集上，TSC-OSK 算法的F1-Measure 值僅低于Borderline-SMOTE+KNN 方法；而在其余5 個數(shù)據(jù)集上，TSC-OSK算法均取得了最高的F1-Measure值。

表6 不同方法的F1-Measure值

綜合以上實驗結(jié)果可以發(fā)現(xiàn)，本文所提出的TSC-OSK 算法，通過采用OC-SVM 算法與KNN 算法進行兩個階段的分類，繼承了OC-SVM算法在處理不平衡數(shù)據(jù)上的良好性能，同時避免了邊界樣本與離群樣本對OC-SVM算法性能的影響，為不平衡數(shù)據(jù)的處理提供了一種更加合理的機制。因此，TSC-OSK 算法能夠在不增加訓(xùn)練成本的情況下，取得相比其他算法更好的分類性能。

4 結(jié)語

針對OC-SVM 算法無法對不平衡數(shù)據(jù)集中的邊界樣本與離群樣本做出正確的分類的問題，本文提出了一種基于OC-SVM 與KNN 的兩階段分類算法TSC-OSK。實驗證明，TSC-OSK 算法在各個領(lǐng)域的不平衡數(shù)據(jù)集上均能表現(xiàn)出不錯的分類性能。但在實際使用TSC-OSK 算法時，難以通過試錯調(diào)參的方式讓第一階段的多數(shù)類檢測器與少數(shù)類檢測器各自擬合到最合適的狀態(tài)。同時，第二階段中KNN 算法的k 值也對TSC-OSK 算法的分類性能有很大的影響，需要通過進一步的研究選擇更好的k 值取值策略。因此在未來的研究中，針對兩階段分類算法TSC-OSK 的第一階段分類，可以嘗試將優(yōu)化算法結(jié)合到多數(shù)類檢測器與少數(shù)類檢測器的構(gòu)建過程中，解決OC-SVM算法參數(shù)設(shè)置困難的問題，也可以嘗試使用其他的單類學(xué)習(xí)算法；針對第二階段分類，應(yīng)當(dāng)尋找一種啟發(fā)式的k 值確定策略，或是嘗試使用不同的分類算法來進行第二階段的分類。