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

劉 陽 江 峰

（青島科技大學信息科學與技術學院 青島 266061）

1 引言

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

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

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

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

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

2 TSC-OSK算法的設計與實現

2.1 OC-SVM算法

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

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

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

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

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

2.2 TSC-OSK算法

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

TSC-OSK算法

輸入：不平衡的訓練集IT，測試集Test

輸出：預測結果

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

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

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

4.對Test中的每個待測樣本t，反復執行下列語句：

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

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

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

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

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

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

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

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

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

7.返回Test中每個樣本t的預測結果prediction（t）；

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

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

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

表1 多數類檢測器與少數類檢測器對樣本t分類結果的組合

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

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

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

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

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

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

3 實驗

3.1 實驗設置

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

表2 數據集主要特征

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

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

3.2 評價指標

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

表3 混淆矩陣

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

同時，計算實驗結果中少數類樣本的F1-Measure 值，用來衡量分類器對不平衡數據集中的少數類樣本的分類性能。F1-Measure 是查準率（Precision）和查全率（Recall）的調和平均值，F1-Measure值越高，說明分類器對少數類樣本的分類能力越強。其中：

3.3 實驗結果

各個方法在各個數據集上的實驗結果如表4～表6。

表4 不同方法的G-mean值

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

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

表5 不同方法的AUC值

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

表6 不同方法的F1-Measure值

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

4 結語

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