分段加權的概念漂移檢測方法

陳志強，韓萌，武紅鑫，李慕航，張喜龍

（北方民族大學 計算機科學與工程學院，銀川 750021）

0 引言

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

目前，相當多的自適應學習算法使用概念漂移檢測方法來檢測不斷演變的數據流中的概念漂移。通常情況下，當分類器檢測到漂移時，分類模型將會更新或重新訓練以適應概念漂移。已經有許多概念漂移檢測方法被提出，主要分為：1）基于統計的方法，包括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）基于序列分析的方法，如文獻［18］中的方法。

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

1 相關工作

1.1 概念漂移

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

其中：pt表示在t時刻特征向量xt和目標類標簽yt之間的聯合概率分布。數據流分布的變化即發生了概念漂移，可通過聯合概率分布的變化體現。

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

然后再對輸入的xt進行預測，根據貝葉斯決策論可得后驗概率分布如下：

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

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

1.2 不同窗口機制的漂移檢測方法

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

圖2 滑動窗口Fig.2 Sliding window

Gama等［7］提出了在單個窗口內使用二項分布的DDM。對于每一個實例i，DDM 計算它的錯誤率即給定實例錯誤分類的概率pi與對應的標準偏差si以檢測概念漂移。DDM 更加適合處理突變漂移，因為漸變漂移容易被忽略而不會觸發警告。Pesaranghader等［15］提出FHDDM，使用單滑動窗口與Hoeffding 不等式來計算并比較最大預測正確率與當前預測正確率的差異，從而檢測漂移。最近，Baidari等［12］使用單個窗口提出了一種基于Bhattacharyya 距離的BDDM，利用Bhattacharyya 距離檢測窗口內的錯誤率與方差的變化以檢測突變與漸變漂移。

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

2 本文方法

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

2.1 分段加權機制

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

綜合發現，較短的滑動窗口能夠更快地發現發生突變型概念漂移時數據流中的數據分布變化，并及時觸發一個漂移信號并使分類器作出相應的變化以適應概念漂移。另外，對于漂移長度較長的漸變型概念漂移，較短的滑動窗口可能無法適應緩慢變化的數據流，因此長度較大的滑動窗口可能更適合處理漸變型概念漂移［25］?；谝陨辖Y論，本文使用一組長滑動窗口與短滑動窗口相重疊的滑動窗口組合以同時適應數據流中的突變型與漸變型概念漂移，如圖4 所示。

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

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

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

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

圖5 加權機制Fig.5 Weighting mechanism

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

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

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

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

為了何時進入“警告階段”，本文分別為長滑動窗口與短滑動窗口定義了一個階段轉變閾值參數λs和λl：

當滿足λs＞θs或λl＞θl時，進入“警告階段”，且θs=0.78，θl=0.85。事先定義的閾值θs和θl的確定將在實驗部分進行詳細討論。

在“警告階段”內，MSDDM 將增加長短滑動窗口與短滑動窗口內實例間的權重值的差異，強調最新的實例的重要性以更快地檢測出概念漂移。因此，進入“警告階段”后，將長短滑動窗口內的加權平均分類預測正確率us，ω和ul，ω更新為us，ω′與ul，ω′：

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

最終，在“漂移階段”，MSDDM 基于Hoeffding 不等式產生的Hoeffding 界計算漂移檢測的閾值以判斷概念漂移是否發生?；诳赡芙普_（Probably Approximate Correct，PAC）學習理論，分類錯誤率隨實例數的增加而減小，否則，則有可能發生了概念漂移。因此，MSDDM 同時計算長短滑動窗口內的最大加權平均分類預測正確率與加權平均分類預測正確率，若兩者之差大于事先定義的閾值，則報告一個概念漂移的發生。此時，將重置分類器以重新訓練來適應新的數據分布。

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

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

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

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

MSDDM 分別定義長、短滑動窗口內的最大加權平均分類預測正確率與當前平均分類預測正確率之差為Δl與Δs，且。那么，當Δs大于事先定義的閾值εs或Δl大于事先定義的閾值εl時，都將報告概念漂移的發生。

2.2 分段加權的漂移檢測方法（MSDDM）

基于以上分階段的加權機制，本文將分析分類器產生的預測結果，并存入雙層滑動窗口內，然后應用決策模型嘗試檢測數據分布的變化并表明概念漂移的發生。

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

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

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

3 實驗與結果分析

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

3.1 評估指標

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

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

真檢率（True Positive Ratio，TPR）：設漂移發生的時刻為T，則在區間［T，T+Δd］內檢測到的漂移個數視為正確檢測的個數TP（True Positive）即正確檢測漂移的個數。本文將TPR定義為在區間［T，T+Δd］正確檢測的個數/總漂移個數。

誤檢率（False Positive Ratio，FPR）：設漂移發生的時刻為T，如果檢測到超出可接受檢測間隔的漂移，則它會錯誤地發出漂移警報。在區間［T，T+Δd］外檢測到漂移的個數視為誤報個數FP（False Positive），誤檢率FPR 定義為FP（/FP+TP）。

漏檢率（False Negative Ratio，FNR）：漏報指錯誤地忽略了在區間［T，T+Δd］內發生的漂移，漏檢的漂移個數為漏報個數FN（False Negative），定義漏檢率FNR為FN（/FN+TP）。

最后，將在真實數據集中的分類準確率（Accuracy）、內存使用（RAM-Hours）與運行時間（CPU seconds）同樣作為重要的評價指標。

3.2 實驗數據集

人工數據集的優勢之一是了解漂移的位置等詳細信息。本文所用的真實數據集如下，它們經常被用于數據流中的概念漂移檢測和自適應學習領域。表1 則對本文使用的人工數據集和真實數據集進行了總結。

表1 實驗數據集信息Tab.1 Information of experimental datasets

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

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

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

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

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

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

7）POKER HAND：由106個實例組成，每個實例都是從標準52 張牌組中抽取的5 張牌的示例。每張牌由兩個屬性（花色和等級）描述，總共有10 個預測屬性。

3.3 實驗與結果分析

1）參數分析。

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

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

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

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

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

2）漂移檢測性能實驗。

將MSDDM 與對比方法在具有突變型概念漂移的人工數據集SINE 和MIXED 以及具有漸變型概念漂移的人工數據集CIRCLES 和LED 上進行了實驗，分別以NB 和HT 作為分類器，結果如表2 所示，最優結果加粗表示。在SINE、MIXED數據集上設置最大檢測延遲為250，在CIRCLES、LED 數據集上設置Δd為1 000，因為本文考慮漸變漂移的漂移寬度較長，若設置過小的Δd則會導致較高的誤檢率。

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

另外，本文增加了MSDDM 的變體MSDDMnon，MSDDMnon沒有使用分階段的加權機制，而是在漂移檢測的全部過程中使用MSDDM 在“警告階段”內使用的實例加權機制。

從LED 數據集上的結果可以看出，無論以NB 還是HT 作為分類器，MSDDM 都取得了最低的檢測延遲。在以NB 為分類器時，相較于對比算法，MSDDM 的DD 降低了0.02～526.47。EDDM 則具有最高的誤檢率與漏檢率。MSDDMnon雖然具有與MSDDM 相當的DD 與TPR，但是無論是以NB 還是HT 作為分類器，FPR 都比MSDDM 增加不少。

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

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

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

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

3）準確度實驗。

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

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

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

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

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

4 結語

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