基于CPD-SMOTE的類不平衡數(shù)據(jù)分類算法研究

彭如香 楊 濤 孔華鋒 姜國(guó)慶 凡友榮

(公安部第三研究所 上海 201204) (信息網(wǎng)絡(luò)安全公安部重點(diǎn)實(shí)驗(yàn)室 上海 201204)

0 引 言

類不平衡是指屬于某一類別的觀測(cè)樣本的數(shù)量顯著少于其他類別，通常情況下把多數(shù)類樣本的比例為100∶1、1 000∶1，甚至是10 000∶1這種情況下為不平衡數(shù)據(jù)[1]。類不平衡現(xiàn)象普遍存在著不同應(yīng)用領(lǐng)域中，如金融欺詐、網(wǎng)絡(luò)入侵、垃圾郵件過(guò)濾、醫(yī)學(xué)檢測(cè)，直接采用傳統(tǒng)的學(xué)習(xí)分類算法，分類準(zhǔn)確率較低[1-3]。通常采用重采樣方法處理類不平衡問(wèn)題,重采樣包括欠采用和過(guò)采樣兩種[1]。相比于傳統(tǒng)欠采樣方法，SMOTE算法克服傳統(tǒng)隨機(jī)欠采樣導(dǎo)致的數(shù)據(jù)丟失問(wèn)題。但是，SMOTE容易出現(xiàn)過(guò)泛化和高方差的問(wèn)題，進(jìn)而影響數(shù)據(jù)分布特征。為了解決這些問(wèn)題，Borderline-SMOTE、ADASYN、LN-SMOTE等SMOTE改進(jìn)算法相繼被提出[4-6]。這些算法充分考慮小樣本的分布，新增的樣本不影響小樣本的分布。然而這些算法未考慮小樣本與大樣本的交叉區(qū)域，最終形成的數(shù)據(jù)集將改變?cè)袛?shù)據(jù)集的分布，而影響分類算法的準(zhǔn)確性。

1 相關(guān)工作

1.1 SMOTE算法

SMOTE，即合成少數(shù)類過(guò)采樣技術(shù)[1]。該算法由Chawla于2002年提出，是對(duì)隨機(jī)過(guò)采樣算法的一種改進(jìn)。SMOTE算法的基本思想是對(duì)少數(shù)類樣本進(jìn)行分析和人工模擬，同時(shí)將模擬得到的新樣本數(shù)據(jù)添加到原始數(shù)據(jù)集當(dāng)中，使得數(shù)據(jù)正負(fù)樣本比例均衡。

SMOTE算法流程如下：

(1) 對(duì)于少數(shù)類樣本中每一個(gè)樣本x，通過(guò)計(jì)算x到該類樣本集所有樣本的歐式距離，利用KNN算法，選出離樣本x最近的k個(gè)同類樣本點(diǎn)，得到其K近鄰。

(2) 根據(jù)正負(fù)樣本比例確定采樣倍率為N，對(duì)每一個(gè)樣本x分別隨機(jī)從K近鄰中選取N個(gè)樣本，假設(shè)選擇的近鄰為x1,x2,…,xN。

SMOTE算法的出現(xiàn)，改進(jìn)了處理非平衡數(shù)據(jù)中傳統(tǒng)的隨機(jī)過(guò)采樣算法，可以有效地對(duì)非平衡數(shù)據(jù)進(jìn)行糾偏，整體上提高了模型的精度，同時(shí)還很大程度上降低了模型的誤識(shí)率，這是SMOTE算法的優(yōu)點(diǎn)[9]。其缺陷是無(wú)法解決非平衡數(shù)據(jù)的分布問(wèn)題，容易產(chǎn)生分布邊緣化問(wèn)題，對(duì)于邊緣的少類樣本，對(duì)其進(jìn)行K近鄰生成樣本也位于邊緣且會(huì)越來(lái)越邊緣化，這會(huì)使得正負(fù)樣本的邊界越來(lái)越模糊，加大樣本分類的難度。

1.2 類不平衡算法評(píng)價(jià)指標(biāo)

根據(jù)不同的應(yīng)用場(chǎng)景，分類器考慮的評(píng)價(jià)指標(biāo)也不同，通?；诨煜仃囘M(jìn)行性能評(píng)價(jià)?；煜仃嚨亩x如表1所示[7]：

表1 混淆矩陣定義

使用混淆矩陣可以得到如下幾個(gè)評(píng)價(jià)指標(biāo)：

精確度Accuracy=(TP+TN)/(TP+FN+FP+TN)

召回率R=TP/(TP+FN)

準(zhǔn)確度P=TP/(TP+FP)

召回率和準(zhǔn)確度通常會(huì)出現(xiàn)矛盾，這樣需要綜合考慮，最常見(jiàn)的方法就是F-Measure(又稱為F-Score)。 F-Measure是Precision和Recall加權(quán)調(diào)和平均，其定義如下：

另外，可以通過(guò)ROC曲線評(píng)價(jià)一個(gè)分類器好壞。ROC曲線是基于樣本的真實(shí)類別和預(yù)測(cè)概率來(lái)畫的，具體來(lái)說(shuō)，ROC曲線的x軸是偽陽(yáng)性率(FP/(TN+FP))，y軸是真陽(yáng)性率(TP/(TP+FN))；AUC(Area Under Curve)被定義為ROC曲線下的面積。簡(jiǎn)單地說(shuō)，AUC值越大的分類器，正確率越高。

2 CPD-SMOTE類不平衡數(shù)據(jù)處理算法

通過(guò)上述介紹，SMOET算法充分考慮小樣本的分布，新增的樣本不影響小樣本的分布。然而該算法未考慮小樣本與大樣本的交叉區(qū)域，最終形成的數(shù)據(jù)集將改變?cè)袛?shù)據(jù)集的分布，而影響分類算法的準(zhǔn)確性[5-6]。

本文提出一種改進(jìn)型SMOET——CPD-SMOTE。CPD-SMOTE通過(guò)考慮訓(xùn)練集小樣本Si的特征、位置及其周圍樣本分布，來(lái)確定Si的強(qiáng)相關(guān)鄰居集SCNi。以SCNi作為SMOTE最近鄰居集，產(chǎn)生新的小樣本。這里強(qiáng)相關(guān)鄰居集SCNi滿足：

1)SCNi每個(gè)元素都為小樣本特征向量；

2) 對(duì)于SCNi每個(gè)元素Ck，Ck與Si組成的超矩陣中不包含大樣本特征向量。

其算法如下：

算法1強(qiáng)相關(guān)鄰居集確定算法

輸出：所有小樣本的強(qiáng)相關(guān)鄰居集{SCN1，SCN2,…,SCNs}。

4: i=1;

5: For j in[2,s]

6: 判斷zi與zj組成超矩陣中，是否包含Λ中的值；

7: 若不包含，則將zj加入到SCNi集合中；

8: Fori in[2,s-1]

9: For j in[1,i-1]

10: 判斷SCNj中是否包含zi

11: 若包含，則將zi加入到SCNj集合中；

12: For j in[i+1,s]

13: 判斷zi與zj組成超矩陣中，是否包含Λ中的值；

14: 若不包含，則將zj加入到SCNi集合中；

15: i=s;

16: For j in[1,s-1]

17: 判斷SCNj中是否包含zi

18: 若包含，則將zi加入到SCNj集合中；

19: 若不包含，則將zj加入到SCNi集合中；

20: 計(jì)算非空強(qiáng)相關(guān)鄰居集中元素?cái)?shù)量平均值k;

21: 對(duì)于所有為空的強(qiáng)相關(guān)鄰居集SCNi

22: 從大樣本集Λ中隨機(jī)挑選k個(gè)zi(小樣本)的最近鄰居Λ′

23: 對(duì)于Λ′中的所有uj

24: 取α為n維向量，元素取值為[0,0.5]之間的隨機(jī)值；

25:znew=zi+(uj-zi)×α

26: 將znew加入到SCNi中

下面通過(guò)二維圖簡(jiǎn)單說(shuō)明強(qiáng)相關(guān)鄰居節(jié)點(diǎn)選擇方法，如圖1所示。

圖1 小樣本x1的強(qiáng)相關(guān)鄰居節(jié)點(diǎn)選擇示意圖

圖1中，實(shí)心圓表示小樣本節(jié)點(diǎn)，空心圓表示大樣本節(jié)點(diǎn)。通過(guò)上述強(qiáng)相關(guān)鄰居集確定算法，判斷x2是否是x1的強(qiáng)相關(guān)節(jié)點(diǎn)的依據(jù)是由x2與x1組成的超矩陣中，是否包含大樣本節(jié)點(diǎn)確定的。從圖中看出x2滿足該條件，故可將x2加入x1的強(qiáng)相關(guān)鄰居集SCN1中。同理，x3也為SCN1的元素，而x4將不會(huì)被選到SCN1中。雖然x4到x1的距離小于x3,但是x4與x1之間存在大樣本節(jié)點(diǎn)。若不考慮大樣本節(jié)點(diǎn)的存在，采用傳統(tǒng)的SMOTE,在x4與x1連線上隨機(jī)產(chǎn)生新的節(jié)點(diǎn)，將影響大樣本的分布，進(jìn)而影響整個(gè)樣本空間的分布。采用本文中的提出強(qiáng)相關(guān)鄰居集確定算法，x4將不會(huì)被納入到SCN1。然后，將SCN1作為SMOTE算法中鄰居集產(chǎn)生新的小樣本節(jié)點(diǎn)仍服從原來(lái)的分布。對(duì)于x5，根據(jù)上述判斷條件，將不存在符合條件的鄰居，所得到的強(qiáng)相關(guān)鄰居集為空?？紤]到這種情況，本算法充分考慮節(jié)點(diǎn)鄰居數(shù)量均衡的特點(diǎn)，首先計(jì)算非空強(qiáng)相關(guān)鄰居集中元素?cái)?shù)量平均值k，然后從大樣本集中隨機(jī)挑選k個(gè)x5最近鄰居，其次從x5與每個(gè)鄰居的連線不超過(guò)一半(x5為起點(diǎn))上隨機(jī)挑選一個(gè)點(diǎn)作為x5的強(qiáng)相關(guān)鄰居。至此，每個(gè)小樣本的強(qiáng)相關(guān)鄰居集都已確定。接下來(lái)將得到的強(qiáng)相關(guān)鄰居集作為SMOTE算法中鄰居集，完成新樣本的生成，其算法過(guò)程如下：

算法2CPD-SMOTE算法

1: 設(shè)α為n維向量，元素取值為[0,1]之間的隨機(jī)值；

2: 使用上述強(qiáng)相關(guān)鄰居集確定算法，得出強(qiáng)相關(guān)鄰居集{SCN1，SCN2,…,SCNs}

3: Fori從1到N

4: 隨機(jī)挑選小樣本Φ中的點(diǎn)zj：

5: 對(duì)于SCNi中元素zj

6:znew=zi+(zj-zi)×α

7: 將這些新的點(diǎn)加入S中

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)采用來(lái)自Kaggle上的兩個(gè)數(shù)據(jù)集，paySim和CreditCard Fraud Detection。

數(shù)據(jù)集paySim一種移動(dòng)金融交易數(shù)據(jù)數(shù)據(jù)集，該數(shù)據(jù)集包括總樣本數(shù)6 362 620個(gè)，其中正常交易樣本數(shù)為6 354 407，欺詐交易樣本數(shù)為8 237個(gè)，比例為772∶1。paySim數(shù)據(jù)集字段表如表2所示。

表2 字段含義表

數(shù)據(jù)集CreditCard Fraud Detection為信用卡交易數(shù)據(jù)。該數(shù)據(jù)集包含兩天內(nèi)發(fā)生的交易，其中284 807筆交易中有492筆被盜刷。數(shù)據(jù)集為不平衡數(shù)據(jù)集，類(被盜刷)占所有交易的0.172%。它只包含作為PCA轉(zhuǎn)換結(jié)果的數(shù)字輸入變量。該數(shù)據(jù)集屬性除了時(shí)間和金額保留原始值，其他屬性采用PCA轉(zhuǎn)換進(jìn)行了變換，轉(zhuǎn)換特征V1，V2，…,V28，特征“Class”為響應(yīng)變量，如果發(fā)生被盜刷，則取值1，否則為0。

通過(guò)上述分析，這兩類數(shù)據(jù)均為不平衡數(shù)據(jù)集。

3.2 實(shí)驗(yàn)分析

paySim數(shù)據(jù)集和CreditCard Fraud Detection數(shù)據(jù)集都給出了目標(biāo)列，為監(jiān)督學(xué)習(xí)的應(yīng)用場(chǎng)景。是否是欺詐交易或信用卡是否被盜刷是一個(gè)二元分類問(wèn)題，本文選用基分類算法是支持向量機(jī)SVM算法作為基分類器[7-8]。

為了驗(yàn)證CPD-SMOTE算法與其他幾種類不平衡處理算法SMOTE、Borderline-SMOTE、ADASYN、LN-SMOTE的性能，本文構(gòu)建的分類算法模型首先分別通過(guò)這些算法將數(shù)據(jù)進(jìn)行類平衡處理，使得數(shù)據(jù)正負(fù)樣本比例均衡。然后分別采用SVM算法對(duì)數(shù)據(jù)分類，并采用10倍交叉驗(yàn)證方法驗(yàn)證模型的性能。這里SVM算法采用skik-learn算法集中，表3-表5分別給出了不同算法在兩個(gè)數(shù)據(jù)集上評(píng)測(cè)指標(biāo)均值，包括召回率R、F-Measure與AUC均值。實(shí)驗(yàn)結(jié)果表明，相比其他類平衡處理算法，CPD-SMOTE算法效果明顯，學(xué)習(xí)性能更優(yōu)。

表3 基分類器為SVM下的不同算法的召回率R均值

表4 基分類器為SVM下的不同算法的F-Measure均值

表5 基分類器為SVM下的不同算法的AUC均值

4 結(jié) 語(yǔ)

針對(duì)類不平衡情況對(duì)分類器的影響，本文在SMOTE算法的基礎(chǔ)上，提出了CPD-SMOTE算法。該算法通過(guò)考慮訓(xùn)練集小樣本的特征、位置及其周圍樣本分布，來(lái)確定小樣本的強(qiáng)相關(guān)鄰居集，以此作為SMOTE最近鄰居集，產(chǎn)生新的小樣本，實(shí)現(xiàn)數(shù)據(jù)正負(fù)樣本比例均衡，并采用SVM算法對(duì)數(shù)據(jù)進(jìn)行分類預(yù)測(cè)。在相同的基分類器SVM情況下，相比其他4種算法(SOMTE、Borderline-SMOTE、ADASYN、LN-SMOTE)，CPD-SMOTE算法在處理不平衡問(wèn)題時(shí)能提升分類性能。