基于改進的半監督聚類的不平衡分類算法

陸 宇，趙凌云，白斌雯，姜 震

（江蘇大學 計算機科學與通信工程學院，江蘇 鎮江 212013）

0 引言

類別不平衡是指數據集中某些類（少數類）的樣本數量與其他類（多數類）的樣本數量有很大差距［1］。不平衡數據分類廣泛存在于醫療診斷、故障診斷、信用卡欺詐檢測［2］等領域。傳統的分類算法假設各類別樣本的誤分代價相等，以最小化總體錯誤率為目標進行模型優化，這會導致最終決策偏向于多數類樣本，造成少數類樣本被錯分。但是現實任務中少數類樣本往往更具有價值。因此如何有效提高少數類樣本的識別率、提升不平衡分類算法性能，已經成為近年來機器學習領域的研究重點之一。

當前不平衡分類的算法大致可分為兩類：1）算法層面的方法［3］通過對已有分類算法進行修改或者提出新算法以提高對少數類的識別率，這依賴于特定的算法并要求對相關領域有深入的了解。2）數據層面的方法通過削減多數類樣本的數量（欠采樣）或者增加少數類樣本的數量（過采樣）來實現訓練集的再平衡，從而緩解分類模型的類別傾斜［4］。該類方法獨立于具體的分類算法，可擴展性高；但是欠采樣容易丟失有效的信息。過采樣通過復制原有少數類樣本或者根據原有分布合成新的少數類樣本；但是過采樣具有不確定性，且增加的樣本都是基于原有的分布，包含信息量過少，無法揭示更多的數據集分布特征。

本文提出一種利用改進的半監督聚類來輔助不平衡分類的算法。首先，提出一種改進的半監督聚類算法CS-KMeans（Constrained-Seeded-K-Means）來挖掘數據的分布特征，并在聚簇中選擇高置信度的無標簽樣本（偽標簽樣本）來補充少數類樣本。這種新型的過采樣方法除了實現數據集的再平衡外，還可以有效引入聚類所獲得的分布特征來改善分類模型在不平衡數據集上的性能。其次，將改進的半監督聚類與分類模型相結合進行最終的預測。該算法緩解了單一分類器泛化能力較差的問題，進一步提升了不平衡分類性能。在實驗部分，通過將本文算法與經典的Borderline-SMOTE（Borderline Synthetic Minority Oversampling TEchnique）［5］、自適應 綜合過 采樣技 術（ADAptive SYNthetic sampling approach，ADASYN）［6］和最新 提出的RCSMOTE（Range-Controlled Synthetic Minority Oversampling TEchnique）［7］等算法在10 個數據集上進行對比，實驗結果表明本文所提算法有更好的性能，驗證了本文算法的可行性和有效性。

1 相關研究

在算法層面，根據不平衡數據集的分布特點，通過對已有經典算法進行修改或者提出新算法以提高對不平衡數據集中少數類的識別率，代表算法有代價敏感學習［8］、集成學習［9］等?；诖鷥r敏感學習的方式分別給不同的類別賦予不同的代價因子，以求獲得誤分代價最小的分類結果［10］，或者考慮對決策函數添加不同的權重，使最終的決策更傾向于少數類［11］?；诩蓪W習的不平衡分類算法分為數據預處理與集成學習相結合的方法［12］和代價敏感的集成學習［13］。為了對所選算法進行適當的修改用于不平衡數據分類，必須對分類算法和相關領域有深入的了解。

在數據層面，通過改變數據集樣本的分布或者消除各個類別之間樣本數量的差異來平衡數據集，由于其獨立于具體的分類算法，可以與任意的分類算法結合使用［14］，可擴展性高，這種方法是目前主流的算法，代表算法有SMOTE（Synthetic Minority Oversampling TEchnique）［15］，Borderline-SMOTE［5］等。SMOTE通過隨機在其K近鄰中選擇樣本進行插值，生成無重復的新的少數類樣本，可以在一定程度上解決過擬合的問題；但是新生成的樣本也會出現噪聲、樣本重疊的問題。后續在SMOTE 的基礎上又提出了許多改進的方法，Borderline-SMOTE 認為邊界附近的樣本比遠離邊界的樣本更容易被分錯，因此在邊界的樣本應該更重要。這個設想也符合經典分類器的思想，如支持向量機（Support Vector Machine，SVM）就是為了最大化超平面，而超平面又由其附近的支持向量所構成。RCSMOTE［7］為了解決引入價值量低甚至降低分類性能的噪聲樣本，將原始數據集分為安全區域、邊界區域和噪聲區域，在采樣過程中首先針對邊界區域的樣本進行采樣，擴充會影響決策平面的樣本，若邊界區域中樣本過少，不足以滿足采樣需求，那么再對安全區域的樣本進行采樣，而不會對噪聲區域的樣本進行采樣，有利于引入大量信息量高的樣本，同時減少噪聲樣本的引入。CDSMOTE（Class Decomposition SMOTE）［16］通過K-Means 將多數類分解為多個子簇，并為其賦予新的子標簽，然后針對性地對這些簇進行過采樣。TU（Trainable Undersampling）［17］通過強化學習方式，將欠采樣過程與具體的分類過程相結合，從而有指導地進行欠采樣，減少過采樣刪除過多有價值的樣本。

近年來一個值得關注的方向是采用聚類分析發掘數據的分布特征，從而提高采樣的質量。K-Means SMOTE（KMeans SMOTE）［18］首先利用聚類尋找“安全區域”，即那些更適合進行過采樣的樣本簇，然后隨機選擇這些簇中的樣本使用SMOTE 進行過采樣，這不僅解決了類間不平衡，而且有效解決了類內不平衡。文獻［19］中通過在全體樣本上使用聚類算法和過濾的策略很好解決了類內不平衡的問題，該算法首先在整個數據集上使用密度峰值聚類算法，然后根據簇的密度和距離多數類樣本的距離為每個簇分配采樣比重，最后該算法為了避免過采樣帶來的重疊的問題，開發了一種啟發式過濾策略，以迭代的方式將可能重疊的少數實例從多數類中移除。目前不平衡分類中基本傾向于在各個類內部對有標簽樣本進行無監督聚類［20］。這種方式難以發掘數據的整體分布規律，此外還有大量的有標簽數據未被有效利用。

2 基于改進的半監督聚類的不平衡分類

針對當前的不平衡分類研究中引入聚類技術的局限性，本文提出一種改進的半監督聚類算法來輔助不平衡分類。其基本思想是利用有標簽樣本的指導，在全體數據上進行聚類，建立簇與類的映射關系。相較于無監督的局部聚類，該算法可以更好地發掘原始數據分布特征以輔助分類。首先，基于半監督聚類的結果，從無標簽數據中選擇置信度高的部分，作為少數類的偽標簽樣本加入訓練集。這種新型的過采樣方法可以更好地發掘數據的分布特征，改善隨后分類模型的訓練。然后，考慮到類別傾斜的影響，半監督聚類預測結果中的少數類樣本可能不足以實現數據集的再平衡。這種情況下，使用SMOTE 作為補充，將偽標簽數據集、原始數據集和過采樣數據集三者結合得到新的訓練集。最后，為了進一步提高模型的泛化性能，將改進的半監督聚類的預測結果和分類方法的預測結果結合得到最終的分類結果。算法原理如圖1 所示。

圖1 本文算法原理Fig.1 Principle of the proposed algorithm

2.1 Constrained-Seeded-K-Means算法

半監督聚類利用標記數據或成對約束信息來指導聚類，以求得到更好的聚類結果。最常見的約束類型是成對約束，它要求數據在分配過程中滿足必連約束或勿連約束［21］，其聚類結果會受到約束順序的影響。相較于成對約束，使用部分有標簽樣本來指導聚類的劃分更為自然，并避免了約束的自相矛盾和順序的影響。這些有標簽樣本通常被用于聚類模型的初始化。其中Seeded-K-Means［22］使用標記信息初始化質心，然后采用標準的K-Means 迭代方法來更新質心并完成聚簇劃分。值得注意的是，迭代過程中一些預測錯誤的樣本會明顯造成聚類性能的下降。本文提出一種目標函數，利用標記信息來指導質心迭代，從而控制噪聲影響并改善聚類性能。

2.1.1 初始化

根據訓練集中各個樣本的標簽，把有標簽樣本依次劃分到距離它們最近且標簽相同的簇中，最后得到每個簇的初始質心：

其中：Pk表示第k個簇。在不平衡數據集中，由于少數類樣本數量少，而且分布可能比較分散，往往會出現少數類樣本被錯分到多數類的簇中的情況。針對該問題，在計算樣本到各個質心的距離時，本文提出了一種結合各個類別的不平衡率作為權重的新型距離公式如下：

其中：|P|代表樣本總數。該距離計算公式可以有效降低少數類樣本被誤分的概率。

2.1.2 目標函數

在傳統的K-Means 算法中，其目標函數是最小化各個數據點到質心的距離和，即誤差平方和（Sum of Square Error，SSE）。

其中：Pk是第k個簇，mk是第k個簇的質心，Λ為聚類模型。Seeded-K-Means 利用有標簽樣本初始化簇的個數以及對應的質心，通過標準的質心迭代來最小化SSE 并獲得聚簇結果；但是質心迭代過程中有些不屬于該類（簇）的數據可能會被錯誤劃分進來，進而影響質心和簇的質量。這種問題在不平衡數據集中更加突出，由于少數類樣本數量少且分布分散，聚類往往為了得到最小化誤差，會將少數類樣本劃分到多數類的簇中，造成聚類性能嚴重下降。

傳統質心迭代的終止條件常用的有兩種方式：方式一是設置最大迭代次數；方式二是計算前后兩次迭代的差值，若小于指定的閾值，則終止迭代。這兩種終止方式都有一個缺點，迭代過程中極有可能錯過最優的劃分結果，導致聚類性能下降。

本文提出了一種新的目標函數用來控制質心迭代過程：利用有標簽樣本XL來評估聚類模型的性能，進而指導質心的迭代。具體做法是將訓練集上計算的準確率（Accuracy，Acc）與少數類的查全率（Recall，Rec）相結合來判斷是否停止迭代。

其中Rec的計算方式為：

其中：|Y|表示數據集類別個數，tpi是預測為i類且實際上屬于i類的樣本的數量，fni是未預測為i類但實際上屬于i類的樣本的數量。在保證SSE 下降的前提下，該目標函數同時考慮了簇的預測準確度以及少數類的查全率。在多數類不被誤分的情況下，最大化將少數類樣本劃分到對應的少數類簇中。當目標函數下降時，表明如果繼續迭代會降低聚類算法性能，應該停止迭代，并恢復上輪聚類結果。

2.1.3 簇的劃分

測試樣本x屬于所在簇的概率的計算方式為：

其中：mi為簇Pi的質心，‖x-mi‖是樣本x到質心mi的距離，|P|表示簇的數量，Λ為聚類模型。在不平衡數據集中，少數類樣本數量過少且分布分散，這樣屬于少數類的簇的直徑可能過小，而多數類樣本數量較多且分布集中，這有可能造成屬于多數類的簇直徑過大，二者的差距會導致最終對于不同類別樣本預測概率計算存在誤差。因此通過式（6）可發現，本文算法不僅考慮了無標簽樣本x到其所屬簇的質心的距離，還綜合考慮了其到所有具有相同標簽的簇質心的距離，這有利于避免因為簇的直徑影響不同樣本的置信度，提高了預測置信度的準確性。

Constrained-Seeded-K-Means 算法的具體步驟如下。

算法1 Constrained-Seeded-K-Means 算法。

2.2 基于CS-K-Means的不平衡分類算法

本文算法首先在數據集上使用改進的半監督聚類得到若干簇，這些簇揭示了原數據的底層分布特征；然后根據各個簇的屬性對這些多數類簇進一步處理，弱化多數類樣本的影響；接著基于聚類結果選擇高置信度偽標簽樣本加入訓練集并使用分類算法訓練分類模型；最后為了提高算法的泛化性能，融合分類算法和改進的半監督聚類結果得到最終的分類結果。算法描述如下。

算法2 基于CS-K-Means 的不平衡分類算法。

在步驟1）結束后，可能會存在一些不純的或者規模過小的多數類的簇，即重疊區域或小集群，這可能會誤導分類模型的訓練；因此通過步驟2），刪除在重疊區域中可能降低少數類識別率的過小多數類簇。該做法有助于最終的決策偏向于少數類，進一步提高少數類的識別率。

在步驟3）中，有別于其他重采樣算法引入大量人工生成的樣本，本文算法篩選高置信度的偽標簽樣本補充少數類樣本，不會破壞原始的數據分布。CS-K-Means對于樣本x的置信度預測計算方式如式（6）所示，本文將用式（6）作為置信度計算的標準——置信度越高，被選為偽標簽樣本的概率就越大。

最終通過步驟5），將CS-K-Means 與傳統的分類算法相結合，得到最終分類結果，進一步提升算法的泛化能力；理論上可以使用任意具有概率輸出的分類算法，本文采用經典的支持向量機（SVM）算法，結合方式如式（7）所示：

其中：P(y|x；Λ) 為CS-K-Means 的預測概率結果，根據式（6）計算；P(y|x；Θ)為分類器的預測概率結果，根據具體分類器計算所得。式（7）通過權重參數w調節CS-K-Means 和分類器對最終結果的影響，為了更好地融合二者預測概率，本文算法利用數據集的先驗知識不平衡率（Imbalance Ratio，IR）結合模型在訓練集上的表現，自適應地確定w，如式（8）所示：

其中：ri為先驗知識IR,分別為分類器和改進的半監督聚類在測試集上預測結果的不同類標簽比例。因此，分類表現更好的模型對于最終的決策影響更大。

3 實驗分析

3.1 數據集介紹

為了衡量本文算法的性能，本文使用keel 和UCI 中10 組數據集訓練分類器并對結果進行分析。其中部分數據為多分類數據集，本文實驗將某些類合并成二分類數據集：規模較小的類標記為少數類，其余類合并為多數類。數據集詳情如表1 所示，其中IR 代表數據集的不平衡率。

表1 數據集的基本信息Tab.1 Basic information of datasets

3.2 評估指標

本文將使用不平衡分類常用的G-mean 和曲線下面積（Area Under Curve，AUC）作為分類模型的評估指標（本文將少數類定義為正類，多數類定義為負類）。令TP（True Positive）表示預測為正類的正樣本；TN（True Negative）為預測為負類的負樣本；FP（False Positive）為預測為正類的負樣本；FN（False Negative）為預測為負類的正樣本?？梢杂嬎愠鲮`敏度（Sensitivity，Sens）和特異度（Specificity，Spec）：

根據這兩項指標，可以得到G-mean：

受試者工作特征（Receiver Operating Characteristic，ROC）是一個二維平面上的曲線，以假陽率為橫軸，以真陽率為縱軸。最佳的分類器應當盡可能處于左上方。當一個分類器的ROC 曲線完全覆蓋另一個分類器的ROC 曲線，則說明前者的分類性能優于后者；若兩分類器的ROC 曲線發生交叉則無法斷言哪個分類器性能更好。因此引入了ROC 曲線下的面積，即AUC 進行對比。

3.3 結果分析

本文將所提算法與6 個過采樣算法Borderline-SMOTE（B-SMOTE）、SVM-SMOTE（Support Vector Machines Synthetic Minority Oversampling TEchnique）［23］、K-Means SMOTE、ADASYN［6］、RCSMOTE 和CDSMOTE 以及1 種欠采樣算法TU進行比較，其中前4 個算法使用Python 下的Imbalance-learn包實現，參數均使用默認參數，RCSMOTE、CDSMOTE 和TU使用與相應文獻相同的參數設置。基礎分類器使用的都是SVM，均采用徑向基核函數（Radial Basis Function，RBF）。表2、3 同時列出了基礎分類器SVM 和改進的半監督聚類算法的結果。最終結果為5 折交叉驗證的平均值。

表2、3分別給出了10種不同算法在10個不平衡數據集上的AUC 和G-mean 指標的實驗結果，最優結果加粗表示，其中CS-K-Means 表示改進的半監督聚類的結果，SVM 表示基分類器SVM的結果，C_SVM表示SVM在CS-K-Means處理過后的數據集上的結果。從結果可以看出，在AUC和G-mean的平均結果上本文算法都達到了最優。這表明了本文算法對于不平衡數據分類的有效性。與基分類器SVM 相比，所有的不平衡分類算法在AUC和G-mean上都有了明顯的提升，這表明了這些算法在處理不平衡數據分類上的優越性能。

表2 不同算法的AUC對比Tab.2 AUC comparison of different algorithms

表3 不同算法的G-mean對比Tab.3 G-mean comparison of different algorithms

從表2 可以看出，改進的半監督聚類算法在AUC 指標上，在pima 數據集上表現接近其他不平衡分類算法，其原因可能為CS-K-Means 利用式（2）重點將樣本劃分到少數類簇，因此提高了少數類的預測概率；同時利用改進的目標函數控制簇的迭代過程，使算法適時收斂，得到了相對最優簇劃分。C_SVM 在2 個指標上的平均結果表現也要優于SVM，這表明了改進的半監督聚類算法提供的偽標簽樣本對于發掘數據底層分布特征的作用。本文算法通過式（7）融合SVM 和改進的半監督聚類算法，平均結果優于CS-K-Means 和C_SVM，算法的不平衡分類性能得到進一步提高，充分體現了融合算法的效果。

在AUC 指標上，本文算法在6 個數據集上得到了最優結果，并取得最高的平均結果，在ecoli-0-4-6vs5 上優勢更加明顯。分析其原因為得益于半監督聚類得到了該數據集的原始分布特征，并補充偽標簽樣本和引入符合原始分布的人造樣本，在減少了不平衡的情況下很少引入噪聲數據，這充分說明本文利用偽標簽樣本，有助于發現更多的少數類邊緣樣本分布特征，從而推動決策面向有利于少數類的方向移動。

在G-mean 指標上，本文算法在5 個數據集上得到了最優結果，同時也取得了最高的平均結果。在ijcnn1 數據集上，由于該數據集所含樣本數很大，CS-K-Means 在G-mean 指標上表現較差，分析其原因可能是該樣本多數類樣本數量遠多于少數類樣本，可能存在樣本重疊的情況，導致CS-K-Means無法得到有效的簇。但是本文算法最終的結果卻未嚴重受到其影響，這說明通過式（8）可以綜合基分類器的性能，提高算法的魯棒性。在數據集abalone19 上，SVM 無法識別出少數類樣本；而欠采樣算法TU 相較于其他過采樣算法在AUC和G-mean 上都表現較差。可能由于該數據集不平衡率非常大，通過大批量刪除多數類樣本取得數據集的平衡，很容易刪除掉大批信息豐富的樣本，造成性能的下降；而過采樣避免了這一問題，通過補充少數類樣本數量，大部分還是取得了不錯的表現。

4 結語

本文提出一種改進的半監督聚類算法，并利用該算法來輔助不平衡分類。首先，針對傳統的半監督聚類算法在質心迭代中由于噪聲引起的性能下降問題，本文提出一種改進的目標函數來約束質心迭代。其次，提出一種新型的重采樣方法：利用改進的半監督聚類來補充少數類的偽標簽樣本。最后，結合半監督聚類與分類的結果進行最終預測，以進一步提升模型的不平衡分類性能。在與6 個基于過采樣和1 個基于欠采樣的不平衡分類算法的實驗對比中，本文算法在AUC和G-mean 指標上均獲得了最優的平均結果。這些實驗結果表明，基于改進的半監督聚類的不平衡分類算法有助于提高少數類樣本的識別率?？紤]到偽標簽樣本中可能存在的噪聲問題，計劃在下一步的研究中結合自步學習（Self-Paced Learning，SPL）技術來降低偽標簽樣本中的噪聲影響，從而進一步提高不平衡分類性能。