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

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

0 引言

近年來，大數(shù)據(jù)、物聯(lián)網(wǎng)技術(shù)以及人工智能迅速發(fā)展，各行各業(yè)都在持續(xù)產(chǎn)生大量數(shù)據(jù)，并以驚人的速度不斷增長。這些數(shù)據(jù)根據(jù)自身特性被稱為數(shù)據(jù)流，如網(wǎng)絡(luò)數(shù)據(jù)、天氣預(yù)測數(shù)據(jù)、無線傳感數(shù)據(jù)、金融和電網(wǎng)數(shù)據(jù)等［1］。傳統(tǒng)的機(jī)器學(xué)習(xí)算法假設(shè)數(shù)據(jù)平穩(wěn)分布，然而，不斷演變的數(shù)據(jù)流環(huán)境中的基礎(chǔ)數(shù)據(jù)分布可能會隨時(shí)間變化，即發(fā)生一種被稱為概念漂移的現(xiàn)象，意味著時(shí)間點(diǎn)x與y的數(shù)據(jù)分布滿足D≠x在現(xiàn)實(shí)生活中，概念漂移的案例包括不斷變化的用戶興趣偏好、監(jiān)測系統(tǒng)、天氣預(yù)測和財(cái)務(wù)欺詐檢測等［3-6］。隨著概念漂移的發(fā)生，過去舊的學(xué)習(xí)模型不再有效，繼而導(dǎo)致分類精度下降。因此，適應(yīng)不斷變化的數(shù)據(jù)分布從而保證較高的學(xué)習(xí)性能至關(guān)重要。

目前，相當(dāng)多的自適應(yīng)學(xué)習(xí)算法使用概念漂移檢測方法來檢測不斷演變的數(shù)據(jù)流中的概念漂移。通常情況下，當(dāng)分類器檢測到漂移時(shí)，分類模型將會更新或重新訓(xùn)練以適應(yīng)概念漂移。已經(jīng)有許多概念漂移檢測方法被提出，主要分為：1）基于統(tǒng)計(jì)的方法，包括DDM（Drift Detection Method）［7］、EDDM（Early DDM）［8］、RDDM（Reactive DDM）［9］、WSTD（Wilcoxon rank Sum Test Drift detector）［10］、DMDDM（Diversity Measure DDM）［11］以及BDDM（Bhattacharyya distance-based DDM）［12］；2）基于窗 口的方法，包 括ADWIN（ADaptive WINdowing）［13］、SEED（SEED drift detector）［14］、FHDDM（Fast Hoeffding DDM）［15］、HDDM（DDM based on Hoeffding’s bounds）［16］以及MDDM（McDiarmid DDM）［17］；3）基于序列分析的方法，如文獻(xiàn)［18］中的方法。

上述漂移檢測方法要么需要巨大的時(shí)間和內(nèi)存成本，要么無法以較低的檢測延遲盡快地檢測出概念漂移，同時(shí)又保持較低的誤檢率與漏檢率。因此，為了平衡檢測延遲、誤檢率與漏檢率以及時(shí)空效率等漂移檢測方法中的重要評價(jià)指標(biāo)，本文提出一種分段加權(quán)的概念漂移檢測方法（Multi-Stage weighted DDM，MSDDM）。該方法提出一個(gè)階段轉(zhuǎn)換的閾值參數(shù)，在概念漂移檢測中引入包含“穩(wěn)定階段-警告階段-漂移階段”三個(gè)階段的分段加權(quán)漂移檢測機(jī)制，同時(shí)使用長滑動窗口與短滑動窗口重疊的窗口機(jī)制。在“穩(wěn)定階段”對兩個(gè)窗口內(nèi)的實(shí)例賦予權(quán)重，窗口中最新的實(shí)例將被賦予較大的權(quán)重，而舊的、過時(shí)的實(shí)例則被賦予較低的權(quán)重以更快地檢測出概念漂移，且此時(shí)實(shí)例間的權(quán)重值差異較小，同時(shí)計(jì)算窗口內(nèi)的加權(quán)與最大加權(quán)分類預(yù)測正確平均值。進(jìn)入“警告階段”后，增大窗口內(nèi)實(shí)例間的權(quán)重值的差異，并更新加權(quán)與最大加權(quán)分類預(yù)測正確平均值。最終，在“漂移階段”使用基于Hoeffding 不等式產(chǎn)生的Hoeffding 界，判斷加權(quán)與最大加權(quán)分類預(yù)測正確平均值的差值，若超過事先定義的閾值，則報(bào)告一個(gè)概念漂移的發(fā)生。此時(shí)，將重置分類器進(jìn)行重新訓(xùn)練。實(shí)驗(yàn)結(jié)果表明，本文提出的MSDDM 檢測方法在檢測數(shù)據(jù)流中的概念漂移時(shí)，具備較高的漂移檢測性能。

1 相關(guān)工作

1.1 概念漂移

概念漂移是數(shù)據(jù)流挖掘中廣泛存在的問題，由流式數(shù)據(jù)隨時(shí)間的變化或演變引起。底層分布的改變會導(dǎo)致到達(dá)實(shí)例的特征向量不再反映類標(biāo)簽。這會對使用流數(shù)據(jù)分布進(jìn)行預(yù)測的分類器的可靠性和準(zhǔn)確性造成消極影響。假設(shè)數(shù)據(jù)流以連續(xù)的(xt，yt)實(shí)例的形式出現(xiàn)，其中t=1，2，…，xt是一個(gè)特征向量，y∈{y1，y2，…，yn}是一個(gè)具有n個(gè)類標(biāo)簽的集合。預(yù)測器在一個(gè)特定時(shí)間基于特征向量xt得到的預(yù)測結(jié)果可以用yi表示。那么在t0到t1的時(shí)刻內(nèi)的概念漂移可以被定義為式（1）［19］：

其中：pt表示在t時(shí)刻特征向量xt和目標(biāo)類標(biāo)簽yt之間的聯(lián)合概率分布。數(shù)據(jù)流分布的變化即發(fā)生了概念漂移，可通過聯(lián)合概率分布的變化體現(xiàn)。

文獻(xiàn)［20］中對概念漂移作了近一步描述。在某一時(shí)刻，p(xt，yt)可由條件類概念分布得到：

然后再對輸入的xt進(jìn)行預(yù)測，根據(jù)貝葉斯決策論可得后驗(yàn)概率分布如下：

以上是一般情況下對概念漂移的定義。另外，通常把一個(gè)新目標(biāo)概念取代舊目標(biāo)概念的時(shí)間步稱作概念漂移持續(xù)的時(shí)間，而完成漂移的持續(xù)時(shí)間越短，則漂移的速度就越快［21］。因此根據(jù)概念漂移的速度，可以把概念漂移分為突變型、漸變型、增量型以及重復(fù)型［22］，如圖1 所示。突變型與漸變型概念漂移作為最常見的概念漂移類型是本文的重點(diǎn)研究對象。

圖1 概念漂移示意圖Fig.1 Schematic diagram of concept drift

1.2 不同窗口機(jī)制的漂移檢測方法

窗口機(jī)制已廣泛用于處理數(shù)據(jù)流中的概念漂移問題。一般認(rèn)為，最新的實(shí)例是最有用的信息，并逐步估計(jì)通過當(dāng)前時(shí)間或數(shù)據(jù)窗口內(nèi)數(shù)據(jù)的變化［2］。窗口機(jī)制定義窗口是一個(gè)短的內(nèi)存數(shù)據(jù)結(jié)構(gòu)，可以存儲信息性數(shù)據(jù)或總結(jié)有關(guān)模型行為或數(shù)據(jù)分布的一些統(tǒng)計(jì)信息，以描述當(dāng)前的概念。目前，滑動窗口機(jī)制是漂移檢測方法最常用的窗口機(jī)制之一?；瑒哟翱谟梢环N先進(jìn)先出（First In First Out，F(xiàn)IFO）的數(shù)據(jù)結(jié)構(gòu)構(gòu)成。滑動窗口定義了一個(gè)大小為n的窗口后，隨著一個(gè)新實(shí)例的到達(dá)，最舊的一個(gè)實(shí)例將被丟棄［23］。它的機(jī)制如圖2 所示。目前，滑動窗口機(jī)制主要分為單窗口與雙窗口。

圖2 滑動窗口Fig.2 Sliding window

Gama等［7］提出了在單個(gè)窗口內(nèi)使用二項(xiàng)分布的DDM。對于每一個(gè)實(shí)例i，DDM 計(jì)算它的錯(cuò)誤率即給定實(shí)例錯(cuò)誤分類的概率pi與對應(yīng)的標(biāo)準(zhǔn)偏差si以檢測概念漂移。DDM 更加適合處理突變漂移，因?yàn)闈u變漂移容易被忽略而不會觸發(fā)警告。Pesaranghader等［15］提出FHDDM，使用單滑動窗口與Hoeffding 不等式來計(jì)算并比較最大預(yù)測正確率與當(dāng)前預(yù)測正確率的差異，從而檢測漂移。最近，Baidari等［12］使用單個(gè)窗口提出了一種基于Bhattacharyya 距離的BDDM，利用Bhattacharyya 距離檢測窗口內(nèi)的錯(cuò)誤率與方差的變化以檢測突變與漸變漂移。

雙窗口機(jī)制主要分為分離型、鄰接型與重疊型，如圖3所示。STEPD（Statistical Test of Equal Proportions Detection）［24］對兩個(gè)分離型窗口的數(shù)據(jù)使用具有連續(xù)性校正的等比例統(tǒng)計(jì)檢驗(yàn)，當(dāng)檢測到最近窗口和舊窗口中的精度存在顯著差異時(shí)，發(fā)出警告和漂移信號。ADWIN［13］則是經(jīng)典的使用鄰接型雙窗口的漂移檢測方法。ADWIN 的主要思路是：當(dāng)最新窗口W的兩個(gè)子窗口w1、w2內(nèi)的平均值顯示出足夠大的差異時(shí)，如果推斷出對應(yīng)的預(yù)測值相異，則刪除舊窗口。SEED［14］同樣基于ADWIN 中的雙窗口，當(dāng)子窗口的平均值高于所選閾值時(shí)，丟棄舊的子窗口，使用帶有Bonferroni 校正的Hoeffding 不等式計(jì)算測試統(tǒng)計(jì)量。而FHDDMS（Stacking Fast Hoeffding DDM）［25］則使用疊加的兩個(gè)滑動窗口獲取預(yù)測結(jié)果以檢測概念漂移。不同于FHDDMS［25］中的Hoeffding邊界，Pears等［26］在兩個(gè)子窗口中使用Bernstein 邊界來比較樣本的均值與方差，并且認(rèn)為Bernstein 邊界相較于其他已發(fā)布的邊界能夠提供更優(yōu)秀的結(jié)果，尤其是在方差分布較低的情況下。本文方法同樣是在窗口機(jī)制的框架下比較窗口間的分類預(yù)測準(zhǔn)確率、方差與標(biāo)準(zhǔn)差以得到差異性，更加注重于不同等級的漂移狀態(tài)之間的關(guān)聯(lián)與差異。

2 本文方法

本文將數(shù)據(jù)流中出現(xiàn)的突變型與漸變型概念漂移作為研究對象，提出了一個(gè)階段轉(zhuǎn)換閾值參數(shù)，在概念漂移檢測中引入了“穩(wěn)定階段-警告階段-漂移階段”三個(gè)階段的分段加權(quán)機(jī)制，分階段地在漂移檢測過程中使用實(shí)例加權(quán)機(jī)制，最后結(jié)合雙層滑動窗口機(jī)制，并基于Hoeffding 不等式，提出了一種分段加權(quán)的漂移檢測方法MSDDM。

2.1 分段加權(quán)機(jī)制

ADWIN［13］、DDM［7］、STEPD［24］、FHDDM［15］都是使用滑動窗口的經(jīng)典漂移檢測方法，它們大都比較一個(gè)窗口內(nèi)的兩個(gè)子窗口內(nèi)部的差異性以檢測漂移。

綜合發(fā)現(xiàn)，較短的滑動窗口能夠更快地發(fā)現(xiàn)發(fā)生突變型概念漂移時(shí)數(shù)據(jù)流中的數(shù)據(jù)分布變化，并及時(shí)觸發(fā)一個(gè)漂移信號并使分類器作出相應(yīng)的變化以適應(yīng)概念漂移。另外，對于漂移長度較長的漸變型概念漂移，較短的滑動窗口可能無法適應(yīng)緩慢變化的數(shù)據(jù)流，因此長度較大的滑動窗口可能更適合處理漸變型概念漂移［25］。基于以上結(jié)論，本文使用一組長滑動窗口與短滑動窗口相重疊的滑動窗口組合以同時(shí)適應(yīng)數(shù)據(jù)流中的突變型與漸變型概念漂移，如圖4 所示。

圖4 雙層滑動窗口機(jī)制Fig.4 Double sliding window mechanism

在數(shù)據(jù)流環(huán)境中，一般認(rèn)為舊的實(shí)例已經(jīng)過時(shí)并將對學(xué)習(xí)模型不再有效，新實(shí)例更能反映數(shù)據(jù)流環(huán)境中當(dāng)前的情況，因此，增量式分類器應(yīng)該使用最近的實(shí)例進(jìn)行訓(xùn)練。在線學(xué)習(xí)算法通常使用衰落因子或加權(quán)方法來增加最近的實(shí)例的權(quán)重。從自適應(yīng)學(xué)習(xí)的角度來看，這一點(diǎn)非常重要，尤其是在數(shù)據(jù)流中的兩個(gè)概念之間發(fā)生轉(zhuǎn)換即發(fā)生概念漂移時(shí)。對窗口中最新的實(shí)例賦予更大的權(quán)重，并逐漸忘記舊的實(shí)例，有助于更快地檢測出概念漂移。

本文提出了一種分段加權(quán)的概念漂移檢測機(jī)制。將漂移檢測階段共分為三個(gè)階段，分別為“穩(wěn)定階段”“警告階段”和“漂移階段”。首先，數(shù)據(jù)流以成對的實(shí)例組(xi，yi)組成，其中xi是屬性向量，yi是對應(yīng)的類。對于每個(gè)實(shí)例，樸素貝葉斯（Na?ve Bayes，NB）或Hoeffding 樹（Hoeffding Tree，HT）等分類器將作出一個(gè)預(yù)測，然后將與實(shí)際結(jié)果yi相比較，以決定預(yù)測是否正確（即=yi是否成立）。若當(dāng)前預(yù)測結(jié)果正確，則同時(shí)向長滑動窗口與短滑動窗口中插入1；若預(yù)測錯(cuò)誤，則插入0。

在“穩(wěn)定階段”，本文對兩個(gè)窗口內(nèi)的實(shí)例進(jìn)行加權(quán)。本文使用線性加權(quán)方案，加權(quán)機(jī)制如圖5 所示。隨著實(shí)例的增加，最新實(shí)例的權(quán)重值相較于舊的實(shí)例的權(quán)重值線性增加。定義ωi為某一實(shí)例所賦予的權(quán)重值，在線性加權(quán)方案中，ωi+1-ωi=diff，即某個(gè)實(shí)例的權(quán)重值計(jì)算公式如下：

圖5 加權(quán)機(jī)制Fig.5 Weighting mechanism

ωi=1 +(i-1)*diff

在“穩(wěn)定階段”內(nèi)，diff賦值為0.01。定義在短滑動窗口與長滑動窗口內(nèi)的加權(quán)平均分類預(yù)測正確率為us，ω和ul，ω，如式（4）、式（5）所示：

其中：|Ws|與 |Wl|分別表示長滑動窗口與短滑動窗口的長度；ωi=1 +(i-1)*0.01。因此，在“穩(wěn)定階段”，計(jì)算實(shí)例的權(quán)重值時(shí)所使用的diff值為0.01，該參數(shù)的取值是通過實(shí)驗(yàn)對比得到的最佳數(shù)值。

同時(shí)，在下一次概念漂移被報(bào)告之前，本文分別定義長滑動窗口與短滑動窗口中迄今為止觀察到的最大加權(quán)平均分類預(yù)測正確率為，它們的計(jì)算方式為：若us，ω，則；若

為了何時(shí)進(jìn)入“警告階段”，本文分別為長滑動窗口與短滑動窗口定義了一個(gè)階段轉(zhuǎn)變閾值參數(shù)λs和λl：

當(dāng)滿足λs＞θs或λl＞θl時(shí)，進(jìn)入“警告階段”，且θs=0.78，θl=0.85。事先定義的閾值θs和θl的確定將在實(shí)驗(yàn)部分進(jìn)行詳細(xì)討論。

在“警告階段”內(nèi)，MSDDM 將增加長短滑動窗口與短滑動窗口內(nèi)實(shí)例間的權(quán)重值的差異，強(qiáng)調(diào)最新的實(shí)例的重要性以更快地檢測出概念漂移。因此，進(jìn)入“警告階段”后，將長短滑動窗口內(nèi)的加權(quán)平均分類預(yù)測正確率us，ω和ul，ω更新為us，ω′與ul，ω′：

其中：ωi′=1 +(i-1)*5。即在“警告階段”，計(jì)算實(shí)例的權(quán)重值時(shí)所使用的diff=5，該參數(shù)的取值同樣是通過實(shí)驗(yàn)對比得到的最佳數(shù)值。

最終，在“漂移階段”，MSDDM 基于Hoeffding 不等式產(chǎn)生的Hoeffding 界計(jì)算漂移檢測的閾值以判斷概念漂移是否發(fā)生。基于可能近似正確（Probably Approximate Correct，PAC）學(xué)習(xí)理論，分類錯(cuò)誤率隨實(shí)例數(shù)的增加而減小，否則，則有可能發(fā)生了概念漂移。因此，MSDDM 同時(shí)計(jì)算長短滑動窗口內(nèi)的最大加權(quán)平均分類預(yù)測正確率與加權(quán)平均分類預(yù)測正確率，若兩者之差大于事先定義的閾值，則報(bào)告一個(gè)概念漂移的發(fā)生。此時(shí)，將重置分類器以重新訓(xùn)練來適應(yīng)新的數(shù)據(jù)分布。

MSDDM 中使用的Hoeffding 不等式描述的是一組隨機(jī)變量均值的概率不等式，給出了隨機(jī)變量與它的期望值偏差的概率上限，如定理1［27］所示。

定理1 Hoeffding 不等式。設(shè)X1，X2，…，Xn是n個(gè)獨(dú)立的隨機(jī)變量，Xi∈[ai，bi]，i∈{1，2，…，n} 。經(jīng)驗(yàn)均值之間的差值，對于任意的ε＞0，都有如下：

其中：式（11）表示顯著性水平δ，即真實(shí)分類正確率與訓(xùn)練分類正確率不相符的最大概率。最后，考慮樣本的平均值Xˉ，給定顯著性水平最高為δ和樣本數(shù)量n，得到一個(gè)估計(jì)誤差εδ即Hoeffding 邊界，如式（12）所示。該Hoeffding 邊界能夠描述當(dāng)前窗口中的最大加權(quán)分類預(yù)測正確率與窗口中當(dāng)前的分類預(yù)測正確率能夠被允許的最大差值即錯(cuò)誤率邊界，以此當(dāng)作漂移檢測閾值并作為檢測概念漂移的信號。

將長短滑動窗口的漂移檢測閾值εs與εl定義為：

MSDDM 分別定義長、短滑動窗口內(nèi)的最大加權(quán)平均分類預(yù)測正確率與當(dāng)前平均分類預(yù)測正確率之差為Δl與Δs，且。那么，當(dāng)Δs大于事先定義的閾值εs或Δl大于事先定義的閾值εl時(shí)，都將報(bào)告概念漂移的發(fā)生。

2.2 分段加權(quán)的漂移檢測方法（MSDDM）

基于以上分階段的加權(quán)機(jī)制，本文將分析分類器產(chǎn)生的預(yù)測結(jié)果，并存入雙層滑動窗口內(nèi)，然后應(yīng)用決策模型嘗試檢測數(shù)據(jù)分布的變化并表明概念漂移的發(fā)生。

具體地，給定一組成對的實(shí)例(xi，yi)，其中：xi是屬性向量，yi是對應(yīng)的類，對于每個(gè)例子，基分類器將作出一個(gè)預(yù)測，然后與實(shí)際結(jié)果yi比較，以決定預(yù)測是否正確（即=yi是否正確），并將預(yù)測結(jié)果的信息存入滑動窗口內(nèi)以供檢測模型使用。大多數(shù)現(xiàn)有的漂移檢測器通過預(yù)測結(jié)果分析分類精度（錯(cuò)誤率）以及相應(yīng)的標(biāo)準(zhǔn)差，并找到不同窗口內(nèi)的差異性。不同的漂移檢測方法使用不同的策略或統(tǒng)計(jì)信息來監(jiān)視基分類器的性能，并決定何時(shí)發(fā)生概念漂移。

基于PAC 學(xué)習(xí)模型，MSDDM 假設(shè)只要樣本分布平穩(wěn)，當(dāng)樣本數(shù)量增加時(shí)錯(cuò)誤率會減小，即分布精度呈上升趨勢。因此，錯(cuò)誤率的增加或分類精度的降低都表明數(shù)據(jù)分布可能發(fā)生了變化，現(xiàn)有分類器的學(xué)習(xí)性能很可能降低。因此可以利用分類器的分類正確率（或錯(cuò)誤率）反映當(dāng)前數(shù)據(jù)流中的數(shù)據(jù)分布變化。本文使用疊加的長短滑動窗口獲取分類預(yù)測結(jié)果，并基于Hoeffding 不等式提出了一種分段加權(quán)的漂移檢測方法（MSDDM）。

MSDDM 的具體流程如算法1 所示。第1）～3）行表示初始化兩個(gè)滑動窗口的窗口大小，并給參數(shù)賦值，然后計(jì)算εs、εl的值。第4）～7）行判斷窗口內(nèi)的實(shí)例是否已滿，若是則丟棄最舊的實(shí)例并插入最新的實(shí)例。第8）～12）行表示在“穩(wěn)定階段”內(nèi)，計(jì)算窗口內(nèi)的加權(quán)分類預(yù)測正確平均值us·ω和ul·ω，并更新 最大加 權(quán)分類 預(yù)測平均值值。第13）～20）行判斷方法是否進(jìn)入“警告階段”，若是，則將分類預(yù)測正確平均值us·ω和ul·ω、更新為加權(quán)分類預(yù)測正確平均值us，ω′和ul，ω′，并更新得到長短窗口當(dāng)前的最大加權(quán)分類預(yù)測正確平均值。計(jì)算得到更新后的最大加權(quán)分類預(yù)測正確平均值與加權(quán)分類預(yù)測正確平均值的差值Δs、Δl。第21）～23）行表示在“漂移階段”內(nèi)，判斷Δs、Δl是否大于事先定義的閾值，若是則將報(bào)告一個(gè)漂移的發(fā)生，并重置分類器以重新訓(xùn)練。

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

為了驗(yàn)證MSDDM 的有效性，在人工數(shù)據(jù)集以及真實(shí)數(shù)據(jù)集上都進(jìn)行了實(shí)驗(yàn)評估，實(shí)驗(yàn)平臺為海量在線分析（Massive Online Analysis，MOA）框架［28］。將MSDDM與最DDM［7］、EDDM［8］、RDDM［9］、FHDDM［15］、FHDDMS［25］、MDDM［17］、HDDM［16］以及BDDM［12］等方法進(jìn)行對比。其中：MDDM_A、MDDM_E、MDDM_G 代表MDDM 分別使用線性加權(quán)、指數(shù)加權(quán)與歐拉加權(quán)；HDDM_A、HDDM_W 代表HDDM分別通過移動平均值和加權(quán)移動平均值檢測漂移。實(shí)驗(yàn)使用Intel Core i5-4200H CPU @ 2.80 GHz 和8 GB RAM。

3.1 評估指標(biāo)

當(dāng)漂移發(fā)生在某一時(shí)刻時(shí)，通常存在漂移檢測延遲的情況。因此，為了有效評估漂移檢測的及時(shí)性，引入檢測延遲（Detection Delay，DD），即描述漂移的實(shí)際位置與檢測到的位置之間的實(shí)例數(shù)量以評估方法的檢測及時(shí)性。設(shè)某一次漂移實(shí)際發(fā)生時(shí)刻的實(shí)例位置為itrue，漂移檢測方法檢測到漂移發(fā)生時(shí)刻的實(shí)例位置為idetect，則定義某一次漂移檢測的延遲為idetect-itrue。本文定義某一數(shù)據(jù)集中的DD 如式（15）所示：

引入文獻(xiàn)［13］中的最大檢測延遲Δd，它是用于確定檢測到的漂移距離漂移的真實(shí)位置有多遠(yuǎn)時(shí)則被視為真正的漂移的閾值。參考文獻(xiàn)［15］中的設(shè)置，本文在包含突變型概念漂移的數(shù)據(jù)集中設(shè)置最大檢測延遲Δd為250，在包含漸變型概念漂移數(shù)據(jù)集中設(shè)置為1 000。

真檢率（True Positive Ratio，TPR）：設(shè)漂移發(fā)生的時(shí)刻為T，則在區(qū)間［T，T+Δd］內(nèi)檢測到的漂移個(gè)數(shù)視為正確檢測的個(gè)數(shù)TP（True Positive）即正確檢測漂移的個(gè)數(shù)。本文將TPR定義為在區(qū)間［T，T+Δd］正確檢測的個(gè)數(shù)/總漂移個(gè)數(shù)。

誤檢率（False Positive Ratio，F(xiàn)PR）：設(shè)漂移發(fā)生的時(shí)刻為T，如果檢測到超出可接受檢測間隔的漂移，則它會錯(cuò)誤地發(fā)出漂移警報(bào)。在區(qū)間［T，T+Δd］外檢測到漂移的個(gè)數(shù)視為誤報(bào)個(gè)數(shù)FP（False Positive），誤檢率FPR 定義為FP（/FP+TP）。

漏檢率（False Negative Ratio，F(xiàn)NR）：漏報(bào)指錯(cuò)誤地忽略了在區(qū)間［T，T+Δd］內(nèi)發(fā)生的漂移，漏檢的漂移個(gè)數(shù)為漏報(bào)個(gè)數(shù)FN（False Negative），定義漏檢率FNR為FN（/FN+TP）。

最后，將在真實(shí)數(shù)據(jù)集中的分類準(zhǔn)確率（Accuracy）、內(nèi)存使用（RAM-Hours）與運(yùn)行時(shí)間（CPU seconds）同樣作為重要的評價(jià)指標(biāo)。

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

人工數(shù)據(jù)集的優(yōu)勢之一是了解漂移的位置等詳細(xì)信息。本文所用的真實(shí)數(shù)據(jù)集如下，它們經(jīng)常被用于數(shù)據(jù)流中的概念漂移檢測和自適應(yīng)學(xué)習(xí)領(lǐng)域。表1 則對本文使用的人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集進(jìn)行了總結(jié)。

表1 實(shí)驗(yàn)數(shù)據(jù)集信息Tab.1 Information of experimental datasets

1）SINE：該數(shù)據(jù)集包含突變漂移。它帶有兩個(gè)屬性（x和y），均勻分布在［0，1］中。此外，該數(shù)據(jù)集使用y=sin（x）進(jìn)行分類。因此，曲線下方的實(shí)例都被歸類為正，而其他實(shí)例則為負(fù)，直到發(fā)生第一次漂移。數(shù)據(jù)集共包含105個(gè)實(shí)例，每2× 104個(gè)實(shí)例，就會發(fā)生一次漂移，然后反向分類。數(shù)據(jù)集共包含4 個(gè)漂移，分別在2× 104、4× 104、6× 104、8× 104個(gè)實(shí)例處，含10%噪聲。

2）MIXED：該數(shù)據(jù)集包含突變漂移。數(shù)據(jù)集有2 個(gè)數(shù)值屬性x和y均勻分布在［0，1］，以及兩個(gè)布爾屬性v和w。實(shí)例被歸類為positive 需要至少滿足以下3 個(gè)條件中的2 個(gè)：v，w，y＜0.5+0.3 sin（2πx）。數(shù)據(jù)集在一次漂移后將分類翻轉(zhuǎn)，且每2× 104個(gè)實(shí)例發(fā)生一次漂移，漂移點(diǎn)分別在2× 104、4× 104、6× 104、8× 104個(gè)實(shí)例處，并含10%噪聲。

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

4）LED：該數(shù)據(jù)集包含漸變漂移。該數(shù)據(jù)集的目標(biāo)是預(yù)測7 段顯示器上的數(shù)字，其中每個(gè)數(shù)字有10%的機(jī)會被顯示。該數(shù)據(jù)集有7 個(gè)與類相關(guān)的屬性、17 個(gè)不相關(guān)的屬性。通過交換相關(guān)屬性來模擬概念漂移。數(shù)據(jù)集共包含100 000個(gè)實(shí)例，每隔25 000 個(gè)實(shí)例產(chǎn)生一次漸變型漂移，即漂移點(diǎn)分別在25 000、50 000、75 000 個(gè)實(shí)例處，并含10%噪聲。

5）ELECTRICITY：它包含45 312 個(gè)實(shí)例，具有8 個(gè)輸入屬性，由澳大利亞新南威爾士電力公司在兩年內(nèi)每30 min 記錄一次。分類器必須預(yù)測電價(jià)的上升（Up）或下降（Down）。概念漂移可能源于消費(fèi)習(xí)慣的改變或突發(fā)事件。

6）FOREST COVERTYPE：由54 個(gè)屬性和581 012 個(gè)實(shí)例組成，描述了從美國林務(wù)局（United States Forest Service，USFS）信息系統(tǒng)獲得的30 m×30 m 的7 種森林覆蓋類型，位于北科羅拉多州羅斯福國家森林的4 個(gè)荒野地區(qū)。

7）POKER HAND：由106個(gè)實(shí)例組成，每個(gè)實(shí)例都是從標(biāo)準(zhǔn)52 張牌組中抽取的5 張牌的示例。每張牌由兩個(gè)屬性（花色和等級）描述，總共有10 個(gè)預(yù)測屬性。

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

1）參數(shù)分析。

首先，對MSDDM 中的參數(shù)θs和θl進(jìn)行了實(shí)驗(yàn)分析。若采集人工與真實(shí)數(shù)據(jù)集中所有實(shí)例下的λs和λl，數(shù)量過于龐大，無法清晰顯示λs和λl隨實(shí)例變化的總體趨勢。因此，本文對所有人工數(shù)據(jù)集中的第一個(gè)漂移點(diǎn)前1 000 個(gè)實(shí)例以及后1 000 個(gè)實(shí)例的λs和λl進(jìn)行了采集，并分別使用樸素貝葉斯以及Hoeffding 樹作為分類器進(jìn)行了實(shí)驗(yàn)。圖6 為參數(shù)值λs和λl分別在突變漂移數(shù)據(jù)集（SINE、MIXED）和漸變漂移數(shù)據(jù)集（CIRCLES、LED）中第一個(gè)漂移點(diǎn)附近的變化趨勢。

由圖6 可以看出無論是在突變或漸變漂移數(shù)據(jù)集，λs在絕大多數(shù)情況下，均在［0.78，1.00］的范圍內(nèi)不斷波動，而在漂移點(diǎn)附近即實(shí)例數(shù)為20 000 時(shí)，λs從0.78 急劇下降至0.40 左右。這意味著在滿足λs∈[0.78，1.00]時(shí)，推測數(shù)據(jù)流中的數(shù)據(jù)分布處于“穩(wěn)定階段”，而當(dāng)λs＜0.78 時(shí)，將有可能發(fā)生概念漂移而進(jìn)入“警告階段”。因此，本文將θs設(shè)置為0.78。另外，從圖6（b）、（d）中可以看出，λl在絕大多數(shù)情況下均在［0.85，1.00］的范圍內(nèi)不斷變化，而在漂移點(diǎn)附近的范圍內(nèi)，λs的值從0.85 驟降至0.70 左右，并且這種變化在圖6（d）中表現(xiàn)得尤為明顯。同時(shí)，圖中所展現(xiàn)的是漸變數(shù)據(jù)集中的長滑動窗口下λl值的變化趨勢，這對于檢測漸變型概念漂移尤為重要。因此，本文將θl的值設(shè)置為0.85。

本文還對“穩(wěn)定階段”與“警告階段”計(jì)算實(shí)例權(quán)重時(shí)所使用的diff值的確定進(jìn)行了實(shí)驗(yàn)討論。圖7 為使用不同diff值的MSDDM 在以NB 作為分類器時(shí)，在包含突變漂移的MIXED 數(shù)據(jù)集與包含漸變漂移的CIRCLES 數(shù)據(jù)集中的檢測延遲（DD）與誤報(bào)率（FPR）。圖7 中，橫坐標(biāo)diff′表示在“警告階段”的取值，且取值范圍為［1，10］區(qū)間內(nèi)的整數(shù)，圖例中的diff則表示在“穩(wěn)定階段”內(nèi)的取值。可以看出，無論是在哪個(gè)數(shù)據(jù)集，diff′的增加雖然會降低DD，但同時(shí)也會提高FPR；而且diff取值的變化對DD 和FPR 的影響較小。因此，為了使本文方法取得較低的DD 并使FPR 達(dá)到一個(gè)可接受的范圍，將“警告階段”使用的diff′取值為5，將“穩(wěn)定階段”內(nèi)所使用的diff取值為0.01。

圖7 不同diff值的MSDDM在人工數(shù)據(jù)集上的漂移檢測性能Fig.7 Drift detection performance of MSDDM with different values of diff on artificial datasets

另外，參考文獻(xiàn)［15］中的設(shè)置，本文將短滑動窗口的長度 |Ws|設(shè)置為25，將長滑動窗口的長度 |Wl|設(shè)置為100。同時(shí)，Hoeffding 界中的置信度δ被設(shè)置為10-7。

2）漂移檢測性能實(shí)驗(yàn)。

將MSDDM 與對比方法在具有突變型概念漂移的人工數(shù)據(jù)集SINE 和MIXED 以及具有漸變型概念漂移的人工數(shù)據(jù)集CIRCLES 和LED 上進(jìn)行了實(shí)驗(yàn)，分別以NB 和HT 作為分類器，結(jié)果如表2 所示，最優(yōu)結(jié)果加粗表示。在SINE、MIXED數(shù)據(jù)集上設(shè)置最大檢測延遲為250，在CIRCLES、LED 數(shù)據(jù)集上設(shè)置Δd為1 000，因?yàn)楸疚目紤]漸變漂移的漂移寬度較長，若設(shè)置過小的Δd則會導(dǎo)致較高的誤檢率。

表2 不同人工數(shù)據(jù)集上的漂移檢測性能結(jié)果Tab.2 Drift detection performance results on different artificial datasets

另外，本文增加了MSDDM 的變體MSDDMnon，MSDDMnon沒有使用分階段的加權(quán)機(jī)制，而是在漂移檢測的全部過程中使用MSDDM 在“警告階段”內(nèi)使用的實(shí)例加權(quán)機(jī)制。

從LED 數(shù)據(jù)集上的結(jié)果可以看出，無論以NB 還是HT 作為分類器，MSDDM 都取得了最低的檢測延遲。在以NB 為分類器時(shí)，相較于對比算法，MSDDM 的DD 降低了0.02～526.47。EDDM 則具有最高的誤檢率與漏檢率。MSDDMnon雖然具有與MSDDM 相當(dāng)?shù)腄D 與TPR，但是無論是以NB 還是HT 作為分類器，F(xiàn)PR 都比MSDDM 增加不少。

從CIRCLES 數(shù)據(jù)集上的結(jié)果可以看出，MSDDM 具有最低的DD，相較于次最優(yōu)的MDDM_E，DD 降低了6.87。FHDDMS、FHDDM 以及MDDM_A 則取得了最低的FPR，但是DD 較高。在NB 為分類器時(shí)，MSDDMnon的FPR 比MSDDM 增加 了43.5%；在 以HT 為分類器時(shí)，MSDDMnon的FPR 比MSDDM 增加了110%。

從SINE 數(shù)據(jù)集上的結(jié)果可以看出，以NB 作為分類器時(shí)，MSDDM 取得了最低的DD 與FNR，但同時(shí)具有一定誤檢，MSDDMnon的FPR 比MSDDM 增加了110%。另外，EDDM和DDM 則具有最高的DD 與最低的TPR。在以HT 作為分類器時(shí)，HDDM_W 取得了最低的檢測延遲，MSDDM 與BDDM 次之，EDDM 和DDM 則具有 最高的DD，MSDDMnon的FPR 比MSDDM 增加了9 倍。

從MIXED 數(shù)據(jù)集上的結(jié)果可以看出，MSDDM 同樣取得了最低的DD 與最高的TPR。在以NB 與HT 為分類器時(shí)，MSDDMnon的FPR 比MSDDM 分別增加了65%與40%。

實(shí)驗(yàn)結(jié)果表明，無論是在具有突變漂移還是漸變漂移的人工數(shù)據(jù)集上，MSDDM 在大多數(shù)情況下，相較于對比方法都具有最低的DD、FPR 與最高的TPR。同時(shí)，MSDDM 在一些數(shù)據(jù)集上也存在一定的誤檢率，但在可接受范圍內(nèi)。分析MSDDM 與MSDDMnon發(fā)現(xiàn)，MSDDM 的DD 與TPR 與MSDDMn相當(dāng)，但是MSDDMnon的FPR 卻比MSDDM 增加了40%～900%，表明MSDDM 的分階段加權(quán)機(jī)制能夠有效地適應(yīng)數(shù)據(jù)流中的噪聲數(shù)據(jù)，同時(shí)又能取得最低的DD 與最高的TPR。

3）準(zhǔn)確度實(shí)驗(yàn)。

本文將MSDDM 在真實(shí)數(shù)據(jù)集即PH（POKER HAND）、ELE（ELECTRICITY）和FC（FOREST COVERTYPE）中進(jìn)行了準(zhǔn)確度的實(shí)驗(yàn)。真實(shí)數(shù)據(jù)集中概念漂移的具體位置、持續(xù)時(shí)間無法得知，因此無法評估檢測延遲、真檢率、誤檢率以及漏檢率。因此，在真實(shí)數(shù)據(jù)集上，主要考慮了在數(shù)據(jù)集中的分類準(zhǔn)確度以及運(yùn)行時(shí)間和內(nèi)存消耗。分別使用NB 和HT 作為分類器，MSDDM 以及對比方法在3 個(gè)真實(shí)數(shù)據(jù)集上的分類準(zhǔn)確度結(jié)果如表3 所示。

表3 使用不同分類器的分類準(zhǔn)確度結(jié)果 單位：%Tab.3 Classification accuracy results by using different classifiers unit：%

由表3 可知，使用NB 作為分類器時(shí)，在PH 數(shù)據(jù)集上，EDDM、BDDM、HDDM_W 以及MSDDM 取得了相對較高的分類準(zhǔn)確度；在ELE 數(shù)據(jù)集上，EDDM、HDDM_A 以及MSDDM則取得了最高的分類準(zhǔn)確度；在FC 數(shù)據(jù)集上，DDM 取得了最高的分類準(zhǔn)確度。使用HT 作為分類器時(shí)，在PH、FC 數(shù)據(jù)集上，MSDDM 取得了最高的分類準(zhǔn)確度；在ELE 數(shù)據(jù)集上，HDDM_A 與MSDDM 取得了相對較高的分類準(zhǔn)確度。

表4 為以NB 和HT 作為分類器，MSDDM 和對比方法在3個(gè)真實(shí)數(shù)據(jù)集上的運(yùn)行時(shí)間（CPU seconds）和內(nèi)存使用（RAM-Hours）結(jié)果對比。CPU seconds 指滿功率運(yùn)行的中央處理器（Central Processing Unit，CPU）上執(zhí)行挖掘算法的時(shí)間，相較于整個(gè)進(jìn)程運(yùn)行時(shí)間，CPU seconds 能夠更加合理地描述漂移檢測方法的時(shí)間消耗；1 RAM-Hour 指算法挖掘過程中，調(diào)用1 GB 隨機(jī)存取存儲器（Random Access Memory，RAM）1 h 所使用的內(nèi)存資源［29］。這兩個(gè)評估指標(biāo)通過MOA框架［28］得到，在目前的主流數(shù)據(jù)挖掘算法［19］中都有使用。在運(yùn)行時(shí)間方面，MSDDM 在PH 與ELE 上所花費(fèi)的運(yùn)行時(shí)間比其他大多數(shù)對比方法都要少。在內(nèi)存消耗方面，MSDDM盡管使用了雙層窗口，但是由于對預(yù)測結(jié)果的存取方式，能取得較少的內(nèi)存消耗。綜上所述，MSDDM 具有最高或較高的分類準(zhǔn)確度，同時(shí)它的時(shí)間與空間消耗也具有優(yōu)秀的表現(xiàn)。

表4 使用不同分類器的時(shí)空消耗結(jié)果Tab.4 Spatiotemporal performance result using different classifier

4 結(jié)語

在用戶興趣偏好、監(jiān)測系統(tǒng)、天氣預(yù)測和財(cái)務(wù)欺詐檢測等諸多現(xiàn)實(shí)世界的應(yīng)用場景中，概念漂移現(xiàn)象成為一個(gè)亟待解決的難題。為了更好地解決數(shù)據(jù)流中的概念漂移問題，本文提出了一種分段加權(quán)的概念漂移檢測方法（MSDDM），利用一個(gè)階段轉(zhuǎn)換的閾值參數(shù)，在概念漂移檢測過程中引入了“穩(wěn)定階段-警告階段-漂移階段”三個(gè)階段的分段加權(quán)機(jī)制，并將該機(jī)制應(yīng)用在雙層滑動窗口機(jī)制。在“穩(wěn)定階段”，MSDDM 將對窗口中最新的實(shí)例賦予較大的權(quán)重，而舊的過時(shí)的實(shí)例則被賦予較低的權(quán)重，且此時(shí)實(shí)例間的權(quán)重值差異較?。欢M(jìn)入“警告階段”，增大窗口內(nèi)實(shí)例間的權(quán)重值的差異以更快地檢測出概念漂移；在“漂移階段”，使用Hoeffding不等式判斷是否發(fā)生了概念漂移。相較于對比方法，本文方法能夠以最低的誤檢率和漏檢率，更快地檢測出數(shù)據(jù)流中的突變和漸變概念漂移，并在真實(shí)數(shù)據(jù)集中取得了高分類精度。在未來工作中，考慮使用自適應(yīng)窗口機(jī)制并采取措施來增強(qiáng)對數(shù)據(jù)流中噪聲的魯棒性以減小誤檢率。