基于聚類融合欠采樣的不平衡分類方法

葉 楓 江永省

(浙江工業(yè)大學管理學院 浙江 杭州 310023)

0 引 言

不平衡分類是機器學習中的一個重要組成部分，主要指建立一個數(shù)學模型對不平衡數(shù)據(jù)集進行分類。在傳統(tǒng)學習方法中，所有樣本類別的權(quán)重相同，容易造成多數(shù)類的分類精確高，但少數(shù)類的分類精度低的情況(即多數(shù)類掩蓋了少數(shù)類的特征)。類似的應用例子有疾病診斷[1-2]、信用卡欺詐消費[3]、網(wǎng)絡入侵檢測[4]和情緒分析[5]等。顯然，在這些不平衡數(shù)據(jù)集中，少數(shù)類被錯分成多數(shù)類時，帶來的損失更大。因此，許多學者對如何提高少數(shù)類分類精度展開了研究。

縱觀過去的研究，學者們基于統(tǒng)計學與機器學習的知識，提出了許多種經(jīng)典的方法來構(gòu)建分類模型，如多元判別分析、邏輯回歸、神經(jīng)網(wǎng)絡、決策樹、隨機森林、樸素貝葉斯、支持向量機和Adaboost等。文獻[6-7]的研究表明，集成模型的預測效果普遍優(yōu)于單個模型，有效提高了模型泛化能力。

不平衡分類的解決方法眾多，按照分類的步驟，可以將其分為特征選擇、數(shù)據(jù)分布調(diào)整、模型訓練算法幾類[8]。重采樣技術(shù)是常用的數(shù)據(jù)分布調(diào)整手段，主要通過增加少數(shù)類樣本或減少多數(shù)類樣本來平衡數(shù)據(jù)集，其方法包括過采樣、欠采樣，典型的例子如隨機欠采樣(random under-sampling, RUS)、隨機過采樣(random over-sampling, ROS)。在重采樣方法中，過采樣可能會造成模型的過擬合，欠采樣則可能會丟失一些重要數(shù)據(jù)。

1 相關(guān)工作

2002年，Chawla等[9]通過合成少數(shù)類樣本來平衡數(shù)據(jù)集，提出了SMOTE算法，并將SMOTE算法與Boosting算法結(jié)合，提出了SMOTEBoost[10]算法。Han等[11]指出，SMOTE在合成少數(shù)類樣本時對噪聲比較敏感，合成過程較為盲目，并針對其不足提出了BSM(Borderline-SMOTE)算法。BSM算法將SMOTE算法與少數(shù)類邊界信息融合，減少了冗余樣本的生成。

Kubat等[12]提出，欠采樣算法的效果優(yōu)于過采樣。文獻[13]經(jīng)過多次實驗表明，在多個數(shù)據(jù)集的平均性能上，欠采樣算法RUS優(yōu)于ROS、SMOTE和BSM等過采樣算法。傳統(tǒng)欠采樣方法主要有RUS、ClusterCentroids 、Tomeklinks、NearMiss[14]和OSS(one-sided selection)[12]等。ClusterCentroids 是一種基于原型生成的欠采樣方法，在數(shù)據(jù)集可以聚類成簇的前提下，這種方法能通過生成樣本替代原始數(shù)據(jù)集，高效地減少樣本。OSS是由Tomeklinks改進的啟發(fā)式算法，同樣具有降噪思想，目的是將多數(shù)類的噪聲樣本、邊界樣本、冗余樣本刪除，從而得到類別分布更均衡的數(shù)據(jù)集。張梟山等[15]將聚類融合欠抽樣與代價敏感學習思想融入Boosting技術(shù)，有效提高了正類分類效果。Tumer 等[16]提出一種基于自適應投票聚類VACs，在無噪聲環(huán)境下的效果不弱于傳統(tǒng)方法，在一些傳統(tǒng)方法不適用的有噪聲環(huán)境中也有較好的效果。牛壯等[17]通過聚類融合方法來去除數(shù)據(jù)集中的冗余樣本，從而得到了一種改良的欠采樣方法。該方法充分考慮到欠采樣對數(shù)據(jù)分布造成的影響，但同時文獻中也指出可能造成對多數(shù)類過度刪除。文獻[18]表明，對于不平衡分類問題，多數(shù)類中的噪聲樣本造成的危害比少數(shù)類噪聲更高，少數(shù)類噪聲即使比例較大，影響也相對較小。Yu 等[19]提出了一種新的抗噪聲聚類融合算法AP2CE，在大多數(shù)的數(shù)據(jù)集，尤其是噪聲數(shù)據(jù)集上具有更高的準確率。由于AP2CE算法的聚類共識函數(shù)較為復雜，因此不適用于高維數(shù)據(jù)集，在保證高準確率的同時需要付出較高的計算成本。

綜上所述，如何改良欠采樣算法以提高抗噪聲能力是目前的一個研究方向。本文通過提出一個新的異常指標，結(jié)合了聚類融合欠采樣和高效的異常檢測算法iForest，得到改進欠采樣RUIF算法，并與XGboost[20]算法組合，進而得到RUIF-XG算法。實驗結(jié)果證明，本文算法有效提高了XGboost算法在不平衡分類中的F1值與AUC值。

2 算法設計

2.1 聚類融合算法

聚類算法是無監(jiān)督學習方法中的一種典型方法，通過對未標記樣本的學習，把相似度高的樣本聚集成一組，進而將數(shù)據(jù)集劃分成若干個簇。一般地，聚類算法對數(shù)據(jù)集往往存在一個預設，例如劃分聚類適用于凸形分布、密度相近的數(shù)據(jù)集。然而，現(xiàn)實中存在著很多不規(guī)則、形狀復雜或分布未知的數(shù)據(jù)集。因此，實際應用時很難針對一個數(shù)據(jù)集找到一種較合適的聚類算法。針對這一現(xiàn)象，有學者提出了聚類融合[21]方法。

聚類融合是一種較新的聚類方法，通過合并多次聚類結(jié)果從而得到一個更優(yōu)的聚類劃分。相對于單一聚類，聚類融合的魯棒性、適用性、穩(wěn)定性、可拓展性更加出色。由于聚類融合方法能更好地揭示數(shù)據(jù)集的真實分布，因而可以用來解決分類算法中的不穩(wěn)定性問題，例如改進不平衡數(shù)據(jù)分類問題。

在各種聚類算法中，k-means算法時間復雜度低，運行速度快，常被用于聚類融合來產(chǎn)生聚類結(jié)果。

2.2 iForest算法

iForest 算法是Liu等[22]提出的一種無監(jiān)督異常檢測算法。該算法將噪聲理解為“密度稀疏、易被分離的離群點”。為劃分出噪聲樣本，不同于傳統(tǒng)方法中以距離、密度等指標去描述數(shù)據(jù)的疏離程度的方式，iForest算法使用一個隨機超平面，以類似切分蛋糕的方式，將數(shù)據(jù)空間分割成兩個子空間，再以同一方式對每個子空間持續(xù)進行分割，直到所有樣本無法再繼續(xù)分割。iForest包含多個二叉樹iTree(Isolation Tree)，其中iTree構(gòu)造過程如下：

(1) 隨機采樣得到子樣本集，子集中樣本個數(shù)為n，作為二叉樹的根節(jié)點。

(2) 隨機取一個屬性作為節(jié)點，并在該屬性中隨機選擇一個值作為切割點。

(3) 用切割點將子樣本集分割成兩個子集，分別作為左節(jié)點和右節(jié)點。

(4) 復步驟(2)和步驟(3)，直到節(jié)點無法切割或二叉樹已經(jīng)達到限定高度。

(5) 記錄葉子節(jié)點到根節(jié)點的路徑長度h(x)。

(6) 記錄樣本x在n個樣本中的異常指數(shù)s(x,n)。

(1)

式中：s(x,n)∈[0,1],接近0表示正常，接近1表示異常；c(n)表達式為:

(2)

式中:ξ為歐拉常數(shù)。

(7) 代入二叉樹數(shù)量t的經(jīng)驗值后，可將t個iTree組成iForest，t的經(jīng)驗值為100，由Liu等[22]測算得到，計算樣本異常指數(shù)s(x,n)，其表達式為：

(3)

式中:E(h(x))表示對樣本x在所有iTree上的高度取均值。

(8) 確定閾值ρ之后，若異常指數(shù)大于ρ，代表樣本是噪聲樣本，否則判斷為正常樣本。

在高維數(shù)據(jù)集上，iForest算法由于采用了隨機切割思想，切割處理后可能仍存在一些噪聲維度，影響到檢測效果。

2.3 RUIF-XG算法

聚類融合保證了算法的魯棒性，增強了模型的泛化能力，異常檢測算法iForest計算效率高，對噪聲樣本識別率高，滿足了RUIF-XG算法的分類精度要求。結(jié)合聚類融合與iForest的優(yōu)點，本文提出一種改進欠采樣RUIF-XG算法。在分類中多數(shù)類噪聲樣本影響大，少數(shù)類噪聲樣本影響小，所以本文算法中應用iForest時只針對多數(shù)類進行檢測。

本文算法首先以k-means方法對多數(shù)類進行n次聚類，每次聚類產(chǎn)生k個聚類簇，對每個聚類簇使用iForest算法檢測噪聲樣本，并給予噪聲標記Cj(Xi)，進而計算樣本異常指標F(Xi)。通過異常指標來篩選、去除多數(shù)類噪聲樣本，減少了欠采樣過程中留下噪聲樣本的概率，保證了得到的樣本集更具代表性，有利于提高分類器的分類效果。

其中樣本異常指標F(Xi)本質(zhì)上是指在聚類融合算法中，樣本被判斷為噪聲的概率。通過聚類融合，樣本被iForest算法正確標識的可能性增大，減少了偶然的錯誤標識帶來的誤差。在處理高維數(shù)據(jù)集時，由于iForest自身的局限性，本文算法可能無法很好地檢測出噪聲樣本，對高維數(shù)據(jù)集的適用性相對較弱。本文算法流程如圖1 所示。

圖1 算法流程

具體算法描述如下：

輸入：少數(shù)類Sm，多數(shù)類SM，少數(shù)類數(shù)量m，多數(shù)類數(shù)量M，聚類次數(shù)n，刪除比例λ。

(1) 初始化,F(Xi)=0,i∈SM

(2) forj=1:n

(3) 指定簇數(shù)k，對多數(shù)類SM進行k-means聚類；

(4) 聚類后得到聚類成員πk，分別使用iForest算法檢測噪聲；

(5) 對每個聚類簇中被iForest算法標記為噪聲的樣本，給予噪聲標記Cj(Xi)：

(4)

(6) end forj

(7) 計算每個多數(shù)類樣本的異常指標F(Xi)：

(5)

式中:F(Xi)∈[0,1]接近1代表樣本異常，接近0代表樣本正常；

(8)F(Xi)按數(shù)值降序排列，刪除F(Xi)值非零、且排列靠前的μ個多數(shù)類樣本，μ的計算式為：

μ=INT(M×λ)

(6)

(9) 獲得少數(shù)類Sm與新的多數(shù)類SM1；

(10) 對SM1使用RUS方法得到子數(shù)據(jù)集SM2；

(11) 使用XGboost算法學習分類器H,并輸出分類結(jié)果。

3 實驗與分析

3.1 數(shù)據(jù)集描述

由于多分類過程能通過一定手段轉(zhuǎn)換成二分類，因此本文主要研究二分類的情況，少數(shù)類和多數(shù)類的類標簽按通俗習慣分別標為{1,0}。為了驗證本文算法的效率，使用UCI與KEEL數(shù)據(jù)庫中的七個不平衡數(shù)據(jù)集作為實驗數(shù)據(jù)。數(shù)據(jù)集中，只有cmc數(shù)據(jù)集是多分類數(shù)據(jù)集，選擇類標“2”作為少數(shù)類，其他類標作為多數(shù)類。其他數(shù)據(jù)集都是二分類數(shù)據(jù)集。不平衡率(Imbalanced Rate, IR)表示少數(shù)類與多數(shù)類的數(shù)量比例。數(shù)據(jù)集描述見表1。

表1 數(shù)據(jù)集描述

3.2 數(shù)據(jù)預處理

為保證測試效果，刪除breast數(shù)據(jù)集的編號屬性列，刪除seismic數(shù)據(jù)集中屬性值單一的三列數(shù)據(jù)。

對數(shù)據(jù)集進行歸一化處理，使用min-max標準化方法去量綱，保證不同特征屬性值的可比性。min-max標準化處理方法內(nèi)容為：找出每列特征屬性的最大值與最小值，將所有樣本的該屬性值減去最小值，再除以最大值與最小值的差。

歸一化計算公式如下：

(7)

3.3 不平衡分類的評估方法

表2為機器學習中二分類的混淆矩陣，TP和TN分別表示預測結(jié)果正確的實際少數(shù)類和多數(shù)類，F(xiàn)N和FP分別表示預測結(jié)果錯誤的實際少數(shù)類和多數(shù)類。

表2 混淆矩陣

在不平衡數(shù)據(jù)分類中，一般不直接使用準確率作為評估指標。針對不平衡分類，常用查準率(Precision)、查全率(Recall)、F1值(F1-Measure)，AUC等指標來評估分類器性能。

(8)

(9)

(10)

當F-Measure的β取1時，即是常見的F1-Measure，表示查準率與查全率的權(quán)重平均，F(xiàn)1越高表明分類效果越理想。

AUC是 ROC曲線的下方面積的直觀反映，取值越大代表模型分類能力越強，取值為1代表是完美分類器，取值為0.5代表等于隨機分類器。

本文使用AUC值與F1值作為性能評估標準。

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

本文實驗采用十折交叉驗證，每次將所有樣本隨機分成10份，取9份作為訓練集，剩余1份作為測試集。最后，將10次測試結(jié)果得到的評估值取均值,作為實驗最終結(jié)果。本次實驗將本文算法與base、RUS、CC (ClusterCentroids)、TL(TomekLinks)、OSS等五種情況進行對比。base代表對原始數(shù)據(jù)集直接使用分類器，其余4種皆是經(jīng)典的欠采樣算法。其中，分類算法來自Python的xgboost.xklearn包，采用標準模型與默認參數(shù)。欠采樣方法來自imblearn.ensemble包，欠采樣后多數(shù)類與少數(shù)類比例為1∶1。k-means算法的聚類次數(shù)取20次，刪除比例λ經(jīng)過多次對比測試，選擇λ取5%。實驗對比結(jié)果如表3、表4所示。每個數(shù)據(jù)集上的最優(yōu)評估值使用了粗體進行標注。

表3 各算法的AUC對比情況

表4 各算法的F1對比情況

實驗結(jié)果表明，相比直接使用分類器，使用欠采樣普遍提高了評估指標。可以看到，在大部分數(shù)據(jù)集上，本文算法的兩個評估指標均優(yōu)于其他4種欠采樣算法；在wdbc、breast數(shù)據(jù)集上，AUC指標略優(yōu)于其他算法，F(xiàn)1指標雖然不是最優(yōu)值，但仍優(yōu)于原本的RUS算法。

OSS算法同樣具有降噪思想，其在個別數(shù)據(jù)集上有最優(yōu)評估值，但在平均性能上，兩個評估值都不如本文算法，CC算法也是同理。綜上所述，本文算法在解決不平衡分類問題上，效果優(yōu)于其他幾種算法。造成這種結(jié)果的原因可能是RUS算法殘留了噪聲樣本，CC算法的生成樣本無法完全替代原始數(shù)據(jù)集，而TL算法與OSS算法將噪聲樣本與有用的邊界樣本一同刪除。

4 蛋白質(zhì)的亞細胞定位預測

蛋白質(zhì)的亞細胞定位指蛋白質(zhì)在細胞中的具體位置。近年來，在細胞生物學的進一步研究中，蛋白質(zhì)序列數(shù)據(jù)庫不斷擴大，蛋白質(zhì)亞細胞定位的價值越來越受到肯定?？茖W家們已經(jīng)普遍認識到，蛋白質(zhì)的定位對預測一些疾病的發(fā)生具有極重要的價值。比如，在我國70歲以上的老年群體中，阿爾茲海默癥(老年癡呆癥)的病患越來越多。大多數(shù)學者相信，大腦淀粉樣蛋白與阿爾茲海默癥的發(fā)生有關(guān)，對這種蛋白質(zhì)的相關(guān)研究可以用于預測阿爾茲海默癥。

現(xiàn)代研究指出，一切生命離不開蛋白質(zhì)，但只有在蛋白質(zhì)被轉(zhuǎn)運到特定位置時才能良好地參與到生命活動當中。因此蛋白質(zhì)的定位對揭示蛋白質(zhì)功能、理解復雜的生理過程具有重大意義。對病患而言，相關(guān)研究有助于醫(yī)學界研究疾病機理并研制新藥物，對未來患者的診斷治病起著巨大的作用。

現(xiàn)今已有多種實驗方法來對蛋白質(zhì)進行定位，如熒光顯微觀察、核磁共振法等。雖然實驗方法效果突出，但必須消耗巨大的時間成本與人力、物力，并不適用于大規(guī)模操作，因此，如喬善平等[23]的一部分學者們開始研究不同的預測模型，這些預測模型通過提取蛋白質(zhì)特征信息來給蛋白質(zhì)定位預測。

本次測試的數(shù)據(jù)集由大阪大學分子與細胞生物研究所的Kenta Nakai 創(chuàng)建，后由Paul Horton整理發(fā)布。數(shù)據(jù)集共包括1 484個酵母菌的樣本，因原數(shù)據(jù)集是多分類數(shù)據(jù)集，為符合測試要求，將蛋白質(zhì)位置類標“CYT”(胞質(zhì)或細胞骨架)作為少數(shù)類，其他位置類標作為多數(shù)類，并將序號屬性信息略去。數(shù)據(jù)集預處理后不平衡率IR為1∶2.21。表5給出了相關(guān)屬性信息。

表5 酵母數(shù)據(jù)集屬性

測試使用十折交叉驗證，將本文算法的提升效果與其他5種算法對比。詳細的實驗過程同本文第3節(jié)的實驗。表6列出了測試對比結(jié)果。

表6 酵母數(shù)據(jù)集實驗對比結(jié)果

可以看到，本文算法的F1、AUC評估值比直接使用分類器時分別提高11.83%與6.97%，比次優(yōu)的欠采樣方法分別提高2.72%與2.54%，均有顯著提升，說明了本文算法的實效性。

5 結(jié) 語

本文提出了一種新的改進欠采樣RUIF-XG算法，該算法結(jié)合了聚類融合欠采樣與iForest技術(shù)，通過在7個數(shù)據(jù)集上的比較驗證，證明其能降低多數(shù)類樣本中的噪聲樣本比率，進而一定程度上提高對不平衡分類的評估值，具有魯棒性。將本文算法用于蛋白質(zhì)的亞細胞定位預測，測試結(jié)果顯示預測效果得到提升，驗證了本文算法的實效性。后續(xù)工作將圍繞如何更好地得到噪聲樣本比率、提高算法對大數(shù)據(jù)的適應度這兩個方向展開。