基于統(tǒng)計信息聚類邊界的不平衡數(shù)據(jù)分類方法

李 欣，俞衛(wèi)琴

(上海工程技術大學 數(shù)理與統(tǒng)計學院，上海 201620)

0 引 言

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

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

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

1 基于統(tǒng)計信息聚類邊界的不平衡數(shù)據(jù)處理

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

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

1.1 邊界集的識別

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

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

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

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

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

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

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

定義3對于任意自然數(shù)，一個對象p的k-dist值定義為點p和數(shù)據(jù)集中滿足下列條件的另一對象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定義一個數(shù)據(jù)對象p的邊界度bf(p)(boundary factor)為NEps(p)內所有k-dist值的方差

(1)

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

1.2 噪聲點的去除

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

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

Eps=EX+w*sqrt(DX)

(2)

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

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

圖1 數(shù)據(jù)集邊界檢測及采樣

1.3 非邊界集的處理

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

1.4 基于統(tǒng)計信息聚類邊界的不平衡數(shù)據(jù)算法流程

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

圖2 CBSM算法流程

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

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

輸出：平衡數(shù)據(jù)集

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

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

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

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

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

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

2 實驗結果及分析

2.1 評價指標

評估標準對于評估分類器的性能好壞方面發(fā)揮了關鍵作用。準確率在傳統(tǒng)的分類方法是常用的指標。然而在不平衡數(shù)據(jù)分類中，該指標發(fā)揮重要作用不明顯。一個非平衡數(shù)據(jù)分類算法的評價指標情況可通過混淆矩陣結合F-value和G-mean來表示?；煜仃囈姳?。

表1 混淆矩陣

表1中，Tp是實際為多數(shù)類并預測為多數(shù)類的個數(shù)，F(xiàn)n是實際為多數(shù)類預測為少數(shù)類的個數(shù)，F(xiàn)p是實際為少數(shù)類預測為多數(shù)類的個數(shù)，Tn是實際為少數(shù)類預測為少數(shù)類的個數(shù)。

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

(3)

(4)

(5)

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

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

(6)

(7)

其中，Naccrance為真負率。

2.2 數(shù)據(jù)集描述

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

表2 實驗數(shù)據(jù)集

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

2.3 實驗結果分析

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

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

表3 少數(shù)類準確率

表4 多數(shù)類準確率

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

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

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

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

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

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

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

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

3 結束語

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