4) 如果k≥a，則從數(shù)據(jù)集SP中進行隨機欠采樣，采樣數(shù)目為m-k，將其加入集合S′，在集合SN中應(yīng)用SMOTE進行過采樣，生成k-a個合成樣例，連同SN中的a個樣本，都加入集合S′；
5)輸出集合S′ 。
算法依據(jù)2)中所產(chǎn)生的隨機整數(shù)值大小來決定相應(yīng)的采樣操作，如果產(chǎn)生的隨機數(shù)k小于初始數(shù)據(jù)集的負類樣本數(shù)量，則在負類樣本集進行欠采樣，在正類樣本集進行過采樣，使得最終輸出集合S′的樣本數(shù)量與初始數(shù)據(jù)集數(shù)量一致，反之，則進行相反的采樣。與傳統(tǒng)的采樣方法不同的是，在步驟4中對正類樣本進行欠采樣，對負類樣本進行過采樣，通過隨機函數(shù)產(chǎn)生的隨機數(shù)，使得輸出集合S′在總數(shù)量一定的情況下保持對對各類別樣本的中立性。
2.2訓練樣例權(quán)值更新
在第t次迭代過程中，需要對兩個集合中的樣例權(quán)重進行更新，分別是動態(tài)平衡采樣后的輸出集合S′和子分類器形成之后的初始數(shù)據(jù)集S。
分析動態(tài)平衡采樣算法過程可知，經(jīng)過數(shù)據(jù)采樣之后，新數(shù)據(jù)集S′的樣例總數(shù)與初始數(shù)據(jù)集S一致，均為m，其中包括從數(shù)據(jù)集S抽取的部分樣例，以及部分由SMOTE方法產(chǎn)生的合成樣例。S′中的樣本權(quán)值按照式(1)更新：
(1)
第t次迭代訓練結(jié)束時，AdaBoost分類算法在數(shù)據(jù)集S′進行學習后得到子分類器ht:x→{-1,+1},t=1,2，…,T,ht(x)給出數(shù)據(jù)集S中的樣例x的所屬類別，根據(jù)子分類器的分類情況，更新樣本權(quán)值，增加錯分樣本的權(quán)值，減少正確分類樣本權(quán)值，以便下次迭代時，“錯分”樣本得到更多關(guān)注。
計算子分類器ht(x)的分類錯誤率εt：
(2)
如果εt>0.5，終止此輪迭代。
計算子分類器投票權(quán)重αt：
(3)
更新樣例權(quán)值:
(4)
式中Zt是歸一化常數(shù)。
完整算法如算法2所示。
算法2動態(tài)平衡采樣的不平衡分類算法
2) for t=1,2,…,T
① 調(diào)用動態(tài)平衡采樣算法，獲得數(shù)據(jù)集S′；
② 利用式(1)設(shè)置S′中的樣例權(quán)值；
③ 使用數(shù)據(jù)集S′及其中的樣例權(quán)值，訓練基于AdaBoost算法的子分類器ht(x)；
④ 按照式(2)計算分類器ht(x)的誤差εt，按照式(3)計算ht(x)的投票權(quán)重αt；
⑤ 按照式(4)更新數(shù)據(jù)集S中的樣本權(quán)重；
3實驗結(jié)果與分析
3.1評價度量
傳統(tǒng)分類器采用分類精度指標衡量分類性能，其追求整體分類準確率，忽略了在不平衡數(shù)據(jù)分類過程中需要特別關(guān)注的正類分類準確率。針對不平衡數(shù)據(jù)，許多學者提出了在兩類混淆矩陣基礎(chǔ)上的Fmeasure[10]、Gmean[11]等評價方法。
在混淆矩陣中，TP(true positive)、FN(false negative)、TN(true negative)、FP(false positive)分別代表分類正確的正類樣本、假的負類樣本、正確的負類樣本以及假的正類樣本的數(shù)目?；诨煜仃?，F(xiàn)measure定義如下:
Fmeasure定義說明：較大值表示Recall和Precision都較大，因此，其能夠較好評價正類分類性能。
Gmean其定義如下：
式中
Gmean兼顧了正類準確率和負類準確率，比整體分類準確率更適合于不平衡數(shù)據(jù)分類評價。
本文使用Fmeasure準則來衡量正類的分類性能，使用Gmean準則來衡量數(shù)據(jù)集整體分類性能。
3.2UCI數(shù)據(jù)
為了檢驗本文所提方法的有效性，選擇6組具有實際工程應(yīng)用背景的UCI數(shù)據(jù)[21]進行測試，對于含有多個類別的數(shù)據(jù)，取其中某個類為正類，合并其余類為負類，各數(shù)據(jù)集的基本信息見表1。
表1 UCI數(shù)據(jù)集信息
3.3實驗結(jié)果及分析
實驗中對比算法如下：
1)隨機森林(random forest，RF)算法，RF算法作為一種集成算法，在處理不平衡數(shù)據(jù)時有獨特的優(yōu)勢，能夠在某種程度上減少不均衡數(shù)據(jù)帶來的影響[22]，因此將其直接應(yīng)用在初始不平衡數(shù)據(jù)集進行分類。
2)SMOTEBoost[23]算法，將SMOTE方法與AdaBoost.M2結(jié)合，在每次集成迭代中生成新的合成樣例，使得分類器更加關(guān)注小類樣本。
3)RUSBoost[24]，與SMOTEBoost方法相類似，采用隨機欠采樣從負類樣本中隨機移除樣例，然后應(yīng)用AdaBoost進行多次迭代。
4)文獻[4]提出的集成方法K-means+Bagging，首先在負類樣本上應(yīng)用K-means聚類，提取與正類樣本數(shù)量一致的聚類質(zhì)心，組成平衡訓練集，參與Bagging集成。
上述3種集成方法以及本文算法均使用C4.5決策樹算法作為基分類器算法。
為客觀對比上述不平衡數(shù)據(jù)分類方法，實驗數(shù)據(jù)采用10折交叉驗證方式，重復(fù)10次，以平均值作為最終的分類結(jié)果。
表2和表3分別列出5種方法在6個UCI數(shù)據(jù)集上的正類Fmeasure值和數(shù)據(jù)集整體的Gmean值，最后一行列出每種方法在所有數(shù)據(jù)集上的平均結(jié)果。
表2 5種方法的Fmeasure值比較
表3 5種方法的Gmean值比較
從表2的Fmeasure值可以看出，本文方法除了在sick數(shù)據(jù)集稍微低于SMOTEBoost算法之外，在其他5個數(shù)據(jù)集上均有最佳表現(xiàn)，比較各種算法在6組UCI數(shù)據(jù)上的平均值，本文方法比隨機森林RF算法有14.2%的提升，與基于聚類欠采樣的集成算法相比有27.3%的提升，說明本文所提方法在少數(shù)類分類性能方面有巨大的提升。
比較各個算法的整體分類性能Gmean，從表3可以看出，本文方法也僅在sick數(shù)據(jù)集上稍遜于最優(yōu)算法SMOTEBoost，二者精度相差不超過1‰；在6個數(shù)據(jù)集上的平均分類性能上，本文方法獲得最優(yōu)精度。
結(jié)合表1～3可以看出，隨著數(shù)據(jù)不平衡度的提高，無論是隨機欠采樣還是基于聚類的欠采樣，由于都會對原始數(shù)據(jù)集造成樣本丟失，分類性能都有所下降，特別是在letter和page-blocks數(shù)據(jù)集上，差距比較明顯。與之對比，本文方法在數(shù)據(jù)采樣過程中也需要對某類樣本進行欠采樣，通過多次動態(tài)、隨機性采樣調(diào)和，使得抽樣數(shù)據(jù)能夠較好地保持對原始數(shù)據(jù)的分布；與此同時，對另外一類樣本進行SMOTE過采樣，在沒有增加數(shù)據(jù)規(guī)模條件下，保持對各類樣本的中立性，或者對正類過采樣，或者對負類過采樣。從最終分類結(jié)果來看，本文方法在不降低數(shù)據(jù)集整體Gmean值的基礎(chǔ)上，提高了正類的Fmeasure值，對正類和負類都具有較高的識別率。
本文算法中經(jīng)過動態(tài)平衡采樣后參與基分類器訓練的數(shù)據(jù)集樣本規(guī)模與初始數(shù)據(jù)集一致，即集合數(shù)據(jù)大小比例為100%，為考察參與訓練的不同數(shù)據(jù)規(guī)模比例對算法分類性能的影響，選取本文算法、隨機森林和SMOTEBoost 3種算法，同時選擇以letter數(shù)據(jù)集為例，在20%～100%范圍內(nèi)每次增加20%比例的數(shù)據(jù)，參與集成學習，迭代10次，相關(guān)算法的Fmeasure、Gmean均值如圖1所示。
圖1 不同數(shù)據(jù)規(guī)模對分類性能影響Fig.1 Performance measures of different ensemble size
從圖1可看出，隨著參與訓練數(shù)據(jù)集比例的增大，無論是正類分類性能還是整體分類精度，都有所上升，但是隨著數(shù)據(jù)比例的增大，相應(yīng)的分類性能提升幅度有限。另外，在數(shù)據(jù)比例為20%、40%時，3種算法相對應(yīng)的Fmeasure和Gmean值幾乎是線性提升，這說明過低比例的抽樣數(shù)據(jù)由于損失太大的原始數(shù)據(jù)分布信息，會嚴重影響算法的分類性能。
4結(jié)束語
針對類別不平衡數(shù)據(jù)分類問題，本文提出了一種混合數(shù)據(jù)采樣與Boosting技術(shù)相結(jié)合的集成分類方法。該方法統(tǒng)籌運用欠采樣和過采樣，在保持訓練集數(shù)據(jù)規(guī)模一致條件下，靈活調(diào)整各類別樣本數(shù)量比例，較好地保持原始數(shù)據(jù)分布，然后采用Boosting技術(shù)進行多次迭代學習，獲得更強性能分類器。實驗結(jié)果表明，該方法能夠有效提高正類樣本的分類性能。
由于數(shù)據(jù)集本身的多樣性和復(fù)雜性，諸如類重疊分布、噪聲樣本等均會影響不平衡數(shù)據(jù)性能，如果進行有針對性的數(shù)據(jù)預(yù)處理工作，將會使得動態(tài)平衡采樣的數(shù)據(jù)分布更加合理，對正類的分類性能將會進一步提高。此外，將本文方法應(yīng)用于多類別不平衡數(shù)據(jù)分類，也是今后需要進一步研究的方向。
參考文獻:
[1]CATENI S, COLLA V, VANNUCCI M. A method for resampling imbalanced datasets in binary classification tasks for real-world problems[J]. Neurocomputing, 2014, 135: 32-41.
[2]ZHANG Huaxiang, LI Mingfang. RWO-Sampling: a random walk over-sampling approach to imbalanced data classification[J]. Information fusion, 2014, 20: 99-116.
[3]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.
[4]郭麗娟, 倪子偉, 江弋, 等. 集成降采樣不平衡數(shù)據(jù)分類方法研究[J]. 計算機科學與探索, 2013, 7(7): 630-638.
GUO Lijuan, NI Ziwei, JIANG Yi, et al. Research on imbalanced data classification based on ensemble and under-sampling[J]. Journal of frontiers of computer and technology, 2013, 7(7): 630-638.
[5]李雄飛, 李軍, 董元方, 等. 一種新的不平衡數(shù)據(jù)學習算法PCBoost[J]. 計算機學報, 2012, 35(2): 202-209.
LI Xiongfei, LI Jun, DONG Yuanfang, et al. A new learning algorithm for imbalanced data-PCBoost[J]. Chinese journal of computers, 2012, 35(2): 202-209.
[6]CHEN Xiaolin, SONG Enming, MA Guangzhi. An adaptive cost-sensitive classifier[C]//Proceedings of the 2nd International Conference on Computer and Automation Engineering. Singapore: IEEE, 2010, 1: 699-701.
[7]李倩倩, 劉胥影. 多類類別不平衡學習算法: EasyEnsemble. M[J]. 模式識別與人工智能, 2014, 27(2): 187-192.
LI Qianqian, LIU Xuying. EasyEnsemble. M for multiclass imbalance problem[J]. Pattern recognition and artificial intelligence, 2014, 27(2): 187-192.
[8]韓敏, 朱新榮. 不平衡數(shù)據(jù)分類的混合算法[J]. 控制理論與應(yīng)用, 2011, 28(10): 1485-1489.
HAN Min, ZHU Xinrong. Hybrid algorithm for classification of unbalanced datasets[J]. Control theory & applications, 2012, 28(10): 1485-1489.
[9]WANG Shijin, XI Lifeng. Condition monitoring system design with one-class and imbalanced-data classifier[C]//Proceedings of the 16th International Conference on Industrial Engineering and Engineering Management. Beijing, China: IEEE, 2009: 779-783.
[10]葉志飛, 文益民, 呂寶糧. 不平衡分類問題研究綜述[J]. 智能系統(tǒng)學報, 2009, 4(2): 148-156.
YE Zhifei, WEN Yimin, LV Baoliang. A survey of imbalanced pattern classification problems[J]. CAAI transactions on intelligent systems, 2009, 4(2): 148-156.
[11]翟云, 楊炳儒, 曲武. 不平衡類數(shù)據(jù)挖掘研究綜述[J]. 計算機科學, 2010, 37(10): 27-32.
ZHAI Yun, YANG Bingyu, QU Wu. Survey of mining imbalanced datasets[J]. Computer science, 2010, 37(10): 27-32.
[12]HAN Hui, WANG Wenyuan, MAO Binghuan. Borderline-SMOTE: a new over-sampling method in imbalanced data sets learning[C]//International Conference on Intelligent Computing. Berlin Heidelberg, Germany: Springer, 2005: 878-887.
[13]HE Haibo, BAI Yang, GARCIA E A, et al. ADASYN: adaptive synthetic sampling approach for imbalanced learning[C]//Proceedings of IEEE International Joint Conference on Neural Networks. Hong Kong, China: IEEE, 2008: 1322-1328.
[14]BATISTA G, PRATI R C, MONARD M C. A study of the behavior of several methods for balancing machine learning training data[J]. ACM SIGKDD explorations newsletter, 2004, 6(1): 20-29.
[15]KUBAT M, MATWIN S. Addressing the curse of imbalanced training sets: one-sided selection[C]//Proceedings of the 14th International Conference on Machine Learning. San Francisco, USA: Morgan Kaufmann, 1997: 179-186.
[16]蔣盛益, 苗邦, 余雯. 基于一趟聚類的不平衡數(shù)據(jù)下抽樣算法[J]. 小型微型計算機系統(tǒng), 2012, 33(2): 232-236.
JIANG Shengyi, MIAO Bang, YU Wen. Under-sampling method based on one-pass clustering for imbalanced data distribution[J]. Journal of Chinese computer systems, 2012, 32(2): 232-236.
[17]胡小生, 鐘勇. 基于加權(quán)聚類質(zhì)心的SVM不平衡分類方法[J]. 智能系統(tǒng)學報, 2013, 8(3): 261-265.
HU Xiaosheng, ZHONG Yong. Support vector machine imbalanced data classification based on weighted clustering centroid[J]. CAAI transactions on intelligent systems, 2013, 8(3): 261-265.
[18]胡小生, 張潤晶, 鐘勇. 兩層聚類的類別不平衡數(shù)據(jù)挖掘算法[J]. 計算機科學, 2013, 40(11): 271-275.
HU Xiaosheng, ZHANG Runjing, ZHONG Yong. Two-tier clustering for mining imbalanced datasets[J]. Computer science, 2013, 40(11): 271-275.
[19]陳思, 郭躬德, 陳黎飛. 基于聚類融合的不平衡數(shù)據(jù)分類方法[J]. 模式識別與人工智能, 2010, 23(6): 772-780.
CHEN Si, GUO Gongde, CHEN Lifei. Clustering ensembles based classification method for imbalanced data sets[J]. Pattern recognition and artificial intelligence, 2010, 23(6): 772-780.
[20]UCI machine learning repository[EB/OL]. (2009-10-16)[2015-3-20]. http://archive.ics.uci.edu/ml.
[21]李建更, 高志坤. 隨機森林針對小樣本數(shù)據(jù)類權(quán)重設(shè)置[J]. 計算機工程與應(yīng)用, 2009, 45(26): 131-134.
LI Jiangeng, GAO Zhikun. Setting of class weights in random forest for small-sample data[J]. Computer engineering and applications, 2009, 45(26): 131-134.
[22]CHAWLA N V, LAZAREVIC A, HALL L O, et al. SMOTBoost: improving prediction of the minority class in boosting[C]//Proceedings of the 7th European Conference on Principles and Practice of Knowledge Discovery in Databases. Berlin Heidelberg: Springer, 2003, 2838: 107-119.
[23]SEIFFERT C, KHOSHGOFTAAR T M, VAN HULSE J, et al. RUSBoost: a hybrid approach to alleviating class imbalance[J]. IEEE transactions on system, man and cybernetics-part a: systems and humans, 2010, 40(1): 185-197.
胡小生，男，1978年生，講師/高級工程師，主要研究方向為機器學習、數(shù)據(jù)挖掘、人工智能。主持廣東省教育廳育苗工程項目1項，參與省級、市廳級科研項目6項，發(fā)表學術(shù)論文12篇，其中被EI、ISTP檢索4篇。
溫菊屏， 女，1979年生，講師，主要研究方向為虛擬現(xiàn)實、數(shù)據(jù)挖掘。主持廣東省教育廳科研項目1項，參與省級、廳級科研和教改項目4項，發(fā)表學術(shù)論文9篇。
鐘勇， 男，1970年生，教授，博士，主要研究方向為訪問控制、隱私保護、信息檢索、云計算。主持和參與國家自然科學基金、國家星火科技計劃、省自然科學基金等國家級、省級科研項目10余項，發(fā)表學術(shù)論文30多篇，其中被SCI、EI檢索10篇。
Imbalanced data ensemble classification using dynamic balance sampling
HU Xiaosheng， WEN Juping， ZHONG Yong
(College of Electronic and Information Engineering, Foshan University, Foshan 528000, China)
Abstract：Traditional classification algorithms assume balanced class distribution or equal misclassification costs, which result in poor predictive accuracy of minority classes when handling imbalanced data. A novel imbalanced data classification method that combines dynamic balance sampling with ensemble boosting classifiers is proposed. At the beginning of each iteration, each member of the dynamic balance ensemble is trained with under-sampled data from the original training set and is augmented by artificial instances obtained using SMOTE . The distribution proportion of each class sample is randomly chosen to reflect the diversity of the training data and to provide a better training platform for the ensemble sub-classifier. Once the sub-classifiers are trained, a strong classifier is obtained using a weighting vote. Experimental results show that the proposed method provides better classification performance than other approaches.
Keywords：data mining; imbalanced data; re-sampling; ensemble; random forest
作者簡介：
中圖分類號：TP181
文獻標志碼：A
文章編號：1673-4785(2016)02-0257-07
通信作者：胡小生. E-mail：feihu@fosu.edu.cn.
基金項目：國家星火計劃項目(2014GA780031)；廣東省自然科學基金項目(2015A030313638)；廣東高校優(yōu)秀青年創(chuàng)新人才培養(yǎng)計劃資助項目(2013LYM_0097，2014KQNCX184，2015KQNCX180) ；佛山科學技術(shù)學院校級科研項目.
收稿日期：2015-07-09. 網(wǎng)絡(luò)出版日期：2016-03-14.
DOI:10.11992/tis.201507015
網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160314.1431.002.html
