武永成，劉 釗

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

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

武永成1，劉 釗2

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

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

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

0 引言

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

(1)

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

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

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

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

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

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

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

3 實驗結(jié)果與分析

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

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

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

表3 兩種算法的實驗結(jié)果

4 結(jié)束語

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

[1] 韓家煒.數(shù)據(jù)挖掘:概念與技術(shù)[M].北京:機械工業(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é)院講師，碩士。研究方向：機器學(xué)習(xí)和數(shù)據(jù)挖掘； 劉釗(1967-)，男，湖北襄陽人，武漢科技大學(xué)教授，博士。研究方向：人工智能和演化計算。

TP301.6

A

1008-4657(2014)02-0045-04

寸曉非]