流數(shù)據(jù)概念漂移檢測(cè)研究進(jìn)展

聶秀山，林熙明

(山東建筑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東濟(jì)南 250101)

0 引言

流數(shù)據(jù)(Data Stream)是大量快速連續(xù)傳輸?shù)捻樞驍?shù)據(jù)序列，是一個(gè)隨時(shí)間延續(xù)而無限增長(zhǎng)的動(dòng)態(tài)數(shù)據(jù)集，且數(shù)據(jù)類型和數(shù)據(jù)的分布是不確定的。 在現(xiàn)今的大數(shù)據(jù)時(shí)代，網(wǎng)絡(luò)監(jiān)控、氣象、工業(yè)流程、交通、金融等領(lǐng)域都會(huì)產(chǎn)生大量的流數(shù)據(jù)。 在日常生活中，隨著社交網(wǎng)絡(luò)及短視頻平臺(tái)的普及，網(wǎng)絡(luò)聊天、網(wǎng)上購(gòu)物、視頻評(píng)論等[1]也產(chǎn)生了大量的流數(shù)據(jù)。 政府機(jī)構(gòu)和企業(yè)單位通常需要依據(jù)流數(shù)據(jù)做出各種預(yù)測(cè)和決策[2]，因此對(duì)流數(shù)據(jù)的挖掘和分析就顯得非常重要。 但是，流數(shù)據(jù)的統(tǒng)計(jì)關(guān)系會(huì)隨著時(shí)間的變化而隨機(jī)改變，且很難預(yù)測(cè)，這種變化稱為概念漂移。 其會(huì)以改變類分布、出現(xiàn)新特征等多種方式影響流數(shù)據(jù)的屬性[3]，降低各種基于流數(shù)據(jù)的管理和決策系統(tǒng)的效率和準(zhǔn)確度。

概念漂移通常發(fā)生在數(shù)據(jù)預(yù)測(cè)和決策模型中，離線(Offline)訓(xùn)練好的模型在面對(duì)在線(Online)流數(shù)據(jù)時(shí)，因在線流數(shù)據(jù)的不確定變換，導(dǎo)致預(yù)測(cè)目標(biāo)變量的統(tǒng)計(jì)特性會(huì)隨時(shí)間發(fā)生不可預(yù)測(cè)的變化，進(jìn)而導(dǎo)致原有模型性能的急劇下降，此時(shí)需要訓(xùn)練新的模型重新適應(yīng)目標(biāo)新的統(tǒng)計(jì)特性。 在不斷變化的大數(shù)據(jù)環(huán)境中，如何檢測(cè)到概念漂移，并采取相應(yīng)的措施成為了一個(gè)關(guān)鍵問題。

1 概念漂移概述

1.1 概念漂移定義及來源

概念漂移是指輸出目標(biāo)的統(tǒng)計(jì)特性隨時(shí)間以任意方式隨機(jī)變化的現(xiàn)象[4]，指的是輸入數(shù)據(jù)和輸出目標(biāo)之間的關(guān)系隨時(shí)間變化的在線監(jiān)督學(xué)習(xí)場(chǎng)景。1986 年，SCHLIMMER 等[5]首次提出概念漂移后，國(guó)內(nèi)外的數(shù)據(jù)挖掘研究人員對(duì)概念漂移展開了深入研究。 如今概念漂移已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)，當(dāng)預(yù)測(cè)模型遭遇概念漂移時(shí)，需要預(yù)測(cè)模型能夠動(dòng)態(tài)調(diào)整，以便對(duì)概念漂移做出適當(dāng)?shù)姆磻?yīng)[6]。

1.2 概念漂移的分類

概念漂移常見的一個(gè)分類標(biāo)準(zhǔn)是概念變換的速度。 當(dāng)概念之間的變化是突然或迅速時(shí)，稱之為突變；當(dāng)從一個(gè)概念到另一個(gè)概念的轉(zhuǎn)變?cè)诙鄠€(gè)實(shí)例中發(fā)生時(shí)，稱之為漸變[10]。 根據(jù)概念變換的速度，概念漂移分類如圖1 所示，可以分為突發(fā)式漂移、漸進(jìn)式漂移、增量式漂移和復(fù)發(fā)式漂移。 由圖1 可知，突發(fā)式漂移是指在短時(shí)間內(nèi)突然發(fā)生概念間的變化；漸進(jìn)式漂移是指舊概念在一段時(shí)間內(nèi)，間隔隨機(jī)的時(shí)間逐步轉(zhuǎn)變?yōu)樾赂拍?；增量式漂移是指舊概念持續(xù)轉(zhuǎn)變?yōu)樾赂拍?；?fù)發(fā)式漂移是指舊概念轉(zhuǎn)變?yōu)樾赂拍詈螅g隔一段時(shí)間又重新變?yōu)榕f概念。 其中，突發(fā)式漂移和增量式漂移屬于突變，而漸進(jìn)式漂移屬于漸變。

圖1 概念漂移分類圖

對(duì)于突發(fā)式、漸進(jìn)式和增量式3 類概念漂移研究的重點(diǎn)是如何在概念漂移過程中使模型預(yù)測(cè)精度下降最少，并實(shí)現(xiàn)較高的恢復(fù)率，即檢測(cè)出是何種類型的漂移后，盡快訓(xùn)練出新的模型以適應(yīng)具有新的數(shù)據(jù)分布或?qū)傩缘牧鲾?shù)據(jù)。 相比之下，對(duì)復(fù)發(fā)式漂移的研究強(qiáng)調(diào)歷史概念的使用，即如何在最短的時(shí)間內(nèi)找到與之匹配的歷史概念，由于復(fù)發(fā)式的漂移可能呈現(xiàn)周期性現(xiàn)象，因此檢測(cè)出是此類漂移后，僅需在原有模型的基礎(chǔ)上增加具有周期性的漂移模型即可繼續(xù)使用。

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

當(dāng)出現(xiàn)了概念漂移現(xiàn)象時(shí)，如何檢測(cè)出概念漂移是一個(gè)重要的問題。 傳統(tǒng)的機(jī)器學(xué)習(xí)系統(tǒng)主要由模型訓(xùn)練和模型預(yù)測(cè)2 個(gè)部分組成，但在概念漂移現(xiàn)象下，系統(tǒng)新增了3 個(gè)組成模塊，即漂移檢測(cè)(是否發(fā)生漂移)、漂移理解(何時(shí)、何地、如何發(fā)生漂移)和漂移適應(yīng)(對(duì)漂移存在的反應(yīng))，如圖2 所示。其中，漂移檢測(cè)是最為重要的環(huán)節(jié)。

圖2 概念漂移下機(jī)器學(xué)習(xí)模型示意圖

2.1 漂移檢測(cè)基本框架

概念漂移檢測(cè)是指通過識(shí)別變化點(diǎn)或變化時(shí)間間隔，來表征和量化概念漂移的技術(shù)和機(jī)制。 漂移檢測(cè)一般包含數(shù)據(jù)獲取、數(shù)據(jù)建模、統(tǒng)計(jì)值計(jì)算和假設(shè)檢驗(yàn)4 個(gè)階段[2]，其框架如圖3 所示。

圖3 概念漂移檢測(cè)基本框架圖

數(shù)據(jù)獲取階段旨在從數(shù)據(jù)流中獲取到數(shù)據(jù)塊。因?yàn)閱蝹€(gè)數(shù)據(jù)實(shí)例不足以攜帶足夠的信息來判斷總體分布，所以將多個(gè)數(shù)據(jù)單例組織成數(shù)據(jù)塊在分析數(shù)據(jù)流數(shù)據(jù)分布中非常重要。

數(shù)據(jù)建模階段旨在提取數(shù)據(jù)特征，特別是提取數(shù)據(jù)漂移時(shí)對(duì)系統(tǒng)影響最大的特征進(jìn)行數(shù)據(jù)建模。這一階段是可省略的，因?yàn)槠渲饕婕皵?shù)據(jù)降維或減少樣本量，以滿足存儲(chǔ)和在線學(xué)習(xí)速度的需求。

統(tǒng)計(jì)值計(jì)算階段是相異性度量或距離估計(jì)。 其量化了漂移的嚴(yán)重性，并形成了假設(shè)檢驗(yàn)階段的檢驗(yàn)統(tǒng)計(jì)數(shù)據(jù)。

假設(shè)檢驗(yàn)階段使用特定的假設(shè)檢驗(yàn)評(píng)估階段三觀察到的變化的統(tǒng)計(jì)顯著性。 通過證明第三階段提出的檢驗(yàn)統(tǒng)計(jì)量的統(tǒng)計(jì)界限確定漂移檢測(cè)的準(zhǔn)確性。

2.2 漂移檢測(cè)算法

根據(jù)在第三階段中所使用的檢驗(yàn)統(tǒng)計(jì)量可將漂移檢測(cè)分為基于錯(cuò)誤率檢測(cè)概念漂移、基于數(shù)據(jù)分布檢測(cè)概念漂移以及多假設(shè)檢驗(yàn)檢測(cè)概念漂移3 類。

2.2.1 基于錯(cuò)誤率的漂移檢測(cè)

流數(shù)據(jù)的概念漂移可通過模型隨時(shí)間變化而產(chǎn)生的精度性能變化來監(jiān)測(cè)。 如果存在一個(gè)時(shí)間節(jié)點(diǎn)t，模型在時(shí)間t 后的預(yù)測(cè)錯(cuò)誤率明顯增加，這就說明數(shù)據(jù)流的性質(zhì)可能已經(jīng)發(fā)生了改變，即可能存在概念漂移。 如果出現(xiàn)這種情況，則需要根據(jù)發(fā)生變化后的數(shù)據(jù)重新訓(xùn)練模型。 這種根據(jù)模型預(yù)測(cè)錯(cuò)誤率的變化來檢測(cè)是否發(fā)生概念漂移的方法是概念漂移檢測(cè)最常見策略[11]。 這類方法關(guān)注在線錯(cuò)誤率的變化，一旦錯(cuò)誤率的增加或減少被驗(yàn)證是具有統(tǒng)計(jì)意義的，將觸發(fā)漂移警報(bào)。

這類算法中最具代表性的算法是漂移檢測(cè)算法(Drift Detection Method，DDM)[12]，這是第一個(gè)為概念漂移檢測(cè)定義警告級(jí)別和漂移級(jí)別的算法。 在該算法中，根據(jù)二項(xiàng)式分布，針對(duì)漂移程度定義警告級(jí)別和漂移級(jí)別。 該算法使用時(shí)間窗口采集新的數(shù)據(jù)實(shí)例，當(dāng)新的數(shù)據(jù)可用于檢測(cè)時(shí)，DDM 會(huì)計(jì)算時(shí)間窗口內(nèi)的數(shù)據(jù)樣本的錯(cuò)誤率。 如果觀察到的錯(cuò)誤率變化的置信水平達(dá)到警告級(jí)別，DDM 開始構(gòu)建新的模型，同時(shí)使用舊的模型進(jìn)行預(yù)測(cè)。 如果變化達(dá)到漂移級(jí)別，舊的模型將被新的模型替換，以進(jìn)行后續(xù)的在線預(yù)測(cè)。 DDM 算法認(rèn)為，如果數(shù)據(jù)實(shí)例的分布保持平穩(wěn)，錯(cuò)誤率應(yīng)該隨著示例數(shù)量的增加而降低；如果錯(cuò)誤率增加，DDM 則認(rèn)為數(shù)據(jù)分布發(fā)生了變化，當(dāng)前使用的學(xué)習(xí)器已經(jīng)過時(shí)。 DDM 采用的時(shí)間窗口[2]如圖4 所示，DDM 在原有的歷史數(shù)據(jù)窗口中添加下一時(shí)刻的實(shí)例，從而構(gòu)成新數(shù)據(jù)塊。

圖4 DDM 時(shí)間窗口策略圖

DDM 在突變式的概念漂移上表現(xiàn)效果較好，但對(duì)漸變式概念漂移效果不佳，且會(huì)增加內(nèi)存的開銷，后續(xù)的很多算法改進(jìn)了 DDM。 如漂移檢測(cè)方法(Early Drift Detection Method， EDDM)[13]和基 于Heoffding 不等式的漂移檢測(cè)方法(Drift Detection Method based on the Hoeffding's inequality，HDDM)[14]。 EDDM 與 DDM 類似，但其統(tǒng)計(jì)的是兩個(gè)連續(xù)分類錯(cuò)誤之間的距離，即兩個(gè)分類錯(cuò)誤之間的實(shí)例個(gè)數(shù)，而不是如DDM 一樣統(tǒng)計(jì)錯(cuò)誤率。 因此，當(dāng)概念穩(wěn)定時(shí)，錯(cuò)誤之間距離增大，當(dāng)其減小時(shí)，會(huì)觸發(fā)警告級(jí)別和漂移級(jí)別。 EDDM 比DDM 更適合檢測(cè)漸進(jìn)的概念漂移。 HDDM 則同DDM 一樣，也使用錯(cuò)誤率作為檢驗(yàn)統(tǒng)計(jì)量，HDDM 在假設(shè)檢驗(yàn)階段采用Hoeffding 不等式判斷概率差異來檢測(cè)漂移，同時(shí)需要對(duì)漸變式概念漂移和突進(jìn)式概念漂移分別設(shè)置不同閾值，增加了額外的開銷。

與DDM 等方法相比，NISHIDA 等[15]提出了等比例檢測(cè)的統(tǒng)計(jì)測(cè)試方法(Statistical Test of Equal Proportions，STEPD)，該方法通過比較最近的時(shí)間窗口和整個(gè)時(shí)間窗口來檢測(cè)錯(cuò)誤率變化，對(duì)于每個(gè)時(shí)間戳，系統(tǒng)中有歷史數(shù)據(jù)窗口和新數(shù)據(jù)窗口，新數(shù)據(jù)窗口的大小必須由用戶定義，其檢驗(yàn)統(tǒng)計(jì)量符合標(biāo)準(zhǔn)正態(tài)分布，因此可以很容易計(jì)算出警告閾值與漂移閾值。 基于STEPD 方法，研究者提出了Fisher 比例漂移檢測(cè)器(Fisher Proportions Drift Detector，F(xiàn)PDD)[10]，這是在樣本較小時(shí)使用Fisher 精確檢驗(yàn)的STEPD 的一種變體。 同樣是使用等比例檢驗(yàn)。Fisher 平方漂移檢測(cè)器 FSDD(Fisher Square Drift Detector， FSDD)與 FPDD 類似，但其檢驗(yàn)統(tǒng)計(jì)量使用卡方統(tǒng)計(jì)檢驗(yàn)來代替等比例檢驗(yàn)。 此外，F(xiàn)isher檢驗(yàn)漂移檢測(cè)器(Fisher Test Drift Detector，F(xiàn)TDD)則使用了Fisher 精確測(cè)試來檢測(cè)漂移。

與STEPD 需要用戶自定義新數(shù)據(jù)窗口大小不同，BIFET 等[16]提出了一種基于兩個(gè)時(shí)間窗口的漂移檢測(cè)算法， 稱為自適應(yīng)窗口方法(Adaptive Windowing，ADWIN)，其采用的窗口策略如圖5 所示。 在ADWIN 中，可以自動(dòng)調(diào)整比較窗口的大小。ADWIN 不要求用戶預(yù)先定義窗口大小，而只需指定窗口的總大小。 然后，其會(huì)檢查所有可能的窗口切割，并根據(jù)新舊兩個(gè)子窗口之間的變化率計(jì)算出各個(gè)子窗口的最佳大小。 當(dāng)這些子窗口的均值差大于給定閾值時(shí)，會(huì)檢測(cè)到漂移，但這種方法過于靈敏，在噪聲較多的數(shù)據(jù)流中會(huì)導(dǎo)致檢測(cè)的錯(cuò)誤率較高。此外，在概念漂移檢測(cè)方法中，由于ADWIN 能夠動(dòng)態(tài)適應(yīng)概念漂移，但其新數(shù)據(jù)窗口存在吞吐量瓶頸，因此 GRULICH 等[17]提出了并行自適應(yīng)窗口(Parallel Adaptive Windowing)技術(shù)，為每秒數(shù)百萬元組的高速數(shù)據(jù)流提供可伸縮的概念檢測(cè)。

圖5 ADWIN 自適應(yīng)時(shí)間窗口策略圖

在基于HDDM 的方法中，研究人員融合了統(tǒng)計(jì)方法與窗口，提出了使用滑動(dòng)窗口和Hoeffding 不等式進(jìn)行漂移檢測(cè)的方法(Fast Hoeffding Drift Detection Method，F(xiàn)HDDM)[18]，該方法在漂移檢測(cè)中能有效的提高數(shù)據(jù)流分類的正確率，但仍存在漂移檢測(cè)的延遲問題。 為此，徐清妍等[19]在FHDDM算法的基礎(chǔ)上，提出了基于交疊滑動(dòng)雙窗口和Hoeffding 不等式的漂移檢測(cè)方法(New Fast Hoeffding Drift Detection Method， NFHDDM )。FHDDM 為基于滑動(dòng)窗口的檢測(cè)方法，通過在預(yù)測(cè)結(jié)果上設(shè)置滑動(dòng)窗口，在滑動(dòng)窗口中根據(jù)預(yù)測(cè)結(jié)果正確與否填入“1”或“0”實(shí)現(xiàn)，NFHDDM 在此基礎(chǔ)上通過在滑動(dòng)窗口上使用四分位距來提取當(dāng)前數(shù)據(jù)流段的特征，并改進(jìn)了FHDDM 算法中Hoeffding 不等式閾值定義。 NFHDDM 不僅能夠獲得更高的漂移點(diǎn)檢測(cè)正確率，還能有效減小概念漂移檢測(cè)的延遲，從而提高流數(shù)據(jù)分類的正確率。 HUGGARD等[11]則提出了一種新的概念漂移檢測(cè)方法，稱為校準(zhǔn)漂移檢測(cè)方法(Calibrated Drift Detection Method，CDDM)。 現(xiàn)有的概念漂移檢測(cè)方法監(jiān)控模型預(yù)測(cè)的準(zhǔn)確度，并在準(zhǔn)確度度下降時(shí)預(yù)測(cè)漂移。 然而，準(zhǔn)確度可能是一個(gè)粗糙的指標(biāo)。 CDDM 通過檢測(cè)基礎(chǔ)學(xué)習(xí)器校準(zhǔn)的變化而不是準(zhǔn)確性的變化來實(shí)現(xiàn)這一點(diǎn)，將基礎(chǔ)學(xué)習(xí)器所預(yù)測(cè)的標(biāo)簽以及人工打上的真實(shí)標(biāo)簽輸入漂移檢測(cè)器，若二者標(biāo)簽一致，則表明沒有發(fā)生漂移；若二者出現(xiàn)差異，則以人工打上的真實(shí)標(biāo)簽為準(zhǔn)，對(duì)學(xué)習(xí)器進(jìn)行重新訓(xùn)練，并報(bào)告發(fā)生了漂移。 CDDM 利用校準(zhǔn)來區(qū)分真實(shí)漂移和虛擬漂移，對(duì)任何虛擬漂移常見的領(lǐng)域都是有效的，但其在計(jì)算效率上有時(shí)是比較滯后。

以上涉及的算法主要聚焦于在線學(xué)習(xí)場(chǎng)景。 近年來，也有部分算法關(guān)注離線場(chǎng)景，如鄭燦彬等[20]主要研究概念漂移的離線場(chǎng)景問題，提出一種3 階段的概念漂移檢測(cè)方法(Tsinghua Progress Concept Drift Detection，TPCDD)。 該方法將事件日志通過活動(dòng)關(guān)系抽取轉(zhuǎn)變成一個(gè)活動(dòng)關(guān)系矩陣；通過活動(dòng)關(guān)系的頻繁度分析隨時(shí)間的變化情況檢測(cè)出每個(gè)活動(dòng)關(guān)系的變更點(diǎn)，將其列為候選變更點(diǎn)；再通過聚類合并候選變更點(diǎn)得到漂移點(diǎn)。 其采用分治策略檢測(cè)出變更點(diǎn)后再整合，使得檢測(cè)準(zhǔn)確率高、誤差小，但是該方法沒有考慮到相鄰的兩個(gè)模型可能會(huì)存在時(shí)間上重疊的情況。

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

第二類漂移檢測(cè)算法是基于數(shù)據(jù)分布的漂移檢測(cè)。 這類算法使用距離函數(shù)或距離度量來量化歷史數(shù)據(jù)和新數(shù)據(jù)分布之間的差異。 如果差異被證明在統(tǒng)計(jì)上存在顯著差異，系統(tǒng)將觸發(fā)學(xué)習(xí)模型更新過程。 這些算法通常要求用戶預(yù)定義歷史時(shí)間窗口和新數(shù)據(jù)窗口。 常用的策略是兩個(gè)滑動(dòng)窗口，固定歷史時(shí)間窗口，同時(shí)滑動(dòng)新數(shù)據(jù)窗口[2]，如圖6 所示。KIFER 等[21]首先提出了這一思路，如果分布有自身的 概 率 密 度 函 數(shù)， 則 距 離 DL1＝歷史時(shí)間窗口和新數(shù)據(jù)窗口中數(shù)據(jù)分布的概率密度函數(shù)。

圖6 基于數(shù)據(jù)分布的漂移檢測(cè)雙時(shí)間窗口策略圖

儲(chǔ)光等[1]考慮文本數(shù)據(jù)流隱含的語義信息，提出一種新的概念漂移檢測(cè)算法。 通過引入潛在狄利克雷分布( Latent Dirichlet Allocation，LDA)模型計(jì)算語義相似度，并基于相鄰數(shù)據(jù)塊共有詞比例和相似主題比例，在頻繁漂移情況下實(shí)現(xiàn)有效的概念漂移檢測(cè)。

在基于滑動(dòng)窗口的方法研究中，楊帆等[22]在準(zhǔn)確率的基礎(chǔ)之上，充分考慮了數(shù)據(jù)塊間概率分布的差異性，提出了一種基于相對(duì)熵的概念漂移檢測(cè)算法，將分類器的分類準(zhǔn)確率與相對(duì)熵的值作為漂移判別基準(zhǔn)。

姜振東等[23]則提出了一種基于 Kolmogorov-Smirnov 檢驗(yàn)的概念漂移檢測(cè)方法。 根據(jù)Kolmogorov-Smirnov 檢驗(yàn)，計(jì)算當(dāng)前樣本和參考集的累積分布函數(shù)之間的差異。 如果分布 Pi≠ Pi＋1，時(shí)間i 處被稱為概念漂移點(diǎn)。 該方法使用滑動(dòng)窗口，在每次滑動(dòng)時(shí)都檢驗(yàn)基窗口以及新窗口中的樣本差異是否大于閾值來判斷是否發(fā)生了概念漂移。

郭虎升等[24]提出一種基于時(shí)序窗口的概念漂移類別檢測(cè)(Concept Drift Class Detection based on Time Window， CD-TW)方法，既可檢測(cè)漂移的節(jié)點(diǎn)，又可檢測(cè)漂移的類別。 該方法借助時(shí)序窗口機(jī)制對(duì)流數(shù)據(jù)進(jìn)行分塊學(xué)習(xí)。 通過對(duì)參考窗口進(jìn)行訓(xùn)練，得到訓(xùn)練的準(zhǔn)確率作為檢測(cè)基準(zhǔn)，然后對(duì)滑動(dòng)窗口進(jìn)行測(cè)試，得到滑動(dòng)窗口的準(zhǔn)確率。 比較滑動(dòng)窗口與訓(xùn)練窗口的準(zhǔn)確率的比值，若低于閾值則輸出為漂移節(jié)點(diǎn)。 CD-TW 可以較為準(zhǔn)確地檢測(cè)漂移節(jié)點(diǎn)，并且對(duì)不同類別的概念漂移有較強(qiáng)識(shí)別能力，對(duì)數(shù)據(jù)流挖掘提供了重要的幫助。

此外，章恒等[25]則以傳統(tǒng)網(wǎng)絡(luò)數(shù)據(jù)流為研究對(duì)象，提出了基于歷史數(shù)據(jù)分布的雙交叉窗口概念漂移檢測(cè)算法。 該方法使用滑動(dòng)窗口接受數(shù)據(jù)流，交叉部分為窗口大小的一半。 通過計(jì)算歷史數(shù)據(jù)與窗口中數(shù)據(jù)的每個(gè)元素的距離來判斷是否發(fā)生了概念漂移。 若窗口中的所有元素與歷史數(shù)據(jù)的距離小于警告級(jí)別，則不存在漂移；若存在些許元素的距離高于警告級(jí)別，而所有元素距離小于漂移級(jí)別則只發(fā)出警告信號(hào)；若存在元素的距離高于漂移級(jí)別，則直接判斷發(fā)生了漂移。 因此該方法有較高的精度以及一定的抗噪能力。

除了基于滑動(dòng)窗口的檢測(cè)方法以外，還有基于圖的檢測(cè)方法。 PAUDEL 等[26]提出了一種新的基于圖流的無監(jiān)督概念漂移檢測(cè)方法，稱為基于鑒別子圖的漂移檢測(cè)器(Discriminative Subgraph-based Drift Detector，DSDD)，該方法的基本過程是:(1) 為流中的每個(gè)圖發(fā)現(xiàn)有區(qū)別的子圖；(2) 根據(jù)判別子圖相對(duì)于圖的分布來計(jì)算窗口的熵，使用直接密度比估計(jì)，在滑動(dòng)窗口向前移動(dòng)時(shí)得到的熵值序列中檢測(cè)概念漂移。 在連續(xù)的窗口中，通過熵的變化鑒別出子圖分布的變化程度，若此變化是明顯的，則可判斷為概念漂移。 DSDD 具有較低的漂移檢測(cè)延遲以及較低的漂移錯(cuò)誤率。

LIU 等[27]則提出了一個(gè)基于等強(qiáng)度k 均值聚類空間分割直方圖的方法 ( EqualIntensity kMeans，EI-kMeans)，EI-kMeans 重點(diǎn)關(guān)注的如何有效地將多變量樣本轉(zhuǎn)換為多項(xiàng)式分布，再使用現(xiàn)有的假設(shè)檢驗(yàn)檢測(cè)漂移。 此方法能夠在保持高抗噪能力的同時(shí)有著更高的檢測(cè)靈敏度。

總體來說，已有的方法尚未能很好地應(yīng)對(duì)類別分布不平衡的多類數(shù)據(jù)流，為此，KORYCKI 等[3]提出了一種新的基于受限玻爾茲曼機(jī)(Restricted Boltzmann Machine for Multi-Class Imbalanced Data Streams， RBM-IM)的可訓(xùn)練概念漂移檢測(cè)器。 該算法能夠同時(shí)監(jiān)測(cè)多個(gè)類，并利用重構(gòu)誤差，獨(dú)立檢測(cè)每個(gè)類的變化。 RBM-IM 使用了一個(gè)不平衡的損失函數(shù)，允許其處理多個(gè)不平衡的分布。 由于其可訓(xùn)練性，能夠跟蹤流中的變化和不斷演化的類角色，以及能夠處理發(fā)生在少數(shù)類中的局部概念漂移。 這是一種新穎且可訓(xùn)練的概念漂移檢測(cè)器，具有對(duì)偏移不敏感的損失函數(shù)，能夠監(jiān)測(cè)具有動(dòng)態(tài)不平衡比率的多類不平衡數(shù)據(jù)流，是一種對(duì)偏移不敏感的生成型神經(jīng)網(wǎng)絡(luò)。 RBM-IM 存儲(chǔ)訓(xùn)練數(shù)據(jù)分布的壓縮特征，通過使用舊數(shù)據(jù)和新傳入數(shù)據(jù)的屬性間的相似性度量，便可評(píng)估數(shù)據(jù)分布是否有變化，以此來檢測(cè)概念漂移。 其對(duì)多個(gè)類別不平衡的數(shù)據(jù)分布具有穩(wěn)定性。

此外，還有針對(duì)區(qū)域或局部數(shù)據(jù)分布的漂移檢測(cè)方法。 LIU 等[28]提出了一個(gè)區(qū)域密度不等式度量，稱為局部漂移度(Local Drift Degree， LDD)測(cè)量方法，通過量化兩個(gè)不同樣本間的區(qū)域密度的差異，從而識(shí)別密度增減或穩(wěn)定的區(qū)域，以衡量在每個(gè)可疑區(qū)域的區(qū)域漂移的可能性。 LIU 等[29]提出了一種基于區(qū)域密度估計(jì)的概念漂移檢測(cè)方法，稱為基于最近鄰的密度變化識(shí)別方法(Nearest Neighborbased Density Variation Identification，NN-DVI)。 其由3 個(gè)部分組成。 第一部分是基于k 最近鄰的空間劃分模式，通過檢索關(guān)鍵信息來將不可測(cè)量的離散數(shù)據(jù)實(shí)例轉(zhuǎn)換為一組共享子空間，用于密度估計(jì)；第二部分是一個(gè)距離函數(shù)，其累積了這些子區(qū)域中的密度變化，以量化數(shù)據(jù)集之間的總體差異；第三部分是針對(duì)距離的統(tǒng)計(jì)顯著性檢驗(yàn)，通過該檢驗(yàn)可以確定概念漂移的置信區(qū)間。 NN-DVI 中應(yīng)用的距離對(duì)區(qū)域漂移非常敏感，并已被證明遵循正態(tài)分布。 因此，NN-DVI 的準(zhǔn)確性和誤報(bào)率在統(tǒng)計(jì)上得到了保證。 NN-DVI 對(duì)區(qū)域密度變化引起的概念漂移敏感度高，同時(shí)也對(duì)噪聲具有穩(wěn)定性。 CHEN 等[30]基于觀測(cè)值，提出了一種基于局部感知分布的概念漂移檢測(cè)方法，可對(duì)突發(fā)性的概念漂移進(jìn)行檢測(cè)。 該方法對(duì)潛在的概念集進(jìn)行維護(hù)，若新傳入的數(shù)據(jù)實(shí)例被錯(cuò)誤地分類，則難以區(qū)分其是一個(gè)新的概念數(shù)據(jù)實(shí)例還是一個(gè)噪聲數(shù)據(jù)實(shí)例；然而，如果在短時(shí)間內(nèi)有相對(duì)大量的數(shù)據(jù)實(shí)例被錯(cuò)誤地分類，且同時(shí)都處在同一個(gè)密集的區(qū)域中，則可以合理假設(shè)此時(shí)出現(xiàn)了新的概念，若在潛在概念集中發(fā)現(xiàn)有足夠多的相鄰點(diǎn)與錯(cuò)誤分類的實(shí)例具有相同的標(biāo)簽屬性，則可以推斷出發(fā)生了突發(fā)式概念漂移。

此外，部分方法利用已有的漂移檢測(cè)方案，將其融合訓(xùn)練出新的漂移檢測(cè)結(jié)構(gòu)。 張永等[31]提出了一種基于多層次驗(yàn)證的多標(biāo)簽數(shù)據(jù)流概念漂移檢測(cè)算法，此方法的基本過程是:(1) 利用滑動(dòng)窗口的思想，將多標(biāo)簽數(shù)據(jù)流視為一個(gè)大小相同的連續(xù)數(shù)據(jù)塊；(2) 將檢測(cè)概念漂移分為兩層進(jìn)行驗(yàn)證:第一層為檢驗(yàn)層，主要計(jì)算數(shù)據(jù)分布的變化情況，使用相應(yīng)標(biāo)簽數(shù)據(jù)質(zhì)心與區(qū)間夾角的對(duì)比來測(cè)量數(shù)據(jù)塊的差異，如果高于區(qū)間上限則直接判斷為發(fā)生了概念漂移，低于區(qū)間下限則為未發(fā)生漂移，若在區(qū)間內(nèi)發(fā)出漂移預(yù)警信息，則傳入第二層校驗(yàn)層。 在校驗(yàn)層中，使用相應(yīng)標(biāo)簽混淆矩陣之間的歐氏距離來測(cè)量差異程度，若距離大于閾值則判斷為發(fā)生了概念漂移。該方法通過兩層判斷是否發(fā)生概念漂移，并監(jiān)控?cái)?shù)據(jù)流分布的變化。 此方法顯著降低了誤報(bào)率。ZHANG 等[9]則采用分層結(jié)構(gòu)，提出了一種多變量監(jiān)督數(shù)據(jù)流的分層縮減空間檢測(cè)框架(Hierarchycal Reduced Space Detection Framework for Multivariates Supervised Data Streams，HRDS)，用于準(zhǔn)確有效地檢測(cè)多維數(shù)據(jù)流的真實(shí)漂移和虛擬漂移。 其關(guān)鍵思想是利用監(jiān)督信息中的知識(shí)來發(fā)現(xiàn)現(xiàn)有檢測(cè)方法可能無法檢測(cè)到的變化。 實(shí)現(xiàn)這一目標(biāo)的基本過程為:(1) 識(shí)別一個(gè)低維空間，該空間包含與給定分類任務(wù)的最相關(guān)的信息，即識(shí)別由訓(xùn)練樣本跨越的特征子空間，以便將輸入的多元數(shù)據(jù)樣本投影到該空間；(2) 不再監(jiān)視原始輸入樣本，而是在這個(gè)縮減的特征空間中為特定的分類任務(wù)執(zhí)行檢測(cè)，不僅監(jiān)控?cái)?shù)據(jù)流的邊緣分布，還監(jiān)控每個(gè)類的條件分布；(3) 提出了一種在每次檢測(cè)后重新配置信息量更大的再訓(xùn)練數(shù)據(jù)集的新方法，可以檢測(cè)出真實(shí)漂移和虛擬漂移，同時(shí)在高維數(shù)據(jù)流上具有較高的準(zhǔn)確性和低誤報(bào)率，并且有較低的漂移檢測(cè)延遲。

除了通過檢測(cè)特征分布來比較數(shù)據(jù)分布的方法以外，LU 等[4]提出了一種基于案例推理(Casebased Reasoning， CBR)系統(tǒng)的檢測(cè)概念漂移方法，引入了一個(gè)新的勝任力模型，通過測(cè)量勝任力而非特征分布來比較數(shù)據(jù)分布，勝任力是指當(dāng)前能夠成功解決的問題的比例，基于勝任力的概念檢測(cè)方法不需要案例分布的先驗(yàn)知識(shí)，而是通過勝任力模型估計(jì)概率分布并檢測(cè)變化，并提供檢測(cè)到的變化的可靠性的統(tǒng)計(jì)保證。 除了確定是否存在概念漂移，該方法還可以根據(jù)勝任力模型量化和描述檢測(cè)到的變化。

此外，TANHA 等[32]提出了一種數(shù)據(jù)流半監(jiān)督分類的共形預(yù)測(cè)漂移檢測(cè)框架(Conformal Prediction for Semi-Supervised Classification on Data Streams，CPSSDS)， 使用歸納共形預(yù)測(cè)方法(Inductive Conformal Prediction， ICP)識(shí)別信息量最大的數(shù)據(jù)點(diǎn)，以提高增量基礎(chǔ)學(xué)習(xí)器在每個(gè)輸入數(shù)據(jù)塊上的分類精度。 該框架使用增量分類器作為基礎(chǔ)學(xué)習(xí)器，并使用自訓(xùn)練框架來處理標(biāo)記樣本的稀缺性。該方法利用一種形式的共形預(yù)測(cè)器發(fā)現(xiàn)一組信息豐富的未標(biāo)記數(shù)據(jù)實(shí)例，并在每個(gè)訓(xùn)練過程中添加到原始訓(xùn)練集中。 在此框架下，通過比較兩個(gè)連續(xù)數(shù)據(jù)塊的共形預(yù)測(cè)輸出的分布，采用 Kolmogorov-Smirnov 檢驗(yàn)來檢測(cè)概念漂移，而不必考慮分類過程的計(jì)算困難性。 此方法提高了半監(jiān)督分類性能，且能夠檢測(cè)突進(jìn)式與漸進(jìn)式漂移，此外該方法可以改進(jìn)用以高度不平衡的數(shù)據(jù)流。

2.2.3 多假設(shè)檢驗(yàn)的漂移檢測(cè)

多假設(shè)檢驗(yàn)漂移檢測(cè)算法使用多個(gè)假設(shè)檢驗(yàn)以不同的方式檢測(cè)概念漂移[2]。 YU 等[33]提出了分層線性四速率(Hierarchical Linear Four Rates， HLFR)框架，該框架通過在在線環(huán)境中利用一組分層假設(shè)檢驗(yàn)來檢測(cè)不同數(shù)據(jù)流分布(包括不平衡數(shù)據(jù))的概念漂移，該方法還提出了一個(gè)用于概念漂移檢測(cè)的兩層分層假設(shè)測(cè)試框架。 此方法可以檢測(cè)概念漂移的所有可能的變體并且可以顯著減小誤報(bào)率，甚至在存在不平衡類標(biāo)簽的情況下也能做到這一點(diǎn)。

孫子健等[34]則提出一種面向工業(yè)過程難測(cè)參數(shù)建模的雙窗口概念漂移檢測(cè)方法。 步驟為:(1) 建立離群樣本檢測(cè)窗口及分布檢測(cè)窗口雙窗口，在離群樣本檢測(cè)窗口采用支持向量回歸獲得實(shí)時(shí)過程數(shù)據(jù)中包含的離群樣本，在分布檢測(cè)窗口計(jì)算離群與歷史樣本間的歐氏距離；(2) 使用F 檢驗(yàn)、t 檢驗(yàn)及Q 檢驗(yàn)方法，計(jì)算出樣本的漂移度指標(biāo)，若低于閾值則報(bào)告該離群樣本發(fā)生概念漂移。 該方法提升了檢測(cè)的準(zhǔn)確度，但較依賴于模型預(yù)測(cè)精度，降低了檢測(cè)效率。

2.2.4 復(fù)合漂移檢測(cè)

近年來，部分研究者將上述幾類方法組合起來，提出了復(fù)合漂移檢測(cè)算法。 張寶菊等[35]基于錯(cuò)誤率和漂移度，提出概念漂移的并行檢測(cè)機(jī)制。(1) 使用學(xué)習(xí)算法訓(xùn)練模型獲得每個(gè)數(shù)據(jù)塊的分類錯(cuò)誤率；(2) 比較預(yù)測(cè)錯(cuò)誤率，如果超出置信區(qū)間；(3) 計(jì)算基于歐氏距離的概念漂移程度，若漂移程度上升，表明數(shù)據(jù)分布很可能發(fā)生變化，則報(bào)告發(fā)生概念漂移。

由于目前的漂移檢測(cè)方法大多數(shù)集中于漂移位置的檢測(cè)，關(guān)于漂移類型識(shí)別的研究很少。 在漂移類別識(shí)別的研究中，GUO 等[36]提出了一種基于多滑動(dòng)窗口的概念漂移類型識(shí)別方法，能夠在快速檢測(cè)漂移位置的過程中有效識(shí)別概念漂移類型，準(zhǔn)確分析在線學(xué)習(xí)過程中的關(guān)鍵信息，提高流數(shù)據(jù)分析和挖掘的效率和泛化性能。 該方法基于錯(cuò)誤率及數(shù)據(jù)分布，在檢測(cè)過程中，漂移位置由單個(gè)基本滑動(dòng)窗口和單個(gè)基本靜態(tài)窗口檢測(cè)。 在增長(zhǎng)過程中，使用多個(gè)滑動(dòng)窗口來識(shí)別漂移類別，其中填充了少量漂移位置后的新數(shù)據(jù)。 在跟蹤過程中，使用復(fù)合滑動(dòng)窗口和復(fù)合靜態(tài)窗口獲得識(shí)別漂移子類別的重要信息。 漂移類型識(shí)別過程中通過檢測(cè)漂移長(zhǎng)度識(shí)別漂移類別。 而基于漂移類別，根據(jù)流數(shù)據(jù)中不同數(shù)據(jù)塊的分布之間的關(guān)系來識(shí)別漂移的子類別。 但該方法僅適用于監(jiān)督學(xué)習(xí)中，且無法準(zhǔn)確檢測(cè)增量式漂移。

2.2.5 漂移檢測(cè)方法總結(jié)

綜上所述，基于錯(cuò)誤率的漂移檢測(cè)方法在數(shù)據(jù)獲取階段時(shí)，基本采用固定初始窗口大小并隨時(shí)間滑動(dòng)以增大窗口，或自適應(yīng)劃分歷史數(shù)據(jù)及新數(shù)據(jù)窗口，在統(tǒng)計(jì)值選擇上以計(jì)算時(shí)間窗口之間數(shù)據(jù)實(shí)例的分類錯(cuò)誤率為主，能夠快速地檢測(cè)突進(jìn)式漂移或漸進(jìn)式漂移。 此外，基于錯(cuò)誤率的漂移檢測(cè)方法主要預(yù)測(cè)模型隨時(shí)間推移的性能，因此只在分類精度下降后才會(huì)檢測(cè)變化，進(jìn)而發(fā)出警報(bào)信號(hào)，而且這類漂移檢測(cè)方法通常需要全面地訪問真實(shí)標(biāo)簽，但在一些真實(shí)的場(chǎng)景中，概念標(biāo)簽并不是很容易獲得，這樣就降低了此類方法的實(shí)用性。

基于數(shù)據(jù)分布的漂移檢測(cè)方法在數(shù)據(jù)獲取階段，其歷史數(shù)據(jù)窗口與新數(shù)據(jù)窗口相互獨(dú)立，該類方法主要聚焦于使用距離函數(shù)以判斷雙窗口中的數(shù)據(jù)實(shí)例分布的相似性差異，具有較高的檢測(cè)靈敏度與穩(wěn)定性，甚至能夠識(shí)別概念漂移類型。 但是，此類方法雖然能夠檢測(cè)到輸入空間內(nèi)的漂移，但仍無法準(zhǔn)確地判斷漂移出現(xiàn)的原因是數(shù)據(jù)分布的變化還是標(biāo)簽標(biāo)記的錯(cuò)誤。

多假設(shè)檢驗(yàn)的漂移檢測(cè)方法在數(shù)據(jù)獲取階段以及所采用的統(tǒng)計(jì)值與前兩者相似，但在假設(shè)檢驗(yàn)階段使用了多個(gè)不同的假設(shè)檢驗(yàn)來檢測(cè)漂移，能夠提升檢測(cè)的準(zhǔn)確率，但損失了檢測(cè)的效率。

復(fù)合漂移檢測(cè)方法則是將上述多種方法組合起來，能夠在提升漂移檢測(cè)的精確度以及速度的同時(shí)，識(shí)別出漂移的類型。

2.3 概念漂移檢測(cè)常用的公開數(shù)據(jù)集

常用的公開真實(shí)數(shù)據(jù)集，包括帶有混合漂移的真實(shí)數(shù)據(jù)集，總結(jié)如下:

(1) Electricity[37]數(shù)據(jù)集 每30 min 從澳大利亞新南威爾士電力市場(chǎng)獲取的隨時(shí)間變化的電價(jià)樣本，樣本總數(shù)為45 312 個(gè)，每個(gè)樣本包含8 個(gè)特征和2 個(gè)類。 數(shù)據(jù)集上的每個(gè)樣本都有5 個(gè)字段，即星期幾、時(shí)間戳、新南威爾士州電力需求、維多利亞州電力需求、各州之間的計(jì)劃電力傳輸和類別標(biāo)簽。此數(shù)據(jù)集可用于短期的概念漂移檢測(cè)。

(2) CoverType[38]數(shù)據(jù)集 植被覆蓋類型數(shù)據(jù)集，其樣本總數(shù)為581 012 個(gè)，每個(gè)樣本擁有54 個(gè)特征，共有7 個(gè)類，其中54 個(gè)特征中除了前10 個(gè)為浮點(diǎn)數(shù)，其余均為One-hot 變量。

(3) Poker-Hand[38]數(shù)據(jù)集 撲克手?jǐn)?shù)據(jù)集，可用于檢測(cè)類別不平衡的概念漂移，其中包含1 025 010個(gè)樣本，每個(gè)樣本包含10 個(gè)特征和10 個(gè)類。

(4) KDD-Cup99[38]數(shù)據(jù)集 網(wǎng)絡(luò)入侵檢測(cè)數(shù)據(jù)集，可用于檢測(cè)未知類別的概念漂移，有494 021個(gè)樣本，每個(gè)樣本有41 個(gè)特征和23 個(gè)類。

(5) Spam[39]數(shù)據(jù)集 垃圾郵件數(shù)據(jù)集，主要用于漸進(jìn)式漂移檢測(cè)，有9 324 個(gè)樣本，包含了499 個(gè)特征和2 個(gè)類。

(6) NOAA Weather[40]數(shù)據(jù)集 NOAA 氣象站點(diǎn)數(shù)據(jù)集，有18 159 個(gè)樣本，每個(gè)樣本有8 個(gè)特征和2 個(gè)類。

數(shù)據(jù)集設(shè)置情況見表1。

表1 真實(shí)數(shù)據(jù)集 單位:個(gè)

此外，還列出了漂移檢測(cè)使用頻率較高的人工合成數(shù)據(jù)集。 由于數(shù)據(jù)實(shí)例是由預(yù)先定義的規(guī)則和特定參數(shù)生成的，所以合成數(shù)據(jù)集是評(píng)估不同概念漂移場(chǎng)景下學(xué)習(xí)算法性能的一個(gè)很好的選擇。 包括

(1) STAGGER[41]數(shù)據(jù)集 每個(gè)樣本有3 個(gè)特征和2 個(gè)類。 其來源為真實(shí)漂移，可檢測(cè)突發(fā)式概念漂移。

(2) Hyperplane[42-43]數(shù)據(jù)集 每個(gè)樣本有10個(gè)特征和2 個(gè)類。 其來源為真實(shí)漂移，可檢測(cè)漸進(jìn)式與增量式概念漂移。

(3) SEA[44]數(shù)據(jù)集 每個(gè)樣本有3 個(gè)特征和2個(gè)類。 其來源為真實(shí)漂移，可檢測(cè)突發(fā)式概念漂移。

(4) Circle[12]數(shù)據(jù)集 每個(gè)樣本有2 個(gè)特征和2 個(gè)類。 其來源為混合漂移，可檢測(cè)漸進(jìn)式概念漂移。

(5) Sine[12]數(shù)據(jù)集 每個(gè)樣本有2 個(gè)特征和2個(gè)類。 其來源為真實(shí)漂移，可檢測(cè)突發(fā)式概念漂移。

(6) LED[38]數(shù)據(jù)集 每個(gè)樣本有24 個(gè)特征和10 個(gè)類。 其來源為真實(shí)漂移，可用于檢測(cè)突發(fā)式概念漂移。

(7) RandomRBF[45]數(shù)據(jù)集 樣本總數(shù)、特征數(shù)、類的個(gè)數(shù)均可隨機(jī)生成。 其來源為混合漂移，可用于檢測(cè)突發(fā)式、漸進(jìn)式以及增量式概念漂移。

數(shù)據(jù)集設(shè)置情況見表2。

表2 人工合成數(shù)據(jù)集

3 展望

文章介紹了概念漂移檢測(cè)的定義、形式、分類以及現(xiàn)有研究工作，描述了現(xiàn)有概念漂移檢測(cè)算法重點(diǎn)，分析了各類方法的優(yōu)缺點(diǎn)，并介紹了對(duì)概念漂移檢測(cè)常用數(shù)據(jù)集。

現(xiàn)有的漂移檢測(cè)算法雖然能夠判斷是否發(fā)生了概念漂移，但仍不能準(zhǔn)確識(shí)別概念漂移的類型，因此該領(lǐng)域還需要加強(qiáng)對(duì)漂移類型識(shí)別的研究。 此外，漂移檢測(cè)算法還面臨著冷啟動(dòng)問題，現(xiàn)有的漂移檢測(cè)算法需要初始窗口來收集假設(shè)檢驗(yàn)的基本統(tǒng)計(jì)屬性，但在初始窗口中無法實(shí)現(xiàn)檢測(cè)策略，如果初始窗口中就存在概念漂移，這就影響了檢測(cè)的效果，因此，如何解決冷啟動(dòng)問題是概念漂移檢測(cè)的重要研究方向。

在數(shù)據(jù)集的獲取方面，由于在實(shí)際應(yīng)用中獲得數(shù)據(jù)真實(shí)標(biāo)簽的成本較高，因此無監(jiān)督或半監(jiān)督的概念漂移檢測(cè)方法也是重要的研究方向。