梁 斌，李光輝+

1.江南大學(xué) 人工智能與計(jì)算機(jī)學(xué)院，江蘇 無錫 214122

2.物聯(lián)網(wǎng)技術(shù)應(yīng)用教育部工程研究中心，江蘇 無錫 214122

隨著物聯(lián)網(wǎng)技術(shù)的快速發(fā)展，社會各個(gè)領(lǐng)域產(chǎn)生了大量數(shù)據(jù)流，如傳感器數(shù)據(jù)流、電子商務(wù)數(shù)據(jù)流等。隨著時(shí)間的推移，數(shù)據(jù)流的目標(biāo)概念或潛在分布會發(fā)生變化，這種現(xiàn)象被稱為概念漂移[1-2]。例如顧客網(wǎng)上購物的喜好分析會隨著時(shí)間、商品的變化而改變；工廠的用電量隨著季節(jié)交替出現(xiàn)周期性變化[3]。概念漂移會導(dǎo)致已有的分類模型性能顯著下降，因此數(shù)據(jù)流挖掘算法要求快速準(zhǔn)確地檢測出漂移并及時(shí)調(diào)整原分類模型，快速適應(yīng)當(dāng)前新概念，提高數(shù)據(jù)流的分類準(zhǔn)確率。目前處理概念漂移的算法大致可分為兩類[4-5]：主動檢測和被動適應(yīng)。

主動檢測算法具有顯式的漂移檢測機(jī)制，通常與在線分類器組合使用。檢測到漂移時(shí)，當(dāng)前分類器被丟棄同時(shí)，訓(xùn)練一個(gè)新的分類器。如Gama 等提出的DDM（drift detection method）[6]是第一個(gè)主動檢測型算法，它假設(shè)數(shù)據(jù)流服從正態(tài)分布，通過監(jiān)測分類模型的錯(cuò)誤率變化檢測概念漂移，但該方法只適合檢測突變型漂移，不適合漸變型漂移。Barros 等提出的RDDM（reactive drift detection method）[7]通過周期性地重置DDM 的漂移檢測統(tǒng)計(jì)量解決DDM 在長期穩(wěn)定數(shù)據(jù)流下的漂移檢測敏感性下降的問題。Pears等提出的SeqDrift（sequential hypothesis testing drift detector）[8]維護(hù)兩個(gè)相鄰的滑動窗口，通過比較兩個(gè)窗口中的錯(cuò)誤率差異是否超過某閾值檢測漂移，該閾值由Bernstein界確定。Frias-Blanco等提出的HDDM（drift detection methods based on Hoeffding bounds）[9]利用Hoeffding 界檢驗(yàn)當(dāng)前模型的錯(cuò)誤率是否發(fā)生顯著性變化檢測漂移。Barros 等提出的FPDD（concept drift detection based on Fisher's exact test）[10]使 用Fisher's exact test 檢驗(yàn)兩個(gè)相鄰窗口中的錯(cuò)誤率是否存在統(tǒng)計(jì)學(xué)上顯著性差異，若存在則表明出現(xiàn)概念漂移。針對重復(fù)概念問題，Gon?alves 等提出的RCD（recurring concept drifts）[11]在DDM 的基礎(chǔ)上，結(jié)合多元非參數(shù)統(tǒng)計(jì)方法識別當(dāng)前的新概念是否為過去概念的重現(xiàn)。類似的，白洋等提出的DRDM（drift recurrence detection method）[12]在SeqDrift 的基礎(chǔ)上，使用有向圖保存歷史概念并使用Hotelling's T2檢驗(yàn)判斷新舊概念是否來自同一分布。

被動適應(yīng)型算法大都為集成算法，沒有專門的漂移檢測機(jī)制，通過調(diào)整集成模型的結(jié)構(gòu)和成員分類器的權(quán)重被動適應(yīng)概念漂移。如Brzezinski 等提出的AUE 算法（accuracy updated ensemble）[13]，每到達(dá)一個(gè)數(shù)據(jù)塊訓(xùn)練一個(gè)新的分類器添加至集成中，每個(gè)分類器的權(quán)重由它們的分類準(zhǔn)確率決定。進(jìn)一步，Brzezinski 等提出OAUE 算法（online accuracy updated ensemble）[14]，該算法在AUE 的加權(quán)公式中引入了時(shí)間概念，同時(shí)結(jié)合在線分類器，更好地處理各種類型概念漂移。Elwell 等提出的LearnNSE[15]使用復(fù)雜的加權(quán)策略，每個(gè)基分類器的權(quán)重需要綜合考慮當(dāng)前和過去所有數(shù)據(jù)塊上的錯(cuò)誤率。

目前處理概念漂移的數(shù)據(jù)流分類算法主要存在兩個(gè)問題：一是漂移檢測延遲和誤報(bào)率較高，且難以同時(shí)處理不同類型漂移；二是缺乏識別重復(fù)概念的能力，當(dāng)歷史概念重現(xiàn)時(shí)，當(dāng)前分類模型無法利用過去所學(xué)知識快速適應(yīng)新概念。為此，本文基于雙層模糊窗口和McDiarmid 界，結(jié)合半?yún)?shù)對數(shù)似然比方法，提出了一種新的可以適應(yīng)多類型概念漂移的數(shù)據(jù)流分類算法（data stream classification algorithm based on double-layer fuzzy sliding window and McDiarmid bound，DFWM）。該算法維護(hù)一個(gè)固定大小的雙層滑動窗口，保存當(dāng)前模型最新的分類結(jié)果，根據(jù)隸屬度函數(shù)對窗口中每個(gè)數(shù)據(jù)分配對應(yīng)權(quán)重并計(jì)算加權(quán)錯(cuò)誤率，然后利用McDiarmid 界檢驗(yàn)當(dāng)前窗口中的錯(cuò)誤率是否發(fā)生顯著性變化來檢測概念漂移。同時(shí)DFWM 維護(hù)一個(gè)分類器池保存已出現(xiàn)過的概念及其對應(yīng)的分類器，檢測到漂移時(shí)，使用半?yún)?shù)對數(shù)似然方法判斷當(dāng)前概念是否為某個(gè)舊概念的重現(xiàn)，若是則直接復(fù)用舊概念對應(yīng)的分類器，否則重新構(gòu)建一個(gè)新的分類器。實(shí)驗(yàn)結(jié)果表明，與同類算法相比，所提算法在漂移檢測延遲、誤報(bào)率、分類精度和運(yùn)行時(shí)間上均有一定優(yōu)勢。

1 相關(guān)知識

1.1 概念漂移定義和分類

根據(jù)文獻(xiàn)[2,16-17]，概念漂移的定義如下：

定義1概念漂移設(shè)[0，t]表示一段時(shí)間,數(shù)據(jù)流可表示為St={d0,d1,…,dt}，其中di=(Xi,yi)表示一個(gè)實(shí)例，Xi為特征向量，yi為標(biāo)簽，i=1,2,…,t。假設(shè)St服從某分布Ft(X,y)，P(y|X)表示y關(guān)于X的條件概率分布，若在t+1 時(shí)刻有Ft(X,y)≠Ft+1(X,y)且Pt(y|X)≠Pt+1(y|X)，表明原有的決策邊界發(fā)生變化，這種現(xiàn)象稱為概念漂移。

概念漂移的分類普遍是基于概念變化的速度[1-2,7]。當(dāng)新舊概念過渡很快，舊的概念突然被另一個(gè)數(shù)據(jù)分布完全不同的新概念取代，這種漂移屬于突變型概念漂移（abrupt concept drift），如圖1（a）所示，其中實(shí)心圓代表一段數(shù)據(jù)，圓內(nèi)的數(shù)字代表到達(dá)的時(shí)間；反之，新舊概念過渡較慢時(shí)，舊概念被新概念逐漸替換，且二者在漂移前后或多或少有些相似，如圖1（b）所示，這種漂移則屬于漸變型概念漂移（gradual concept drift）。

Fig.1 Abrupt and gradual concept drift圖1 突變型和漸變型概念漂移

重復(fù)概念漂移指過去的某個(gè)概念再次出現(xiàn)，既可以有規(guī)律地出現(xiàn)，也可以無規(guī)律地出現(xiàn)[11]，通常與突變型漂移或漸變型漂移聯(lián)合出現(xiàn)，如圖2（a）中的數(shù)據(jù)段7 和8 即是重復(fù)概念，圖2（b）中的數(shù)據(jù)段9 也是重復(fù)概念。

Fig.2 Recurring concept drift圖2 重復(fù)概念漂移

1.2 模糊集理論和隸屬度函數(shù)

若論域U中的任一元素x，都有一個(gè)值A(chǔ)(x)∈[0,1]與之對應(yīng)，則稱A為U上的模糊集，A(x)稱為元素x對A的隸屬度。當(dāng)x在U中變化時(shí)，A(x)則是關(guān)于x的函數(shù)，稱為A的隸屬度函數(shù)。在模糊集理論中，使用取值在區(qū)間[0,1]的隸屬度函數(shù)A(x)表征x屬于A的程度。A(x)的值越接近于1，表示x屬于A的程度越高；A(x)越接近于0，則表示x屬于A的程度越低。常見的隸屬度函數(shù)有梯形型、對數(shù)型和柯西型等[18]，本文主要使用了對數(shù)型隸屬度函數(shù)A(x)，如式（1）所示。

其中，a、b代表區(qū)間[a,b]的左右端點(diǎn)，xi為區(qū)間中的第i個(gè)元素，e為自然常數(shù)，λ為自定義常數(shù)，用于控制隸屬度函數(shù)的形狀。

1.3 半?yún)?shù)對數(shù)似然算法

文獻(xiàn)[19]提出了半?yún)?shù)對數(shù)似然算法（semiparametric log-likelihood，SPLL），它從似然的角度檢驗(yàn)兩組多元樣本W(wǎng)1和W2是否來自同一概率分布。相較于傳統(tǒng)的K-L 散度檢驗(yàn)和Hotelling's T2檢驗(yàn)，SPLL 的計(jì)算更為簡單，檢驗(yàn)效果更好。它假設(shè)樣本W(wǎng)1服從分布p1，W2服從p2，則W2中數(shù)據(jù)的對數(shù)似然比LLR如式（2）所示：

式中，L(?)代表似然函數(shù)。由于W2服從p2，故L(W2|p2)=1。式（2）可改寫為式（3），這意味著LLR代表W2中的數(shù)據(jù)擬合分布p1的程度。

LLR的縮放上界LL，如式（4）所示，其中x為樣本W(wǎng)1中的一個(gè)實(shí)例，n代表x的維度，u為距x馬氏距離最近的簇中心，簇中心由K-means 聚類得到，Σ為W1中數(shù)據(jù)的協(xié)方差矩陣。

使用LL，可得SPLL的檢驗(yàn)統(tǒng)計(jì)量δ如式（5）所示：

若δ服從自由度為n的卡方分布，表明W2中的數(shù)據(jù)服從分布p1，即W1和W2中的數(shù)據(jù)來自相同的分布。

2 基于McDiarmid 界的概念漂移數(shù)據(jù)流分類算法（DFWM）

DFWM 由兩部分組成：概念漂移檢測模塊和重復(fù)概念識別模塊。本章先介紹基于雙層模糊窗口和McDiarmid 界的概念漂移檢測機(jī)制，并給出了漂移檢測閾值的計(jì)算方法，然后介紹如何識別重復(fù)概念，最后描述DFWM 的算法流程。

2.1 概念漂移檢測機(jī)制

根據(jù)PAC（probably approximately correct）理論，隨著數(shù)據(jù)流規(guī)模的增加，分類模型的錯(cuò)誤率應(yīng)該逐漸下降或保持不變。否則，數(shù)據(jù)流中有很大可能出現(xiàn)概念漂移[6]?；诖耍拍钇茩z測問題可轉(zhuǎn)化為檢測分類模型的錯(cuò)誤率是否發(fā)生顯著性變化。數(shù)據(jù)流的長度是無限的，無法獲取所有數(shù)據(jù)，因此通常使用固定長度的滑動窗口來獲取當(dāng)前最新數(shù)據(jù)，根據(jù)滑動窗口內(nèi)的錯(cuò)誤率的變化情況檢測概念漂移也是漂移檢測領(lǐng)域的常用方法[8,18,20-21]。然而，滑動窗口大小的選擇對概念漂移檢測的效果至關(guān)重要。大量實(shí)驗(yàn)發(fā)現(xiàn)（如3.4 節(jié)的實(shí)驗(yàn)結(jié)果），面對突變型漂移，使用短窗口具有更低的檢測延遲。而面對漸變型漂移，使用長窗口的檢測延遲更低，漏報(bào)率也顯著低于使用短窗口，因此僅使用一個(gè)單層滑動窗口難以同時(shí)適應(yīng)突變型和漸變型漂移。為此，本文在靠近長窗口頭部的位置分割窗口，形成長短嵌套的雙層滑動窗口。每次檢測先使用短窗口，若未檢測到漂移，再使用長窗口檢測，可以兼顧不同類型的漂移。雙層窗口結(jié)構(gòu)如圖3 所示，短窗口位于長窗口的頭部（圖3 中雙層窗口的右側(cè)為窗口頭部，左側(cè)為窗口尾部），負(fù)責(zé)檢測突變型漂移，而長窗口用于檢測漸變型漂移。

Fig.3 Structure of double-layer window圖3 雙層窗口結(jié)構(gòu)

窗口中每個(gè)數(shù)據(jù)的到達(dá)的時(shí)間不同，當(dāng)前的數(shù)據(jù)必然比過去的數(shù)據(jù)更能代表當(dāng)前概念，因此在計(jì)算窗口內(nèi)錯(cuò)誤率時(shí)，應(yīng)該對靠近窗口頭部的數(shù)據(jù)分配更大的權(quán)重，以便更快速地檢測概念漂移。隸屬度函數(shù)可以很好地反映集合中每個(gè)元素對集合的隸屬程度，當(dāng)出現(xiàn)概念漂移時(shí)，窗口頭部的數(shù)據(jù)對新概念的隸屬程度必然大于窗口尾部的數(shù)據(jù)，因此使用1.2 節(jié)中介紹的對數(shù)型隸屬度函數(shù)對窗口中的每個(gè)數(shù)據(jù)分配權(quán)重，權(quán)重計(jì)算方法如式（6）所示：

其中，w(i)表示雙層窗口中第i個(gè)數(shù)據(jù)（窗口尾端的數(shù)據(jù)為第1 個(gè)數(shù)據(jù)）的權(quán)重，表示長窗口的大小，e為自然常數(shù)，λ為預(yù)設(shè)值，決定隸屬度函數(shù)的形狀。式（6）為分段函數(shù)，靠近窗口頭部，即短窗口中的數(shù)據(jù)最能代表當(dāng)前概念，因此權(quán)重均設(shè)為最大值1，之后數(shù)據(jù)的權(quán)重根據(jù)對數(shù)函數(shù)逐漸衰減，當(dāng)1

Fig.4 Weight distribution of each data in window圖4 窗口中每個(gè)數(shù)據(jù)權(quán)重的分布

DFWM 的漂移檢測過程如下：每到達(dá)一個(gè)實(shí)例，先使用當(dāng)前模型獲取分類結(jié)果并添加至雙層窗口中，分類錯(cuò)誤記為1，正確記為0。然后根據(jù)式（8）計(jì)算短窗口內(nèi)數(shù)據(jù)的加權(quán)錯(cuò)誤率，其中di是窗口中第i個(gè)元素，wi是其對應(yīng)的權(quán)重，如果psw

若當(dāng)前短窗口內(nèi)錯(cuò)誤率psw與其歷史最小值psw′滿足式（9），表明當(dāng)前短窗口內(nèi)錯(cuò)誤率psw較過去出現(xiàn)了顯著性變化，即數(shù)據(jù)流中出現(xiàn)了概念漂移。式（9）中閾值的θ1由McDiarmid 界決定（2.2 節(jié)詳細(xì)介紹閾值的計(jì)算）。

若使用短窗口未檢測到概念漂移，繼續(xù)計(jì)算長窗口內(nèi)數(shù)據(jù)的加權(quán)錯(cuò)誤率plw，計(jì)算方法與計(jì)算psw相同。如果plw

若式（9）、式（10）均不滿足，表明當(dāng)前數(shù)據(jù)流處于穩(wěn)定狀態(tài)，無概念漂移。

2.2 漂移檢測閾值計(jì)算

DFWM 中的漂移檢測閾值的計(jì)算依賴于McDiarmid 界[22-23]，該統(tǒng)計(jì)邊界不需要對數(shù)據(jù)流的分布做任何假設(shè)，給出了樣本的函數(shù)f與其期望值E[f]之差的上界，如定理1 所示。

定理1McDiarmid 界設(shè)X1,X2,…,Xn為n個(gè)獨(dú)立有界隨機(jī)變量，其中Xi∈A∈[a,b]。設(shè)f:An→R 為X1,X2,…,Xn上的一個(gè)函數(shù)，且滿足?i，?x1,x2,…,xi,…,xn，xi′∈A,|f(x1,x2,…,xi,…,xn)-f(x1,x2,…,xi′,…,xn)|≤ci，即使用集合A中的任意值xi′替換函數(shù)f中的第i個(gè)元素xi最多改變函數(shù)f的值為ci。對于任意θ>0，則有：

式（11）表明f與其期望值E[f]之差大于θ的概率受到關(guān)于θ的指數(shù)邊界控制，在給定顯著性水平α下，令式（11）中不等號的右側(cè)等于α，θ值可由式（12）獲得：

在DFWM 中，雙層窗口中保存的分類結(jié)果di均為二值變量，即di∈{0,1}，分類錯(cuò)誤記為1，正確記為0。因此式（8）中的加權(quán)錯(cuò)誤率就是窗口中數(shù)據(jù)的加權(quán)平均值。以短窗口檢測漂移為例，介紹2.1 節(jié)中的閾值θ1的計(jì)算過程（長窗口中的閾值θ2同理）。首先將式（8）改寫為式（13）：

其中，vi如式（14）所示，wi為短窗口中第i個(gè)數(shù)據(jù)di對應(yīng)的權(quán)重，|SW|為短窗口大小。

式中，psw是關(guān)于di的函數(shù)，記作psw(d1,d2,…,di,…,d|sw|)，且滿足?i，?d1,d2,…,di,…,d|sw|，di′∈{0,1},|psw(d1,d2,…,di,…,d|sw|)-psw(d1,d2,…,di′,…,d|sw|)|≤ci，其中ci=(1-0)vi，即ci=vi。當(dāng)數(shù)據(jù)流處在穩(wěn)定狀態(tài)，無概念漂移時(shí)，短窗口內(nèi)錯(cuò)誤率psw會逐漸下降最終穩(wěn)定在其最小值psw′附近，因此psw′可以代表psw的期望值。將psw和psw′代入式（11）可得式（15）：

在給定的顯著性水平α下，根據(jù)式（12）可得短窗口漂移檢測閾值θ1，如式（16）所示：

2.3 重復(fù)概念的識別

DFWM 檢測到概念漂移時(shí)，表明數(shù)據(jù)流中出現(xiàn)了新概念，當(dāng)前分類器不再適用。通常的做法是丟棄當(dāng)前分類器，重新訓(xùn)練一個(gè)新的分類器去適應(yīng)新概念。然而，如果當(dāng)前的新概念是某個(gè)歷史概念的重現(xiàn)，即數(shù)據(jù)流中出現(xiàn)了重復(fù)概念，重新訓(xùn)練一個(gè)分類器的代價(jià)比復(fù)用舊分類器大得多。復(fù)用舊分類器可以充分利用過去已學(xué)習(xí)到的知識，更快地適應(yīng)新概念。基于此，DFWM 使用分類器池和1.3 節(jié)中介紹的SPLL 處理重復(fù)概念。具體來說，使用C={C1,C2,…,Ci,…,Cm}表示由m個(gè)分類器組成的分類器池，其中每個(gè)分類器Ci附帶它的使用頻率k和一個(gè)數(shù)據(jù)塊Bi，Bi用于保存分類器Ci的錯(cuò)誤率達(dá)到最小值時(shí)對應(yīng)的若干數(shù)據(jù)，因?yàn)榇藭r(shí)數(shù)據(jù)流最穩(wěn)定，這些數(shù)據(jù)最能代表當(dāng)前概念，Bi的大小和長窗口|LW|大小相同。檢測到漂移時(shí)，若分類器池非空，根據(jù)池中每個(gè)分類器頻率的高低，使用SPLL 依次對每個(gè)分類器對應(yīng)的數(shù)據(jù)塊和當(dāng)前窗口中的數(shù)據(jù)檢驗(yàn)，若二者來自相同分布，表明出現(xiàn)了重復(fù)概念，直接復(fù)用該分類器，并將它的使用頻率加1。否則，表明數(shù)據(jù)流中出現(xiàn)了全新的概念，將當(dāng)前的分類器和它對應(yīng)的數(shù)據(jù)塊添加至分類器池中，使用頻率置為1，然后使用當(dāng)前數(shù)據(jù)重新訓(xùn)練一個(gè)新分類器。出于占用內(nèi)存的考慮，不可能把所有出現(xiàn)過的概念及其對應(yīng)分類器都保存到分類器池中。頻率最低的分類器表明它對應(yīng)的概念最少出現(xiàn)，因此分類器池容量達(dá)到上限時(shí)移除該分類器。DFWM 是基于單分類器的分類算法，只使用當(dāng)前分類器進(jìn)行預(yù)測，分類器池只保存若干訓(xùn)練過的舊分類器。如果被刪除的最低頻率分類器對應(yīng)的概念再次出現(xiàn)，DFWM 會立即使用當(dāng)前數(shù)據(jù)重新訓(xùn)練一個(gè)分類器，這只會增加一定的時(shí)空開銷，不會影響信息的完整性。識別重復(fù)概念進(jìn)而復(fù)用過去已訓(xùn)練好的舊分類器，可以充分利用過去所學(xué)知識，快速適應(yīng)當(dāng)前概念，有效提高DFWM 的分類速度和準(zhǔn)確率。同時(shí)避免了重復(fù)概念導(dǎo)致重復(fù)訓(xùn)練的問題，降低時(shí)間和空間的開銷。

DFWM 的執(zhí)行流程圖如圖5 所示。

Fig.5 Flow diagram of DFWM圖5 DFWM 的流程圖

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

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

為驗(yàn)證DFWM 的性能，本文在6 個(gè)人工數(shù)據(jù)集和2 個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行了兩方面的實(shí)驗(yàn)：（1）與DDM[6]、SeqDrift[8]、HDDM[9]、RDDM[7]和FPDD[10]五種算法進(jìn)行對比實(shí)驗(yàn)，從漂移檢測延遲、誤報(bào)率和漏報(bào)率三方面驗(yàn)證DFWM的漂移檢測性能；（2）與RCD[11]、LearnNSE[15]和OAUE[14]三種算法進(jìn)行對比實(shí)驗(yàn)，從分類準(zhǔn)確率和運(yùn)行時(shí)間兩方面驗(yàn)證DFWM 的分類性能。本文的實(shí)驗(yàn)環(huán)境為一臺處理器為Intel Core i7-7700HQ，內(nèi)存為16 GB 的筆記本電腦，運(yùn)行Windows 10 系統(tǒng)和python3.7。在該環(huán)境下，分別實(shí)現(xiàn)了本文算法和各種對比算法。DFWM 的參數(shù)均根據(jù)大量實(shí)驗(yàn)結(jié)果設(shè)置：長窗口大小|LW|設(shè)為100，隸屬度函數(shù)參數(shù)λ設(shè)為0.75，顯著性水平α為10-7，分類器池的最大容量m為10，池中分類器對應(yīng)的數(shù)據(jù)塊B的大小為100。對比算法保持與原論文完全相同的參數(shù)設(shè)置。所有實(shí)驗(yàn)采用test-then-train 策略，即每個(gè)實(shí)例先用作測試數(shù)據(jù)，然后作為訓(xùn)練數(shù)據(jù)，這種策略不用劃分?jǐn)?shù)據(jù)集，可以充分利用每個(gè)數(shù)據(jù)的信息。

3.2 數(shù)據(jù)集介紹

人工數(shù)據(jù)集在概念漂移檢測領(lǐng)域十分重要，因?yàn)榭梢匀藶槎x概念漂移的數(shù)量、位置和持續(xù)時(shí)間，以模擬不同的場景。本文用到的6個(gè)人工數(shù)據(jù)集均為概念漂移領(lǐng)域的Benchmarks，可通過python 的skmultiflow[24]包生成，詳情如下所示：

SINE：該數(shù)據(jù)集包含突變重復(fù)型漂移，它有兩個(gè)屬性x和y。分類函數(shù)是y=sin(x)，在第一次漂移之前，函數(shù)曲線下方的實(shí)例被標(biāo)記正，曲線上方的被標(biāo)記為負(fù)，共有兩個(gè)類別。在漂移點(diǎn)，通過突然反轉(zhuǎn)分類規(guī)則來產(chǎn)生漂移。數(shù)據(jù)集共包含100 000 個(gè)實(shí)例，每隔20 000 個(gè)實(shí)例產(chǎn)生一次漂移，共有5 個(gè)概念，其中第1、3、5 個(gè)概念互為重復(fù)概念，第2、4 個(gè)概念互為重復(fù)概念，含10%噪聲。

STAGGER：該數(shù)據(jù)集包含突變型漂移，它有3 個(gè)離散屬性和2 個(gè)類別，每隔33 333 個(gè)實(shí)例通過突然反轉(zhuǎn)分類規(guī)則產(chǎn)生漂移，共100 000個(gè)實(shí)例，含10%噪聲。

SEA：該數(shù)據(jù)集包含漸變重復(fù)型漂移，有3 個(gè)連續(xù)屬性，其中第3 個(gè)屬性與類別無關(guān)，如果x1+x2<θ，實(shí)例分類為正，否則為負(fù)，x1、x2表示前兩個(gè)屬性。每隔20 000 個(gè)實(shí)例，通過逐漸改變閾值θ來產(chǎn)生漸變型漂移，共包含100 000 個(gè)實(shí)例，含10%噪聲。閾值θ∈{5,15,5,15,5}，其中第1、3、5 個(gè)概念互為重復(fù)概念，第2、4 個(gè)概念互為重復(fù)概念。

LED：該數(shù)據(jù)集包含漸變型漂移，有24 個(gè)屬性，共10 個(gè)類別。通過逐漸改變相關(guān)屬性值來產(chǎn)生漸變型概念漂移，共包含100 000 個(gè)實(shí)例，每隔25 000 個(gè)實(shí)例產(chǎn)生一次漸變型漂移，含10%噪聲。

MIXED：該數(shù)據(jù)集包含突變型漂移，它有兩個(gè)連續(xù)屬性x和y以及兩個(gè)布爾屬性v和w。如果滿足條件v,w,y<0.5+0.3×sin(2πx)，實(shí)例被分類為正，否則為負(fù)，共有兩個(gè)類別。在漂移點(diǎn)，通過突然反轉(zhuǎn)分類規(guī)則產(chǎn)生漂移。數(shù)據(jù)集共包含100 000 個(gè)實(shí)例，每隔20 000 個(gè)實(shí)例產(chǎn)生一次漂移，共有5 個(gè)概念，其中第1、3、5 個(gè)概念互為重復(fù)概念，第2、4 個(gè)概念互為重復(fù)概念，含10%噪聲。

CIRCLE：該數(shù)據(jù)集包含漸變型漂移，它有兩個(gè)連續(xù)屬性x和y。4 個(gè)圓方程表示4 個(gè)不同概念，圓內(nèi)的實(shí)例被分類為正，圓外為負(fù)，共2 個(gè)類別。在漂移點(diǎn)通過逐漸改變圓的方程來產(chǎn)生漂移。數(shù)據(jù)集共包含100 000 個(gè)實(shí)例，每隔25 000 個(gè)實(shí)例產(chǎn)生一次漸變型漂移，含10%噪聲。

人工數(shù)據(jù)集中的數(shù)據(jù)均為隨機(jī)產(chǎn)生，因此使用skmultiflow 包在每類人工數(shù)據(jù)集上生成10 個(gè)不同的子集，做10 次實(shí)驗(yàn)，取平均值作為最終結(jié)果。

2個(gè)真實(shí)數(shù)據(jù)集均為概念漂移領(lǐng)域的Benchmarks，詳情如下所示：

Spam：該數(shù)據(jù)集包括9 324 個(gè)實(shí)例和500 個(gè)屬性，每個(gè)實(shí)例表示一個(gè)郵件的信息，有兩個(gè)類別垃圾郵件和合法郵件，其中垃圾郵件的特征會隨著時(shí)間變化?？稍趆ttp://mlkd.csd.auth.gr/concept_drfit.html下載。

Electricity：該數(shù)據(jù)集收集了1996 年 至1998 年澳大利亞新南威爾士州電力市場的45 312 個(gè)實(shí)例，包含8 個(gè)屬性和2 個(gè)類別。該數(shù)據(jù)集可在http://sourceforge.net/projects/moa-datastream/files/Datasets/Classification/下載。

所有數(shù)據(jù)集的信息總結(jié)如表1 所示。

3.3 算法性能評價(jià)指標(biāo)

根據(jù)文獻(xiàn)[2]，概念漂移數(shù)據(jù)流分類算法通用的評價(jià)指標(biāo)有平均檢測延遲（average delay of detection，ADOD）、誤報(bào)率（false positive rate，F(xiàn)PR）、漏報(bào)率（false negative rate，F(xiàn)NR）、運(yùn)行時(shí)間和分類準(zhǔn)確率。特別地，平均檢測延遲、誤報(bào)率、漏報(bào)率定義如下：

（1）平均檢測延遲（ADOD）：假設(shè)第i個(gè)漂移發(fā)生的時(shí)刻為Ti，漂移被檢測到的時(shí)刻為Ti′，則檢測延遲為(Ti′-Ti)。平均檢測延遲，其中dist=為所有檢測延遲之和，n為檢測到的漂移個(gè)數(shù)。

根據(jù)文獻(xiàn)[7]，通過定義可容忍的最大檢測延遲Δd來定義誤報(bào)率和漏報(bào)率，Δd通常為概念長度的2%。例如在SINE數(shù)據(jù)集中，概念長度為20 000，則Δd為400。設(shè)漂移發(fā)生的時(shí)刻為T，則在區(qū)間[T,T+Δd]內(nèi)檢測到的漂移個(gè)數(shù)視為正確檢測個(gè)數(shù)（TP）?；诖?，誤報(bào)率和漏報(bào)率的定義如下所示：

（2）誤報(bào)率（FPR）：在區(qū)間[T,T+Δd]外檢測到漂移的個(gè)數(shù)視為誤報(bào)個(gè)數(shù)（FP）。

（3）漏報(bào)率（FNR）：在區(qū)間[T,T+Δd]內(nèi)漏檢的漂移個(gè)數(shù)視為漏報(bào)個(gè)數(shù)（FN）。

Table 1 Datasets of experiments表1 實(shí)驗(yàn)數(shù)據(jù)集

3.4 雙層窗口的有效性

本節(jié)通過與DFWM_S、DFWM_L 的對比實(shí)驗(yàn)來驗(yàn)證DFWM 中雙層窗口的有效性，其中DFWM_S 只使用大小為25 的短窗口，DFWM_L 只使用大小為100 的長窗口，其他設(shè)置相同。每個(gè)表中的檢測指標(biāo)的最優(yōu)值加粗表示，排名1 表示在某個(gè)數(shù)據(jù)集上的效果最好。由表2 知，DFWM_S 在STAGGER、MIXED和SINE 3 個(gè)突變型漂移數(shù)據(jù)集上平均檢測延遲較低，與DFWM 相似；而在其他3 個(gè)漸變型漂移數(shù)據(jù)集上平均檢測延遲顯著高于DFWM。DFWM_L 與它正相反。誤報(bào)率方面，由表3 知，DFWM_S 沒有出現(xiàn)誤報(bào)，而DFWM、DFWM_L 在SEA 上出現(xiàn)了少量誤報(bào)。漏報(bào)率方面，由表4 知，DFWM_S 在LED、SEA和CIRCLE 3 個(gè)漸變型漂移數(shù)據(jù)集上的漏報(bào)率遠(yuǎn)高于其他兩種算法。綜合來看，使用短窗口的DFWM_S適合檢測突變型漂移，而使用長窗口的DFWM_L 更適合檢測漸變型漂移，DFWM 使用雙層窗口結(jié)合了二者的優(yōu)點(diǎn)，在突變型和漸變型漂移數(shù)據(jù)集上均獲得了較好的檢測效果。

3.5 概念漂移檢測

表5～表7給出了6種算法（DFWM、DDM、SeqDrift、HDDM、RDDM 和FPDD）在6 個(gè)人工數(shù)據(jù)集上的平均檢測延遲、誤報(bào)率和漏報(bào)率的實(shí)驗(yàn)結(jié)果。由表5知，在平均檢測延遲方面，DFWM 在MIXED、SEA、LED 和CIRCLE 這4 個(gè)數(shù)據(jù)集上最低，排名第1，較第2 名分別降低了0.12、66.9、54.3、123.5。在SINE 和STAGGER 數(shù)據(jù)集中位列第2，檢測延遲略高于FPDD，在所有數(shù)據(jù)集上平均排名第1。誤報(bào)率方面，如表6 所示，DFWM 僅在SEA 上出現(xiàn)了誤報(bào)，誤報(bào)率較第1 名高出了1.04%，在所有數(shù)據(jù)集上平均排名第1。由表7 知，DFWM 僅在SEA 數(shù)據(jù)集上存在漏報(bào)，漏報(bào)率較第1 名高出了3.33%，在所有數(shù)據(jù)集上平均排名第1。

具體來看，DDM 在各數(shù)據(jù)集上均有較高的檢測延遲和漏報(bào)率，在包含漸變型漂移的數(shù)據(jù)集上更為嚴(yán)重。RDDM 則在DDM 基礎(chǔ)上，通過設(shè)定閾值周期性地重置DDM 的漂移統(tǒng)計(jì)量來提高檢測漂移的敏感性，一定程度上降低了檢測延遲和漏報(bào)率，但也增加了誤報(bào)的風(fēng)險(xiǎn)。在6 個(gè)人工數(shù)據(jù)集上平均檢測延遲和漏報(bào)率都低于DDM，但誤報(bào)率都高于DDM。HDDM 的效果與RDDM 相似，在所有數(shù)據(jù)集上較DDM 有更低的檢測延遲和漏報(bào)率，但這以增加誤報(bào)為代價(jià)。FPDD 在STAGGER、SINE 和MIXED3 個(gè)突變型漂移的數(shù)據(jù)集上檢測效果很好，具有極低的檢測延遲、誤報(bào)率和漏報(bào)率，而在其他3 個(gè)漸變型漂移的數(shù)據(jù)集上效果很差。SeqDrift 在漸變型漂移的數(shù)據(jù)集上的檢測延遲要好于突變型漂移數(shù)據(jù)集，而在所有數(shù)據(jù)集上均存在較高的誤報(bào)率，但漏報(bào)率極低，僅在LED 數(shù)據(jù)集上出現(xiàn)了漏報(bào)。與其他算法相比，DFWM 處理突變型漂移的能力僅次于FPDD，由表5知，在STAGGER、SINE 和MIXED 3 個(gè)突變型數(shù)據(jù)集上，F(xiàn)PDD 的平均檢測延遲最低，DFWM 次之。而DFWM 處理漸變型漂移能力顯著強(qiáng)于其他算法，在LED、CIRCLE 和SEA 3 個(gè)漸變型數(shù)據(jù)集上平均檢測延遲、誤報(bào)率和漏報(bào)率均最低。這主要得益于DFWM 的雙層滑動窗口和基于隸屬度的加權(quán)機(jī)制，使其可以快速處理多種類型的概念漂移，具有較強(qiáng)的魯棒性。除DFWM 外，F(xiàn)PDD 和SeqDrift 也是基于滑動窗口的算法，但它們均使用一個(gè)固定長度的窗口，缺少加權(quán)機(jī)制，只適用于某一種特定類型概念漂移。由表5～表7 知，F(xiàn)PDD 只適合處理突變型漂移，而SeqDrift 只適合處理漸變型漂移，具有較大的局限性。而DDM、RDDM 和HDDM 三種算法是基于統(tǒng)計(jì)過程控制的算法，沒有使用滑動窗口，在所有數(shù)據(jù)集上的檢測延遲和誤報(bào)率均高于DFWM，因此處理突變型漂移和漸變型漂移的能力均弱于DFWM。

Table 2 Comparison of average delay of detection表2 平均檢測延遲對比

Table 3 Comparison of false positive rate表3 誤報(bào)率對比

Table 4 Comparison of false negative rate表4 漏報(bào)率對比

Table 5 Comparison of algorithm average delay of detection on synthesized datasets表5 人工數(shù)據(jù)集上的算法平均檢測延遲對比

Table 6 Comparison of algorithm false positive rate on synthesized datasets表6 人工數(shù)據(jù)集上的算法誤報(bào)率對比

Table 7 Comparison of algorithm false negative rate on synthesized datasets表7 人工數(shù)據(jù)集上的算法漏報(bào)率對比

3.6 分類準(zhǔn)確率和運(yùn)行時(shí)間

檢測概念漂移的目的是為了及時(shí)發(fā)現(xiàn)數(shù)據(jù)流中概念的變化，調(diào)整當(dāng)前分類模型，提高分類準(zhǔn)確率。為進(jìn)一步驗(yàn)證DFWM 的概念漂移檢測機(jī)制和重復(fù)概念識別機(jī)制能否有效提高分類準(zhǔn)確率，本文選取了RCD、OAUE 和LearnNSE 三種算法進(jìn)行對比。在SINE、SEA、Spam 和Electricity 4 個(gè)數(shù)據(jù)集上分別比較它們的分類準(zhǔn)確率和運(yùn)行時(shí)間。SINE 和SEA 包含重復(fù)概念，Spam 和Electricity 為含有概念漂移真實(shí)數(shù)據(jù)集，但漂移的類型、發(fā)生的時(shí)間未知。DFWM 和RCD 是基于單分類器的算法，使用skmultiflow 包中的HoeffdingTree做分類器。OAUE 和LearnNSE 為集成算法，根據(jù)文獻(xiàn)[14-15]，OAUE 使用Hoeffding Tree做基分類器，而LearnNSE 使用CART 決策樹做基分類器。

表8 給出了各算法在4 個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率。4 個(gè)算法中，只有DFWM 和RCD 具有重復(fù)概念識別機(jī)制?？梢钥闯觯赟INE 和SEA 兩個(gè)具有重復(fù)概念的數(shù)據(jù)集上，盡管DFWM 是單分類器算法，但由于可以識別重復(fù)概念，直接復(fù)用過去已訓(xùn)練好的舊分類器，避免重建分類器，更快地適應(yīng)新概念，獲得了最高準(zhǔn)確率。在Spam 上，DFWM 的準(zhǔn)確率最高，略高于RCD，而在Electricity 上，OAUE 獲得最高的準(zhǔn)確率，DFWM 次之。

Table 8 Comparison of classification accuracy表8 分類準(zhǔn)確率對比

每個(gè)算法的運(yùn)行時(shí)間如表9 所示。在4 個(gè)數(shù)據(jù)集上，RCD 的運(yùn)行時(shí)間最短，本文算法DFWM 略高于RCD。而OAUE 和LearnNSE 是集成算法，運(yùn)行時(shí)間遠(yuǎn)高于基于單分類器的RCD 和DFWM。特別地，在SINE 和SEA 兩個(gè)數(shù)據(jù)集上，LearnNSE 的運(yùn)行時(shí)間顯著高于OAUE，而在Spam 和Electricity 上則相反。這主要因?yàn)長earnNSE 沒有剪枝策略，會保留在所有數(shù)據(jù)塊上訓(xùn)練的分類器。而SINE 和SEA 數(shù)據(jù)集規(guī)模要遠(yuǎn)大于Spam 和Electricity，因此LearnNSE 在前者上會訓(xùn)練更多的分類器，運(yùn)行時(shí)間更長。

Table 9 Comparison of running time表9 運(yùn)行時(shí)間對比

由圖6 可知，SINE 數(shù)據(jù)集上共發(fā)生4 次漂移，分別位于數(shù)據(jù)流的20%、40%、60%和80%處。在初始階段，數(shù)據(jù)流中無概念漂移，所有算法的準(zhǔn)確率的變化趨勢相似，先上升然后趨于穩(wěn)定。遭遇概念突變時(shí)，所有算法的準(zhǔn)確率均出現(xiàn)了不同程度的下降，DFWM 由于可以快速檢測到概念漂移，并識別重復(fù)概念，及時(shí)調(diào)整當(dāng)前分類器，抗漂移能力較強(qiáng)，準(zhǔn)確率曲線僅出現(xiàn)了小幅下降，基本保持穩(wěn)定。而OAUE和RCD 的準(zhǔn)確率在漂移處發(fā)生了顯著下降，然后緩慢上升。LearnNSE 的準(zhǔn)確率也基本保持穩(wěn)定，但整體準(zhǔn)確率始終較低。此外，SINE 中含有10%的噪聲，表明DFWM 具有一定的抗噪能力。

Fig.6 Comparison of classification accuracy on SINE dataset圖6 SINE 數(shù)據(jù)集上的分類準(zhǔn)確率比較

圖7 展示了所有算法在Spam 上的準(zhǔn)確率變化情況，Spam 為真實(shí)數(shù)據(jù)集，無法確切地知道概念的變化情況，更能反映算法的泛化能力。觀察圖7 可知，大約在數(shù)據(jù)流的10%處出現(xiàn)了概念漂移。所有算法的準(zhǔn)確率開始不同程度地下降，其中OAUE 下降最嚴(yán)重。RCD 和DFWM 的變化趨勢相似，準(zhǔn)確率小幅下降后緩慢上升，但DFWM 更為穩(wěn)定，始終保持最高的準(zhǔn)確率，這表明本文算法的抗漂移能力較強(qiáng)，可以很好地適應(yīng)真實(shí)數(shù)據(jù)環(huán)境。

Fig.7 Comparison of classification accuracy on Spam dataset圖7 Spam 數(shù)據(jù)集上的分類準(zhǔn)確率比較

通過上述實(shí)驗(yàn)，可以得出以下結(jié)論：（1）相比同類算法，DFWM 檢測漂移具有較低的平均檢測延遲、誤報(bào)率和漏報(bào)率，能夠快速檢測到不同類型的概念漂移。（2）DFWM 的概念漂移檢測機(jī)制和重復(fù)概念識別機(jī)制有效提高了分類準(zhǔn)確率，尤其在含有重復(fù)概念的數(shù)據(jù)流中，并且在復(fù)雜的真實(shí)數(shù)據(jù)環(huán)境中也有較強(qiáng)的適應(yīng)性。（3）如果已知數(shù)據(jù)流僅包含突變型或漸變型漂移，建議使用單層窗口版本的DFWM_S 或DFWM_L，可以降低一定的內(nèi)存占用和運(yùn)行時(shí)間。如果數(shù)據(jù)流包含突變型、漸變型或重復(fù)型等多種類型的概念漂移，或者不清楚數(shù)據(jù)流中的漂移類型，建議使用雙層窗口版本的DFWM，它具有更強(qiáng)的性能和魯棒性。

4 結(jié)束語

本文提出了一種新的可以適于多類型概念漂移的數(shù)據(jù)流分類算法(DFWM)。針對當(dāng)前主動檢測型數(shù)據(jù)流分類算法存在較高的檢測延遲和誤報(bào)率，無法有效處理不同類型漂移等問題，DFWM 在傳統(tǒng)滑動窗口的基礎(chǔ)上引入了雙層窗口，結(jié)合隸屬度函數(shù)和McDiarmid 界，通過分析當(dāng)前窗口內(nèi)數(shù)據(jù)錯(cuò)誤率是否發(fā)生顯著性變化，可以快速檢測到數(shù)據(jù)流中不同類型的概念漂移。而針對當(dāng)前數(shù)據(jù)流分類算法無法有效利用歷史信息處理重復(fù)概念的問題，DFWM 通過SPLL 判斷當(dāng)前概念是否為歷史概念的重現(xiàn)，只有檢測到新概念時(shí)才重新構(gòu)建新分類器，否則直接復(fù)用舊分類器，有效減少了重復(fù)構(gòu)建分類器的開銷，更快地適應(yīng)當(dāng)前概念。人工和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，與以往同類算法相比，DFWM 在平均檢測延遲、誤報(bào)率、分類準(zhǔn)確率和運(yùn)行時(shí)間上都具有一定優(yōu)勢。

本文只考慮了類別平衡數(shù)據(jù)流中的概念漂移問題，而數(shù)據(jù)流中的類別不平衡問題會進(jìn)一步增加處理概念漂移的難度，下一步將考慮如何處理不平衡數(shù)據(jù)流中的概念漂移問題，以便模擬更多的實(shí)際情況。