不平衡數據加權邊界點集成欠采樣方法

何云斌，冷 欣，萬 靜

(哈爾濱理工大學 計算機科學與技術學院，黑龍江 哈爾濱 150000)

近年來，隨著人工智能和大數據的發(fā)展，不平衡數據已經廣泛出現在人們的現實生活中，如醫(yī)學領域[1]、信用卡欺詐檢測[2]、文本分類[3-4]、垃圾郵件的檢測[5]以及故障檢測[6]等領域。在以上領域少數類數據集往往發(fā)揮更重要的作用。但是人們一直忽略少數類信息所特有的價值，過多地關注多數類信息，而且被錯分的樣本往往是少數類數據，因此提高少數類的識別率是非常有必要的。

文獻[7]提出基于聚類的欠采樣方法，將多數類中的簇數設置為等于少數類中的數據點個數，提出兩種策略進行聚類：第1種是使用聚類中心來表示多數類，第2種是使用每個聚類中心的最近鄰來表示多數類。研究了5到10個聚類中心的添加或刪除對多數類數據性能的影響。文獻[8]提出一種基于樣本權重的不平衡數據欠抽樣方法(KAcBag)，通過bagging成員分類器得到若干決策樹子分類器，最后進行加權投票生成預測模型。該算法所選數據具有較強的代表性，可以有效提高少數類的分類性能，但是在聚類時需要通過實驗來獲得聚類次數、類簇的個數以及簇減少的步長等參數，耗費時間較多。文獻[9]提出一種基于距離的支持向量機加權欠采樣方法，是一種改進的WU-支持向量機算法，將大多數樣本劃分為一些子區(qū)域(SRS)，并根據它們到超平面的歐幾里得距離分配不同的權重。文獻[10]通過改進懲罰函數，有效處理含有噪聲點的非平衡數據集，并采用網格搜索算法來確定各個支持向量機模型中參數的優(yōu)化取值。

在欠采樣方法中，現有的對多數類數據進行處理的方法大多都是忽略邊界點的計算，但是邊界點中往往含有有用的信息，所以對邊界點進行刪除對不平衡數據的預處理是有影響的。為了有效解決多數類樣本集中含有的邊界點問題，筆者通過研究多數類樣本的分布情況，提出一種基于邊界點加權的不平衡數據集成欠采樣方法。首先，對多數類數據進行聚類；其次，對邊界點進行加權，約簡數據集；最后，使用AdaBoost成員分類器對平衡數據集進行訓練并通過加權投票生成預測模型。

1 基于聚類的欠采樣方法

筆者提出的基于聚類的集成欠采樣方法主要分為4部分，即對多數類數據進行聚類、邊界點加權、刪除低密度數據簇和數據加權集成分類。

1.1 多數類數據集的聚類

記多數類數據集N={d1，d2，…，dn}，少數類數據集M={s1，s2，…，sm}，邊界點集S={b1，b2，…，bt}。首先以少數類數據集中的樣本數作為初始聚類中心個數，對多數類數據采用k均值聚類方法進行聚類，形成初始的聚類簇。

不平衡數據的聚類過程，如圖1所示。

從圖1(a)可以看出，不平衡數據集中含有多數類數據和少數類數據。圖1(b)中含有的少數類數據個數是7個，運用k均值聚類[11]對多數類數據進行聚類，形成的初始聚類中心的個數為7個，所得到的初始聚類簇為7個。

基于以上的理論分析，算法的主要過程及計算步驟為：首先以少數類數據集中的個數m作為多數類數據集初始聚類中心的個數，計算每個樣本到所有聚類中心的歐氏距離，每個樣本di選擇最近的聚類中心oj，并將該樣本加入到與其最近的聚類中心所在的聚類簇Wj中，把所有樣本放在不同的集合后，得出一共有m個集合。然后重新計算每個集合中所有對象的平均值，作為新的簇中心。計算方法是計算該簇中所有對象的平均值，也就是分別對所有對象的各個維度的值求平均值，從而得到簇的中心點。例如：一個簇包括以下3個數據對象{(1，3，3)，(2，6，4)，(3，3，5)}，則這個簇的中心點就是((1+2+3)/3，(3+6+3)/3，(3+4+5)/3)=(2，4，4)。不斷重復上述過程，直到準則函數收斂，也就是簇中心不再發(fā)生明顯的變化。

算法1多數類數據集聚類算法(Clustering_MCD(N，M))。

輸入：多數類數據集N={d1，d2，…，dn}，少數類數據集M={s1，s2，…，sm}。

輸出：聚類結果W={W1，W2，…，Wm}。

①k←count num(M)；/*少數類數據集的樣本個數*/

② 在數據集N的樣本中，隨機選擇m個樣本作為初始聚類中心，m個初始聚類中心記為O={o1，o2，…，om}，并放入相應的聚類結果Wj中；

③ fori=1 tondo

④ forj=1 tomdo

⑤ calculate dist(di，oj)； /*計算每個樣本到所有聚類中心的歐氏距離*/

⑥ end for；

⑦ select_center(oj)；/*每個樣本dj選擇最近的聚類中心oj*/

⑧ join_center(Wj)；/*加入該聚類中心所在的聚類簇Wj中*/

⑨ end for；

⑩ forj=1 tomdo

1.2 邊界點加權

在圖1所得到的初始聚類簇中，將聚類邊界點提取出來，然后對提取出的邊界點進行加權，形成新的多數類樣本集。

1.2.1 提取邊界點

薛麗香等[12]提出的算法通過引入變異系數刻畫數據集的分布特征，進而提取出聚類邊界點。該方法可以在含有噪聲的數據集上將邊界點與噪聲點以及孤立點分離開，有效檢測出聚類邊界點。通過引入變異系數將邊界點輸出。主要利用密度的標準差與密度的平均值來刻畫數據的分布特征。如果一個數據對象的變異系數越大，那么就說明該點附近點的密度的分布相對離散，密度變化較大，數據分布不均勻，即該點附近既有高密度的區(qū)域，也有低密度的區(qū)域，該點成為邊界點的可能性就越大。

定義1數據對象的邊界因子。給定一個數據對象pi和pi的局部密度與整個數據集中所有對象局部密度的平均值的比值作為數據對象pi的邊界因子，記為B。計算公式如下：

(1)

如果一個邊界點的局部密度越大，那么它的邊界因子也越大；相反，如果一個邊界點的局部密度越小，那么它的邊界因子就越小。

給定數據集D={p1，p2，…，pn}，pi∈D，1≤i≤n，其中在數據集D中包含n個數據對象，在這里選取任意一個數據對象pi作為代表點進行相關運算。假設pi和pj是數據集D中的對象，對象pi和pj之間的距離記作d(pi，pj)。

定義2數據對象pi的k距離[13]。對任意的正整數k和數據集D，數據對象pi的k距離記作k_dist(pi)，并定義其為數據對象pi與數據對象o∈D之間的距離d(pi，o)。且滿足：

(1) 至少有k個數據對象qi∈D-{pi}，使得d(pi，qi)≤d(pi，o)，i=1，2，…，k；

(2) 至多有k-1個數據對象qi∈D-{pi}，使得d(p，qi)

定義3數據對象pi的局部密度[12]，定義為數據對象pi與其k距離鄰居距離和的平均值的倒數：

(2)

其中，d(pi，qi)是數據對象pi與其k距離鄰居之間的距離。

(3)

1.2.2 邊界點加權算法

本節(jié)提出的邊界點加權算法首先是引用文獻[14]識別邊界點的過程，對這一過程中所得到的邊界點集進行操作；其次給出權重大小，讓邊界點集上的每一個數據點和權重相乘，得到加權后的邊界點集。因此，使得邊界點中具有價值信息的點不被刪除，提高了分類結果的準確性。

定義4邊界點[14]。根據每個對象的反向k近鄰值按從小到大的順序排列整個數據集，并把前n個對象作為邊界點。

定義5權重[15]。對任意的數據集D，數據點pi的權重ωpi定義為

(4)

定義6加權邊界點。數據集D中邊界點pi的加權邊界點ω(pi)，定義為

ω(pi)=B(pi)ωpi，

(5)

其中，ω(pi)記錄的是每個邊界點pi與權重ω的乘積。由加權邊界點ω(pi)組成的集合叫作加權邊界點集合。根據邊界點和權重的定義可得，靠近非邊界點集的邊界點會具有較高的權重，而這類點是具有價值信息的邊界點的概率更大。因此，結合邊界點和權重，使得算法在更好地保留邊界點的同時，能夠盡可能地提高發(fā)現邊界點中有價值的點的概率，再次提高分類的準確性。

算法2邊界點加權算法(BDP_W(N，M))。

輸入：多數類數據集N={d1，d2，…，dn}，少數類數據集M={s1，s2，…，sm}。

輸出：加權邊界點集合S′，加權后的多數類數據集N′。

①S′←?；/*初始化加權邊界點為空集*/

②W←Clustering_MCD(M，N)；/*調用算法1*/

③S←BAND(W)；/*調用BAND算法生成邊界點集*/

④ fori=1 totdo

⑤ calculateB(pi)；/*公式(1)*/

⑥ calculateωpi；/*公式(4)*/

⑦ calculateω(pi)；/*公式(5)*/

⑧ end for；

⑨S′←ω(pi)；/*形成加權邊界點集合*/

⑩N′←S′∪N-S；/*形成加權后的多數類樣本集*/

1.3 約簡數據集

給定樣本集N′=C1∪C2∪…∪Cn，Ci(i=1，2，…，n)代表一個簇，Ci={X1i，X2i，…，Xmi}，其中Xki(k=1，2，…，m)是Ci中的一個樣本。

定義7簇密度。一個簇Ci的簇密度為樣本集N′中簇Ci中數據對象的個數，記為T(Ci)。

定義8平均密度。樣本集N′的平均密度計算公式為

(6)

基于以上理論分析，算法的主要過程和計算步驟如下。

算法3約簡數據集算法(RE_DS(N，M))。

輸入：多數類數據集N={d1，d2，…，dn}，少數類數據集M={s1，s2，…，sm}。

輸出：約簡后的多數類數據集和少數類數據集結合形成平衡的數據集Nall。

①N′，S′←BDP_W(N，M)；/*調用算法2*/

② fori=1 tondo

③ countT(Ci)；/*計算每個類簇的數據對象的個數*/

④ end for

⑤ Quick_Sort(T(Ci))；/*降序排序*/

⑧Nnew←Ci；/*Ci為高密度類簇*/

⑨ else

⑩ deleteCi；/*刪除Ci*/

2 基于聚類的加權邊界點集成分類方法

基于聚類的加權邊界點的欠采樣過程中利用聚類方法在保留多數類數據特征的基礎上使得不平衡數據集變成平衡數據集，集成分類則是基于集成學習的方法在已經均衡的數據集上進行分類學習，最終輸出強分類器的過程。分類模型如圖2所示。

圖2 基于欠采樣的不平衡數據集成分類模型

不平衡數據集經過算法1、算法2以及算法3處理后，得到平衡數據集，對平衡數據集使用AdaBoost算法進行訓練，得出分類模型。

經過算法1～3后形成平衡的數據集，在數據訓練階段的每次迭代過程中權重會不斷進行更新。將D1(i)初始化，得

(7)

其中，n表示平衡數據集中樣本的個數。經過t次迭代訓練結束時，得到子分類器ht(x)，子分類器ht(x)形成后的權值更新記為Dt+1(i)[16]，則有

(8)

其中，Nall為t次迭代后的訓練樣本集。Zt[16]為歸一化常量，可表示為

(9)

第t次迭代所得子分類器的訓練誤差記為et[16]，可表示為

(10)

由式(10)訓練誤差et，得到子分類器參數記為αt[16]，可表示為

(11)

算法4加權邊界點集成分類算法(CWBUSC(Nall))。

輸入：平衡數據集Nall，迭代次數T，子分類器ht(x)；

① 初始化樣本權重D1(i)； /*公式(7)*/

② fort=1 toTdo

③ calculateet； /*公式(10)*/

④ ifet>0.5 oret=0

⑤ break；

⑥ else

⑦ calculateαt； /*公式(11)，計算子分類器參數*/

⑧ updateDt； /*更新樣本權重*/

⑨ end if；

⑩ end for；

通過CWBUSC算法獲得了新的分類模型，使得在不平衡數據集的處理過程中獲得更加精確的結果。

3 實 驗

3.1 數據集

實驗選取標準的UCI數據庫中的實驗數據，詳細信息如表1所示。

表1 實驗數據集參數統(tǒng)計表

3.2 實驗結果及分析

為驗證筆者所提出的樣本約簡算法的優(yōu)勢與降低數據集不平衡率的有效性，首先采用UCI數據集進行驗證，將CWBUSC算法與C 4.5算法、SMOTE-Boost算法、PC-Boost算法、Ada-Boost算法進行對比，比較約簡樣本的分布情況。

對上面的5個算法進行50次十折交叉檢驗，并且統(tǒng)計每次實驗的結果，求出平均值；對這幾種算法的平均值進行比較，得出結果，如表2所示。

表2 算法評測有效性對比Fmeasure指標均值

從表2的Fmeasure值可以看出，CWBUSC算法除了在Letter數據集稍微低于SMOTE-Boost算法和PC-Boost算法之外，在其他6個數據集上均有最佳表現。比較各種算法在7組UCI數據集上的平均值，CWBUSC算法相比其余4個算法的Fmeasure值都高，說明筆者所提方法在少數類分類性能方面有較大的提升。

表3 算法評測有效性對比Gmean指標均值

從表3的Gmean值可以看出，CWBUSC算法在Letter數據集上稍遜于SMOTE-Boost算法和PC-Boost算法，在7個數據集上的平均分類性能上，CWBUSC算法獲得了最優(yōu)精度。

(a) Ada-Boost算法

(b) SMOTE-Boost算法

(c) CWBUSC算法

(e) SMOTE-Boost算法

(f) CWBUSC算法

CWBUSC算法中經過邊界點加權再進行欠采樣后參與基分類器訓練的數據集樣本規(guī)模與初始數據集相比有所減少。為考察參與訓練的不同數據規(guī)模比例對算法分類性能的影響，選取Ada-Boost算法、SMOTE-Boost算法和CWBUSC算法3種方法，同時選擇以Letter數據集為例，在20%～100%范圍內以每次增加20%比例的數據參與基分類器，迭代10次，相關算法的Fmeasure、Gmean均值如圖3所示。從圖3可看出，隨著參與訓練數據集比例的增大，無論是Fmeasure還是Gmean值都有所上升，但是隨著數據比例的增大，相應的分類性能提升幅度有限。另外，在數據比例為20%至40% 時，3種算法相對應的Fmeasure值和Gmean值幾乎是線性提升，這說明過低比例的抽樣數據，由于損失太大的原始數據分布信息，會嚴重影響算法的分類性能。

4 結束語

為了有效解決邊界點直接被刪除的問題，筆者提出了基于邊界點加權的欠采樣方法，解決了不平衡數據的處理問題，將多數類樣本進行欠采樣，最后和少數類達到平衡的狀態(tài)。該算法的過程主要分為預處理和訓練兩個部分，預處理階段主要是將多數類數據進行約簡，得到約簡后的多數類數據集，與所有少數類數據集組成平衡的訓練集，然后融合集成學習的思想，通過分類器加權投票提高整體的分類性能。在UCI數據集上的實驗表明，筆者所提算法充分利用了邊界點中有用的信息，所得到的樣本較好地保持了多數類信息，有效縮小數據集規(guī)模，具有較高的執(zhí)行效率。該算法重點是對已有不平衡數據集進行約簡，后續(xù)將會重點研究動態(tài)不平衡數據集。