基于主動學習不平衡多分類AdaBoost算法的心臟病分類

王莉莉，付忠良，陶 攀，胡 鑫

(1.中國科學院 成都計算機應用研究所，成都 610041； 2.中國科學院大學，北京 100049) (*通信作者電子郵箱wanglili8773@163.com)

基于主動學習不平衡多分類AdaBoost算法的心臟病分類

王莉莉1,2*，付忠良1,2，陶 攀1,2，胡 鑫1,2

(1.中國科學院 成都計算機應用研究所，成都 610041； 2.中國科學院大學，北京 100049) (*通信作者電子郵箱wanglili8773@163.com)

針對不平衡分類中小類樣本識別率低問題，提出一種基于主動學習不平衡多分類AdaBoost改進算法。首先，利用主動學習方法通過多次迭代抽樣，選取少量的、對分類器最有價值的樣本作為訓練集；然后，基于不確定性動態間隔的樣本選擇策略，降低訓練集的不平衡性；最后，利用代價敏感方法對多分類AdaBoost算法進行改進，對不同的類別給予不同的錯分代價，調整樣本權重更新速度，強迫弱分類器“關注”小類樣本。在臨床經胸超聲心動圖(TTE)測量數據集上的實驗分析表明：與多分類支持向量機(SVM)相比，心臟病總體識別率提升了5.9%，G-mean指標提升了18.2%，瓣膜病(VHD)識別率提升了0.8%，感染性心內膜炎(IE)(小類)識別率提升了12.7%，冠心病(CAD)(小類)識別率提升了79.73%；與SMOTE-Boost相比，總體識別率提升了6.11%，G-mean指標提升了0.64%，VHD識別率提升了11.07%，先心病(CHD)識別率提升了3.69%。在TTE數據集和4個UCI數據集上的實驗結果表明，該算法在不平穩多分類時能有效提高小類樣本識別率，并且保證其他類別識別率不會大幅度降低，綜合提升分類器性能。

主動學習；不平衡分類；多分類AdaBoost；多類別分類；心臟病分類

0 引言

不平衡數據集通常指類別間數量相差較大的數據集，稱具有少量樣本的那些類為小類，而具有大量樣本的那些類為大類，傳統分類方法追求的是整體識別率，而對小類的識別率一般較低。目前，對于不平衡數據集的分類問題的研究主要分為兩大類：一類是改變訓練集樣本分布，降低不平衡程度；另一類是適當修改現有算法，使之適應不平衡分類問題。

降低不平衡度的方法包括訓練集重采樣方法和訓練集劃分方法。SMOTE(Synthetic Minority Over-sampling Technique)算法[1]是一種簡單有效的上采樣方法，首先為每個小類樣本隨機選出幾個鄰近樣本，并在該樣本與這些鄰近樣本的連線上隨機取點，生成無重復的新的小類樣本。Japkowicz等[2]的實驗研究了不平衡數據對經典算法的影響，包括決策樹C4.5、BP(Back Propagation)神經網絡和支持向量機(Support Vector Machine, SVM)等，由于支持向量機對分類性能影響較大的是少數的支持向量，因此該方法對數據不平衡度相對不敏感。Chen等[3]通過修剪大類的支持向量，使支持向量個數平衡，提高稀有類的識別率。Chan等[4]將大類樣本按照合理的類別樣本分布比例隨機地劃分成一系列不相交子集，并分別與小類樣本融合，組成一系列平衡的分類子問題，訓練成子分類器，最后通過元學習將這些子分類器集成組合分類器。Lu等[5-6]采用最小最大模塊化SVM模型，提出了“部分對部分”任務分解策略，控制每個子問題的規模和平衡度，并根據先驗知識和訓練集的樣本分布，制定有效的分解規則。SMOTEBoost(Synthetic Minority Over-sampling Technique and Boosting)算法[7]的每次迭代使用SMOTE生成新的樣本，不再使用AdaBoost(Adaptive Boosting)集成算法中的權值調整規則，使Boosting算法更專注于小類樣本中的難分樣本。這些方法雖然能有效地提升小類的識別率，但同時也忽略了很多潛在有用的大類樣本信息，造成大類識別率降低。

算法自適應方法包括分類器集成[8]和代價敏感學習[9]等。Zhou等[10]提出了代價敏感神經網絡與分類器集成相結合的方法，實驗表明，分類器集成對二分類不平衡問題和多分類不平衡問題同樣有效。文獻[11]提出了AdaBoost.MLR算法解決多類別分類問題，對識別率較低的類別給予較高的錯分代價，提高“難分”類別的識別精度，但提升幅度有限。AdaCost[12]算法在AdaBoost算法[13]的權值更新規則中引入錯分代價因子，提高了小類樣本的查全率和查準率。這些方法在模型訓練過程中引入了錯分代價因子，強迫分類器“關注”錯分代價較高的小類樣本，能在確保大類樣本識別率的前提下，提升小類樣本的識別率，但由于類別不平衡性和模型自身的原因，對小類識別率的提升是有限的。

多分類SVM算法[14]采用一對一、一對其余的方法將二分類SVM擴展到多類別分類問題中，在不平衡數據分類中表現出很好的分類性能。文獻[15]采用主動學習方法構造平衡的訓練集，并提出了一種基于SVM的主動學習樣本選擇策略，實驗表明，主動學習方法能用較少的樣本獲得較高的分類性能，但是主動學習需要迭代多次選擇最有價值的樣本，進行多次模型訓練，而SVM的非線性模型優化過程對計算和存儲要求太高。AdaC2.M1算法[16]針對多類別不平衡分類問題，提出了基于代價敏感的AdaBoost集成學習方法，采用遺傳算法搜索各個類別的錯分代價,實驗表明代價敏感方法很難較好地適用于多類別不平衡分類問題。

研究分析表明，單一地使用重采樣方法改變訓練集樣本分布，雖然能提升小類樣本的識別率，但也會大幅度降低大類樣本的識別率；單一地使用代價敏感方法雖然保證了大類樣本識別率不會降低，但對小類樣本的識別率提升是有限的，因此，本文采用主動學習方法，選擇最有潛在價值的樣本，充分利用稀有的小類樣本，降低數據集的不平衡性，并結合代價敏感方法，在多分類AdaBoost算法弱分類器的迭代訓練中，對小類樣本給予較高的錯分代價，對大類樣本給予較低的錯分代價，動態調整樣本權值更新速度，實現主動學習方法、代價敏感方法和多分類AdaBoost方法的融合，在保證大類樣本識別率不會降低的前提下，大幅度提高小類樣本的識別率。

1 傳統多分類AdaBoost算法

AdaBoost算法是目前應用最廣泛的機器學習方法之一，基本思想是將若干個弱分類器按照某種規則組合起來，集成為一個分類能力很強的強分類器，最初應用于二分類問題，多類別分類問題是二分類問題的擴展。假設訓練樣本集X={(x1,y1),(x2,y2),…,(xm,ym)}，其中yi∈{1,2,…,K}。對于樣本xi，若l=yi，則Yi(l)=1,否則Yi(l)=-1。集成學習算法通常指通過某種方式得到T個弱分類器ht(x):X×Y→R，弱分類器權重αt，然后進行組合得到強分類器，即

(1)

多分類AdaBoost算法如下。

輸入：訓練樣本集X={(x1,Y1),…,(xm,Ym)}，樣本權重D，弱分類器h(x):X×Y→R，迭代次數T。 初始化：D1(i,l)=1/(mK)，其中i=1,2,…,m，l=1,2,…,K。

AdaBoost算法中T個不同的弱分類器是通過改變數據分布來實現的，樣本權重更新是根據弱分類器對樣本的分類情況來確定的，具體來說，如果弱分類器對某個樣本的某個標簽分類正確，則對應的權重減少，如果分類錯誤，則對應權重增加，權重減少與增加的速度只與弱分類器有關，每次權重改變的速度是一樣的。

2 主動學習不平衡多分類方法

在傳統的主動學習任務中，往往選擇對分類器最有價值的樣本加入訓練集參與訓練，以更新分類器，但在不平衡多分類問題中，如果仍采用傳統的樣本選擇方法，可能會導致訓練集中大類的樣本一直更新，而小類的樣本一直得不到更新，即分類器的更新存在不平衡性。針對這個問題，本文提出一種新的基于不確定性動態間隔的樣本選擇策略，從原始訓練集中挑選那些更有意義的樣本，選擇數量最小但信息量最大的子集作為最終訓練集，降低類別之間數據的不平衡性。

2.1 主動學習多分類AdaBoost算法

設有標注樣本集為X={(x1,y1),(x2,y2),…,(xm,ym)}，首先抽取部分最有價值的樣本作為初始訓練集，且類別之間樣本均衡。設Lk、Uk分別為第k次學習時的訓練集和非訓練集，滿足X=Lk∪Uk。用多分類AdaBoost算法對Lk樣本集進行訓練，得到強分類器，并對樣本集Uk進行預測，按照某種樣本選擇策略選擇最有價值的樣本加入到Lk+1中，重復上述過程直到滿足停止條件。

2.1.1 樣本選擇策略

本文采用基于Margin策略的不確定性來選擇待標注的樣本，如式(2)所示：

(2)

其中：l1和l2分別是最具有最大和第二大值的置信度輸出值，即當前分類模型最確定的兩個類別，二者的差值越小說明模型對樣本的不確定性越大，則對樣本進行標注獲得的信息量越多；βx為數據平衡控制因子，目的是保證類別之間的數據平衡性。

2.1.2 基于主動學習的訓練集選擇方法

輸入：有標注樣本集X={(x1,y1),(x2,y2),…,(xm,ym)}，其中yi∈{1,2,…,K}，初始訓練集L1，非訓練集U1=X-L1。 Fork=1,2,…,iter1)在訓練集Lk上訓練多分類AdaBoost分類器f； 2)統計訓練集Lk中各類別包含樣本個數，記包含樣本數最少的類別為c1，包含樣本數最大的類別為c2； 3)用分類器f對非訓練集Uk中樣本預測，如果分類模型滿足停止條件，循環終止； 4)如果c2/c1>thresh，且非訓練集Uk中樣本x對應的類別為c1，則令βx=ε；否則βx=1；對每個樣本計算βx(f(x,l1)-f(x,l2))，l1和l2分別是最具有最大和第二大值的置信度輸出值，選擇最小的N個樣本，記為S； 5)更新Lk+1=Lk∪S，Uk+1=UkS; End輸出：訓練集L。

2.2 基于代價敏感的不平衡多分類AdaBoost算法

分類算法總是希望平均錯分代價最小，即希望式(3)最小：

(3)

對于δ(π)函數，當π為真時，δ(π)為1；否則為0。在多分類AdaBoost算法中引入動態代價調整函數，可以得到代價敏感多分類AdaBoost算法。

2.2.1 改進算法流程

2.2.2 如何選擇αt

3 實驗與分析

3.1 評價指標

3.2 實驗數據集

本文實驗使用數據包括TTE測量數據集和4個UCI(University of California Irvine)數據集，其中TTE數據集來源于華西醫院，34個屬性，共有2 214個心臟疾病病例，包括感染性心內膜炎(Infective Endocarditis, IE)58例，冠心病(Coronary Artery Disease, CAD)169例，先心病(Congenital Heart Disease, CHD)733例，瓣膜病(Valvular Heart Disease, VHD)1 177例，每個病例只患有一種疾病，最大不平衡度為20.3。詳細的數據集信息如表1所示。

表1 數據集信息

3.3 在TTE數據集上的實驗結果與分析

3.3.1 基于主動學習的訓練集選擇

實驗過程中，訓練集和測試集比例按照6∶4劃分，然后在訓練集上采用基于不確定性動態間隔的樣本選擇策略選擇新的訓練集。

初始訓練集L1的選擇：在全部訓練集上訓練多分類AdaBoost分類器f，然后調用分類器f對訓練集中全部樣本進行預測，對每個樣本計算f(x,l1)-f(x,l2)，其中l1和l2分別是最具有最大和第二大值的置信度輸出值，對每個類別選擇f(x,l1)-f(x,l2)值最小的10個樣本，共得到40個樣本作為初始訓練集；

訓練集選擇過程：按照2.1.2節的訓練集選擇方法，結合數據集實際情況，每次迭代選擇4個最有價值的樣本加入訓練集，令ε=0.005，控制訓練集平衡度，一定程度上保證每次迭代都能選擇到小類樣本加入訓練集。訓練集選擇前后及測試集樣本個數如表2所示。

3.3.2 錯分代價因子c的調節

本文采用2.2.1節中描述的改進算法，選擇每個類別的查準率作為評價指標來驗證改進算法對各個類別的性能影響。在對參數c的最優選擇實驗時，錯分代價調整因子c值在[1,30]區間內以步長1變化，找出較小的最合適的c值范圍，然后在小范圍內以0.1步長變化，尋找最合適的c值。以下僅列出c=22,23,24,25,26時的實驗結果，具體如表3所示，可知最可能的c在區間[23,24]內。

表2 訓練集選擇結果(TTE)

表3 不同參數c的識別率(TTE)

3.3.3 與其他算法的對比實驗結果

在對參數c的最優選擇實驗時，錯分代價調整因子c值在[23,24]區間內以步長0.1變化，尋找最合適的參數c。通過實驗可知，當c=23.8時，總體識別率最高可達88.34%，VHD識別率為92.62%，CHD識別率為85.76%，IE識別率為76.85%，CAD識別率為80.14%。

在最優參數下，將本文算法與SMOTEBoost、AdaBoost.MLR、多分類SVM和ML-KNN(Multi-LabelK-Nearest Neighbor)[17]進行比較，每個類別的詳細識別率和總體分類識別率如表4所示。

表4 不同算法的識別率(TTE)

從表4可以看出，ML-KNN算法和AdaBoost.MLR算法對IE和CAD的識別率很低，這是因為這兩種算法的分類性能跟訓練集有關；由于SVM模型只與少數支持向量有關，分類性能較好一些，但對CAD的識別率較低，對IE的識別率僅稍好于隨機猜測；SMOTEBoost算法雖然能提升小類樣本識別率，但其他類別的樣本識別率也會很大幅度地降低。本文算法相較于多分類SVM，心臟病總體識別率提升了5.9%，G-mean指標提升了18.2%，VHD識別率提升了0.8%，IE(小類)識別率提升了12.7%，CAD(小類)識別率提升了79.73%；相較于SMOTEBoost，總體識別率提升了6.11%，G-mean指標提升了0.64%，VHD識別率提升了11.07%，CHD識別率提升了3.69%。

3.4 在UCI數據集上的實驗結果與分析

實驗過程中，分別對4個UCI數據集按照6∶4劃分訓練集和測試集，首先按照2.1.2節中的樣本選擇方法，產生新的訓練集，然后在新的訓練集上采取和3.3.2節類似的步驟，尋找最佳錯分代價因子c。對于每個數據集，選擇前后訓練集的樣本個數和最佳參數c值如表5所示。

表5 訓練集選擇結果和參數c設置(UCI)

只有當各個類別的查準率都很高時G-mean才會高，因此實驗采用G-mean指標對本文算法和ML-KNN、多分類SVM、SMOTEBoost、AdaBoost.MLR算法進行對比，各算法的G-mean值如表6所示。

表6 各算法的G-mean值對比(UCI)

從表6可以看出有些數據集的G-mean值為0，這是由于小類樣本的查準率為0造成的，這也說明小類樣本的分類性能影響算法的整體性能。

本文算法在TTE、abalone和ecoli數據集上取得最高的G-mean值；相較于多分類SVM算法，TTE數據集上的G-mean值提升了18.2%，相較于SMOTEBoost算法，G-mean值提升了0.64%。

4 結語

本文針對多類別不平衡分類中小類樣本識別率低問題，采用主動學習思想，選擇少量的最有價值的樣本作為訓練集，并將不平衡分類問題轉化為代價敏感分類問題。在多分類AdaBoost算法弱分類器的迭代訓練時，對小類樣本給予較高的錯分代價，在可行的代價選擇空間內，尋找能使得分類性能最優的錯分代價調整因子，調整樣本權重更新速度，對多分類AdaBoost算法進行改進。在心臟病TTE測量數據集上的實驗結果表明，該方法對小類樣本識別率有較大幅度的提升，還能保證其他類別的識別率不會大幅降低，綜合提升了分類器的性能。綜合UCI數據集上的實驗結果表明，本文算法在TTE、abalone和ecoli數據集上的G-mean值最高，而且訓練集只需要少量的有價值的樣本，模型訓練效率高、速度快、識別率高，性能更優。

References)

[1] 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.

[2] JAPKOWICZ N, STEPHEN S. The class imbalance problem: a systematic study [J]. Intelligent Data Analysis, 2002, 6(5): 429-449.

[3] CHEN X, GERLACH B, CASASENT D. Pruning support vectors for imbalanced data classification [C]// IJCNN 2005: Proceedings of the 2005 International Joint Conference on Neural Networks. Piscataway, NJ: IEEE, 2005, 3: 1883-1888.

[4] CHAN P K, STOLFO S J. Toward scalable learning with non-uniform class and cost distributions: a case study in credit card fraud detection [C]// KDD 1998: Proceedings of the 1998 ACM SIGKDD Conference on Knowledge Discovery and Data Mining. Menlo Park, CA: AAAI Press, 1998: 164-168.

[5] LU B L, ITO M. Task decomposition and module combination based on class relations: a modular neural network for pattern classification [J]. IEEE Transactions on Neural Networks, 1999, 10(5): 1244-1256.

[6] LU B L, WANG K A, UTIYAMA M, et al. A part-versus-part method for massively parallel training of support vector machines [C]// IJCNN 2004: Proceedings of the 2004 International Joint Conference on Neural Networks. Piscataway, NJ: IEEE, 2004, 1: 735:740.

[7] CHAWLA N V, LAZAREVIC A, HALL L O, et al. SMOTEBoost: improving prediction of the minority class in boosting [C]// PKDD 2003: Proceedings of the 2003 European Conference on Principles of Data Mining and Knowledge Discovery. Berlin: Springer, 2003: 107-119.

[8] FU Z, WANG L, ZHANG D. An improved multi-label classification ensemble learning algorithm [C]// CCPR 2014: Proceedings of the 6th Chinese Conference on Pattern Recognition. Berlin: Springer, 2014: 243-252.

[9] 付忠良.多分類問題代價敏感AdaBoost算法[J].自動化學報,2011,37(8):973-983.(FU Z L. Cost-sensitive AdaBoost algorithm for multi-class classification problems [J]. Acta Automatica Sinica, 2011, 37(8): 973-983.)

[10] ZHOU Z H, LIU X Y. Training cost-sensitive neural networks with methods addressing the class imbalance problem [J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(1): 63-77.

[11] 王莉莉,付忠良.基于標簽相關性的多標簽分類AdaBoost算法[J].四川大學學報(工程科學版),2016,48(5):91-97.(WANG L L, FU Z L. Multi-label AdaBoost algorithm based on label correlations [J]. Journal of Sichuan University (Engineering Science Edition), 2016, 48(5): 91-97.)

[12] FAN W, STOLFO S J, ZHANG J, et al. AdaCost: misclassification cost-sensitive boosting [C]// ICML 1999: Proceedings of the 1999 International Conference on Machine Learning. San Francisco, CA: Morgan Kaufmann, 1999: 97-105.

[13] SCHAPIRE R E, SINGER Y. Improved boosting algorithms using confidence-rated predictions [J]. Machine Learning, 1999, 37(3): 297-336.

[14] WU T F, LIN C J, WENG R C. Probability estimates for multi-class classification by pairwise coupling [J]. Journal of Machine Learning Research, 2004, 5: 975-1005.

[15] ERTEKIN S, HUANG J, GILES C L. Active learning for class imbalance problem [C]// SIGIR 2007: Proceedings of the 2007 International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2007: 823-824.

[16] SUN Y, KAMEL M S, WANG Y. Boosting for learning multiple classes with imbalanced class distribution [C]// ICDM 2006: Proceedings of the 2006 International Conference on Data Mining. Washington, DC: IEEE Computer Society, 2006: 592-602.

[17] ZHANG M L, ZHOU Z H. ML-KNN: a lazy learning approach to multi-label learning [J]. Pattern Recognition, 2007, 40(7): 2038-2048.

This work is partially supported by the Sichuan Science and Technology Support Project (2016JZ0035), West Light Foundation of Chinese Academy of Sciences.

WANGLili, born in 1987, Ph. D. candidate. Her research interests include machine learning, pattern recognition, data mining.

FUZhongliang, born in 1967, M. S., professor. His research interests include machine learning, pattern recognition.

TAOPan, born in 1988, Ph. D. candidate. His research interests include machine learning, data mining.

HUXin, born in 1987, M. S. candidate. His research interests include data warehouse, data mining.

Heartdiseaseclassificationbasedonactiveimbalancemulti-classAdaBoostalgorithm

WANG Lili1,2*, FU Zhongliang1,2, TAO Pan1,2, HU Xin1,2

(1.ChengduInstituteofComputerApplication,ChineseAcademyofSciences,ChengduSichuan610041,China;2.UniversityofChineseAcademyofSciences,Beijing100049,China)

An imbalance multi-class AdaBoost algorithm with active learning was proposed to improve the recognition accuracy of minority class in imbalance classification. Firstly, active learning was adopted to select the most informative samples for classifiers through multiple iterations of sampling. Secondly, a new sample selection strategy based on uncertainty of dynamic margin was proposed to tackle the problem of data imbalance in the multi-class case. Finally, the cost sensitive method was adopted to improve the multi-class AdaBoost algorithm: giving different class with different misclassification cost, adjusting sample weight update speed, and forcing weak learners to “concern” minority class. The experimental results on clinical TransThoracic Echocardiography (TTE) data set illustrate that, when compared with multi-class Support Vector Machine (SVM), the total recognition accuracy of heart disease increases by 5.9%, G-mean improves by 18.2%, the recognition accuracy of Valvular Heart Disease (VHD) improves by 0.8%, the recognition accuracy of Infective Endocarditis (IE) (minority class) improves by 12.7% and the recognition accuracy of Coronary Artery Disease (CAD) (minority class) improves by 79.73%; compared with SMOTE-Boost, the total recognition accuracy of heart disease increases by 6.11%, the G-mean improves by 0.64%, the recognition accuracy of VHD improves by 11.07%, the recognition accuracy of Congenital Heart Disease (CHD) improves by 3.67%. The experiment results on TTE data and 4 UCI data sets illustrate that when used in imbalanced multi-class classification, the proposed algorithm can improve the recognition accuracy of minority class effectively, and upgrade the overall classifier performance while guaranteeing the recognition accuracy of other classes not to be decreased dramatically.

active learning; imbalance classification; multi-class AdaBoost; multi-class classification; heart disease classification

TP391.4; TP181

:A

2017- 01- 12;

:2017- 02- 27。

四川省科技支撐計劃項目(2016JZ0035)；中國科學院西部之光項目。

王莉莉(1987—)，女，河南周口人，博士研究生，主要研究方向：機器學習、模式識別、數據挖掘； 付忠良(1967—)，男，重慶合川人，教授，碩士，主要研究方向：機器學習、模式識別； 陶攀(1988—)，男，河南安陽人，博士研究生，主要研究方向：機器學習、數據挖掘； 胡鑫(1987—)，男，貴州遵義人，碩士研究生，主要研究方向：數據倉庫、數據挖掘。

1001- 9081(2017)07- 1994- 05

10.11772/j.issn.1001- 9081.2017.07.1994