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

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

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

0 引言

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

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

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

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

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

圖1 多數類數據集劃分前后數據的特征

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

1.1 PkNN算法流程與偽碼

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

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

圖2 PkNN模型學習和預測過程示意圖

算法1 PkNN算法。

訓練階段:

輸入 訓練集D;劃分的簇數目m。

輸出 預測模型PkNN。

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

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

預測階段:

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

輸出 樣本x所屬類別y。

7)γ=Partition(x);

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

8)y=kNNγ(x,k)

//在相應kNN模型中預測x的類別;

returny

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

1.2 基于K-Means數據劃分法

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

(1)

其中:

(2)

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

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

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

(3)

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

(4)

然后使用相應的模型kNNγ預測待測樣本x的類標號。

圖3 KM-kNN在四個數據集上的性能與m取值的關系

圖4 KM-kNN在四個數據集上的性能與k取值的關系

1.3 隨機數據劃分法

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

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

1.4 基于層次聚類數據劃分法

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

d(Ci,Cj)=

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

2 參數學習

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

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

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

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

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

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

表1 實驗數據集

3 實驗

3.1 數據集和實驗設置

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

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

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

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

過抽樣技術設置劃分簇數m=「Nmaj/Nmin×2?,k近鄰中的近鄰數k=3,其中Nmaj和Nmin分別表示多數類和少數類實例數(參見第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))，所有指標中的平均值均最差。該實驗結果表明,本文算法能很好地適應不平衡類環(huán)境,有效地提高了模型識別少數類樣本的能力。本文算法對模型分類性能影響的關鍵因素是對數據集進行劃分,而非具體某種劃分方法。

3.3 抽樣技術對PkNN的影響

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

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

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

3)SM-KM-kNN(SMOTE+KM-kNN)為KM-kNN在學習每個k近鄰模型前,使用SMOTE過抽樣方法處理新創(chuàng)建的訓練數據集(算法1第4)行和第5)行之間),然后學習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)。

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

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

4 結語

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