熊冰妍 王國胤 鄧維斌

(重慶郵電大學(xué)計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室 重慶 400065)(1217185006@qq.com)

?

基于樣本權(quán)重的不平衡數(shù)據(jù)欠抽樣方法

熊冰妍 王國胤 鄧維斌

(重慶郵電大學(xué)計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室 重慶 400065)(1217185006@qq.com)

現(xiàn)實(shí)世界中廣泛存在不平衡數(shù)據(jù),其分類問題是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的一個(gè)研究熱點(diǎn).欠抽樣是處理不平衡數(shù)據(jù)集的一種常用方法,其主要思想是選取多數(shù)類樣本中的一個(gè)子集,使數(shù)據(jù)集的樣本分布達(dá)到平衡,但其容易忽略多數(shù)類中部分有用信息.為此提出了一種基于樣本權(quán)重的欠抽樣方法KAcBag(K-means AdaCost bagging),該方法引入了樣本權(quán)重來反映樣本所處的區(qū)域,首先根據(jù)各類樣本的數(shù)量初始化各樣本權(quán)重,并通過多次聚類對各個(gè)樣本的權(quán)重進(jìn)行修改,權(quán)重小的多數(shù)類樣本即處于多數(shù)類的中心區(qū)域;然后按權(quán)重大小對多數(shù)類樣本進(jìn)行欠抽樣,使位于中心區(qū)域的樣本較容易被抽中,并與所有少數(shù)類樣本組成bagging成員分類器的訓(xùn)練數(shù)據(jù),得到若干個(gè)決策樹子分類器;最后根據(jù)各子分類器的正確率進(jìn)行加權(quán)投票生成預(yù)測模型.對19組UCI數(shù)據(jù)集和某電信運(yùn)營商客戶換機(jī)數(shù)據(jù)進(jìn)行了測試實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明:KAcBag方法使抽樣所得的樣本具有較強(qiáng)的代表性,能有效提高少數(shù)類的分類性能并縮小問題規(guī)模.

不平衡數(shù)據(jù);欠抽樣;樣本權(quán)重;聚類;集成學(xué)習(xí)

不平衡數(shù)據(jù)集是指在數(shù)據(jù)集中某一類的樣本數(shù)量遠(yuǎn)遠(yuǎn)少于其他類的樣本數(shù)量,其中數(shù)量占多數(shù)的類稱為多數(shù)類,而占少數(shù)的類稱為少數(shù)類.不平衡數(shù)據(jù)集的分類問題大量存在于人們的現(xiàn)實(shí)生活和工業(yè)生產(chǎn)之中,如客戶流失預(yù)測[1]、DNA微陣列數(shù)據(jù)分析[2]、軟件缺陷預(yù)測[3]、垃圾郵件過濾[4]、文本分類[5]、醫(yī)療診斷[6]等,在這些應(yīng)用中少數(shù)類分類精度往往更為重要.因此,提高少數(shù)類的分類精度成為不平衡數(shù)據(jù)集中的研究重點(diǎn).

現(xiàn)有的不平衡數(shù)據(jù)處理方法主要分2類:

1) 從訓(xùn)練集入手,通過改變訓(xùn)練集樣本分布,降低不平衡程度.常用的抽樣方法有2種：過抽樣和欠抽樣.過抽樣是通過增加訓(xùn)練集中少數(shù)類的數(shù)量,使數(shù)據(jù)集的樣本分布達(dá)到平衡,如SMOTE(synthetic minority over-sampling technique)算法[7],該方法通過插值生成新的人造樣本,使少數(shù)類具有更大的泛化空間.Borderline-SMOTE算法[8]是一種改進(jìn)的SMOTE算法,其只對少數(shù)類的邊界樣本進(jìn)行過抽樣處理,以保證新增加的樣本是有價(jià)值的.欠抽樣是通過減少多數(shù)類樣本來使數(shù)據(jù)集的樣本分布達(dá)到平衡,如單邊選擇(one-sided selection)算法[9],該方法采用單邊采樣方式,去除大類中的噪音樣本、邊界樣本和冗余樣本.SBC(under-sampling based on clustering)算法[10]通過聚類后簇內(nèi)的正類與負(fù)類的比例確定抽樣比例參數(shù).

2) 從學(xué)習(xí)算法入手,根據(jù)算法在解決不平衡問題時(shí)的缺陷,適當(dāng)?shù)匦薷乃惴ㄊ怪m應(yīng)不平衡分類問題.常用策略有: 代價(jià)敏感方法,在傳統(tǒng)的分類算法的基礎(chǔ)上引人代價(jià)敏感因子,設(shè)計(jì)出代價(jià)敏感的分類算法,如代價(jià)敏感決策樹[11]、代價(jià)敏感支持向量機(jī)[12]等；集成學(xué)習(xí)方法,使用一系列分類器進(jìn)行學(xué)習(xí),并使用某種規(guī)則把各個(gè)學(xué)習(xí)結(jié)果進(jìn)行整合從而獲得比單個(gè)學(xué)習(xí)器更好的學(xué)習(xí)效果,如bagging[13],AdaBoost[14],AdaCost[15]等.

此外,將欠抽樣方法與集成學(xué)習(xí)進(jìn)行融合,既能利用欠抽樣的優(yōu)點(diǎn)平衡數(shù)據(jù)集,使分類器能更好地提高少數(shù)類的分類性能,又能利用集成方法的優(yōu)點(diǎn)提高不平衡數(shù)據(jù)集的整體分類能.文獻(xiàn)[16]提出的EBBag(exactly balanced bagging)算法結(jié)合隨機(jī)欠抽樣和bagging算法,對于每次迭代,訓(xùn)練集由所有的少數(shù)類樣本和從多數(shù)類樣本中隨機(jī)抽取的一個(gè)子集組成,但隨機(jī)抽取多數(shù)類樣本沒有考慮數(shù)據(jù)的分布特點(diǎn),容易丟失有用信息.RBBag(roughly balanced bagging)[16]算法是對EBBag算法的改進(jìn),其主要思想在于如何決定2類中樣本采樣的數(shù)目：少數(shù)類樣本采樣的數(shù)目等于原子集樣本的數(shù)目,而多數(shù)類樣本采樣數(shù)據(jù)取決于其二項(xiàng)分布,該算法的優(yōu)點(diǎn)在于它既保留了初始背包技術(shù)的優(yōu)點(diǎn),同時(shí)還使得少數(shù)類樣本的有用信息得到充分利用,因此較一般的背包技術(shù)魯棒性更強(qiáng).文獻(xiàn)[17]提出的uNBBag0.5(under-sampling neighbourhood bagging)算法是通過統(tǒng)計(jì)各樣本周圍的多數(shù)類樣本數(shù)來計(jì)算其樣本權(quán)重,并根據(jù)權(quán)重對原始數(shù)據(jù)集進(jìn)行欠抽樣,使分類器性能得到較大提升,但其只著重研究了少數(shù)類的樣本權(quán)重,所有多數(shù)類樣本的權(quán)重相同,未考慮樣本間的分布差異.將過抽樣技術(shù)與bagging算法相結(jié)合也是一種有效提高分類性能的方法,如oNBBag2(over-sampling neighbourhood bagging)算法[17]、OvBag(over-sampling bagging)算法[18]、SmBag(SMOTE bagging)算法[18].

基于以上研究,本文通過研究多數(shù)類樣本的分布情況提出一種基于樣本權(quán)重的不平衡數(shù)據(jù)欠抽樣方法KAcBag(K-means AdaCost bagging),首先根據(jù)原始數(shù)據(jù)集中各類樣本的數(shù)量初始化各樣本的權(quán)重,然后通過K-means聚類算法對數(shù)據(jù)集進(jìn)行多次聚類,并根據(jù)每次的聚類結(jié)果更新樣本權(quán)重,最后按照樣本權(quán)重的大小對多數(shù)類樣本進(jìn)行欠抽樣得到平衡的訓(xùn)練集,以決策樹作為bagging算法的基分類器,新的測試樣本的類別由多個(gè)基分類器投票表決.

1 相關(guān)理論

1.1K-means聚類算法

MacQueen[19]在1967年提出了K-means算法,它是廣泛應(yīng)用于科學(xué)和工業(yè)諸多聚類算法中有效的算法之一.K-means算法的工作機(jī)理是把n個(gè)樣本點(diǎn)分為k個(gè)簇,各簇內(nèi)的樣本點(diǎn)具有較高的相似性,而各簇間的樣本點(diǎn)相似程度較低.如算法1所示.

算法1.K-means聚類算法.

輸入:樣本數(shù)據(jù)集、簇的個(gè)數(shù)k、最大迭代次數(shù);

輸出:k個(gè)簇.

Step1. 在樣本數(shù)據(jù)集中隨機(jī)選擇k個(gè)樣本點(diǎn)作為初始簇中心;

Step2. 在第i次迭代中,對任意一個(gè)樣本,求其到k個(gè)中心的距離,將該樣本歸到距離最短的中心所在的簇;

Step3. 使用每個(gè)簇內(nèi)的樣本均值作為新的簇中心;

Step4. 對于所有的k個(gè)簇中心,如果利用Step2和Step3的迭代法更新后,目標(biāo)函數(shù)達(dá)到最優(yōu)或達(dá)到最大迭代次數(shù),則迭代結(jié)束,否則繼續(xù)迭代;

Step5. 結(jié)束,得到k個(gè)簇.

采用歐氏距離作為距離度量方法,其計(jì)算公式為

(1)

其中,xi和yi分別代表數(shù)據(jù)x的第i維和數(shù)據(jù)y的第i維.

目標(biāo)函數(shù)為最小化樣本到其簇中心的距離的平方和,其計(jì)算公式為

(2)

其中,E是數(shù)據(jù)集中所有樣本的誤差平方和,c是給定的樣本,ci是簇的中心.

1.2 AdaCost算法

AdaCost算法是Fan于1999年為改進(jìn)AdaBoost算法而提出[15],其主要思想是給每一個(gè)訓(xùn)練樣本分配一個(gè)權(quán)重,并通過不斷修正權(quán)重來實(shí)現(xiàn)推進(jìn)(boosting)訓(xùn)練.分配初始權(quán)重后,用一個(gè)弱分類算法在訓(xùn)練集上進(jìn)行訓(xùn)練,訓(xùn)練后得到一個(gè)弱分類器,同時(shí)對樣本權(quán)重進(jìn)行調(diào)整,訓(xùn)練失敗的樣本權(quán)重增大,訓(xùn)練成功的樣本權(quán)重減少,使分類算法能在下一輪訓(xùn)練中集中力量對訓(xùn)練失敗的樣本進(jìn)行學(xué)習(xí).權(quán)重更新后,算法在更新的訓(xùn)練集上繼續(xù)訓(xùn)練,再調(diào)整樣本權(quán)重,循環(huán)往復(fù),從而得到一系列的弱分類器.這些弱分類器構(gòu)成組合分類器,算法采用有權(quán)重的投票方式來產(chǎn)生最終預(yù)測結(jié)果.

AdaCost算法的權(quán)重更新公式為

(3)

1.3 bagging算法

bagging 是一種基于組合的元學(xué)習(xí)算法,其基本思想是是給定一個(gè)弱學(xué)習(xí)算法和一個(gè)訓(xùn)練集S,讓該學(xué)習(xí)算法訓(xùn)練T輪,每輪的訓(xùn)練集由從初始的訓(xùn)練集中隨機(jī)取出的n個(gè)訓(xùn)練樣本組成,每個(gè)訓(xùn)練樣本在某輪訓(xùn)練集中可以出現(xiàn)多次或根本不出現(xiàn).訓(xùn)練T輪之后可得到一個(gè)預(yù)測函數(shù)序列h1,h2,…,ht,最終的預(yù)測函數(shù)h*對分類問題采用投票方式對測試樣本進(jìn)行判別.

2 基于樣本權(quán)重的欠抽樣方法

欠抽樣是一種有效處理不平衡數(shù)據(jù)的方法,但在抽樣過程中可能丟失一些具有較強(qiáng)判別性的樣本,為了彌補(bǔ)這一缺點(diǎn),本文通過引入樣本權(quán)重來反映樣本所處區(qū)域,旨在找出位于多數(shù)類中心區(qū)域的樣本,增大強(qiáng)判別性樣本被選中的概率.bagging方法是一個(gè)復(fù)合模型,它由多個(gè)分類器通過投票返回預(yù)測的類標(biāo)號,可以大幅度提高基分類器的準(zhǔn)確率,鑒于每個(gè)基分類器的性能不同,本文對各基分類器賦予權(quán)重來反映其對最終結(jié)果的貢獻(xiàn)程度.KAcBag方法主要包括樣本權(quán)重的確定與分類器加權(quán)投票2部分.

2.1 樣本權(quán)重的確定

具體思路為: 首先根據(jù)原始數(shù)據(jù)集中各類樣本的數(shù)量初始化各個(gè)樣本的權(quán)重;然后通過K-means聚類算法對數(shù)據(jù)集進(jìn)行多次聚類,根據(jù)每次聚類的結(jié)果對各個(gè)樣本的權(quán)重進(jìn)行修改,若樣本的類別與其所在簇的類別一致則權(quán)重減少,若兩者類別不一致則權(quán)重增大,且權(quán)重變化的幅度與其當(dāng)前權(quán)重的大小成正比；最后所得權(quán)重小的多數(shù)類樣本即位于多數(shù)類的中心區(qū)域,具體過程如算法2所示.

算法2. 樣本權(quán)重的確定.

輸入：帶類標(biāo)記的訓(xùn)練數(shù)據(jù)集D、聚類次數(shù)K、第1次聚類簇的個(gè)數(shù)N、簇減少的個(gè)數(shù)n;

輸出：一個(gè)帶權(quán)重的數(shù)據(jù)集.

Step1. 根據(jù)D中每類樣本的個(gè)數(shù)給各個(gè)樣本賦予權(quán)重,正類樣本數(shù)為p,負(fù)類樣本數(shù)為q,所有正類樣本權(quán)重為1/2p,負(fù)類樣本權(quán)重為1/2q;

Step2. 用K-means算法對訓(xùn)練集D進(jìn)行聚類,形成N個(gè)簇;

Step3. 計(jì)算每個(gè)簇的類別標(biāo)記：分別計(jì)算每個(gè)簇內(nèi)正負(fù)類樣本的權(quán)重和,取權(quán)重和大的類為簇的類標(biāo)記;

Step4. 根據(jù)聚類結(jié)果修改各個(gè)樣本的權(quán)重,類標(biāo)記與簇的類標(biāo)記相同則權(quán)重減小,不同則增大;

Step5. 若聚類次數(shù)小于K,修改聚類簇的個(gè)數(shù)N=N-n,并轉(zhuǎn)Step2;

Step6. 返回一個(gè)帶權(quán)重的數(shù)據(jù)集.

其中,修改權(quán)重的方法以AdaCost算法的權(quán)重更新公式為基礎(chǔ),用樣本的當(dāng)前權(quán)重替代其代價(jià)調(diào)整函數(shù)里的ci,即樣本的當(dāng)前權(quán)重為樣本的誤分代價(jià),代價(jià)調(diào)整函數(shù)定義如下：

(4)

2.2 分類器加權(quán)投票

在確定訓(xùn)練集中各樣本的權(quán)重之后,按權(quán)重大小對多數(shù)類樣本進(jìn)行抽樣,得到與少數(shù)類樣本數(shù)相同的多數(shù)類樣本；然后將抽樣所得樣本與所有少數(shù)類樣本組合成一個(gè)平衡的訓(xùn)練集,作為bagging成員分類器的訓(xùn)練數(shù)據(jù)；最后根據(jù)以每個(gè)分類器的正確率作為權(quán)值,進(jìn)行加權(quán)投票.但是因?yàn)榘礄?quán)重大小抽樣,權(quán)重越大的樣本被抽中的概率越大,本文旨在多抽取位于中心區(qū)域的樣本,而根據(jù)2.1節(jié)的權(quán)重確定算法所得的結(jié)果,權(quán)重小的樣本處于中心區(qū)域,所以在對多數(shù)類進(jìn)行抽樣之前,需要對所有多數(shù)類樣本的權(quán)重進(jìn)行一次求倒運(yùn)算,使權(quán)重小的樣本變?yōu)闄?quán)重大的樣本.具體過程如算法3所示.

算法3. 分類器加權(quán)投票.

輸入: 帶權(quán)重和類標(biāo)記的訓(xùn)練數(shù)據(jù)集D、測試數(shù)據(jù)集T、子分類器的個(gè)數(shù)K;

輸出: 帶預(yù)測類標(biāo)記的數(shù)據(jù)集.

Step1. 對D中所有多數(shù)類樣本的權(quán)重進(jìn)行求倒計(jì)算;

Step2. 按權(quán)重對D中的所有多數(shù)類樣本進(jìn)行有放回抽樣,與所有少數(shù)類樣本組成一個(gè)平衡的數(shù)據(jù)集Di;

Step3. 使用決策樹算法對Di進(jìn)行學(xué)習(xí),得到預(yù)測函數(shù)hi;

Step4. 若分類器個(gè)數(shù)小于K,轉(zhuǎn)Step2;

Step5. 使用預(yù)測函數(shù)序列h1,h2,…,hk對T中的每個(gè)樣本進(jìn)行投票表決.

其中,每個(gè)預(yù)測函數(shù)的表決權(quán)重為

error(hi)為預(yù)測函數(shù)hi的錯(cuò)誤率,即hi誤分Di中每個(gè)樣本的權(quán)重和,其計(jì)算公式為

3 實(shí)驗(yàn)與分析

3.1 分類的評價(jià)方法

傳統(tǒng)的分類器采用精度指標(biāo)來衡量分類性能,但在不平衡數(shù)據(jù)集中,多數(shù)類樣例個(gè)數(shù)遠(yuǎn)遠(yuǎn)多于少數(shù)類,傳統(tǒng)分類算法預(yù)測會傾向于多數(shù)類,如把所有樣例分為多數(shù)類,依然會獲得很高的分類精度,但是卻不能識別一個(gè)少數(shù)類,故分類精度不能正確反映不平衡數(shù)據(jù)集的分類結(jié)果.針對不平衡數(shù)據(jù),很多學(xué)者提出F-measure[8],G-mean[20]等評價(jià)方法,其大多建立在混淆矩陣(如表1所示)的基礎(chǔ)上.假設(shè)表1中正類和負(fù)類分別代表少數(shù)類和多數(shù)類,則TP和TN分別表示正確分類的少數(shù)樣本和多數(shù)樣本的個(gè)數(shù),FP和FN分別表示誤分類的少數(shù)類樣本和多數(shù)類樣本的個(gè)數(shù).

Table1 Confusion Matrix for Two-class Problem

F-measure是一種不平衡數(shù)據(jù)分類問題的評價(jià)準(zhǔn)則,其定義[8]為

其中,Recall為查全率;Precision為查準(zhǔn)率;β表示Precision與Recall的相對重要性,在本文實(shí)驗(yàn)中β=1.只有當(dāng)查全率和查準(zhǔn)率都較大時(shí),F-measure才會相應(yīng)地較大.因此,F-measure可以合理地評價(jià)分類器對于少數(shù)類的分類性能[21].即令：

G-mean是一種衡量數(shù)據(jù)集整體分類性能的評價(jià)指標(biāo),其定義如下[20]：

G-mean準(zhǔn)則是在保持正、負(fù)類分類精度平衡的情況下最大化2類的精度.假定對負(fù)類的分類精度很高,而對正類的分類精度很低,則會導(dǎo)致低的G-mean值,而只有當(dāng)兩者都較高時(shí),才會得到高的G-mean值.因此,G-mean準(zhǔn)則衡量的是數(shù)據(jù)集整體的分類性能[21].本文將使用F-measure,G-mean來衡量少數(shù)類及數(shù)據(jù)集整體的分類性能.

3.2 非參數(shù)統(tǒng)計(jì)檢驗(yàn)方法

F-measure和G-mean是從單個(gè)數(shù)據(jù)集上衡量不同算法的分類性能,為了從整體上比較各種算法的性能優(yōu)劣,本文將非參數(shù)統(tǒng)計(jì)檢驗(yàn)方法中的Friedman檢驗(yàn)[22]和Wilcoxon符號秩檢驗(yàn)[22]引入到分類算法的性能評估中.

Friedman檢驗(yàn)用于判斷多種分類算法是否存在顯著差異,其原假設(shè)是：多種分類算法無顯著差異,具體檢驗(yàn)步驟為:

1) 將各區(qū)組內(nèi)數(shù)據(jù)由小到大分別編秩,遇相同數(shù)值取平均秩次;

2) 計(jì)算各分類算法的秩和Ri、平均秩;

3) 計(jì)算檢驗(yàn)統(tǒng)計(jì)量：

3×n×(k+1),

其中，n是區(qū)組的數(shù)量,k是分類算法的數(shù)量;

4) 利用統(tǒng)計(jì)軟件或查表確定P值,如果概率P值小于給定的顯著性水平,則拒絕原假設(shè),認(rèn)為各分類算法之間存在顯著差異,反之則不能拒絕原假設(shè).

Wilcoxon符號秩檢驗(yàn)是用于檢驗(yàn)2種分類器算法之間是否存在明顯差異問題,其具體檢驗(yàn)步驟為: 1)計(jì)算2種分類器算法在每一組數(shù)據(jù)上的性能差值,并將差值的絕對值按從小到大的順序編秩;2)計(jì)算秩和,令R1為第1個(gè)算法優(yōu)于第2個(gè)算法的秩和,R2為第2個(gè)算法優(yōu)于第1個(gè)算法的秩和;3)計(jì)算T值,T=min(R1,R2);4)根據(jù)所得T值查表或統(tǒng)計(jì)軟件確定P值,若P小于給定的顯著性水平,則認(rèn)為2種算法具有顯著差異.在本文中,使用SPSS軟件來進(jìn)行Friedman檢驗(yàn)和Wilcoxon符號秩檢驗(yàn)分析.

3.3 UCI數(shù)據(jù)

為了檢驗(yàn)本文抽樣方法的有效性,選擇19組少數(shù)類和多數(shù)類樣本比例不平衡的且具有不同實(shí)際應(yīng)用背景的UCI數(shù)據(jù)*http://www.ics.uci.edu/～mlearn/ML Repository.html,對于含有多個(gè)類別的數(shù)據(jù),選擇數(shù)量最少的類作為少數(shù)類,并將其他類合并為一個(gè)大的多數(shù)類.各數(shù)據(jù)集的基本信息如表2所示,Ratio為數(shù)據(jù)集的不平衡程度,即Ratio等于多數(shù)類樣本數(shù)除以少數(shù)類樣本數(shù).

為了使實(shí)驗(yàn)結(jié)果更具客觀性,采用10折交叉驗(yàn)證的方法對分類效果進(jìn)行驗(yàn)證,即將數(shù)據(jù)集中的數(shù)據(jù)隨機(jī)等分為10份,依次取其中1份作為測試集,其余9份作為訓(xùn)練集,然后運(yùn)行相應(yīng)的分類方法對訓(xùn)練集中的數(shù)據(jù)進(jìn)行分類學(xué)習(xí),并用測試集進(jìn)行測試,相應(yīng)的10次測試結(jié)果的平均值作為1次10折交叉驗(yàn)證的結(jié)果.

在實(shí)驗(yàn)中,采用weka軟件[23]中SimpleKMeans聚類算法對數(shù)據(jù)進(jìn)行多次聚類,設(shè)聚類次數(shù)為6次,第1次聚類的簇的個(gè)數(shù)為訓(xùn)練集樣本數(shù)的10%左右,簇減少的步長根據(jù)初始簇的個(gè)數(shù)和聚類次數(shù)確定,其取值需確保最后1次聚類的簇的個(gè)數(shù)大于0,weka軟件中的J48決策樹算法作為基分類器,算法參數(shù)使用軟件中的默認(rèn)參數(shù)設(shè)置.將實(shí)驗(yàn)結(jié)果與RBBag,OvBag,SmBag,oNBBag2,uNBBag0.5這5種bagging技術(shù)與抽樣方法相結(jié)合的算法進(jìn)行對比,表3和表4分別列出6種方法在19個(gè)UCI數(shù)據(jù)集上的少數(shù)類F-measure值和數(shù)據(jù)集整體的G-mean值,其中作為對比的5種算法的實(shí)驗(yàn)結(jié)果來自文獻(xiàn)[17],表格中的最后一行為通過Friedman檢驗(yàn)計(jì)算的各個(gè)算法的平均秩,其值越小證明算法的性能越好.表5列出了6種算法在F-measure和G-mean上兩兩進(jìn)行Wilcoxon符號秩檢驗(yàn)的結(jié)果(P值),顯著性水平設(shè)置為0.05.

Table 2 Information of Data Sets

Table3 Minority Class F-measure Comparison of Different Sampling Algorithms

Note: The number between brackets represents the rank of the algorithm on this data set.

Table 4 Minority Class G-mean Comparison of Different Sampling Algorithms

Note: The number between brackets represents the rank of the algorithm on this data set.

Table 5 The Wilcoxon Sign Rank Set for Pairwise Comparisons of Different Algorithms

由表3和表4可以看出,KAcBag算法在2個(gè)性能指標(biāo)F-measure和G-mean上的平均秩最小,在breast-w,new-thyroid,credit-g,haberman,cleveland,breast-cancer,transfusion,postoperative,solar-flare,cmc上2個(gè)評價(jià)指標(biāo)均優(yōu)于其他算法,在pima,ecoli,abalone,yeast上有1個(gè)評價(jià)指標(biāo)高于其他算法,并且另1個(gè)評價(jià)指標(biāo)也是良好的,在ionosphere,hepatitis,balance-scale上評價(jià)指標(biāo)略低于其他5種算法的最優(yōu)值.對ecoli,abalone,yeast,balance-scale,car,vehicle這6個(gè)數(shù)據(jù)集,可以明顯地看出過抽樣方法的結(jié)果要優(yōu)于欠抽樣方法,這是因?yàn)閿?shù)據(jù)集中少數(shù)類樣本過少且不平衡程度較高,使得用欠抽樣方法得到的平衡數(shù)據(jù)集丟失了過多的多數(shù)類樣本,造成分類性能降低,本文方法雖在這類數(shù)據(jù)集上分類性能略低于OvBag,SmBag,oNBBag2這3種過抽樣方法,但其在1個(gè)或2個(gè)評價(jià)指標(biāo)上優(yōu)于RBBag和uNBBag0.5這2種欠抽樣方法.

從統(tǒng)計(jì)檢驗(yàn)的角度來看,在F-measure上的Friedman檢驗(yàn)結(jié)果為0.047,略小于顯著性水平0.05,說明6種算法在此項(xiàng)指標(biāo)上顯著性差異不大.在G-mean上的Friedman檢驗(yàn)結(jié)果小于0.001,說明6種算法在此項(xiàng)指標(biāo)上有顯著性差異,由表5的Wilcoxon符號秩檢驗(yàn)結(jié)果可以明顯看出,KAcBag算法在G-mean這項(xiàng)指標(biāo)上效果優(yōu)于其他5種算法(P<0.05),RBBag和uNBBag0.5算法無顯著差異(P=0.629),但均優(yōu)于另外3種欠抽樣方法(P<0.05),3種欠抽樣方法中以oNBBag2算法為最優(yōu).

為了觀察聚類次數(shù)和簇減少的步長這2個(gè)參數(shù)的設(shè)定對KAcBag算法的影響,選擇solar-flare數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù),它具有較高的不平衡比例和較大的樣本個(gè)數(shù).圖1給出了當(dāng)簇減少的步長為6且其他參數(shù)不變,聚類次數(shù)為3,6,9,12,15時(shí),solar-flare數(shù)據(jù)集的F-measure值和G-mean值的變化情況.圖2給出了當(dāng)聚類次數(shù)為6且其他參數(shù)不變,簇減少的步長為3,6,9,12,15,18時(shí),2個(gè)評價(jià)指標(biāo)的變化趨勢.

由圖1和圖2可知,在聚類次數(shù)和簇減少步長2個(gè)參數(shù)均設(shè)置合適的情況下,2個(gè)評價(jià)指標(biāo)可以取得較好的結(jié)果.

Fig. 1 Effect of different clustering numbers on KAcBag.圖1 不同聚類次數(shù)對KAcBag方法的影響

Fig. 2 Effect of different clustering reduction step size on KAcBag.圖2 不同簇減少步長對KAcBag方法的影響

3.4 用戶換機(jī)數(shù)據(jù)

在手機(jī)用戶數(shù)據(jù)集中,樣本數(shù)量分布存在嚴(yán)重的非平衡性,非換機(jī)樣本數(shù)是換機(jī)樣本數(shù)的幾十倍,是一個(gè)典型的不平衡數(shù)據(jù)集.本文針對運(yùn)營商用戶的某一個(gè)月產(chǎn)生的數(shù)據(jù)情況,應(yīng)用本文方法進(jìn)行處理,得到?jīng)Q策規(guī)則并對另一個(gè)月的用戶數(shù)據(jù)進(jìn)行匹配,從而進(jìn)行換機(jī)意向預(yù)測.實(shí)驗(yàn)設(shè)計(jì)如下：

學(xué)習(xí)集為某電信運(yùn)營商4月20萬按自然比例(非換機(jī)∶換機(jī)=27∶1)分布的數(shù)據(jù)記錄,測試集為5月40萬按1∶1分布的數(shù)據(jù)記錄.通過特征選取和專家經(jīng)驗(yàn)相結(jié)合,選擇了19個(gè)屬性作為預(yù)測模型的輸入特征,此外,鑒于在學(xué)習(xí)過程中各屬性之間相互獨(dú)立,但在實(shí)際情況中用戶近3個(gè)月的貢獻(xiàn)收入、通話時(shí)間及流量聯(lián)系緊密,所以人為添加了9個(gè)屬性來衡量3個(gè)月間屬性的變化情況,具體描述如表6所示:

Table 6 Description of User Data Attribute

Continued (Table 6)

首先對連續(xù)屬性按照專家經(jīng)驗(yàn)知識進(jìn)行離散化處理,并利用粗糙集作屬性約簡,得到最終用于學(xué)習(xí)的25個(gè)屬性: jiling,old_online_month,AGE,countimei,avg_hjzhouqi,tac_month,arpu1,arpu2,mou1,mou2,mou3,dou1,dept,new_flag,price_flag,arpu12,arpu23,mou12,mou23,dou12,dou23,arpu,mou,dou,class,然后采用KAcBag算法進(jìn)行學(xué)習(xí),并與EBBag算法(隨機(jī)欠抽樣+bagging技術(shù))進(jìn)行對比,實(shí)驗(yàn)結(jié)果如表7所示,黑體表示評價(jià)指標(biāo)在2種算法上的最大值.

Table 7 Experimental Results

由表7可以看出,本文的抽樣方法較隨機(jī)欠抽樣方法在2項(xiàng)指標(biāo)上有明顯的提高,能有效識別出換機(jī)用戶,并降低非換機(jī)用戶的誤分率,特別對具有大量樣本的數(shù)據(jù)集來說,1個(gè)百分點(diǎn)的提高會帶來非常可觀的收益,說明基樣本權(quán)重的欠抽樣方法在預(yù)測用戶換機(jī)等追求正確率的工程問題下應(yīng)用前景廣闊.

4 結(jié)束語

在實(shí)際應(yīng)用領(lǐng)域中存在著大量的不平衡數(shù)據(jù)集,然而傳統(tǒng)的機(jī)器學(xué)習(xí)算法對少數(shù)類的識別率較低.本文提出一種基于樣本權(quán)重的不平衡數(shù)據(jù)欠抽樣方法,該方法通過樣本權(quán)重來刻畫多數(shù)類樣本所處的區(qū)域,在多次聚類后確定各樣本的權(quán)重；然后根據(jù)權(quán)重大小抽取對多數(shù)類樣本進(jìn)行欠抽樣處理,使位于中心區(qū)域的多數(shù)類樣本較容易被抽中,與所有少數(shù)類樣本組成平衡的訓(xùn)練集,提高少數(shù)類的識別率,并融合集成學(xué)習(xí)的思想,通過分類器加權(quán)投票提高數(shù)據(jù)集整體的分類性能.在UCI數(shù)據(jù)集和移動用戶換機(jī)數(shù)據(jù)上的實(shí)驗(yàn)表明,本文提出的抽樣方法充分利用了少數(shù)類和多數(shù)類的分布信息,抽樣所得樣本較好地保持了多數(shù)類信息,同時(shí)有效縮小了數(shù)據(jù)集規(guī)模,提高了分類器的分類性能.

在調(diào)用 KAcBag方法時(shí),為了選取能夠取得最佳預(yù)測性能的分類器,需要設(shè)置恰當(dāng)?shù)木垲惔螖?shù)、類簇的個(gè)數(shù)以及簇減少的步長,本文主要是通過大量的實(shí)驗(yàn)來得到最優(yōu)結(jié)果,關(guān)于如何根據(jù)訓(xùn)練集的樣本數(shù)及類分布特點(diǎn)自適應(yīng)地確定參數(shù),是后續(xù)研究的重點(diǎn).

[1]Xiao J, Xie L, He C, et al. Dynamic classifier ensemble model for customer classification with imbalanced class distribution[J]. Expert Systems with Applications, 2012, 39(3): 3668-3675

[2]Yu H, Ni J, Zhao J. ACOSampling: An ant colony optimization-based undersampling method for classifying imbalanced DNA microarray data[J]. Neurocomputing, 2013, 101: 309-318

[3]Wang S, Yao X. Using class imbalance learning for software defect prediction[J]. IEEE Trans on Reliability, 2013, 62(2): 434-443

[4]Ma Z, Yan R, Yuan D, et al. An imbalanced spam mail filtering method[J]. International Journal of Multimedia and Ubiquitous Engineering, 2015, 10(3): 119-126

[5]Kim H, Howland P, Park H. Dimension reduction in text classification with support vector machines[J]. Journal of Machine Learning Research, 2005, 6(1): 37-53

[6]Maes F, Vandermeulen D, Suetens P. Medical image registration using mutual information[J]. Proceedings of the IEEE, 2003, 91(10): 1699-1722

[7]Chawla N V, Bowyer K W, Hall L O, et al. SMOTE: Synthetic minority over-sampling technique[J]. Journal of Artificial Intelligence Research, 2002, 16(1): 321-357

[8]Han H, Wang W Y, Mao B H. Borderline-SMOTE: A new over-sampling method in imbalanced data sets learning[C] //Proc of the Int Conf on Intelligent Computing. Berlin: Springer, 2005: 878-887

[9]Kubat M, Matwin S. Addressing the curse of imbalanced training sets: One-sided selection[C] //Proc of the 14th Int Conf on Machine Learning. San Francisco, CA: Morgan Kaufmann, 1997: 179-186

[10]Yen S J, Lee Y S. Cluster based under-sampling approaches for imbalanced data distributions[J]. Expert Systems with Applications, 2009, 36(3): 5718-5727

[11]Zhang S. Decision tree classifiers sensitive to heterogeneous costs[J]. Journal of Systems and Software, 2012, 85(4): 771-779

[12]Park Y, Luo L, Parhi K K, et al. Seizure prediction with spectral power of EEG using cost-sensitive support vector machines[J]. Epilepsia, 2011, 52(10): 1761-1770

[13]Breiman L. Bagging predictors[J]. Machine Learning, 1996, 24(2): 23-140

[14]Freund Y, Schapire R E. A decision-theoretic generalization of on-line learning and an application to boosting[J]. Journal of Computer and System Sciences, 1997, 55(1): 119-139

[15]Fan W, Stolfo S J, Zhang J, et al. AdaCost: Misclassification cost-sensitive boosting[C] //Proc of the 16th Int Conf on Machine Learning. San Francisco, CA: Morgan Kaufmann, 1999: 97-105

[16]Hido S, Kashima H, Takahashi Y. Roughly balanced bagging for imbalanced data[J]. Statistical Analysis and Data Mining, 2009, 2(5/6): 412-426

[17]Blaszczynski J, Stefanowski J. Neighbourhood sampling in bagging for imbalanced data[J]. Neurocomputing, 2015, 150: 529-542

[18]Wang S, Yao X. Diversity analysis on imbalanced data sets by using ensemble models[C] //Proc of IEEE Symp on Computational Intelligence and Data Mining. Piscataway, NJ: IEEE, 2009: 324-331

[19]MacQueen J. Some methods for classification and analysis of multivariate observations[C] //Proc of the 15th Berkeley Symp on Mathematical Statistics and Probability. Berkeley, CA: University of California Press, 1967: 281-297

[20]Su C T, Chen L S, Yih Y. Knowledge acquisition through information granulation for imbalanced data[J]. Expert Systems with Applications, 2006, 31(3): 531-541

[21]Chen Si, Guo Gongde, Chen Lifei. Clustering ensembles based classification method for imbalanced data sets[J]. Pattern Recognition and Artificial Intelligence, 2010, 23(6): 772-780 (in Chinese)

(陳思, 郭躬德, 陳黎飛. 基于聚類融合的不平衡數(shù)據(jù)分類方法[J]. 模式識別與人工智能, 2010, 23(6): 772-780)

[22]Japkowicz N, Shah M. Evaluating Learning Algorithms: A Classification Perspective[M]. Cambridge, UK: Cambridge University Press, 2011

[23]Witten I H, Frank E. Data Mining: Practical Machine Learning Tools and Techniques[M]. San Francisco, CA: Morgan Kaufmann, 2005

Xiong Bingyan, born in 1991. Master. Her main research interests include data mining and rough set.

Wang Guoyin, born in 1970. Professor and PhD supervisor. Member of China Computer Federation. His main research interests include rough set, neural network, machine learning and data mining (wanggy@cqupt.edu.cn).

Deng Weibin, born in 1978. PhD and associate professor. His main research interests include intelligent information processing and uncertainty decision (dengwb@cqupt.edu.cn).

Under-Sampling Method Based on Sample Weight for Imbalanced Data

Xiong Bingyan, Wang Guoyin, and Deng Weibin

(ChongqingKeyLaboratoryofComputationalIntelligence,ChongqingUniversityofPostsandTelecommunications,Chongqing400065)

Imbalanced data exists widely in the real world, and its classification is a hot topic in data mining and machine learning. Under-sampling is a widely used method in dealing imbalanced data set and its main idea is choosing a subset of majority class to make the data set balanced. However, some useful majority class information may be lost. In order to solve the problem, an under-sampling method based on sample weight for imbalance problem is proposed, named as KAcBag (K-means AdaCost bagging). In this method, sample weight is introduced to reveal the area where the sample is located. Firstly, according to the sample scale, a weight is made for each sample and is modified after clustering the data set. The samples which have less weight in the center of majority class. Then some samples are drawn from majority class in accordance with the sample weight. In the procedure, the samples in the center of majority class can be selected easily. The sampled majority class samples and all the minority class samples are combined as the training data set for a component classifier. After that, we can get several decision tree sub-classifiers. Finally, the prediction model is constructed based on the accuracy of each sub-classifiers. Experimental tests on nineteen UCI data sets and telecom user data show that KAcBag can make the selected samples have more representativeness. Based on that, this method can improve the the classification performance of minority class and reduce the scale of the problem.

imbalanced data; under-sampling; sample weight; clustering; ensemble learning

2015-06-19；

2015-10-29

國家自然科學(xué)基金項(xiàng)目(61272060);教育部人文社科規(guī)劃基金項(xiàng)目(15XJA630003);重慶市教委科學(xué)技術(shù)研究項(xiàng)目(KJ1500416);重慶市自然科學(xué)基金項(xiàng)目(CSTC2013jjB40003)

王國胤(wanggy@cqupt.edu.cn)

TP391

This work was supported by the National Natural Science Foundation of China (61272060), the Social Science Foundation of the Chinese Education Commission (15XJA630003), the Scientific and Technological Research Program of Chongqing Municipal Education Commission (KJ1500416), and the Key Natural Science Foundation of Chongqing (CSTC2013jjB40003).