魏 力,張育平

(南京航空航天大學 計算機科學與技術(shù)學院,南京 211100)

1 引 言

在機器學習中,不平衡數(shù)據(jù)集是指不同類別的樣本分布不均衡,即會出現(xiàn)某一類別的樣本遠遠多于另一類別的樣本[1].這在各個研究領(lǐng)域也是很常見的,比如信用欺詐檢驗[2],信用不合格的客戶往往是占少數(shù)的；又如醫(yī)院疾病檢測,生病的人較正常人也是少數(shù)的.然而,如果直接使用這種數(shù)據(jù)集進行分類研究,會因為類別不平衡問題對算法的學習過程造成干擾,使得分類結(jié)果不盡如人意[3].

Wessi[4]的研究表明,不平衡數(shù)據(jù)集分類困難的主要原因有如下幾點：1.傳統(tǒng)的分類器性能評價標準失效.在很多情況下,我們會將精度(Accuracy)作為評價分類器好壞的依據(jù),但有些時候精度并不能很好的反映模型的好壞.例如,100個人中有10個人生病,分類器即使將所有個例都預測為正常人也能獲得90%的精度.但這不是我們想要的預測模型,能將患者預測出來才是研究的目標.因此,在不平衡數(shù)據(jù)集中,以精度為評價標準的分類學習會使分類器更偏向于預測為多數(shù)類.2.少數(shù)類樣本過于少.從Wessi的文獻[5]可以知道,在一些應用下,多類樣本與少類樣本比例過高時就會使分類變得困難.說明分類器的性能與樣本類別比例有關(guān).3.數(shù)據(jù)碎片問題.不少分類算法采用了分治思想,即將原來的大規(guī)模數(shù)據(jù)空間劃分成若干個小規(guī)模子空間,而這些子空間會包含更少的少數(shù)類樣本,導致少數(shù)類信息的匱乏,那么預測模型也較難建立.4.歸納偏置問題.在預測任務中,未知樣本可以是任意的,而如果沒有額外假設來約束的話,任務完成不了.這些假設約束條件就稱為歸納偏置.為了獲得更好的性能并能避免過度擬合,很多學習算法不利于少數(shù)類樣本的預測,即這類算法會更偏向于將樣本預測為多數(shù)類.

2 相關(guān)技術(shù)

對于處理不平衡數(shù)據(jù)集給學習任務造成的困擾,目前研究主要從兩方面著手：從算法設計層面改進算法；從數(shù)據(jù)層面改變樣本分布.

為了解決上文提到的不平衡數(shù)據(jù)集對傳統(tǒng)分類算法性能的影響,從算法設計著手是一種思路,主要包括：

代價敏感學習.代價敏感學習主要考慮在分類任務中,不同類別錯分時如何通過此時的“錯誤代價”來調(diào)整分類器.比如在疾病診斷一例中,將正常人誤分為病人和將病人誤分為正常人的“代價”是不同的.很明顯,將病人誤分為正常人很可能會讓患者錯過最佳治療時機而導致比較嚴重的后果.那么在代價敏感學習中,會先設計一個C×C的Cost代價矩陣,用以表明將某一類別錯分時的代價.所以代價敏感學習任務追求的不是總體的錯誤率最低,而是完成分類后的總“代價”最小.

單分類方法.與二分類或多分類任務不同,單分類方法是去確定唯一類別的邊界條件.這樣做的結(jié)果就是,該方法只能識別一個類別,而不包含在邊界內(nèi)的都屬于“其它”.劉敬[19]等人對基于單分類支持向量機和主動學習的異常檢測進行了研究,利用原始數(shù)據(jù)采用無監(jiān)督方式建立單分類支持向量機模型,然后結(jié)合主動學習找出能夠提高異常檢測性能的樣本并標記,所提方法能夠利用少量標記數(shù)據(jù)獲取性能提升.常用的單分類SVM在處理不平衡數(shù)據(jù)問題是有較好的效果,文獻[6]也證明,因為只要訓練某一類別的數(shù)據(jù),這無論是在時間開銷還是空間開銷上都節(jié)省了很多.

重劃分.重劃分就是將多數(shù)類通過聚類算法劃分為若干個與少數(shù)類均衡的子類,以此來達到類別平衡.鄔長安[18]等人提出了基于 k-mean的數(shù)據(jù)預處理的邏輯回歸學習方法ILKL提高邏輯回歸在不平衡類中的分類性能.不同于傳統(tǒng)的邏輯回歸方法,該方法采用k-means聚類進行了數(shù)據(jù)預處理,將多數(shù)類實例劃分為一個個子簇,然后用ILKL學習到的模型在重平衡的數(shù)據(jù)集上進行分類.

其它諸如改進集成學習算法Adaboost的Ada-Cost[8],基于核函數(shù)的學習方法[9],主動學習[10],遺傳算法[11]等等.

從根本上說,導致不平衡數(shù)據(jù)集學習問題的原因還是不同類別的樣本分布不均.那么,減少多類樣本數(shù)目,增加少類樣本數(shù)目,也就是從數(shù)據(jù)層面入手自然成為另一種思路.通過增加少數(shù)類樣本來降低不平衡度的方法叫做過采樣(over-sampling),減少多數(shù)類樣本的方法叫做欠采樣(under-s-ampling).迄今為止,不少學者在這兩個方法上已有建樹.

過采樣方面,最基礎的方法就是復制已經(jīng)存在的少數(shù)類樣本個例,這樣做的好處是簡單,但是復制操作在沒有給出額外信息的情況下,不僅會增加訓練器學習的時間,更會導致過擬合問題.Chawa-la[12]等人提出的SMOTE算法簡單高效地模擬產(chǎn)生相似的少數(shù)類樣本數(shù)據(jù).算法為每一個少數(shù)類樣本根據(jù)K-Nearest算法選擇與其近鄰的其它樣本,然后在與這些樣本的連線上隨機產(chǎn)生人造樣本.盡管在一些實驗中,SMOTE算法有較優(yōu)異的表現(xiàn),但它存在著兩個很明顯的問題,由于該算法在每個少數(shù)類樣本上都產(chǎn)生若干個近鄰相似樣本,所以在擴展少數(shù)類樣本方面只能是成倍的,另外也不可避免的會產(chǎn)生過于重疊的樣本.針對這些問題,后人提出了一些改進算法.比如Han[13]等人提出的Bordline-SMOTE算法,該算法首先在整個樣本空間中為每個少數(shù)類樣本生成K-Nearest近鄰樣本集Si,如果Si中屬于多數(shù)類的大于屬于少數(shù)類的,則將這個Si放入Danger集中,之后只在Danger集中根據(jù)SMOTE算法產(chǎn)生新樣本.Bordline-SMOTE算法只為那些處于邊界的少數(shù)類樣本產(chǎn)生新樣本會有更好的效果.王超學等人[16]提出了一種改進的SMOTE算法GA-SM-OTE.該算法在傳統(tǒng)的SMOTE算法中引入遺傳算法的三個基本算子,利用選擇算子實現(xiàn)對少數(shù)類樣本有區(qū)別的選擇,使用交叉、變異算子實現(xiàn)對合成樣本質(zhì)量的控制.最后結(jié)合SVM算法來處理不平衡數(shù)據(jù)的分類問題.

欠采樣方面,很容易想到隨機去掉若干個多數(shù)類樣本,但這樣做會去除掉富有信息量的樣本,不利于后面的學習過程.針對這一缺陷,熊冰研等人[15]提出了一種基于樣本權(quán)重的欠抽樣方法KAcBag(K-means AdaCost bagging),該方法通過樣本權(quán)重來刻畫多數(shù)類樣本所處的區(qū)域,在多次聚類后確定各樣本的權(quán)重,然后根據(jù)權(quán)重從多數(shù)類中抽取樣本以平衡數(shù)據(jù)集.最后結(jié)合集成學習思想,通過投票集成提升分類效果.楊杰明等人[17]提出一種基于數(shù)據(jù)密度分布的欠采樣方法US-DD.該算法通過某個數(shù)據(jù)樣本點在一定半徑內(nèi)包含的樣本個數(shù)來定義數(shù)據(jù)密度概念,并以此來區(qū)分高密度數(shù)據(jù)和低密度數(shù)據(jù),再通過閾值參數(shù)來提出低密度數(shù)據(jù)樣本.Mani[14]等人根據(jù)數(shù)據(jù)分布特征,給出了4種基于KNN(K Nearest Neighbour)欠采樣方案.分別是NearMiss-1,NearMiss-2,NearMiss-3和Most Distant.其中NearMiss-1選擇到最近的三個少數(shù)類樣本平均距離最小的那些多數(shù)類樣本,屬于局部最近.NearMiss-2選擇到最遠的三個少數(shù)類樣本平均距離最小的那些多數(shù)類樣本,屬于全局最近.而NearMiss-3讓每個少數(shù)類樣本都選擇給定數(shù)量的最近多數(shù)類樣本,使得每一個少數(shù)類樣本附近都有足夠多的多數(shù)類樣本,這會使得模型的精確度高、召回率低.Most Distant選擇那些與最近的三個少數(shù)類樣本平均距離最遠的多數(shù)類樣本,這可以用作比較.實驗結(jié)果表明,NearMiss-2擁有較好的不平衡數(shù)據(jù)學習能力.然而,在論文中Mani也提到即使是NearMiss-2與隨機欠抽樣相比提升也比較有限.

本文利用聚類簇中心的信息概括能力結(jié)合Ne-arMiss-2在欠抽樣過程中的優(yōu)先權(quán)重,提出了一種基于K-Means聚類的欠抽樣方法——CCNM.

3 算法設計

K-Means算法是很典型的基于距離的聚類算法,采用距離作為相似性的評價指標,即認為兩個對象的距離越近,其相似度就越大.由K-Means算法聚類得出的簇中心點可以認為是各個簇內(nèi)樣本點的信息概括.以簇中心點作為代表,根據(jù)Near-Miss距離去賦予各個簇選擇權(quán)重,讓權(quán)重最高的簇按照距離中心點近優(yōu)先原則選擇K個樣本,權(quán)重次之的選擇樣本數(shù)目遞減.

CCNM算法的步驟如下：

記多數(shù)類樣本集為S,樣本數(shù)目為M,少數(shù)類樣本集為T,樣本數(shù)目為N.

1)按照公式(1),根據(jù)少數(shù)類樣本數(shù)目N確定K值；

K=?(2N+0.25)1/2-0.5」

(1)

2)對少數(shù)類樣本進行確定后K值的聚類,得出K個簇及其中心點；

3)按照NearMiss距離(NearMiss-1,NearMi-ss-2,NearMiss-3)對K個簇中心點進行排序,并賦予權(quán)重,權(quán)重最高的簇即選擇K個,接下來的選擇K-1個；

4)在各個簇內(nèi)依照權(quán)重選擇那些離簇中心點最近的樣本,如果當前簇的樣本點少于應該選擇點的數(shù)目,則將不夠的選擇數(shù)目交予權(quán)重次之的簇；

5)整理各簇選擇的樣本,構(gòu)建欠采樣后的多數(shù)類樣本S′.

圖1 不同類型的NearMiss算法示例Fig.1 Examples of different types of NearMiss algorithm

聚類采樣可以保證在以距離為相似性的評價標準下,比較多的保留樣本信息.從步驟3)可以看到,在不同簇內(nèi)的采樣個數(shù)是根據(jù)當前簇的權(quán)重遞減的,呈等差數(shù)列態(tài),那么為了平衡樣本數(shù)的差異,公式(1)就通過確立K值,并約定最高權(quán)重簇的采樣個數(shù)為K,來完成最終采樣數(shù)約等于少數(shù)類樣本個數(shù)的目的.應用NearMiss距離也可以在縱觀整個數(shù)據(jù)空間下,選出那些易于分類的數(shù)據(jù).圖1給出三種NearMiss的典型示例.

4 實驗結(jié)果

4.1 評價標準

傳統(tǒng)的學習任務采用精度作為分類器性能好壞的評價標準,但由于不平衡數(shù)據(jù)集的特殊性,分類器更偏向?qū)⒔Y(jié)果預測為多數(shù)類從而獲得較高的精確度.但是在一些情況下,不能識別少數(shù)類的分類并不是我們想要的,所以將精度作為不平衡數(shù)據(jù)集中分類器的評價標準是不合適的.為此,一些學者提出了更完善的解決方案,如F-Measure[9],G-Mean[10].這些指標都基于分類評價中常用的混淆矩陣(confusion matrix),根據(jù)分類器預測結(jié)果與實際情況劃別4類組合,真正例(true positive),假正例(false positive),真反例(true negative),假反例(false negative).混淆矩陣如表1所示.

表1 混淆矩陣Table 1 Confusion matrix

在此基礎上,查準率precision如公式(2)所示,查全率recall定義如公式(3)所示.

(2)

(3)

F-Measure是不平衡數(shù)據(jù)分類評價中最為常見的標準,其定義如下：

(4)

基于調(diào)和平均定義的F度量標準的一般形式取β為1,本文也按此進行試驗.綜合考慮查全率和查準率的F-Measure只有當precision和recall都較高時才會有比較出色的表現(xiàn),更適合不平衡數(shù)據(jù)分類評價.

當考慮有多少正例被成功預測出來(Positive-Accuracy),多少負例被成功預測出來(NegativeA-ccuracy)時,就有了G-Mean的定義：

(5)

(6)

(7)

G-Mean的定義同時考慮正、負類的預測結(jié)果,在那些偏向預測為多數(shù)類的情況下,G-Mean不會有好的分數(shù),能夠完成不平衡數(shù)據(jù)分類評價的任務.

表2 數(shù)據(jù)集Table 2 Data set

4.2 數(shù)據(jù)集

本文從UCI上選取10個數(shù)據(jù)集,如表2所示.以少數(shù)類與樣本總數(shù)的比例作為數(shù)據(jù)集的稀有度,先將前6個數(shù)據(jù)集用作在本文中三類NearMiss距離效果的比較,確定最佳的一種NearMiss距離,后續(xù)補充4個數(shù)據(jù)集與其它方法比較.

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

實驗先要將多數(shù)類樣本和少數(shù)類樣本按照一定比例歸入訓練集和測試集,為了讓實驗結(jié)果更加客觀,在采用不同欠采樣策略時,都使用“10折交叉驗證”.即將數(shù)據(jù)集劃分為10個互斥子集,然后將9個子集的并集作為訓練集,剩下的作為測試集,從而可以進行10次訓練和預測.欠采樣后的訓練集分別調(diào)用樸素貝葉斯(NaiveBayes)和支持向量機算法(SVM)完成對測試集的預測.預測結(jié)果對比實際情況,得出F-Measure和G-Mean的值,評估模型好壞.

首先比較在6個訓練集上應用三類不同Near-Miss距離后CCNM的表現(xiàn),分別稱之為CCNM-1、CCNM-2和CCNM-3.

表3 應用不同NearMiss距離CCNM在SVM上的F-Measure(G-Mean)Table 3 SVM′s F-Measure(G-Mean)applied with different NearMiss distance CCNM

從表3可以看出,應用NearMiss-2后的CCNM有著更為出色的表現(xiàn),從選擇策略上也可以發(fā)現(xiàn),NearMiss-2會從全局角度考慮多數(shù)類與少數(shù)類的距離,通過這種方式選出的多數(shù)類會均勻的分布在少數(shù)類的周圍,從而更容易找出分類界限.NearMiss-1從局部著手,只考慮最近的那么三個,選出的多數(shù)類不會均勻分布在少數(shù)類周圍.會出現(xiàn)某些少數(shù)類周圍有大量多數(shù)類,而某些周圍幾乎沒有.那么,大量多數(shù)類環(huán)繞著少數(shù)類就會導致很低的查全率(recall),相反則會導致很低的查準率(pre-cision).NearMiss-3雖然會“刻意”使少數(shù)類周圍有一定量的多數(shù)類,但局部仍然會出現(xiàn)某一類樣本密集,導致少數(shù)類預測(PositiveAccuracy)、多數(shù)類預測(NegativeAccuracy)都不夠理想.

表4 各欠采樣方法在SVM上的F-Measure(G-Mean)表現(xiàn)Table 4 Different under-sampling methods′F-Measure(G-Mean)using SVM

表5 各欠采樣方法在NaiveBayes上的F-Measure(G-Mean)表現(xiàn)Table 5 Different under-sampling methods′F-Measure(G-Mean)using NaiveBayes

表4和表5可以看到應用NearMiss-2后的CCNM算法與其它算法在10個數(shù)據(jù)集上F-Measure和G-Mean的表現(xiàn).隨機欠采樣是最簡單的方法,但如上表展示一樣,由于隨機性會去除大量的有用信息,R-andom算法無論在F-Measure還是G-Mean上都有著較低的分數(shù).但值得注意的是,隨機欠采樣在le-tter、wine和balance數(shù)據(jù)集上有著尚可的表現(xiàn),原因是這兩個數(shù)據(jù)集是多類別的,將稀有類別作為少數(shù)類而其他類別作為多數(shù)類時,隨機欠采樣后的多數(shù)類樣本在各個類別的分布可能是比較均勻的,利于后面的分類學習.CCNM算法首先利用聚類將多數(shù)類樣本進行歸類,再利用NearMiss-2對各個簇周圍少數(shù)類樣本個數(shù)進行分析,這樣選出的多數(shù)類樣本不僅具有更豐富的信息,在樣本空間分布上也能圍繞著少數(shù)類.因此,CCNM在不平衡數(shù)據(jù)分類任務中有更好的性能,尤其在不平衡度較高的yeast和glass數(shù)據(jù)集上提升明顯,聚類在此處起到了很明顯的去噪聲的作用,同時保留了信息量高的多數(shù)類.

5 總 結(jié)

在各行業(yè)應用領(lǐng)域中,不平衡數(shù)據(jù)問題是較為常見的,數(shù)據(jù)類別分布不均會直接影響學習過程,給最后的預測造成困擾.本文提出一種結(jié)合KMea-ns聚類和NearMiss距離的欠采樣算法CCNM,在應用UCI數(shù)據(jù)集后,驗證了該算法在處理不平衡數(shù)據(jù)集問題的有效性,提高了學習器的分類性能.CCNM欠采樣后的多數(shù)類樣本數(shù)目約等于少數(shù)類樣本數(shù)目,如何使得采樣后的數(shù)目更加接近或者等于少數(shù)類樣本,以及結(jié)合聚類和NearMiss距離的過采樣方法是今后工作的下一個目標.