董明剛，張 偉，敬 超

1(桂林理工大學 信息科學與工程學院,廣西 桂林 541004)

2(嵌入式技術與智能系統重點實驗室,廣西 桂林 541004)E-mail:jingchao@glut.edu.cn

1 引 言

近年來隨著信息技術在交通管制、垃圾郵件檢測等領域的應用，產生了大量具有動態(tài)變化的數據流[1].這些動態(tài)的數據流中存在著大量類分布不均衡問題.同時相比于靜態(tài)數據流的數據分布，該類型數據流中的數據分布會隨著真實環(huán)境實時發(fā)生變化，從而導致概念漂移問題[2-4].目前，國內外很多研究者針對這類問題做了深入的研究，他們的研究重點主要是圍繞：數據預處理、分類算法以及采用集成分類器三個層面來進行.

對于數據的預處理方法，Gao[5]等人設計了一個估計后驗概率的采樣模型，以此來使小類樣本與大類樣本達到平衡.Wang[6]等人提出通過下采樣技術，從大類樣本中按照Bootstrap方法隨機挑選相當于正類樣本數量的樣本形成平衡的數據對，以此解決不平衡問題.Chen[7]等人提出SERA算法，通過選擇性的將先前的接收到的正類樣本放到當前數據塊中，這樣可以較好的解決數據不平衡問題.對于分類器層面的改進方法，Yu[8]等人提出一種層次假設檢驗框架-HHT去識別概念漂移類型，后又基于此框架提出HLFR算法.該算法使用自適應訓練策略代替常用的重訓練策略在應對不同的概念漂移類型的適應性方面有良好的表現.Wang[9]等人通過下采樣技術來處理不平衡數據流問題，通過動態(tài)修改分類器的權重使分類器具有良好的準確性.使用下采樣技術能夠減少運行時間，提高效率，同時動態(tài)修改分類器的權重能夠很好的適應新的數據概念，使得分類器具有很強的魯棒性.

相比之下，集成分類算法由于集成多個基分類器共同決策，因此能很好地處理概念漂移問題[10]：Ditzler[11]等人提出Learn++.CDS和Learn++.NIE，他們采用將數據流中到達一定數量的數據封裝成數據塊的方法，并為每個數據塊單獨創(chuàng)建一個子分類器，通過基分類器的組合集成來預測新傳入的數據的標簽.基分類的權重隨時間的增加和分類性能的降低而減少.Kolter[12]等人提出DWM算法，提出了一種基于基分類器加權求和算法的通用框架，DWM在分類過程中保持基分類器不變，其權重在不同的數據塊上不斷地修改，并通過權重與分類器的加權求和進行樣本預測，通過使用動態(tài)訓練分類器權重解決概念漂移問題.Wu[13]等人提出了DFGW-IS算法，該算法通過在基分類器中運用采樣技術來解決數據不平衡問題，然后對基分類器加權來解決數據概念動態(tài)變化的問題.Ghazikhani[14]等人通過使用遞歸最小二乘(RLS)誤差模型來處理數據流的概念漂移問題，通過調整基分類器的加權誤差解決類不平衡問題.當前數據流分類算法主要聚焦在集成分類算法[15-18]，該類型算法使用便捷，容易部署，且效果比單分類器更突出，能很好地解決概念漂移問題.

綜上所述，在數據流的分類中，通常有兩方面的困難，第一數據流中類分布不平衡，需要一種機制來克服類不平衡，以提高總體性能，第二需要動態(tài)調整學習機制來適應類概念的轉變，即概念漂移問題.為了能夠同時處理這兩類問題，Yang[19]等人提出了一種動態(tài)加權的集成分類算法(Dynamic Weighted Majority for Incremental Learning，簡稱DWMIL)，該算法能同時較好地處理數據流分類中存在的概念漂移和數據不平衡問題，但該方法在處理數據流時每個樣本只處理一次，這樣做雖然節(jié)省了數據運算空間，但會丟失很多關于小類樣本的信息，影響了小類樣本的識別精度，Chen[20]等人提出REA算法，通過實驗驗證將小類樣本收集起來根據某種規(guī)則再次應用能很好地提高分類器對小類樣本的識別度，因此采用某種機制犧牲一部分運算空間，將之前的小類樣本保存下來應用于分類器的訓練能提高對小類樣本的識別度.

為了有效處理帶有概念漂移的不平衡數據流，基于DWMIL模型，提出了基于采樣技術的集成分類算法DWES(Dynamic Weight Ensemble Learning Method Based on Sampling Technology).本文的主要貢獻為：

1)采用上采樣技術與下采樣技術結合的方式來平衡數據塊：假設數據流以數據塊的方式到達，在對當前數據訓練分類器的時候，上采樣將之前的小類樣本收集起來，篩選滿足一定條件的樣本加上當前小類樣本形成當前數據塊的合成小類樣本，然后大類樣本采用下采樣技術每次抽取等同于當前數據塊合成小類樣本數量的樣本，以此來形成一個平衡的數據對，用這個平衡的數據塊來訓練分類器.

2)調整了基分類器的權重計算方式，通過熵值計算能影響綜合性能的評價指標，使用這個評價指標來計算該分類器的權重，這樣做能使分類效果好的分類器有更高的權重，淘汰效果差的分類器.

3)通過馬氏距離計算先前小類樣本集與當前小類樣本的相似性，挑選相似性高的樣本，樣本數量由計算得到的馬氏距離集合的均方差來確定.

2 相關工作

2.1 DWMIL集成分類器

圖1 DWMIL集成分類器流程圖

2.2 數據流的采樣方法

采樣技術是處理不平衡數據流的有效方法，一般分為上采樣方法跟下采樣方法.上采樣方法SMOTE[22]或者DataBoost-IM[23]基于存在的實例樣本來合成新的實例樣本點.這種合成新樣本的方式有可能產生噪聲樣本，影響分類的精度.為了改善這個缺陷，REA算法不通過產生新樣本來平衡數據，而是根據一定的規(guī)則選取歷史樣本中的點，以此達到樣本平衡的效果.REA這種方式減少了噪聲點的影響，加強了對小類樣本的識別能力，在實際應用中取得了很好的效果.下采樣方法一般采用UOB或者OOB，其基本思想是從大類樣本中按照Bootstrap方法隨機挑選相當于正類樣本數量的樣本形成平衡的數據對，以此解決不平衡問題.

2.3 馬氏距離

馬氏距離[24]是一種無量綱的計算兩個未知樣本之間相似度的度量，他考慮了樣本各個屬性之間的聯系，能很好地反映樣本的之間的關聯程度.設樣本集合u，其中μ是樣本總體的均值，Σ為樣本的協方差矩陣，則樣本x到u的馬氏距離計算公式如公式(1)所示：

(1)

綜上，采用上采樣技術增加小類樣本的數量，同時根據小類樣本的數量對大類樣本進行下采樣，減少大類樣本的數量可以很好的解決不平衡數據問題.對生成的基分類器進行動態(tài)權重調整能使最終的分類器很快的適應新的數據流樣本，解決概念漂移問題.

3 基于采樣技術的集成分類算法DWES設計與分析

在對不帶標簽的數據流進行分類的時候，DWMIL集成分類器既能保持較高的分類精度，也能保證在數據流發(fā)生概念漂移的時候有較好的分類效果，但是在處理數據塊的時候DWMIL集成分類器將之前的用過的數據塊中小類樣本全部拋棄，這樣做雖然節(jié)省了計算的存儲空間但是會損失一部分小類樣本的數據特征，影響分類精度.并且在其進行分類器篩選的時候僅用到一個評價指標(G-mean/F-Value)，其不能合理地決定分類器的權重.基于DWMIL集成分類器，充分利用之前用過的小類樣本，本文提出了一種集成分類算法--DWES算法.該算法上采樣歷史中存儲的小類樣本，下采樣該數據塊中的大類樣本形成平衡的樣本對，然后根據訓練的分類器的表現不斷調整分類器權重以適應新的樣本.

3.1 DWES的采樣策略

假設數據流以塊的方式到達，將當前整個數據塊看作是訓練集，將下一個將要到達的數據塊整體看作是測試集，數據流中只有正類、負類兩種類標識，正類樣本在每個數據塊中相較于負類樣本占比例較少，令t表示某一時間戳，D(t-1)表示在時間戳為t-1時到達的數據塊，下一時刻到達的數據塊為D(t)，則數據流為{…,D(t-1),D(t),D(t+1),…}.DWES集成分類器的采樣過程如下(采樣框架如圖2所示).

圖2 DWES的采樣流程

1)上采樣：在上采樣的過程中我們將數據塊{D(1),D(2),…,D(t-1)}中正類樣本塊{DNp1,DNp2,…,DNp(t-1)}收集起來放入集合PA中，當新的數據塊D(t)到達的時候將前面1至t-1時間段內收集的正類樣本PA用于當前數據塊D(t).當數據塊D(t)(t>2)到達的時候，根據馬氏距離(公式1)計算當前數據塊中正類樣本DNp與集合PA中所有樣本的馬氏距離，挑選出其馬氏距離小于馬氏距離均方差的樣本Pat加入到當前數據塊的正類樣本中得到當前數據塊合成的正類樣本Dp=Pat+DNpt.

2)下采樣：根據當前數據塊中合成的正類樣本數量選取當前數據塊中等量的負類樣本組成平衡的樣本對進行分類器的訓練.

DWES集成分類算法的基于上采樣與下采樣結合的分類器構造過程偽代碼如算法1所示.

算法 1.

輸入：數據塊DataD={xi∈X,yi∈Y},i=1,…,N,數據塊D中正類樣本數量為NP；數據塊D中正類樣本為DNp,數據塊D中大類樣本數量為Nn,數據塊中D中大類樣本為DNn,數據塊D訓練基分類器的大小為T.

1.t=1;

2.ifNP

3.Ns←NP;PA=DNp;

4.else

5.Ns←Nn;PA=DNn;

6.endif

7.fort← 2toTdo

8.ifNP

9.Ns←NP;Dn=DNp;

10.else

11.Ns←Nn;Dn=DNn;

12.endif

13.di←計算當前小類樣本Dn與之前記錄的所有小類樣本PA之間的馬氏距離;

14.DCOV←計算{di}的協方差;

15.(Ne，Dempty)←從之前記錄的小類樣本PA中挑選{di}小于DCOV的樣本，得到樣本集Dempty，樣本集的數量為Ne;

16.PA={PA,Dn};

17.Dp←從(DNp+Dempty)樣本中采用Bootstrap算法隨機挑選(Ns+Ne)個樣本;

18.Dn←從DNn樣本中采用Bootstrap算法隨機挑選(Ns+Ne)個樣本;

19.Ht←{Dp,Dn}組成最終需要訓練的樣本集合，之后采用CART算法訓練分類規(guī)則;

20.endfor

3.2 DWES的權重制定策略

(a)數據歸一化公式如公式(2)所示：

(2)

其中i的取值范圍是[1,n]，j的取值范圍是[1,m].i表示連續(xù)到達的第i個數據塊，j表示某種評價指標，在這里選取的評價指標P={G-Mean、F-measure、Precision、Recall，NPcost[18]}.

(b)計算評價標準中第j項評價指標所占該類型評價指標的比重，其公式計算如公式(3)所示:

(3)

(c)計算第j項評價指標的熵值如公式(4)所示：

(4)

(d)計算第j項評價指標的權值如公式(5)所示：

(5)

其中gj表示第j項評價標準的差異系數其計算方式為：gj=1-ej，當指標在不同數據塊中差異越大代表對評測的最終結果影響越大，熵值越小.

(e)計算各評價標準的綜合評分值如公式(6)所示：

(6)

選取綜合評價值高的評價標準作為基分類器對樣本錯分類的代價其計算方式如公式(7)所示：

ε(t)=1-Pj

(7)

權重的計算公式為如公式(8)所示：

(8)

(9)

DWES的具體流程的偽代碼如算法2所示.

算法 2.DWES算法

1.fori←1 toNdo;

2.通過基分類器預測Xi的標簽：

3.endfor

4.forj←1 tomdo

6.更新分類器的權重：

7.endfor

8.移除權值低于θ的基分類器:

10.創(chuàng)建新的分類器，初始化分類器權重為1;

11.m←m+1;

12.H←將(D(t),T)傳給基于上采樣與下采樣的分類器;

13.H(t)←H(t-1)∪H;

3.3 DWES算法復雜度分析

在上采樣過程中，由于計算當前正類樣本與之前正類樣本集之間的馬氏距離是線性的，設其復雜度為O(f(np))，其下采樣的算法復雜度為O(f(nn))則DWES在采樣過程中時間復雜度為：O(f(np))+O(f(nn))，在訓練分類器時計算權重的復雜度為O(n*f(n))，故其分類器計算的復雜度為：m*O(n*f(n)).DWES算法復雜性為：O((f(np)+f(nn))*n*f(n)*m),m為樣本中數據塊的總個數.

4 實驗分析

4.1 實驗設置

在本實驗中，我們使用了4個合成數據流跟兩個真實環(huán)境數據流，他們的詳細信息如表1所示,小類樣本在每個塊中所占的百分比固定在塊大小的 5%.

表1 六種數據流信息表

本文算法在開源平臺MOA[26](Massive Online Analysis)基礎下實現，實驗程序由matlab編寫，實驗程序在CPU為2.4GHz,內存為8GB，操作系統為WIN10的PC機上進行實驗.為了驗證DWES的有效性，我們比較了5種權威的處理帶有概念漂移的不平衡數據流的算法：LPN[13]、DWM[14]、DFGW[15]、DWMIL[16]、REA[20]，分析它們與DWES算法在6種不同類型數據流上的表現情況.DWM在使用時，采用Under-sampling Online Bagging(UOB)算法來進行處理.

DWMIL、DWM、LPN、DWES基分類器大小T設置為11.DWMIL、DWES分類器的閾值θ設置為0.001.LPN、DWMIL的誤差函數ε(t)=1-(GMean),所有算法都通過CART訓練基分類器[19].所有的實驗跑10次取平均值.

4.2 實驗比對與分析

DWES中利用馬氏距離尋找正類樣本點時，為了找到合適的均方差的閾值上限值，我們分別對不同的均方差閾值上限(DCOV值)進行實驗，實驗結果如圖3所示.

圖3 DCOV值與AUC值的關系

從實驗得出在DCOV值取為7的時候多數數據流達到AUC值最優(yōu)時刻，因此實驗中我們選取DCOV值為7.

以AUC、G-Mean、F-measure、Precision為評價指標，采用先測試后訓練的策略對各種算法在每個數據塊上進行評價.每個數據塊的AUC值、G-Mean值、F-measure值如圖4-圖6所示，根據折線圖可以看出，由于是先測試再訓練，因此所有的算法的評價指標的初始值是相同的.在AUC評價標準上，DWES算法相較于其他算法，在Moving Gaussian、Hyper Plane、SEA、Electricity、Weather 5個數據流上有更好的性能，在Checkerboard數據流上與Electricity數據流上，跟DWMIL算法平均性能大致相同.相較于DWMIL外的其他算法有更高的精度.在F-Measure評價標準上,由于我們的算法對正類樣本有更好的識別度，因此DWES算法在F-Measure評價標準上性能在6個數據流上優(yōu)于其它所有算法.在G-Mean評價標準上,REA算法在Moving Gaussian數據流上逐漸減少到0，這是由于其在僅采用上采樣算法處理存儲的小類樣本集，對有些數據流的概念漂移問題無法很好地處理.DWES算法在上采樣的同時對大類樣本進行下采樣，以此來解決這種問題，因此DWES在這種情況下發(fā)揮更好的性能，相較于其他算法DWES在G-Mean評價標準上表現優(yōu)異，在Checkerboard數據流上由于對大類樣本采用下采樣技術，因此降低了對大類樣本的識別度，導致G-Mean值提升不明顯.

圖4 每個數據塊的AUC值

圖5 每個數據塊的F-Measure值

圖6 每個數據塊的 G-Mean值

各算法的綜合性能表現如表2-表6所示，在AUC評價標準上，DWES對比DWMIL算法在6個數據流上平均提升4.07%，其中最好表現在Hyper Plane數據流上，對比DWM算法提升了29.64%.在G-Mean評價標準上，DWES對比DWMIL算法在6個數據流上平均提升1.74%，總體來說，其中最好表現在Moving Gaussian數據流上，對比REA算法提升了44.59%.在F-Measure評價標準上，DWES對比DWMIL算法在6個數據流上平均提升20.85%.最好的表現在Checkerboard數據流上，對比DWM算法提高了58%.在Precision評價標準上，DWES對比DWMIL算法在6個數據流上平均提升29.01%，其中最好表現在Moving Gaussian數據流上，對比DFGW算法提升了58.2%.

表2 AUC值

DWES算法采用類似REA算法思想選取小部分之前存儲的正類樣本參與到當前分類器的訓練，并且根據正類樣本的數量取相同數量的負類樣本形成平衡的樣本對，利用多個平衡的樣本對訓練分類規(guī)則組成當前數據塊的分類器，這樣做相對于僅將部分正類樣本拿到當前數據塊進行訓練的REA算法，或者利用自身樣本進行上采樣的DFGW算法來講，能夠增加對正類樣本的識別度，并且避免產生噪聲樣本點，DWM、Learn++并沒有對不平衡數據進行預處理，使得DWES算法在識別為正類樣本的數據中有更多的是真正的正類樣本，因此在Precision評價標準上相對于其他算法表現較好；在對新的數據塊做測評時，因為新的數據塊中有較多之前沒出現過的正類樣本，或者出現正類樣本與負類樣本概念互換(即發(fā)生概念漂移)的情況，DWES算法采用基于熵值的權重修改策略，動態(tài)尋找對綜合表現影響最高的評價指標，通過評價指標值動態(tài)的更新分類器的權重，并不斷淘汰權重較低的分類器，相對于僅采用單一評價指標來更新分類器的DWM算法和DWMIL算法或者通過時間的增加來減小分類器權重方法的Learn++算法能夠分別增加正類樣本跟負類樣本的識別度，使得全部正類樣本被識別為正類樣本的數量大于其他算法，即Recall值優(yōu)于其他算法；同時也會提高對負類樣本的識別度，全部負類樣本中識別為負類樣本的數量大于其他算法，又由于Recall值優(yōu)于其他算法，所以G-Mean值相對于其他算法表現較好；F-measure值與Precision值跟Recall值呈正相關性，由于Precision值跟Recall值均高于其他算法，因此F-measure值也會優(yōu)于其他算法.AUC值是ROC曲線與坐標軸圍成的面積，DWES通過多種機制提高正類樣本的識別度，同時也會提升了負類樣本的識別度，使得模型的魯棒性更高，ROC去線下的面積相對于其他算法也會較大，最終使得AUC值優(yōu)于其他算法.總體來說，DWES算法對比其他算法在處理帶有概念漂移的不平衡數據流問題時有更好的性能.總體來說，DWES算法對比其他算法在處理帶有概念漂移的不平衡數據流問題時有更好的性能.

表3 G-Mean值

表4 F-Measure值

表5 Precision值

表6 時間(秒)

4.3 算法效率分析

時間復雜度對評價在線學習算法的性能方面發(fā)揮重要的作用.表6給出了6種算法在六種數據流中運行時間，綜合來看DWES算法在運行時間方面相比其他算法排在第三，這是因為DWMIL算法采用基于下采樣的Bagging算法，而DWES在此基礎上還增加了上采樣算法，因此時間花費要多于DWMIL算法，由于REA算法采用單一的決策樹算法，其在某些數據集上速度會更快.LNIE使用所有訓練的分類器對每個數據塊進行訓練，因此預測成本會高一些，DWM是最慢的，這是由于它一對一的學習方法，而其他算法是基于數據塊的，處理時間會快于這種一對一的學習方法.

5 總結與展望

類不平衡與概念漂移是數據流處理的兩個難點問題.針對帶有概念漂移的不平衡數據流問題，本文提出了基于上采樣與下采樣結合的集成分類算法-DWES，該算法能同時解決數據流的不平衡和概念漂移問題，并能提高對小類樣本的辨識度.最后在六個帶有概念漂移的不平衡數據流上對比五種權威的算法，綜合結果表明DWES算法相比于其他算法在解決帶有概念漂移的不平衡數據流上有更高的精度.下一步將探索通過樣本的分布去計算數據集的不平衡率，將算法拓展到解決多類數據流不平衡問題上去.