基于分類難度的過(guò)采樣度優(yōu)化方法

祝團(tuán)飛，羅成，曾一夫，張維

（1.長(zhǎng)沙學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙 410022；2.江西工業(yè)貿(mào)易職業(yè)技術(shù)學(xué)院信息工程系，江西 南昌 330038）

不平衡數(shù)據(jù)的分類是指分類的數(shù)據(jù)中一些類（大數(shù)類）的樣本數(shù)目顯著多于另外一些類（少數(shù)類）的樣本數(shù)目，該問題廣泛地存在于現(xiàn)實(shí)世界的應(yīng)用中，例如疾病診斷、軟件缺陷預(yù)測(cè)、故障偵測(cè)等。樣本數(shù)目的不平衡分布給傳統(tǒng)的分類學(xué)習(xí)算法帶來(lái)了巨大挑戰(zhàn)，主要表現(xiàn)在兩方面：分類算法通常以最小化訓(xùn)練錯(cuò)誤為目標(biāo)，樣本數(shù)量絕對(duì)占優(yōu)的大數(shù)類會(huì)使其分類器的預(yù)測(cè)偏置［1-2］；類重疊、類內(nèi)不平衡、噪聲等數(shù)據(jù)困難因子與類不平衡在學(xué)習(xí)困難度上有超疊加效應(yīng)［3-4］。此兩項(xiàng)挑戰(zhàn)使標(biāo)準(zhǔn)的分類學(xué)習(xí)算法在少數(shù)類上的預(yù)測(cè)表現(xiàn)出低泛化性能。然而，稀有的少數(shù)類對(duì)象往往能體現(xiàn)出問題的本質(zhì)，對(duì)少數(shù)類樣本錯(cuò)誤地分類可能會(huì)付出相比錯(cuò)誤預(yù)測(cè)大數(shù)類樣本更高的代價(jià)。例如，在疾病診斷中誤將一個(gè)健康人診斷為患某種疾病固然會(huì)給人帶來(lái)精神負(fù)擔(dān)，但將一個(gè)實(shí)際病患漏診為健康人會(huì)讓其錯(cuò)過(guò)最佳的治療時(shí)機(jī)，導(dǎo)致災(zāi)難性的后果。

過(guò)去的二十年，研究人員提出了多種類型的不平衡學(xué)習(xí)方法［5-6］。其中，人工合成少數(shù)類樣本的過(guò)采樣技術(shù)是熱門的方法之一。過(guò)采樣技術(shù)需要解決兩個(gè)基本問題：如何生成人工的少數(shù)類合成樣本，以及為每一個(gè)少數(shù)類樣本生成多少合成樣本。這兩個(gè)問題分別涉及合成樣本的生成和過(guò)采樣度的尋優(yōu)。現(xiàn)有研究中，幾乎所有的過(guò)采樣算法都側(cè)重于合成樣本的生成方法創(chuàng)新，而忽略過(guò)采樣度的尋優(yōu)策略設(shè)計(jì)。然而，過(guò)采樣度能顯著影響算法的性能，過(guò)高的過(guò)采樣度會(huì)嚴(yán)重?fù)p害大數(shù)類的分類性能，過(guò)低的過(guò)采樣度將不能有效糾正分類器偏向大數(shù)類的預(yù)測(cè)偏置。

在過(guò)采樣度尋優(yōu)策略中，一個(gè)關(guān)鍵的問題是如何解決過(guò)采樣權(quán)重分布，即在總的合成樣本一定的情況下，如何完成合成樣本在各個(gè)少數(shù)類樣本上量的分配?，F(xiàn)有的方法基于樣本分布的局部特征，為少數(shù)類樣本測(cè)量若干反映學(xué)習(xí)重要性的數(shù)據(jù)因子，然后整合這些數(shù)據(jù)因子作為過(guò)采樣權(quán)重［7-11］。然而，學(xué)習(xí)的重要性依賴于具體的分類學(xué)習(xí)方法，且出于強(qiáng)化難于分類的樣本學(xué)習(xí)的目的，少數(shù)類樣本的過(guò)采樣度應(yīng)由其本身的分類難度決定。

基于以上動(dòng)機(jī)，我們提出一種依賴分類困難度的過(guò)采樣權(quán)重分配方法CD-W（Classification Difficulty-based Weighting）。通過(guò)將CD-W與目前流行的SMOTE插值生成技術(shù)相結(jié)合，得到新的過(guò)采樣算法CD-SM。CD-SM中每一個(gè)少數(shù)類樣本的過(guò)采樣權(quán)重由分類器對(duì)其預(yù)測(cè)的軟損失決定，以確保分類損失越高的少數(shù)類樣本分配到越多的合成樣本。為了評(píng)估CD-SM的有效性，我們以神經(jīng)網(wǎng)絡(luò)為分類器，以F1、G-mean和AUC［12］為性能評(píng)價(jià)指標(biāo)，在18個(gè)UCI標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，結(jié)果表明，CD-SM是具有高度競(jìng)爭(zhēng)力的加權(quán)過(guò)采樣算法。

1 相關(guān)工作

現(xiàn)有文獻(xiàn)中，只有非常少量的過(guò)采樣方法涉及估計(jì)過(guò)采樣權(quán)重的分布，我們對(duì)有限的過(guò)采樣權(quán)重估計(jì)方法進(jìn)行了總結(jié)。

自2002年合成少數(shù)過(guò)采樣技術(shù)SMOTE被提出以來(lái)，學(xué)術(shù)界和工業(yè)界的研究人員設(shè)計(jì)了大量的過(guò)采樣算法去處理不平衡的分類問題［6-9，13-18］。絕大部分的算法致力于合成樣本生成方法的創(chuàng)新，而忽視過(guò)采樣度尋優(yōu)策略的設(shè)計(jì)，其中代表性的算法有SMOTE［17］、SMOM［13］、PAIO［14］和SMOR［15］。這些方法簡(jiǎn)單地假設(shè)過(guò)采樣權(quán)重分布是一個(gè)均勻的分布，為每一個(gè)少數(shù)類樣本生成等量的合成樣本。然而，不同的少數(shù)類樣本具有不同的重要性，一些樣本可為數(shù)據(jù)的分類學(xué)習(xí)提供更多有用的信息。

Borderline-SMOTE［9］和ADASYN［7］是被最早提出加權(quán)過(guò)采樣的兩個(gè)算法，且都基于少數(shù)類樣本的k最近鄰居分布確定過(guò)采樣的權(quán)重。前者只對(duì)k最近鄰居中存在一半以上大數(shù)類樣本的少數(shù)類樣本賦權(quán)重（不包括k最近鄰居全為大數(shù)類的少數(shù)類“噪聲”樣本），后者少數(shù)類樣本的過(guò)采樣權(quán)重與其k最近鄰居中大數(shù)類樣本數(shù)目成正比。此種加權(quán)過(guò)采樣策略的動(dòng)機(jī)是邊界的樣本往往具有更高的重要性，需為其分配更多的合成樣本。后續(xù)的INOS［10］和RAMOBoost［11］過(guò)采樣沿用了ADASYN的過(guò)采樣權(quán)重計(jì)算方法。然而，找到一個(gè)合適的鄰居參數(shù)k去捕捉所有的邊界樣本和充分反映學(xué)習(xí)的重要性是非常困難甚至不可行的［18］。

為避免設(shè)置參數(shù)k，MWMOTE［18］引入邊界大數(shù)類樣本和少數(shù)類樣本間的親密因子與密度因子來(lái)計(jì)算少數(shù)類樣本的過(guò)采樣度，其中親密因子衡量每一個(gè)邊界大數(shù)類樣本與其k最近的少數(shù)類樣本的鄰近程度（即距離遠(yuǎn)近），而密度因子反映每一個(gè)邊界大數(shù)類樣本周圍分布少數(shù)類樣本的稀疏程度。一個(gè)少數(shù)類樣本的過(guò)采樣權(quán)重是累加所有邊界大數(shù)類樣本提供的親密因子與密度因子的乘積。MWMOTE分配過(guò)采樣權(quán)重的主要出發(fā)點(diǎn)是為越靠近大數(shù)類樣本（更高的親密因子）和位于越稀疏聚類（傾向更高的密度因子）的少數(shù)類樣本分配越高的權(quán)重。

最近，基于高斯分布的過(guò)采樣方法GDO［8］采用了與MWMOTE相似的權(quán)重計(jì)算方法，其使用密度因子和距離因子來(lái)衡量少數(shù)類樣本所具有的信息量差異。在GDO中，密度因子被定義為少數(shù)類樣本的k最近鄰居中大數(shù)類樣本的比率，距離因子衡量k最近鄰居中大數(shù)類樣本鄰居相對(duì)于少數(shù)類樣本鄰居與當(dāng)前考慮的少數(shù)類樣本的平均距離比。GDO將一個(gè)少數(shù)類樣本的密度因子與距離因子之和作為此樣本的過(guò)采樣權(quán)重，其背后的動(dòng)機(jī)是為遠(yuǎn)離大數(shù)類樣本的邊界少數(shù)類樣本分配更高的權(quán)重。然而，類似于ADASYN，如果少數(shù)類樣本的k最近鄰居不存在任何的大數(shù)類樣本，GDO將為這些樣本的權(quán)重賦值為零。顯然，這可能導(dǎo)致大部分的過(guò)采樣權(quán)重只集中在個(gè)別的少數(shù)類樣本上。

2 基于分類難度的算法

我們提出的過(guò)采樣算法的主要思想是依據(jù)少數(shù)類的分類難度來(lái)分配少數(shù)類樣本的過(guò)采樣權(quán)重，然后與目前流行的合成樣本生成方法SMOTE相結(jié)合，得到一種基于分類難度的加權(quán)過(guò)采樣方法CD-SM。在CD-SM中，一個(gè)少數(shù)類樣本的分類難度是分類模型對(duì)其多次預(yù)測(cè)的分類損失平均。CD-SM首先將樣本的分類難度轉(zhuǎn)化為過(guò)采樣的權(quán)重分布，然后據(jù)此分布，在更難分類的少數(shù)類樣本附近插值生成更多的合成樣本，以強(qiáng)化這些樣本的學(xué)習(xí)。

CD-SM的算法過(guò)程如下。

輸入：原始不平衡數(shù)據(jù)集D，少數(shù)類樣本集S，分類學(xué)習(xí)算法L，估計(jì)分類難度的次數(shù)nc，生成的合成樣本總量ns；

輸出：合成的少數(shù)樣本集Syn；

步驟1：對(duì)原始不平衡數(shù)據(jù)集D的每一類，應(yīng)用SMOTE方法生成相同數(shù)量的合成樣本，以得到一個(gè)與D相同類分布的合成數(shù)據(jù)集Dsyn；

步驟2：基于Dsyn，使用分類學(xué)習(xí)算法L訓(xùn)練得到分類模型M；

步驟3：使用M對(duì)D中的少數(shù)類樣本集S分類，得到少數(shù)類樣本的分類難度；

步驟4：重復(fù)以上步驟nc次，將少數(shù)類樣本的nc次分類難度的平均值作為其最終的分類難度CD；

步驟5：將獲得的難度CD轉(zhuǎn)換為過(guò)采樣權(quán)重分布W；

步驟6：執(zhí)行下面過(guò)程，為少數(shù)類生成合成樣本數(shù)據(jù)集Syn。

（1）從S中根據(jù)過(guò)采樣權(quán)重分布W，抽樣出一個(gè)少數(shù)類樣本xi作為主種子樣本；

（2）從xi的k最近同類鄰居中隨機(jī)選擇一個(gè)少數(shù)類樣本xj作為輔助種子樣本；

（3）基于xi和xj，插值得到一個(gè)合成樣本，其中δ是一個(gè)元素處在［0，1］之間的隨機(jī)向量，“.*”代表元素級(jí)的乘法；

（4）將xs加入；

（5）重復(fù)（1）至（4）ns次，返回Syn。

步驟1與步驟2的目的是生成D的一個(gè)副本數(shù)據(jù)集Dsyn以訓(xùn)練得到分類模型M，然后使用M去對(duì)少數(shù)類樣本集S分類。步驟3中，一個(gè)少數(shù)類樣本xi的分類難度可表示為：

其中yi是xi的真實(shí)標(biāo)簽。即為預(yù)測(cè)xi時(shí)產(chǎn)生的軟損失。損失越高代表xi越難被M正確分類。由于Dsyn是使用SMOTE生成的原始數(shù)據(jù)集D的副本，其樣本受SMOTE中隨機(jī)因素的影響而具有一定的隨機(jī)性。步驟4的目的是為D生成多次的副本Dsyn，通過(guò)反復(fù)訓(xùn)練與預(yù)測(cè)S，從而得到S中每一個(gè)樣本的可靠分類難度估計(jì)CD（一個(gè)少數(shù)樣本的最終分類難度是nc次估計(jì)的平均值）。

得到少數(shù)類樣本的分類困難度后，在步驟5中利用下面兩式將其轉(zhuǎn)換為一個(gè)過(guò)采樣權(quán)重分布W：

最后，基于W和S，在步驟6中為少數(shù)類生成合成樣本集Syn。步驟6中，每一個(gè)主種子樣本xi是據(jù)分布W從S中抽樣得到，越高分類難度的少數(shù)類樣本有越高的概率被選擇作為主種子樣本，從而有越大可能在其附近生成較多的合成樣本。

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

3.1 實(shí)驗(yàn)設(shè)置

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

我們從UCI數(shù)據(jù)庫(kù)［19］中選擇了18個(gè)現(xiàn)實(shí)的數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)。這些數(shù)據(jù)集的特征總結(jié)如表1所示。從表1中可以看出，選擇的實(shí)驗(yàn)數(shù)據(jù)集具有不同的特征數(shù)目、樣本數(shù)目和類不平衡度。

表1 實(shí)驗(yàn)的18個(gè)UCI不平衡數(shù)據(jù)集的特征總結(jié)

續(xù)表

3.1.2 方法比較

在已有的文獻(xiàn)中，過(guò)采樣算法ADASYN、MWMOTE和GDO采用的權(quán)重計(jì)算方法分別是三種代表性的過(guò)采樣度權(quán)重分配方法。我們重點(diǎn)與此三種方法進(jìn)行比較。為了剔除合成樣本生成方式的不同所造成的實(shí)驗(yàn)干擾，將ADASYN、MWMOTE和GDO中的過(guò)采樣度權(quán)重方式分別與SMOTE的合成樣本生成方法相結(jié)合，簡(jiǎn)寫為ADSM，MW-SM和GD-SM。此外，我們將被普遍采用的均勻權(quán)重分配方式也納入實(shí)驗(yàn)比較中，即原始的SMOTE（簡(jiǎn)寫為SM）過(guò)采樣。所有比較的方法的參數(shù)分別使用相應(yīng)論文中的推薦值。實(shí)驗(yàn)提出的CD-SM中，估計(jì)分類難度的次數(shù)nc設(shè)置為5。

3.1.3 性能指標(biāo)

由于類分布的不平衡，評(píng)估分類模型在不平衡數(shù)據(jù)上的學(xué)習(xí)性能需要采用專門的類不平衡評(píng)價(jià)指標(biāo)。在現(xiàn)有的研究中，F(xiàn)1、G-mean和AUC［12］是三個(gè)最為常用的面向類不平衡的性能指標(biāo)。對(duì)F1、G-mean的定義如下：

其中，召回率Recall和精確度Precision分別是少數(shù)類樣本被正確預(yù)測(cè)的比率（即少數(shù)類的預(yù)測(cè)精度）和預(yù)測(cè)為少數(shù)類的樣本中實(shí)際為少數(shù)類的比率。不同于F1和G-mean，AUC不依賴于具體的決策閾值。實(shí)驗(yàn)中每一個(gè)作為比較的方法在每一個(gè)數(shù)據(jù)集取得的實(shí)驗(yàn)結(jié)果都基于10次獨(dú)立運(yùn)行的5分層交叉驗(yàn)證，然后將其平均值作為最后的性能。

3.1.4 統(tǒng)計(jì)性檢驗(yàn)

Wilcoxon符號(hào)秩檢驗(yàn)［20］是最受歡迎的非參數(shù)顯著性檢驗(yàn)方法。我們使用此方法去驗(yàn)證提出的方法與其他比較的方法間是否存在顯著性差異。

3.1.5 基分類器

我們使用一個(gè)三層的神經(jīng)網(wǎng)絡(luò)作為基分類器，其輸入層和輸出層的神經(jīng)元個(gè)數(shù)分別為訓(xùn)練集的特征數(shù)目和類別數(shù)目，中間層采用固定的10個(gè)神經(jīng)元。神經(jīng)網(wǎng)絡(luò)以0.01的學(xué)習(xí)率訓(xùn)練500代以收斂分類模型。

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

表2和表3分別總結(jié)了當(dāng)過(guò)采樣倍率為100%和300%時(shí)，NONE、SM、AD-SM、MW-SM、GD-SM和我們提出的CD-SM在每一個(gè)數(shù)據(jù)集上的F1、G-mean和AUC性能值（NONE表示未結(jié)合任何過(guò)采樣算法的性能結(jié)果）?；诒?和表3的結(jié)果，CD-SM在兩種過(guò)采樣倍率和每一種評(píng)價(jià)指標(biāo)下都獲得了最好的平均性能值。為更好地演示各種比較的方法的競(jìng)爭(zhēng)力，圖1給出了所有用于比較的方法在18個(gè)實(shí)驗(yàn)數(shù)據(jù)集上的平均性能排名。從圖1可以看出，CD-SM以明顯的優(yōu)勢(shì)在每一個(gè)評(píng)價(jià)指標(biāo)上獲得最低的平均排名，表明基于分類難度的過(guò)采樣權(quán)重分配方法具有最高的競(jìng)爭(zhēng)力和穩(wěn)健性。

圖1 a與b分別表示當(dāng)過(guò)采樣倍率100%和300%時(shí)，各方法在F1、G-mean和AUC上的平均排名

表2 過(guò)采樣倍率100%時(shí)，比較的方法在18個(gè)實(shí)驗(yàn)數(shù)據(jù)集上的F1、G-mean和AUC性能結(jié)果

表3 過(guò)采樣倍率300%時(shí)，比較的方法在18個(gè)實(shí)驗(yàn)數(shù)據(jù)集上的F1、G-mean和AUC性能結(jié)果

續(xù)表

為了測(cè)試比較的方法間是否存在顯著性差異，表4列出了CD-SM與其他每一個(gè)方法的Wilcoxon符號(hào)秩檢驗(yàn)結(jié)果（“++”“+*”分別表示CD-SM以0.05和0.1的顯著性水平好于其他比較的方法，“+”表示CD-SM只定量地好于其他比較的方法）。表4的結(jié)果說(shuō)明在絕大部分情況下，CD-SM顯著性地好于其他比較的方法，從而驗(yàn)證了提出的方法的有效性。

表4 CD-SM與每一個(gè)其他比較的方法間的Wilcoxon符號(hào)秩顯著性檢驗(yàn)結(jié)果

4 結(jié)論

我們提出了一種基于分類難度的加權(quán)過(guò)采樣方法，將分類學(xué)習(xí)算法在少數(shù)類樣本上的分類損失作為過(guò)采樣權(quán)重，以強(qiáng)化那些難于正確分類的少數(shù)類樣本的學(xué)習(xí)。不同于已有的加權(quán)過(guò)采樣方法，我們提出的方法分配過(guò)采樣權(quán)重不再基于數(shù)據(jù)特征所反映的樣本重要性，而是直接考慮當(dāng)前的分類學(xué)習(xí)算法對(duì)少數(shù)類樣本的分類難度。為了評(píng)價(jià)提出的方法的有效性，我們以18個(gè)UCI現(xiàn)實(shí)數(shù)據(jù)集為實(shí)驗(yàn)數(shù)據(jù)，以神經(jīng)網(wǎng)絡(luò)為基分類器進(jìn)行實(shí)驗(yàn)，結(jié)果表明，此方法在常用的評(píng)價(jià)指標(biāo)F1、G-mean和AUC上都優(yōu)于現(xiàn)有的加權(quán)過(guò)采樣方法。

最后，需要指出的是，我們提出的方法需要額外訓(xùn)練nc次的模型和預(yù)測(cè)nc次的少數(shù)類樣本集去獲得準(zhǔn)確的分類難度分布。在實(shí)驗(yàn)仿真中，CD-SM的nc只需設(shè)置為一個(gè)較小的常數(shù)5，即可取得相比已有方法顯著更好的性能。因此，我們認(rèn)為其產(chǎn)生的額外時(shí)間代價(jià)是值得的。