郭虎升 任巧燕 王文劍

1(山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 太原 030006)2(計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室(山西大學(xué)) 太原 030006)

目前，在實(shí)際應(yīng)用領(lǐng)域中均涌現(xiàn)出大量動(dòng)態(tài)數(shù)據(jù)，如網(wǎng)頁(yè)點(diǎn)擊數(shù)據(jù)[1]、在線欺詐檢測(cè)[2]、垃圾郵件過(guò)濾[3]等，這些數(shù)據(jù)不同于傳統(tǒng)靜態(tài)數(shù)據(jù)，而是作為一種持續(xù)不斷產(chǎn)生、實(shí)時(shí)性較強(qiáng)的流式數(shù)據(jù)存在，被稱為流數(shù)據(jù)[4-5].近年來(lái)，伴隨著流數(shù)據(jù)的大量產(chǎn)生，在線學(xué)習(xí)在機(jī)器學(xué)習(xí)領(lǐng)域受到越來(lái)越多的關(guān)注，其目的是使得學(xué)習(xí)模型對(duì)當(dāng)前數(shù)據(jù)做出實(shí)時(shí)響應(yīng)[6-7].流數(shù)據(jù)又可分為穩(wěn)定數(shù)據(jù)流與動(dòng)態(tài)數(shù)據(jù)流，穩(wěn)定數(shù)據(jù)流具有獨(dú)立同分布特點(diǎn)，而動(dòng)態(tài)數(shù)據(jù)流則不是獨(dú)立同分布的，其典型特征是由環(huán)境等因素變化使得數(shù)據(jù)中隱含的目標(biāo)概念發(fā)生變化，即發(fā)生概念漂移[8].流數(shù)據(jù)中存在的概念漂移使得已有方法難以滿足用戶對(duì)漂移檢測(cè)精確度、時(shí)空性能等方面的要求，如客戶行為模式隨時(shí)間推移會(huì)發(fā)生變化，這種變化中隱含著商機(jī)，而商家為發(fā)現(xiàn)客戶行為模式的變化并對(duì)銷(xiāo)售情況進(jìn)行預(yù)測(cè)，會(huì)搜集越來(lái)越多的實(shí)時(shí)數(shù)據(jù)，如銷(xiāo)售圖表和客戶數(shù)據(jù)，從而動(dòng)態(tài)地調(diào)整預(yù)測(cè)模型，因此在對(duì)流數(shù)據(jù)學(xué)習(xí)時(shí)，檢測(cè)其存在的概念漂移并實(shí)時(shí)動(dòng)態(tài)調(diào)整模型對(duì)準(zhǔn)確把握流數(shù)據(jù)中的關(guān)鍵信息具有重要意義.

針對(duì)流數(shù)據(jù)中存在的概念漂移問(wèn)題，目前提出的檢測(cè)方法大體可分為增量學(xué)習(xí)[9]與集成學(xué)習(xí)[10-11].這2類方法均是在流數(shù)據(jù)劃分的基礎(chǔ)上進(jìn)行的，而數(shù)據(jù)劃分一般通過(guò)在線窗口(本文將其稱為時(shí)序窗口)技術(shù)或思想實(shí)現(xiàn).增量學(xué)習(xí)方法采用單個(gè)分類器對(duì)流數(shù)據(jù)進(jìn)行學(xué)習(xí)，通過(guò)動(dòng)態(tài)調(diào)整模型以達(dá)到適應(yīng)流數(shù)據(jù)變化的特點(diǎn)，如：基于滑動(dòng)窗口的概念漂移檢測(cè)方法通過(guò)窗口的不斷向前滑動(dòng)來(lái)獲得新的樣本進(jìn)行增量學(xué)習(xí)，并與舊分布數(shù)據(jù)相比較來(lái)檢測(cè)概念漂移[12-13]；自適應(yīng)的增量貝葉斯方法對(duì)流數(shù)據(jù)中較難分類的歷史樣本進(jìn)行單獨(dú)處理以得到先驗(yàn)概率，并結(jié)合主動(dòng)學(xué)習(xí)的半監(jiān)督方法計(jì)算當(dāng)前樣本的后驗(yàn)概率以檢測(cè)概念漂移[14-15].盡管增量學(xué)習(xí)策略在解決概念漂移檢測(cè)問(wèn)題中起到了重要作用，且由于單個(gè)分類器的遺忘機(jī)制對(duì)新概念反應(yīng)迅速，通常不受舊概念影響，對(duì)突變類概念漂移具有較高的適應(yīng)性，但其仍然存在時(shí)序?qū)W習(xí)過(guò)程中復(fù)雜度的累積效應(yīng)、增量樣本選擇困難、模型不收斂、學(xué)習(xí)結(jié)果不穩(wěn)定、不適用于漸變類概念漂移檢測(cè)等多方面問(wèn)題.

集成學(xué)習(xí)方法利用歷史數(shù)據(jù)構(gòu)建一系列子學(xué)習(xí)器，借助投票加權(quán)機(jī)制進(jìn)行集成決策，當(dāng)概念漂移發(fā)生時(shí)，根據(jù)各學(xué)習(xí)器在當(dāng)前數(shù)據(jù)的學(xué)習(xí)效果進(jìn)行權(quán)值調(diào)整，從而較好地適應(yīng)流數(shù)據(jù)中的概念漂移.Soares等人[16]提出了一種基于回歸模型的在線加權(quán)集成(on-line weighted ensemble, OWE)方法，它能在概念重復(fù)出現(xiàn)的情況下保留舊的概念信息；Song等人[17]提出了一種新的集成模型，即動(dòng)態(tài)聚類森林(dynamic clustering forest, DCF)，用于文本流分類的概念漂移；在線深度學(xué)習(xí)將深度學(xué)習(xí)與集成學(xué)習(xí)結(jié)合在一起，能夠從流數(shù)據(jù)中學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)模型，并對(duì)神經(jīng)網(wǎng)絡(luò)中不同層次網(wǎng)絡(luò)進(jìn)行集成，可獲得更高的分類精度并檢測(cè)流數(shù)據(jù)中存在的概念漂移[18]；文益民等人[19]借助遷移學(xué)習(xí)思想，將歷史概念的學(xué)習(xí)器與目標(biāo)領(lǐng)域的學(xué)習(xí)器進(jìn)行集成，實(shí)現(xiàn)從源領(lǐng)域到目標(biāo)領(lǐng)域的知識(shí)遷移，提高了概念漂移檢測(cè)的準(zhǔn)確率及模型的收斂性能.集成學(xué)習(xí)方法的模型構(gòu)建簡(jiǎn)單，對(duì)流數(shù)據(jù)學(xué)習(xí)效果較好，但往往由于模型中包含歷史數(shù)據(jù)較多，不能及時(shí)對(duì)概念漂移做出反應(yīng)，模型實(shí)時(shí)性能較差.

目前還有一些研究將二者結(jié)合，充分利用各自優(yōu)點(diǎn)來(lái)提升概念漂移檢測(cè)方法的性能.Lu等人[20]將基于競(jìng)爭(zhēng)模型的增量學(xué)習(xí)與在線集成學(xué)習(xí)方法LEARN++相結(jié)合，提出了基于競(jìng)爭(zhēng)模型的概念漂移檢測(cè)方法，并從理論上證明了其統(tǒng)計(jì)意義下的性能；潘吳斌等人[21]結(jié)合增量學(xué)習(xí)和集成學(xué)習(xí)，引入當(dāng)前數(shù)據(jù)建立的新分類器進(jìn)行學(xué)習(xí)器更新，并與舊分類器進(jìn)行加權(quán)集成，解決了網(wǎng)絡(luò)流量監(jiān)控中的概念漂移問(wèn)題.

然而，由于實(shí)際應(yīng)用領(lǐng)域數(shù)據(jù)流發(fā)生的概念漂移具有隱含、未知、易變以及多樣等復(fù)雜特點(diǎn)，按照概念漂移發(fā)生時(shí)數(shù)據(jù)分布的變化情況可大體上分為2類：突變類概念漂移與漸變類概念漂移[22].概念的突然漂移意味著原始數(shù)據(jù)分布在很短時(shí)間內(nèi)直接改變?yōu)樾碌臄?shù)據(jù)分布，如股票的漲停是在短時(shí)間內(nèi)突然變化的；而概念的逐漸漂移意味著在一段時(shí)間內(nèi)服從舊分布的數(shù)據(jù)逐漸減少，服從新分布的數(shù)據(jù)逐漸增多，直到新分布取代舊分布，如工廠中不斷磨損的器械會(huì)逐漸影響其加工出的零件質(zhì)量.不同類別概念漂移蘊(yùn)含的實(shí)時(shí)信息往往存在差異，因此，如何快速有效地發(fā)現(xiàn)不同類別概念漂移的特征，對(duì)概念漂移類別進(jìn)行劃分，并依據(jù)概念漂移類別提供有針對(duì)性的應(yīng)對(duì)策略以加速在線模型收斂是一個(gè)有重要意義的研究課題.

現(xiàn)有概念漂移檢測(cè)方法大多是針對(duì)單一類型的概念漂移提出的(即僅檢測(cè)突變類概念漂移或僅檢測(cè)漸變類概念漂移)，難以同時(shí)適應(yīng)多種漂移特征.針對(duì)這個(gè)問(wèn)題，本文提出一種有效檢測(cè)概念漂移并進(jìn)行類別判斷的方法，主要貢獻(xiàn)有2個(gè)方面：

1) 給出不同類別概念漂移的特征描述，以此為基礎(chǔ)提出流數(shù)據(jù)概念漂移類別的劃分方式；

2) 以不同類別概念漂移為檢測(cè)目標(biāo)，提出基于時(shí)序窗口機(jī)制的概念漂移類別判斷方法.

1 概念漂移類別描述及分析

1) 突變類概念漂移(sudden concept drift)[23].假設(shè)流數(shù)據(jù)初始分布為Φ，在時(shí)刻t之后到來(lái)的數(shù)據(jù)服從的分布以迅速且不可逆的方式變?yōu)榱硪环N分布Φ′，形式化描述為{D1,D2,…,Dt-1}～Φ，{Dt,…}～Φ′，即在時(shí)刻t處發(fā)生概念漂移，且此類概念漂移具有永久性，一旦發(fā)生原始數(shù)據(jù)分布信息立刻被新的分布信息不可逆轉(zhuǎn)地覆蓋掉,如圖1(a)所示.

2) 漸變類概念漂移(gradual concept drift)[23].類似地假設(shè)流數(shù)據(jù)初始分布為Φ，在時(shí)刻t之后到來(lái)的數(shù)據(jù)服從的分布持續(xù)發(fā)生變化，經(jīng)過(guò)一段時(shí)間間隔后流數(shù)據(jù)服從新的分布Φ′，描述為：{D1,D2,…,Dt-1}～Φ，{Dt+m,…}～Φ′，而二者之間的m個(gè)時(shí)間間隔內(nèi)每個(gè)子序列的數(shù)據(jù){Dt,…,Dt+m-1}一部分服從Φ，另一部分服從Φ′，且按照先后順序滿足規(guī)律：服從舊分布的數(shù)據(jù)逐漸減少，服從新分布的數(shù)據(jù)逐漸增多,如圖1(b)所示.漸變類概念漂移發(fā)生時(shí)，樣本從一種分布過(guò)渡到另一種分布需要經(jīng)過(guò)一段時(shí)間，且該段時(shí)間內(nèi)數(shù)據(jù)分布信息隨時(shí)間緩慢變化.

Fig. 1 Concept drift class diagram

在實(shí)際的流數(shù)據(jù)挖掘應(yīng)用問(wèn)題中，相同時(shí)間間隔內(nèi)產(chǎn)生的樣本規(guī)模可能不同，即不同的Dt中n值可能不同，若按時(shí)間間隔對(duì)流數(shù)據(jù)進(jìn)行劃分，則得到的不同模型之間可比性較小，因此本文在對(duì)數(shù)據(jù)進(jìn)行學(xué)習(xí)時(shí)設(shè)定學(xué)習(xí)單元的閾值為ω(即一個(gè)學(xué)習(xí)單元的樣本容量)，并按照所設(shè)閾值對(duì)數(shù)據(jù)流進(jìn)行劃分，劃分后的每部分?jǐn)?shù)據(jù)稱為一個(gè)學(xué)習(xí)單元.若當(dāng)前時(shí)間間隔內(nèi)未被學(xué)習(xí)的樣本數(shù)量大于該閾值，則按照先后順序取前ω個(gè)數(shù)據(jù)作為一個(gè)單元，其余數(shù)據(jù)自動(dòng)劃分到下一個(gè)單元；若當(dāng)前時(shí)間段未被學(xué)習(xí)的數(shù)據(jù)小于該閾值，則繼續(xù)等待新數(shù)據(jù)，直到數(shù)據(jù)量達(dá)到該閾值時(shí)進(jìn)行新的學(xué)習(xí)過(guò)程.通過(guò)對(duì)流數(shù)據(jù)進(jìn)行等量劃分，可將其表示為SD={X1,X2,…,Xh,…}，其中Xh表示對(duì)樣本重新進(jìn)行劃分后的第h個(gè)學(xué)習(xí)單元.

不難看出，突變類概念漂移與漸變類概念漂移的最大區(qū)別在于樣本分布規(guī)律從一種分布過(guò)渡到另一種分布所需的時(shí)間不同，這個(gè)過(guò)程為漂移過(guò)程.為便于描述，本文利用漂移過(guò)程中包含的學(xué)習(xí)單元數(shù)量——漂移跨度(Span)，來(lái)衡量漂移過(guò)程所需時(shí)間.對(duì)于突變類概念漂移，其漂移跨度為1，而漸變類概念漂移的跨度則大于1.

2 基于時(shí)序窗口機(jī)制的概念漂移類別檢測(cè)

針對(duì)傳統(tǒng)概念漂移檢測(cè)方法檢測(cè)目標(biāo)單一且對(duì)于概念漂移分類研究較少的問(wèn)題，本文提出了一種基于時(shí)序窗口機(jī)制的概念漂移類別檢測(cè)(concept drift class detection based on time window, CD-TW)方法.該方法的主要貢獻(xiàn)為：

1) 擴(kuò)展窗口技術(shù)，本文在概念漂移節(jié)點(diǎn)檢測(cè)階段利用節(jié)點(diǎn)時(shí)序窗口不斷加載最新數(shù)據(jù)，以檢測(cè)流數(shù)據(jù)中的概念漂移節(jié)點(diǎn)，剔除歷史信息干擾，保證高速有效學(xué)習(xí)；在漂移跨度檢測(cè)階段，在不降低算法實(shí)時(shí)性的基礎(chǔ)上，采用向未來(lái)“借數(shù)據(jù)”的思想，創(chuàng)建跨度時(shí)序窗口檢測(cè)漂移跨度，解決增量學(xué)習(xí)中存在的復(fù)雜度累積效應(yīng)與樣本選擇困難問(wèn)題，也解決了集成學(xué)習(xí)中基學(xué)習(xí)器敏感性較低的問(wèn)題.

2) 采用棧和隊(duì)列的數(shù)據(jù)結(jié)構(gòu)在學(xué)習(xí)過(guò)程中按照流數(shù)據(jù)時(shí)效性對(duì)其進(jìn)行高效合理的組織，不以舍棄歷史數(shù)據(jù)來(lái)提高時(shí)效性和敏感度；本文在檢測(cè)到概念漂移節(jié)點(diǎn)后，進(jìn)一步通過(guò)檢測(cè)跨度實(shí)現(xiàn)其類別判斷，處理目標(biāo)不再單一，可以更有針對(duì)性地進(jìn)行在線模型調(diào)整.

2.1 概念漂移節(jié)點(diǎn)檢測(cè)

首先，需要定義當(dāng)前數(shù)據(jù)緩存區(qū)(current data buffer,CD_buffer)和歷史數(shù)據(jù)緩存區(qū)(historical data buffer,HD_buffer)，分別用于存放新到的未被處理的數(shù)據(jù)和已經(jīng)處理過(guò)的數(shù)據(jù)，在CD_buffer中以隊(duì)列結(jié)構(gòu)存取數(shù)據(jù)，在HD_buffer中以堆棧結(jié)構(gòu)存取數(shù)據(jù).當(dāng)流數(shù)據(jù)進(jìn)入CD_buffer后，首先按照學(xué)習(xí)單元閾值ω將數(shù)據(jù)進(jìn)行等規(guī)模劃分，可以容納一個(gè)學(xué)習(xí)單元的窗口稱為基礎(chǔ)時(shí)序窗口.隨后創(chuàng)建2個(gè)容量相同的基礎(chǔ)節(jié)點(diǎn)時(shí)序窗口w1(參考窗口)和w2(滑動(dòng)窗口).

概念漂移節(jié)點(diǎn)檢測(cè)的過(guò)程包含數(shù)據(jù)準(zhǔn)備和漂移節(jié)點(diǎn)檢測(cè)2個(gè)過(guò)程：

1) 數(shù)據(jù)準(zhǔn)備

CD_buffer→HD_buffer：隊(duì)頭數(shù)據(jù)轉(zhuǎn)移；

HD_buffer→w1：棧頂數(shù)據(jù)復(fù)制；

CD_buffer→HD_buffer：隊(duì)頭數(shù)據(jù)轉(zhuǎn)移；

HD_buffer→w2：棧頂數(shù)據(jù)復(fù)制.

2) 漂移節(jié)點(diǎn)檢測(cè)

(1)

若ph滿足ph<τ(τ為漂移節(jié)點(diǎn)探測(cè)參數(shù))，則將h作為概念漂移節(jié)點(diǎn)輸出，反之繼續(xù)通過(guò)CD_buffer→HD_buffer的數(shù)據(jù)轉(zhuǎn)移與HD_buffer→w2的數(shù)據(jù)復(fù)制來(lái)完成更新和檢測(cè)工作，直到找到滿足ph<τ的學(xué)習(xí)單元所在節(jié)點(diǎn)時(shí)停止概念漂移節(jié)點(diǎn)檢測(cè)過(guò)程，如圖2所示：

Fig. 2 Concept drift site detection

在每輪概念漂移節(jié)點(diǎn)檢測(cè)過(guò)程中，參考窗口w1僅加載初始學(xué)習(xí)單元，且不進(jìn)行更新，對(duì)于將來(lái)的概念漂移而言，其中包含的數(shù)據(jù)始終代表原始分布，故將其作為本次檢測(cè)的基準(zhǔn)；滑動(dòng)窗口w2中的數(shù)據(jù)則隨著緩沖區(qū)之間的數(shù)據(jù)流動(dòng)不斷更新，直到第h個(gè)學(xué)習(xí)單元所得到的探測(cè)流動(dòng)比滿足漂移探測(cè)參數(shù)時(shí)停止，此時(shí)該學(xué)習(xí)單元內(nèi)存在概念漂移.圖2中十字箭頭標(biāo)注處的學(xué)習(xí)單元為概念漂移檢測(cè)的起始節(jié)點(diǎn)，本輪檢測(cè)完成后找到概念漂移節(jié)點(diǎn)(同心圓標(biāo)注位置)，在檢測(cè)過(guò)程中逐步將舊數(shù)據(jù)轉(zhuǎn)移到HD_buffer中.

2.2 概念漂移跨度檢測(cè)

1) 數(shù)據(jù)準(zhǔn)備

CD_buffer→R：隊(duì)頭數(shù)據(jù)復(fù)制.

2) 漂移跨度檢測(cè)

利用學(xué)習(xí)器對(duì)R所包含的每個(gè)基窗口數(shù)據(jù)進(jìn)行訓(xùn)練測(cè)試得到相應(yīng)的測(cè)試精度，假設(shè)分別為AccR1，AccR2，…，AccRk，計(jì)算其均值及方差：

Fig. 3 Concept drift span detection

(2)

(3)

圖3中短箭頭標(biāo)注位置為概念漂移節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，即跨度時(shí)序窗口檢測(cè)起點(diǎn).跨度時(shí)序窗口R中的數(shù)據(jù)直接從CD_buffer隊(duì)頭加載，檢測(cè)過(guò)程需要不斷完成CD_buffer隊(duì)頭到HD_buffer棧頂?shù)臄?shù)據(jù)轉(zhuǎn)移和CD_buffer隊(duì)頭到R的數(shù)據(jù)復(fù)制.在得到概念漂移跨度之后，即可根據(jù)漂移跨度確定概念漂移類別，若漂移跨度等于1，則對(duì)應(yīng)的概念漂移為突變類，反之則為漸變類.

由于流數(shù)據(jù)不斷產(chǎn)生，因此節(jié)點(diǎn)檢測(cè)和跨度檢測(cè)2個(gè)過(guò)程循環(huán)進(jìn)行，每一輪檢測(cè)只關(guān)注當(dāng)前數(shù)據(jù)是否存在概念漂移，若存在則計(jì)算其跨度，否則繼續(xù)向前檢測(cè)概念漂移節(jié)點(diǎn).

2.3 CD-TW方法

本文采用時(shí)序窗口機(jī)制對(duì)流數(shù)據(jù)進(jìn)行學(xué)習(xí)，檢測(cè)其中的概念漂移節(jié)點(diǎn)并對(duì)其劃分類別.該方法將流數(shù)據(jù)劃分為均等的學(xué)習(xí)單元，對(duì)每個(gè)單元進(jìn)行獨(dú)立高效學(xué)習(xí)，通過(guò)計(jì)算探測(cè)流動(dòng)比來(lái)檢測(cè)概念漂移節(jié)點(diǎn)；在此基礎(chǔ)上，分析跨度時(shí)序窗口中所包含數(shù)據(jù)的分布穩(wěn)定性，計(jì)算漂移跨度并對(duì)概念漂移類別進(jìn)行劃分.該方法流程如圖4所示：

Fig. 4 Concept drift class detection process

算法1展示了基于時(shí)序窗口機(jī)制的概念漂移類別檢測(cè)的具體過(guò)程.

算法1.基于時(shí)序窗口的概念漂移類別檢測(cè)(CD-TW)算法.

輸出：概念漂移節(jié)點(diǎn)、跨度及類別(h,m,Class).

① while流數(shù)據(jù)序列SD未結(jié)束

② 加載新到的X子序列到CD_Buffer當(dāng)中；

③ whileCD_Buffer中數(shù)據(jù)規(guī)模大于等于ω

④ 移動(dòng)CD_Buffer中隊(duì)頭數(shù)據(jù)單元到

HD_Buffer棧頂；

⑥h=0初始漂移節(jié)點(diǎn)探測(cè)流動(dòng)比p0=1；

⑦ whileph≥τ

⑧h=h+1;

⑨ 移動(dòng)CD_Buffer中隊(duì)頭數(shù)據(jù)單元到HD_Buffer棧頂；

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

為驗(yàn)證所提算法在概念漂移檢測(cè)與類別判斷方面的性能，本文分別在7個(gè)UCI(University of California Irvine)標(biāo)準(zhǔn)數(shù)據(jù)集和3個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)平臺(tái)為Windows10，CPU為酷睿i7-3210，內(nèi)存為8 GB，語(yǔ)言為Matlab2016b.實(shí)驗(yàn)中，將本文提出的CD-TW方法與基于單窗口機(jī)制的概念漂移檢測(cè)方法(single-windows-based classifi-cation algorithm for concept drifting data streams, SWCDS)[12]、基于雙窗口的概念漂移檢測(cè)方法(double-windows-based classification algorithm for concept drifting data streams, DWCDS)[12]和基于遷移學(xué)習(xí)的概念漂移檢測(cè)方法(concept drift online learning, CDOL)[24]進(jìn)行對(duì)比.由于SVM在小規(guī)模樣本上具有良好的泛化性能，因此本文選擇LIBSVM作為基礎(chǔ)分類器來(lái)構(gòu)建模型，由于SVM本身參數(shù)選擇不是本文的研究重點(diǎn)，其具體選擇方法目前已經(jīng)有較多研究[25-26]，本文實(shí)驗(yàn)中均取默認(rèn)值.

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

1) UCI數(shù)據(jù)集.UCI是用于機(jī)器學(xué)習(xí)的標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)，可方便設(shè)置概念漂移節(jié)點(diǎn)、模擬不同類別概念漂移，以檢驗(yàn)算法對(duì)不同類別概念漂移的識(shí)別能力.實(shí)驗(yàn)中利用正反例互換方式來(lái)模擬概念漂移中樣本分布的變化.實(shí)驗(yàn)采用的UCI數(shù)據(jù)集如表1所示:

Table 1 UCI Datasets Used in Experiment

2) 真實(shí)數(shù)據(jù)集.實(shí)驗(yàn)采用的真實(shí)數(shù)據(jù)集包括KDDCup99[27]，USPS[28]，MITface[29].其中，KDDCup99是網(wǎng)絡(luò)入侵檢測(cè)數(shù)據(jù)，常用于模擬漂移數(shù)據(jù)以驗(yàn)證算法有效性；USPS為美國(guó)郵政手寫(xiě)數(shù)據(jù)集；MITface來(lái)自MIT的人臉實(shí)例庫(kù).KDDCup99，USPS，MITface數(shù)據(jù)集的具體信息如表2所示:

Table 2 Realistic Datasets Used in Experiment

3.2 參數(shù)設(shè)置及漸變類漂移模擬

1) 參數(shù)設(shè)置.為充分驗(yàn)證本文所提出的概念漂移類別檢測(cè)方法的性能，本文采用不同的學(xué)習(xí)單元規(guī)模參數(shù)ω、漂移探測(cè)參數(shù)τ和跨度探測(cè)參數(shù)δ進(jìn)行實(shí)驗(yàn).所有數(shù)據(jù)流均在前、中、后3個(gè)階段分別插入概念漂移節(jié)點(diǎn).

每個(gè)數(shù)據(jù)單元對(duì)應(yīng)一個(gè)基窗口，ω太大會(huì)降低概念漂移節(jié)點(diǎn)檢測(cè)的敏感性，反之則容易將正常微小波動(dòng)誤檢為概念漂移，實(shí)驗(yàn)中ω分別取20，40，60，80，100進(jìn)行檢測(cè)，漂移探測(cè)參數(shù)τ分別取0.75，0.8，0.85，0.9，0.95，跨度探測(cè)參數(shù)δ分別采用 0.001，0.002，0.005，0.008，0.01.實(shí)驗(yàn)中展示了在不同ω下的最優(yōu)參數(shù)組合對(duì)應(yīng)的結(jié)果(ω=20，τ=0.8，δ=0.01；ω=40，τ=0.85，δ=0.01；ω=60，τ=0.85，δ=0.001；ω=80，τ=0.9，δ=0.001；ω=100，τ=0.9，δ=0.001).實(shí)驗(yàn)中伴隨窗口包含4個(gè)基窗口，即k=4.

2) 漸變類漂移模擬.本文實(shí)驗(yàn)中漸變類概念漂移中漂移跨度范圍內(nèi)的舊分布數(shù)據(jù)以10%的步長(zhǎng)遞減，新分布的數(shù)據(jù)以10%的步長(zhǎng)遞增.

3.3 評(píng)測(cè)指標(biāo)

為衡量所提出的CD-TW方法的性能，本文針對(duì)概念漂移節(jié)點(diǎn)、漂移跨度及漂移類別的檢測(cè)分別提出不同的評(píng)價(jià)指標(biāo).不同類別概念漂移節(jié)點(diǎn)檢測(cè)情況如圖5所示.圖5中，TL={tli}為真實(shí)插入的概念漂移節(jié)點(diǎn)集合，概念漂移tli的跨度內(nèi)節(jié)點(diǎn)構(gòu)成集合為T(mén)Li[O]，對(duì)于突變類概念漂移，該集合僅包含一個(gè)節(jié)點(diǎn)，即tli本身；對(duì)于漸變類概念漂移，若檢測(cè)到的漂移起始節(jié)點(diǎn)落在TLi[B]內(nèi)(包含真實(shí)插入節(jié)點(diǎn)及與其相鄰的后3個(gè)節(jié)點(diǎn)),則視為正確檢測(cè)且無(wú)延時(shí)；檢測(cè)到的漂移結(jié)束節(jié)點(diǎn)(起始節(jié)點(diǎn)經(jīng)過(guò)漂移跨度到達(dá)的節(jié)點(diǎn))落在TLi[E]內(nèi)(包含真實(shí)結(jié)束節(jié)點(diǎn)及與其相鄰的前3個(gè)節(jié)點(diǎn))視為正確檢測(cè).本文定義誤檢率、漏檢率和平均檢測(cè)延時(shí)來(lái)評(píng)價(jià)概念漂移位點(diǎn)檢測(cè)效果，定義缺失率與溢出率衡量漂移跨度的檢測(cè)準(zhǔn)確度，定義類別準(zhǔn)確率觀察CD-TW對(duì)類別的決策能力.

Fig. 5 Standard for determining concept drift position

1) 誤檢率(error detection rate,EDR).檢測(cè)到的漂移節(jié)點(diǎn)中存在的錯(cuò)誤漂移節(jié)點(diǎn)比例，可反映模型的抗干擾性能，定義為

(4)

其中S表示檢測(cè)到的漂移節(jié)點(diǎn)集合.

2) 漏檢率(miss detection rate,MDR).真實(shí)插入的漂移節(jié)點(diǎn)中沒(méi)被檢測(cè)到的比例，可反映模型的漂移檢測(cè)敏感性，定義為

(5)

3) 平均檢測(cè)延時(shí)(average detection delay,ADD).檢測(cè)到的漂移節(jié)點(diǎn)相對(duì)于真實(shí)漂移節(jié)點(diǎn)的延遲程度，用于衡量漸變類概念漂移節(jié)點(diǎn)檢測(cè)的時(shí)效性，定義為

(6)

4) 缺失率(loss rate,LR).檢測(cè)到的概念漂移跨度缺失部分占真實(shí)跨度的比例，定義為

(7)

其中:

5) 溢出率(flow rate,FR).檢測(cè)到的概念漂移跨度溢出部分占檢測(cè)跨度的比例，定義為

(8)

其中:

6) 類別準(zhǔn)確率(accuracy,Acc).概念漂移類別判斷正確的比例，定義為

(9)

其中，|Ts|為檢測(cè)到的突變類概念漂移被正確分類的數(shù)量，|Fs|代表檢測(cè)到的突變類概念漂移被錯(cuò)誤分類的數(shù)量，|Tg|表示檢測(cè)到的漸變類概念漂移被正確分類的數(shù)量，|Fg|代表檢測(cè)到的漸變類概念漂移被錯(cuò)誤分類的數(shù)量.

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

為有效衡量本文提出的CD-TW方法在概念漂移檢測(cè)及其類別檢測(cè)的不同階段所得結(jié)果的性能，實(shí)驗(yàn)中分別對(duì)概念漂移節(jié)點(diǎn)檢測(cè)的情況(包括誤檢率、漏檢率、平均檢測(cè)延時(shí))、概念漂移跨度檢測(cè)(包括缺失率、溢出率)及漂移類別檢測(cè)結(jié)果分別進(jìn)行測(cè)試分析.

3.4.1 概念漂移節(jié)點(diǎn)檢測(cè)

實(shí)驗(yàn)中采用EDR，MDR，ADD這3個(gè)指標(biāo)來(lái)評(píng)測(cè)不同方法在流數(shù)據(jù)中的概念漂移節(jié)點(diǎn)檢測(cè)性能.圖6和圖7分別為突變類概念漂移節(jié)點(diǎn)檢測(cè)得到的EDR和MDR值.從實(shí)驗(yàn)結(jié)果可以看出，除數(shù)據(jù)集USPS(w=40)外，本文提出的CD-TW方法在突變類概念漂移檢測(cè)的實(shí)驗(yàn)中得到的EDR和MDR值優(yōu)于其他概念漂移檢測(cè)方法，這說(shuō)明本文所提出的算法在檢測(cè)突變類概念漂移時(shí)的誤檢與漏檢均較低，表現(xiàn)出了良好的概念漂移節(jié)點(diǎn)檢測(cè)效果，同時(shí)反映出本文在小樣本學(xué)習(xí)中占有絕對(duì)性優(yōu)勢(shì)，而SWCDS和DWCDS方法無(wú)法有效區(qū)分小樣本學(xué)習(xí)與突變類概念漂移帶來(lái)的波動(dòng).

圖8和圖9分別為漸變類概念漂移節(jié)點(diǎn)檢測(cè)得到的EDR和MDR值.從實(shí)驗(yàn)結(jié)果可以看出，CD-TW方法對(duì)漸變類概念漂移的識(shí)別能力也明顯優(yōu)于其他方法，在標(biāo)準(zhǔn)數(shù)據(jù)集中所有不同基窗口容量下檢測(cè)到的結(jié)果均為最優(yōu)，即EDR與MDR的取值同時(shí)達(dá)到最小甚至接近0.在真實(shí)數(shù)據(jù)集上，CD-TW方法除在極少數(shù)特定基窗口容量下性能與其他方法相同或略遜色之外(如在數(shù)據(jù)集USPS上，當(dāng)ω=40時(shí)，本文提出的CD-TW方法要比SWCDS和DWCDS差)，整體檢測(cè)效果依然具有較為明顯的優(yōu)勢(shì)，這充分說(shuō)明本文方法可以更精準(zhǔn)地捕捉到數(shù)據(jù)分布的緩慢變化，具有較強(qiáng)的漸變類概念漂移檢測(cè)能力，在小樣本學(xué)習(xí)中具有明顯優(yōu)勢(shì).

Fig. 6 EDR of sudden concept drift

Fig. 7 MDR of sudden concept drift

Fig. 8 EDR of gradual concept drift

Fig. 9 MDR of gradual concept drift

Fig. 10 ADD of gradual concept drift

圖10為漸變類概念漂移節(jié)點(diǎn)檢測(cè)的平均檢測(cè)延時(shí)結(jié)果，所有正確檢測(cè)到的漸變類概念漂移節(jié)點(diǎn)延時(shí)均不超過(guò)5，因此用“∞”表示沒(méi)有檢測(cè)到概念漂移.從圖10中可以看出每個(gè)方法在檢測(cè)漸變類概念漂移節(jié)點(diǎn)時(shí)都存在不同程度的延時(shí)，這是由于在漂移開(kāi)始時(shí)刻大部分實(shí)例仍然服從舊分布，模型不能及時(shí)檢測(cè)到數(shù)據(jù)流所發(fā)生的微小分布變化.CD-TW方法在標(biāo)準(zhǔn)數(shù)據(jù)集上的概念漂移節(jié)點(diǎn)平均延時(shí)在0～2之間，在真實(shí)數(shù)據(jù)集KDDCup99上，CD-TW對(duì)應(yīng)的平均檢測(cè)延時(shí)較大，這是由于此數(shù)據(jù)集服從舊分布的數(shù)據(jù)對(duì)于構(gòu)建模型的影響可能更大，因此對(duì)新分布的檢測(cè)比較遲緩，而在真實(shí)數(shù)據(jù)集USPS上，當(dāng)ω=20時(shí)，沒(méi)有準(zhǔn)確檢測(cè)到漸變類概念漂移.而SWCDS方法沒(méi)有檢測(cè)到漸變類概念漂移的情況很多，且檢測(cè)到時(shí)所對(duì)應(yīng)的平均延時(shí)也較大，說(shuō)明該方法不適用于檢測(cè)漸變類概念漂移，且在小樣本學(xué)習(xí)背景下的檢測(cè)效果很差；DWCDS方法檢測(cè)到漸變類概念漂移節(jié)點(diǎn)的平均延時(shí)集中于0～3之間，在數(shù)據(jù)集USPS上則未檢測(cè)到，因此其檢測(cè)結(jié)果的實(shí)時(shí)性不好，且受數(shù)據(jù)流本身特性的影響較大；CDOL方法在大部分?jǐn)?shù)據(jù)集上節(jié)點(diǎn)的延時(shí)集中于0～2之間，但其在KDDCup99數(shù)據(jù)集上全部未檢測(cè)到.綜上實(shí)驗(yàn)結(jié)果可以看出，本文提出的CD-TW方法對(duì)于漸變類漂移的檢測(cè)更為有效準(zhǔn)確.

3.4.2 概念漂移跨度檢測(cè)

由于目前的漂移檢測(cè)方法大多針對(duì)突變類概念漂移，因此幾乎不涉及概念漂移跨度的檢測(cè)，本文認(rèn)為在漸變類概念漂移下，跨度蘊(yùn)含數(shù)據(jù)分布的重要信息，因此實(shí)驗(yàn)中僅采用文中定義的指標(biāo)對(duì)CD-TW方法進(jìn)行漂移跨度檢測(cè)分析，即采用缺失率(LR)和溢出率(FR)進(jìn)行評(píng)估，如表3和表4所示.

從表3和表4中可以看出，突變類概念漂移不存在漂移跨度的任何缺失，這是由于本文所提出的CD-TW方法對(duì)于突變類概念漂移，只有在真實(shí)的概念漂移插入節(jié)點(diǎn)處檢測(cè)到概念漂移才視為正確檢測(cè)，而突變類概念漂移的跨度為1，因此不可能存在缺失，故僅包含檢測(cè)到和檢測(cè)不到這2種情況，但在個(gè)別數(shù)據(jù)集上存在跨度溢出，即檢測(cè)到的概念漂移跨度大于1，這是由于小樣本學(xué)習(xí)產(chǎn)生的波動(dòng)被錯(cuò)誤地當(dāng)作數(shù)據(jù)分布的波動(dòng)，但這種情形僅在少量數(shù)據(jù)集上存在.從整體上看，本文所提出的CD-TW方法對(duì)突變類概念漂移的跨度檢測(cè)是較為準(zhǔn)確的.對(duì)于漸變類概念漂移，幾乎所有檢測(cè)結(jié)果中都存在不同程度的漂移跨度缺失，但跨度溢出的情況則相對(duì)較少，這是由于在整個(gè)漸變類概念漂移跨度范圍內(nèi)，接近漂移起始節(jié)點(diǎn)處服從原始分布的數(shù)據(jù)占絕大多數(shù)，而接近漂移結(jié)束節(jié)點(diǎn)處時(shí)的大部分?jǐn)?shù)據(jù)則服從新的分布，因此漸變類概念漂移的起始節(jié)點(diǎn)檢測(cè)容易發(fā)生延遲，而結(jié)束節(jié)點(diǎn)檢測(cè)則容易提前，即漸變類概念漂移跨度檢測(cè)比較困難.此外，在多數(shù)數(shù)據(jù)集上，隨著基窗口尺寸的增大，小樣本學(xué)習(xí)對(duì)模型精度產(chǎn)生的波動(dòng)強(qiáng)度逐漸減弱，故漸變類概念漂移跨度檢測(cè)準(zhǔn)確率呈現(xiàn)上升趨勢(shì)，但當(dāng)窗口增大到一定程度后，漂移跨度檢測(cè)準(zhǔn)確率幾乎不再受到這種波動(dòng)的干擾，因此準(zhǔn)確率保持在一個(gè)穩(wěn)定的水平.

Table 3 LR and FR in Span Detection of Sudden Concept Drift

Table 4 LR and FR in Span Detection of Gradual Concept Drift

3.4.3 概念漂移類別檢測(cè)

由于目前對(duì)概念漂移類別檢測(cè)的研究較少，這里對(duì)本文提出的CD-TW方法在概念漂移類別檢測(cè)結(jié)果的性能進(jìn)行評(píng)估，表5為概念漂移類別檢測(cè)結(jié)果.表5中Accs表示突變類概念漂移類別檢測(cè)的準(zhǔn)確率，Accg表示漸變類概念漂移類別檢測(cè)的準(zhǔn)確率.由于不同類別的概念漂移都是在流數(shù)據(jù)的前期、中期、后期節(jié)點(diǎn)處分別插入一個(gè)漂移節(jié)點(diǎn)進(jìn)行模擬，因此每種類別的概念漂移類別檢測(cè)的準(zhǔn)確率就只有0，0.333，0.667，1這4種取值.

由表5可以看出，本文提出的CD-TW方法在標(biāo)準(zhǔn)數(shù)據(jù)集上對(duì)于概念漂移類別檢測(cè)的準(zhǔn)確率較高，其中突變環(huán)境下類別檢測(cè)更為準(zhǔn)確，而漸變環(huán)境下的類別檢測(cè)準(zhǔn)確率略低于突變類.在真實(shí)數(shù)據(jù)集上，類別劃分精度平均精度約為62%，且對(duì)突變類概念漂移的類別檢測(cè)情況整體上也略優(yōu)于漸變類概念漂移.這是由于漸變類漂移跨度檢測(cè)是通過(guò)跟蹤數(shù)據(jù)分布的波動(dòng)來(lái)實(shí)現(xiàn)的，而本文充分考慮小樣本學(xué)習(xí)帶來(lái)的波動(dòng)并極力減小這種影響，故存在削弱數(shù)據(jù)概念波動(dòng)的情形，因此會(huì)降低漸變類判斷的準(zhǔn)確度，從實(shí)驗(yàn)結(jié)果整體來(lái)看，本文提出的CD -TW方法可以在準(zhǔn)確定位概念漂移節(jié)點(diǎn)的基礎(chǔ)上，通過(guò)檢測(cè)概念漂移的跨度，得到概念漂移的類別.

Table 5 Results of Concept Drift Class Judgment

續(xù)表5

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

由于流數(shù)據(jù)中可能存在類別不同的概念漂移且不同類別概念漂移可能蘊(yùn)含情況不等的重要信息，本文提出了一種基于時(shí)序窗口機(jī)制的概念漂移類別檢測(cè)方法.首先通過(guò)將流數(shù)據(jù)劃分時(shí)序單元，利用靜態(tài)的參考基礎(chǔ)節(jié)點(diǎn)時(shí)序窗口和滑動(dòng)的基礎(chǔ)節(jié)點(diǎn)時(shí)序窗口加載最新數(shù)據(jù)進(jìn)行探測(cè)，實(shí)時(shí)檢測(cè)概念漂移節(jié)點(diǎn)；然后利用跨度時(shí)序窗口加載概念漂移節(jié)點(diǎn)之后的數(shù)據(jù)，分析其分布情況的穩(wěn)定性以得到概念漂移跨度；最后利用漂移跨度來(lái)檢測(cè)概念漂移類別.本文所提方法可以較準(zhǔn)確地檢測(cè)流數(shù)據(jù)中的概念漂移節(jié)點(diǎn)，同時(shí)對(duì)不同類別概念漂移具有較強(qiáng)的識(shí)別能力，可為流數(shù)據(jù)的精準(zhǔn)分析挖掘提供有意義的指導(dǎo).

作者貢獻(xiàn)聲明：郭虎升負(fù)責(zé)思想提出、方法設(shè)計(jì)、代碼實(shí)現(xiàn)、初稿寫(xiě)作及論文修改;任巧燕負(fù)責(zé)代碼實(shí)現(xiàn)、數(shù)據(jù)測(cè)試及初稿寫(xiě)作;王文劍負(fù)責(zé)思想設(shè)計(jì)、寫(xiě)作指導(dǎo)、修改審定及基金資助.