基于聚類的非平衡K-NN分類方法

崔麗娜

（長治學(xué)院沁縣師范分院，長治 046400）

基于聚類的非平衡K-NN分類方法

崔麗娜

（長治學(xué)院沁縣師范分院，長治 046400）

現(xiàn)實(shí)世界中存在大量非平衡分類問題，傳統(tǒng)K-近鄰（K-NN）分類方法采用近鄰決策的原則，導(dǎo)致少數(shù)類樣本在分類過程中難以識別。針對這個(gè)問題，提出一種基于聚類的非平衡K-NN分類方法（IKNN_C），該方法通過對已標(biāo)記的多數(shù)類樣本進(jìn)行聚類，壓縮多數(shù)類樣本的規(guī)模，從而提高標(biāo)記樣本的平衡性，提高非平衡數(shù)據(jù)的分類性能。

非平衡分類；K-NN算法；聚類；平衡性

0 引言

隨著大數(shù)據(jù)時(shí)代的到來，現(xiàn)實(shí)世界中的數(shù)據(jù)不僅規(guī)模急劇增長，數(shù)據(jù)的復(fù)雜性日益增大，多數(shù)的數(shù)據(jù)挖掘問題呈現(xiàn)出不平衡等復(fù)雜趨勢。例如，在用戶感興趣的網(wǎng)頁數(shù)據(jù)分類任務(wù)中，大眾化領(lǐng)域的網(wǎng)頁（如經(jīng)濟(jì)、教育等）可能被更多用戶標(biāo)記為感興趣的網(wǎng)頁，而一些受眾較小的領(lǐng)域（如神學(xué)、周易等）可能只有少數(shù)用戶才會(huì)感興趣。再如在腫瘤疾病分類檢測領(lǐng)域，大多數(shù)病人的腫瘤往往都是陰性的，而只有極個(gè)別病人的腫瘤檢測為陽性。在這些非平衡分類問題當(dāng)中，明顯存在一類樣本規(guī)模大于另外一類的情形，而少數(shù)類樣本對于非平衡分類問題往往更為重要，但傳統(tǒng)的數(shù)據(jù)挖掘方法很難有效識別這些重要的少數(shù)類樣本。因此，如何提高非平衡分類問題的性能近年來成為一個(gè)重要的研究問題[1-4]。

K-NN(K-Nearest Neighbor)分類方法是一種最為常見的分類預(yù)測方法，其模型設(shè)計(jì)簡單，容易實(shí)現(xiàn)，且分類的可靠性往往較高，目前已經(jīng)在多種領(lǐng)域中得到了成功應(yīng)用[5-8]。然而，對于非平衡分類問題，由于標(biāo)記樣本集中負(fù)類樣本規(guī)模遠(yuǎn)大于重要的正類樣本規(guī)模，當(dāng)新樣本進(jìn)入時(shí)，K-NN分類方法采用近鄰規(guī)則進(jìn)行測試，導(dǎo)致多數(shù)樣本都被歸入到并不重要的多數(shù)類樣本中，對重要的少數(shù)類樣本識別率不高，無法有效處理非平衡分類問題（如圖1所示）。圖中，圓圈代表多數(shù)不重要的負(fù)類樣本，正方形代表少數(shù)的重要的正類樣本，三角形代表待測樣本，顯然采用K-NN方法進(jìn)行分類時(shí)，待測樣本周圍的負(fù)類樣本較多，因此更容易將待測樣本標(biāo)記為負(fù)類樣本，特別地，當(dāng)近鄰參數(shù)的取值達(dá)到少數(shù)類樣本規(guī)模的兩倍以上時(shí)，待測樣本在任何情況下都將被標(biāo)記為負(fù)類。

圖1 K-NN處理非平衡分類問題示意圖

針對這個(gè)問題，本文提出了一種基于聚類的非平衡K-NN分類方法。該方法通過對已標(biāo)記的多數(shù)負(fù)類樣本進(jìn)行聚類，并采用抽樣的方法提取每個(gè)類的中心來代替該類別參與K-NN分類方法打標(biāo)簽的過程，壓縮了負(fù)類樣本規(guī)模，提高了標(biāo)記樣本的平衡性，改進(jìn)了K-NN方法處理非平衡數(shù)據(jù)的性能。

1 傳統(tǒng)K-NN分類

K-NN分類算法是數(shù)據(jù)挖掘領(lǐng)域一種非常成熟而典型的分類方法，其具有思路簡單、易于實(shí)現(xiàn)的優(yōu)點(diǎn)，同時(shí)往往具有較高的分類準(zhǔn)確率，已經(jīng)在諸多領(lǐng)域得到了廣泛的應(yīng)用。其基本思路就是給定含有類別標(biāo)簽的標(biāo)記樣本集，對于無標(biāo)簽的待測樣本，計(jì)算其與所有已標(biāo)記樣本集中所有樣本的距離，選擇聚類最近的k個(gè)樣本作為近鄰，然后根據(jù)這k個(gè)近鄰樣本的類別標(biāo)簽，采用少數(shù)服從多數(shù)的原則對待測樣本進(jìn)行類別標(biāo)注。

（1）算距離：計(jì)算無類別標(biāo)簽的待測樣本txm到包含類別標(biāo)記的樣本集Tr中每個(gè)樣本xi的距離，對于實(shí)際問題，可采用歐氏距離：

（2）找近鄰：從所有的帶類別標(biāo)簽的樣本集中選擇k個(gè)距離待測樣本txm最近的標(biāo)記樣本；

（3）打標(biāo)簽：根據(jù)少數(shù)服從多數(shù)的原則，從待測樣本txm的k個(gè)近鄰標(biāo)記樣本中，選擇類別最多的標(biāo)記作為待測樣本txm的類別標(biāo)簽。

對于平衡的分類問題，K-NN分類方法可得到較為優(yōu)秀的分類結(jié)果，但對于非平衡的分類問題，由于負(fù)類樣本規(guī)模遠(yuǎn)大于正類樣本規(guī)模，對于待測樣本選取近鄰時(shí)，往往在近鄰樣本中負(fù)類樣本也會(huì)占據(jù)多數(shù)，因此都被標(biāo)記為負(fù)類標(biāo)簽，對于少數(shù)的重要正類樣本無法有效識別。

2 基于聚類的非平衡K-NN分類方法

針對傳統(tǒng)K-NN分類方法無法處理非平衡數(shù)據(jù)分類的問題，本文提出一種基于聚類的非平衡K-NN分類方法。該方法首先對多數(shù)的負(fù)類已標(biāo)記樣本集進(jìn)行聚類，聚類個(gè)數(shù)即可選擇正類樣本數(shù)目，然后計(jì)算聚類之后每個(gè)類的類中心，并選擇每個(gè)類中距離類中心最近的樣本點(diǎn)作為該類的代表點(diǎn)，然后將這些代表點(diǎn)與少數(shù)正類樣本合并，構(gòu)成新的平衡標(biāo)記樣本集來對待測樣本進(jìn)行分類。該方法通過對大規(guī)模的負(fù)類樣本進(jìn)行聚類采樣，使之與正類樣本盡可能平衡，從而減小類別不平衡性對于待測樣本打標(biāo)簽過程的負(fù)面影響，提高K-NN分類方法對于非平衡數(shù)據(jù)分類的性能。具體地，本文提出的 IKNN_C（Imbalanced K-NN classifica?tion method based on Clustering）算法如下。

算法1 IKNN_C算法：

Step 1：將負(fù)類帶標(biāo)記樣本集X-聚類，聚類參數(shù)取正類樣本數(shù)l2，即且第i個(gè)類具體聚類方式可采用最常用的K均值聚類方法[9]。

Step 2：計(jì)算聚類生成的每個(gè)負(fù)類類別的中心，計(jì)算方法為：

Step 3：選擇每個(gè)負(fù)類類別中距離中心最近的樣本作為該類別的代表點(diǎn)：

Step 5：在新生成的標(biāo)記樣本集Tr'上執(zhí)行K-NN分類過程，對待測樣本txm進(jìn)行類別決策；

Step6：對于每個(gè)無標(biāo)記測試樣本，都得到其對應(yīng)的類別標(biāo)簽，并與真實(shí)標(biāo)簽集比對，測試性能；

Step 7：算法結(jié)束。

3 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證本文提出的IKNN_C分類方法的性能，本文5個(gè)典型的非平衡UCI數(shù)據(jù)集[9]上進(jìn)行了測試（如表1所示），其中測試樣本的正負(fù)類比例與標(biāo)記樣本一致。實(shí)驗(yàn)的環(huán)境為1臺PC（3.60GHz CPU,4G內(nèi)存），實(shí)驗(yàn)平臺是MATLAB2014a。由于K-NN近鄰參數(shù)設(shè)置的問題不是本文的重點(diǎn)，實(shí)驗(yàn)中近鄰參數(shù)全部統(tǒng)一設(shè)置為5，關(guān)于近鄰參數(shù)的選擇及設(shè)置可以參考文獻(xiàn)[10-12]。

表1 實(shí)驗(yàn)數(shù)據(jù)集

在傳統(tǒng)分類問題當(dāng)中，常采用精度作為分類的度量指標(biāo)，但對于非平衡分類問題，精度作為指標(biāo)只能反映分類的整體情況，而無法突出重要的少數(shù)類樣本的分類情況，特別地，重要的少數(shù)正類樣本被全部錯(cuò)分為負(fù)類樣本時(shí)，實(shí)際上構(gòu)造的分類器沒有任何意義，因?yàn)楸举|(zhì)上無法實(shí)現(xiàn)對兩類的有效分離，但由于測試樣本中存在大量的負(fù)類樣本可以被正確預(yù)測，從而導(dǎo)致得到了較高的分類精度，針對這個(gè)問題，本文采用了如下多種非平衡分類指標(biāo)類衡量所提出非平衡分類方法的性能，這些指標(biāo)中變量的意義見表2中的混淆矩陣。

表2 混淆矩陣

（1）精度（Acc）

為了體現(xiàn)測試完整性，本文仍然采用了傳統(tǒng)的精度作為一項(xiàng)指標(biāo)，即用于反映所有樣本整體的分類正確率：

（2）召回率（Rec）

召回率用于反映真實(shí)的正類樣本中預(yù)測為正類的比例，其定義為：

（3）準(zhǔn)確性（Pre）

準(zhǔn)確性用于反映預(yù)測的正類樣本中包含正類樣本的比例，其定義為：

（4）F-值（F）

F可用于綜合衡量重要的少數(shù)類樣本的分類性能。

為體現(xiàn)本文提出的基于聚類非平衡K-NN分類方法的性能，本文與傳統(tǒng)的K-NN方法進(jìn)行了對比，表3為不同數(shù)據(jù)集在4個(gè)指標(biāo)上得到的實(shí)驗(yàn)結(jié)果。

在表3中，對于數(shù)據(jù)集German和Flare，由于傳統(tǒng)K-NN分類結(jié)果中沒有預(yù)測為正類的樣本，因此其對應(yīng)的Pre值和F值不存在。表3中，本文提出的IKNN_C方法相對于傳統(tǒng)K-NN方法得到的衡量指標(biāo)提高的情況用“↑”表示，降低的情況用“↓”表示，不變的情形用“-”表示。從表中可以看出，對于傳統(tǒng)的精度Acc指標(biāo)，所提出的IKNN_C算法在Diabetis、German和Flare數(shù)據(jù)集上均有較為明顯的下降，而在數(shù)據(jù)集Titanic上略有提升，這是是由于對于多數(shù)的非平衡分類問題，大量的負(fù)類樣本分類正確，從而提升了整體的測試精度，但對于重要的少數(shù)類樣本分類情況該指標(biāo)卻無法反應(yīng)得到。對于直接反映正類樣本分類性能的召回率Rec指標(biāo)，可以觀測到在所有數(shù)據(jù)集上本文提出的IKNN_C都有提高；而對于Pre指標(biāo)，在數(shù)據(jù)集German、Flare和Titanic上均有提高，在Thyroid上兩種方法都得到了最大值1.0，但在數(shù)據(jù)集Diabetis上卻有一定程度下降，這是由于所提出的方法IKNN_C盡管預(yù)測對了較多的重要正類樣本，但同時(shí)在負(fù)類數(shù)據(jù)上產(chǎn)生了較大的預(yù)測誤差。但是，從綜合反映正負(fù)類誤差的F值來看，在五個(gè)數(shù)據(jù)集上都得到了提高。這充分說明本文提出的基于聚類非平衡K-NN分類方法增強(qiáng)了K-NN分類中標(biāo)記樣本的平衡性，可有效解決傳統(tǒng)K-NN對于重要的少數(shù)正類樣本識別率不高的問題，提升了K-NN方法對于非平衡數(shù)據(jù)分類的整體性能。

表3 標(biāo)準(zhǔn)UCI數(shù)據(jù)集上的測試結(jié)果

4 結(jié)語

針對傳統(tǒng)K-NN分類方法無法處理非平衡數(shù)據(jù)分類的問題，本文提出了一種基于聚類的非平衡K-NN分類方法。通過對多數(shù)的負(fù)類已標(biāo)記樣本集進(jìn)行聚類，并選擇每個(gè)類中距離類中心最近的小規(guī)模樣本替代原始大規(guī)模的負(fù)類樣本參與待測樣本類別決策，減小了類別不平衡性對于待測樣本打標(biāo)簽過程的負(fù)面影響，提高了K-NN分類方法對于非平衡數(shù)據(jù)分類的性能。

[1]W.Ng,G.J.Zeng,J.J.Zhang,et al.,Dual Autoencoders Features for Imbalance Classification Problem[J].Pattern Recognition,2016,60,875-889.

[2]許震，沙朝鋒，王曉玲等.基于KL距離的非平衡數(shù)據(jù)半監(jiān)督學(xué)習(xí)算法[J].計(jì)算機(jī)研究與發(fā)展，2010,47(1):81-87.

[3]F.Y.Cheng,J.Zhang,C.H.Wen,et al.Large Cost-Sensitive Margin Distribution Machine for Imbalanced Data Classification[J].Neurocomputing,2017,224,45-57.

[4]M.D.Martino,A.Fernández,P.Iturralde,et al.Novel Classifier Scheme for Imbalanced Problems[J].Pattern Recognition Letters,2013,34(10):1146-1151.

[5]Liu Yi,Jing Ning,Chen Luo,et al.Algorithm for Processing K-nearest Join Based on R-tree in MapReduce[J].Journal of Software,2013,24(8):1836-1851(in Chinese).

[5]劉義，景寧，陳犖等.MapReduce框架下基于R-樹的k-近鄰連接算法[J].軟件學(xué)報(bào)，2013,24(8):1836-1851.

[6]Z.B.Pan,Y.D.Wang,W.P.Ku.A New K-Harmonic Nearest Neighbor Classifier Based on the Multi-Local Means[J].Expert Systems with Applications,2017,67,115-125.

[7]Han Jia-wei,Kamber Micheline,Pei Jian.Data Mining,Concepts and Techniques(Third Edition)[M].Elsevier Press,2012.

[8]N.Toma?ev,D.Mladeni.Hubness-Aware Shared Neighbor Distance for High-Dimensional K-Nearest Neighbor Classification[J].Knowledge and Information Systems,2014,39(1):89-122.

[9]UCI Machine Learning Repository.(2009-10-16)[2016-11-05],http://archive.ics.uci.edu/ml.

Imbalanced K-NN Classification Method Based on Clustering

CUI Li-na
（Qinxian Normal Institute,Changzhi University,Changzhi Shanxi 046400）

In real world,there are many imbalanced classification problems.The traditional K-nearest neighbor（K-NN）classification method adopts the principle of nearest neighbor decision rule,and the important minority class samples are always classified wrongly.To solve this prob?lem,this paper presents an imbalanced K-NN classification method based on clustering（IKNN_C）.This method can compress the size of majority class size by clustering the majority class samples.Then it improves the balance of labeled samples and improves the classification performance of imbalanced data.

Imbalanced Classification;K-NN Algorithm;Clustering;Balance

1007-1423（2017）33-0006-04

10.3969/j.issn.1007-1423.2017.33.002

崔麗娜(1981-)，女，山西武鄉(xiāng)人，助教，研究方向?yàn)閿?shù)據(jù)挖掘與智能信息處理

2017-08-24

2017-11-20