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

葉 楓 丁 鋒

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

0 引 言

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

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

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

1 相關知識

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

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

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

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

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

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

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

如圖1-圖4所示。

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

圖2 碎片問題

圖3 噪音問題

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

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

1.2 k-means聚類算法

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

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)作為目標函數(shù)：

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

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

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

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

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

表1 混淆矩陣

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

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

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

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

其中β≥0,且常取1。

在分類方法中，經(jīng)常使用準確率作為評價指標，但是在不平衡數(shù)據(jù)分類中，用準確率來評價分類性能的好壞是不恰當?shù)?。例如在具?%的少數(shù)類樣本中，將所有樣本都預測為多數(shù)類的準確率為99%,盡管沒分類出任何少數(shù)類。

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

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

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

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

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

1) 將樣本訓練集k-means 聚類；

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

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

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

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

6) 新樣本集new_s 進行分類訓練。

算法流程圖見圖5。

圖5 KM-RF算法流程

3 實驗及結論

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

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

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

表3 k-means 欠抽樣處理后訓練集信息

3.2 實驗及結論

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

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

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

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

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

圖6 三種算法的Recall對比

圖7 三種算法的F值對比

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

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

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

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

圖8 部分數(shù)據(jù)集

屬性屬性描述PRE4用力肺活量FVC(數(shù)值型)PRE5第1秒用力呼氣容積FEV1(數(shù)值型)PRE6性能狀態(tài)-Zubrod量表(PRZ2,PRZ1,PRZ0)PRE7術前疼痛(T,F)PRE8術前咯血(T,F)PRE9術前呼吸苦難(T,F)PRE10術前咳嗽(T,F)PRE11術前虛弱(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ù)據(jù)隨機分配成7∶3，分別作為訓練集和測試集。并依次進行直接隨機森林算法分類；隨機欠抽樣處理后進行隨機森林算法分類和KM-RF算法分類，實驗過程同第三部分實驗。表5給出了數(shù)據(jù)在各個狀態(tài)下的多數(shù)類，少數(shù)類及其不平衡比。表6給出了實驗結果：三種算法的少數(shù)類召回率和F值。

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

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

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

5 結 語

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

由于本實驗在確定λ值時，根據(jù)多數(shù)類樣本數(shù)目，多數(shù)類樣本和少數(shù)類樣本比，以及樣本聚合程度等綜合考慮，定性得出。另外當少數(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].計算機應用研究,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].計算機科學,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] 劉學,張素偉.基于二次隨機森林的不平衡數(shù)據(jù)分類算法[J].軟件,2016,37(7):75-79.

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

[17] 王丹丹,陳情,畢平.肺癌左全肺切除術后心肺并發(fā)癥的發(fā)生與術前低肺功能的相關性[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.