一種基于改進BTS的多類非平衡分類的集成學習方法

湯志亞，趙亮，楊玲，甄小瓊，楊志鵬

(1. 成都信息工程學院，四川 成都 610225；2. 中國氣象局大氣探測重點開放實驗室，四川 成都 610225)

一種基于改進BTS的多類非平衡分類的集成學習方法

湯志亞1,2，趙亮1,2，楊玲1,2，甄小瓊1,2，楊志鵬1,2

(1. 成都信息工程學院，四川 成都 610225；2. 中國氣象局大氣探測重點開放實驗室，四川 成都 610225)

提出一種適用于多類不平衡數(shù)據(jù)的集成學習方法，以解決多類樣本分布不均衡問題.首先，利用合成少類樣本的過采樣技術(Synthetic Minority Over-sampling Technique, SMOTE)得到一組類別平衡的訓練集.然后，對每個訓練集采用二叉樹支持向量機(SVM of Binary Tree，BTS)進行訓練，最后，采用Bagging進行集成.通過5組UCI測試數(shù)據(jù)表明該算法在Gmean參數(shù)上比SMOTEBagging算法提高2.55%.

多類不平衡分類；集成方法；二叉樹支持向量機；SMOTE算法

0 引 言

類別非平衡學習問題是數(shù)據(jù)挖掘領域研究的重要課題之一.所謂類別非平衡學習問題是指在分類過程中，少數(shù)類樣本的誤判率通常比多數(shù)類樣本的誤判率高很多[1].近年來，在類別非平衡學習問題中，集成方法以其高效的性能，被廣泛用于提高現(xiàn)有方法或者幫助形成新的方法[2]，由此也越來越受到研究人員的青睞.

目前，集成方法大致分為三類：Bagging、Boosting和不同組合策略相結合的組合方法[3].集成方法主要是通過重采樣方法與集成方法相結合的方法來處理非平衡數(shù)據(jù).例如文獻[4]提出的SMOTEBagging.文獻[5]提出的SMOTEBoost和文獻[6]提出的RUSBoost，以及文獻[7]提出的EasyEnsemble和BalanceCascade.

但是，上述方法中，只有SMOTEBagging方法可直接用于多分類，其余方法只適用于二分類.并且在SMOTEBagging算法中以決策樹作為基分類器，穩(wěn)定性欠佳.BTS是由文獻[8]于2004年提出的一種新的用于多分類的分類器，以其穩(wěn)定性和高效性而得到廣泛的應用.但是其對非平衡數(shù)據(jù)集的分類不理想.因此，本文結合SMOTE算法和BTS算法，形成一種新的適用于多類非平衡數(shù)據(jù)集的分類器，稱為SMOTE-BTS.并且在此基礎上將該分類器進一步采用Bagging算法進行集成，提出一種新的適用于多類別非平衡數(shù)據(jù)分類的集成算法，稱為SMOTE-BTS-Bagging.

1 二叉樹支持向量機

1.1 支持向量機

SVM通常用于二分類問題.以二分類情況為例，假設兩類訓練樣本集為{(x1,y1),(x2,y2),…,(xn,yn)},yi∈{+1,-1},i=1,2,…,n為樣本標簽.

構造代價函數(shù)為：

(1)

約束條件為：

yi(wTxi+b)≥1-ξi,ξi≥0,i=1,2,…,n

(2)

其中：ξi稱為松弛變量；C稱為懲罰因子，用來控制關聯(lián)項的相對影響；w和b分別表示分類函數(shù)f(x)=wTx+b的權向量和閾值.則相應的拉格朗日函數(shù)為：

(3)

其中λi和μi是拉格朗日算子.對應的最優(yōu)化條件為：

λi[yi(wTxi+b)-1+ξi]=0,i=1,2,…,n;

(4)

C-μi-λi=0,i=1,2,…,n.

(5)

μiξi=0,i=1,2,…,n

(6)

最終求解分類函數(shù)為：

1.2 二叉樹支持向量機

傳統(tǒng)SVM進行多分類的方法大致分為3種：One-against-all、One-against-one和無向環(huán)圖法[9].針對SVM進行多分類的問題，近年來，一些學者提出一種基于二叉樹的支持向量機(Binary Tree of SVM，簡稱BTS)越來越受到人們的關注[8～10].同傳統(tǒng)的二分類轉(zhuǎn)多分類的方法相比，BTS結構具有高準確率，快速，并且能夠避免類別不可分和分類重疊等優(yōu)點[10].

其主要思想是：將所有類別分成兩個子類，再將兩個子類分別劃分成兩個次級子類，依次類推，直到所有的節(jié)點只含有一個類別為止.這樣，多分類問題就轉(zhuǎn)化為二分類問題，每個節(jié)點處采用SVM二值分類器作為分類函數(shù).

2 SMOTE-BTS-Bagging算法

本文采用Bagging集成學習方法，以SMOTE-BTS作為基分類器，形成一種新的適用于多分類非平衡數(shù)據(jù)的集成分類算法，稱為SMOTE-BTS-Bagging算法.

2.1 SMOTE-BTS分類器

本文結合SMOTE算法[11]和BTS算法，形成一種新的解決多類非平衡數(shù)據(jù)集的分類算法，稱為SMOTE-BTS算法.該分類算法中除了采用SMOTE算法增加樣本的平衡性，還采用隨機過采樣技術使得BTS算法中每個非葉子節(jié)點左右兩個訓練集達到平衡.

算法主要思想：首先，采用SMOTE算法使得原始訓練集S中每一類的樣本數(shù)目相等，此時得到平衡訓練集Sk；然后，采用BTS算法進行訓練，得到一個分類器；最后，采用該分類器進行分類預測.

2.2 SMOTE-BTS-Bagging算法

Bagging作為一種新的高效集成算法，應用范圍變得越來越廣泛[12].作為集成分類方法中的基分類器，要求識別率高和多樣性[13].這樣才能使得集成之后的分類器成為一個強分類器.而SMOTE-BTS正是這樣一種分類器，基于上述原則，兼顧對不平衡數(shù)據(jù)集的適應性.本文以SMOTE-BTS為基分類器，采用Bagging進行集成，形成一種新的適應于多類非平衡數(shù)據(jù)分類的集成算法，簡稱為SMOTE-BTS-Bagging算法.

SMOTE-BTS-Bagging算法流程：

(1)訓練：

1.設原始訓練集為S；

2.按照每一類的樣本數(shù)目，由小到大排列重新組成訓練集Snew；

3.按照下面的規(guī)則構建一個訓練集Sk，此訓練集中所有類別的樣本數(shù)目相等：

3a 設樣本最多的一類為M；

3b 對于每一類i(i=1,…,M-1)，

以(Nm/Ni)*b%的比例采用可重復采樣技術，對第i類進行采樣；

設置N=(Nm/Ni)*(1-b%)*100，

采用SMOTE(K,N)生成新的樣本；

4.采用Sk訓練一個SMOTE-BTS模型；

5.改變b的值；

6.重復步驟3到5，直到運行次數(shù)等于NumTree.

(2)測試新樣本：

1 .生成每一個SMOTE-BTS分類器的輸出；

2.返回得到最多投票的類別.

其中NumTree表示基分類器的個數(shù).參數(shù)b是為了增加訓練集的多樣性，同時也會使得SMOTE-BTS的分類器變得多樣性.一般如果NumTree=10，則b的變化范圍以10為間隔由10變到100.

3 類別非平衡分類的評價方法

傳統(tǒng)的分類器一般會以整體的準確率作為評價標準，由于非平衡數(shù)據(jù)中少數(shù)類的準確率通常占據(jù)更重要的地位，因此它不再適用于不平衡數(shù)據(jù)分類問題.文獻[14]中提出的平衡查準率(balanced accuracy rate，簡稱BArate)和文獻[15]提出的F-measure兩個參數(shù)能夠有效地衡量二分類非平衡數(shù)據(jù)的分類性能.文獻[16]提出的Gmean可以有效測試多類別非平衡數(shù)據(jù)的分類性能.

如果用TP表示實際為正類被預測為正類的樣本個數(shù)，TN表示實際為負類被預測為負類的樣本個數(shù)，F(xiàn)P表示實際為負類被預測為正類的樣本個數(shù)，F(xiàn)N表示實際為正類被預測為負類的樣本個數(shù).其中正類表示少數(shù)類，負類表示多數(shù)類.那么：

BArate=TP/(2(TP+FN))+TN/(2(TN+FP))

(7)

(8)

(9)

(10)

Gmean具體定義如下：設樣本集類別的總數(shù)目為N，分類器將i類樣本錯分為j類的樣本數(shù)目為Kij，則類別i的查全率的表達式為：

(11)

查全率的幾何平均值表達式為：

(12)

4 實驗結果與分析

為了驗證本文所提出算法的有效性，本節(jié)分別采用3組UCI兩類不平衡數(shù)據(jù)集和4組UCI多類不平衡數(shù)據(jù)集進行驗證，全部數(shù)據(jù)均在UCI上下載，下載網(wǎng)址是http://archive.ics.uci.edu/ml/.實驗設計思路如下：首先，選擇3組UCI中的兩類非平衡數(shù)據(jù)，同目前處理不平衡數(shù)據(jù)的主要集成方法進行對比，來驗證本算法的有效性和優(yōu)越性.然后，使用4組UCI多類非平衡數(shù)據(jù)測試本算法，同可用于多類非平衡數(shù)據(jù)的SMOTEBagging算法作對比，來進一步驗證本文提出算法在多類非平衡數(shù)據(jù)集分類上的優(yōu)越性.

4.1 兩類非平衡數(shù)據(jù)分類

表1 兩類UCI數(shù)據(jù)使用說明

本文選取pima，solarflare和balance 3組UCI測試數(shù)據(jù)進行試驗.與本文提出的SMOTE-BTS-Bagging算法作對比的集成分類方法有SMOTEBagging、SMOTEBoost、RUSBoost、EasyEnsemble和BalanceCascade.采用5折交叉驗證得到BArate、Gmean和F-measure 3個參數(shù)的測試值.3組數(shù)據(jù)的測試結果分別如圖1、圖2、圖3所示：

圖1 Pima數(shù)據(jù)測試結果 圖2 Solarflare數(shù)據(jù)測試結果

圖3 Balance數(shù)據(jù)測試結果

如圖1、圖2、圖3所示，3組UCI測試集中，本文提出的算法只有在F-measure參數(shù)上的性能略差，3組數(shù)據(jù)中，有2組數(shù)據(jù)該參數(shù)取得最高值.在BArate和Gmean兩個參數(shù)中，本文提出的算法在3組數(shù)據(jù)上均取得最高值.從而證明了本文所提出算法針對兩類非平衡問題，同其他幾種集成算法相比，具有更好的分類性能.

4.2 多類別非平衡數(shù)據(jù)分類

采用UCI中的glass、new_thyroid、ecoli和yeast 4組多類非平衡數(shù)據(jù)集進行測試.上述對比的幾種集成算法中只有SMOTEBagging算法可直接應用與多類別分類.因此本節(jié)中將本文提出的算法與SMOTEBagging、BTS和SMOTE-BTS對比，并采用5折交叉驗證得出Gmean參數(shù)值.

表2 多類UCI數(shù)據(jù)使用說明

表3 Gmean參數(shù)測試結果

由表3可以看出，在多類非平衡數(shù)據(jù)分類中，本文中的SMOTE-BTS算法在5組數(shù)據(jù)上，Gmean值均高于BTS算法，從而證明SMOTE-BTS算法更適用于多類非平衡數(shù)據(jù).采用Bagging集成方法進一步提出的SMOTE-BTS-Bagging算法在5組測試數(shù)據(jù)中，有3組數(shù)據(jù)取得最優(yōu)，而SMOTEBagging和SMOTE-BTS各在一個數(shù)據(jù)中取得最優(yōu).進一步對比所有數(shù)據(jù)的平均Gmean值，發(fā)現(xiàn)SMOTE-BTS-Bagging算法比其它算法更具有優(yōu)勢，其平均Gmean值為61.67%，而SMOTE-BTS與SMOTEBagging算法的Gmean值分別為55.64%和59.12%，分別提高了6.03%和2.55%.

5 結束語

為了解決多類樣本非平衡問題，本文提出一種基于改進BTS的多類非平衡分類集成算法，即SMOTE-BTS-Bagging方法，該方法結合SMOTE和BTS算法，并采用Bagging算法進行集成.在處理多類別非平衡數(shù)據(jù)集時，比其它算法在性能參數(shù)上有一定的提高.但是，BTS算法中參數(shù)的優(yōu)化以及與其它重采樣技術的結合仍需要進一步的研究.

[1] Liu X Y, Wu J, Zhou Z H. Exploratory undersampling for class-im- balance learning[J]. Systems, Man, and Cybernetics, Part B: Cyber- netics, IEEE Transactions on, 2009, 39(2): 539-550.

[2] HE H, MA Y. Imbalanced learning: foundations, algorithms, and a- pplications[M]. Wiley. com, 2013.

[3] Zhou Z H. Ensemble methods: foundations and algorithms [M]. C- RC Press, 2012.

[4] Wang S, Yao X. Diversity analysis on imbalanced data sets by usin- g ensemble models[C].Computational Intelligence and Data Mining, 2009. CIDM′09. IEEE Symposium on. IEEE, 2009.324-331.

[5] CHAWLA N V, LAZAREVIC A, HALL L O, et al. SMOTEBoost: Improving prediction of the minority class in boosting[M].Knowle- dge Discovery in Databases: PKDD 2003. Springer Berlin Heidelb- erg, 2003.107-119.

[6] SEIFFERT C, KHOSHGOFTAAR T M, VAN HULSE J, et al. RU- SBoost: A hybrid approach to alleviating class imbalance[J]. Syste- ms, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 2010, 40(1): 185-197.

[7] LIU X Y, WU J, ZHOU Z H. Exploratory undersampling for class- imbalance learning [J]. Systems, Man, and Cybernetics, Part B: Cy- bernetics, IEEE Transactions on, 2009, 39(2): 539-550.

[8] CHEONG S, OH S H, LEE S Y. Support vector machines with bin- ary tree architecture for multi-class classification[J]. Neural Inform- ation Processing-Letters and Reviews, 2004, 2(3): 47-51.

[9] MADZAROV G, GJORGJEVIKJ D, CHORBEV I. A multi-class S- VM classifier utilizing binary decision tree[J]. Informatica(Sloveni- a), 2009, 33(2): 225-233.

[10] FEI B, LIU J. Binary tree of SVM: a new fast multiclass training and classification algorithm[J]. Neural Networks, IEEE Transactions on, 2006, 17(3): 696-704.

[11] CHAWLA N V, BOWYER K W, HALL L O, et al. SMOTE: synthe- tic minority over-sampling technique[J]. Journal of Artificial Intelli- gence Research,2002,16(1):321-357.

[12] YAO D, YANG J, ZHAN X. An improved random forest algorithm for class-imbalanced data classification and its application in PAD risk factors analysis[J]. Open Electrical & Electronic Engineering Journal, 2013, 7(1): 62-70.

[13] HANSEN L K, SALAMON P. Neural network ensembles[J]. Patte- rn Analysis and Machine Intelligence, IEEE Transactions on, 1990, 12(10): 993-1001.

[14] HONES T R. Living in an imbalanced world[D]. University of Notre Dame, 2012.

[15] HE H, GARCIA E A. Learning from imbalanced data [J]. Knowled- ge and Data Engineering, IEEE Transactions on, 2009, 21(9): 1263-1284.

[16] 霍緯綱,高小霞. 一種適用于多類不平衡數(shù)據(jù)集的模糊關聯(lián)分類方法[J].控制與決策,2012,27(12):1833-1838.

[責任編輯：王軍]

An ensemble classification method for multi-class imbalanced datasets

TANG Zhiya1,2, ZHAO Liang1,2,YANG Ling1,2,ZHEN Xiaoqiong1,2,YANG Zhipeng1,2

(1. Chengdu University of Information Technology, Chengdu 610225,China;2. CMA.Key Laboratory of Atmospheric Sounding，Chengdu 610225,China)

To solve the problem of multi-class imbalanced datasets classification, an ensemble classification method for multi-class imbalanced datasets is presented. Firstly, we get balanced datasets by using the SMOTE algorithm. Then, we utilize the binary tree of SVMs to get the models for every training dataset. Finally, we make an ensemble with bagging method for the models. The result showed that compared with SMOTEBagging, our method improved 2.55% on the Gmean value to five UCI multi-class imbalanced benchmark datasets.

multi-class imbalanced dataset; ensemble method; Binary tree of SVM; SMOTE algorithm

2015-03-19

科技部公益性行業(yè)(氣象)科研專項課題(GYHY201106047)支持

湯志亞(1977-)，男，河南商丘人，成都信息工程學院講師，碩士，主要從事氣象探測技術的研究.

TP391

A

1672-3600(2015)06-0030-05