融合聚類過采樣算法的信貸不平衡數(shù)據(jù)分類

樊東醒，葉春明

（上海理工大學 管理學院，上海 200093）

0 引言

不平衡數(shù)據(jù)廣泛存在于信用風險評估［1］、網(wǎng)絡異常監(jiān)測［2］、機械故障診斷［3］和新冠病毒疾病診斷領(lǐng)域［4］，在信用風險評估領(lǐng)域中，若將“壞客戶”誤判為“好客戶”將會造成極大的損失風險。夏利宇等［5］認為，提升模型對不平衡數(shù)據(jù)的分類效果已成為信用評級領(lǐng)域的研究重點之一。

傳統(tǒng)分類器對不平衡數(shù)據(jù)的分類通常傾向于多數(shù)類，如支持向量機（SVM）［6］、K 近鄰算法（KNN）［7］和神經(jīng)網(wǎng)絡［8］等，針對這一問題目前主要有3 種解決方法：抽樣法、代價敏感學習、集成學習分類［9］。代價敏感學習和集成學習方法作用于算法層面，抽樣法作用于數(shù)據(jù)層面，通過插值和抽樣等方式以重新達到類別平衡，通常可與集成學習模型相結(jié)合以提高分類效果。

抽樣法包括過采樣和欠采樣兩種，其中最經(jīng)典的過采樣方法是SMOTE 算法［10］，它通過合成少數(shù)類樣本對抗不平衡，但存在泛化和高方差問題，并影響數(shù)據(jù)分布特征［11］。針對這一問題，Borderline-SMOTE［12］和ADASYN［13］根據(jù)少數(shù)類K 近鄰中危險點數(shù)目調(diào)整采樣策略。Douzas 等［14］提出K-meansSMOTE，其使用K-means 進行聚類分簇采樣，并根據(jù)密度分配采樣權(quán)重，該方法有效緩解了類間不平衡，但是由于K-means 聚類的局限性，存在孤立點敏感和邊界樣本損失問題；針對K-means 聚類，韓旭等［15］指出它會破壞掉兩類數(shù)據(jù)之間的空間結(jié)構(gòu)，從而造成邊界樣本損失。此外，當K-means 應用于不平衡數(shù)據(jù)時存在“均勻效應”，導致邊界樣本被劃分到鄰近大類中［16］。針對以上問題，本文提出了一種融合K 中心點聚類和邊界閾值的過采樣方法，通過確定邊界閾值，選擇適合聚類的區(qū)域范圍，避免遠離類邊界樣本的干擾，并通過改進K 中心點算法使聚類結(jié)果更加“緊湊化”。此外，本文提出了適用于不平衡數(shù)據(jù)的聚類K 值尋優(yōu)方法，并通過實驗驗證了所提方法的有效性。

1 K 中心點算法改進

1.1 K 中心點算法

K 中心點算法是一種針對K-means 孤立點敏感問題提出的改進方法，具體步驟如下：①輸入數(shù)據(jù)集和聚類個數(shù)K；②在樣本中隨機選擇K 個點作為各簇的中心點；③計算其余點到K 個中心點的距離，根據(jù)每個點到K 個中心點的最短距離，劃分到最近的簇；④在每個簇中按照順序依次選取候選點，計算該點到當前簇中所有點的距離之和，將距離代價最小的點作為新的中心點；⑤重復②③④步驟，直到各簇的中心點不再改變；⑥輸出K 個簇。

1.2 改進的K 中心點算法

在使用K-means 等算法劃分類簇時，處于稀疏大形簇邊界上的樣本容易被錯分到鄰近的小簇中，文獻［17］針對這一問題引入了聚類準則函數(shù)和加權(quán)距離進行改進。本文將該方法引入到K 中心點算法的第3 步，從而提高對邊界樣本的聚類精度。

聚類準則函數(shù)以加權(quán)簇內(nèi)標準差之和最小化為目標，在每次迭代時根據(jù)聚類準則函數(shù)大小將數(shù)據(jù)點分配到相應的簇中。設樣本總量為M，第i個簇中樣本個數(shù)為mi，第i個簇的標準差為σi，則聚類準則函數(shù)定義如式（1）所示。

加權(quán)距離計算公式如式（2）所示。

其中，dist(ck,x)表示簇中數(shù)據(jù)點x到中心點ck的距離，ωk表示樣本權(quán)重，式（3）使得密集簇的權(quán)重更高，從而使劃分結(jié)果更加靠近簇中心點，聚類結(jié)果變得緊湊。

2 不平衡數(shù)據(jù)下的K 值尋優(yōu)

2.1 ET-SSE 算法

最佳K 值的選擇對于聚類結(jié)果有著很大影響，為判定最優(yōu)K 值，文獻［18］提出了ET-SSE 算法，通過引入指數(shù)函數(shù)放大正值影響并在簇內(nèi)誤差平方和的基礎上提出了新的度量方式，以提高度量效果。ET-SSE 的計算公式如式（4）所示。

其中，θ為權(quán)重，可調(diào)節(jié)SSE 的大小，Ci表示第i個簇的中心點，p為第i個簇中的樣本對象。

2.2 UET-SSE 算法

不同于ET-SSE 的是，在聚類過采樣算法中，聚類算法僅僅作為預處理步驟，其目的是通過聚類發(fā)現(xiàn)規(guī)則相似的樣本，為接下來的樣本合成步驟提供參考，因此聚類的目標不是區(qū)分兩類樣本，而是將相似度高的樣本進行歸納。因此，本文提出了應用于非平衡數(shù)據(jù)的K 值選取方法UETSSE，它通過計算每個簇內(nèi)的多數(shù)類樣本中心距離與少數(shù)類樣本中心距離的平均比值確定最優(yōu)K 值，計算公式如式（5）所示。

其中，Ci表示第i個簇的中心點，p為第i個簇中的樣本，pm為第i個簇中的少數(shù)類樣本。式（5）中第一項的分子是全體樣本與少數(shù)類樣本的中心距離差，分母為少數(shù)類樣本的中心距離，第一項代表pm周圍的多數(shù)類樣本密度；第二項為偏執(zhí)項，它取第一項結(jié)果中的最大值，用來放大差異。USET在計算USET后可以作圖判斷K 值凹點，以German數(shù)據(jù)集為例計算USET得分并作圖，如圖1 所示，USET隨著K值增大不斷上升，表明分簇越多樣本越稀疏。當K=4 時形成一個明顯的凹點（二階導數(shù)大于0），因此最佳K 值為4。

Fig.1 Optimal K-value judgment圖1 最佳K 值判斷

3 聚類過采樣

3.1 邊界閾值與區(qū)域劃分

KmeansSMOTE 給予稀疏簇更高的采樣權(quán)重，但是沒有規(guī)定決策邊界，容易過度關(guān)注遠離類邊界的稀疏樣本，導致一些孤立點或邊緣點被過度采樣，而邊界樣本采樣過少，具體如圖2 所示。為劃分適合聚類采樣的區(qū)域，本文利用混疊樣本對聚類區(qū)域進行劃分，如圖3 所示，內(nèi)圈為樣本混疊較多，適合深度聚類區(qū)分，外圈為稀疏區(qū)域，過大的歐式距離不適合進行聚類。

Fig.2 KmeansSMOTE sampling results圖2 KmeansSMOTE 采樣結(jié)果

Fig.3 Boundary thresholds and region demarcation圖3 邊界閾值與區(qū)域劃分

邊界閾值計算步驟如下：

（1）計算n個特征與標簽的Pearson 相關(guān)系數(shù)r(fi,y)，得到集合P，將P 中絕對值最大的特征作為關(guān)鍵特征T。

（2）計算少數(shù)類樣本點Xi的K 近鄰，設Xi的K 近鄰中相反類別占比為θ，若0 <θ≤1/3，則將Xi視為邊界支持點，加入集合E，若θ等于1 則作為噪聲點剔除。

（3）計算集合E 中樣本點在T 上的均值作為邊界閾值，XT表示樣本X 在T 上的值，將XT與比較并根據(jù)式（8）劃分內(nèi)圈和外圈。

3.2 加權(quán)過采樣

通常情況下，樣本重要性取決于密集度和信息量，張家偉等［19］指出靠近類別中心和邊界的樣本生成權(quán)重應該更大；田臣等［20］認為邊界樣本和稀疏簇中的少數(shù)類樣本采樣權(quán)重更大。因此，本文在聚類時引入加權(quán)過采樣策略，給予靠近簇中心樣本更高的權(quán)重，具體步驟如下：

（1）通過K 中心點聚類得到K 個簇，對于每個簇C 中的少數(shù)類樣本Xi，計算它到中心點的歐幾里得距離Di，取中心距離的倒數(shù)作為Xi的采樣權(quán)重。

（2）根據(jù)采樣倍率N 確定合成樣本數(shù)目，對每一個少數(shù)類樣本Xi，從其K 近鄰中隨機選擇樣本點Yj，并根據(jù)式（11）合成新樣本。

（3）將新樣本與原始數(shù)據(jù)集合并，得到新數(shù)據(jù)集。

4 KMediods-SMOTE

4.1 算法流程

KMediods-SMOTE 采樣流程如圖4 所示，為檢驗合成效果，本文在合成樣本后輸入分類模型，并使用三折交叉驗證和網(wǎng)格搜索進行調(diào)參，最后驗證分類結(jié)果。

4.2 算法描述

輸入：不平衡數(shù)據(jù)集S，K近鄰數(shù)n，簇最小保留閾值irt。

輸出：合成的樣本數(shù)據(jù)集。

Step1：將原始數(shù)據(jù)集分為訓練集T和驗證集V；

Step2：計算T 中所有少數(shù)類樣本的K近鄰，根據(jù)上文方法得到訓練集X_train和邊界點集合Xd；

Step3：計算需生成樣本的總數(shù)量；

Fig.4 Algorithm flow圖4 算法流程

Step4：根據(jù)邊界閾值劃分聚類區(qū)域與非聚類區(qū)域；

Step4.1：根據(jù)式（6）和式（7）計算邊界閾值；

Step4.2：將小于邊界閾值的樣本劃為內(nèi)圈點，剩余的劃為外圈點，分別記作inner_X和outter_X；

Step5：根據(jù)式（5）確定最優(yōu)K 值，使用改進的K 中心點算法對內(nèi)圈樣本聚類，并將inner_X劃分為K 個簇；

Step6：判斷各簇內(nèi)少數(shù)類樣本數(shù)量是否大于irt，過濾掉較小的簇；

Step7：計算采樣權(quán)重；

Step7.1：計算樣本到簇中心點平均距離的倒數(shù)作為簇間采樣權(quán)重；

Step7.2：根據(jù)式（10）計算簇內(nèi)采樣權(quán)重；

Step8：將邊界支持點X_edge加入outterX，計算外圈點中少數(shù)類樣本的K 近鄰集合以供插值，并根據(jù)內(nèi)圈和外圈中的樣本數(shù)量分配合成數(shù)目；

Step9：分別對內(nèi)圈點和外圈點過采樣，得到合成后的新數(shù)據(jù)集new_X。

5 實驗與分析

5.1 數(shù)據(jù)來源

實驗選取了4 個信用風險數(shù)據(jù)集，由于Credit_card 類別極端不平衡，因此隨機抽取2%的多數(shù)類樣本與少數(shù)類樣本混合組成新數(shù)據(jù)集，數(shù)據(jù)情況如表1 所示。

Table 1 Data description表1 數(shù)據(jù)描述

5.2 評價指標

實驗使用混淆矩陣刻畫分類效果，其定義如表2 所示。由于準確率無法準確評估不平衡數(shù)據(jù)的分類效果，因此實驗選取前人使用較多的G-means和F-measure作為評價指標。式（15）中，β表示Recall和Precision的相對重要性，實驗中通常取值為1。

Table 2 Credit risk assessment confusion matrix表2 信用風險評估混淆矩陣

5.3 實驗設置與分析

實驗使用Python3.7 實現(xiàn)本文算法，并與SMOTE、Bor?derlineSMOTE、KMeansSMOTE 進行比較，在參數(shù)調(diào)優(yōu)后進行五折交叉驗證。為檢驗各方法在集成分類模型下的效果，選擇RF、Adaboost、logistics 3 種分類器進行試驗，各分類器參數(shù)取值范圍如表3所示，分類結(jié)果如表4和表5所示。

Table 3 Parameter range表3 參數(shù)取值范圍

Table 5 F-measures of four kinds of oversampling methods in different classifiers表5 4 種過采樣方法在不同分類器中的F-measure

可以看出，本文方法在RF 分類器下的指標全為最優(yōu)，在天池競賽商業(yè)銀行數(shù)據(jù)上相比KmeansSMOTE 在Gmeans 和F-measure 上提升了1.18%和5.35%，在German 數(shù)據(jù)集上相比KmeansSMOTE 在G-means 上提升了2.03%。但在Credit_card 下的效果與KmeansSMOTE 差別不大，主要是因為Credit_card 數(shù)據(jù)集離散度和混疊度不高，邊界樣本比較集中。4 種方法中，KmediodsSMOT 表現(xiàn)良好，Kmeans?SMOTE 次之，BorderlineSMOTE 和SMOTE 表現(xiàn)最差。

6 結(jié)語

本文針對傳統(tǒng)聚類過采樣算法的邊界樣本損失問題，通過劃分邊界閾值和引入聚類準則函數(shù)改進了K 中心點算法，并提出一種適用于非平衡數(shù)據(jù)的K 值尋優(yōu)方法。通過與較新的KMeansSMOTE 進行對比實驗，表明該算法在非均衡數(shù)據(jù)集上性能較好，并有效地提高了少數(shù)類樣本的分類精度。研究表明，縮小聚類區(qū)域和改進聚類準則函數(shù)可以提高對邊界樣本的采樣權(quán)重，并避免了孤立點和極值點的干擾，從而在聚類過采樣后得到了更好的分類效果。然而本文方法仍然存在一些不足：它并未考慮到數(shù)據(jù)集的混疊度和樣本分布，因此后續(xù)研究有待引入分布函數(shù)以確定樣本密集區(qū)域，并重點對邊界樣本集中區(qū)域使用本文方法，以提高聚類過采樣效果。