郭華平,周 俊,鄔長安,范 明

(1.信陽師范學(xué)院 計算機與信息技術(shù)學(xué)院,河南 信陽 464000; 2.鄭州大學(xué) 信息工程學(xué)院,鄭州 450000)(*通信作者電子郵箱hpguo_cm@163.com)

0 引言

非平衡類問題是機器學(xué)習(xí)與模式識別中的一個重要研究方向[1],其表現(xiàn)為一個類的實例數(shù)(多數(shù)類或者負類)遠多于另一個類(少數(shù)類或者正類)的實例數(shù)[2]。在一些實際應(yīng)用中,正確識別少數(shù)類實例往往比正確識別多數(shù)類實例更具價值,如在信用欺詐檢測中,只有少數(shù)案例屬于欺詐案例,如何正確識別這些欺詐案例更加重要[3]。然而傳統(tǒng)分類方法如k近鄰、決策樹、后饋神經(jīng)網(wǎng)絡(luò)、支持向量機等通常試圖學(xué)習(xí)具有高準確率的分類模型,這往往導(dǎo)致學(xué)習(xí)到的模型不能充分考慮到少數(shù)類實例的特征,進而忽略甚至錯誤分類少數(shù)類實例[4]。實際上,針對非平衡類問題,準確率不是一個理想的評價指標,召回率(recall)、g-mean、 f-measure以及AUC(Area Under ROC Curve)等常用于評估算法在非平衡類問題上的性能[5]。

處理非平衡類問題的方法大致可以分為兩類[6]:

1)基于數(shù)據(jù)的方法。通過對訓(xùn)練集重抽樣以平衡數(shù)據(jù)集的分布,進而使學(xué)習(xí)到的模型更傾向于發(fā)現(xiàn)少數(shù)類特征。該方法不需要對算法本身作過多調(diào)整,只需對數(shù)據(jù)集進行針對性處理。常用的基于數(shù)據(jù)的方法可分為兩種類型:a)重采樣,旨在通過對數(shù)據(jù)集重新采樣以減小類不平衡對分類造成的不利影響,通常分為過抽樣、欠抽樣和組合抽樣三種方法。過抽樣通過創(chuàng)建新的少數(shù)類樣本來平衡訓(xùn)練數(shù)據(jù)集,如隨機過抽樣[7]和合成少數(shù)類過抽樣(Synthetic Minority Over-sampling TEchnique, SMOTE)算法[8]等,其中SMOTE是一種廣泛使用的過抽樣技術(shù),其在少數(shù)類樣本及其同類近鄰樣本的連線上創(chuàng)建新的少數(shù)類樣本以平衡數(shù)據(jù)分布。欠抽樣通過移除一些多數(shù)類樣本以平衡訓(xùn)練數(shù)據(jù)集,如隨機欠抽樣、EasyEnsamble[9]等。組合抽樣則是二者的組合[10]。b)數(shù)據(jù)空間加權(quán)，旨在通過利用誤分類代價信息來調(diào)整訓(xùn)練集分布。Wang等[11]基于此使用非對稱誤分類代價矩陣提出了一種基于SVM的組合分類方法。

2)基于算法的方法。通過調(diào)整已有算法的學(xué)習(xí)過程以增強分類器識別少數(shù)類的能力。該方法需要對算法本身及其應(yīng)用領(lǐng)域有深刻的理解,并了解其在不平類問題上適應(yīng)性差的原因。常用的方法包括使用核變換以增強分類器的區(qū)分能力[12],將訓(xùn)練目標轉(zhuǎn)換為傾向于正確分類少數(shù)類實例的目標函數(shù)[13]等。

針對非平衡類問題,本文提出一種基于劃分的k近鄰(Partition-basedk-Nearest Neighbor, PkNN)算法以提高k近鄰模型在少數(shù)類上的性能，它是一種特殊的基于數(shù)據(jù)的非平衡類學(xué)習(xí)算法。在學(xué)習(xí)階段,PkNN使用劃分算法(如K-Means、層次聚類等)劃分多數(shù)類數(shù)據(jù)集為多個簇,然后將少數(shù)類數(shù)據(jù)集分別與每個簇合并構(gòu)成一組新的訓(xùn)練數(shù)據(jù)集,在每個新的訓(xùn)練集上訓(xùn)練一個k近鄰模型,因此,該方法構(gòu)造了一個包含多個k近鄰模型的分類器庫。之所以這樣做的原因是:劃分后,在合并的數(shù)據(jù)集上,多數(shù)類和少數(shù)類實例的分布更加均衡,如圖1所示。在預(yù)測階段,使用劃分算法K均值(K-Means)算法、層次聚類(Hierarchical Clustering, HC)等從分類器庫中選擇一個模型用于預(yù)測待分類樣本的類別。另外,為了提高模型性能,將SMOTE應(yīng)用到PkNN的學(xué)習(xí)過程中。KEEL數(shù)據(jù)集[14]上的實驗結(jié)果表明,PkNN能有效提高k近鄰分類方法在評價指標recall、g-mean、 f-measure和AUC上的性能;同時,過抽樣能進一步提高k近鄰的泛化能力,并明顯優(yōu)于其他高級算法。

圖1 多數(shù)類數(shù)據(jù)集劃分前后數(shù)據(jù)的特征

1 面向非平衡類的k近鄰分類算法

1.1 PkNN算法流程與偽碼

圖2給出了PkNN模型學(xué)習(xí)和預(yù)測過程示意圖。在學(xué)習(xí)(訓(xùn)練)階段,PkNN首先處理數(shù)據(jù)集,采用劃分算法(如K-Means)將多數(shù)類數(shù)據(jù)集Dmaj劃分為m個簇{Ci|i=1, 2,…,m}使得∪Ci=Dmaj,Ci∩Cj=?,i≠j;然后,PkNN將少數(shù)類數(shù)據(jù)集Dmin分別與每個簇Ci合并得到一個新的訓(xùn)練集Cnew,i=Dmin∪Ci,并在Cnew,i上學(xué)習(xí)一個k近鄰分類模型kNNi。因此PkNN學(xué)習(xí)了一個包含m個k近鄰模型的分類器庫。在預(yù)測階段,PkNN使用學(xué)習(xí)階段學(xué)習(xí)的劃分模型從分類器庫中選擇模型預(yù)測未知類標號樣本x的類別。

算法1給出了PkNN算法偽代碼。在訓(xùn)練階段,PkNN首先將訓(xùn)練數(shù)據(jù)集分離為多數(shù)類和少數(shù)類兩部分(第1)行),并將多數(shù)類數(shù)據(jù)集劃分為m個簇(第2)行);然后,PkNN將每個簇和少數(shù)類數(shù)據(jù)集合并得到一個新的訓(xùn)練集,用于訓(xùn)練一個k近鄰模型(第3)～6)行)。在預(yù)測階段,PkNN使用劃分階段學(xué)習(xí)的劃分方法將待預(yù)測樣本x映射到相應(yīng)的簇(第7)行),使用相應(yīng)的k近鄰模型預(yù)測x的類標號(第8)行)。

圖2 PkNN模型學(xué)習(xí)和預(yù)測過程示意圖

算法1 PkNN算法。

訓(xùn)練階段:

輸入 訓(xùn)練集D;劃分的簇數(shù)目m。

輸出 預(yù)測模型PkNN。

1) 設(shè)Dmaj和Dmin分別為D中的多數(shù)類和少數(shù)類集合;

2)C=Partition(Dmaj,m);

//劃分Dmaj為m個簇,即:C={Ci|i=1, 2,…,m}

3) forCiinCdo

4)Cnew,i=Ci∪Dmin;

5)kNNi= Learner(Cnew,i);

6) end for

預(yù)測階段:

輸入 待分類樣本x;kNN模型近鄰數(shù)k。

輸出 樣本x所屬類別y。

7)γ=Partition(x);

//取得x所屬的簇標號;

8)y=kNNγ(x,k)

//在相應(yīng)kNN模型中預(yù)測x的類別;

returny

算法1中值得注意的是如何選擇劃分方法(第2)行和第7)行)。本文分別采用K-Means算法、隨機劃分法以及層次聚類方法劃分多數(shù)類數(shù)據(jù)集。

1.2 基于K-Means數(shù)據(jù)劃分法

K-Means算法是一種經(jīng)典的聚類算法,因其簡單、適應(yīng)性強的特點,廣泛應(yīng)用于多種實際問題當中[15]。該算法是一種基于平方誤差的聚類算法[16],對于給定的樣本集D={x1,x2, …,xn},算法的最終目標是學(xué)習(xí)到的簇C={C1,C2, …,Cm}具有最小化平方誤差,形式化地:

(1)

其中:

(2)

μj為簇Cj簇心(均值向量);|Cj|為簇Cj中樣本的個數(shù)。直觀地看,式(1)在一定程度上刻畫了簇內(nèi)樣本圍繞簇心的緊密程度,值越小則簇內(nèi)樣本相似度越高。

K-Means采用迭代方法來近似優(yōu)化式(1),具體過程如下:1)從D中任選m個樣本作為初始簇心{μ1,μ2,…,μm};2)對于每個樣本xi∈D,計算其與各簇心μj(1≤j≤m)的距離dij=‖xi-μj‖,并將xi歸并到具有最小距離diλ對應(yīng)的簇Cλ中,即Cλ=Cλ∪ {xi};3)重復(fù)過程2)直到D中所有樣本都處理完畢;4)利用式(2)更新每個簇的簇心,若μj′≠μj則更新簇心μj為μj′,否則保持簇心不變;5)重復(fù)步驟2)～4),直至所有簇的簇心都不再變化。

本文算法PkNN將K-Means算法應(yīng)用到多數(shù)類樣本集的劃分過程中(參見算法1第2)行),并使用歐氏距離計算樣本與簇心間的距離,形式化地

(3)

同樣地,在預(yù)測階段,PkNN使用歐氏距離(式(3))預(yù)測樣本x所屬簇的標號γ(參見算法1第7)行),即

(4)

然后使用相應(yīng)的模型kNNγ預(yù)測待測樣本x的類標號。

圖3 KM-kNN在四個數(shù)據(jù)集上的性能與m取值的關(guān)系

圖4 KM-kNN在四個數(shù)據(jù)集上的性能與k取值的關(guān)系

1.3 隨機數(shù)據(jù)劃分法

隨機劃分法是最簡單的一種數(shù)據(jù)劃分方法,其將任意一個多數(shù)類樣本隨機地劃分到某一個簇中,即對于每一個樣本x∈Dmaj,在區(qū)間[1,m]內(nèi)隨機對x賦以一個簇標號λ,再x將并入相應(yīng)的簇Cλ=Cλ∪{x}中,即可完成對Dmaj的隨機劃分。

本文算法PkNN將隨機劃分方法應(yīng)用到多數(shù)類數(shù)據(jù)集的劃分過程中(參見算法1第2)行)。為了算法預(yù)測方便,本文使用式(2)計算每個劃分的中心。在預(yù)測階段,PkNN使用式(3)(歐氏距離)和式(4)獲得樣本x距離最近的簇的簇標號γ(參見算法1第7)行),然后采用相應(yīng)的預(yù)測模型kNNγ預(yù)測樣本x所屬的類別。

1.4 基于層次聚類數(shù)據(jù)劃分法

層次聚類(Hierarchical Clustering, HC)也是一種廣泛使用的聚類算法,其在不同的層次對數(shù)據(jù)集進行聚類,從而形成樹形的聚類結(jié)構(gòu)[17]。本文算法PkNN采用自下而上凝聚策略的層次聚類劃分多數(shù)類數(shù)據(jù)集:首先將數(shù)據(jù)集中每一個樣本看作一個初始簇,然后在算法運行的每一步中找出距離最近的兩個簇進行合并,不斷重復(fù)該過程,直至達到預(yù)設(shè)的簇個數(shù)。PkNN采用簇間最小距離來度量兩個簇之間的距離,形式化地:

d(Ci,Cj)=

其中dist(x,z)為樣本x和z的歐氏距離。與隨機數(shù)據(jù)劃分法類似,為了算法預(yù)測方便,本文使用式(2)計算每個簇的中心。在預(yù)測階段,PkNN使用式(3)(歐氏距離)計算待預(yù)測樣本x與簇心的距離,根據(jù)最近距離確定x所屬的簇標號γ,然后采用相應(yīng)的預(yù)測模型kNNγ預(yù)測樣本x所屬的類別。

2 參數(shù)學(xué)習(xí)

在算法1中,需要注意兩個輸入?yún)?shù),即劃分多數(shù)類數(shù)據(jù)集的簇數(shù)m和kNN的近鄰數(shù)k。本章使用K-Means算法作為劃分方法討論這兩個參數(shù)。

圖3展示了在四個數(shù)據(jù)集上m(簇數(shù))對模型性能的影響，其中KM-kNN表示使用K-Means對數(shù)據(jù)進行劃分，然后直接在劃分后的數(shù)據(jù)集上學(xué)習(xí)k近鄰模型(參考3.1節(jié))。圖3結(jié)果獲得方式:在數(shù)據(jù)集上執(zhí)行10次10折交叉驗證,并將模型性能的平均值作為最終輸出結(jié)果。這里設(shè)置近鄰數(shù)k=3。

從圖3可以看出,劃分方法能有效提高k近鄰模型在非平衡類問題上的性能(m=1表示直接在未劃分的實例集上學(xué)習(xí)k近鄰模型)。另外,通過觀察圖3可以發(fā)現(xiàn)當m=「Nmaj/Nmin×2?(Nmaj和Nmin分別表示數(shù)據(jù)集多數(shù)類與少數(shù)類樣本的個數(shù))時,模型在四個數(shù)據(jù)集上均取得較好的分類性能。該結(jié)果與期望結(jié)果m=Nmaj/Nmin(每個簇的樣本數(shù)與少數(shù)類樣本數(shù)比例為1∶1)并不一致,其原因是:劃分算法不能保證各個簇大小相當,其中一些小簇樣本數(shù)可能遠小于少數(shù)類樣本數(shù),這會降低模型的性能。故在后面的實驗中,本文取其劃分的簇數(shù)為m=「Nmaj/Nmin×2?。

圖4展示了在四個數(shù)據(jù)集上k(近鄰數(shù))對模型在recall、g-mean、 f-measure和AUC性能上的影響。圖4所有的結(jié)果獲得方法與圖3一致。從圖4可看出，當k取值為3時,四個模型的分類性能均可達到較優(yōu)的效果,故本文取定k=3,并將其應(yīng)用到后續(xù)的實驗中。

表2 kNN、KM-kNN、R-kNN和HC-kNN在recall、g-mean、 f-measure和AUC上性能比較

注:性能最優(yōu)的結(jié)果加粗表示。

表1 實驗數(shù)據(jù)集

3 實驗

3.1 數(shù)據(jù)集和實驗設(shè)置

本文從KEEL機器學(xué)習(xí)數(shù)據(jù)庫中隨機選取16個非平類數(shù)據(jù)集進行實驗,數(shù)據(jù)集的相關(guān)描述如表1所示,其中Exs、Atts和IR分別表示數(shù)據(jù)集的實例個數(shù)、屬性個數(shù)和不平衡度(多數(shù)類與少數(shù)類實例數(shù)目的比例)。對于每個數(shù)據(jù)集,采用10次10折交叉驗證來測試模型的分類性能,因此,在每個數(shù)據(jù)集合上實際共計構(gòu)建了100個模型。

為評估本文提出的面向非平衡類問題的k近鄰分類算法的分類性能,本文設(shè)計了兩組實驗:

1)PkNN的三種具體實現(xiàn)模型KM-kNN、R-kNN和HC-kNN與傳統(tǒng)的kNN模型相比較：KM-kNN表示基于K-Means數(shù)據(jù)劃分法的k近鄰分類算法；R-kNN表示基于隨機數(shù)據(jù)劃分法的k近鄰分類算法；HC-kNN表示基于層次聚類的k近鄰分類算法。

2)將過抽樣技術(shù)SMOTE應(yīng)用到PkNN中,檢測抽樣技術(shù)對PkNN的影響,選擇KM-kNN作為PkNN算法的代表。

過抽樣技術(shù)設(shè)置劃分簇數(shù)m=「Nmaj/Nmin×2?,k近鄰中的近鄰數(shù)k=3,其中Nmaj和Nmin分別表示多數(shù)類和少數(shù)類實例數(shù)(參見第2章)。

3.2 PkNN的性能

為評估本文算法的分類性能,把提出的面向不平衡類問題的k近鄰分類方法的三種具體模型(即KM-kNN、R-kNN和HC-kNN)與kNN算法進行比較。

表2顯示了模型分別在評估指標recall、g-mean、 f-measure和AUC上的性能。從表2可看出：本文提出的面向非平衡類問題的分類算法的三種具體模型各項指標平均值良好，且相差不大。傳統(tǒng)kNN算法僅在f-measure指標中有一次在id10中是最優(yōu)的(id5中與HC-kNN并列最優(yōu))，所有指標中的平均值均最差。該實驗結(jié)果表明,本文算法能很好地適應(yīng)不平衡類環(huán)境,有效地提高了模型識別少數(shù)類樣本的能力。本文算法對模型分類性能影響的關(guān)鍵因素是對數(shù)據(jù)集進行劃分,而非具體某種劃分方法。

3.3 抽樣技術(shù)對PkNN的影響

為了檢測抽樣技術(shù)對PkNN的影響,本文將KM-kNN與SMOTE相結(jié)合,并比較算法KM-kNN、SM-kNN和SM-KM-kNN的性能:

1)KM-kNN(K-Means+kNN)為表示基于K-Means數(shù)據(jù)劃分法的k近鄰分類算法(參考3.1節(jié))。

2)SM-kNN(SMOTE+kNN)為使用SMOTE直接預(yù)處理原始訓(xùn)練數(shù)據(jù)集,然后在處理過的數(shù)據(jù)集上學(xué)習(xí)k近鄰模型。

3)SM-KM-kNN(SMOTE+KM-kNN)為KM-kNN在學(xué)習(xí)每個k近鄰模型前,使用SMOTE過抽樣方法處理新創(chuàng)建的訓(xùn)練數(shù)據(jù)集(算法1第4)行和第5)行之間),然后學(xué)習(xí)k近鄰模型。

表3給出了KM-kNN、SM-kNN和SM-KM-kNN在recall、g-mean、 f-measure和AUC上的性能。從表3可以看出：本文提出的PkNN算法(以KM-kNN為例)與SM-kNN性能相當；而SM-KM-kNN的分類性能明顯優(yōu)于前兩者,各項指標的平均值均最優(yōu)。

該結(jié)果表明:1)劃分方法與抽樣技術(shù)對kNN性能提升效果相當;2)SMOTE抽樣技術(shù)能顯著提升PkNN的性能;3)將抽樣技術(shù)和劃分方法有效地結(jié)合能更好地提升k近鄰在非平衡類問題上的性能。

注:性能最優(yōu)的結(jié)果加粗表示。

4 結(jié)語

本文提出一種基于劃分的面向非平衡類問題的k近鄰分類算法。與傳統(tǒng)的k近鄰方法不同,在學(xué)習(xí)階段,該算法使用劃分方法將多數(shù)類數(shù)據(jù)集劃分為多個簇,將每個簇與少數(shù)類數(shù)據(jù)集合并構(gòu)建新的相對平衡的訓(xùn)練集集合;然后在集合的每個成員上訓(xùn)練一個k近鄰模型,進而獲得k近鄰模型庫。在預(yù)測階段,使用學(xué)習(xí)到的劃分方法選擇庫中的模型預(yù)測樣本類標號。另外,還將過抽樣技術(shù)SMOTE應(yīng)用到該算法中,以進一步提高該算法的性能。相關(guān)實驗結(jié)果表明:1)本文算法能顯著提升k近鄰在非平衡類問題上的泛化能力;2)基于劃分的方法與基于SMOTE的過抽樣技術(shù)在處理非平衡問題上的能力相當(針對k近鄰算法);3)SMOTE能進一步提升基于劃分的k近鄰算法在非平衡類問題上的泛化能力。

參考文獻(References)

[1] GUO H, LI Y, SHANG J, et al. Learning from class-imbalanced data: review of methods and applications [J]. Expert Systems with Applications, 2017, 73: 220-239.

[2] LIN W, TSAI C, HU Y, et al. Clustering-based undersampling in class-imbalanced data [J]. Information Sciences, 2017, 409: 17-26.

[3] SANZ J, BERNARDO A D, HERRERA F, et al. A compact evolutionary interval-valued fuzzy rule-based classification system for the modeling and prediction of real-world financial applications with imbalanced data [J]. IEEE Transactions on Fuzzy Systems, 2015, 23(4): 973-990.

[4] CHAWLA N, JAKOWICZ V N, KOTCZ A. Editorial: special issue on learning from imbalanced data sets [J]. ACM Special Interest Group on Knowledge Discovery and Data Mining Explorations, 2004, 6(1): 1-6.

[5] 郭華平, 董亞東, 毛海濤, 等. 一種基于邏輯判別式的稀有類分類方法[J]. 小型微型計算機系統(tǒng), 2016, 37(1): 140-145.(GUO H P, DONG Y D, MAO H T, et al. Logistic discrimination based rare-class classification method[J]. Journal of Chinese Computer Systems, 2016, 37(1): 140-145.)

[6] SUN Y, WONG A K C, KAMEL M S. Classification of imbalanced data: a review [J]. International Journal of Pattern Recognition and Artificial Intelligence, 2009, 23(4): 687-719.

[7] TAHIR M A, KITTLER J, MIKOLAJCZYK K, et al. A multiple expert approach to the class imbalance problem using inverse random under sampling [C]// Proceedings of 8th International Workshop on Multiple Classifier Systems. Berlin: Springer, 2009: 82-91.

[8] CHAWLA N V, BOWYER K W, HALL L O, et al. SMOTE: synthetic minority over-sampling technique [J]. Journal of Artificial Intelligence Research, 2002, 16: 321-357.

[9] LIU X, WU J, ZHOU Z. Exploratory undersampling for class-imbalance learning [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B, 2009, 39(2): 539-550.

[10] LI P, QIAO P, LIU Y. A hybrid re-sampling method for SVM learning from imbalanced data sets [C]// FSKD 2008: Proceedings of the Fifth International Conference on Fuzzy Systems and Knowledge Discovery. Washington, DC: IEEE Computer Society,2008: 65-69.

[11] WANG B X, JAPKOWICZ N. Boosting support vector machines for imbalanced data sets [J]. Knowledge and Information Systems, 2010, 25(1): 1-20.

[12] ZHANG Y, FU P, LIU W, et al. Imbalanced data classification based on scaling kernel-based support vector machine [J]. Neural Computing and Applications, 2014, 25(3/4): 927-935.

[13] GUO H, LIU H, WU C, et al. Logistic discrimination based on G-mean and F-measure for imbalanced problem [J]. Journal of Intelligent and Fuzzy Systems, 2016, 31(3): 1155-1166.

[14] ALCALA-FDEZ J, FERNANDEZ A, LUENGO J, et al. KEEL data-mining software tool: data set repository, integration of algorithms and experimental analysis framework [J]. Journal of Multiple-Valued Logic and Soft Computing, 2011, 17(2/3): 255-287.

[15] OLIVEIRA G V, COUTINHO F P, CAMPELLO R J G B, et al. Improvingk-means through distributed scalable metaheuristics [J]. Neurocomputing, 2017, 246: 45-57.

[16] BERKHIN P. A survey of clustering data mining techniques [J]. Grouping Multidimensional Data, 2006, 43(1): 25-71.

[17] RUI XU, DONALD C. WUNSCH II. Survey of clustering algorithms[J]. IEEE Transactions on Neural Networks, 2005, 16(3): 645-678.