何云斌，冷 欣，萬 靜

(哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150000)

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

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

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

1 基于聚類的欠采樣方法

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

1.1 多數(shù)類數(shù)據(jù)集的聚類

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

不平衡數(shù)據(jù)的聚類過程，如圖1所示。

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

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

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

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

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

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

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

③ fori=1 tondo

④ forj=1 tomdo

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

⑥ end for；

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

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

⑨ end for；

⑩ forj=1 tomdo

1.2 邊界點(diǎn)加權(quán)

在圖1所得到的初始聚類簇中，將聚類邊界點(diǎn)提取出來，然后對提取出的邊界點(diǎn)進(jìn)行加權(quán)，形成新的多數(shù)類樣本集。

1.2.1 提取邊界點(diǎn)

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

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

(1)

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

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

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

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

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

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

(2)

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

(3)

1.2.2 邊界點(diǎn)加權(quán)算法

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

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

定義5權(quán)重[15]。對任意的數(shù)據(jù)集D，數(shù)據(jù)點(diǎn)pi的權(quán)重ωpi定義為

(4)

定義6加權(quán)邊界點(diǎn)。數(shù)據(jù)集D中邊界點(diǎn)pi的加權(quán)邊界點(diǎn)ω(pi)，定義為

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

(5)

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

算法2邊界點(diǎn)加權(quán)算法(BDP_W(N，M))。

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

輸出：加權(quán)邊界點(diǎn)集合S′，加權(quán)后的多數(shù)類數(shù)據(jù)集N′。

①S′←?；/*初始化加權(quán)邊界點(diǎn)為空集*/

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

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

④ fori=1 totdo

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

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

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

⑧ end for；

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

⑩N′←S′∪N-S；/*形成加權(quán)后的多數(shù)類樣本集*/

1.3 約簡數(shù)據(jù)集

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

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

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

(6)

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

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

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

輸出：約簡后的多數(shù)類數(shù)據(jù)集和少數(shù)類數(shù)據(jù)集結(jié)合形成平衡的數(shù)據(jù)集Nall。

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

② fori=1 tondo

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

④ end for

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

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

⑨ else

⑩ deleteCi；/*刪除Ci*/

2 基于聚類的加權(quán)邊界點(diǎn)集成分類方法

基于聚類的加權(quán)邊界點(diǎn)的欠采樣過程中利用聚類方法在保留多數(shù)類數(shù)據(jù)特征的基礎(chǔ)上使得不平衡數(shù)據(jù)集變成平衡數(shù)據(jù)集，集成分類則是基于集成學(xué)習(xí)的方法在已經(jīng)均衡的數(shù)據(jù)集上進(jìn)行分類學(xué)習(xí)，最終輸出強(qiáng)分類器的過程。分類模型如圖2所示。

圖2 基于欠采樣的不平衡數(shù)據(jù)集成分類模型

不平衡數(shù)據(jù)集經(jīng)過算法1、算法2以及算法3處理后，得到平衡數(shù)據(jù)集，對平衡數(shù)據(jù)集使用AdaBoost算法進(jìn)行訓(xùn)練，得出分類模型。

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

(7)

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

(8)

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

(9)

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

(10)

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

(11)

算法4加權(quán)邊界點(diǎn)集成分類算法(CWBUSC(Nall))。

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

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

② fort=1 toTdo

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

④ ifet>0.5 oret=0

⑤ break；

⑥ else

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

⑧ updateDt； /*更新樣本權(quán)重*/

⑨ end if；

⑩ end for；

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

3 實(shí) 驗(yàn)

3.1 數(shù)據(jù)集

實(shí)驗(yàn)選取標(biāo)準(zhǔn)的UCI數(shù)據(jù)庫中的實(shí)驗(yàn)數(shù)據(jù)，詳細(xì)信息如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集參數(shù)統(tǒng)計(jì)表

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

表2 算法評測有效性對比Fmeasure指標(biāo)均值

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

表3 算法評測有效性對比Gmean指標(biāo)均值

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

(a) Ada-Boost算法

(b) SMOTE-Boost算法

(c) CWBUSC算法

(e) SMOTE-Boost算法

(f) CWBUSC算法

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

4 結(jié)束語

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