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

樊東醒，葉春明

（上海理工大學(xué) 管理學(xué)院，上海 200093）

0 引言

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

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

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

1 K 中心點(diǎn)算法改進(jìn)

1.1 K 中心點(diǎn)算法

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

1.2 改進(jìn)的K 中心點(diǎn)算法

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

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

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

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

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

2.1 ET-SSE 算法

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

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

2.2 UET-SSE 算法

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

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

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

3 聚類過采樣

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

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

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

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

邊界閾值計(jì)算步驟如下：

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

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

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

3.2 加權(quán)過采樣

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

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

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

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

4 KMediods-SMOTE

4.1 算法流程

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

4.2 算法描述

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

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

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

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

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

Fig.4 Algorithm flow圖4 算法流程

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

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

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

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

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

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

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

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

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

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

5 實(shí)驗(yàn)與分析

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

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

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

5.2 評(píng)價(jià)指標(biāo)

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

Table 2 Credit risk assessment confusion matrix表2 信用風(fēng)險(xiǎn)評(píng)估混淆矩陣

5.3 實(shí)驗(yàn)設(shè)置與分析

實(shí)驗(yàn)使用Python3.7 實(shí)現(xiàn)本文算法，并與SMOTE、Bor?derlineSMOTE、KMeansSMOTE 進(jìn)行比較，在參數(shù)調(diào)優(yōu)后進(jìn)行五折交叉驗(yàn)證。為檢驗(yàn)各方法在集成分類模型下的效果，選擇RF、Adaboost、logistics 3 種分類器進(jìn)行試驗(yàn)，各分類器參數(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 分類器下的指標(biāo)全為最優(yōu)，在天池競(jìng)賽商業(yè)銀行數(shù)據(jù)上相比KmeansSMOTE 在Gmeans 和F-measure 上提升了1.18%和5.35%，在German 數(shù)據(jù)集上相比KmeansSMOTE 在G-means 上提升了2.03%。但在Credit_card 下的效果與KmeansSMOTE 差別不大，主要是因?yàn)镃redit_card 數(shù)據(jù)集離散度和混疊度不高，邊界樣本比較集中。4 種方法中，KmediodsSMOT 表現(xiàn)良好，Kmeans?SMOTE 次之，BorderlineSMOTE 和SMOTE 表現(xiàn)最差。

6 結(jié)語(yǔ)

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