多子域隔離學習組合決策用于不均衡樣本

靳燕　彭新光

摘要：

為進一步弱化數據不均衡對分類算法的束縛，從數據集區域分布特性著手，提出了不均衡數據集上基于子域學習的復合分類模型。子域劃分階段，擴展支持向量數據描述（SVDD）算法給出類的最小界定域，劃分出域內密集區與域外稀疏區。借鑒不同類存在相似樣本的類重疊概念，對邊界樣本進行搜索，組合構成重疊域。子域清理階段，基于鄰近算法（KNN）的鄰近性假設，結合不同域的密疏程度，設置出樣本有效性參數，對域內樣本逐個檢測以清理噪聲。各子域隔離參與分類建模，按序組合產生出用于不均衡數據集的復合分類器CCRD。實驗設計三類比較方案（相似算法比較、代價敏感MetaCost比較和SMOTE抽樣比較），前兩類比較中，CCRD對正類的正確分類改善明顯，且未加重負類誤判；后一類比較中，改善了負類的誤判情形，且未影響正類的正確分類。在五類數據集的逐個比較中，CCRD分類性能均有提升，在Haberman_sur的正類分類性能提升上尤為明顯。結果表明，基于子域學習的復合分類模型的分類性能較好，是一種研究不均衡數據集的較有效的方法。

為進一步弱化數據不均衡對分類算法的束縛，從數據集區域分布特性著手，提出了不均衡數據集上基于子域學習的復合分類模型。子域劃分階段，擴展支持向量數據描述（SVDD）算法給出類的最小界定域，劃分出域內密集區與域外稀疏區。借鑒不同類存在相似樣本的類重疊概念，對邊界樣本進行搜索，組合構成重疊域。子域清理階段，基于鄰近算法（KNN）的鄰近性假設，結合不同域的密疏程度，設置樣本有效性參數，對域內樣本逐個檢測以清理噪聲。各子域隔離參與分類建模，按序組合產生出用于不均衡數據集的復合分類器CCRD。在相似算法對比以及代價敏感MetaCost對比中，CCRD對正類的正確分類改善明顯，且未加重負類誤判；在SMOTE抽樣比較中，CCRD改善了負類的誤判情形，且未影響正類的正確分類；在五類數據集的逐個比較中，CCRD分類性能均有提升，在Haberman_sur的正類分類性能提升上尤為明顯。結果表明，基于子域學習的復合分類模型的分類性能較好，是一種研究不均衡數據集的較有效的方法。

關鍵詞：

不均衡數據集區域分布；支持向量數據描述；稀疏域與重疊域；子域隔離學習；復合分類器

中圖分類號：

TP391

文獻標志碼：A

Abstract：

Started with the regional distribution characteristics， a composite classification model learned on multiple isolated subdomains was proposed to further study the class imbalance problem. In the subdomains division stage， each class was described as ultrasmall spheres by improved Support Vector Data Description （SVDD） algorithm， then class domain was divided into intensive and sparse domains. Some instances were founded out from the boundaries of classes and composed of class overlapping domains. In the subdomains cleanup stage， according to sample availability parameters related to domain tightness， noise data was cleaned up by improved KNearest Neighbor （KNN）. After combining classifiers sequentially which were learned on isolated subdomains， the Composite Classification model （CCRD） was generated. The classification performance of CCRD is compared with those algorithms' which are divided into three groups of similar ones， MetaCost and SMOTE. CCRD could classify more positive instances than the top two groups and more negative instances than the last group， and the improvement doesn't affect the classification of the other class. The results indicate that the composite classification model learned on multiple isolated subdomains could classify instances more accurately and could be an effective method for imbalance class.

In the comparison with similar algorithms including SVM （Support Vector Machine）， KNN， C4.5 and MetaCost， CCRD can obviously improve the accuracy of positive instances without increasing mistake of negative instances； in the comparison with SMOTE （Synthetic Minority Oversampling TEchnique） sampling， CCRD can improve the misjudgement of negative instances without affecting the classification of the positive instances； in the experiments on five datasets， the classification performance of CCRD is also improved， especially in Haberman_sur. Experimental results indicate that the composite classification model learned on multiple isolated subdomains has excellent classification capability， and it is an effective method for inbalanced dataset.

英文關鍵詞Key words：

regional distribution of imbalanced class； Support Vector Data Description （SVDD）； sparse and overlapping domains； leaning classifiers on multiple isolated subdomains； Composite Classification model （CCRD）

0引言

不均衡數據集中，按類樣本出現概率的大與小定義多數類與少數類。少數類雖出現概率極小但往往又極其重要。如：通信電話中的騷擾電話、被診患者中的癌癥患者、網絡用戶行為中的攻擊行為、衛星圖片中的油井圖片等。抽樣是使不均衡數據集均衡化的常用方法，增加少數類樣本以減少類間偏斜的方法稱為over_sampling（向上采樣） [1]。文獻[2]提出SMOTE（Synthetic Minority Oversampling TEchnique）算法，在“近距離少數類樣本間仍為同類樣本”的假設基礎上生成人工少數類樣本；文獻[3]選用遺傳算法優化SMOTE參數，以得到適合應用數據集的取樣倍數；文獻[4]提出BorderlineSMOTE方法，將人工合成樣本限于少數類樣本的邊界處。減少多數類樣本以降低類間偏斜的方法稱為under_sampling（向下采樣）[5]。最早由Tomek提出的Tomek links方法按距離尋找分屬兩類的Tomek links對，并刪除其中的多數類樣本；

H. Alhammady和K. Ramamohanarao提出的EPRC（Emerging Patterns for Rareclass Classification）算法提供三個改進步驟來克服EP算法在少數類分類上的不足[6]。目前，不少研究將兩種抽樣相結合[7-8]，以優勢互補。

分析上述兩類抽樣方法，均以改變樣本分布為出發點。文獻[9]選用了10種分類方法對13個數據集進行分類性能分析，認為數據集的不均衡不僅體現在樣本數量的偏差上，類間重疊亦對分類性能產生影響。文獻[10]使用人工數據較系統地分析了類間重疊與類不均衡的關聯程度，并有望在實際數據集中進一步作關聯分析。文獻[11]嘗試通過K近鄰（KNearest Neighbor， KNN）方法來尋找類間重疊區域，距離查找法易受到“維災”效應影響，且當重疊子域較多時，該方法在有效發現各類邊界特征時性能較差。

本文在相關文獻的研究[9-12]基礎上，從數據集區域密疏分布特性著手，引入最小超球體進行類描述，界定出密集與稀疏域，按概率定義找出類邊界的重疊樣本，將樣本空間劃分為密集、重疊與稀疏三個子域。不同于傳統分類方式，本文將各子域隔離參與分類建模，分類模型按序組合構成復合分類器。實驗結果比較表明，本文設計的復合分類器的分類性能提升較明顯，總體較穩定。

1樣本空間密疏域隔離方法設計

類邊界區域中，存在與其他類極為相似的樣本，該類樣本往往會被誤分類，在覆蓋稀疏小樣本的分類學習中尤其明顯，類邊界會因此類樣本而發生偏移，誤分更為嚴重。

當不同類的樣本極其相似時，類重疊就會產生。選用概率法定義類重疊：樣本x均以大于0的概率落在至少兩個類的界定內，則樣本x位于重疊域O。即：x，x∈O，p（Cm|x）>0且p（Cn|x）>0。

圖1的（a）和（b）分別表示沒有重疊和有重疊的情形。重疊造成兩類邊界模糊，為分類帶來困難。若將類的邊界控制在樣本密集區，并與稀疏區域相隔離，類重疊可大大降低。

1）與單個分類算法的性能比較。

本文設計的分類算法是三類算法的擴展與組合，在同一數據集上，依次單個應用三類算法（支持向量機（Support Vector Machine， SVM）、KNN（K=5）、C4.5）和本文算法CCRD。實驗分類學習產生的統計結果見表3。

同一數據集的比較中，CCRD算法的TP值為最大，對正類樣本的正確分類數最多；TP與TN存在互約關系，CCRD的TN值雖非最大，但與最大值較為接近。CCRD算法修正了SVM在Haberman_sur上的“正類全部錯判”，同時對負類仍有很好的分類效果。從實驗結果得出：CCRD算法作為三類算法的擴展與組合，總體分類效果得到了較大提升，分類性能要優于單個算法的性能。

2）與單個分類算法在SMOTE集下的分類性能比較。

SMOTE算法通過生成少數類樣本來降低類間不均衡性，是從改變樣本分布角度來研究不均衡問題的。本文所提方法則充分分析了數據集分布子域特點，并依據該特點選用合理算法進行分類學習。與SMOTE相比，是同一問題的不同角度的設計。因此，設計實驗比較SMOTE集上的相近算法與本文算法的性能。

在同一數據集上，應用SMOTE（倍數為2）進行預處理，并依次單個應用三類算法（SVM、KNN（K=5）、C4.5）進行分類學習，統計結果見表4。

5結語

數據集的不均衡對分類算法性能影響較大，其不均衡性不僅體現在樣本數量懸殊上，也體現在樣本分布的密疏不均與類重疊上。本文從數據樣本分布的密疏程度出發，進行樣本區域分隔，根據不同域的分布特點，針對性選用不同分類方法進行學習，多個分類模型按序組合成復合分類器。從多組數據集的不同算法性能對比分析中得出，本文所用分類器在給定的評價性能指標中，總體提升明顯，且受數據集特性影響較小，總體性能較穩定。

本文所提方法中，擴展SVDD進行區域劃分時，實驗選擇了一種核函數，樣本去噪時的近鄰集計算是按固定K值進行的，并據此給出定值βK。方法實現中涉及的相關參數等在今后研究中，嘗試以優值選取方式進一步分析給定，以將本文方法推廣至多分類問題和大數據集的有效應用中。

參考文獻：

[1]

ABDI L， HASHEMI S. To combat multiclass imbalanced problems by means of oversampling and boosting techniques [J]. Knowledge and Data Engineering， IEEE Transactions on， 2015， 19（12）： 3369-3385.

ABDI L， HASHEMI S. To combat multiclass imbalanced problems by means of oversampling and boosting techniques [J]. Soft Computing， 2015， 19（12）： 3369-3385.

[2]

VERBIEST N， RAMENTOL E， CORNELIS C， et al. Preprocessing noisy imbalanced datasets using SMOTE enhanced with fuzzy rough prototype selection [J]. Applied Soft Computing， 2014， 22（5）： 511-517.

[3]

霍玉丹，谷瓊，蔡之華，等.基于遺傳算法改進的少數類樣本合成過采樣技術的非平衡數據集分類算法[J].計算機應用，2015，35（1）：121-124.（HUO Y D， GU Q， CAI Z H， et al. Classification method for imbalance based on genetic algorithm improved synthetic minority oversampling technique [J]. Journal of Computer Applications， 2015，35（1）：121-124.）

[4]

WANG K J， ADRIAN A M， CHEN K H， et al. A hybrid classifier combining borderlineSMOTE with AIRS algorithm for estimating brain metastasis from lung cancer： a case study in Taiwan [J]. Computer Methods and Programs in Biomedicine， 2015， 119（2）： 63-76.

[5]

YU H， NI J， ZHAO J. ACOSampling： an ant colony optimizationbased undersampling method for classifying imbalanced DNA microarray data [J]. Neurocomputing， 2013， 101（3）： 309-318.

[6]

GARCABORROTO M， MARTNEZTRINIDAD J F， CARRASCOOCHOA J A. A survey of emerging patterns for supervised classification [J]. Artificial Intelligence Review， 2014， 42（4）： 705-721.

[7]

陳睿，張亮，楊靜，等. 基于BSMOTE和逆轉欠抽樣的不均衡數據分類算法[J]. 計算機應用研究，2014，31（11）：3299-3303.（CHEN R， ZHANG L， YANG J， et al. Classification algorithm for imbalanced data sets based on combination of BSMOTE and inverse under sampling [J]. Application Research of Computers， 2014，31（11）：3299-3303.）

[8]

GALAR M， FERNNDEZ A， BARRENECHEA E， et al. A review on ensembles for the class imbalance problem： bagging， boosting， and hybridbased approaches [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part C： Applications and Reviews， 2012， 42（4）： 463-484.

[9]

GARCA V， SNCHEZ J S， MOLLINEDA R A. On the effectiveness of preprocessing methods when dealing with different levels of class imbalance [J]. KnowledgeBased Systems， 2012， 25（1）： 13-21.

[10]

ALEJO R， VALDOVINOS R M， GARCA V， et al. A hybrid method to face class overlap and class imbalance on neural networks and multiclass scenarios [J]. Pattern Recognition Letters， 2013， 34（4）： 380-388.

[11]

BECKMANN M， EBECKEN N F F， DE LIMA B S L P. A KNN undersampling approach for data balancing [J]. Journal of Intelligent Learning Systems and Applications， 2015， 7（4）： 104-116.

[12]

熊海濤，吳俊杰，劉洪甫，等.分類中的類重疊問題及其處理方法研究[J].管理科學學報，2013，16（4）：8-21.（XIONG H T， WU J J， LIU H P， et al. Towards classification with class overlapping [J]. Journal of Management Sciences in China， 2013，16（4）：8-21.）

[13]

KHAZAI S， SAFARI A， MOJARADI B， et al. Improving the SVDD approach to hyperspectral image classification [J]. IEEE Geoscience and Remote Sensing Letters， 2012， 9（4）： 594-598.

[14]

蔣盛益，苗邦，余雯.基于一趟聚類的不平衡數據下抽樣算法[J].小型微型計算機系統，2012，33（2）：232-236.（JIANG S Y， MIAO B， YU W. Undersampling method based on onepass clustering for imbalanced data distribution [J]. Journal of Chinese Computer Systems， 2012， 33（2）： 232-236.）

[15]

李雄飛，李軍，董元方，等.一種新的不平衡數據學習算法PCBoost [J]. 計算機學報，2012，35（2）：202-209.（LI X F， LI J， DONG Y F， et al. A new learning algorithm for imbalanced dataPCBoost [J]. Chinese Journal of Computers， 2012， 35（2）： 202-209.）

[16]

曹鵬，李博，栗偉，等.基于粒子群優化的不均衡數據學習[J].計算機應用，2013，33（3）：789-792.（CAO P， LI B， LI W， et al. Imbalanced data learning based on particle swarm optimization [J]. Journal of Computer Applications， 2013， 33（3）： 789-792.）