崔瑞華，林 玲

（伊犁師范大學(xué)網(wǎng)絡(luò)安全與信息技術(shù)學(xué)院，新疆伊寧 835000）

0 引言

信息技術(shù)的迅速發(fā)展促進(jìn)了工商業(yè)的現(xiàn)代化進(jìn)程，數(shù)據(jù)源生成數(shù)據(jù)的速度越來越快，這種快速連續(xù)的數(shù)據(jù)流中蘊(yùn)含了大量有用信息，稱之為流式數(shù)據(jù)［1］.流數(shù)據(jù)呈現(xiàn)出快速持續(xù)到達(dá)、可變性強(qiáng)、無限等特性，隱含在其中的概念漂移是其最典型的特征.概念漂移描述了流式數(shù)據(jù)分布隨統(tǒng)計(jì)時間而發(fā)生不可預(yù)見的變化.研究概念漂移檢測，有助于提高實(shí)際生活中決策和管理模型的預(yù)知性，預(yù)測和預(yù)警模型的準(zhǔn)確度.

在移動互聯(lián)網(wǎng)時代，大量的流式數(shù)據(jù)涌入人們的生活，不同于傳統(tǒng)的靜態(tài)數(shù)據(jù)，流式數(shù)據(jù)具有數(shù)據(jù)量大，實(shí)時可變性強(qiáng)的特點(diǎn).流式數(shù)據(jù)分為穩(wěn)定的數(shù)據(jù)流和動態(tài)的數(shù)據(jù)流，穩(wěn)定的數(shù)據(jù)流獨(dú)立同分布，而動態(tài)數(shù)據(jù)流不獨(dú)立同分布，容易出現(xiàn)概念漂移.因此迫切需要高效的數(shù)據(jù)分析和機(jī)器學(xué)習(xí)技術(shù)支持我們作出預(yù)測和決策.隨著產(chǎn)品的更新發(fā)展，市場的激烈競爭，顧客需求的改變，就不可避免地出現(xiàn)概念漂移問題.若出現(xiàn)概念漂移，歷史數(shù)據(jù)的歸納模式可能與新數(shù)據(jù)不相關(guān)，預(yù)測和決策結(jié)果的準(zhǔn)確度就會大大降低.概念漂移現(xiàn)象被認(rèn)為是數(shù)據(jù)驅(qū)動信息模型、預(yù)警模型和決策支持模型效率下降的根本原因.在不斷變化的大數(shù)據(jù)環(huán)境中，如何提供更可信有效的數(shù)據(jù)驅(qū)動預(yù)測和決策工具已成為一個不可或缺的問題.以在線商城為例，在線商城顧客行為可能會隨著時間的推移而發(fā)生變化.賣家通過觀察顧客一段時間的搜索購買等數(shù)據(jù)來獲得一個銷售預(yù)測模型，前期買家可以得到一個有效的工作模型，由于顧客的行為是動態(tài)的，會隨著時間的推移而發(fā)生不可預(yù)計(jì)的改變，就會使得模型的預(yù)測結(jié)果越來越不精確，即發(fā)生了概念漂移現(xiàn)象.導(dǎo)致賣家銷售預(yù)測模型發(fā)生概念漂移的因素有很多，例如季度的變化，夏季避暑產(chǎn)品的銷售額會比冬季高，冬季保暖物品的銷售額會比夏季高等.

1986年，Schlimmer 和Granger［2］提出概念漂移的概念，自此有關(guān)概念漂移的研究層出不窮.許冠英等人詳細(xì)闡述了集成分類器中的概念漂移問題［3］，對比算法和實(shí)驗(yàn)數(shù)據(jù)集區(qū)分了不同集成算法的優(yōu)缺點(diǎn)，但并未從檢測概念漂移角度對集成算法進(jìn)行描述；杜詩語等人對概念漂移數(shù)據(jù)流集成分類算法進(jìn)行了介紹［4］，指出現(xiàn)階段概念漂移數(shù)據(jù)流集成分類算法迫切需要解決的問題；翟婷婷等人描述了在線學(xué)習(xí)方法對流數(shù)據(jù)分類的研究現(xiàn)狀［5］，描述了在演化流數(shù)據(jù)上處理“概念漂移”問題；賈濤等人分別從單分類器和集成分類器兩個角度對數(shù)據(jù)流決策樹進(jìn)行綜述［6］，分別介紹了快速決策樹、變異決策樹、概念漂移決策樹以及其他決策樹算法.基于上述研究，本文從多個角度對概念漂移檢測算法進(jìn)行歸納和總結(jié)，分析了不同角度概念漂移研究方法和技術(shù)的最新進(jìn)展，并且提出了進(jìn)一步的研究方向.

1 概念漂移的定義、來源和類型

1.1 概念漂移的定義

概念漂移是指預(yù)測模型目標(biāo)變量的性質(zhì)隨統(tǒng)計(jì)時間的推移發(fā)生無法預(yù)計(jì)的改變［7］.機(jī)器學(xué)習(xí)領(lǐng)域，首先要構(gòu)建預(yù)測模型，指輸入特征與其對應(yīng)輸出目標(biāo)之間的映射函數(shù).在給定時間范圍[0,t]中，樣本表示為S0,t={d0,…,dt} ，其中di=(Xi,yi)是對于概念的一次觀察，Xi指特征向量，yi表示標(biāo)簽，S0,t服從一個確定分布F0,t(X,y).如p0,t(X,y)≠pt+1,∞(X,y)，則稱在t+1時刻發(fā)生概念漂移，記為pt(X,y)≠pt+1(X,y).

1.2 概念漂移的來源

依據(jù)貝葉斯學(xué)習(xí)理論，聯(lián)合概率可表示為pt(X,y)≠pt(X)pt+1(X,y)，從概率論的角度來解析產(chǎn)生概念漂移原因，觀察數(shù)據(jù)分布是否變化并且是否改變決策邊界，概念漂移主要有以下3個來源來觸發(fā)：

（1）虛假概念漂移（virtual concept drift）：是指輸入的數(shù)據(jù)分布pt(X)變化，但不會使pt(y/X)改變，對決策邊界無影響，即當(dāng)pt(X)≠pt+1(X)時，pt(y/X)=pt+1(y/X)，如圖1（a）所示.

（2）真實(shí)概念漂移（real concept drift）：pt(X)不變，pt(y/X)改變，影響決策邊界，為真實(shí)的概念漂移，即當(dāng)pt(X)=pt+1(X)時，pt(y/X)≠pt+1(y/X).只有真實(shí)的概念漂移才會影響決策邊界發(fā)生改變，那么之前的決策模型就會過時，如圖1（b）所示.

（3）以上2種漂移的結(jié)合：pt(X)和pt(y/X)兩者都發(fā)生了變化，即pt(X)≠pt+1(X)，pt(y/X)≠pt+1(y/X)，如圖1（c）所示.

圖1 3種觸發(fā)類型的概念漂移

1.3 概念漂移的類型

根據(jù)其形式不同可分為4種：

（1）突變型：數(shù)據(jù)分布或概念在較短的時間內(nèi)可能突然從一個概念轉(zhuǎn)向另一個不可逆又迅速的變化.對于此類概念漂移，要求模型必須有較高的數(shù)據(jù)敏感度，能夠迅速發(fā)現(xiàn)概念漂移，及時修正或更新模型，用以適應(yīng)新的數(shù)據(jù)分布或模型，如圖2（a）所示.

（2）漸進(jìn)型：一個新的概念不會突然出現(xiàn)，不停地回到原來概念.重點(diǎn)是數(shù)據(jù)分布變化發(fā)生的較為緩慢，如圖2（b）所示.

（3）增量型：增量中包含許多中間的概念，強(qiáng)調(diào)概念隨時間發(fā)生改變，如圖2（c）所示.

（4）重復(fù)型：指一個概念或是數(shù)據(jù)分布經(jīng)過一段時間后再次出現(xiàn)，如圖2（d）所示.

圖2 概念漂移的4種類型

依據(jù)概念漂移形式不同，發(fā)現(xiàn)概念漂移檢測可以從兩個方面入手：（a）（d）型中對概念漂移檢測強(qiáng)調(diào)的是發(fā)生的迅速，可以看到具體發(fā)生的時間點(diǎn)，相比之下，（b）（c）型漂移的研究強(qiáng)調(diào)發(fā)生的緩慢，不是立刻發(fā)生，是緩慢逐漸地發(fā)生.

2 概念漂移檢測

2.1 漂移檢測的一般框架

漂移檢測是指通過改變時間間隔或者識別位置變化點(diǎn)來表征和量化概念漂移的技術(shù)和機(jī)制.漂移檢測的一般過程包含4個階段［8］，如圖3所示.

圖3 漂移檢測框架

第一階段：數(shù)據(jù)檢索（Data Retrieval）.檢索數(shù)據(jù)流中的數(shù)據(jù)塊.由于單個數(shù)據(jù)實(shí)例攜帶的信息不足以推斷總體分布.因此，如何將單個數(shù)據(jù)實(shí)例組織起來以形成有意義的模式或知識，在數(shù)據(jù)流的分析任務(wù)中是至關(guān)重要的.

第二階段：數(shù)據(jù)建模（Data Modeling）.在檢索到的數(shù)據(jù)中，抽取其中蘊(yùn)含數(shù)據(jù)信息的關(guān)鍵特征，即若出現(xiàn)概念漂移，則該特征對系統(tǒng)的影響最大.此階段是可進(jìn)行選擇的，因?yàn)樗饕Q于降維或者減少樣本大小，用以實(shí)現(xiàn)在線速度和存儲要求.

第三階段：統(tǒng)計(jì)計(jì)算測試（Test Statistics Calculation）.統(tǒng)計(jì)計(jì)算值，測量差異、距離估計(jì)以及漂移量.漂移的嚴(yán)重程度被表征和量化，并為假設(shè)檢驗(yàn)給出了檢驗(yàn)統(tǒng)計(jì)前提.漂移檢測第三階段被看作是最具挑戰(zhàn)性的部分.因此，如何定義精準(zhǔn)穩(wěn)固的差異度量仍然是一個久懸不決的問題.

第四階段：假設(shè)檢驗(yàn)（Hypothesis Test）.采用特定的假設(shè)檢驗(yàn)評估在第三階段觀測到的改變是否有意義，以此證明在第三階段提出的測試統(tǒng)計(jì)量統(tǒng)計(jì)邊界可以用以確定漂移檢測精度.如果第四階段不存在，那么在第三階段獲得的測試統(tǒng)計(jì)量就沒有任何意義.

2.2 概念漂移檢測算法

依據(jù)概念漂移類型，處理概念漂移問題可從兩個方面入手：主動檢測方法如圖4（a），對于急促的分布改變，需要精確地檢測概念漂移是否發(fā)生以及發(fā)生的具體時間點(diǎn)，并且迅速作出判斷，重點(diǎn)強(qiáng)調(diào)數(shù)據(jù)分布是否發(fā)生變化，主動檢測方法主要有基于數(shù)據(jù)分布、基于窗口，以及假設(shè)檢驗(yàn)的方法.被動適應(yīng)方法也叫自適應(yīng)方法如圖4（b），不關(guān)注輸入數(shù)據(jù)分布如何改變，不斷更新分類器來適應(yīng)數(shù)據(jù)分布的變化，主要有基于模型、決策樹和集成的方法.

圖4 主動檢測方法與被動適應(yīng)方法

2.3 主動檢測方法

2.3.1 基于數(shù)據(jù)分布的概念漂移檢測

在現(xiàn)實(shí)的環(huán)境中，數(shù)據(jù)并不是靜止不變的，而是通過數(shù)據(jù)流的形式到達(dá)，數(shù)據(jù)是隨著時間產(chǎn)生的，隨著時間的變化它隱含的概率分布也可能會改變.基于數(shù)據(jù)分布概念漂移檢測算法的核心是通過計(jì)算樣本集之間概率分布的距離是否超出閾值來判斷概念漂移是否發(fā)生.其主要是依據(jù)觀察數(shù)據(jù)集自身統(tǒng)計(jì)信息來發(fā)現(xiàn)數(shù)據(jù)分布的變化，如圖5所示，主要原理是根據(jù)檢測的數(shù)據(jù)信息分布判斷是否發(fā)生變化，如變化就發(fā)生概念漂移，修正或更新模型.這類算法使用距離函數(shù)或度量來表征和量化新數(shù)據(jù)和歷史數(shù)據(jù)分布之間的差異.如果差異性在統(tǒng)計(jì)上有顯著不同，系統(tǒng)將觸發(fā)學(xué)習(xí)模型更新過程.

圖5 基于數(shù)據(jù)分布的概念檢測

Kifer提出了數(shù)據(jù)流中變化檢測的第一個形式化處理方法［9］，該算法是數(shù)據(jù)流變化檢測表征和量化邁出的第一步.文獻(xiàn)中假設(shè)數(shù)據(jù)點(diǎn)是由某種潛在概率分布按順序獨(dú)立生成的，不對生成的分布做任何假設(shè).目標(biāo)是檢測這種分布何時發(fā)生改變，并量化和描述這種變化.文獻(xiàn)將變化檢測算法建立在一個雙窗口范式之上.算法將某些“參考窗口”中的數(shù)據(jù)與當(dāng)前窗口中的數(shù)據(jù)進(jìn)行比較.這兩個窗口都包含了固定數(shù)量的連續(xù)數(shù)據(jù)點(diǎn).當(dāng)前窗口隨每個傳入數(shù)據(jù)點(diǎn)向前滑動，每當(dāng)檢測到更改時，將更新參考窗口.并且引入一種新的距離度量，該度量是針對尋找分布變化而定制的，同時提供了小樣本量強(qiáng)統(tǒng)計(jì)保證.該算法實(shí)際上是并行運(yùn)行k個獨(dú)立的算法，每個參數(shù)都包含在一個三維數(shù)組中(m1,i,m2,i,αi)算法需要一個函數(shù)d，它測量2個樣本之間的差異，以及一組三元組{(m1,1,m2,2,α1),...,(m1,k,m2,k,αk)}，m1,i和m2,i是窗口(Xi,Yi)的大小.窗口Xi是一個“界標(biāo)”窗口，它包含在上次檢測到更改后數(shù)據(jù)流的第一個m1,i點(diǎn).每個窗口Yi都是一個滑動窗口，其中包含數(shù)據(jù)流中最新的m2,i項(xiàng).在檢測到變化后，它立即控制m2,i滑動到窗口Xi.每當(dāng)數(shù)據(jù)流中出現(xiàn)新數(shù)據(jù)時，就會向前滑動窗口.在每次這樣的更新后，檢查d(Xi,Yi＞αi).當(dāng)距離大于αi時，報告一個更改，然后重復(fù)整個過程，Xi包含第一個m1,i及更改后的點(diǎn).

Bu、Cesare等人提出了一種新的概率密度函數(shù)自由變化檢測測試（LSDD-CDT）［10］，該測試基于最小二乘密度差估計(jì)方法（LSDD），并在線操作多維輸入.該測試不需要任何關(guān)于底層數(shù)據(jù)分布的假設(shè)，并且能夠采用儲層采樣機(jī)制進(jìn)行配置后立即運(yùn)行.一旦應(yīng)用程序設(shè)計(jì)器設(shè)置了誤報率，將自動導(dǎo)出檢測更改請求的閾值.

2.3.2 基于窗口的概念漂移檢測算法

基于流式數(shù)據(jù)的特點(diǎn)，在概念漂移檢測中也廣泛采用窗口機(jī)制.隨著數(shù)據(jù)到來，窗口不斷滑動，就可以完成不斷處理數(shù)據(jù)流中一個區(qū)間的數(shù)據(jù)，此區(qū)間包括數(shù)據(jù)流中最新數(shù)據(jù)的信息.窗口的主要功能有：（1）通過統(tǒng)計(jì)不同子窗口的數(shù)據(jù)信息用以檢測概念是否發(fā)生變化；（2）決定哪些實(shí)例需要“遺忘”，以此來根據(jù)最新的訓(xùn)練實(shí)例更新統(tǒng)計(jì)信息；（3）當(dāng)數(shù)據(jù)流中概念發(fā)生改變時，可以采用窗口中的數(shù)據(jù)信息，以及時對模型作出修正或更新.基于窗口機(jī)制的概念漂移檢測方法大概可分為3種：界標(biāo)窗口（Landmark Window）、滑動窗口（Sliding Window）和自適應(yīng)窗口（Adaptive Window）.

在界標(biāo)窗口模型中，有2個端點(diǎn)，起始端點(diǎn)也稱“界標(biāo)”是固定不動的，隨著數(shù)據(jù)流新實(shí)例的到來，終點(diǎn)不斷向前滑動，如圖6（a）所示.隨著數(shù)據(jù)流的不斷涌入窗口，使得窗口的規(guī)模不斷增加，由此可見界標(biāo)窗口內(nèi)保存了較為完整的數(shù)據(jù)信息，每當(dāng)一個新的界標(biāo)到達(dá)時，清除前一個數(shù)據(jù)塊中的所有實(shí)例，再以新的數(shù)據(jù)信息來訓(xùn)練新的模型，該模型可以很好地適應(yīng)漸進(jìn)式概念漂移.DDM、EDDM在第一階段都是基于界標(biāo)窗口機(jī)制實(shí)現(xiàn)的［11-12］.

滑動窗口模型也含有起點(diǎn)和終點(diǎn)2個端點(diǎn)，與界標(biāo)窗口模型有所不同，滑動窗口模型起點(diǎn)和終點(diǎn)2個端點(diǎn)同時不斷向前移動，如圖6（b）所示.滑動窗口不斷地用新涌入的數(shù)據(jù)信息來替換已經(jīng)過時的歷史數(shù)據(jù)，采用“先進(jìn)先出”的策略，用以不斷地消除歷史數(shù)據(jù)對模型的影響.滑動窗口采用“遺忘”機(jī)制.郭虎升等人提出的基于時序窗口的概念漂移類別檢測（concept drift class detection based on time window，CD-TW）方法和上文中基于數(shù)據(jù)分布的算法都是基于滑動窗口機(jī)制的［13］，它們均采用2個滑動窗口，在新的滑動數(shù)據(jù)窗口滑動時，歷史時間窗口固定.因此，在使用滑動窗口訓(xùn)練數(shù)據(jù)建立模型時，選擇合適的窗口大小是決定模型性能好壞的關(guān)鍵.若窗口設(shè)置太小，模型雖然可以很快地進(jìn)行反應(yīng)，但可能會在概念或數(shù)據(jù)分布緩慢變化時使得模型預(yù)測準(zhǔn)確率降低，甚至可能會導(dǎo)致過擬合（Overfitting）.但如若選擇過大的窗口尺寸，雖然在一定程度上會提升在概念或數(shù)據(jù)分布緩慢變化時的預(yù)測準(zhǔn)確率，但可能會由于同一窗口內(nèi)同時包含的概念太多，從而使得無法迅速響應(yīng)概念漂移.因此，在數(shù)據(jù)流不斷發(fā)生改變的環(huán)境中，窗口的大小應(yīng)該伴隨時間和數(shù)據(jù)分布的改變而進(jìn)行自適應(yīng)改變，由此發(fā)展出自適應(yīng)窗口的概念.

自適應(yīng)窗口模型是隨著數(shù)據(jù)流中概念或者數(shù)據(jù)分布發(fā)生變化時，不斷改變窗口的大小，如圖6（c）所示.代表算法是Bifet 提出的自適應(yīng)滑動窗口算法（ADaptive sliding WINdow，ADWIN）［14］，在初始化時，算法會首先確定一個大窗口W，通過比較2個子窗口W0、W1中的統(tǒng)計(jì)值即均值、方差等的差異是否大于某一閾值來判斷是否發(fā)生概念漂移.當(dāng)未發(fā)生概念漂移時，數(shù)據(jù)流的分布未發(fā)生變化，窗口大小也不發(fā)生改變；當(dāng)發(fā)生概念漂移時，確定窗口內(nèi)數(shù)據(jù)分布已經(jīng)發(fā)生改變，窗口縮小至W0、W1中較小的窗口.

圖6 基于窗口機(jī)制圖

另一典型算法是等概率檢測統(tǒng)計(jì)測試.等概率檢測（STEPD）統(tǒng)計(jì)測試是用相等比例的統(tǒng)計(jì)檢驗(yàn)，通過比較最近的時間窗口和總體時間窗口來檢測錯誤率的變化［15］.系統(tǒng)中有2個時間窗口，如圖7所示.新窗口的大小必須由用戶定義.通過公式（1）計(jì)算以下統(tǒng)計(jì)數(shù)據(jù)，比較其值與標(biāo)準(zhǔn)正態(tài)分布的百分比，得到觀察到的顯著性水平.

圖7 等概率檢測統(tǒng)計(jì)測試

其中，r0表示除了最近的W窗口之外的數(shù)據(jù)在所有的例子中正確分類的數(shù)量，n0表示總體時間窗口，rr是W=nr示例中的正確分類數(shù)，如果p，小于顯著性水平，即概念漂移已經(jīng)被發(fā)現(xiàn).STEPD算法可以很容易地計(jì)算出警告閾值和漂移閾值.Tin Mar Myint等人［16］也提出了一種基于自適應(yīng)加窗方法的精度更新集成算法（A-AUE2），該方法使用Brier-Skill分?jǐn)?shù)作為突變和漸變檢測器.此外，采用基于K-最近鄰（KNN）的噪聲濾波方法來消除每個自適應(yīng)窗口中的噪聲樣本，以提高集成學(xué)習(xí)方法的有效性.

2.3.3 基于假設(shè)檢驗(yàn)的概念漂移檢測算法

除了以上方法外，近年來也出現(xiàn)了一種新的漂移檢測方法——多假設(shè)檢驗(yàn)漂移檢測方法，多假設(shè)檢驗(yàn)漂移檢測方法的新穎之處在于它們使用多個假設(shè)檢驗(yàn)以不同的方式檢測概念漂移.這類算法可分為并行多重假設(shè)檢驗(yàn)和分層多假設(shè)檢驗(yàn).

（1）并行多重假設(shè)檢驗(yàn)

Just-In-Time 自適應(yīng)分類器（JIT）是第一個設(shè)置多個漂移檢測假設(shè)的算法［17］.JIT 的核心思想是擴(kuò)展CUSUM圖表，即基于計(jì)算智能的CUSUM測試（CI-CUSUM），用來檢測學(xué)習(xí)系統(tǒng)感興趣特征的平均變化.

另一種并行多假設(shè)漂移檢測算法是基于信息值和Jaccard相似性（IV-Jac）的三層漂移檢測［18］.IV-Jac的目標(biāo)是分別解決標(biāo)簽漂移第一層、特征空間漂移第二層和決策邊界漂移第三層.算法從可用數(shù)據(jù)中提取權(quán)重（WoE）和信息值（IV），然后通過測量特征值對標(biāo)簽的貢獻(xiàn)來檢測從中提取的WoE和IV之間是否存在顯著變化.

（2）分層多假設(shè)檢驗(yàn)

分層漂移檢測是一個新興的漂移檢測類別，具有多個驗(yàn)證模式.該類別中的算法通常使用現(xiàn)有的方法，稱為檢測層用于漂移檢測，驗(yàn)證層應(yīng)用額外的假設(shè)檢驗(yàn)，以分層的方式對第二次檢測到的漂移進(jìn)行驗(yàn)證.

層次變化檢測測試（HCDTs）［19］第一次嘗試使用層次結(jié)構(gòu)來解決概念漂移問題.該檢測層可以是任何現(xiàn)有的漂移延遲率較低、計(jì)算負(fù)擔(dān)較低的漂移檢測方法.驗(yàn)證層將根據(jù)檢測層返回的結(jié)果來激活和停用驗(yàn)證層.文獻(xiàn)給出了設(shè)計(jì)驗(yàn)證層的2種策略：1）通過最大化似然來估計(jì)測試統(tǒng)計(jì)量的分布；2）適應(yīng)現(xiàn)有的假設(shè)檢驗(yàn)方案，如KS檢驗(yàn)或Cramer-VonMises檢驗(yàn).

分層線性四速率Hierarchical Linear Four Rates（HLFR）是最近提出的另一種分層漂移檢測算法［20］.將漂移檢測算法LFR（Linear Four Rates）作為檢測層，一旦檢測層確認(rèn)了漂移，驗(yàn)證層將被觸發(fā).HLFR的驗(yàn)證層只是有序序列測試分割上的0-1損失函數(shù)，表示為E.如果估計(jì)的0-1損失函數(shù)超過預(yù)定義的閾值，驗(yàn)證層將確認(rèn)漂移并向?qū)W習(xí)系統(tǒng)報告，以觸發(fā)模型升級過程.

2.4 被動適應(yīng)方法

2.4.1 基于模型的概念漂移檢測

基于模型的概念檢測主要是根據(jù)模型輸出特征的改變來量化漂移，其主要原理是不關(guān)注數(shù)據(jù)，直接更新模型，如圖8所示，主要代表是基于分類錯誤率的概念漂移檢測算法.

圖8 基于模型的概念漂移檢測

基于分類錯誤率，如若概念漂移發(fā)生，數(shù)據(jù)分布會發(fā)生變化，使得模型性能降低.因此模型性能的下降成為衡量概念漂移發(fā)生的關(guān)鍵標(biāo)志.基于分類錯誤率的漂移檢測算法是概念漂移檢測中最主要的算法類別.這些算法的關(guān)鍵是觀察基本分類器在線錯誤率的變化.如果可以證明錯誤率的增加或減少具有統(tǒng)計(jì)學(xué)意義，則將觸發(fā)升級過程或者報告漂移.

漂移檢測法Drift Detection Method（DDM）是第一個定義概念漂移檢測警告級別和漂移級別的算法.當(dāng)一個新的數(shù)據(jù)實(shí)例可以用來評估時，DDM檢測界標(biāo)時間窗口內(nèi)的總體在線錯誤率是否顯著增加.DDM設(shè)置2個錯誤率閥值，一個是warning，另一個是drift.當(dāng)樣本數(shù)據(jù)中輸入第w個數(shù)據(jù)時，如果觀察到錯誤率的變化達(dá)到了warning值時，說明樣本概率分布有改變的預(yù)兆，DDM開始建立一個新的學(xué)習(xí)器，同時使用舊的學(xué)習(xí)器進(jìn)行預(yù)測，如圖9所示.如果繼續(xù)輸入的數(shù)據(jù)沒有降低錯誤率，在第d個數(shù)據(jù)輸入時錯誤率達(dá)到了drift值，則樣本概率分布發(fā)生確定變化，舊學(xué)習(xí)器將被新學(xué)習(xí)器取代，以完成進(jìn)一步的預(yù)測任務(wù).為了獲得在線錯誤率，DDM需要一個分類器來進(jìn)行預(yù)測.這個過程將訓(xùn)練數(shù)據(jù)轉(zhuǎn)換為學(xué)習(xí)模型，該模型被認(rèn)為是第二階段（數(shù)據(jù)建模）.第三階段的測試統(tǒng)計(jì)構(gòu)成在線錯誤率.第四階段假設(shè)檢驗(yàn)估計(jì)在線錯誤率的分布.雖然在突然變化的類型中，DDM算法有很好的表現(xiàn)，但是當(dāng)遇到變得非常緩慢的漸變時，算法在檢測概念漂移上就變得有困難.在這種情況下，樣本會被存儲得非常久，漂移將會花太多的時間來觸發(fā)，導(dǎo)致樣本存儲空間會超出界限.

圖9 DDM算法

Baena-Garc M 等人在DDM 基礎(chǔ)上提出了早期漂移檢測方法（EDDM），EDDM（Early Drift detection method）依據(jù)DDM算法進(jìn)行優(yōu)化提升，基本思想是考慮2個錯誤分類的變化率，而不只是考慮錯誤率.該方法用于提升緩慢漸變概念漂移條件下的檢測精度，同時在突然漂移的條件下也有很好的表現(xiàn).當(dāng)算法學(xué)習(xí)時，它會提高其預(yù)測結(jié)果精度，而且2個錯誤之間的距離會變大.算法計(jì)算2個錯誤的概率和其標(biāo)準(zhǔn)差之間的距離.在達(dá)到最大值時，算法會存儲和的值.因此，值就表示錯誤距離分布最大值的點(diǎn).在到達(dá)該點(diǎn)時，就會建立一個新的模型，新的模型能夠很好地估計(jì)數(shù)據(jù)集中當(dāng)前概念的分布.文獻(xiàn)中定義2個閾值：（1）warning.當(dāng)值達(dá)到該warning時，訓(xùn)練樣本被預(yù)先存儲到內(nèi)存中，以防止樣本概率分布可能發(fā)生變化，然后報告一個警告.（2）drift：當(dāng)達(dá)到這個drift時，就認(rèn)為真正的概念漂移已經(jīng)發(fā)生了，原來的模型就會被一個新的模型取代，新模型是用之前在觸發(fā)warning時存儲的樣本重新訓(xùn)練出來的，和的值也會被重置.當(dāng)實(shí)際值與最大值之間接近度上升超過warning時，存儲的樣本會被移出，檢測方法會回歸正常.EDDM方法在面對緩慢的漸變的概念漂移情況非常有效.但對于噪聲很大的情況中，該算法表現(xiàn)卻不是很好.

2.4.2 基于決策樹的概念漂移檢測方法

Hulten 等人提出了概念自適應(yīng)的快速決策樹CVFDT（Concept adaptive VFDT）算法［21］.該算法在基于VFDT算法的基礎(chǔ)上做了一個提升，算法集成了固定大小的滑動窗口，使其能夠檢測流式數(shù)據(jù)中概念漂移的問題，并且具有較高的分類精度和迅速響應(yīng)的優(yōu)點(diǎn).算法的核心思想是在VFDT算法上加入滑動窗口，不斷更新決策樹.假定W為窗口的大小，在任意時間點(diǎn)n，滑動窗口的查詢范圍表示為{max(0,n-w+1)}.以當(dāng)前流入數(shù)據(jù)建立臨時子樹，然后再用新流入的數(shù)據(jù)不斷改進(jìn)建好的決策樹.因此CVFDT處理概念漂移問題效果很好.但在檢測舊的概念時，CVFDT算法的效率較低.其次，CVFDT算法也不能主動檢測概念漂移的發(fā)生.因此在此基礎(chǔ)上CVFDT 出現(xiàn)了一系列的延伸算法.Li 等人提出了概念漂移隨機(jī)決策樹（CDRDT）算法［22］，該算法使用隨機(jī)決策樹的集成模型來區(qū)別不同類型的概念漂移與噪聲數(shù)據(jù)流，使用可以變化的小數(shù)據(jù)塊來逐步生成隨機(jī)決策樹，同時還引入了Hoffding 不等式和統(tǒng)計(jì)控制原理用以檢測不同類型的概念漂移和噪聲數(shù)據(jù)流，實(shí)驗(yàn)驗(yàn)證了CDRDT算法可高效地檢測來自噪音數(shù)據(jù)流中的概念漂移.針對非正態(tài)分布類型數(shù)據(jù)流特性，張劍等人提出了基于Hoeffding不等式的自適應(yīng)分級滑動窗口決策樹（AGSW-DT）算法［23］，該算法檢測概念漂移依據(jù)節(jié)點(diǎn)信息增益率，不斷調(diào)整各個窗口大小，以此完成對不同類型概念漂移的自適應(yīng)分類和決策樹更新.

2.4.3 基于集成的概念漂移檢測算法

在概念漂移檢測中，單個的分類器已經(jīng)不能夠適用于復(fù)雜可變的流式數(shù)據(jù)，將多個基分類器組合起來形成集成分類器比單分類器算法效果更好.因此出現(xiàn)了一種新的集成方法來處理概念漂移問題.集成算法根據(jù)其處理數(shù)據(jù)流的輸入形式可以分為2大類：基于數(shù)據(jù)塊的集成方式和在線集成方式.

（1）基于數(shù)據(jù)塊的集成概念漂移檢測

基于數(shù)據(jù)塊的集成分類方式是不斷地在最新數(shù)據(jù)塊上訓(xùn)練并產(chǎn)生稱為候選分類器的基分類器，添加到集成分類器中用以代替性能最差的分類器，最終集成的預(yù)測結(jié)果采用加權(quán)投票等方式，以此應(yīng)對流式數(shù)據(jù)分布變化的特性.

W Nick Street等人提出利用集成方法解決概念漂移問題的SEA算法［24］，該算法利用豐富的數(shù)據(jù)，在連續(xù)的數(shù)據(jù)塊上建立了獨(dú)立的分類器，使用啟發(fā)式替換策略將這些分類器組合成一個固定大小的集成.該算法是一個大規(guī)模的快速算法，它的分類是建立在所有數(shù)據(jù)上的單一決策樹，需要具有恒定的內(nèi)存，并迅速檢測到概念漂移.該算法中，相對較小的數(shù)據(jù)子集構(gòu)建成單個分類器，順序按塊讀取.組件分類器被組合成一個固定大小的集合，若集成滿了，只有當(dāng)新的分類器滿足一些標(biāo)準(zhǔn)的時候，它們才能根據(jù)其估計(jì)的能力來提高集成的性能.因此，現(xiàn)有的分類器必須被刪除，來保持集成的恒定大小.它提供了一個自然的機(jī)制來估計(jì)模型在任何給定階段的泛化精度.該方法易于實(shí)現(xiàn)，而且獨(dú)立于底層分類器.

Haixun Wan 等人提出AWE（Accuracy Weighted Ensemble）算法對SEA 進(jìn)行改進(jìn)［25］，基分類器被賦予權(quán)重，根據(jù)基分類器對當(dāng)前數(shù)據(jù)塊的準(zhǔn)確率進(jìn)行加權(quán)，權(quán)值大的代替權(quán)值小的基分類器進(jìn)行模型更新，最后各弱分類器的預(yù)測結(jié)果通過加權(quán)投票的方式進(jìn)行整合.首先，計(jì)算基分類器Ck在最新數(shù)據(jù)塊bi上的誤差率：

其中，p(y)表示類別y的后驗(yàn)概率.最后，計(jì)算權(quán)值：

式中，ω(Ck)表示權(quán)值.數(shù)據(jù)塊大小對性能影響很大，并且該算法也不能很好地適應(yīng)突變式概念漂移.

在AWE算法弱分類器權(quán)重計(jì)算方式的基礎(chǔ)上，Dariusz Brzezi nski和JerzyStefanowski提出了AUE（Accuracy Updated Ensemble）算法［26］，與AWE 算法不同的是基分類器權(quán)重的計(jì)算方式不同.AUE 算法并不刪除舊基分類器，而是每次從全部基分類器中選出最好的k個組成集成分類器.Dariusz Brzezinski 和Jerzy Stefanowski在AUE的基礎(chǔ)上又提出了AUE2集成算法［27］，使用VFDT作為基分類器，在到達(dá)新數(shù)據(jù)塊后，首先AUE2基分類器的權(quán)重被更新，其次用新基分類器替換準(zhǔn)確率最低的舊基分類器，最終將所有舊基分類器進(jìn)行增量訓(xùn)練.

（2）基于在線集成的概念漂移檢測

基于在線集成的概念漂移檢測是在t時刻根據(jù)已獲得的實(shí)例序列建立分類器，并對新到的實(shí)例進(jìn)行測試，按照分類結(jié)果來修正已有分類器，當(dāng)分類器完成更新后，對下一個接收到的實(shí)例實(shí)施分類.如此循環(huán)不斷進(jìn)行下去.與基于數(shù)據(jù)塊的集成概念漂移檢測方法相比，在線集成每次只檢測單個實(shí)例.因此這種方式能及時應(yīng)對突變式概念漂移，比創(chuàng)建一個新的模型付出的代價要小得多.

WMA算法是最先被提出的在線集成分類算法［28］，它組合子分類器的預(yù)測值，在子分類器出現(xiàn)錯誤預(yù)測時，該子分類器的權(quán)重就被更新.最終，依據(jù)組件權(quán)重對樣本的類型投票表決.另一個應(yīng)用較為廣泛的在線集成分類算法是Online Bagging［29］，該算法是基于傳統(tǒng)的集成方法Bagging 算法的一個延展.與Bagging 算法采用有放回隨機(jī)抽樣獲得訓(xùn)練子集有所不同，它采用增量式分類器作為組件，并通過修改輸入樣本集的分布使得各個子分類器產(chǎn)生區(qū)別，從而適應(yīng)概念漂移.

另一種是康月波提出的基于漂移檢測的在線集成分類算法［30］.算法使用Hoeffding Adaptive Tree構(gòu)建基分類器，每個節(jié)點(diǎn)上多了一棵訓(xùn)練好的替代子樹.DDM檢測器被嵌入到集成模型中，DDM對新的數(shù)據(jù)塊進(jìn)行漂移檢測.如果檢測出概念漂移，就在該樣本處將數(shù)據(jù)塊斷開；如果沒有檢測出概念漂移，就只用最新數(shù)據(jù)塊更新原有基分類器的權(quán)重，新的模型不再被構(gòu)建，有效地降低了時間成本.

3 總結(jié)與展望

本文描述了概念漂移的定義、來源、類型，概念漂移檢測的一般框架，從主動檢測和被動適應(yīng)兩方面分別介紹了基于不同類型的概念漂移檢測方法，分析了不同研究方法的適用場景以及優(yōu)缺點(diǎn).隨著大數(shù)據(jù)時代到來，人工智能飛速發(fā)展，從現(xiàn)有研究可以看出，概念漂移問題已經(jīng)引起了學(xué)術(shù)界的廣泛關(guān)注，也有了代表性的研究成果，但仍然存在如下幾個方面的研究挑戰(zhàn)：

1）現(xiàn)在概念漂移檢測算法大部分都是以通過檢測分類器性能或數(shù)據(jù)流的特征分布來確定數(shù)據(jù)流的穩(wěn)定性，當(dāng)判斷發(fā)生概念漂移時觸發(fā)概念漂移處理機(jī)制來適應(yīng)新環(huán)境的主動檢測方法為主，主動檢測方法通常具有更好的概念漂移適應(yīng)能力，但也往往具有更高的時間和空間復(fù)雜度.因此通過不斷對數(shù)據(jù)或者模型進(jìn)行更新以適應(yīng)新環(huán)境的被動適應(yīng)方法還有待進(jìn)一步研究.

2）流數(shù)據(jù)不同于靜態(tài)數(shù)據(jù)，無法實(shí)現(xiàn)完整的持續(xù)存儲.因此數(shù)據(jù)標(biāo)記將是影響流數(shù)據(jù)分類的突出問題之一.概念漂移問題研究以來，算法都是以檢測單標(biāo)簽為主，對于多標(biāo)簽概念漂移問題還不能很好地適應(yīng)，在此方面還需要進(jìn)一步研究以適應(yīng)多個標(biāo)簽的概念漂移問題.

3）近年來的概念漂移算法大多都只針對突變式概念漂移或是漸變式概念漂移問題，現(xiàn)有概念漂移算法不能很好地適應(yīng)多種類型的概念漂移，如何能同時檢測出多種類型的概念漂移也是一個值得思考的問題.