概念漂移檢測(cè)算法綜述

崔瑞華，林 玲

（伊犁師范大學(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ì)時(shí)間而發(fā)生不可預(yù)見的變化.研究概念漂移檢測(cè)，有助于提高實(shí)際生活中決策和管理模型的預(yù)知性，預(yù)測(cè)和預(yù)警模型的準(zhǔn)確度.

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

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

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

1.1 概念漂移的定義

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

（1）虛假概念漂移（virtual concept drift）：是指輸入的數(shù)據(jù)分布pt(X)變化，但不會(huì)使pt(y/X)改變，對(duì)決策邊界無影響，即當(dāng)pt(X)≠pt+1(X)時(shí)，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)時(shí)，pt(y/X)≠pt+1(y/X).只有真實(shí)的概念漂移才會(huì)影響決策邊界發(fā)生改變，那么之前的決策模型就會(huì)過時(shí)，如圖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ù)分布或概念在較短的時(shí)間內(nèi)可能突然從一個(gè)概念轉(zhuǎn)向另一個(gè)不可逆又迅速的變化.對(duì)于此類概念漂移，要求模型必須有較高的數(shù)據(jù)敏感度，能夠迅速發(fā)現(xiàn)概念漂移，及時(shí)修正或更新模型，用以適應(yīng)新的數(shù)據(jù)分布或模型，如圖2（a）所示.

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

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

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

圖2 概念漂移的4種類型

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

2 概念漂移檢測(cè)

2.1 漂移檢測(cè)的一般框架

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

圖3 漂移檢測(cè)框架

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

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

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

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

2.2 概念漂移檢測(cè)算法

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

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

2.3 主動(dòng)檢測(cè)方法

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

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

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

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

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

2.3.2 基于窗口的概念漂移檢測(cè)算法

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

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

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

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

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

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

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

其中，r0表示除了最近的W窗口之外的數(shù)據(jù)在所有的例子中正確分類的數(shù)量，n0表示總體時(shí)間窗口，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ù)作為突變和漸變檢測(cè)器.此外，采用基于K-最近鄰（KNN）的噪聲濾波方法來消除每個(gè)自適應(yīng)窗口中的噪聲樣本，以提高集成學(xué)習(xí)方法的有效性.

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

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

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

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

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

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

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

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

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

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

2.4.1 基于模型的概念漂移檢測(cè)

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

圖8 基于模型的概念漂移檢測(cè)

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

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

圖9 DDM算法

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

2.4.2 基于決策樹的概念漂移檢測(cè)方法

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

2.4.3 基于集成的概念漂移檢測(cè)算法

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

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

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

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

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

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

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

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

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

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

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

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

3 總結(jié)與展望

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

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

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

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