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

聶秀山，林熙明

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

0 引言

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

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

1 概念漂移概述

1.1 概念漂移定義及來源

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

1.2 概念漂移的分類

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

圖1 概念漂移分類圖

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

2 概念漂移檢測算法

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

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

2.1 漂移檢測基本框架

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

圖3 概念漂移檢測基本框架圖

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

數(shù)據(jù)建模階段旨在提取數(shù)據(jù)特征，特別是提取數(shù)據(jù)漂移時對系統(tǒng)影響最大的特征進(jìn)行數(shù)據(jù)建模。這一階段是可省略的，因?yàn)槠渲饕婕皵?shù)據(jù)降維或減少樣本量，以滿足存儲和在線學(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)評估階段三觀察到的變化的統(tǒng)計(jì)顯著性。 通過證明第三階段提出的檢驗(yàn)統(tǒng)計(jì)量的統(tǒng)計(jì)界限確定漂移檢測的準(zhǔn)確性。

2.2 漂移檢測算法

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

2.2.1 基于錯誤率的漂移檢測

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

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

圖4 DDM 時間窗口策略圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.4 復(fù)合漂移檢測

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 展望

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

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

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