一種不平衡數(shù)據(jù)集成分類方法

王思晨 丁家滿

摘要：不平衡數(shù)據(jù)在各個(gè)應(yīng)用領(lǐng)域普遍存在。在處理不平衡數(shù)據(jù)時(shí)，破壞原始數(shù)據(jù)的分布特點(diǎn)和丟棄多數(shù)類樣本的潛在信息都會(huì)降低分類精度，為此，提出一種不平衡數(shù)據(jù)集成分類方法。從多數(shù)類樣本中依據(jù)計(jì)算得到的綜合權(quán)重進(jìn)行隨機(jī)采樣，并與少數(shù)類樣本組成新的訓(xùn)練樣本子集；為了保證基分類器的差異性，將投影得到的不同樣本子集作為各個(gè)基分類器的訓(xùn)練樣本，通過多分類器集成學(xué)習(xí)獲得最終分類結(jié)果；在UCI數(shù)據(jù)集下進(jìn)行實(shí)驗(yàn)。結(jié)果表明，該方法不僅能夠提高少數(shù)類樣本的分類性能，而且能夠有效提高整體分類精度。

關(guān)鍵詞：不平衡數(shù)據(jù)；分類；集成學(xué)習(xí)；綜合權(quán)重

DOIDOI：10.11907/rjdk.173258

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：1672-7800（2018）008-0076-05

英文摘要Abstract：Imbalanced data is widespread in various application fields.When dealing with imbalanced data，breaking the distribution characteristics of the original data and discarding the latent information in the majority class samples will decrease classification accuracy.Therefore，in this paper，an integrated classification method for imbalance data is proposed.Firstly we randomly extract from the majority samples based on the calculated comprehensive weight，combine the extracted samples with the minority samples into new training samples； then，in order to ensure the difference between the base classifiers，we use the same subset of projections as the training samples of each base classifier，and get the final classification results by ensemble learning of multiple classifiers.Finally，experiments have been done on UCI data sets and the results show that this method can not only improve the classification performance of the minority class samples，but also effectively improve the overall classification accuracy.

英文關(guān)鍵詞Key Words：imbalance data；classification；ensemble learning；comprehensive weight

0 引言

分類是數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)領(lǐng)域研究的重要內(nèi)容，可以有效幫助人們對(duì)獲取的數(shù)據(jù)進(jìn)行預(yù)測分析、對(duì)未知的模式樣本進(jìn)行判斷識(shí)別。目前，已有許多經(jīng)典的分類算法，例如人工神經(jīng)網(wǎng)絡(luò)、決策樹、支持向量機(jī)（SVM）等，用它們對(duì)平衡數(shù)據(jù)進(jìn)行分類一般都能取得較好的分類效果。但是在實(shí)際應(yīng)用中不平衡數(shù)據(jù)普遍存在于各個(gè)應(yīng)用領(lǐng)域，例如文本分類[1]、疾病診斷[2]以及網(wǎng)絡(luò)入侵檢測[3]等。然而傳統(tǒng)分類算法為了追求總體分類性能，通常只基于平衡數(shù)據(jù)分布或者忽略樣本中的少數(shù)類樣本，從而導(dǎo)致少數(shù)類樣本分類準(zhǔn)確率過低，分類器性能下降[4-7]。因此，研究用于處理不平衡數(shù)據(jù)集的分類方法，有效提高對(duì)少數(shù)類的分類準(zhǔn)確率與分類器的整體性能顯得尤為重要。

當(dāng)前，不平衡數(shù)據(jù)分類問題的解決思路主要包括改變數(shù)據(jù)分布和改進(jìn)已有分類算法。改變數(shù)據(jù)分布以達(dá)到數(shù)據(jù)平衡最常見的策略有隨機(jī)過采樣（over-sampling）、隨機(jī)欠采樣（under-sampling）[8-9]。隨機(jī)過采樣是指對(duì)少數(shù)類的樣本進(jìn)行復(fù)制，使數(shù)據(jù)集的樣本數(shù)達(dá)到平衡，隨機(jī)欠采樣則以一定策略選取多類樣本中的一個(gè)子集達(dá)到同樣目的。過采樣中應(yīng)用最廣泛的是 Chawla 等[10]提出來的SMOTE 算法，該算法的本質(zhì)是改進(jìn)隨機(jī)過采樣策略，通過擴(kuò)充少數(shù)類樣本集使得樣本數(shù)目達(dá)到均衡。文獻(xiàn)[11]提出基于RSBoost算法的不平衡數(shù)據(jù)分類方法，該方法采用SMOTE算法對(duì)少數(shù)類進(jìn)行過采樣處理，然后對(duì)整個(gè)數(shù)據(jù)集進(jìn)行隨機(jī)欠采樣處理，以改善整個(gè)數(shù)據(jù)集的不平衡性，提高少數(shù)類的分類準(zhǔn)確性。文獻(xiàn)[12]針對(duì)采用隨機(jī)過采樣處理不平衡數(shù)據(jù)后，可能會(huì)導(dǎo)致不平衡數(shù)據(jù)集分布的整體變化以及模糊正負(fù)類邊界問題，提出基于 KM-SMOTE 和隨機(jī)森林的不平衡數(shù)據(jù)分類方法。文獻(xiàn)[13]提出的RUSBoost算法是在AdaBoost算法迭代過程中采用隨機(jī)欠采樣技術(shù)（RUS）從多數(shù)類中隨機(jī)選擇樣本，但不分配新的權(quán)重，從而使算法更加關(guān)注少數(shù)類樣本，該算法具有實(shí)現(xiàn)簡單、訓(xùn)練時(shí)間短等優(yōu)勢，但是在欠采樣中可能會(huì)移除潛在的有用多數(shù)類樣本。文獻(xiàn)[14]提出了EusBoost算法，采用欠采樣方法選擇多數(shù)類樣本中具有代表性的樣本，實(shí)現(xiàn)樣本數(shù)據(jù)平衡，并引入適應(yīng)度函數(shù)保證基分類器的差異性，最終提高不平衡數(shù)據(jù)的分類精度。文獻(xiàn)[15]提出一種新的不平衡數(shù)據(jù)學(xué)習(xí)算法PCBoost，該算法用數(shù)據(jù)合成方法添加合成的少數(shù)類樣本，以平衡訓(xùn)練樣本。文獻(xiàn)[16]提出一種處理不平衡數(shù)據(jù)的欠采樣方法，用以解決因樣本過于集中導(dǎo)致的過擬合問題。文獻(xiàn)[17]提出一種過采樣算法，將過采樣與欠采樣進(jìn)行融合，利用過采樣的優(yōu)點(diǎn)增加少數(shù)類樣本數(shù)量，使分類器能夠更好地提高少數(shù)類的分類性能。文獻(xiàn)[18]提出多類類別不平衡學(xué)習(xí)算法EasyEssemble M，該算法采用多數(shù)類樣本多次隨機(jī)欠采樣方法，學(xué)習(xí)多個(gè)子分類器提高分類效果。雖然以上通過改變數(shù)據(jù)分布達(dá)到數(shù)據(jù)平衡的算法能夠在一定程度上解決多類類別不平衡問題，但是存在一定的局限性：簡單機(jī)械地采樣將破壞原始數(shù)據(jù)的分布特點(diǎn)，移除過多的多類樣本將會(huì)導(dǎo)致信息丟失[19]。

現(xiàn)有不平衡數(shù)據(jù)處理方法的另一種思路是改進(jìn)已有分類算法。如文獻(xiàn)[20]在AdaBoost算法基礎(chǔ)上使用基于級(jí)聯(lián)模型的分類器，以逐步縮小多類別，使數(shù)據(jù)集趨于平衡，通過迭代訓(xùn)練得到一系列分類器并以集成方式對(duì)預(yù)測樣本進(jìn)行分類。文獻(xiàn)[21，22]針對(duì)現(xiàn)有AdaBoost系列算法未考慮類的先驗(yàn)分布問題，改進(jìn)并提出了不平衡分類問題連續(xù)AdaBoost算法。文獻(xiàn)[23]在SVM分類算法基礎(chǔ)上，針對(duì)不平衡數(shù)據(jù)導(dǎo)致SVM的分類超平面偏移問題，提出了一種改進(jìn) SVM-KNN 算法。這些改進(jìn)方法能夠在某種程度上提高分類精度，但泛化性不夠強(qiáng)大，并且算法參數(shù)和閾值的設(shè)定或選取存在一定主觀性，稍有不當(dāng)將破壞原始數(shù)據(jù)的分布特點(diǎn)且無法充分利用多數(shù)類樣本潛在信息[24]。

綜上所述，雖然以上兩種思路及方法能夠在特定環(huán)境下一定程度上解決數(shù)據(jù)不平衡問題，但是數(shù)據(jù)平衡按比例機(jī)械地抽樣將破壞原始數(shù)據(jù)的分布特點(diǎn)，而對(duì)多數(shù)類樣本進(jìn)行簡單抽樣則可能移除潛在有用分類信息，導(dǎo)致分類效率低、分類精度差等問題。

針對(duì)上述問題，本文提出一種不平衡數(shù)據(jù)集成分類方法（Integrated Classification Method for Imbalanced Data，簡稱ICMID），首先多數(shù)類樣本中依照多數(shù)類樣本的權(quán)重以及少數(shù)類樣本得到的綜合權(quán)重進(jìn)行不放回隨機(jī)抽取，并與少數(shù)類樣本組成訓(xùn)練樣本集；再隨機(jī)選取若干項(xiàng)特征構(gòu)造特征子集，將特征子集對(duì)訓(xùn)練樣本子集進(jìn)行投影，得到的對(duì)應(yīng)特征子集樣本作為算法訓(xùn)練基分類器的訓(xùn)練樣本，經(jīng)過多次迭代產(chǎn)生多個(gè)弱分類器，通過弱分類器權(quán)重投票得出最終輸出結(jié)果。因此，在保證基分類器差異性的前提下，提高了少數(shù)類的分類準(zhǔn)確率，還挖掘了多數(shù)類樣本中的潛在有用信息。

1 問題描述與建模

2 不平衡數(shù)據(jù)集成分類方法

為了保持原始數(shù)據(jù)的分布特點(diǎn)，更好地利用潛在有用的分類信息，保證集成學(xué)習(xí)中各分類器之間的差異性，本文提出基于綜合權(quán)重的不平衡數(shù)據(jù)集成分類方法。主要包括3個(gè)階段：①去除多數(shù)類中的噪聲樣本；②通過綜合樣本權(quán)重抽取多數(shù)類樣本生成合成樣本集；③訓(xùn)練不同的基分類器進(jìn)行集成分類。具體流程如圖1。

2.1 不平衡數(shù)據(jù)處理

為了保持原有樣本的分布特點(diǎn)，同時(shí)又能更好地利用多數(shù)類樣本中潛在有用的信息，在不平衡數(shù)據(jù)處理階段，首先循環(huán)隨機(jī)選取n個(gè)特征子集，然后按照少數(shù)類樣本的數(shù)量和多數(shù)類樣本中每個(gè)類別樣本數(shù)量占比計(jì)算綜合權(quán)重，并依據(jù)綜合權(quán)重抽取每一類別的樣本數(shù)量，再將少數(shù)類樣本與抽取的樣本組合，使少數(shù)類樣本在訓(xùn)練樣本中所占比例升高，重復(fù)抽取M次，最后獲得處理過的訓(xùn)練樣本子集和特征子集。具體過程見算法1。

為了增強(qiáng)分類器之間的差異性以及提高分類準(zhǔn)確率，做法如下：第一，根據(jù)特征子集Fi對(duì)訓(xùn)練樣本子集D′j進(jìn)行投影，得到相對(duì)應(yīng)特征子集的樣本Yij，將該樣本作為訓(xùn)練基分類器的樣本；第二，初始化樣本權(quán)重；第三，通過T次迭代訓(xùn)練得到多個(gè)弱分類器，在每次迭代中計(jì)算每個(gè)基分類器的錯(cuò)誤率，判斷分類錯(cuò)誤率是否超過給定閾值，當(dāng)超過給定閾值時(shí)，說明該部分樣本分類困難，則退出迭代過程進(jìn)行下一輪，當(dāng)錯(cuò)誤率小于給定閾值時(shí)，依據(jù)錯(cuò)誤率更新權(quán)重；第四，依據(jù)所有基分類器錯(cuò)誤率以及分類正確的樣本個(gè)數(shù)綜合計(jì)算投票權(quán)重，得出最終輸出結(jié)果。具體過程見算法2。

3 實(shí)驗(yàn)與結(jié)果

3.1 實(shí)驗(yàn)數(shù)據(jù)

為評(píng)價(jià)本文方法對(duì)不平衡數(shù)據(jù)集分類問題的有效性，選擇6個(gè)少數(shù)類和多數(shù)類樣本比例不平衡的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集來源于 UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫，見表1。其中數(shù)據(jù)集樣本數(shù)用#Ex表示，#F代表特征數(shù)，#Minority代表少數(shù)類樣本數(shù)，#R代表少數(shù)類樣本占數(shù)據(jù)集的比重。采用決策樹C4.5算法以及AdaBoost.M1算法進(jìn)行對(duì)照，Adaboost.M1迭代時(shí)用 C4.5 作為基分類器，迭代 20次，此外還對(duì)數(shù)據(jù)采用十交叉驗(yàn)證。其中，C4.5決策樹算法直接對(duì)不平衡數(shù)據(jù)集進(jìn)行分類，基分類器算法使用C4.5算法，利用weka平臺(tái)中J48分類器實(shí)現(xiàn)。

3.2 評(píng)估指標(biāo)

采用查全率、查準(zhǔn)率和F-measure作為評(píng)價(jià)分類器性能的指標(biāo)，其在機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域應(yīng)用廣泛，能被廣大學(xué)者接受。傳統(tǒng)的二分類評(píng)價(jià)指標(biāo)基于混淆矩陣，在不平衡數(shù)據(jù)集中正類和反類分別代表少數(shù)類和多數(shù)類。TP和 TN分別表示正確分類的正類和反類樣本個(gè)數(shù)；FP表示誤分為正類的樣本個(gè)數(shù)；FN表示誤分為負(fù)類的樣本個(gè)數(shù)，見表2。

3.3 實(shí)驗(yàn)結(jié)果分析

在不平衡數(shù)據(jù)集中，多數(shù)類樣本個(gè)數(shù)遠(yuǎn)遠(yuǎn)多于少數(shù)類，傳統(tǒng)分類算法預(yù)測會(huì)傾向于多數(shù)類，如把所有樣本分為多數(shù)類，依然會(huì)獲得很高的分類精度，但是卻不能識(shí)別一個(gè)少數(shù)類。因此在處理不平衡數(shù)據(jù)時(shí)，提高少數(shù)類樣本在訓(xùn)練樣本中所占比重，能夠有效提高少數(shù)類樣本的分類性能。從表3及圖2可以看出，不平衡數(shù)據(jù)經(jīng)過處理后，每個(gè)數(shù)據(jù)集訓(xùn)練樣本中少數(shù)類樣本的比例明顯提高。

從表4和表5可以看出，AdaBoos.M1算法在Segment、Vehicle數(shù)據(jù)集上的查準(zhǔn)率偏低，而C4.5算法在Segment、Sick數(shù)據(jù)集上有較高的查準(zhǔn)率和查全率。同AdaBoost.M1和C4.5算法相比較，本文算法在Balance-scale 、Satimage以及Yeast 數(shù)據(jù)集上的查準(zhǔn)率具有顯著優(yōu)勢。在這幾個(gè)數(shù)據(jù)集上，本文算法顯著優(yōu)于AdaBoost.M1算法，在Segment 、Sick數(shù)據(jù)集上與C4.5算法水平相當(dāng)。

表6是幾種不同方法在不平衡數(shù)據(jù)分類性能中評(píng)估指標(biāo)F-measure的分類結(jié)果比較。只有當(dāng)查全率和查準(zhǔn)率都較大時(shí)，F(xiàn)-measure才會(huì)相應(yīng)地較大。因此，F(xiàn)-measure可以合理地評(píng)價(jià)分類器對(duì)于少數(shù)類的分類性能。本文提出采用基于綜合權(quán)重采樣和集成學(xué)習(xí)相結(jié)合的方法處理不平衡數(shù)據(jù)的分類問題，相較于其它兩種方法，分類性能得到大幅度提升。比如在數(shù)據(jù)集Satimage、Sick以及Yeast中比其它兩種算法提高了10%以上。

文獻(xiàn)[15]提出處理不平衡數(shù)據(jù)的PCBoost算法在每次迭代初始，利用數(shù)據(jù)合成方法添加合成的少數(shù)類樣本達(dá)到平衡。其在數(shù)據(jù)集Satimage、Segment以及Vehicle中，與本文算法在F-measure方面的比較見圖3。從圖3可以看出，本文算法在數(shù)據(jù)集Satimage中明顯高于PCBoost算法，但是在數(shù)據(jù)集Vehicle明顯低于PCBoost算法，而在數(shù)據(jù)集Segment中兩種方法水平相當(dāng)。對(duì)于每一個(gè)數(shù)據(jù)集，PCBoost算法在實(shí)驗(yàn)中選取不同的迭代次數(shù)以獲得最佳預(yù)測性能的分類器，使其在某些數(shù)據(jù)集上比本文算法取得更為明顯的效果。

5 結(jié)語

為了保持原始數(shù)據(jù)的分布特點(diǎn)，更好地利用潛在有用的分類信息，保證集成學(xué)習(xí)中各分類器之間的差異性，本文采用基于綜合權(quán)重采樣與集成學(xué)習(xí)相結(jié)合的方法處理不平衡數(shù)據(jù)分類問題。通過UCI數(shù)據(jù)集實(shí)驗(yàn)，以查全率、查準(zhǔn)率和F-measure為度量對(duì)算法進(jìn)行評(píng)價(jià)，與決策樹算法、AdaBoost.M1算法以及PCBoost算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明本文方法不僅能夠提高少數(shù)類樣本的分類性能，而且能夠有效提高整體分類精度。

在不平衡數(shù)據(jù)處理階段，本文隨機(jī)選擇特征構(gòu)成特征子集，并沒有考慮到每個(gè)特征對(duì)類的貢獻(xiàn)程度以及特征與特征之間對(duì)類的貢獻(xiàn)程度；另外還未考慮分類效率問題。因此，將來需考慮對(duì)特征的選擇以及提高分類效率，以進(jìn)一步提高該方法的泛化性能。

參考文獻(xiàn)：

[1] KIM H，HOWLAND P，PARK H.Dimension reduction in text classification with support vector machine[J].Journal of Machine Learning Research，2005，6（1）：37-53.

[2] 鄒權(quán)，郭茂祖，劉揚(yáng)，等.類別不平衡的分類方法及在生物信息學(xué)中的應(yīng)用[J].計(jì)算機(jī)研究與發(fā)展，2010，47（8）：1407-1414.

[3] 陸悠，李偉，羅軍舟，等.一種基于選擇性協(xié)同學(xué)習(xí)的網(wǎng)絡(luò)用戶異常行為檢測方法[J].計(jì)算機(jī)學(xué)報(bào)，2014，37（1）：28-40.

[4] CHAWLA N V，JAPKOWICA N，KOTCZ A.Editorial：special issue on learning from imbalanced data sets[J].ACM SIGKDD Explorations Newslettter，2004，6（1）：1-6.

[5] HE H B，EDWARDO A G.Learning from imbalanced data[J].IEEE Transactions on Knowledge and Data Engineering，2009，21（9）：1263-1284.

[6] 陶新民，郝思媛，張冬雪，等.不均衡數(shù)據(jù)分類算法的綜述[J].重慶郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，25（1）：102-110.

[7] CEDER A，HASSOLD S，DANO R.Approaching even-load and even-head way transit timetables using different bus sizes[J].Public Transport，2013，5（3）：193-217.

[8] 林智勇，郝志峰，楊曉偉.不平衡數(shù)據(jù)分類的研究現(xiàn)狀[J].計(jì)算機(jī)應(yīng)用研究，2008，25（2）：332-336.

[9] 錢洪波，賀廣南.非平衡類數(shù)據(jù)分類概述[J].計(jì)算機(jī)工程與科學(xué)，2010，32（5）：85-88.

[10] 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.

[11] 李克文，楊磊，劉文英，等.基于RSBoost算法的不平衡數(shù)據(jù)分類方法[J].計(jì)算機(jī)科學(xué)，2015，42（9）：249-252.

[12] CHEN B，SU Y D，HUANG S.Classification of imbalance data based on KM-SMOTE algorithm and random forest[J].Computer Technology And Development，2015，9（25）：17-21.

[13] SEIFFERTC，KHOSHOFTAARTM，VAN H，et al.RUBoost：a hybrida approach total levitating classing balance[J].IEEE Tran on Systems，Man and Cybernetics，PartA：Systems and Humans，2010，40（1）：185-197.

[14] GALAR M，F(xiàn)ERNNDEZ A，BARRENCHEA E，et al.EUSBoost：enchancing ensembles for highly imbalanced data-sets by evolutionary under sampling[J].Pattern Recognition，2013，46（12）：3460-3471.

[15] 李雄飛，李軍，董元方，等.一種新的不平衡數(shù)據(jù)學(xué)習(xí)算法PCBoost[J].計(jì)算機(jī)學(xué)報(bào)，2012，35（2）：2202-2209.

[16] LIN S Y，LI C H，JIANG Y，et al.Under-sampling method research in class-imbalanced data[J].Journal of Computer Research and Development，2011，48（2）：47-53.

[17] HAN H，WANG W Y，MAO B H.Over-sampling algorithm based on AdaBoost in unbalanced data set[J].Computer Engineering，2007，10（33）：207-209.

[18] 李倩倩，劉胥影.多類類別不平衡學(xué)習(xí)算法：EasyEnsemble.M [J].模式識(shí)別與人工智能，2014（2）：187-192.

[19] 胡小生，溫菊屏，鐘勇.動(dòng)態(tài)平衡采樣的不平衡數(shù)據(jù)集成分類方法[J].智能系統(tǒng)學(xué)報(bào)，2016，11（2）：257-263.

[20] 劉胥影，吳建鑫，周志華.一種基于級(jí)聯(lián)模型的類別不平衡數(shù)據(jù)分類方法[J].南京大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，42（2）：148-155.

[21] FU Z L.Real AdaBoost algorithm for multiclass and imbalanced classification problems[J].Journal of Computer Research and Development，2011，48（12）：2326-2333.

[22] 凌曉峰，SHENG V S.代價(jià)敏感分類器的比較研究[J].計(jì)算機(jī)學(xué)報(bào)，2007，30（8）：1203-1212.

[23] WANG C X，ZHANG T，MA C.Improved SVM-KNN algorithm for imbalanced datasets classification[J].Computer Engineering and Applications，2016，52（4）：51-55.

[24] 馬彪，周瑜，賀建軍.面向大規(guī)模類不平衡數(shù)據(jù)的變分高斯過程分類算法[J].大連理工大學(xué)學(xué)報(bào)，2016，56（3）：279-284.

（責(zé)任編輯：何 麗）