不平衡數(shù)據(jù)分類研究及其應(yīng)用

葉 楓 丁 鋒

(浙江工業(yè)大學(xué)經(jīng)貿(mào)管理學(xué)院 浙江 杭州 310012)

0 引 言

不平衡數(shù)據(jù)是指在數(shù)據(jù)集中各個類別所占的比例不均衡，即某些類別的數(shù)量是其他類別的幾倍甚至幾十倍。此類數(shù)據(jù)在實際應(yīng)用中廣泛存在，如在檢測某種特定疾病[1]中，患該疾病的數(shù)量遠(yuǎn)遠(yuǎn)小于檢查人數(shù)；網(wǎng)站防御[2]中，網(wǎng)絡(luò)入侵的概率也遠(yuǎn)遠(yuǎn)小于正常訪問的概率；在過濾垃圾郵件[3]中，垃圾郵件的數(shù)量小于一般郵件的數(shù)量等。諸如此類問題中，對于少數(shù)類的分類結(jié)果對實際應(yīng)用異常重要，然而傳統(tǒng)分類方法通常假定數(shù)據(jù)集是平衡的，因此對平衡數(shù)據(jù)的分類精確度較高，而對于不平衡數(shù)據(jù)的分類精確度卻往往較低[4]，這使得研究不平衡數(shù)據(jù)的分類問題成為近些年數(shù)據(jù)挖掘研究的熱點問題。

針對不平衡數(shù)據(jù)的分類問題，目前主要從算法層面和數(shù)據(jù)層面兩方面來解決[5]：在算法層面主要是改進算法以適應(yīng)不平衡數(shù)據(jù)的分類，如代價敏感學(xué)習(xí)、集成學(xué)習(xí)等。在不平衡數(shù)據(jù)分類中，少數(shù)類往往是分類的重點，代價敏感學(xué)習(xí)給予每個類別不同的權(quán)重，即代價，當(dāng)分類器錯分少數(shù)類時將付出更多的代價，從而有效地提高少數(shù)類的分類準(zhǔn)確率。但在實際應(yīng)用中，代價敏感學(xué)習(xí)存在代價往往需要人為設(shè)定[6]，算法沒有普遍適用性等缺點。集成學(xué)習(xí)算法的思想則是多個分類器集成的分類效果比單個分類器效果更佳，從而將多個分類器的分類結(jié)果進行組合，提高分類效果。數(shù)據(jù)層面主要針對的是數(shù)據(jù)處理，改變數(shù)據(jù)結(jié)構(gòu)，較為常用的是過抽樣和欠抽樣技術(shù)。過抽樣主要增加少數(shù)類樣本，使少數(shù)類和多數(shù)類達(dá)到平衡。SMOTE方法是較為經(jīng)典的過抽樣數(shù)據(jù)處理方法[7]，但是可能帶來數(shù)據(jù)過度擬合，使多數(shù)類與少數(shù)類的邊界更加模糊[8]等缺點；而欠抽樣主要刪除多數(shù)類樣本，使樣本數(shù)據(jù)平衡，但隨機刪除多數(shù)類樣本，存在使多數(shù)類樣本特性丟失等風(fēng)險[9]。

基于此，本文提出了一種基于k-means 聚類的欠抽樣分類算法，利用k-means算法將樣本數(shù)據(jù)進行聚類，剔除多數(shù)類樣本與少數(shù)類樣本的模糊邊界點和噪聲點，同時又能減少欠抽樣過程中樣本特性丟失的風(fēng)險，以此縮小類別不平衡性，從而提高對少數(shù)類和整體數(shù)據(jù)的分類正確率。

1 相關(guān)知識

1.1 不平衡數(shù)據(jù)分類

傳統(tǒng)分類方法以數(shù)據(jù)平衡化為基礎(chǔ)，即分類的數(shù)據(jù)類別比例分布較為均勻，但是當(dāng)實際數(shù)據(jù)不平衡性較為嚴(yán)重時，算法性能就較差。不平衡數(shù)據(jù)導(dǎo)致分類方法對少數(shù)類分類性能下降的原因如下：

1) 少數(shù)類樣本的絕對稀少[10]；

2) 少數(shù)類與多數(shù)類比例過分懸殊，少數(shù)類樣本相對稀少[11]；

3) 數(shù)據(jù)碎片問題[12]、噪聲問題[11]；

4) 不恰當(dāng)?shù)脑u價方法[13]；

5) 少數(shù)類與多數(shù)類邊界模糊，重疊度較高[14]。

如圖1-圖4所示。

圖1 少數(shù)類樣本絕對稀少

圖2 碎片問題

圖3 噪音問題

圖4 少數(shù)類與多數(shù)類邊界重疊度高

而事實上，相關(guān)研究表明當(dāng)不平衡數(shù)據(jù)具有足夠多的樣本時，少數(shù)類樣本相對稀缺并不一定導(dǎo)致分類算法的性能下降[14]；當(dāng)不平衡數(shù)據(jù)多數(shù)類和少數(shù)類的重疊度較低時，傳統(tǒng)分類算法仍具有較好的分類屬性，而當(dāng)多數(shù)類與少數(shù)類具有較高重疊度時，分類算法的性能較差[15]。

1.2 k-means聚類算法

聚類屬于無監(jiān)督機器學(xué)習(xí)方法，即事先無需了解數(shù)據(jù)的分布情況，按照數(shù)據(jù)特征之間的相似度將數(shù)據(jù)自動劃分成組，通過迭代，使組內(nèi)樣本之間的相識度盡可能高，而不同組的樣本相似度盡可能低。聚類中的組亦稱作簇。聚類系統(tǒng)將樣本集數(shù)據(jù)經(jīng)過聚類算法處理后，輸出簇集。聚類可以初步評價數(shù)據(jù)的樣本結(jié)構(gòu)，用來研究各數(shù)據(jù)間的相關(guān)程度尤其適用。

k-means算法是一種經(jīng)典的聚類算法，采用距離來衡量兩個對象的相似程度(通常采用歐式距離)，距離越短，表示兩個對象的相似度越高。k-means具體算法流程如下：

1) 將數(shù)據(jù)集D(X1,X2,…,Xn)劃分為K個簇(C1,C2,…,Cn)。

2) 從數(shù)據(jù)集D中任意選取K個對象作為初始的簇心(V1,V2,…,Vn)。

3) 計算每一個對象與簇心的距離，通常使用誤差平方和SSE(Sum of Squaerd Error)作為目標(biāo)函數(shù)：

4) 將每個對象劃分到距離最近的簇。

5) 重新計算每個簇中對象的均值，作為新的簇心。

6) 重復(fù)3-5步，直到k個簇中心不再發(fā)生變化。

1.3 不平衡數(shù)據(jù)分類算法評價指標(biāo)

混淆矩陣是評價不平衡數(shù)據(jù)的常用工具，利用混淆矩陣可以獲取分類準(zhǔn)確率(Accuracy)、精度(Precision)、召回率(Recall)、F度量值等指標(biāo)，混淆矩陣見表1。

表1 混淆矩陣

1) 分類準(zhǔn)確率(Accuracy)：表示樣本正確分類的個數(shù)與樣本總數(shù)的比例。

2) 精度(Precision)：表示樣本少數(shù)類正確分類的個數(shù)與分類為少數(shù)類總數(shù)的比例。

3) 召回率(Recall):表示樣本少數(shù)類正確分類的個數(shù)與樣本實際少數(shù)類個數(shù)的比例。

4) F值：表示精度和召回率的調(diào)和平均值。

其中β≥0,且常取1。

在分類方法中，經(jīng)常使用準(zhǔn)確率作為評價指標(biāo)，但是在不平衡數(shù)據(jù)分類中，用準(zhǔn)確率來評價分類性能的好壞是不恰當(dāng)?shù)摹＠缭诰哂?%的少數(shù)類樣本中，將所有樣本都預(yù)測為多數(shù)類的準(zhǔn)確率為99%,盡管沒分類出任何少數(shù)類。

精度和召回率是評價不平衡數(shù)據(jù)的常用指標(biāo)，但若將每個樣本都預(yù)測為少數(shù)類，分類的召回率將達(dá)到100%，但是精度將很差；相反，若正確分類的少數(shù)類很少，而又將多數(shù)類全部識別，則分類的精度將達(dá)到很高，但召回率卻很低。而F值具有平衡精度和召回率的效果，F(xiàn)值越高，能保證精度和召回率都較高。

本文將采用召回率和F值兩個較常用的評價指標(biāo)。

2 基于k-means 的欠抽樣分類算法

由于多數(shù)類問題普遍可以轉(zhuǎn)為二分類問題，為簡便起見，本文以二分類問題為研究對象。

針對欠抽樣方法中，隨機欠抽樣單純?yōu)槭箶?shù)據(jù)多數(shù)類和少數(shù)類達(dá)到平衡，刪除多數(shù)類，而不能針對性地去除一些與少數(shù)類樣本相似的多數(shù)類的問題。引入了k-means 聚類算法，先將樣本集數(shù)據(jù)進行k-means 聚類，根據(jù)各樣本之間的相似度將樣本數(shù)據(jù)進行分組聚類，則樣本屬性相似度較高的數(shù)據(jù)將會形成一組，而不同組之間樣本屬性的相似度較低。從而可以有效地辨別出混雜在少數(shù)類中的多數(shù)類樣本。如此可以更有效地刪除多數(shù)類的噪聲樣本，降低多數(shù)類與少數(shù)類的重疊度和不平衡度，為避免由于聚類中心點隨機選擇，導(dǎo)致的聚類不同，我們進行多次聚類，以刪除穩(wěn)定的噪聲和重疊點。同時，為降低丟失多數(shù)類特性的風(fēng)險，我們引入刪除比例因子λ，動態(tài)調(diào)整剔除個數(shù)。算法流程描述如下：

1) 將樣本訓(xùn)練集k-means 聚類；

2) 計算每個簇的數(shù)目，為個數(shù)多的簇的每個對象標(biāo)號kmaj，另一個簇的對象標(biāo)號kmin；

3) 遍歷多數(shù)類M，選出標(biāo)號為kmin的對象；

4) 進行多次聚類，重復(fù)2-3步驟，將選出的多數(shù)類標(biāo)號FM，并按出現(xiàn)概率正向排序；

5) 根據(jù)比例因子Mλ≤FM，刪除選出的多數(shù)類，得到新樣本集new_s；

6) 新樣本集new_s 進行分類訓(xùn)練。

算法流程圖見圖5。

圖5 KM-RF算法流程

3 實驗及結(jié)論

3.1 數(shù)據(jù)處理

從UCI數(shù)據(jù)庫中選取若干組數(shù)據(jù)集，參考以往文獻(xiàn)，對具備多種類別的數(shù)據(jù)進行某些類的合并，數(shù)據(jù)集信息見表2(不平衡比為多數(shù)類比少數(shù)類的比例)。并將數(shù)據(jù)集按訓(xùn)練集和測試集7∶3的比例進行隨機分配，對訓(xùn)練集進行標(biāo)準(zhǔn)化，進行k-means欠抽樣處理，處理后訓(xùn)練集的信息見表3。

表2 UCI數(shù)據(jù)集信息

表3 k-means 欠抽樣處理后訓(xùn)練集信息

3.2 實驗及結(jié)論

隨機森林集成多個決策樹分類器，分類效果較單個分類器有所提高。故本實驗采用隨機森林作為分類算法，為使實驗更具說服性，分別對比了三種算法的實驗結(jié)果。

1) 未進行欠抽樣處理直接利用隨機森林算法分類。

2) 隨機欠抽樣處理后進行隨機森林算法分類。

3) KM-RF算法。即基于k-means欠抽樣的隨機森林分類算法。且隨機欠抽樣的λ值與KM-RF的λ值相等。

圖6，圖7分別給出了不同數(shù)據(jù)集的Recall和F 值，為使結(jié)果更加客觀，Recall和F值皆是10次實驗，各取其平均值。實驗結(jié)果表明KM-RF算法在Recall和F值上均好于其他兩種算法，在對不平衡數(shù)據(jù)進行分類時具有良好的性能。

圖6 三種算法的Recall對比

圖7 三種算法的F值對比

4 原發(fā)性肺癌術(shù)后生存率預(yù)測

胸外科腫瘤患者，因其疾病的病、生理特性，多數(shù)需手術(shù)治療，而腫瘤的特殊攻擊性，患者伴有的一種或多種基礎(chǔ)病，則加大了手術(shù)的風(fēng)險性。故各級醫(yī)師在術(shù)前需對患者進行綜合風(fēng)險評估，以確保患者的醫(yī)療性安全[16]。

醫(yī)師對患者進行評估的項目除了患者的年齡，營養(yǎng)狀況等基本信息，還包括患者病變器官的性質(zhì)、病變的程度，手術(shù)切除器官范圍等，以便決定患者對手術(shù)的耐受程度和預(yù)測術(shù)后生存質(zhì)量[17]。

本實驗原數(shù)據(jù)收集自弗羅茨瓦夫胸腔外科中心，以預(yù)測原發(fā)性肺癌術(shù)后生存率，數(shù)據(jù)包括2007年-2011年接受肺切除術(shù)的1 200例原發(fā)性肺癌患者，后經(jīng)Maciej Zieba教授整理后發(fā)布，數(shù)據(jù)最終由470個實例組成，患者一年存活率與死亡率的不平衡比為5.71。圖8給出了公布的部分?jǐn)?shù)據(jù)和預(yù)測因子。表4給出了術(shù)前預(yù)測因子[18]。

圖8 部分?jǐn)?shù)據(jù)集

屬性屬性描述PRE4用力肺活量FVC(數(shù)值型)PRE5第1秒用力呼氣容積FEV1(數(shù)值型)PRE6性能狀態(tài)-Zubrod量表(PRZ2,PRZ1,PRZ0)PRE7術(shù)前疼痛(T,F)PRE8術(shù)前咯血(T,F)PRE9術(shù)前呼吸苦難(T,F)PRE10術(shù)前咳嗽(T,F)PRE11術(shù)前虛弱(T,F)PRE14原發(fā)腫瘤的TNM分期(C11(最小)到OC14(最大))PRE172型糖尿病(T,F)PRE19心肌梗塞6個月(T,F)PRE25外周動脈疾病(T,F)PRE30吸煙(T,F)PRE32哮喘(T,F)AGE手術(shù)是年齡(數(shù)值型)

將數(shù)據(jù)隨機分配成7∶3，分別作為訓(xùn)練集和測試集。并依次進行直接隨機森林算法分類；隨機欠抽樣處理后進行隨機森林算法分類和KM-RF算法分類，實驗過程同第三部分實驗。表5給出了數(shù)據(jù)在各個狀態(tài)下的多數(shù)類，少數(shù)類及其不平衡比。表6給出了實驗結(jié)果：三種算法的少數(shù)類召回率和F值。

表5 處理后樣本數(shù)據(jù)狀態(tài)

表6 三種算法Recall和F值對比

由該預(yù)測實驗表明，KM-RF算法對比傳統(tǒng)分類算法，在Recall和F值上均有顯著的提高。

5 結(jié) 語

不平衡數(shù)據(jù)在實際應(yīng)用中普遍存在，這使得對該類數(shù)據(jù)的研究成為數(shù)據(jù)挖掘領(lǐng)域的研究熱點。本文根據(jù)k-means 聚類的特性，提出了基于k-means聚類的分類算法，并引入刪除因子λ，降低欠抽樣時丟失多數(shù)類數(shù)據(jù)的風(fēng)險。實驗表明，該算法具有較好的召回率和F值。最后本文將該算法應(yīng)用于預(yù)測原發(fā)性肺癌術(shù)后一年期生存率，實驗表明數(shù)據(jù)經(jīng)k-means欠抽樣處理后，分類算法的預(yù)測率具有顯著的提升，也證明了該算法的實效性。

由于本實驗在確定λ值時，根據(jù)多數(shù)類樣本數(shù)目，多數(shù)類樣本和少數(shù)類樣本比，以及樣本聚合程度等綜合考慮，定性得出。另外當(dāng)少數(shù)類樣本較分散時，即聚類效果不明顯時，算法分類較不明顯。后續(xù)研究將重點放在如何定量確定λ值及其范圍，使算法分類性能進一步優(yōu)化。

[1] Ren F,Cao P,Li W,et al.Ensemble based adaptive over-sampling method for imbalanced data learning in computer aided detection of microaneurysm[J].Computerized Medical Imaging & Graphics the Official Journal of the Computerized Medical Imaging Society,2017,55(1):54-67.

[2] Radivojac P,Korad U,Sivalingam K M,et al.Learning from class-imbalanced data in wireless sensor networks[C]//Conference:Conference:Vehicular Technology Conference,2003.VTC 2003-Fall.2003 IEEE 58th,Volume:5.IEEE Xplore,2003:3030-3034.

[3] Fawcett T.“In vivo” spam filtering:a challenge problem for KDD[J].Acm Sigkdd Explorations Newsletter,2003,5(2):140-148.

[4] 李勇,劉戰(zhàn)東,張海軍.不平衡數(shù)據(jù)的集成分類算法綜述[J].計算機應(yīng)用研究,2014,31(5):1287-1291.

[5] Zhang X,Song Q,Wang G,et al.A dissimilarity-based imbalance data classification algorithm[J].Applied Intelligence,2015,42(3):544-565.

[6] Elkan C.The Foundations of Cost-Sensitive Learning[C]//Seventeenth International Joint Conference on Artificial Intelligence.2001:973-978.

[7] 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(1):321-357.

[8] 張梟山,羅強.一種基于聚類融合欠抽樣的不平衡數(shù)據(jù)分類方法[J].計算機科學(xué),2015,42(S2):63-66.

[9] Sun Z,Song Q,Zhu X,et al.A novel ensemble method for classifying imbalanced data[J].Pattern Recognition,2015,48(5):1623-1637.

[10] Weiss G M.Mining with rarity[J].Acm Sigkdd Explorations Newsletter,2004,6(1).

[11] Weiss G M.Mining with rarity:a unifying framework[J].Acm Sigkdd Explorations Newsletter,2004,6(1):7-19.

[12] Weiss G M,Hirsh H.A Quantitative Study of Small Disjuncts[C]//Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence.AAAI Press,1970:665-670.

[13] Provost F,Fawcett T.Robust Classification for Imprecise Environments[J].Machine Learning,2001,42(3):203-231.

[14] Ng W W Y,Zeng G,Zhang J,et al.Dual autoencoders features for imbalance classification problem[J].Pattern Recognition,2016,60:875-889.

[15] 劉學(xué),張素偉.基于二次隨機森林的不平衡數(shù)據(jù)分類算法[J].軟件,2016,37(7):75-79.

[16] 胡曉星,李輝.胸外科腫瘤患者術(shù)前醫(yī)療風(fēng)險評估表在病案中的應(yīng)用[J].中國病案,2014(11):15-17.

[17] 王丹丹,陳情,畢平.肺癌左全肺切除術(shù)后心肺并發(fā)癥的發(fā)生與術(shù)前低肺功能的相關(guān)性[J].中國腫瘤臨床,2015,42(7):397-400.

[18] Zieba M,Tomczak J M,Lubicz M,et al.Boosted SVM for extracting rules from imbalanced data in application to prediction of the post-operative life expectancy in the lung cancer patients[J].Applied Soft Computing,2014,14(1):99-108.