張振蓮，魯淑霞，2，翟俊海，2

1(河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院,河北 保定 071002) 2(河北大學(xué) 河北省機(jī)器學(xué)習(xí)與計(jì)算智能重點(diǎn)實(shí)驗(yàn)室，河北 保定 071002)

1 引 言

類(lèi)別非平衡是機(jī)器學(xué)習(xí)領(lǐng)域一個(gè)非?；钴S的研究領(lǐng)域.處理類(lèi)別非平衡的方法主要可分為兩類(lèi)：數(shù)據(jù)級(jí)方法和算法級(jí)方法.在算法層面上，通過(guò)創(chuàng)建新的學(xué)習(xí)算法或修改現(xiàn)有算法來(lái)解決這個(gè)問(wèn)題.算法級(jí)解決方案的優(yōu)點(diǎn)是直接將用戶(hù)的偏好合并到模型中[1].然而，學(xué)習(xí)算法需要預(yù)先確定，一旦實(shí)現(xiàn)就不能改變.我們重點(diǎn)集中在數(shù)據(jù)級(jí)解決方案上.

數(shù)據(jù)層面上最常用的方法有欠采樣[2]、過(guò)采樣[3]，欠采樣方法可能會(huì)刪除一些有用的數(shù)據(jù)，而過(guò)采樣方法有可能會(huì)引起數(shù)據(jù)的過(guò)度擬合.現(xiàn)有文獻(xiàn)表明，類(lèi)重疊[4]對(duì)學(xué)習(xí)算法的性能有很高的負(fù)面影響.基于類(lèi)重疊的方法主要解決非平衡數(shù)據(jù)分類(lèi)中的類(lèi)重疊問(wèn)題.處理類(lèi)重疊的方法主要有整個(gè)重疊區(qū)域的方法、邊界附近重疊樣例的方法.采用的技術(shù)主要有：聚類(lèi)、近鄰搜素、噪聲去除、集成、區(qū)域分割等.

基于重疊的欠采樣(OBU)[5]是處理整個(gè)重疊區(qū)域的方法，該方法旨在通過(guò)消除重疊區(qū)域中的所有多數(shù)類(lèi)樣例來(lái)最大化少數(shù)類(lèi)實(shí)例的可見(jiàn)性，出現(xiàn)了過(guò)多的消除；DBMUTE[6]是另一種基于重疊的欠采樣方法，即消除少數(shù)類(lèi)子聚類(lèi)附近的多數(shù)類(lèi)樣例，強(qiáng)調(diào)類(lèi)重疊問(wèn)題的變異能獲得更好的分類(lèi)結(jié)果；自適應(yīng)合成采樣(ADASYN)[7]，通過(guò)在重疊區(qū)域選擇性地過(guò)采樣來(lái)增強(qiáng)少數(shù)類(lèi)的存在，缺點(diǎn)是與多數(shù)類(lèi)實(shí)例高度重疊的稀疏少數(shù)類(lèi)樣例被排除在過(guò)采樣之外.

為了降低信息丟失的風(fēng)險(xiǎn)，一些方法只關(guān)注位于決策邊界附近的重疊樣例.文獻(xiàn)[8]中提出了一種基于鄰域的欠采樣框架，旨在從重疊區(qū)域中準(zhǔn)確地移除有問(wèn)題的多數(shù)類(lèi)樣例，以防止過(guò)度消除，同時(shí)增強(qiáng)少數(shù)類(lèi)的存在；編輯最近鄰(ENN)[9]關(guān)注于決策邊界附近的實(shí)例，通過(guò)考慮屬于另一個(gè)類(lèi)的k個(gè)最近鄰來(lái)選擇性地刪除多數(shù)類(lèi)樣例；梁等人[10]提出了LR-SMOTE算法，使新生成的樣本更接近樣本中心，錯(cuò)誤分類(lèi)的正類(lèi)樣本的負(fù)最近鄰被全部去除；SMOTE-IPF[11]是為了消除原始數(shù)據(jù)中的噪聲樣例以及SMOTE生成的噪聲樣例而提出的，通過(guò)在SMOTE之后應(yīng)用噪聲濾波器來(lái)實(shí)現(xiàn)；在文獻(xiàn)[12]中，以最小化信息損失為目標(biāo)，只刪除了相似度高、對(duì)分類(lèi)貢獻(xiàn)小的多數(shù)類(lèi)樣例.研究處理非平衡數(shù)據(jù)集中的類(lèi)重疊，可以有效地提高學(xué)習(xí)算法的性能.

為了解決非平衡數(shù)據(jù)分類(lèi)問(wèn)題，我們提出鄰域欠采樣AdaBoostv算法.主要貢獻(xiàn)如下：

1)針對(duì)兩類(lèi)非平衡數(shù)據(jù)的類(lèi)重疊問(wèn)題，引入了兩種基于鄰域的欠采樣方法，用于消除重疊區(qū)域中的負(fù)類(lèi)樣本；將基于鄰域的欠采樣方法應(yīng)用到AdaBoostv算法中，提高分類(lèi)器的分類(lèi)能力.

2)為了解決非平衡數(shù)據(jù)分類(lèi)問(wèn)題，AdaBoostv算法的基分類(lèi)器采用加權(quán)最優(yōu)間隔分布機(jī)模型，并對(duì)模型中的間隔均值項(xiàng)和鉸鏈損失項(xiàng)加權(quán)，權(quán)值是依據(jù)數(shù)據(jù)的非平衡比給出的，并利用帶有方差減小的隨機(jī)梯度下降方法(SVRG)[13]對(duì)加權(quán)最優(yōu)間隔分布機(jī)模型進(jìn)行求解，以提高算法的收斂速度.

2 相關(guān)工作

2.1 加權(quán)最優(yōu)間隔分布機(jī)

(1)

其中，負(fù)類(lèi)樣本的權(quán)重為Bi=(n+/n-)p，正類(lèi)樣本的權(quán)重為Bi=(n-/n+)p，p為(0，1]的常數(shù).λ1，λ2為折中參數(shù).

對(duì)于非線性可分問(wèn)題，將數(shù)據(jù)通過(guò)非線性變換φ(x)映射到高維特征空間，再據(jù)表示定理[16]，得到對(duì)應(yīng)的非線性加權(quán)最優(yōu)間隔分布機(jī)模型為：

(2)

其中，X=[φ(x1)，φ(x2)，…，φ(xn)]，α=[α1，α2，…，αn]T，G=[G1，G2，…，Gn]=XTX.

利用帶有方差減小的隨機(jī)梯度下降方法對(duì)加權(quán)最優(yōu)間隔分布機(jī)模型和非線性加權(quán)最優(yōu)間隔分布機(jī)模型進(jìn)行求解.

2.2 AdaBoostv算法

AdaBoostv算法[17]是提升算法AdaBoost的改進(jìn)版本，它最大化樣例的最小間隔達(dá)到給定的精度.該算法在計(jì)算基分類(lèi)器的線性組合系數(shù)時(shí)，將可達(dá)到間隔的當(dāng)前估計(jì)納入其中.AdaBoostv算法所需要的迭代次數(shù)的上限與AdaBoost所需要的次數(shù)相同，AdaBoost必須有可達(dá)到間隔的顯式估計(jì)作為參數(shù).AdaBoostv算法據(jù)基分類(lèi)器的誤差率來(lái)更新樣例權(quán)重，樣例權(quán)重更新公式為：

(3)

AdaBoostv算法通過(guò)最小化Zt獲得基分類(lèi)器的權(quán)重at，

(4)

樣例xi的間隔為：

(5)

由公式(5)可知，樣例間隔的取值范圍為連續(xù)區(qū)間[-1，1].

最優(yōu)間隔為：

(6)

其中H為基分類(lèi)器集合，H={h|h：x→[-1，1]}.

AdaBoostv算法的最終分類(lèi)器為：

(7)

3 鄰域欠采樣的AdaBoostv算法

當(dāng)多個(gè)類(lèi)的樣例共享數(shù)據(jù)空間中的一個(gè)公共區(qū)域時(shí)，就會(huì)發(fā)生類(lèi)重疊.雖然這些樣例屬于不同的類(lèi)別，但它們有相似的特征，這是分類(lèi)任務(wù)的一個(gè)重大障礙.當(dāng)數(shù)據(jù)中也存在類(lèi)非平衡時(shí)，類(lèi)重疊問(wèn)題變得更加嚴(yán)重.在一個(gè)非平衡和重疊的數(shù)據(jù)集中，多數(shù)類(lèi)是重疊區(qū)域中的主導(dǎo)類(lèi)，決策邊界會(huì)向少數(shù)類(lèi)偏移，那么類(lèi)邊界附近的少數(shù)類(lèi)樣例就會(huì)被錯(cuò)誤分類(lèi)，這在現(xiàn)實(shí)世界的問(wèn)題中是不希望的.

我們引入兩種基于鄰域的欠采樣方法[8]，通過(guò)欠采樣類(lèi)重疊區(qū)域的多數(shù)類(lèi)樣本可使原本模糊的決策邊界更加清晰，有利于提高整體分類(lèi)性能.

3.1 共同近鄰搜索

共同近鄰搜索刪除正類(lèi)樣例的共同負(fù)近鄰，任何兩個(gè)正查詢(xún)的共同負(fù)最近鄰被識(shí)別為潛在的重疊樣例并被刪除.該方法的性能依賴(lài)于數(shù)據(jù)密度，當(dāng)少數(shù)類(lèi)的密度遠(yuǎn)低于多數(shù)類(lèi)的密度時(shí)，只有很少的共同負(fù)近鄰樣例.共同近鄰搜索算法使用k近鄰來(lái)探索每個(gè)樣本的局部環(huán)境，k按照下面的經(jīng)驗(yàn)公式給出：

(8)

其中IR=n-/n+為非平衡比，n-和n+分別為負(fù)類(lèi)和正類(lèi)樣例個(gè)數(shù).

算法1.共同近鄰搜索欠采樣(COM)

輸入：訓(xùn)練集S，k

輸出：欠采樣后的訓(xùn)練集S0

1.begin

2.S←訓(xùn)練集；

3.Spos←S中的正類(lèi)樣例；

1http：//www.keel.es/

4.A←頻率表；

5.foreachx∈Sposdo

6.NN←k近鄰；

7.NNneg←NN中的負(fù)類(lèi)樣例；

8.foreachy∈NNnegdo

9.Ay.freq←Ay.freq+1；-

10.foreachx∈A.instancedo

11.ifAx.freq>1then

12.X←X∪{x}；

13.S0←S-X；

14.return{S0}

3.2 遞歸搜索

遞歸搜索是共同近鄰搜索的擴(kuò)展，以確保足夠和準(zhǔn)確地消除重疊的負(fù)類(lèi)樣例.設(shè)X為共同近鄰搜索中將要?jiǎng)h除的重疊的負(fù)類(lèi)樣例集合，遞歸搜索則刪除X中任意兩個(gè)負(fù)類(lèi)查詢(xún)的共同負(fù)近鄰樣例，以及X中的所有元素.因此，遞歸搜索將會(huì)檢測(cè)到更多的重疊負(fù)類(lèi)樣例.

算法2.遞歸搜索欠采樣(REC)

輸入：訓(xùn)練集S，k，X為算法1中的集合

輸出：欠采樣后的訓(xùn)練集S0

1.begin

2.S←訓(xùn)練集；

3.A←頻率表；

4.foreachx1∈Xdo

5.NN2←k近鄰；

6.NN2neg←NN2中的負(fù)類(lèi)樣例；

7.foreachy∈NN2negdo

9.foreachx2∈A′.instancedo

10.ifA′x2.freq>1then

11.X2←X2∪{x2}；

12.S0←S-(X∪X2)；

13.return{S0}

3.3 鄰域欠采樣的AdaBoostv算法

首先，基于共同近鄰搜索欠采樣(COM)和遞歸搜索欠采樣(REC)對(duì)訓(xùn)練數(shù)據(jù)集S進(jìn)行欠采樣，用于消除類(lèi)重疊區(qū)域中的負(fù)類(lèi)樣例；然后，針對(duì)欠采樣后獲得的數(shù)據(jù)集S0，應(yīng)用AdaBoostv算法，AdaBoostv算法的基分類(lèi)器采用加權(quán)最優(yōu)間隔分布機(jī)模型，利用SVRG方法對(duì)加權(quán)最優(yōu)間隔分布機(jī)模型進(jìn)行求解.以更好地處理非平衡數(shù)據(jù)的分類(lèi)問(wèn)題.

算法3.鄰域欠采樣的AdaBoostv算法.

輸入：訓(xùn)練集S，折中參數(shù)λ1、λ2，迭代次數(shù)T，所需精度v

1.基于COM、REC對(duì)訓(xùn)練數(shù)據(jù)集S進(jìn)行欠采樣，采樣后的訓(xùn)練集記為S0

3.fort=1，…，T

6. 若|γt|=1，則at=sign(γt)，h1=ht，T=1；停止

10.end for

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

給出所提算法和對(duì)比算法的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)結(jié)果均采用五折交叉驗(yàn)證的平均值.編程語(yǔ)言采用Matlab，版本為MatlabR2017b，實(shí)驗(yàn)除Avila數(shù)據(jù)集[18]和bank數(shù)據(jù)集[19]外，其它數(shù)據(jù)集均來(lái)自KEEL1，數(shù)據(jù)集信息如表1所示.

表1 非平衡數(shù)據(jù)集Table 1 Imbalanced datasets

4.1 處理類(lèi)重疊的重要性實(shí)驗(yàn)

為了說(shuō)明非平衡數(shù)據(jù)分類(lèi)中刪除類(lèi)重疊區(qū)域中負(fù)類(lèi)樣本的重要性，在人工數(shù)據(jù)集上進(jìn)行了以下實(shí)驗(yàn).首先，生成服從高斯分布的二維人工數(shù)據(jù)集，該數(shù)據(jù)集中正類(lèi)樣本個(gè)數(shù)為100，負(fù)類(lèi)樣本個(gè)數(shù)為500.首先給出人工數(shù)據(jù)集中高斯分布的參數(shù)設(shè)置如表2所示.

表2 兩個(gè)高斯分布的人工數(shù)據(jù)集Table 2 Two artificial datasets with Gaussian distribution

其次，給出生成的原始數(shù)據(jù)分布圖、COM欠采樣后的數(shù)據(jù)分布圖以及REC欠采樣后的數(shù)據(jù)分布圖，如圖1、圖2、圖3所示(“+”號(hào)為正類(lèi)樣本，“*”號(hào)為負(fù)類(lèi)樣本).

從圖1、圖2、圖3中可以看出，通過(guò)欠采樣類(lèi)重疊區(qū)域的多數(shù)類(lèi)樣本可使原本模糊的決策邊界更加清晰，最大化正類(lèi)樣本的可見(jiàn)性，更有利于整體分類(lèi)性能的提高.

圖1 原始數(shù)據(jù)分布Fig.1 Original data distribution

圖2 COM欠采樣數(shù)據(jù)分布Fig.2 COM undersampling data distribution

圖3 REC欠采樣數(shù)據(jù)分布Fig.3 REC undersampling data distribution

最后，給出原始的AdaBoostv算法與提出的基于欠采樣的AdaBoostv算法在人工數(shù)據(jù)集上的幾何均值和召回率對(duì)比實(shí)驗(yàn)，結(jié)果如表3所示.

從表3中可以看出，提出的兩種算法在幾何均值和召回率上優(yōu)于原始的AdaBoostv算法，并且RECBoostv算法在人工數(shù)據(jù)集上的分類(lèi)能力優(yōu)于COMBoostv算法.

4.2 參數(shù)設(shè)置

觀察表4、表5可知，改進(jìn)SVM優(yōu)化模型中的權(quán)重參數(shù)p在大多數(shù)數(shù)據(jù)集上的值都為0.5，v值在所有數(shù)據(jù)集上都取為0.02，由此可知，v值不宜取得過(guò)大.觀察λ1和λ2，雖然二者取值有差異，但差異不宜過(guò)大.在非線性算法中，高斯核參數(shù)σ的取值會(huì)根據(jù)不同的數(shù)據(jù)集取不同的參數(shù)值，但亦不宜過(guò)大，否則會(huì)影響到分類(lèi)精度，我們需要對(duì)參數(shù)值進(jìn)行適當(dāng)?shù)卣{(diào)整.

表4 線性算法在不同數(shù)據(jù)集上的參數(shù)Table 4 Parameters of the linear algorithm on different data sets

表5 非線性算法在不同數(shù)據(jù)集上的參數(shù)Table 5 Parameters of the nonlinear algorithm

4.3 幾何均值和召回率對(duì)比實(shí)驗(yàn)

首先給出對(duì)比算法的描述，對(duì)比算法分別為AdaBoost算法和隨機(jī)欠采樣AdaBoost算法(RUSBoost)[20].AdaBoost算法采用改進(jìn)的SVM模型，RUSBoost采用標(biāo)準(zhǔn)SVM模型.兩種算法都采用SVRG方法.

線性算法與非線性算法的幾何均值測(cè)試結(jié)果如表6、表7所示.

觀察表6、表7，可以發(fā)現(xiàn)提出的兩種欠采樣集成算法的幾何均值明顯優(yōu)于其它算法，而對(duì)于不同的數(shù)據(jù)集，兩種欠采樣集成方法的幾何均值各有優(yōu)劣，這是由于不同數(shù)據(jù)集的兩類(lèi)樣本的數(shù)據(jù)密度高低不同造成的.

表6 線性算法的幾何均值Table 6 G_mean of linear algorithm

表7 非線性算法的幾何均值Table 7 G_mean of nonlinear algorithm

給出召回率對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表8、表9所示.

觀察表8和表9，提出算法的召回率普遍優(yōu)于對(duì)比算法，并且在一些數(shù)據(jù)集上的召回率達(dá)到1，說(shuō)明提出的兩種算法使得分類(lèi)器更加關(guān)注少數(shù)類(lèi)樣本，從而更能提高少數(shù)類(lèi)樣本的分類(lèi)精度.

表8 線性算法的召回率Table 8 Recall of linear algorithm

4.4 最優(yōu)間隔對(duì)比實(shí)驗(yàn)

給出提出算法與對(duì)比算法在非平衡數(shù)據(jù)集上的最優(yōu)間隔折線圖，如圖4、圖5所示.

表9 非線性算法的召回率Table 9 Recall of nonlinear algorithm

觀察圖4、圖5可以看出，無(wú)論線性算法還是非線性算法，提出的兩種算法在訓(xùn)練集上的最優(yōu)間隔折線走勢(shì)極為相似且緊密靠攏，說(shuō)明兩種算法的最優(yōu)間隔差異不大，均優(yōu)于對(duì)比算法的最優(yōu)間隔.

圖4 線性算法的最優(yōu)間隔Fig.4 Optimal margin for linear algorithm

圖5 非線性算法的最優(yōu)間隔Fig.5 Optimal margin of nonlinear algorithm

5 總 結(jié)

提出了鄰域欠采樣的AdaBoostv算法，首先，針對(duì)類(lèi)別非平衡情況下的類(lèi)重疊問(wèn)題，引入了兩種鄰域欠采樣方法，用于消除類(lèi)重疊區(qū)域中的多數(shù)類(lèi)樣本.其次，將兩種欠采樣方法應(yīng)用在AdaBoostv算法上，AdaBoostv算法的基分類(lèi)器采用加權(quán)最優(yōu)間隔分布機(jī)模型，權(quán)值是依據(jù)數(shù)據(jù)的非平衡比給出的，以提高分類(lèi)器處理非平衡數(shù)據(jù)的能力.并利用帶有方差減小的隨機(jī)梯度下降方法對(duì)優(yōu)化模型進(jìn)行求解，以提高算法的收斂速度.在人工數(shù)據(jù)集上實(shí)驗(yàn)表明通過(guò)欠采樣類(lèi)重疊區(qū)域的多數(shù)類(lèi)樣本可使原本模糊的決策邊界更加清晰，有利于提高整體分類(lèi)性能.在基準(zhǔn)數(shù)據(jù)集上的幾何均值、召回率和最優(yōu)間隔對(duì)比實(shí)驗(yàn)表明，兩種鄰域欠采樣的AdaBoostv算法在處理非平衡數(shù)據(jù)分類(lèi)問(wèn)題上具有明顯的優(yōu)越性.將兩種欠采樣的方法應(yīng)用到多類(lèi)數(shù)據(jù)的非平衡分類(lèi)問(wèn)題中是下一步研究工作的重點(diǎn).