基于統計信息聚類邊界的不平衡數據分類方法

李 欣，俞衛琴

(上海工程技術大學 數理與統計學院，上海 201620)

0 引 言

在不平衡的數據集中，數據集各個類別的樣本量極不均衡[1]。隨著社會發展，不平衡數據分類問題已經引起了研究界的廣泛關注[2]。典型的示例包括垃圾短信篩選、欺詐檢測和醫療預測[3-5]，其中將感興趣類別的實例錯誤分類的代價通常很高，是數據分析的重點問題。并且解決該問題的解決方案可以大致分為數據級和算法級方法。

算法級方法涉及創建新算法或修改現有算法。常用的算法主要有代價敏感學習、隨機森林算法和集成學習方法[6-8]等等。這類算法固定于預定的學習算法，并且需要對算法和成本函數有深入了解，較難加以改進。數據層面是對數據結構進行處理，對數據集進行分類和重組來最大可能增加準確率，在對類分布調整的常見數據分類算法有過采樣SMOTE(synthetic minority oversampling technique)[9]、欠采樣(under-sampling)[10]以及混合采樣[11]。在此基礎上，相關學者提出了一些算法的改進。曹璐等[12]提出了一種新的過采樣方法，該方法基于概率密度函數估計和Gibbs采樣，利用支持向量機生成不符合少數族類別分布的采樣點，以支持不平衡數據集分類。但由于過采樣方法增大了樣本容量，因此增加了算法的時間復雜度以及數據分類的過擬合問題。林偉超等[13]介紹了兩種欠采樣策略，其中在數據預處理步驟中使用了聚類技術。該方法驗證了使用少量集群中心及其最近鄰代表多數類數據樣本的適用性。馮宏偉等[14]提出了“變異系數”概念，在邊界集進行混合采樣形成平衡集。該方法相比其它不平衡處理方法有較高的性能，但同時在對邊界集進行處理時增加了少數類誤刪的可能性，造成重要信息的丟失。

為了在處理少數類數據集時盡量減少重要信息的丟失而影響分類算法的性能，本文提出一種統計信息聚類邊界的不平衡數據處理方法(CBSM)。

1 基于統計信息聚類邊界的不平衡數據處理

本文算法通過數據集邊界度[15]的大小來區分少數類與多數類，同時在少數類邊界集的k鄰域內采用SMOTE算法，在多數類的非邊界集中，通過基于距離的欠采樣方法[16]刪除遠離少數類的點集。本文通過對不平衡數據進行分類后，采用支持向量機(SVM)分類器進行實驗，最后將本算法(CBSM-SVM)與SMOTE欠采樣的SVM算法(SMOTE-SVM)以及Borderline-SMOTE的SVM算法(BS-SVM)進行性能比較。

將數據集的處理分為兩個部分進行。第一部分為處理不平衡數據的邊界集，第二部分對邊界集和非邊界集進行處理合成平衡集。在處理數據之前引入調整參數w來去除數據中的噪聲點，公式如式(2)所示，將數據集中k-dist值大于鄰域值的部分作為噪聲點進行刪除。這樣在得到平衡數集時，能最大程度保留數據的樣本特征，從而保障分類器的分類性能。

1.1 邊界集的識別

傳統算法為了得到平衡的數據集，如通過隨機減少多數類的樣本數目或者增加少數類的樣本數目使得樣本數目保持平衡，但該方法會使數據出現欠擬合或過擬合的現象，故會損失很多重要的信息。然而，不平衡數據集中的邊界樣本點往往包含價值重要的信息，少數類與多數類邊界的模糊會使類別錯分甚至錯刪樣本，分類效果大打折扣。因此，不能直接刪除數據集邊界的數據，為了更好地識別邊界集數據，采用分類方法將邊界清晰化，本文引用統計信息聚類邊界的方法。其中的定義如下。

定義1邊界點(boundary point)：邊界點p是指要求滿足以下2個條件的數據對象：

(1)p位于密集度較高的區域IR邊緣；

(2)p的附近存在一個區域IR′，存在Density(IR) <>Density(IR′)。

定義2 對象p的Eps鄰域NEps(p)定義為

NEps(p)={q∈D|distance(p,q)≤Eps}

式中：distance(p,q)為p與q數據點之間的距離。

定義3對于任意自然數，一個對象p的k-dist值定義為點p和數據集中滿足下列條件的另一對象O的距離：

(1)至少有k個對象o′∈D/{p}，distance(p,o′)≤distance(p,o)；

(2)至多存在k-1對象o′∈D/{p}，distance(p,o′)≤distance(p,o)。

對象p的k-dist值記為kdist(p)。

定義4定義一個數據對象p的邊界度bf(p)(boundary factor)為NEps(p)內所有k-dist值的方差

(1)

其中，|NEps(p)|表示數據點p在Eps鄰域中樣本點的個數。該公式通過數據點p中Eps鄰域內每個樣本點k-dist值的方差，來衡量數據點p周圍數據點的密度變化情況。邊界度bf(p)值越大，說明數據點p周圍密度變化較大，即數據點p周圍同時存在密度高也存在密度低的區域，則該點為邊界點的概率越大。

1.2 噪聲點的去除

數據集中噪聲點的存在較大的影響數據分類的準確率，因此如何辨別并去除噪聲點是需要研究的重點。

在本文算法中，領域有以下兩個作用：①在進行噪聲的篩選時作為邊界度計算的參數，來計算出每個樣本鄰域內的邊界度；②觀測鄰域附近樣本點的密度變化。但是，在沒有經過對數據的處理以及了解數據的含義的情況下，設置合適的鄰域值比較困難。在數學概念中，數學期望表示數據集中全體樣本值的均值，方差為衡量整個數據集中隨機變量與均值的偏離程度。數學期望和方差能夠較好顯示數據集中數據變量的數字特征以及統計信息。根據以上信息，可以設定

Eps=EX+w*sqrt(DX)

(2)

其中，EX是數據集中每個數據點k-dist值的數學期望，DX是數據集中每個數據點對象k-dist值的方差，w是調整參數，作用為調節鄰域的大小。該公式可以在一定程度上估計數據集中每個數據點的k-dist值的分布情況，降低了將該值作為固定參數直接輸入帶來的誤差。在去除噪聲點過程中，使整個數據集中每個樣本點的k-dist值大于鄰域值Eps的部份列為噪聲點，這說明噪聲點位置偏離數據集，未去除將會影響分類的性能。在該等式中，調整參數w為定值，來微調節鄰域的范圍使得分類性能取得最優，需要通過數據訓練人為算出結果。通過對大部分數據進行實驗，結果表示，在大部分數據集中，w的取值區間為[-0.1,1.5]，但對于數據分布比較均勻的數據集，w=0.1較為理想。

為驗證本文邊界算法去除噪聲點以及識別邊界的能力，采用人工數據進行實驗驗證。本文采用python3.7中的sklearn庫隨機生成500個樣本，樣本數據以(1.5,1.5)為中心，數據方差為0.4，隨機種子數為0。結果如圖1所示，圖1(a)為原始樣本，圖1(b)為通過CBSM算法檢測到的邊界點結果，使用的參數為k=6，w=0.1，從中可以看出，邊界檢測算法能夠有效識別出樣本數據的邊界點集。圖1(c)在圖1(b)的基礎上使用隨機SMOTE算法在邊界點內進行過采樣，圖1(d)在圖1(b)的基礎上在邊界點通過SMOTE算法對樣本點鄰域內的樣本進行過采樣。對比圖1(c)和圖1(d)，后者增加的樣本點更加集中，這增加了在分類過程中對邊界點集的關注。通過本文算法能夠較好的分辨數據集中的邊界點，從而將邊界集與非邊界集區分開來，對邊界集中有價值的點集進行SMOTE處理，從而較大地保留數據集中有價值的信息。

圖1 數據集邊界檢測及采樣

1.3 非邊界集的處理

對于少數類的非邊界集采用隨機過采樣。對多數類的非邊界集采用基于距離的過采樣方法，在少數類過采樣過程完后，再計算多數類非邊界集中的數據點與少數類中心點的歐氏距離，并進行升序排列，取出前n個數據。通過計算能夠增加少數類與多數類交界處的點集，這樣能夠保留有價值的信息，又能夠使少數類與多數類保持平衡。

1.4 基于統計信息聚類邊界的不平衡數據算法流程

基于邊界的統計信息聚類方法通過最大程度保持原數據集特征的基礎上，將數據集中的邊界集與非邊界集區分出來分別處理，得到平衡的數據集進行訓練，能夠提高數據分類的準確率，從而提高不平衡數據集的性能。

圖2 CBSM算法流程

本文所提算法的具體分析過程如下：

輸入：不平衡數據集s(i=1,2,…,T，T為樣本數量)，調整參數w，多數類前n個數的比率q

輸出：平衡數據集

步驟1fori=1 toT，計算數據集s中每個樣本點的邊界度bf(xi)值。

步驟1.1計算每個樣本點的值并加入到空集合Dist中，對Dist集合的值進行升序排序，并保留鄰域點集。

步驟1.2求出整體數據集數學期望EX以及方差DX，w取0.1得到鄰域值Eps，去除噪聲。對于數據集中的數據點樣本，如果該樣本點滿足該點以及其鄰域的樣本點的k-dist值都大于Eps值，則該樣本點為噪聲點從數據集中去除。

步驟1.3對于數據集中剩余的對象，計算其每個樣本xi的邊界度bf(xi)。

步驟2 根據邊界度對數據集中的對象降序排列，選取前n個對象歸為邊界集s1中，剩余歸為非邊界集s2中。

步驟5將Train_min_1與Train_max_2合成新的訓練集Train_data。

2 實驗結果及分析

2.1 評價指標

評估標準對于評估分類器的性能好壞方面發揮了關鍵作用。準確率在傳統的分類方法是常用的指標。然而在不平衡數據分類中，該指標發揮重要作用不明顯。一個非平衡數據分類算法的評價指標情況可通過混淆矩陣結合F-value和G-mean來表示。混淆矩陣見表1。

表1 混淆矩陣

表1中，Tp是實際為多數類并預測為多數類的個數，Fn是實際為多數類預測為少數類的個數，Fp是實際為少數類預測為多數類的個數，Tn是實際為少數類預測為少數類的個數。

(1)F-value主要針對多數類的分類精度進行評價。其公式為

(3)

(4)

(5)

其中，Rcall為查全率，Precision為查準率，β表示Rcall和Precision的相對重要性。一般在二分類問題中，β的值為1。Rcall和Precision的值較大時，才會整體增大F-value的值。

(2)G-mean值需要考慮少數類與多數類的召回率，是比較綜合的指標。其公式如下

(6)

(7)

其中，Naccrance為真負率。

2.2 數據集描述

本文數據集是從UCI機器學習庫中選擇5組不平衡數據，將數據集中的負類樣本(樣本數據較多)劃分為多數類，正類樣本(樣本數據較少)劃分為少數類，其數據特征見表2。類分布的不平衡度定義可參見文獻[17,18]。

表2 實驗數據集

其中，Ecoli數據集的第imU、pp類為少數類，其余類別為多數類。Wine quality數據集的第3、第4、第7以及第8類為少數類，第5和第6類為多數類。cmc數據集中第2類為少數類，第1、第3類為多數類。energy數據集中第4、第5類為少數類，其余類別為多數類。biodeg數據集中，第RB類為少數類，第NRB類為多數類。breast數據集中，第4類為少數類，第2類為多數類。

2.3 實驗結果分析

為了評估本文算法的性能，將本文算法(CBSM-SVM)與SMOTE過采樣的SVM算法(SMOTE-SVM)、Borderline-SMOTE的SVM算法(BS-SVM)進行對比。實驗環境在python3.7軟件下進行，為了防止在訓練數據過程中由于隨機結果導致的實驗誤差，對數據集采用五折交叉驗證，最后統計少數類與多數類準確率以及每組實驗數據的F-value和G-mean性能評測指標的平均值。

在表3和表4中，給出了不同數據集在3種不同算法下多數類與少數類的準確率數值。從表3中可以得出如下結論：本文算法對少數類的分類效果優于其它算法，大部分數據集在該算法下對少數類的準確率大于其它對比算法。主要原因在于本文算法加大對邊界處少數類的關注，增加邊界處少數類的點集，使得在識別少數類時降低了錯分的概率。同時在對多數類非邊界集中的處理保留了多數類中有價值的點集，相比較隨機欠采樣則提高了數據的分類性能。

表3 少數類準確率

表4 多數類準確率

從表4對多數類準確率的評估可以得出以下結論：在對數據集邊界進行分類處理后，本文算法CBSM-SVM在對多數類的準確率基本高于其它算法，雖然對于Ecoli和breast數據集上該算法對多數類的準確率不是最優，但該算法準確率與其它算法相比差距在0.007～0.014之間，差距非常小。說明本文算法在提高多數類準確率的基礎上也保證了少數類的分類性能。

在表5中，在以下6類數據集中，分別比較了每個數據庫中使用3種不同不平衡數據分類算法后評估的分類性能，并將每組數據集中的F-value和G-mean最大值加粗表示。

表5 不平衡數據集在3種算法的F-value 和G-mean性能比較

由表5可以看出，相比另外2類不平衡分類算法，本文算法在CBSM-SVM在6類不平衡數據集上的G-mean值大部分表現優秀，其中在Wine quality數據集中本文算法的G-mean值比SMOTE-SVM算法高出了23%。出現該情況的原因是本文算法將邊界集與非邊界集割分開，著重處理邊界區域的數據集，更大程度保留不平衡數據集中的重要信息。這樣能較好降低由邊界樣本點錯分而帶來的影響，同時對多數類樣本的處理采用基于距離的欠采樣算法刪除多余樣本點，較好地保留了有價值的信息

針對F-value，在energy數據集上，算法BS-SVM的值比本文算法高出了0.016，這是因為energy數據集的邊界點比較集中，而BS-SVM算法集中于處理少數類邊界中的危險樣本，對邊界復雜度大的數據集較有優勢，本文算法引入的邊界度概念仍需要不斷改進。但從整體上來看，CBSM-SVM將過采樣和欠采樣算法結合起來，重點研究邊界樣本信息的同時，保留有價值的點，刪除遠離邊界重要信息的無價值點集，因此，CBSM-SVM分類算法相比較于另外2種算法是較為有效的算法，且性能表現也較為優秀。

為了更加直觀表示不平衡數據集在3種不同算法之間的性能變化，將每類數據集的F-value和G-mean值在圖中表示出來，如圖3、圖4所示。其中，橫坐標表示本文涉及的3種算法，縱坐標表示不同的分類效果值，范圍是0～1。從該圖中可以看出，本文算法CBSM-SVM與其它對比算法相比有一定的提升。從本文結論可以看出，對數據集進行分類處理以及對不同的樣本進行不同的處理是有效的，并且在一定程度上有較強的適應性。

圖3 不同算法G-mean變化曲線

圖4 不同算法F-value變化曲線

3 結束語

本文針對不平衡數據分類問題，提出了基于統計信息聚類邊界的不平衡數據分類方法，首先去除數據集中的噪聲點，然后計算數據集中每個樣本的邊界度，通過判斷樣本點邊界度與領域值的大小區分出邊界集與非邊界集。邊界集中少數類的k鄰域內采用SMOTE算法來增加樣本點集，增大重要信息被識別的可能性，對非邊界集中的多數類采用基于距離的欠采樣算法進行篩選，從而得到平衡數據集。從實驗的結果得知，在一定程度上本文算法CBSM-SVM增加了數據集的分類效果。但存在以下問題：一方面，對少數類邊界進行SMOTE算法進行欠采樣，沒有考慮到少數類內部數據的分布情況；另一方面，在定義邊界度bf時選擇歐氏距離為定義方式，研究較少。后面的研究任務主要是基于本文工作，嘗試利用更多可能的邊界分類算法進行改進，使得不平衡數據集有更好的分類效果。