數(shù)據(jù)流滑動窗口方式下的自適應集成分類算法

孫艷歌,王志海, 原繼東,韓 萌

(1.北京交通大學 計算機與信息技術學院，北京 100044; 2.信陽師范學院 計算機與信息技術學院，河南 信陽 464000)

?

數(shù)據(jù)流滑動窗口方式下的自適應集成分類算法

孫艷歌1,2,王志海1, 原繼東1,韓 萌1

(1.北京交通大學 計算機與信息技術學院，北京 100044; 2.信陽師范學院 計算機與信息技術學院，河南 信陽 464000)

針對基于數(shù)據(jù)塊的集成算法，存在數(shù)據(jù)塊大小影響分類效果，且不能及時應對完整式概念漂移的問題，提出了一種考慮數(shù)據(jù)流局部特征的和能應對多種類型概念漂移的集成分類算法．用滑動窗口作為概念漂移檢測器，當檢測到概念漂移時，則建立新的分類器并加入到集成分類器中．本文提出的算法在人工合成和真實數(shù)據(jù)集上與經(jīng)典算法進行了廣泛的對比實驗．結果表明:提出的算法在分類準確率上具有明顯優(yōu)勢，消耗更少的內(nèi)存，更適合多種類型概念漂移的環(huán)境．

數(shù)據(jù)挖掘；數(shù)據(jù)流；概念漂移；集成分類器；滑動窗口

傳感器網(wǎng)絡異常檢測、信用卡欺詐行為監(jiān)測、天氣預報和電價預測等眾多實際問題中，數(shù)據(jù)都是以流的形式不斷產(chǎn)生的．這種快速到達的、實時的、連續(xù)的和無界的數(shù)據(jù)序列稱為數(shù)據(jù)流[1-4]．傳統(tǒng)的數(shù)據(jù)流挖掘與分析過程，一般假設數(shù)據(jù)是獨立同分布的．基于這種假設已經(jīng)研究與開發(fā)了許多實用的面向數(shù)據(jù)流的分類算法[5-7]．

在現(xiàn)實生活中數(shù)據(jù)流的數(shù)據(jù)分布常會隨著時間而變化[5]．如，天氣預報所依據(jù)改變的規(guī)律可能會隨著季節(jié)的變化而發(fā)生改變；顧客網(wǎng)上購物偏好分析方法可能會隨顧客群體的興趣、商家信譽和服務類型等因素的變化而改變；工業(yè)用電量會隨著季節(jié)交替出現(xiàn)周期性變化．一般地，把這種數(shù)據(jù)流的數(shù)據(jù)分布隨著時間以某種方式發(fā)生變化的現(xiàn)象稱為概念漂移[8-10]．近年來，針對概念漂移問題國內(nèi)外學者作了大量研究，主要分為基于實例選擇的方法，基于實例加權的方法和集成學習方法3類[10-12]．其中，集成學習方法通過在不同時段數(shù)據(jù)來訓練個體分類器來保留歷史概念，因此是一種有效的處理概念漂移的方法．概念漂移方式根據(jù)改變速度分為突變式和漸變式[10]，然而大多數(shù)算法只是針對某一類型進行處理的，一個理想的分類模型應能增量式的學習并能適應多種類型的變化．

基于數(shù)據(jù)塊的集成算法[2-3, 9, 13-15]將數(shù)據(jù)流劃分為大小相等的數(shù)據(jù)塊，不斷在最新數(shù)據(jù)塊上訓練并產(chǎn)生分類器，并添加到集成分類器中，周期更新權重，采用加權投票等原則來預測結果．這種方式有助于應對漸變式概念漂移，但存在數(shù)據(jù)塊大小影響分類效果的問題[2]，且不能應對突變式概念漂移．

本文作者設計并實現(xiàn)了一種能應對多種類型概念漂移的自適應數(shù)據(jù)塊大小的集成算法，涉及3個方面問題：概念漂移的類型及其檢測，數(shù)據(jù)塊大小對分類效果的影響，集成方式對算法性能的影響．主要貢獻如下：1)引入了滑動窗口檢測機制來應對突變式概念漂移；2)建立了一種數(shù)據(jù)塊大小的控制機制以適應數(shù)據(jù)變化的特征；3)構建了一種綜合考慮差異性和準確率的集成方式，以提高分類算法的泛化能力．

1 面向數(shù)據(jù)流的集成式分類研究背景

1.1 模型描述及相關概念

數(shù)據(jù)流可以表示為S= {s1,s2, …,st}，其中st=(xt,yt)為t時刻(t= 1, 2, …,T)的實例，xtRd是特征向量，yt{c1,c2, …,ck}是類值，k(k>1)為S中所包含的類值數(shù)．數(shù)據(jù)流理論上是源源不斷產(chǎn)生的．

若數(shù)據(jù)流中數(shù)據(jù)分布隨著時間以某種方式發(fā)生變化，則稱在該數(shù)據(jù)流中發(fā)生了概念漂移現(xiàn)象．更具體的從貝葉斯學習理論的角度來講，在t0到t1時刻發(fā)生了概念漂移可定義為[8]

?x:Pt0(x,y)≠Pt1(x,y)，

式中，Pt0(x,y)表示t0時刻一組輸入變量x與目標變量y的聯(lián)合概率分布．

若在較短的時間內(nèi)，數(shù)據(jù)流中數(shù)據(jù)分布突然地被另一個完全不同的數(shù)據(jù)分布所取代，則稱此時數(shù)據(jù)流中發(fā)生了突變式概念漂移．此類型的漂移通常在毫無征兆的情況下發(fā)生(如傳感器突然發(fā)生故障)，會使準確率急劇下降甚至模型完全失效．而漸變式概念漂移則是一種慢速率改變(如傳感器逐漸失靈)，通常是經(jīng)過較長一段時間后才能觀察到，且概念漂移發(fā)生前后概念之間有或多或少的相似．

1.2 相關工作

如何根據(jù)概念變化來更新基分類器的權重及采取何種集成策略是影響基于數(shù)據(jù)塊的集成算法的關鍵，數(shù)據(jù)流集成分類算法大多數(shù)是基于此進行研究的．文獻[13]提出數(shù)據(jù)流集成分類器算法(Streaming Ensemble Algorithm, SEA)，不斷在最新數(shù)據(jù)塊上訓練基分類器，采用啟發(fā)式策略替換性能最差的分類器，以此來適應概念變化．文獻[2]提出基于準確率加權集成(Accuracy Weighted Ensemble, AWE)算法，以分類器在最新數(shù)據(jù)塊上的分類錯誤率作為加權依據(jù)，但算法性能對數(shù)據(jù)塊大小設置依賴較大，且不能及時應對突變式概念漂移．文獻[9]提出的準確率更新集成(Accuracy Update Ensemble, AUE)算法，采用非線性的加權函數(shù)對基分類器進行加權．結果表明:比AWE準確率高且消耗更少內(nèi)存．文獻[3]提出的Learn++.NSE(Nonstationary Environment)算法采用類似AdaBoost算法的動態(tài)加權投票機制來適應概念漂移環(huán)境．為了解決概念變化頻繁的問題.文獻[14]提出的數(shù)據(jù)流集成分類器算法根據(jù)分類器分類情況制定分類器權重更新策略和分類器淘汰方法．文獻[15]提出了一種用于解決由數(shù)據(jù)集不平衡引起分類器分類性能下降問題的數(shù)據(jù)流集成分類算法．

上述算法的周期更新分類器權重方式，有助于應對漸變式概念漂移，但不能及時應對突變式概念漂移．文獻[2]中實驗表明:這與適當調(diào)整數(shù)據(jù)塊大小有一定關系．使用過小的數(shù)據(jù)塊在一定程度上有助于應對突發(fā)的概念漂移，但可能會由于訓練實例不足而導致過擬合．相反的，選用過大的數(shù)據(jù)塊可能會獲得更準確的分類器，但會消耗更多時間和內(nèi)存，且同一數(shù)據(jù)塊內(nèi)可能同時蘊含多個概念．為此，本文作者提出了一種能應對多種類型概念漂移的自適應集成算法．

2 滑動窗口方式下的自適應集成算法

2.1 概念漂移檢測方法

數(shù)據(jù)流中滑動窗口(Sliding Window，SW)是指在數(shù)據(jù)流上設定一個區(qū)間，該區(qū)間包含數(shù)據(jù)流最新的數(shù)據(jù)，目的是為了更好地獲取當前數(shù)據(jù)的特征[16]．文獻[17]通過比較不同子窗口之間的數(shù)據(jù)均值的差異來判斷是否發(fā)生概念漂移．而本文則通過檢測分類錯誤率的變化來檢測．采用指數(shù)直方圖(Exponential Histogram, EH)的概要數(shù)據(jù)結構來僅存放分類情況(分類正確為1;分類錯誤為0)．本文采用了一種基于Hoeffding不等式的概念檢測算法.通過比較兩個子窗口中數(shù)據(jù)分布是否存在顯著性差異來檢測概念漂移．

定理 Hoeffding不等式

(1)

(2)

式中：δ(0,1)為置信度；n0和n1分別表示W(wǎng)0和W1長度;n表示窗口W總長度；m為n0和n1的幾何平均值，而δ′則是為了避免出現(xiàn)多重假設檢驗問題．算法偽代碼如算法1．

算法1 滑動窗口概念檢測算法

輸出：ChangeAlarme;

01：begin

02：初始化窗口W;

03：for所有實例xt∈S do

04：at←xt的分類情況

05：W←W∪{xt};

06：repeat

07：刪除W中過時的實例;

09：end for

10：輸出ChangeAlarme;

11：end.

2.2 具有檢測機制的自適應集成分類算法

研究結果表明:具有較大差異性的分類器集成可顯著提高其泛化能力[18]，因此大多數(shù)集成學習方法都可看作是生成或選擇更具差異性的基分類器的過程．然而，大多數(shù)數(shù)據(jù)流集成算法僅僅考慮了分類準確率，沒有充分考慮分類器之間的差異性．為此，本文作者提出了一種兼顧正確率和差異性的和基于概念檢測的自適應集成算法(Adaptive Ensemble Based Detection, AED)．首先選取準確率較高的基分類器作為基準，然后通過計算與其余分類器間的差異性值，選擇與準確率最高的分類器差異性最大的k-1個分類器參與集成．

采用分類器的Q統(tǒng)計量來衡量分類器差異性指標值為

(3)

式中，Qij表示第i個分類器與第j個分類器之間的Q統(tǒng)計量;Nab為兩個分類器做出判斷的訓練樣本占總訓練樣本的比例．對于包含k個基分類器的集成分類器的Q統(tǒng)計量Div由所有成對分類器的Q統(tǒng)計平均值獲得

(4)

具體來說，在t時刻，當?shù)竭_一條實例xt后，首先增量式訓練新的分類器，若此時檢測有概念漂移發(fā)生或者緩存區(qū)滿，則建立新的分類器，并根據(jù)每個分類器Ci(i= 1,2,…,k)在B上的分類情況，按下式對其進行加權為

(5)

AED算法增量式訓練新的分類器，通過滑動窗口監(jiān)控錯誤率來檢測概念漂移．并把新到的實例放在緩存區(qū)B中，當檢測到概念漂移發(fā)生時，才把新建的基分類器加入到集成分類器中，并根據(jù)基分類器在B上的分類情況加權．其偽代碼如算法2．

算法2 AED算法偽代碼

輸入：數(shù)據(jù)流S; 概念檢測器 D; 基分類器數(shù)目k; 容量為d的緩存B

輸出：包含k個帶權重的基分類器的集成分類器E

02：for 所有實例xt∈S do

03：根據(jù)xt增量的訓練D；

04：B←B∪{xt};

05：if檢測到有概念漂移發(fā)生 or |B|=d then

06：依據(jù)B中的數(shù)據(jù)建立的新的分類器C′并加權;

07：對所有基分類器根據(jù)在B上的性能由式(5)加權;

08：if|E|

09：else if用基于準確度和差異的方式選出k-1個分類器集成；

10：初始化D;

12：else if

13：end for.

使用式(2)中的εcut定義，在每個時刻，AED算法具有如下性質(zhì)：1)當數(shù)據(jù)分布保持穩(wěn)定時，AED以最大為δ的概率檢測到概念漂移;2)當數(shù)據(jù)分布有顯著變化時，則AED以1 - δ的概率檢測到概念漂移．具體證明過程見文獻[17]．

3 實驗評價

實驗是在CPU為2.8 GHz，內(nèi)存為8 GB，操作系統(tǒng)為Windows 7的PC機上進行的，所有算法均在大規(guī)模數(shù)據(jù)在線分析開源平臺(Massive Online Analysis，MOA)[19]上實現(xiàn)．

3.1 數(shù)據(jù)集描述

實驗選取4個人工合成的和3個真實的數(shù)據(jù)集對所提出模型進行驗證．

1)HyperPlane是使用最廣泛的數(shù)據(jù)流數(shù)據(jù)集[2, 6, 12]，通過改變數(shù)據(jù)樣本屬性的權值來模擬概念漂移現(xiàn)象．實驗中用Generators.HyperplaneGenerator數(shù)據(jù)流產(chǎn)生器生成實例改變概率為0.001的漸變式概念漂移數(shù)據(jù)集．

2)SEA是Street于2001年提出的[13]經(jīng)典的突變式概念漂移數(shù)據(jù)集．其基本結構是f1, f2, f3, C，其中:f1、f2和f3為條件屬性;C為類屬性，僅f1，f2和C相關．當實例的屬性滿足f1+f2≤θ時，屬于第1類；否則屬于第2類．實驗中采用數(shù)據(jù)流產(chǎn)生器SEAGenerator生成包含3次突變的數(shù)據(jù)集，分別在300 000、600 000和900 000條實例處發(fā)生．

3)LED數(shù)據(jù)集包含用來預測7段數(shù)碼顯示器上顯示的數(shù)字的數(shù)據(jù)．實驗采用LEDGeneratorDrift數(shù)據(jù)流產(chǎn)生器生成包含24個屬性和兩個漸變式概念漂移，在第500 000條實例處發(fā)生一次概念突變的數(shù)據(jù)集．

4)Waveform數(shù)據(jù)集用來預測3種基準波形中的一種，每條實例包含40個數(shù)值型屬性，其中，19個為不相關屬性．采用WaveformGenerator數(shù)據(jù)流產(chǎn)生器生成沒有概念漂移的數(shù)據(jù)集．通過MOA中的ArffFileStream產(chǎn)生器將靜態(tài)的真實數(shù)據(jù)模擬生成數(shù)據(jù)流，這些數(shù)據(jù)均可在MOA網(wǎng)站上下載[19]．

5)Covertype數(shù)據(jù)集來自UCI數(shù)據(jù)庫[20]，包含4個野生區(qū)域覆蓋類型信息．該數(shù)據(jù)集包含581 012條實例，每條實例有53個屬性對應7種森林覆蓋類型中的一種．

6)Poker數(shù)據(jù)集來自UCI數(shù)據(jù)庫，包含1 025 010條實例，每條實例有10個屬性和10個類值．每條實例(每副牌)由5張牌組成，每張牌由牌面和花色兩個屬性來描述．

7)Electricity是應用最廣泛的真實數(shù)據(jù)流數(shù)據(jù)集，有45 312條實例，每條實例有7個屬性和2個類值．該數(shù)據(jù)集包含了澳大利亞新南威爾士電力市場能源價格受市場需求、供給、季節(jié)和天氣等因素變化影響的數(shù)據(jù)．

3.2 實驗設置及結果分析

實驗采用文獻[21]中提到的Prequential評價策略，這種評價策略不用扣留數(shù)據(jù)集來試，從而保證最大化利用每個數(shù)據(jù)的信息，也保證準確率隨時間具有平滑性．

AED算法與HT(Hoeffding Tree、 AWE和AUE,)3個算法進行對比:為了便于比較，集成算法均采用k=10個基分類器，基分類器均采用HT選取與文獻[6]相同的參數(shù)：葉子結點采用Adaptive Na?ve Bayes預測類值，其中nmin=100，δ=0.01，τ=0.05．滑動窗口檢測算法的參數(shù)：δ=0.002．從分類準確率、運行時間和內(nèi)存消耗3個方面進行比較．

1)在分類準確率方面，如表1所示算法在7個數(shù)據(jù)集的情況．總體來看，集成算法獲得比單分類器算法要高的分類準確率．通過比較分析發(fā)現(xiàn)，在沒有概念漂移數(shù)據(jù)集Waveform上，由于數(shù)據(jù)分布相對比較穩(wěn)定，所有算法差別并不大，AED并沒有明顯優(yōu)勢．而在漸變式數(shù)據(jù)集HyperPlane上，AWE和AUE獲得了最高準確率，分析原因是由于這些算法不斷在最新數(shù)據(jù)塊上訓練生成分類器，能及時應對此類型概念漂移．而在突變式數(shù)據(jù)集SEA和混合式數(shù)據(jù)集LED上，AED都獲得了最高的準確率，這是由于增加了概念漂移檢測機制，能及時建立新的分類器來適應突然的概念變化，同時算法在保留周期加權機制的同時，增加對突變式概念漂移的檢測，更適合具有多種類型概念漂移的環(huán)境．而HT算法在包含概念漂移的數(shù)據(jù)集上均表現(xiàn)最差，這是由于HT沒有任何處理概念漂移機制，因此不適合概念漂移環(huán)境．在真實數(shù)據(jù)集Covertype上，AED表現(xiàn)最好；在Poker上表現(xiàn)最好的是AUE；在Electricity上，所有算法差別并不大．AED較合理地兼顧了正確率和差異性，較好地克服了根據(jù)單一指標的集成分類器適用性差的缺點，因此在真實環(huán)境中表現(xiàn)出較強的泛化能力．

表1 不同算法分類準確率Tab.1 Classification accuracies of different algorithms %

從圖1中分析發(fā)現(xiàn)，在SEA數(shù)據(jù)集中發(fā)生了3次突變，所有算法變化趨勢基本一致．圖中k等于1 000.每當發(fā)生概念漂移時所有算法的準確率均會有瞬時波動，而AED維持了較高的、平穩(wěn)的準確率．這表明了AED能及時檢測到這種變化，并及時根據(jù)概念的變化來建立分類器，從而達到應對這種類型概念漂移的效果．

從圖2在噪聲最大和實例數(shù)目最多的包含多種類型概念漂移的數(shù)據(jù)集LED上，準確率隨著處理數(shù)據(jù)增多而變化的情況．分析得知：在圖2中當數(shù)據(jù)比較穩(wěn)定時，所有算法都保持了較高的和平穩(wěn)的準確率，本文算法并無明顯優(yōu)勢；當在第500 k個實例處發(fā)生概念突變時，除了AED所有算法的準確率都急劇下降．AED能快速捕捉到概念變化，并建立新的分類器，從而及時應對這種變化．由于數(shù)據(jù)中添加了10%的噪音，也表明了AED具有抗噪聲能力．

2)在運行時間方面，如表2所示．比較分析發(fā)現(xiàn)，單分類器算法比集成分類算法消耗更少的時間.其中，HT的運行時間最短，其次是AED，而AWE時間消耗最長．

3)在內(nèi)存消耗方面，如表3所示.比較分析發(fā)現(xiàn)，HT的內(nèi)存消耗最少，其次是AED，由于AUE采用了剪枝策略，因此消耗比AWE算法要少的內(nèi)存．而AED是根據(jù)部分數(shù)據(jù)來建立分類器，且只需要存儲數(shù)據(jù)的分類準確率，因此消耗更少的內(nèi)存．

表2 不同算法運行時間Tab.2 Running times of different algorithms s

表3不同算法的內(nèi)存消耗Tab.3 Memory usage of different algorithms MB

4 總結與展望

本文詳細分析了幾種經(jīng)典的數(shù)據(jù)流集成分類算法及相關理論基礎與研究背景．針對數(shù)據(jù)塊集成算法存在的問題，提出了一種具有概念漂移檢測機制的、兼顧正確率和差異性的自適應集成算法．理論分析和實驗結果得出以下結論：1)本文算法在包含突變式和混合式概念漂移的數(shù)據(jù)集上具有明顯優(yōu)勢；2)本文算法在保持較高的分準確率情況下，消耗相對較少的時間和內(nèi)存代價；3)本文算法對噪聲具有一定的健壯性．

目前的數(shù)據(jù)流學習算法主要針對有標記的數(shù)據(jù)進行處理的，未考慮數(shù)據(jù)帶有缺失屬性值或不完全類標識的情況．因此，如何在動態(tài)數(shù)據(jù)流環(huán)境下利用少量的標簽實例信息指導無標簽實例的標記，進而開展概念漂移檢測與分類是進一步研究的問題．

[1] COHEN L, AVRAHAMI-BAKISH G, LAST M, et al. Real-time data mining of non-stationary data streams from sensor networks[J]. Information Fusion, 2008,9(3):344-353.

[2] WANG H, FAN W,YU P S, et al. Mining concept-drifting data streams using ensembles classifiers[C]. Proceedings of Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003: 226-235.

[3] ELWELL R, POLIKAR R. Incremental learning of concept drift in nonstationary environments[J]. IEEE Transactions on Neural Networks,2011, 22(10): 1517-1531.

[4] GAMA J.Knowledge discovery from data streams[M]. New York: CRC Press, 2010.

[5] GABER M M, ZASLAVSKY A, KRISHNASWAMY S. Mining data streams: A review[J]. ACM Sigmod Record, 2005,34(2):18-26.

[6] DOMINGOS P, HULTEN G. Mining high-speed data streams[C]. Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining New York, 2000: 71-80.

[7] 王濤，李舟軍，顏躍進，等. 數(shù)據(jù)流挖掘分類技術綜述[J]. 計算機研究與發(fā)展, 2007， 44(11)：1809-1815. WANG Tao, LI Zhoujun, YAN Yuejin, et al. A survey of classification of data streams[J].Journal of Computer Research and Development, 2007, 44 (11): 1809-1815. (in Chinese)

[8] WIDMER G, KUBAT M . Learning in the presence of concept drift and hidden contexts[J]. Machine Learning, 1996,23(1): 69-101.

[9] BRZEZINSK D, STEFANOWSKI J. Reacting to different types of concept drift: The accuracy updated ensemble algorithm[J]. IEEE Transactions on Neural Networks and Learning Systems, 2014,25(1): 81-94.

[10] TSYMBAL A. Problem of concept drift: Definitions and related work. technical report[R].Dublin: Trinity College, 2004.

[11] GAMA J, ZLIOBAIT I, BIFET A, et al. A survey on concept drift adaptation[J]. ACM Computing Surveys, 2014,46(4):231-238.

[12] 文益民，強保華，范志剛．概念漂移數(shù)據(jù)流分類研究綜述[J]．智能系統(tǒng)學報，2013，8(2):95-104. WEN Yimin, QIANG Baohua, FAN Zhigang. A survey of the classification of data streams with concept drift [J]. Transactions on Intelligent Systems, 2013，8(2):95-104. (in Chinese)

[13] STREET W N,KIM Y S. A streaming ensemble algorithm (SEA) for large-scale classification[C]. Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2001:377-382.

[14] 孫岳，毛國君，劉旭，等. 基于多分類器的數(shù)據(jù)流中的概念漂移挖掘[J].自動化學報，2008，34(1): 93-96. SUN Yue, MAO Guojun,LIU Xu, et al. Mining concept drifts from data streams based on multi-classifiers[J]. Acta Automatica Sinica，2008，34(1): 93-96. (in Chinese)

[15] 歐陽震凈，羅建書，胡東敏，等. 一種不平衡數(shù)據(jù)流集成分類模型[J]. 電子學報，2010, 38(1): 184-189. OUYANG Zhenjing, LUO Jianshu, HU Dongming, et al. An ensemble classifier framework for mining imbalanced data streams[J]. Acta Electronica Sinica, 2010, 38(1): 184-189. (in Chinese)

[16] DATAR M, GIONIS A, INDYK P, et al. Maintaining stream statistics over sliding windows[C]. SIAM Journal on Computing, 2002,31(6): 1794-1813.[17] BIFET A,GAVALDA R. Learning from time-changing data with adaptive windowing[C].Proceedings of the Seventh SIAM International Conference on Data Mining, 2007: 443-448.

[18] KUNCHEVA L I, WHITAKER C J. Measures of diversity in classifier ensembles and their relationship with the ensemble accuracy[J]. Machine Learning,2003,51(2) :181-207.

[19] BIFET A, HOLMES G,KIRKBY R, et al. MOA: Massive online analysis[J]. Journal of Machine Learning Research, 2010,11:1601-1604.

[20] LICHMAN M. UCI Machine Learning Repository [EB/OL].[2016-09-05].http://archive.ics.uci.edu/ml. [21] GAMA J, SEBASTIAO R,RODRIGUES P P. Issues in evaluation of stream learning algorithms[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009: 329-338.

Adaptive ensemble algorithm based on sliding windows model for data streams

SUNYange1，2,WANGZhihai1，YUANJidong1,HANMeng1

(1.School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044,China; 2.School of Computer and Information Technology, Xinyang Normal University, Xinyang Henan 464000,China)

The main drawback of block-based ensembles is the difficulty of tuning the block size to offer a compromise between fast reactions to drifts. Motivated by this challenge, an adaptive ensemble for evolving data streams is proposed to deal with different types of drift. The algorithm uses the adaptive window algorithm as a change detector. When a change is detected, the worst classifier of the ensemble is removed and a new is added. The proposed algorithm is experimentally compared with the state-of-the-art algorithms on synthetic and real datasets. Out of all the compared algorithms, the proposed algorithm provided higher classification accuracy while proving to be less memory consuming than other approaches. Experimental results show that the proposed algorithm can be considered suitable for scenarios, involving different types of drift as well as static environments.

data mining; data streams; concept drift; ensemble classifier; sliding windows

2016-01-15

國家自然科學基金資助項目(61572005)；北京市自然科學基金資助項目(4142042)；信陽師范學院青年骨干教師資助計劃項目資助(2016GGJS-08)

孫艷歌(1982—)，女，河南平頂山人，講師，博士生.研究方向為數(shù)據(jù)挖掘和機器學習.email: 13112074@bjtu.edu.cn.

王志海( 1963—)，男，河南安陽人，教授，博士，博士生導師. email：zhhwang@bjtu.edu.cn.

TP181

A

1673-0291(2016)05-0009-07

10.11860/j.issn.1673-0291.2016.05.002