王俊紅，閆家榮

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

0 引言

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

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

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

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

1 相關(guān)工作

1.1 AdaBoost算法

AdaBoost作為Boosting技術(shù)的代表算法，近年來被相關(guān)學(xué)者廣泛研究和使用。該算法主要通過更新樣本權(quán)值，使基分類器在每次迭代中更加注重分錯的樣本，對這一部分樣本進行著重訓(xùn)練，最后將每次迭代訓(xùn)練的基分類器加權(quán)組合。假如數(shù)據(jù)集樣本數(shù)量為N，算法在第一輪迭代時賦予所有訓(xùn)練樣本相同的權(quán)重1/N；然后學(xué)習(xí)基分類器。對于訓(xùn)練集中的樣本數(shù)據(jù)，假如樣本被此次學(xué)習(xí)的基分類器分類錯誤，這個樣本權(quán)值將會增加；反之，被基分類器分類正確的樣本權(quán)值會被降低。因此在下次迭代訓(xùn)練的基分類器會更加著重學(xué)習(xí)上次被分錯的數(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）有著可解釋性強、運行速度快等優(yōu)點，集成學(xué)習(xí)中經(jīng)常使用具有較小深度的決策樹作為基本分類器。本文中構(gòu)建的集成模型使用CART（Classification And Regression Tree）算法生成基本分類器。

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

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

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

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

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

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

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

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

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

綜上所述，本文首先通過欠采樣刪除了大量對分類器貢獻不大的多數(shù)類樣本，降低了訓(xùn)練基分類器的時間復(fù)雜度，繼而在樣本更新時通過引入代價調(diào)整函數(shù)使得誤分代價高的樣本在每次迭代中權(quán)重增加更快，使得下次迭代時基分類器更加注重錯分的少數(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 實驗結(jié)果與分析

3.1 評價標準

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

表1 混淆矩陣Tab.1 Confusion matrix

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

2）查準率（Precision）表示被分為正例的示例中實際為正例的比例，計算公式如式（5）：

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

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

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

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

本實驗中采用準確率、F1-measure值、G-mean值作為衡量算法性能的評價指標。

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

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

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

3.3 實驗設(shè)計與結(jié)果分析

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

實驗分析了4 種算法的準確率、F1-measure值、G-mean值。表3 列舉了本文算法和其他3 種對比算法在各數(shù)據(jù)集下的評價指標值，其中加粗的數(shù)值為最高的評價指標值。

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

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

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

但本文算法在和使用隨機欠采樣的RUSBoost 算法比較，在letter_2 數(shù)據(jù)集上F1-measure值有顯著的提高，這是因為本文算法在每次迭代中欠采樣后得到的是權(quán)重高的樣本，而這些樣本對于基分類器的影響更大。

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

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

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

4 結(jié)語

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