張喜龍，韓 萌，陳志強(qiáng)，武紅鑫，李慕航

(北方民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，寧夏 銀川 750021)

1 引言

從非平穩(wěn)數(shù)據(jù)流中學(xué)習(xí)仍然是目前數(shù)據(jù)挖掘領(lǐng)域研究的重點(diǎn)，決策算法應(yīng)該考慮到類別之間數(shù)量的不平衡性。真實(shí)的數(shù)據(jù)流還會(huì)表現(xiàn)出不斷變化的類不平衡比率，從而進(jìn)一步影響分類性能。在數(shù)據(jù)流處理中，不平衡數(shù)據(jù)現(xiàn)象變得至關(guān)重要，因?yàn)樗霈F(xiàn)在各個(gè)領(lǐng)域，例如天氣數(shù)據(jù)預(yù)測(cè)、異常檢測(cè)和社交媒體挖掘等[1]。具有多數(shù)類數(shù)據(jù)的類別稱為多數(shù)類，而其它類別稱為少數(shù)類。

近些年隨著研究人員對(duì)不平衡數(shù)據(jù)的深入研究，集成學(xué)習(xí)與重采樣技術(shù)的結(jié)合屢見不鮮。Wang等[2]改進(jìn)了基于在線的Bagging集成的過采樣OOB(Oversampling based Online Bagging)和欠采樣UOB(Undersampling based Online Bagging)算法。作者利用時(shí)間衰減度量對(duì)OOB和UOB 2種集成學(xué)習(xí)方法進(jìn)行改進(jìn)，以克服在線類不平衡問題。Wu等[3]提出了一個(gè)重要性采樣方法，即動(dòng)態(tài)特征組加權(quán)框架用于對(duì)不平衡數(shù)據(jù)進(jìn)行分類DFGW-IS(Dynamic Feature Group Weighting framework for classifying data Streams of Imbalanced distribution)。通過使用帶有子分類器的特征組進(jìn)行加權(quán)集成去處理不斷變化的數(shù)據(jù)概念，其中子分類器通過它自身的分類性能和穩(wěn)定性進(jìn)行加權(quán)。為了解決概念漂移和類不平衡問題，Chen等[4]提出了遞歸集成方法REA(Recursive Ensemble Approach)。該方法有選擇地挑選以前的少數(shù)類實(shí)例加入當(dāng)前訓(xùn)練的塊，以平衡類分布，同時(shí)使用動(dòng)態(tài)加權(quán)適應(yīng)概念漂移。同時(shí),Lu等[5]提出了一種基于塊的增量方法,稱為動(dòng)態(tài)多數(shù)加權(quán)不平衡學(xué)習(xí)DWMIL(Dynamic Weighted Majority for Imbalance Learning)算法。該算法使用集成框架對(duì)基分類器動(dòng)態(tài)加權(quán)，以處理帶有概念漂移和類的數(shù)據(jù)流不平衡問題。

盡管現(xiàn)有的集成分類算法能夠很好地處理類不平衡問題，但在不平衡數(shù)據(jù)流的集成分類中還存在很多問題有待解決。例如,如何解決帶有概念漂移的不平衡數(shù)據(jù),基分類器如何分配合適的權(quán)值等。針對(duì)以上問題，本文提出了一種新的集成分類算法，主要工作如下所示：

(1)提出了一種新的基于Hellinger距離的Boosting集成加權(quán)算法BCA-HD(Boosting Classification Algorithm for imbalanced drift data stream based on Hellinger Distance)。算法采用實(shí)例權(quán)重和分類器權(quán)重組合的方法進(jìn)行分類，首先使用Hellinger距離計(jì)算實(shí)例之間的權(quán)重，然后使用分類誤差計(jì)算分類器的權(quán)重，通過分類器的動(dòng)態(tài)更新方式去適應(yīng)不平衡數(shù)據(jù)流中的概念漂移。

(2)提出的BCA-HD算法在底層使用了集成算法SMOTEBoost(Synthetic Minority Oversampling TEchnique Boost)[6]作為動(dòng)態(tài)更新的基分類器，該集成分類器通過重采樣的方式處理不平衡的數(shù)據(jù)，同時(shí)集成分類器在適應(yīng)概念漂移方面比單分類器有著更好的魯棒性。

實(shí)驗(yàn)表明，BCA-HD算法與典型的9種對(duì)比算法相比，它能更好地適應(yīng)突變型和漸變型的概念漂移，同時(shí)對(duì)不平衡數(shù)據(jù)流分類性能也更好。

2 相關(guān)工作

2.1 不平衡數(shù)據(jù)流分類

隨著研究人員對(duì)不平衡數(shù)據(jù)研究的深入，它的解決方案也變得更加多元化。目前不平衡數(shù)據(jù)分類研究主要涉及數(shù)據(jù)重采樣和算法創(chuàng)新。

數(shù)據(jù)重采樣是通過丟棄一些多數(shù)類樣本(即欠采樣技術(shù))或添加新的少數(shù)類樣本(即過采樣技術(shù))來(lái)重新平衡類的分布[7]。在欠采樣技術(shù)方面，隨機(jī)欠采樣是最簡(jiǎn)單的方法，它使用隨機(jī)方式丟棄多數(shù)類樣本。鑒于可能會(huì)去除一些有用的多數(shù)類樣本，研究人員設(shè)計(jì)了很多有效的欠采樣方法。在數(shù)據(jù)過采樣方面，最直接的方法是隨機(jī)過采樣，它隨機(jī)復(fù)制原始少數(shù)類樣本以引入少數(shù)類樣本。過采樣的一個(gè)顯著缺點(diǎn)是它會(huì)增加過度擬合的風(fēng)險(xiǎn)，為此研究人員提出了合成少數(shù)類樣本的過采樣技術(shù)即SMOTE[8]。在特征空間中生成合成樣本，通過在2個(gè)相鄰的原始少數(shù)類樣本之間進(jìn)行插值，創(chuàng)建的新少數(shù)類樣本將不同于現(xiàn)有的少數(shù)類樣本。

在算法創(chuàng)新上集成學(xué)習(xí)是目前研究較多的方向之一，集成學(xué)習(xí)旨在通過組合多個(gè)基分類器來(lái)提高分類性能。由于其面向準(zhǔn)確性的設(shè)計(jì)，標(biāo)準(zhǔn)集成學(xué)習(xí)算法不適合類不平衡學(xué)習(xí)。研究人員經(jīng)常結(jié)合重采樣方法來(lái)開發(fā)基于集成的解決方案，以處理類不平衡問題。SMOTEBoost是第1個(gè)基于Boosting解決類不平衡問題的算法。在該算法中，SMOTE被嵌入AdaBoost.M2[9]的學(xué)習(xí)框架中，通過生成新的合成樣本來(lái)隱式增加少數(shù)類樣本的權(quán)重。最近Zyblewski等[10]提出結(jié)合動(dòng)態(tài)集成和預(yù)處理技術(shù)的框架來(lái)處理高度不平衡的數(shù)據(jù)流，提出了使用分層Bagging分類器對(duì)少數(shù)類和多數(shù)類進(jìn)行替換抽樣的方法。

2.2 概念漂移問題

在真實(shí)世界中，數(shù)據(jù)流的生成通常是在非平穩(wěn)環(huán)境中進(jìn)行，這意味著數(shù)據(jù)的底層分布可以隨時(shí)間任意更改。在這樣的非平穩(wěn)環(huán)境中，數(shù)據(jù)流的概念和數(shù)據(jù)分布隨時(shí)間而變化，這種現(xiàn)象被稱為概念漂移[11]。下面從概率的角度來(lái)定義概念漂移，當(dāng)2個(gè)時(shí)間點(diǎn)t0和t1的聯(lián)合概率發(fā)生變化時(shí)就會(huì)出現(xiàn)概念漂移，即pto(X,yi)≠pt1(X,yi)。

根據(jù)漂移變化的速度,概念漂移可分為突變、漸近、重復(fù)和增量漂移，如圖1所示。如果一種數(shù)據(jù)分布的來(lái)源被另一種數(shù)據(jù)分布的來(lái)源代替，稱為突變型。當(dāng)開始觀察到兩種數(shù)據(jù)分布混合時(shí)，這種漂移被稱為增量型。當(dāng)舊數(shù)據(jù)分布的數(shù)據(jù)實(shí)例開始減少，新數(shù)據(jù)分布的數(shù)據(jù)實(shí)例開始增加時(shí)，這種漂移被稱為漸變型。重復(fù)漂移是指新概念的實(shí)例或舊概念的實(shí)例在特定時(shí)間之后開始重復(fù)出現(xiàn)的情況[12]。在不平衡數(shù)據(jù)流中，概念漂移的體現(xiàn)已經(jīng)簡(jiǎn)化到了不平衡比率的變化隨著時(shí)間變化少數(shù)類或多數(shù)類轉(zhuǎn)變?yōu)槎鄶?shù)類或少數(shù)類。

Figure 2 Illustration of BCA-HD圖2 BCA-HD示意圖

3 BCA-HD算法

通過對(duì)文獻(xiàn)的分析可以看出，不平衡數(shù)據(jù)流分類算法表現(xiàn)不佳，而且大多數(shù)工作沒有解決分類模型運(yùn)行過程中可能出現(xiàn)的概念漂移問題。因此，所提出的解決方案應(yīng)該對(duì)分類任務(wù)的參數(shù)變化具有很高的適應(yīng)性，基于分類器集成方法是目前最受關(guān)注和研究較多的方向之一。同時(shí)，提出的解決方案應(yīng)該考慮數(shù)據(jù)分布的局部特征和類之間的不平衡。

3.1 BCA-HD集成算法框架

在目前新的理論方面，Du等[13]提出了在線學(xué)習(xí)處理不平衡數(shù)據(jù)流的方法，通過改進(jìn)在線Bagging技術(shù)來(lái)進(jìn)一步提高分類性能。作者對(duì)少數(shù)類樣本和多數(shù)類樣本采用不同的泊松分布參數(shù)λ來(lái)區(qū)分樣本之間的采樣概率，以進(jìn)一步平衡數(shù)據(jù)。在計(jì)算分類器的權(quán)重時(shí)，不是采用分類器的分類誤差而是用泛化誤差計(jì)算權(quán)重。該算法沒有考慮帶有概念漂移的不平衡數(shù)據(jù)流的處理，同時(shí)加權(quán)的方式是以分類器為主，在分類器的更新方面也沒有以動(dòng)態(tài)的方式去實(shí)現(xiàn)整體更新。基于以上算法的啟發(fā)和分析，本文提出的算法考慮了概念漂移的存在，同時(shí)在加權(quán)方面引進(jìn)了實(shí)例加權(quán)和分類器加權(quán)，以實(shí)現(xiàn)分類器的動(dòng)態(tài)更新。

為了解決帶有概念漂移的不平衡數(shù)據(jù)流問題，本文提出了基于Hellinger距離的Boosting集成分類算法BCA-HD。該算法主要解決2大核心問題：概念漂移和不平衡，該集成算法框架處理數(shù)據(jù)的全部過程如圖2所示。算法在訓(xùn)練階段，數(shù)據(jù)流以塊的形式輸入內(nèi)存中，表示為S={D(1),…,D(t-1),D(t)},輸入的數(shù)據(jù)塊依次分配給當(dāng)前集成分類算法SMOTEBoost，該算法將作為BCA-HD算法的基分類器來(lái)訓(xùn)練數(shù)據(jù)。分類器內(nèi)部采用經(jīng)典的重采樣技術(shù)SMOTE，它使用差值方法來(lái)合成新的少數(shù)類樣本，以平衡當(dāng)前的不平衡數(shù)據(jù)集生成新的平衡后的數(shù)據(jù)塊S′，然后使用當(dāng)前分類器進(jìn)行訓(xùn)練。在概念漂移的處理方面，算法采用實(shí)例級(jí)和分類器級(jí)的加權(quán)組合方式，權(quán)重大小代表對(duì)當(dāng)前概念的重視程度。算法的集成過程是一種分類器的動(dòng)態(tài)更新方式，這個(gè)過程可以讓分類器更好地學(xué)習(xí)。隨著分類器的創(chuàng)建，如果當(dāng)前分類器的權(quán)重沒有低于用戶設(shè)置的閾值將直接加入分類器池π，否則當(dāng)前基分類器會(huì)被刪除，同時(shí)這個(gè)分類器會(huì)一直處于一種動(dòng)態(tài)更新的過程。在測(cè)試階段，生成的集成分類器根據(jù)多數(shù)投票原則對(duì)輸入的數(shù)據(jù)進(jìn)行預(yù)測(cè)分類。

3.2 BCA-HD算法訓(xùn)練過程

(1)

由于Hellinger距離公式對(duì)不平衡狀態(tài)下的數(shù)據(jù)具有不敏感性，BCA-HD算法使用該公式作為實(shí)例之間相似度的度量。這種相似度的度量對(duì)時(shí)刻發(fā)生概念變化的數(shù)據(jù)來(lái)說是一種友好的檢測(cè)方法，通過計(jì)算實(shí)例之間的距離權(quán)重然后分配給分類器來(lái)體現(xiàn)其對(duì)當(dāng)前數(shù)據(jù)的重視程度。在分類器級(jí)，使用分類器的誤差來(lái)體現(xiàn)當(dāng)前學(xué)習(xí)數(shù)據(jù)的好壞程度，從而能進(jìn)一步更新分類器的權(quán)重，如式(2)所示：

(2)

(3)

(4)

其中，α為比例參數(shù)，當(dāng)分類器池中的基分類器的更新權(quán)重低于閾值θ時(shí)，則進(jìn)行刪除操作。如果要?jiǎng)h除分類器，一個(gè)原因可能是分類器是在一個(gè)非常早的時(shí)間上進(jìn)行的訓(xùn)練，先前訓(xùn)練的基分類器無(wú)法對(duì)當(dāng)前的數(shù)據(jù)概念進(jìn)行擬合，它的誤差變大導(dǎo)致其權(quán)重會(huì)減小，表現(xiàn)在式(3)中總的求和權(quán)重降低。另一個(gè)原因是最近塊上數(shù)據(jù)的概念發(fā)生變化，使得分類器的測(cè)試誤差很大 ，導(dǎo)致權(quán)重變小被刪除。如果數(shù)據(jù)流非常長(zhǎng)，則BCA-HD僅在集合中保留有限數(shù)量的分類器，而不會(huì)遇到存儲(chǔ)不夠的問題。分類器使用式(5)最終預(yù)測(cè)輸入的數(shù)據(jù)分布D(t)上的實(shí)例xi的分類結(jié)果。

(5)

其中，sign(·)為符號(hào)函數(shù)。

算法1是本文提出的BCA-HD集成分類算法的偽代碼，該算法是基于塊學(xué)習(xí)的方法,對(duì)于概念漂移有很好的適應(yīng)性。

算法1BCA-HD

步驟1傳入數(shù)據(jù)流S;

步驟3創(chuàng)建基分類器C；//(call算法2)

C←SMOTEBoost(D(t))，π←{C};

步驟4fori←1 toNdo//遍歷實(shí)例

步驟5使用當(dāng)前集成分類器C(t)預(yù)測(cè)實(shí)例xi;

步驟9else取所有實(shí)例權(quán)重的平均值

步驟10forj←1 tomdo//遍歷分類器

步驟16m←|C(t)|；

步驟17創(chuàng)建新的基分類器：

C←SMOTEBoost(D(t))//call算法2

步驟18m←m+1;

步驟19π←π∪{C};

步驟21endif

步驟22endfor

步驟23 endfor

3.3 不平衡數(shù)據(jù)的處理

在分類器的創(chuàng)建上使用了集成分類算法作為BCA-HD算法的基分類器。SMOTEBoost算法是一個(gè)很健壯的算法，該算法數(shù)據(jù)采樣部分使用SMOTE重采樣技術(shù)處理不平衡數(shù)據(jù)。SMOTEBoost的偽代碼如算法2所示。

算法2SMOTEBoost

輸出：輸出集成分類器C。

步驟1D1(i)=1/N,i=1,…,N;//初始數(shù)據(jù)分布。

步驟2 forj←1 tomdo//遍歷分類器

步驟3采用SMOTE算法合成少數(shù)類，生成新的訓(xùn)練集S′；

步驟6fori←1 toNdo

步驟7遍歷實(shí)例來(lái)更新分類器誤差：

步驟8endfor

步驟9endfor

步驟10輸出最終的集成分類器C。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集

在實(shí)驗(yàn)中，本文采用了6個(gè)人工數(shù)據(jù)集和2個(gè)真實(shí)數(shù)據(jù)集來(lái)驗(yàn)證本文算法。其中Drifting Gaussian、Moving Gaussian、SEA、Hyper Plane、Spiral和Checkboard人工數(shù)據(jù)集使用概念漂移生成器生成;2個(gè)真實(shí)數(shù)據(jù)集為Electricity[15]和Weather[15]。Electricity數(shù)據(jù)集包含了澳大利亞新南威爾士州時(shí)間和需求的電價(jià)，類標(biāo)簽是通過過去24小時(shí)的價(jià)格變化情況來(lái)確定。Weather數(shù)據(jù)集包含美國(guó)貝爾維尤和內(nèi)布拉斯加州超過50年的天氣信息，任務(wù)是預(yù)測(cè)某一天是否會(huì)下雨。具體的數(shù)據(jù)集特征如表1和表2所示。本文算法主要以二元分類為主，為了更好地研究帶有概念漂移的不平衡數(shù)據(jù)流，數(shù)據(jù)集會(huì)分為突變型(Abrupt)和漸變型(Gradual)2種漂移類型的數(shù)據(jù),如表1和表2所示。

Table 1 Abrupt datasets表1 突變型數(shù)據(jù)集

Table 2 Gradual datasets表2 漸變型數(shù)據(jù)集

為了模擬真實(shí)的數(shù)據(jù)流中概念漂移變化的情況，實(shí)驗(yàn)通過不平衡比率的動(dòng)態(tài)變化來(lái)模擬漂移的發(fā)生。

(1)突變型概念漂移：不平衡比率初始設(shè)置為0.01,數(shù)據(jù)流產(chǎn)生過半時(shí)，不平衡比率突變成0.99,也就是多數(shù)類變成了比率只有0.01的少數(shù)類。

(2)漸變型概念漂移：不平衡比率初始設(shè)置為0.01,在產(chǎn)生1/3的數(shù)據(jù)流后，不平衡比率不斷增大，直至數(shù)據(jù)流量到達(dá)最大時(shí)，不平衡比率達(dá)到了0.99。

4.2 算法評(píng)估指標(biāo)

在類不平衡數(shù)據(jù)流中，傳統(tǒng)的指標(biāo)已經(jīng)不適用不平衡的場(chǎng)景，分類器總傾向多數(shù)類別，因此針對(duì)不平衡分類性能評(píng)估，相關(guān)學(xué)者提出了常用的F-measure和G-mean等以評(píng)價(jià)分類器對(duì)于多數(shù)類和少數(shù)類樣本的分類性能。G-mean是由Kubat等[16]提出的幾何均值，常被應(yīng)用于不平衡類標(biāo)簽屬性的數(shù)據(jù)流所在的領(lǐng)域。G-mean用表3所示的混淆矩陣來(lái)定義,其計(jì)算如式(6)所示：

(6)

Table 3 Confusion matrix表3 混淆矩陣

受試者工作特征曲線ROC(Receiver Operating Characteristic)和AUC(Area Under ROC Curve)是常用的評(píng)估分類器性能的指標(biāo)。其中AUC是ROC曲線下的面積，AUC越接近1，表示該分類器性能越好。本文采用G-mean和AUC作為BCA-HD算法的性能評(píng)價(jià)指標(biāo)。

4.3 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證BCA-HD算法的性能，本文將BCA-HD算法與9種對(duì)比算法應(yīng)用于突變型和漸變型數(shù)據(jù)集，然后比較其G-mean和AUC。本次實(shí)驗(yàn)的硬件環(huán)境是Intel Core i5 1T+128 MB RAM的PC機(jī)，操作系統(tǒng)是Windows 10專業(yè)版，編程語(yǔ)言為Python3.6。

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

5.1 塊大小對(duì)BCA-HD算法的影響

BCA-HD是基于塊實(shí)現(xiàn)的集成分類算法，因此塊的大小直接影響算法的執(zhí)行效果。為了驗(yàn)證塊大小對(duì)算法的影響，實(shí)驗(yàn)分別將數(shù)據(jù)塊大小設(shè)置為d=500，750，1 000，1 250，1 500，1 750和2 000。其中d表示一個(gè)塊所包含實(shí)例的數(shù)目。算法在Abrupt和Gradual 2種類型數(shù)據(jù)集上運(yùn)行，實(shí)驗(yàn)結(jié)果使用G-mean指標(biāo)展示，如表4和表5所示。

表4給出了在突變型數(shù)據(jù)集上不同塊大小算法的G-mean性能。整體看初始隨著塊大小的增長(zhǎng)G-mean值也在不斷增長(zhǎng)，當(dāng)d=1 000時(shí)除了Spiral數(shù)據(jù)集外其余7個(gè)數(shù)據(jù)集上的G-mean都開始下降,說明隨著塊大小的增大，不平衡比率也都在不斷變化，使得分類器適應(yīng)它的能力變差。但是,在d=1 750時(shí),G-mean開始緩慢增長(zhǎng)，Drifting Gaussian和Hyper Plane在d取值為1 750和2 000時(shí)分別增長(zhǎng)了2.14%和1.54%,說明分類器開始適應(yīng)突變數(shù)據(jù)流，其中SMOTEBoost算法作為基分類器由于采用了SMOTE的重采樣技術(shù)可以很好地平衡數(shù)據(jù)流。

表5是漸變型數(shù)據(jù)集上的運(yùn)行結(jié)果，從整體看除了Drifting Gaussian和Moving Gaussian數(shù)據(jù)集上G-mean的性能下降較快外，其余的保持了平穩(wěn)的增長(zhǎng)狀態(tài)。其中在真實(shí)數(shù)據(jù)集Weather上，在d取值為1 000和1 500時(shí)指標(biāo)增長(zhǎng)了7.63%，在Spiral數(shù)據(jù)集上,在d取值為1 000和1 250時(shí)指標(biāo)增長(zhǎng)了6.66%,說明數(shù)據(jù)流的塊大小在緩慢變化情況下并不影響分類器的訓(xùn)練。其中在2種類型數(shù)據(jù)集上d=2 000時(shí)，分類器的表現(xiàn)均出現(xiàn)了下滑，說明塊大小不能無(wú)限度地增大。在2種類型數(shù)據(jù)集上表現(xiàn)最好的G-mean使用粗體標(biāo)了出來(lái)。

5.2 基分類器數(shù)量對(duì)BCA-HD算法的影響

本文提出的BCA-HD是集成分類算法，它是由基分類器組合形成的，因此很有必要探究基分類器的數(shù)量對(duì)算法的影響。實(shí)驗(yàn)設(shè)置分類器的數(shù)量在[1,15]內(nèi)變化，BCA-HD算法在突變型和漸變型數(shù)據(jù)集上的G-mean如表6和表7所示。為了更好地展現(xiàn)數(shù)據(jù)的變化情況，給出了如圖3和圖4所示的箱線圖，其縱坐標(biāo)是G-mean值的均方差。例如,在Electricity數(shù)據(jù)集上在分類器數(shù)量在[1,15]內(nèi)的G-mean平均值為0.674 2，當(dāng)分類器為1時(shí)均方差為+0.003 9。

Table 4 G-mean of different algorithms on abrupt datasets with different chunk sizes 表4 不同數(shù)據(jù)塊大小時(shí)不同算法在突變型數(shù)據(jù)集上的G-mean

Table 5 G-mean of different algorithms on gradual datasets with different chunk sizes表5 不同數(shù)據(jù)塊大小時(shí)不同算法在漸變型數(shù)據(jù)集上的G-mean

Table 6 G-mean of different algorithms on abrupt datasets when the number of base classifiers varies表6 不同基分類器數(shù)量時(shí)不同算法在突變型數(shù)據(jù)集上的G-mean

Table 7 G-mean of different algorithms on gradual datasets when the number of base classifiers varies表7 不同基分類器數(shù)量時(shí)不同算法在漸變型數(shù)據(jù)集上的G-mean

Figure 3 G-mean of different algorithms on abrupt datasets when the number of base classifiers varies圖3 不同基分類器數(shù)量時(shí)不同算法在突變型數(shù)據(jù)集上的G-mean

Figure 4 G-mean of different algorithms on gradual datasets when the number of base classifiers varies圖4 不同基分類器數(shù)量時(shí)不同算法在漸變型數(shù)據(jù)集上的G-mean

圖3展示了在突變型數(shù)據(jù)集上分類器數(shù)量由1～15的變化情形。分類器數(shù)量在[1,3]時(shí)，均方差的變化是±0.01；在[6,12]時(shí)，隨著分類器數(shù)量的增加均方差的變化在±0.04。均方差整體處于一種正增長(zhǎng)，說明分類器數(shù)量的增多可以更好地適應(yīng)突變型概念漂移。圖3中的圓點(diǎn)是異常點(diǎn)，在表6中用黑體字標(biāo)示了。

圖4展示了漸變型數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。從圖4中可以看到,隨著分類器數(shù)量的增加，整體的G-mean值均方差變化控制在±0.02左右,說明隨著分類器數(shù)量的增加，分類器的性能趨于一種穩(wěn)定的狀態(tài)。漸變型數(shù)據(jù)集對(duì)分類器的影響較小，圖4中的圓點(diǎn)是異常點(diǎn),在表7中用黑體字標(biāo)示了。

5.3 BCA-HD算法性能對(duì)比分析

為了驗(yàn)證BCA-HD的分類性能，本文使用基于塊和在線的9種算法進(jìn)行比較?；趬K的算法有ACDWM(Adaptive Chunk-Based Dynamic Weighted Majority)[15](采用了塊大小不固定的形式適應(yīng)概念漂移同時(shí)采用重采樣技術(shù)平衡數(shù)據(jù)集)、Learn++.NIE[16](在每個(gè)塊上創(chuàng)建分類器進(jìn)行訓(xùn)練)、DWMIL[5]、REA[4]和DFGW-IS[3]?；谠诰€的算法有：HLFR (Hierarchical Liner Four Rates)[18]、DDM-OCI (Drift Detection Method-Online Class Imbalance learning)[19]、PAUC-PH (Prequential Area Under the ROC curve Page-Hinkley)[20]和OOB[2]算法,前3個(gè)算法是不平衡數(shù)據(jù)的漂移檢測(cè)算法。以上算法的數(shù)據(jù)塊大小d=1 000，基分類器個(gè)數(shù)設(shè)為12，損失函數(shù)為G-mean。實(shí)驗(yàn)結(jié)果如表8～表11所示。其中對(duì)比算法在每個(gè)數(shù)據(jù)集上的性能指標(biāo)大小進(jìn)行了排名(括號(hào)里面進(jìn)行了標(biāo)注)，最好的指標(biāo)使用黑體字進(jìn)行了標(biāo)注，同時(shí)Average Rank展示了每個(gè)算法的平均排名。

表8和表9列出了對(duì)比算法在突變型數(shù)據(jù)集和漸變型數(shù)據(jù)集上的G-mean值。由表8可知，BCA-HD算法在5個(gè)突變型數(shù)據(jù)集上的G-mean值高于其他對(duì)比算法的。其中在Drifting Gaussian數(shù)據(jù)集上本文算法的G-mean值分別比DMWIL、OOB算法高2.99%,10.12%;BCA-HD算法在Checkboard數(shù)據(jù)集上位于第2名，與DWMIL算法相差0.08%。在表9中，BCA-HD算法在7個(gè)漸變型數(shù)據(jù)集上取得了第1名，其中在Hyper Plane數(shù)據(jù)集上高于ACDWM算法3.92%。

Table 8 G-mean of different algorithms on abrupt datasets表8 不同算法在突變型數(shù)據(jù)集上的G-mean值

Table 9 G-mean of different algorithms on gradual datasets表9 不同算法在漸變型數(shù)據(jù)集上的G-mean值

表10和表11展現(xiàn)的是各算法在2種類型數(shù)據(jù)集上的AUC。從表10可知，本文算法在5個(gè)突變型數(shù)據(jù)集上的AUC高于其它對(duì)比算法的，其中在Drifting Gaussian數(shù)據(jù)集上，BCA-HD的AUC是91.96%,高于所有對(duì)比算法的；在Moving Gaussian和Checkboard數(shù)據(jù)集上取得了第2名和第3名，并且在這2個(gè)數(shù)據(jù)集上的結(jié)果與第1名分別僅相差1.35%和0.96%。在表11中，BCA-HD在6個(gè)漸變數(shù)據(jù)集上的AUC取得了第1名，其中在Moving Gaussian與第2名相差最大,為2.36%，而在Sea數(shù)據(jù)集上低于第1名0.73%。

為了更詳細(xì)地對(duì)比不同算法的性能，圖5和圖6給出了不同算法的G-mean和AUC對(duì)比情況。在圖5a中給出的是在8個(gè)突變型數(shù)據(jù)集上的G-mean和AUC平均值的對(duì)比情況，BCA-HD在2種評(píng)估指標(biāo)上都是趨于持平狀態(tài),說明隨著不平衡比例的不斷變化本文提出的算法可以很快適應(yīng)概念漂移的發(fā)生。而HLFR算法的G-mean和AUC平均值相差較大，雖然該算法可以檢測(cè)概念漂移的存在，但是又無(wú)法快速處理變化的不平衡數(shù)據(jù)流。在圖5b中BCA-HD算法的平均排名是第1名，緊跟其后的便是DWMIL算法,這是由于其底層使用了處理不平衡的欠采樣算法和動(dòng)態(tài)更新機(jī)制，因此能很好地適應(yīng)數(shù)據(jù)流的變化。圖6a和圖6b是漸變型數(shù)據(jù)集上各算法2種指標(biāo)的平均值和平均排名，可以看到BCA-HD是10種算法中分類性能最好的，具體表現(xiàn)為其G-mean和AUC值高，排名也最高，這表明在漸變狀態(tài)下的不平衡數(shù)據(jù)流集成算法依然可以很好地處理變化微小的數(shù)據(jù)。同時(shí),基于塊的ACDWM、Learn++.NIE、DFGW-IS和DWMIL算法也有很平穩(wěn)的適應(yīng)性，這與它們各自使用的平衡數(shù)據(jù)流機(jī)制有關(guān)。

Table 10 AUC of different algorithms on abrupt datasets表10 不同算法在突變型數(shù)據(jù)集上的AUC值

Table 11 AUC of different algorithms on gradual datasets表11 不同算法在漸變型數(shù)據(jù)集上的AUC值

Figure 5 Comparison of G-mean and AUC of different algorithms on abrupt datasets圖5 不同算法在突變型數(shù)據(jù)集上的G-mean和AUC對(duì)比

5.4 BCA-HD算法參數(shù)與時(shí)間效率分析

本文提出的BCA-HD算法是基于Hellinger距離的集成加權(quán)算法，由于算法是基于實(shí)例級(jí)和分類器級(jí)的組合加權(quán)，因此主要使用2種參數(shù)，即權(quán)重組合參數(shù)α和刪除分類器的閾值參數(shù)θ。實(shí)驗(yàn)中2種參數(shù)的取值分別在[0.1,0.5]內(nèi)，實(shí)驗(yàn)的結(jié)果如表12和表13所示。

表12和表13是在5個(gè)突變型數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。從圖7中可以看到，整體隨著α的增加均方差的變化范圍在±0.02，其中α=0.2時(shí)均方差變化超過±0.03，說明α的取值為0.02較為合適。圖7中圓點(diǎn)是異常點(diǎn),在表12用黑體字標(biāo)注出來(lái)了。在圖8的箱線圖中，整體θ的增加使均方差變化在±0.02內(nèi)，但是負(fù)增長(zhǎng)的比較多。說明隨著閾值θ的增大無(wú)法刪除更多的分類器，動(dòng)態(tài)更新變得緩慢，適應(yīng)概念漂移的能力開始下降。

Table 12 G-mean of BCA-HD when α=0.1～0.5表12 α=0.1～0.5時(shí)BCA-HD 的G-mean

Table 13 G-mean of BCA-HD when θ=0.1～0.5表13 θ=0.1～0.5時(shí)BCA-HD 的G-mean

Figure 7 Comparison of deviation from average G-mean of BCA-HD when α=0.1～0.5圖7 α=0.1～0.5時(shí)BCA-HD的G-mean均方差比較

Figure 8 Comparison of deviation from average G-mean of BCA-HD when θ=0.1～0.5圖8 θ=0.1～0.5時(shí)BCA-HD的G-mean均方差比較

為了實(shí)驗(yàn)的完整性，本文還在真實(shí)數(shù)據(jù)集上分析了BCA-HD算法的時(shí)間效率,結(jié)果如圖9和10所示。從圖9和圖10中可以看到,BCA-HD算法的運(yùn)行時(shí)間是在不斷地上升，這是由于算法使用了實(shí)例級(jí)和分類器級(jí)的加權(quán),增加了計(jì)算復(fù)雜度。其中DWMIL和HLFR算法的時(shí)間也處于一種線性增長(zhǎng)態(tài)勢(shì)，這是因?yàn)樗鼈兎謩e使用了動(dòng)態(tài)加權(quán)和概念漂移的檢測(cè)機(jī)制，從而增加了計(jì)算時(shí)間。

Figure 9 Comparison of algorithm running time on Weather圖9 Weather上的算法運(yùn)行時(shí)間對(duì)比

Figure 10 Comparison of algorithm running time on Electricity圖10 Electricity上的算法運(yùn)行時(shí)間對(duì)比

6 結(jié)束語(yǔ)

本文首先闡述了不平衡數(shù)據(jù)流分類和概念漂移的基本概念,并對(duì)已有算法進(jìn)行了概述；隨后提出了一種新的基于Hellinger距離的集成加權(quán)分類算法BCA-HD用于處理帶有概念漂移和不平衡問題的數(shù)據(jù)。對(duì)比分析實(shí)驗(yàn)顯示，本文所提出的算法具有較好的優(yōu)勢(shì)，并得出了以下結(jié)論：

在突變型和漸變型數(shù)據(jù)集上，隨著塊的增大算法性能會(huì)先下降然后再逐漸回升，說明該算法可以較好地適應(yīng)塊大小的變化。在基分類器數(shù)量的實(shí)驗(yàn)中，算法在漸變型數(shù)據(jù)集上隨著分類器數(shù)量的增加變化趨于穩(wěn)定，而在突變型數(shù)據(jù)集上有明顯變化，說明在突變情況下受分類器數(shù)量影響較大。在對(duì)比實(shí)驗(yàn)中，相比經(jīng)典的不平衡算法,本文提出的算法取得了更優(yōu)的性能，說明BCA-HD算法能很好地適應(yīng)漸變型和突變型概念漂移和不平衡的發(fā)生。

本文所提出的算法為二元不平衡分類問題提供了有效的解決方案。但是,組合加權(quán)的方式增加了計(jì)算復(fù)雜度,消耗了更多的時(shí)間。后續(xù)的研究將會(huì)在算法的基分類器數(shù)量的剪枝策略入手以降低時(shí)空復(fù)雜度。