基于欠采樣和代價(jià)敏感的不平衡數(shù)據(jù)分類算法

王俊紅，閆家榮

（1.山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，太原 030006；2.計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室（山西大學(xué)），太原 030006）

0 引言

分類是數(shù)據(jù)挖掘領(lǐng)域中一個(gè)重要的分支，普通的分類模型通常假設(shè)數(shù)據(jù)集中各類別的樣本數(shù)量差距很小且對(duì)于每個(gè)類別的誤分代價(jià)相等，而使用不平衡數(shù)據(jù)集訓(xùn)練傳統(tǒng)的分類器會(huì)導(dǎo)致模型對(duì)于少數(shù)類的預(yù)測(cè)精度很低，因此不平衡數(shù)據(jù)學(xué)習(xí)一直是機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)［1］。數(shù)據(jù)的類別不平衡主要指數(shù)據(jù)集中某類樣本數(shù)量與其他類別樣本數(shù)量有很大差距，而擁有較多樣本數(shù)據(jù)量的類被稱為多數(shù)類，擁有較少樣本數(shù)據(jù)量的類則被稱為少數(shù)類。在互聯(lián)網(wǎng)應(yīng)用方面存在著大量不平衡數(shù)據(jù)分類問題，如醫(yī)療檢測(cè)［2］、欺詐識(shí)別［3］、入侵檢測(cè)［4］、工業(yè)故障檢測(cè)［5］等。

對(duì)于目前不平衡數(shù)據(jù)分類問題，通常的解決方法主要分為數(shù)據(jù)預(yù)處理層面和分類算法層面［6］。數(shù)據(jù)預(yù)處理層面的方法主要思想是通過重采樣技術(shù)使數(shù)據(jù)集中各個(gè)類別樣本數(shù)量達(dá)到相對(duì)的平衡，主要有對(duì)多數(shù)類的欠采樣［7-8］，對(duì)少數(shù)類的過采樣［9-10］，以及結(jié)合兩種采樣方法的混合采樣［11］。而在算法層面，相關(guān)研究人員通過改進(jìn)算法以增加分類器對(duì)少數(shù)類的重視程度，比較有代表性的算法是代價(jià)敏感［12］、單類學(xué)習(xí)［13-14］和集成學(xué)習(xí)［15］等。本文重點(diǎn)關(guān)注基于集成學(xué)習(xí)的不平衡數(shù)據(jù)分類算法的研究進(jìn)展。

集成學(xué)習(xí)主要思想是將學(xué)習(xí)得到的多個(gè)子分類模型通過一定方式組合，從而得到一個(gè)泛化能力更好的強(qiáng)分類器。其中Bagging和Boosting是機(jī)器學(xué)習(xí)中應(yīng)用最廣泛的集成學(xué)習(xí)技術(shù)，Boosting 雖然不是為處理不平衡數(shù)據(jù)設(shè)計(jì)的，但卻可以有效提高分類器對(duì)于不平衡數(shù)據(jù)的分類性能。Freund等［16］提出的自適應(yīng)增強(qiáng)（Adaptive Boosting，AdaBoost）算法是最常用的Boosting 算法。目前基于集成學(xué)習(xí)方法的不平衡數(shù)據(jù)分類算法中主要分為將數(shù)據(jù)重采樣技術(shù)與集成算法結(jié)合和將代價(jià)敏感思想與集成算法相結(jié)合。將數(shù)據(jù)預(yù)處理與集成方法結(jié)合主要是在訓(xùn)練基分類器之前對(duì)數(shù)據(jù)樣本使用重采樣技術(shù)。Chawla等［17］提出了一種將過采樣技術(shù)與集成學(xué)習(xí)結(jié)合的算法SOMTEBoost（Synthetic Minority Over-sampling TEchnique Boosting），該算法基于AdaBoost.M2［18］算法，通過每次迭代中使用合成少數(shù)類過采樣技術(shù)（Synthetic Minority Over-sampling TEchnique，SMOTE）對(duì)少數(shù)類過采樣，從而獲得較為平衡的數(shù)據(jù)。算法通過將SMOTE 算法和AdaBoost算法的結(jié)合，有效改善了分類器的性能，其結(jié)果優(yōu)于單獨(dú)使用SMOTE 和AdaBoost算法。但SMOTEBoost 算法在訓(xùn)練過程中由于過采樣生成了更多的數(shù)據(jù)，當(dāng)樣本容量很大時(shí)，時(shí)間復(fù)雜度會(huì)增加。因此Seiffert 等［19］在2010 年提出了RUSBoost（Random Under-Sampling Boosting）算法，它與SOMTEBoost 算法相似，該算法在迭代中使用了隨機(jī)欠采樣技術(shù)，使用更少的數(shù)據(jù)集訓(xùn)練弱分類器，在提升不平衡數(shù)據(jù)集分類性能的同時(shí)降低了訓(xùn)練的時(shí)間復(fù)雜度，在處理樣本容量較大的分類問題中更具優(yōu)勢(shì)。Rayhan 等［20］提出了CUSBoost（Cluster-based Under-Sampling with Boosting）算法，該算法首先使用K均值聚類（K-Means Clustering，KMC）算法對(duì)多數(shù)類進(jìn)行聚類，然后在每次迭代中對(duì)每個(gè)聚類子簇中的數(shù)據(jù)隨機(jī)下采樣，得到平衡的數(shù)據(jù)集。該算法雖然在下采樣之后可以獲得更具代表性的多數(shù)類樣本，但對(duì)多數(shù)類進(jìn)行聚類時(shí)，會(huì)消耗大量的時(shí)間。Feng 等［21］通過將間隔理論與集成技術(shù)結(jié)合，提出了基于間隔理論的不平衡數(shù)據(jù)分類算法，算法在采樣時(shí)使用信息量更大的低間隔樣本，從而獲得更高的預(yù)測(cè)精度。陳圣靈等［22］通過將SMOTE算法和集成學(xué)習(xí)思想相結(jié)合，提出了一種基于更新樣本權(quán)重的不平衡數(shù)據(jù)學(xué)習(xí)算法，算法通過重采樣從而間接地更新樣本權(quán)重，有效提高算法模型少數(shù)類識(shí)別能力。將代價(jià)敏感與集成方法結(jié)合最具代表性的方法是Fan 等［23］提出的代價(jià)敏感集成（Cost-sensitive AdaBoosting，AdaCost）算法，算法主要通過修改樣本錯(cuò)分代價(jià)，使得AdaBoost 采用不同的策略更新不同錯(cuò)分代價(jià)的樣本權(quán)重。

基于此，本文從數(shù)據(jù)預(yù)處理層面出發(fā)，并將代價(jià)敏感思想引入AdaBoost 算法的權(quán)重更新公式，提出一種基于欠采樣和代價(jià)敏感的不平衡數(shù)據(jù)分類算法——USCBoost（UnderSamples and Cost-sensitive Boosting），算法旨在對(duì)多數(shù)類樣本進(jìn)行欠采樣，并將代價(jià)矩陣引入到權(quán)重更新公式中，使得錯(cuò)分少數(shù)類的樣本權(quán)重增加更快。使用UCI庫中的數(shù)據(jù)集對(duì)本文算法進(jìn)行實(shí)驗(yàn)分析，結(jié)果表明USCBoost 算法與其他對(duì)比算法相比，在F1-measure值和G-mean值上有了顯著提高，該算法處理不平衡數(shù)據(jù)分類具有一定可行性。

1 相關(guān)工作

1.1 AdaBoost算法

AdaBoost作為Boosting技術(shù)的代表算法，近年來被相關(guān)學(xué)者廣泛研究和使用。該算法主要通過更新樣本權(quán)值，使基分類器在每次迭代中更加注重分錯(cuò)的樣本，對(duì)這一部分樣本進(jìn)行著重訓(xùn)練，最后將每次迭代訓(xùn)練的基分類器加權(quán)組合。假如數(shù)據(jù)集樣本數(shù)量為N，算法在第一輪迭代時(shí)賦予所有訓(xùn)練樣本相同的權(quán)重1/N；然后學(xué)習(xí)基分類器。對(duì)于訓(xùn)練集中的樣本數(shù)據(jù)，假如樣本被此次學(xué)習(xí)的基分類器分類錯(cuò)誤，這個(gè)樣本權(quán)值將會(huì)增加；反之，被基分類器分類正確的樣本權(quán)值會(huì)被降低。因此在下次迭代訓(xùn)練的基分類器會(huì)更加著重學(xué)習(xí)上次被分錯(cuò)的數(shù)據(jù)。最后將每次迭代訓(xùn)練的基分類器根據(jù)權(quán)值線性相加。

AdaBoost算法執(zhí)行步驟如下。

算法1 AdaBoost算法。

輸入：訓(xùn)練數(shù)據(jù)集S={(x1，y1)，(x2，y2)，…，(xi，yi)|i=1，2，…，N，yi∈{1，-1}}，T為迭代次數(shù)，g為基分類器；

1.2 決策樹生成算法

決策樹（Decision Tree）有著可解釋性強(qiáng)、運(yùn)行速度快等優(yōu)點(diǎn)，集成學(xué)習(xí)中經(jīng)常使用具有較小深度的決策樹作為基本分類器。本文中構(gòu)建的集成模型使用CART（Classification And Regression Tree）算法生成基本分類器。

CART 是一種常見的決策樹生成算法，該算法采用Gini系數(shù)作為評(píng)價(jià)最優(yōu)劃分特征的指標(biāo)。假如樣本集合Gini值越小，數(shù)據(jù)集中樣本屬于同一類別的概率越高。

對(duì)于樣本集合D，Gini系數(shù)計(jì)算公式如下：

其中：K為樣本集合D中類別數(shù)量，Ck為第k類的樣本數(shù)量。

特征A上樣本集合D的基尼系數(shù)計(jì)算公式如下：

其中：D1和D2為使用特征值A(chǔ)上的某一特征值將數(shù)據(jù)集劃分后形成的兩個(gè)子集。

2 基于欠采樣和代價(jià)敏感的不平衡數(shù)據(jù)分類算法

從AdaBoost 算法的相關(guān)研究可知，由于多數(shù)類在不平衡數(shù)據(jù)集中占有著很大的比例，使得傳統(tǒng)AdaBoost 算法在迭代過程中更加著重訓(xùn)練占比更大的多數(shù)類數(shù)據(jù)，而忽略了不平衡數(shù)據(jù)集中的少數(shù)類數(shù)據(jù)，導(dǎo)致最終算法模型的分類決策面會(huì)偏向少數(shù)類。而在集成算法每次迭代中，被分類正確的多數(shù)類樣本權(quán)值會(huì)降低，對(duì)于下次弱分類器的性能影響變小，因此可以對(duì)于這部分權(quán)值低的多數(shù)類樣本欠采樣；但是由于欠采樣之后的多數(shù)類樣本中仍然存在大量權(quán)重高的多數(shù)類樣本，為了使少數(shù)類樣本在訓(xùn)練中進(jìn)一步得到重視，將代價(jià)敏感的思想引入樣本權(quán)重更新公式，賦予少數(shù)類更高的樣本權(quán)重，使得分錯(cuò)的少數(shù)類樣本權(quán)重增加更快。

本文算法在每次迭代訓(xùn)練弱分類器之前根據(jù)采樣率選取權(quán)重較大的多數(shù)類樣本并和所有少數(shù)類樣本組成臨時(shí)訓(xùn)練集；在樣本權(quán)重調(diào)整階段，本文采用了AdaCost 算法中樣本權(quán)重更新的策略，將代價(jià)調(diào)整函數(shù)β引入到權(quán)重更新公式中。β函數(shù)的計(jì)算公式如下：

其中：β+為模型預(yù)測(cè)正確時(shí)的β函數(shù)，β-為模型預(yù)測(cè)錯(cuò)誤時(shí)的β函數(shù)，c為樣本的錯(cuò)分代價(jià)。

綜上所述，本文首先通過欠采樣刪除了大量對(duì)分類器貢獻(xiàn)不大的多數(shù)類樣本，降低了訓(xùn)練基分類器的時(shí)間復(fù)雜度，繼而在樣本更新時(shí)通過引入代價(jià)調(diào)整函數(shù)使得誤分代價(jià)高的樣本在每次迭代中權(quán)重增加更快，使得下次迭代時(shí)基分類器更加注重錯(cuò)分的少數(shù)類樣本。

本文集成算法步驟如下。

算法2 USCBoost算法。

輸入：訓(xùn)練數(shù)據(jù)集：S={(x1，y1)，(x2，y2)，…，(xi，yi)|i=1，2，…，N，yi∈{1，-1}}，T為迭代次數(shù)，g為基分類器；

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

3.1 評(píng)價(jià)標(biāo)準(zhǔn)

在數(shù)據(jù)不平衡的分類任務(wù)中，通常使用準(zhǔn)確率、召回率、F1-measure值等當(dāng)作模型的性能度量指標(biāo)。二分類問題混淆矩陣如表1 所示。其中：TP（True Positive）為正例樣本分類正確時(shí)的情況；FP（False Positive）為反例樣本被分類錯(cuò)誤的情況；FN（False Negative）為正例樣本被分類錯(cuò)誤的情況；TN（True Negative）為反例樣本分類正確的情況。

表1 混淆矩陣Tab.1 Confusion matrix

1）準(zhǔn)確率（Accuracy）表示分對(duì)的樣本數(shù)除以所有的樣本數(shù)，計(jì)算公式如式（4）：

2）查準(zhǔn)率（Precision）表示被分為正例的示例中實(shí)際為正例的比例，計(jì)算公式如式（5）：

3）召回率（Recall）為分類正確的正例樣本與所有正例樣本的比值，用來度量算法識(shí)別正例樣本的能力。計(jì)算公式如式（6）：

4）特異度為分類正確的反例樣本與所有反例樣本的比值，用來度量算法識(shí)別反例樣本的能力。計(jì)算公式如式（7）：

5）F1-measure表示Precision和Recall加權(quán)調(diào)和平均值，計(jì)算公式如式（8）：

6）G-mean值表示召回率和特異度的幾何平均值，如式（9）：

本實(shí)驗(yàn)中采用準(zhǔn)確率、F1-measure值、G-mean值作為衡量算法性能的評(píng)價(jià)指標(biāo)。

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

為了衡量本文提出的USCBoost 算法的性能，使用UCI 中標(biāo)準(zhǔn)數(shù)據(jù)庫10 組數(shù)據(jù)集訓(xùn)練分類器并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。實(shí)驗(yàn)數(shù)據(jù)集的不平衡度（Imbalance Ratio，IR）從1.8 到24。其中有的數(shù)據(jù)中為多分類數(shù)據(jù)集，本實(shí)驗(yàn)將這些數(shù)據(jù)集中的某些類別合并成二分類數(shù)據(jù)集。例如在Ecoli數(shù)據(jù)集中，樣本分為8 類，Ecoli_5 表示將數(shù)據(jù)集中類別為5 的樣本作為少數(shù)類，并將剩余其他類別的樣本合成多數(shù)類。實(shí)驗(yàn)數(shù)據(jù)集信息如表2。

表2 實(shí)驗(yàn)數(shù)據(jù)集描述Tab.2 Experimental datasets description

3.3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

本實(shí)驗(yàn)中所有算法采用五折交叉驗(yàn)證方法，實(shí)驗(yàn)中對(duì)比算法為AdaBoost 算法、AdaCost 算法和RUSBoost 算法。其中RUSBoost 算法采用C4.5 生成基分類器，其余集成算法采用CART 生成基分類器，所有決策樹的深度為5，算法的基分類器數(shù)都為10。

實(shí)驗(yàn)分析了4 種算法的準(zhǔn)確率、F1-measure值、G-mean值。表3 列舉了本文算法和其他3 種對(duì)比算法在各數(shù)據(jù)集下的評(píng)價(jià)指標(biāo)值，其中加粗的數(shù)值為最高的評(píng)價(jià)指標(biāo)值。

從實(shí)驗(yàn)對(duì)比結(jié)果可以看出，相比傳統(tǒng)的AdaBoost算法，本文提出的算法在大部分?jǐn)?shù)據(jù)集上準(zhǔn)確率提高并不明顯，而且在有的數(shù)據(jù)集上會(huì)降低。說明算法在提高少數(shù)類分類準(zhǔn)確率的同時(shí)可能會(huì)降低多數(shù)類的準(zhǔn)確率。

F1-measure值和G-mean值更能夠衡量不平衡數(shù)據(jù)分類算法的性能。由表3 可以看出USCBoost 算法與其他算法相比，在大部分?jǐn)?shù)據(jù)集上都具有明顯的優(yōu)勢(shì)，在vowel_3 和anneal_1_2數(shù)據(jù)集上本文算法的F1-measure值略小于AdaBoost算法，這是因?yàn)闃颖镜臏p少可能會(huì)導(dǎo)致精度的損失；但在Letter_2數(shù)據(jù)集中，本文算法的F1-measure值與AdaBoost 算法差距較大，這是由于在高度不平衡的數(shù)據(jù)中，少數(shù)類樣本只占到總樣本數(shù)的很少一部分，當(dāng)對(duì)多數(shù)類樣本欠采樣到少數(shù)類樣本的數(shù)量時(shí)，可能會(huì)刪除掉很多潛在的有價(jià)值的多數(shù)類樣本，此時(shí)可以通過適當(dāng)?shù)靥岣叨鄶?shù)類的采樣率或?qū)ι贁?shù)類進(jìn)行過采樣操作，保留有價(jià)值的樣本。

表3 不同分類算法在不平衡數(shù)據(jù)集上的分類準(zhǔn)確率、F1-measure值、G-mean值對(duì)比Tab.3 Classification accuracy，F(xiàn)1-measure and G-mean comparison of different classification algorithms on unbalanced datasets

但本文算法在和使用隨機(jī)欠采樣的RUSBoost 算法比較，在letter_2 數(shù)據(jù)集上F1-measure值有顯著的提高，這是因?yàn)楸疚乃惴ㄔ诿看蔚星凡蓸雍蟮玫降氖菣?quán)重高的樣本，而這些樣本對(duì)于基分類器的影響更大。

為了更直觀地對(duì)比4 種算法，圖1、2 展示了對(duì)比算法和USCBoost 算法在10個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，可以看出本文算法處理不平衡數(shù)據(jù)具有一定優(yōu)勢(shì)。

圖1 4種算法的F1-measure值對(duì)比Fig.1 F1-measure comparison of four algorithms

圖2 4種算法的G-mean值對(duì)比Fig.2 G-mean comparison of four algorithms

4 結(jié)語

本文通過對(duì)不平衡數(shù)據(jù)分類在傳統(tǒng)AdaBoost算法中存在的問題進(jìn)行研究：在集成算法的每次迭代學(xué)習(xí)中根據(jù)樣本權(quán)重對(duì)多數(shù)類欠采樣，挑選出貢獻(xiàn)大的樣本訓(xùn)練基分類器；在權(quán)重調(diào)整階段，通過調(diào)整樣本誤分代價(jià)，使得誤分代價(jià)高的樣本權(quán)重將會(huì)增加更快，從而使少數(shù)類樣本在下次訓(xùn)練中被重視。算法在保證模型不平衡分類性能的同時(shí)，降低了訓(xùn)練分類模型的時(shí)間復(fù)雜度。然而，本文算法繼承了AdaBoost 對(duì)噪聲敏感的缺點(diǎn)，如何在訓(xùn)練過程中保證預(yù)測(cè)精度的同時(shí)降低噪聲數(shù)據(jù)對(duì)模型的影響，將是未來重點(diǎn)研究方向。