4) 如果k≥a,則從數據集SP中進行隨機欠采樣,采樣數目為m-k,將其加入集合S′,在集合SN中應用SMOTE進行過采樣,生成k-a個合成樣例,連同SN中的a個樣本,都加入集合S′;
5)輸出集合S′ 。
算法依據2)中所產生的隨機整數值大小來決定相應的采樣操作,如果產生的隨機數k小于初始數據集的負類樣本數量,則在負類樣本集進行欠采樣,在正類樣本集進行過采樣,使得最終輸出集合S′的樣本數量與初始數據集數量一致,反之,則進行相反的采樣。與傳統的采樣方法不同的是,在步驟4中對正類樣本進行欠采樣,對負類樣本進行過采樣,通過隨機函數產生的隨機數,使得輸出集合S′在總數量一定的情況下保持對對各類別樣本的中立性。
2.2訓練樣例權值更新
在第t次迭代過程中,需要對兩個集合中的樣例權重進行更新,分別是動態平衡采樣后的輸出集合S′和子分類器形成之后的初始數據集S。
分析動態平衡采樣算法過程可知,經過數據采樣之后,新數據集S′的樣例總數與初始數據集S一致,均為m,其中包括從數據集S抽取的部分樣例,以及部分由SMOTE方法產生的合成樣例。S′中的樣本權值按照式(1)更新:
(1)

第t次迭代訓練結束時,AdaBoost分類算法在數據集S′進行學習后得到子分類器ht:x→{-1,+1},t=1,2,…,T,ht(x)給出數據集S中的樣例x的所屬類別,根據子分類器的分類情況,更新樣本權值,增加錯分樣本的權值,減少正確分類樣本權值,以便下次迭代時,“錯分”樣本得到更多關注。
計算子分類器ht(x)的分類錯誤率εt:
(2)
如果εt>0.5,終止此輪迭代。
計算子分類器投票權重αt:
(3)
更新樣例權值:
(4)
式中Zt是歸一化常數。
完整算法如算法2所示。
算法2動態平衡采樣的不平衡分類算法

2) for t=1,2,…,T
① 調用動態平衡采樣算法,獲得數據集S′;
② 利用式(1)設置S′中的樣例權值;
③ 使用數據集S′及其中的樣例權值,訓練基于AdaBoost算法的子分類器ht(x);
④ 按照式(2)計算分類器ht(x)的誤差εt,按照式(3)計算ht(x)的投票權重αt;
⑤ 按照式(4)更新數據集S中的樣本權重;
3實驗結果與分析
3.1評價度量
傳統分類器采用分類精度指標衡量分類性能,其追求整體分類準確率,忽略了在不平衡數據分類過程中需要特別關注的正類分類準確率。針對不平衡數據,許多學者提出了在兩類混淆矩陣基礎上的Fmeasure[10]、Gmean[11]等評價方法。
在混淆矩陣中,TP(true positive)、FN(false negative)、TN(true negative)、FP(false positive)分別代表分類正確的正類樣本、假的負類樣本、正確的負類樣本以及假的正類樣本的數目。基于混淆矩陣,Fmeasure定義如下:

Fmeasure定義說明:較大值表示Recall和Precision都較大,因此,其能夠較好評價正類分類性能。
Gmean其定義如下:
式中

Gmean兼顧了正類準確率和負類準確率,比整體分類準確率更適合于不平衡數據分類評價。
本文使用Fmeasure準則來衡量正類的分類性能,使用Gmean準則來衡量數據集整體分類性能。
3.2UCI數據
為了檢驗本文所提方法的有效性,選擇6組具有實際工程應用背景的UCI數據[21]進行測試,對于含有多個類別的數據,取其中某個類為正類,合并其余類為負類,各數據集的基本信息見表1。

表1 UCI數據集信息
3.3實驗結果及分析
實驗中對比算法如下:
1)隨機森林(random forest,RF)算法,RF算法作為一種集成算法,在處理不平衡數據時有獨特的優勢,能夠在某種程度上減少不均衡數據帶來的影響[22],因此將其直接應用在初始不平衡數據集進行分類。
2)SMOTEBoost[23]算法,將SMOTE方法與AdaBoost.M2結合,在每次集成迭代中生成新的合成樣例,使得分類器更加關注小類樣本。
3)RUSBoost[24],與SMOTEBoost方法相類似,采用隨機欠采樣從負類樣本中隨機移除樣例,然后應用AdaBoost進行多次迭代。
4)文獻[4]提出的集成方法K-means+Bagging,首先在負類樣本上應用K-means聚類,提取與正類樣本數量一致的聚類質心,組成平衡訓練集,參與Bagging集成。
上述3種集成方法以及本文算法均使用C4.5決策樹算法作為基分類器算法。
為客觀對比上述不平衡數據分類方法,實驗數據采用10折交叉驗證方式,重復10次,以平均值作為最終的分類結果。
表2和表3分別列出5種方法在6個UCI數據集上的正類Fmeasure值和數據集整體的Gmean值,最后一行列出每種方法在所有數據集上的平均結果。

表2 5種方法的Fmeasure值比較

表3 5種方法的Gmean值比較
從表2的Fmeasure值可以看出,本文方法除了在sick數據集稍微低于SMOTEBoost算法之外,在其他5個數據集上均有最佳表現,比較各種算法在6組UCI數據上的平均值,本文方法比隨機森林RF算法有14.2%的提升,與基于聚類欠采樣的集成算法相比有27.3%的提升,說明本文所提方法在少數類分類性能方面有巨大的提升。
比較各個算法的整體分類性能Gmean,從表3可以看出,本文方法也僅在sick數據集上稍遜于最優算法SMOTEBoost,二者精度相差不超過1‰;在6個數據集上的平均分類性能上,本文方法獲得最優精度。
結合表1~3可以看出,隨著數據不平衡度的提高,無論是隨機欠采樣還是基于聚類的欠采樣,由于都會對原始數據集造成樣本丟失,分類性能都有所下降,特別是在letter和page-blocks數據集上,差距比較明顯。與之對比,本文方法在數據采樣過程中也需要對某類樣本進行欠采樣,通過多次動態、隨機性采樣調和,使得抽樣數據能夠較好地保持對原始數據的分布;與此同時,對另外一類樣本進行SMOTE過采樣,在沒有增加數據規模條件下,保持對各類樣本的中立性,或者對正類過采樣,或者對負類過采樣。從最終分類結果來看,本文方法在不降低數據集整體Gmean值的基礎上,提高了正類的Fmeasure值,對正類和負類都具有較高的識別率。
本文算法中經過動態平衡采樣后參與基分類器訓練的數據集樣本規模與初始數據集一致,即集合數據大小比例為100%,為考察參與訓練的不同數據規模比例對算法分類性能的影響,選取本文算法、隨機森林和SMOTEBoost 3種算法,同時選擇以letter數據集為例,在20%~100%范圍內每次增加20%比例的數據,參與集成學習,迭代10次,相關算法的Fmeasure、Gmean均值如圖1所示。

圖1 不同數據規模對分類性能影響Fig.1 Performance measures of different ensemble size
從圖1可看出,隨著參與訓練數據集比例的增大,無論是正類分類性能還是整體分類精度,都有所上升,但是隨著數據比例的增大,相應的分類性能提升幅度有限。另外,在數據比例為20%、40%時,3種算法相對應的Fmeasure和Gmean值幾乎是線性提升,這說明過低比例的抽樣數據由于損失太大的原始數據分布信息,會嚴重影響算法的分類性能。
4結束語
針對類別不平衡數據分類問題,本文提出了一種混合數據采樣與Boosting技術相結合的集成分類方法。該方法統籌運用欠采樣和過采樣,在保持訓練集數據規模一致條件下,靈活調整各類別樣本數量比例,較好地保持原始數據分布,然后采用Boosting技術進行多次迭代學習,獲得更強性能分類器。實驗結果表明,該方法能夠有效提高正類樣本的分類性能。
由于數據集本身的多樣性和復雜性,諸如類重疊分布、噪聲樣本等均會影響不平衡數據性能,如果進行有針對性的數據預處理工作,將會使得動態平衡采樣的數據分布更加合理,對正類的分類性能將會進一步提高。此外,將本文方法應用于多類別不平衡數據分類,也是今后需要進一步研究的方向。
參考文獻:
[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]郭麗娟, 倪子偉, 江弋, 等. 集成降采樣不平衡數據分類方法研究[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]李雄飛, 李軍, 董元方, 等. 一種新的不平衡數據學習算法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]韓敏, 朱新榮. 不平衡數據分類的混合算法[J]. 控制理論與應用, 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]. 智能系統學報, 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]翟云, 楊炳儒, 曲武. 不平衡類數據挖掘研究綜述[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]蔣盛益, 苗邦, 余雯. 基于一趟聚類的不平衡數據下抽樣算法[J]. 小型微型計算機系統, 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]胡小生, 鐘勇. 基于加權聚類質心的SVM不平衡分類方法[J]. 智能系統學報, 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]胡小生, 張潤晶, 鐘勇. 兩層聚類的類別不平衡數據挖掘算法[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]陳思, 郭躬德, 陳黎飛. 基于聚類融合的不平衡數據分類方法[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]李建更, 高志坤. 隨機森林針對小樣本數據類權重設置[J]. 計算機工程與應用, 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年生,講師/高級工程師,主要研究方向為機器學習、數據挖掘、人工智能。主持廣東省教育廳育苗工程項目1項,參與省級、市廳級科研項目6項,發表學術論文12篇,其中被EI、ISTP檢索4篇。

溫菊屏, 女,1979年生,講師,主要研究方向為虛擬現實、數據挖掘。主持廣東省教育廳科研項目1項,參與省級、廳級科研和教改項目4項,發表學術論文9篇。

鐘勇, 男,1970年生,教授,博士,主要研究方向為訪問控制、隱私保護、信息檢索、云計算。主持和參與國家自然科學基金、國家星火科技計劃、省自然科學基金等國家級、省級科研項目10余項,發表學術論文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);廣東高校優秀青年創新人才培養計劃資助項目(2013LYM_0097,2014KQNCX184,2015KQNCX180) ;佛山科學技術學院校級科研項目.
收稿日期:2015-07-09. 網絡出版日期:2016-03-14.
DOI:10.11992/tis.201507015
網絡出版地址:http://www.cnki.net/kcms/detail/23.1538.TP.20160314.1431.002.html