武永成，劉 釗

(1.荊楚理工學(xué)院 計(jì)算機(jī)工程學(xué)院，湖北 荊門 448000；2.武漢科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430081)

一種基于聚類的非平衡分類算法

武永成1，劉 釗2

(1.荊楚理工學(xué)院 計(jì)算機(jī)工程學(xué)院，湖北 荊門 448000；2.武漢科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430081)

傳統(tǒng)的分類算法大多假定用來學(xué)習(xí)的數(shù)據(jù)集是平衡的，但實(shí)際應(yīng)用中真正面臨的數(shù)據(jù)集往往是非平衡數(shù)據(jù)。針對(duì)非平衡數(shù)據(jù), 利用傳統(tǒng)的分類方法往往不能獲得良好的性能。文章提出了一種新的基于聚類的非平衡分類算法，通過聚類生成多個(gè)聚類體，在每個(gè)聚類體中選取一定數(shù)量的數(shù)據(jù)作為訓(xùn)練樣本，有效地處理了樣例數(shù)據(jù)的不平衡問題，在相關(guān)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了本方法的有效性。

機(jī)器學(xué)習(xí)；非平衡分類；減重取樣；聚類

0 引言

分類(classification)是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中最典型的任務(wù)之一[1]。分類算法在對(duì)有標(biāo)記樣本集合(或稱為有分類類型的樣本集合)進(jìn)行分析和學(xué)習(xí)后，生成一個(gè)分類器。利用得到的分類器，可以對(duì)那些沒有分類類型的數(shù)據(jù)進(jìn)行預(yù)測(cè)，判斷其分類類型。如醫(yī)務(wù)人員可以將病人的相關(guān)數(shù)據(jù)輸入分類系統(tǒng)，分類系統(tǒng)就能根據(jù)以往學(xué)習(xí)得到的分類器，自動(dòng)判斷某個(gè)病人是否會(huì)藥物過敏。

傳統(tǒng)的分類算法很多都基于一種假定：用來學(xué)習(xí)的樣本數(shù)據(jù)都是平衡的，即各類樣本數(shù)據(jù)的數(shù)量差別不大，不是一類樣本數(shù)據(jù)的數(shù)量遠(yuǎn)遠(yuǎn)大于另一類數(shù)據(jù)。然而，現(xiàn)實(shí)世界中，很多情況下，樣例數(shù)據(jù)是不均衡的。例如：在1 000個(gè)體檢數(shù)據(jù)集中，最終分類類型為健康的可能占90%，分類類型為不健康的可能為10%，這樣的數(shù)據(jù)集就是非平衡的。本文中，為便于敘述，將一個(gè)數(shù)據(jù)集中大多數(shù)的樣例都屬于的分類類型稱為MA，而剩余的樣例的分類類型稱為MI。

對(duì)于非平衡數(shù)據(jù)的分類(imbalanced classification)，最大的問題是：最終得到的分類器可能只對(duì)MA數(shù)據(jù)敏感，而忽略MI數(shù)據(jù)。在對(duì)測(cè)試數(shù)據(jù)進(jìn)行分類預(yù)測(cè)時(shí)，容易將其分類為MA而忽略MI。例如：銀行想利用分類算法構(gòu)造一個(gè)分類器，對(duì)顧客未來是否進(jìn)行信用貸款進(jìn)行預(yù)測(cè)。銀行的歷史數(shù)據(jù)(有標(biāo)記樣本集合)中，只有2%的顧客信用貸款，其余98%顧客不貸款。傳統(tǒng)的分類算法在這樣的樣本數(shù)據(jù)上進(jìn)行學(xué)習(xí)得到的分類器，會(huì)將所有被預(yù)測(cè)的顧客判定為不貸款，因?yàn)檫@樣可以得到98%的分類準(zhǔn)確率。顯然這不是銀行的真正目的。能對(duì)少數(shù)的可能貸款的用戶進(jìn)行準(zhǔn)確預(yù)測(cè)，才是銀行所需分類器的真正目的。

針對(duì)非平衡數(shù)據(jù)的分類，在監(jiān)督學(xué)習(xí)中，主要采用的是重取樣(re-sampling)[2]和代價(jià)敏感(cost-sensitive learning)[3]的方法。

本文在重取樣技術(shù)的基礎(chǔ)上，提出了一種新的基于聚類(clustering)[1]的非平衡分類算法，通過聚類生成多個(gè)聚類體，在每個(gè)聚類體中選取一定數(shù)量有代表性的數(shù)據(jù)作為訓(xùn)練樣本，有效地提高了對(duì)MI類數(shù)據(jù)預(yù)測(cè)的準(zhǔn)確性。在相關(guān)數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證了本方法的有效性。

1 相關(guān)工作

機(jī)器學(xué)習(xí)的分類問題中，給定一個(gè)樣例集合D={,…}∈X×Y，其中是一個(gè)樣例。xi是一個(gè)向量[xi1,…xim]，yi是該樣例的標(biāo)注(或分類類型)。X、Y分別是xi,yi的取值范圍。是未標(biāo)注樣例，是有標(biāo)注樣例。分類算法的任務(wù)就是在集合D上進(jìn)行學(xué)習(xí)得到分類器。利用學(xué)習(xí)得到的分類器，就可以對(duì)未標(biāo)注樣例的分類類型進(jìn)行預(yù)測(cè)。

非平衡分類問題，作為一個(gè)具有挑戰(zhàn)性的機(jī)器學(xué)習(xí)問題，近些年在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域被廣泛研究。其中使用的最重要的技術(shù)是：重取樣技術(shù)和代價(jià)敏感學(xué)習(xí)技術(shù)。重取樣技術(shù)又分為增重取樣(over-sampling)[2]和減重取樣(under-sampling)[4]兩種方法，增重取樣技術(shù)通過復(fù)制MI樣本來使得它和MA的樣本數(shù)達(dá)到平衡，減重取樣技術(shù)則通過減少一定的MA樣本使它與MI的樣本數(shù)達(dá)到平衡。

減重取樣技術(shù)中最簡(jiǎn)單的一種方法稱為隨機(jī)減重取樣技術(shù)(random under-sampling approach，簡(jiǎn)稱為RUSA)，它隨機(jī)地在MA數(shù)據(jù)集中選取一定數(shù)量的MA樣本，與MI一起組成一個(gè)平衡的訓(xùn)練集。

2 基于聚類的非平衡分類算法

隨機(jī)減重取樣技術(shù)最大的問題是隨機(jī)選取的樣本代表性可能不強(qiáng)。為此，本文提出了一種基于聚類的非平衡分類算法。首先對(duì)整個(gè)訓(xùn)練集D(由MA樣本和MI樣本組成的非平衡數(shù)據(jù)集)進(jìn)行聚類，生成若干個(gè)聚類體。對(duì)于這些聚類體，每個(gè)可能具有不同的特點(diǎn)。某個(gè)聚類體可能包含較多的MA樣本和較少的MI樣本，則這個(gè)聚類體的整體特性與MA樣本更接近；同樣，某個(gè)聚類體可能包含較多的MI樣本和較少的MA樣本，則這個(gè)聚類體的整體特性與MI樣本更接近。因此，根據(jù)每個(gè)聚類體中MA樣本與MI樣本的比值，我們的算法從每個(gè)聚類體中選取不同數(shù)量的MA樣本，與D中所有的MI一起，組成最終的訓(xùn)練樣本D’(平衡的數(shù)據(jù)集)，這樣就有效地克服了隨機(jī)減重取樣技術(shù)的盲目性問題。

2.1 基于聚類的平衡數(shù)據(jù)集產(chǎn)生辦法

(1)

例如：有一個(gè)非平衡數(shù)據(jù)集D，它的樣本數(shù)量為1 100，其中SizeMA=1 000，SizeMI=100。聚類算法將D聚類為3個(gè)聚類體，3個(gè)聚類體的相關(guān)數(shù)據(jù)如表1所示。

設(shè)平衡化處理后的數(shù)據(jù)集D’中MA與MI樣本之比1∶1，則可知從D中選取的MA樣本數(shù)為100。這100個(gè)MA樣本，是分別從聚類體1、2、3中選取82、10、8個(gè)MA樣本組成的。具體計(jì)算方法如表2所示。

表1 3個(gè)聚類體的相關(guān)數(shù)據(jù)表

表2 3個(gè)聚類體中分別選取的MA樣本數(shù)

2.2 基于聚類的非平衡分類算法的完整描述

本文提出的基于聚類的非平衡分類算法，其完整描述如算法1所示。

算法1 基于聚類的非平衡分類算法

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

實(shí)驗(yàn)中用到兩個(gè)真實(shí)的數(shù)據(jù)集。一個(gè)是美國(guó)人口統(tǒng)計(jì)局1994年和1995年的人口-收入統(tǒng)計(jì)數(shù)據(jù)庫，該數(shù)據(jù)集中包含公民的年齡、性別、受教育程度、工作等信息，該數(shù)據(jù)集的任務(wù)是能對(duì)每個(gè)公民的收入進(jìn)行預(yù)測(cè)?？倶颖緮?shù)為30 162，其中MA(收入低于5萬美元)樣本數(shù)為22 654，MI(收入高于5萬美元)樣本數(shù)為7 508；另一個(gè)數(shù)據(jù)庫是銀行貸款拖欠檢測(cè)數(shù)據(jù)集，該數(shù)據(jù)集中包含客戶基本信息、客戶支付能力和客戶賬單資金總量等信息，該數(shù)據(jù)集的任務(wù)是能對(duì)容易拖欠的客戶進(jìn)行預(yù)測(cè)。該數(shù)據(jù)集的樣本總數(shù)為62 309，其中MA(不容易拖欠的客戶)樣本數(shù)為47 707，MI(容易拖欠的客戶)樣本數(shù)為14 602。我們使用80%的樣本作為學(xué)習(xí)樣本，其余20%的樣本用來對(duì)學(xué)習(xí)得到的分類器進(jìn)行評(píng)價(jià)。

算法1的第一步提到的聚類算法采用k-medoids算法[6]，算法1的第四步提到的分類算法采用神經(jīng)網(wǎng)絡(luò)算法[7]。

為驗(yàn)證本算法的有效性，與隨機(jī)減重取樣算法(RUSA)進(jìn)行了對(duì)比，實(shí)驗(yàn)結(jié)果如表3所示。從表3可看出，在兩個(gè)數(shù)據(jù)集上，我們的算法都優(yōu)于RUSA算法。

表3 兩種算法的實(shí)驗(yàn)結(jié)果

4 結(jié)束語

本文針對(duì)隨機(jī)減重取樣技術(shù)的局限性，提出了一種基于聚類的非平衡分類算法。首先采用聚類算法對(duì)整個(gè)原始非平衡樣本集合進(jìn)行聚類，得到多個(gè)聚類體；然后在每個(gè)聚類體中，選取一定數(shù)量的MA樣本，與原始樣本中的所有MI樣本一起，組成一個(gè)新的平衡的樣本集合。在該樣本集合上，利用傳統(tǒng)的分類算法進(jìn)行學(xué)習(xí)，得到最終的分類器。在兩個(gè)非平衡數(shù)據(jù)集上，驗(yàn)證了本算法的有效性。

[1] 韓家煒.數(shù)據(jù)挖掘:概念與技術(shù)[M].北京:機(jī)械工業(yè)出版社,2004.

[2] N Chawla,K Bowyer,L Hall,et al.SMOTE:Synthetic Minority Over-Sampling Technique[J].Journal of Artificial Intelligence Research,2002,16:321-357.

[3] Z Zhou,X Liu.Training Cost-Sensitive Neural Networks with Methods Addressing the Class Imbalance Problem[C]// IEEE Transaction on Knowledge and Data Engineering,2006:63-77.

[4] R Barandela,J Sánchez,V García,et al.Strategies for Learning in Class Imbalance Problems[J].Pattern Recognition, 2003,36:849-851.

[5] M Kubat,S Matwin.Addressing the Curse of Imbalanced Training Sets:One-Sided Selection[C]//In Proceedings of ICML-97,1997:179-186.

[6] Struyf A,Hubert M,Rousseeuw P.Integrating Robust Clustering Techniques in S-plus[J].Computational Statistics and Data Analysis,1997(26):17-37.

[7] Sondak N E,Sondak V K.Neural Networks and Artificial Intelligence[C]//In Proceedings of the 20th SIGCSE Technical Symposium on Computer Science Education,1989.

2013-11-05

武永成(1971-)，男，湖北仙桃人，荊楚理工學(xué)院講師，碩士。研究方向：機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘； 劉釗(1967-)，男，湖北襄陽人，武漢科技大學(xué)教授，博士。研究方向：人工智能和演化計(jì)算。

TP301.6

A

1008-4657(2014)02-0045-04

寸曉非]