基于DPC聚類重采樣結合ELM的不平衡數據分類算法 *

董宏成，文志云,3，萬玉輝 ，晏飛揚

(1.重慶郵電大學通信與信息工程學院，重慶 400065；2.重慶郵電大學通信新技術應用研究中心，重慶 400065；3.重慶信科設計有限公司，重慶 401121)

1 引言

不平衡分類問題在醫(yī)學診斷[1]、機器故障檢測[2]、軟件缺陷預測[3]和計算機視覺[4]等領域得到了廣泛的應用。與類不平衡學習相關的問題是，標準方法通常將大多數正類樣本錯誤地歸類為負類樣本。對于以上應用來說，少數類樣本的檢測更加重要，因此如何更加準確地檢測出這類稀有樣本已經成為當前機器學習研究者面臨的挑戰(zhàn)之一[5]。

近年來，針對類不平衡學習問題涌現出了大量的研究，研究人員也給出了很多解決方法，這些方法概括起來可以分為3類：(1)改進訓練數據集的不平衡分布(數據層面上的方法)，例如采用上采樣方法、下釆樣方法和混合采樣等對原始數據集進行處理，目的是使類分布更加平衡；(2)改進經典算法(算法層面方法)：對當前比較成熟的分類器算法，采用優(yōu)化參數、對各類樣本賦予不同的錯分代價[6]、設計面向不平衡數據集的新算法等手段。例如，基于代價敏感的支持向量機[7]和極限學習機ELM(Extreme Learning Machine)[8 - 12];(3)結合數據層面和算法層面的方法：首先采用合適的采樣方法對數據集進行平衡處理得到多個平衡數據集，然后再訓練相應的分類器進行集成學習，例如DPBag(Density Peaks Bagging)算法[13]。

極限學習機ELM在分類問題上已經成為世界各國研究人員的研究熱點。研究人員大量的實踐表明，ELM對于不平衡數據分類問題具有較強的優(yōu)越性，其改進思想主要包括與采樣技術的結合和對自身算法的改進2方面。例如，Vong等人[14]將 ELM 與隨機過采樣技術ROS(Random Over Sampling)相結合提出了ROS-ELM算法，但是由于隨機過采樣是隨機復制少數類樣本使類分布達到平衡，容易導致過擬合。Sun 等人[15]則將SMOTE(Synthetic Minority Over-sampling TEchnique)算法[16]引入到 ELM 集成學習框架中,提出了SMOTE-ELM算法并用于企業(yè)生命周期預測。于化龍[17]將ELM與隨機欠采樣RUS(Random Under Sampling)相結合，和其它ELM算法對比雖然可提升少數類樣本識別精度但提升效果并不明顯。上述算法均采用了單一的采樣技術，未考慮到樣本的不平衡程度及樣本內部的分布情況，無法解決樣本噪聲及類內不平衡問題，導致噪聲被誤分為少數類樣本，并且適用場景過于局限，對不同平衡程度的數據集依然存在分類效果不明顯甚至效率低下的問題。

針對上述算法存在的問題，本文提出了一種基于密度峰值聚類DPC(Clustering by fast search and find of Density Peaks)的重采樣技術結合ELM的不平衡數據分類算法DPCR-ELM(imbalanced data classification algorithm based on DPC clustering Resampling combined with ELM)。

2 DPC聚類和ELM算法

2.1 DPC聚類

Alex等人[18]于2014年提出了一種新的聚類算法——密度峰值聚類DPC(Clustering by fast search and find of Density Peaks)算法。相比于其它聚類算法，該算法有以下優(yōu)勢：(1)可以發(fā)現任意形狀的簇并且可高效處理高維數據；(2)算法簡單，不需要迭代計算，耗時少；(3)能夠高效進行樣本分配和發(fā)現噪聲點，適用于大規(guī)模數據的聚類分析。對于每個樣本xi，由樣本的局部密度ρi和該點到更大局部密度的樣本的最小距離δi2個量來表示，相應的計算方法如式(1)～式(4)所示：

(1)

(2)

δi=minj:ρi<ρjdij

(3)

λi=ρiδi

(4)

其中,dij表示樣本xi與樣本xj之間的距離，dc為輸入的截斷距離，本文選取dij升序排序后的1%或2%的分位數作為dc的值，并且由式(1)和式(2)可以看出，樣本點xi的局部密度ρi表示以dc為半徑的圓內樣本的個數。ρi越小表示該樣本點周圍越稀疏，越有可能成為邊界點，ρi越大表示該樣本點周圍越密集，越靠近集群中心。λi為聚類中心選擇的一個衡量標準，λi越大，表示樣本xi的2個屬性值都很大，xi越有可能成為聚類中心點。

根據DPC算法的原理，δi值和ρi值能很好地反映樣本點在分布集群中所處的位置，其生成的決策圖可方便用戶去除噪聲樣本和選取聚類中心點，圖1和圖2分別展示了原始數據分布圖及其生成的決策圖。

Figure 1 Original data distribution圖1 原始的數據分布

Figure 2 ρ_δ decision diagram based on DPC圖2 基于DPC的ρ_δ決策圖

根據圖2所示決策圖來分析圖1可知，樣本26～28被視為噪聲點或離群點，因為它們都遠離大部分樣本，以dc為半徑的圓內樣本的個數只有一個。因此，本文定義樣本局部密度ρ=1的點為噪聲點或離群點，這樣的點在采樣之前會被去除。

2.2 極限學習機

ELM是一種廣義的單隱層前饋神經網絡，該網絡中所有的隱層節(jié)點參數都是隨機生成的，輸出權值采用批量最小二乘學習技術進行訓練。與傳統的人工神經網絡相比，ELM具有訓練誤差和輸出權的范數最小的特點。其次ELM的學習算法簡單有效，不需要在隱層中迭代調整，在學習速度極快的情況下也具有良好的泛化能力，已被廣泛應用于各種分類問題中。ELM基本原理簡述如下：

給定一組N個訓練數據D(xi,ti)，i=1,…,N，即輸入和期望輸出分別為xi=[xi1,xi2,…,xin]T∈Rn和ti=[ti1,ti2,…,tim]T∈Rm，其中n和m分別為特征維度和輸出層的維數。因此，隱層輸出矩陣為：

(5)

其中,wi和bi為隱層節(jié)點的輸入權重和隱層偏置，G為隱層的激活函數，L為隱層的節(jié)點數。

輸出權重β可通過求解式(6)所示的目標優(yōu)化函數得到：

(6)

其中,ξi是第i個訓練樣本的訓練誤差向量，C是正則化因子，‖β‖2是分離超平面的參數，‖ξi‖2是誤差平方和。H(xi)為輸入樣本xi的隱層輸出函數，ti為訓練xi的類別標記。求解以上目標函數可得隱層與輸出層之間的輸出權向量，β表示為:

(7)

其中，T為訓練樣本的目標矩陣。

進而得到ELM的決策輸出如式(8)所示：

(8)

其中,signh(x)為隱層激活函數，也叫做特征映射函數。由該式可以得到對應樣本xi的輸出向量f(xi)=[f1(xi),…,fm(xi)],進一步可以得出xi的預測標號label(xi)=argmaxfk(xi),k=1,…,m。由于本文主要研究的是二分類問題，所以m取值為2，具體的分類模型如圖3所示。

Figure 3 ELM classification model圖3 ELM的分類模型

3 本文提出的分類算法

3.1 算法流程

根據采樣技術與ELM分類算法相結合的思想，本文提出了基于DPC聚類采樣結合ELM的不平衡數據DPCR-ELM分類算法，該算法考慮了分類模型的效率問題，根據數據集不平衡程度進行相應的處理。算法流程如圖4所示。

Figure 4 Flow chart of DPCR-ELM algorithm圖4 DPCR-ELM的算法流程圖

該算法首先判斷不平衡數據集的不平衡比率，即R=Nmax/Nmin，其中Nmax和Nmin分別為多數類樣本和少數類樣本的數量，本文設置不平衡閾值為9(實驗所用公共數據集標準劃分)來判斷使用何種采樣方法。若R>9，表明數據集十分不平衡，少數類樣本相對于多數類樣本來說是很稀少的，如果采用經典的SMOTE過采樣方法生成(Nmax-Nmin)個少數類樣本會加大數據集的訓練量，增加分類器的時間復雜度，還會出現過度擬合現象。因此，本文通過采用DPC聚類算法對少數類樣本進行過采樣，并根據聚類后各個樣本的ρ值和β值選取少數類邊界(即稀疏域)樣本集，對選取的少數類簇邊界樣本集采用經典的SMOTE過采樣方法自適應地合成確定數目的少數類樣本。對于R≤9的不平衡數據集，其少數類樣本數量相對多數類樣本不再那么稀少，ELM分類算法足以識別出大部分少數類樣本，因此本文提出的算法只對多數類樣本進行欠采樣，去除一些冗余的樣本，選取更具代表性的多數類樣本。對于不平衡比率較大的數據集(R>9)來說，此類數據集因為減少了對少數類樣本過采樣的步驟，并且未對數據進行聚類，節(jié)省了算法的時間開銷。

3.2 DPCR-ELM分類算法

DPCR-ELM分類算法主要包括樣本平衡處理和ELM算法分類2部分。在樣本平衡處理部分，本文受DPC聚類原理的啟發(fā)，提出了一種能夠有效平衡2類樣本的重采樣方法。

樣本平衡處理部分主要包括多數類樣本處理和少數類樣本處理，處理過程分別如算法1和算法2所示，其中算法2借鑒了文獻[19]的采樣思想，并對其進行了改進，因為文獻 [19]的算法需要對少數類樣本進行聚類，復雜度會很高，還會破壞原始樣本的類分布，因此本文根據DPC聚類的原理尋找少數類集群邊界樣本，不需要復雜的聚類；然后在邊界樣本周圍合成更多的樣本，解決類內不平衡問題，保持少數類樣本原始分布的同時提高ELM分類對邊界區(qū)域樣本的識別度。

算法1多數類樣本集的欠采樣

輸入:多數類樣本集Smax，欠采樣系數α。

輸出:采用后的多數類樣本集S′max。

步驟1應用DPC聚類的原理計算每個多數類樣本的ρ、δ和λ值。

步驟2去除離群點和噪聲點：

選取局部密度ρi=1的點為離群點或噪聲點，因為ρi=1，表示該點與所有點之間的距離大于截斷距離dc，遠離了所有樣本。

步驟3計算樣本權重：根據式(4)計算剩余樣本的λi值作為采樣權重并進行降序排列。

步驟4根據權重進行采樣系數為α的樣本采樣得到采樣后的多數類樣本集S′max。

算法2少數類樣本集的過采樣

輸入:少數類樣本集Smin，過采樣系數β。

輸出:少數類過采樣樣本集S′min。

步驟1根據式(1)～式(3)計算每個樣本點xi的局部密度ρi以及xi到具有更大局部密度的點的最小距離δi。

步驟2去除ρi=1的樣本，即噪聲點或離群點。

步驟3根據式(9)計算每個樣本點xi的采樣權重wi：

(9)

其中,Nmin為去除噪聲后少數類樣本的數量，從式(9)中可以發(fā)現，若樣本的ρi值越小，即周圍越稀疏，越有可能為邊界樣本，其采樣權重越大，樣本的ρi值越大，即周圍越密集，越靠近中心點，其采樣權重越小。

步驟4計算要合成的樣本數目：

N=(N′max-Nmin)×β

(10)

其中，N′max為算法1處理過后的多數類樣本數量，β為取值在0～1的過采樣系數。當β=1時，表示過采樣后的正負類樣本絕對平衡。

步驟5計算每個樣本需要合成的樣本數：

Ni=N×wi

(11)

步驟6對簇邊界樣本xi進行SMOTE采樣合成對應的Ni個樣本，合成樣本的計算方式如式(12)所示：

x′i=xi+rand(0,1)×(xi-s)

(12)

其中，xi為進行采樣的邊界樣本，s為xi的一個鄰近樣本，可根據xi的鄰近距離δi來隨機選擇，x′i為合成的樣本。合成的樣本加入到樣本集Snew中。

步驟7生成少數類過采樣集S′min：S′min=Smin+Snew。

算法1可以有效去除噪聲和異常值，其次利用樣本的λi值作為抽樣權值，方便了代表性樣本的選擇，因為樣本類簇邊界點的ρ值比簇中心周圍點的ρ值小，δ值比簇中心周圍點的δ值大，簇中心周圍點的情況則剛好與之相反，通過對λ值降序采樣可確保簇中心點被選取的情況下還可以隨機選取到邊界點以及簇中心周邊點，保留了原始數據的分布特性。算法2考慮了類內樣本不平衡及噪聲的影響，使用式(9)計算過采樣的權重不影響原始的類分布同時還保證了邊界樣本具有更大的過采樣權重，因為邊界樣本更容易被錯誤分類。其次，采用SMOTE算法避免了合成重疊樣本，保證了采樣的合理性。

算法3DPCR-ELM分類算法

輸入:不平衡數據集S，測試數據集V，欠采樣率α，過采樣率β。

輸出:重新采樣數據集S′，ELM分類器的預測目標。

步驟1將不平衡數據集S劃分為少數類樣本集Smin和多數類樣本集Smax，確定樣本不平衡比率R。

步驟2利用算法1對多數類樣本集Smax進行處理，得到數據集S′max。

如果R> 9繼續(xù)執(zhí)行以下步驟，否則轉到步驟4。

步驟3利用算法2對少數類樣本集Smin進行處理，得到數據集S′min。

步驟4合成重采樣平衡數據集S′:

(13)

步驟5訓練ELM分類模型:

(1)將平衡數據集S′輸入圖3所示的ELM分類模型進行訓練。

2)利用測試數據集V對ELM分類器進行測試，預測其分類準確率和少數類樣本識別率。

4 實驗與結果分析

4.1 實驗評價指標

傳統分類器采用的分類準則是整體分類準確率和錯誤率[20]，但是這些分類準則不適用不平衡分類問題。二分類的分類性能評價標準通常建立在表1所示的混淆矩陣基礎上，由表1中4個量可以表示幾種常用的分類性能指標，計算方式如式(14)～式(17)所示：

(14)

(15)

(16)

(17)

其中,F-Measure是查準率Precision和查全率Recall的調和平均，當兩者大小相當時F-Measure較大，G-mean指標為正精度和負精度的幾何平均，用于評估感應偏差的程度，較大的G-mean值表明分類器對正負類的分類效果較好。為了更加全面評價本文算法的分類性能，本文選用F-Measure和G-mean作為實驗結果的評價指標。

Table 1 Confusion matrix of binary classification problem

4.2 實驗設置

本文實驗的硬件環(huán)境：Intel(R) Core (TM) i5-6200U CPU@2.40 GHz,內存為8 GB，Windows 10 64位操作系統以及Matlab2018編譯環(huán)境。

本文選用KEEL數據庫中的8個二分類不平衡數據集來進行實驗對比和性能測試，選取規(guī)則盡可能考慮了樣本數量和不平衡樣本比率的多樣性，以驗證本文算法在不同平衡程度數據集上的分類適用性。具體數據集信息如表2所示。

Table 2 Data sets details

為了有效評價本文所提DPCR-ELM分類算法的分類性能，實驗將其與ELM、ROS-ELM、RUS-ELM和SMOTE-ELM分類算法進行比較。另外，本文將平衡處理后的數據集進行10倍交叉驗證，實驗結果取10次平均值以保證實驗結果的公平性。對于實驗參數的設定，ELM均使用Sigmoid 函數作為隱層節(jié)點激活函數，隱層節(jié)點數L取值為訓練樣本的個數。本文所采用的過采樣率和欠采樣率均設為0.8，以保證處理樣本后的正負樣本相對平衡，SMOTE算法的K近鄰個數設為5，DPC聚類截斷距離dc的選取至關重要，將其設置為最常用的前dij升序排序后的前1%或2%的分位數。

4.3 實驗結果及分析

本文進行了大量的實驗，得出了分類結果，表3和表4分別展示了5種算法在8個數據集上的F-Measure值和G-Mean值，表中的值越大表示算法的分類效果越好(最大值使用粗體字表示)，能識別出更多的少數類樣本。為了更加清楚地展示本文所提算法的分類效果，展示算法的綜合性能，圖5給出了5種算法在8個數據集上的F-Measure和G-Mean平均值的折線圖。

Table 3 F-Measure values of DPCR-ELM algorithm and other algorithms

由表3可以看出，對于大多數數據集，除數據集vehicle0和ecoli3之外，DPCR-ELM算法的F-Measure值均優(yōu)于其他算法的，在數據集vehicle0和ecoli3上，SMOTE-ELM算法的性能優(yōu)于本文算法的性能，這是由于樣本的分布相對均衡，本文算法在對多數類樣本處理時選擇的欠采樣率過低導致小部分代表性樣本被丟棄所引起的。對于其他數據集，特別是對于不平衡程度較高的數據集，本文所提算法具有最高的F-Measure值，提升效果最為明顯，其中，在數據集yeast5上提升最高，相比于ELM算法和次優(yōu)的SMOTE-ELM算法，F-Measure值分別提升了15.09%和2.55%，充分說明了本文算法在采樣過程中使用DPC聚類進行采樣的合理性。

Table 4 G-Mean values of DPCR-ELM algorithm and other algorithms

Figure 5 Average G-Mean and F-Measure values of different algorithms on 8 data sets圖5 不同算法在8個數據集上的平均G-Mean值和F-Measure值

由表4可以看出，除數據集abalone9-18之外，DPCR-ELM算法的G-mean值均優(yōu)于其他算法的。其次，由圖5可以看出，本文算法在8個數據集上的分類平均值(F-Measure和G-Mean)均大于其他算法的，這是因為其它算法在采樣過程中未考慮到樣本的類內不平衡以及多數類樣本中噪聲的影響，導致合成的少數類樣本不合理以及噪聲被ELM錯誤分類，本文提出的采樣方法有效解決了這2個問題，所提算法確實可以提升少數類樣本的分類精度以及具有較好的適用性。從圖5還可以看出，未對數據集進行平衡處理的ELM算法的F-Measure平均值和G-Mean平均值均低于其他算法的，驗證了ELM結合采樣技術這一思想的合理性。

本文提出的采樣方法涉及到欠采樣率和過采樣率2個參數，并且提出的DPCR-ELM算法也是根據不平衡比率來進行采樣的，因此為了驗證采樣率對本文算法的影響，選取了數據量較大且不平衡比率小于9的vehicle0數據集和不平衡比率大于9的winequality-red4數據集進行實驗。采樣率的選取為[0.5,1]。對于不平衡比率大于9的winequality-red-4數據集，合成的少數類樣本數量根據欠采樣后的樣本數量來確定，2個采樣系數有著必然的聯系。因此為了保證處理后的正負樣本相對平衡，將2個值設為同樣大小來討論采樣率對算法的影響。圖6和圖7分別給出了不同采樣率在vehicle0數據集和winequality-red-4數據集上的F-Measure值和G-Mean值。

Figure 6 F-Measure and G-Mean values of different sampling rates on vehicle0 data set圖6 不同采樣率下在vehicle0數據集上的G-Mean值和F-Measure值

Figure 7 F-Measure and G-Mean values of different sampling rates on winequality-red4 data set圖7 不同采樣率下在winequality-red-4數據集上的G-Mean值和F-Measure值

從圖6和圖7可以看出，當采樣率取0.8時，ELM的分類效果最好，其次，當采樣率小于0.7或大于0.8時，F-Measure值和G-Mean值有所下降，其原因為當采樣率較小時，會導致多數類樣本的重要信息丟失和少數類合成樣本不足，使ELM得不到充分的訓練，當采樣率過大時，會導致多數類噪聲無法去除以及少數類樣本出現過擬合的現象。因此，選擇合適的采樣率，DPCR-ELM分類算法的F-Measure值和G-Mean值才會有所提升。其次，由最佳采樣率可知，本文改進的重采樣方式確實能夠有效去除多數類的冗余樣本，并且合成的少數樣本數量并非絕對的，減少了訓練樣本的數量，能夠有效提升ELM分類算法的效率。因此，對于數據量較大場景，本文提出的DPCR-ELM算法分類效果會更佳。

5 結束語

類別不平衡是分類問題中最重要的數據挑戰(zhàn)之一。為了解決少數類樣本的分類精度不高的問題，本文提出并評估了一種基于DPC聚類的重采樣結合ELM的不平衡數據分類算法。根據數據集不平衡程度來選擇多數類代表性樣本和創(chuàng)建屬于少數類的合成樣本，在對多數類樣本選取時考慮了噪聲的影響，有效解決了噪聲誤判的問題，在對少數類樣本合成時考慮了類內不平衡的影響，根據聚類后找到每個集群的邊界樣本進行合成，解決了合成樣本分布不均的問題。其次，利用ELM算法在平衡數據集上的分類優(yōu)勢，提升了分類效率。利用KEEL數據庫中的不平衡數據集對算法進行了評估，實驗結果表明了本文算法的有效性和適用性。由于本文算法只是針對二分類問題進行討論，未來的工作將對多分類問題進一步展開研究，以便更加有效適應實際生活中的不平衡數據多分類問題。