徐清妍，何 麗，朱泓西

天津財經(jīng)大學(xué) 理工學(xué)院，天津300222

1 引言

數(shù)據(jù)流是一組順序、大量和快速連續(xù)到達(dá)的數(shù)據(jù)序列，如何對數(shù)據(jù)流進(jìn)行準(zhǔn)確高效的分類是機(jī)器學(xué)習(xí)的研究方向之一[1]。在數(shù)據(jù)流分類過程中，當(dāng)數(shù)據(jù)的特征分布隨時間發(fā)生變化時，之前訓(xùn)練獲得的分類器可能無法適應(yīng)當(dāng)前數(shù)據(jù)的特征分布，從而導(dǎo)致無法準(zhǔn)確分類當(dāng)前數(shù)據(jù)[2]。由于數(shù)據(jù)流具有時效性，概念漂移是影響數(shù)據(jù)流分類性能的重要因素[3]。為了及時發(fā)現(xiàn)數(shù)據(jù)流中的概念漂移，需要在數(shù)據(jù)流分類過程中進(jìn)行概念漂移檢測，并在發(fā)生概念漂移后的數(shù)據(jù)上重新訓(xùn)練分類器，以提高分類器的正確率。

目前，針對數(shù)據(jù)流的概念漂移檢測方法主要是基于分類錯誤率分析和多窗口數(shù)據(jù)比對。1954 年，CUSUM和Ph算法作為概念漂移檢測的先鋒被提出[4]，這種方法通過計算觀測值檢測概念漂移。當(dāng)觀測值大于用戶定義的閾值時，使用漂移的平均值和警報的差值來判斷是否發(fā)生了概念漂移。ph 算法作為CUSUM 算法的一個變體，主要用于信號處理領(lǐng)域的變化檢測[5]。2004 年，Gama等人[6]提出了DDM算法，該算法通過分析分類器錯誤率及相應(yīng)的標(biāo)準(zhǔn)偏差來檢測數(shù)據(jù)流中的概念漂移，在突變漂移上獲得了很好的檢測效果，但是在漸變漂移上效果不佳，且內(nèi)存的使用量較大。2006年，文獻(xiàn)[7]在DDM 的基礎(chǔ)上提出了EDDM 算法，該算法通過監(jiān)視兩個連續(xù)錯誤之間的距離來檢測概念漂移，能夠有效改善漸變漂移的檢測效果。為了減少DDM算法中的內(nèi)存使用量，文獻(xiàn)[8]提出了RDDM 算法，該算法在DDM 算法的基礎(chǔ)上丟棄了之前未發(fā)生概念漂移的部分舊實(shí)例，然后重新計算檢測警告和漂移級別，能夠有效減小概念漂移的延遲。2015年，文獻(xiàn)[9]提出了HDDM算法，該算法使用Hoeffding不等式[10]進(jìn)行概念漂移檢測。HDDM算法使用Hoeffding不等式來設(shè)置窗口平均值之間差值的上限，但是，這種算法需要對突變漂移和漸變漂移分別設(shè)定不同的閾值。

目前，基于窗口的方法主要使用固定窗口來提取最近流過的數(shù)據(jù)流段特征，用滑動窗口來提取當(dāng)前數(shù)據(jù)流段的特征，并通過分析這兩個窗口數(shù)據(jù)分布的差異來判斷是否會發(fā)生概念漂移。2007年，Bifet提出了ADWIN算法，該算法使用具有可變大小的滑動窗口來檢測概念漂移，有概念漂移時，窗口尺寸減小[11]。這種方法過于靈敏，在噪聲點(diǎn)多的情況下，錯誤率較高。為改進(jìn)ADWIN存在的問題，文獻(xiàn)[12]提出了SEQDRIFT 算法，該算法使用兩個窗口來分別描述新數(shù)據(jù)和舊數(shù)據(jù)。其中，舊數(shù)據(jù)使用蓄水池采樣的方法進(jìn)行管理，即一次性從舊數(shù)據(jù)中抽取固定大小隨機(jī)樣本；新數(shù)據(jù)使用跟隨滑動窗口的方法提取最近的數(shù)據(jù)。2014 年，Huang 等人[13]利用ADWIN 算法的雙窗口思想，提出了SEED 算法。在SEED 算法中，當(dāng)兩個子窗口的統(tǒng)計量比較值大于等于漂移判定的閾值時，即判斷發(fā)生概念漂移，該方法執(zhí)行塊壓縮以消除不必要的切割點(diǎn)合并本質(zhì)相同的塊。

以上這些方法雖然能夠較好地檢測出數(shù)據(jù)流分類中的概念漂移，但是均存在一定的檢測延遲，并且對概念漂移過于敏感。當(dāng)數(shù)據(jù)流中噪聲率較大時，概念漂移的誤判率也隨之變高。在實(shí)際應(yīng)用中，快速準(zhǔn)確的檢測出概念漂移有助于提高數(shù)據(jù)流分類的正確率，但是要盡量避免噪聲點(diǎn)的影響。

2016年，文獻(xiàn)[14]融合了統(tǒng)計方法和窗口方法，提出了FHDDM 算法，該算法使用滑動窗口和Hoeffding 不等式進(jìn)行漂移點(diǎn)檢測。2018 年，文獻(xiàn)[15]在FHDDM 的基礎(chǔ)上又提出了FHDDMS算法，該算法設(shè)置一個長窗口和一個短窗口，并通過兩個窗口的疊加來檢測漂移點(diǎn)，能夠降低檢測延遲和誤判率。其中，短窗口用來應(yīng)對突變概念漂移，長窗口用于減少噪聲對漂移檢測的影響。

基于FHDDM 算法的漂移檢測方法雖然獲得了較好的效果，但仍存在漂移檢測延遲的現(xiàn)象。本文在FHDDM算法的基礎(chǔ)上，提出了基于交疊滑動雙窗口和Hoeffding不等式的漂移檢測方法（New Fast Hoeffding Drift Detection Method，NFHDDM），該方法通過在滑動窗口上使用四分位距來提取當(dāng)前數(shù)據(jù)流段的特征，并對FHDDM 算法中Hoeffding 不等式閾值定義進(jìn)行了改進(jìn)。實(shí)驗證明，本文提出的方法不僅能夠獲得更高的漂移點(diǎn)檢測正確率，還能有效減小概念漂移檢測的延遲，從而提高數(shù)據(jù)流分類正確率。

2 FHDDM的基礎(chǔ)理論

FHDDM是一種基于滑動窗口的漂移檢測方法，該算法在預(yù)測結(jié)果上設(shè)置一個滑動窗口。如果預(yù)測結(jié)果正確，則把1插入到滑動窗口當(dāng)中，否則把0插入到滑動窗口中。若t 時刻滑動窗口數(shù)據(jù)的平均值用ut表示，分類過程中滑動窗口數(shù)據(jù)的最大均值用um表示，um的調(diào)整方法如公式（1）所示：

在可能大概正確（probably approximate correct）學(xué)習(xí)模型下，分類正確率應(yīng)該隨實(shí)例數(shù)的增加而增加或穩(wěn)定，否則，發(fā)生概念漂移的可能性會變大[16]。如果um值不變且ut與um之間的差大于預(yù)設(shè)的閾值時，即判斷發(fā)生了概念漂移。

FHDDM的漂移檢測方法如公式（2）所示：

公式（2）中，εd 是FHDDM 定義的概念漂移檢測閾值，該值對漂移檢測效果具有重要的影響。FHDDM 算法使用Hoeffding不等式（3）來定義閾值εd：

3 改進(jìn)的FHDDM漂移檢測方法（NFHDDM）

3.1 NFHDDM的窗口設(shè)定

為了提取到當(dāng)前數(shù)據(jù)流段的主要特征分布，本文提出了一種基于四分位距的滑動窗口大小設(shè)置方法。四分位距（Inter Quartile Range，IQR）是離散度的一種度量方式，定義為第三個四分位數(shù)和第一個四分位數(shù)之間的差[17]。若用IQ1表示數(shù)據(jù)序列中的第一個四分位數(shù)的下標(biāo)，用IQ3表示數(shù)據(jù)序列中的第三個四分位數(shù)的下標(biāo)，則四分位距窗口數(shù)據(jù)集DIQR可用公式（5）描述：

在靜態(tài)數(shù)據(jù)分析中，通常假定數(shù)據(jù)是服從同一分布的，但是數(shù)據(jù)流數(shù)據(jù)的分布會隨著時間而變化。本文使用四分位距設(shè)定窗口，即取滑動窗口的四分之一到四分之三范圍內(nèi)的對象進(jìn)行處理。在窗口滑動過程中，選取的數(shù)據(jù)可能會把一個完整的概念斷開，繼而影響概念特征提取的完整性，最終導(dǎo)致分類器性能的下降。四分位距窗口內(nèi)數(shù)據(jù)的穩(wěn)定性說明如圖1所示。

圖1 窗口解釋圖

在圖1中，滑動窗口中的數(shù)據(jù)在一定時間后發(fā)生了概念漂移，藍(lán)色標(biāo)記點(diǎn)和紅色標(biāo)記點(diǎn)分別表示兩種概念。從圖上可以看出，極端異常值通常發(fā)生在兩個概念的交疊區(qū)域，而概念漂移一般存在于該區(qū)域中。相較于取整個滑動窗口，四分位距窗口中的數(shù)據(jù)能夠保持當(dāng)前概念的完整性，降低極端異常值對分類結(jié)果的影響，進(jìn)而提升分類器的正確率[18]。同時，因為四分位距窗口中的樣本數(shù)更小，還可以減少分類器的運(yùn)行時間。

3.2 Hoeffding不等式的改進(jìn)方法

在概念漂移檢測中，使用Hoeffding 不等式計算概念漂移檢測的閾值。在Hoeffding 不等式中，e-2nεd2中2是一個固定的敏感系數(shù)，用于控制模型對概念漂移檢測的靈敏度。但在實(shí)際應(yīng)用中，數(shù)據(jù)流通常是存在噪聲的，固定系數(shù)難以適應(yīng)不同噪聲率的數(shù)據(jù)流。為了更好地適應(yīng)不同噪聲率下的概念漂移檢測，本文在Hoeffding不等式中引入了動態(tài)系數(shù)λ，公式（6）和（7）分別描述了改進(jìn)后的Hoeffding不等式。

將λ引入到四分位距窗口的數(shù)據(jù)處理中能夠更加準(zhǔn)確快速地檢測到數(shù)據(jù)流中的概念漂移。在λ的定義中，Pmax相對穩(wěn)定，當(dāng)噪聲增大時，如公式（8）所示四分位距窗口中數(shù)據(jù)的分類正確率Pc的值會相應(yīng)下降，使得λ的值變小，導(dǎo)致公式（7）中的εd增大，從而降低概念漂移檢測的靈敏度，減少錯誤漂移點(diǎn)的檢測。反之，當(dāng)噪聲減小時，Pc的值會上升，使得λ的值增大，εd減小，達(dá)到提高概念漂移檢測靈敏度的目的。

3.3 NFHDDM算法

NFHDDM算法使用滑動窗口和四分位距窗口來檢測概念漂移。首先，NFHDDM 需要根據(jù)數(shù)據(jù)流中對象的分類結(jié)果來建立滑動窗口。NFHDDM使用的分類器依次對數(shù)據(jù)流中的每個對象進(jìn)行分類，若分類正確，分類器輸出1，否則輸出0，然后將當(dāng)前處理對象的分類結(jié)果添加到滑動窗口。當(dāng)滑動窗口中的數(shù)據(jù)個數(shù)等于滑動窗口的尺寸時，NFHDDM 根據(jù)圖1 定義的四分位距窗口，從滑動窗口中截取生成四分位距窗口，并計算Pc，更新Pmax。

若滑動窗口用W表示，四分位距窗口用W_IQR表示，Length(W)用于求窗口W中的數(shù)據(jù)元素個數(shù)，檢測到的漂移點(diǎn)的順序表用Seq_dp[]表示，NFHDDM 的具體步驟如下：

4 實(shí)驗與結(jié)果分析

為了驗證本文提出的NFHDDM 算法的有效性，分別在兩個不同類型的人工數(shù)據(jù)集和兩個真實(shí)數(shù)據(jù)集上進(jìn)行了測試，并與數(shù)據(jù)流分類研究中九個主要的概念漂移檢測算法進(jìn)行了比較。實(shí)驗環(huán)境為Windows7，2.4 GHz CPU，8 GB內(nèi)存，編程語言python3.6。

4.1 實(shí)驗設(shè)計

4.1.1 實(shí)驗數(shù)據(jù)集

考慮到概念漂移包括突變漂移和漸變漂移，實(shí)驗中使用了兩個人工數(shù)據(jù)集：存在突變漂移的SINE1數(shù)據(jù)集和存在漸變漂移的CIRCLES 數(shù)據(jù)集，以及兩個真實(shí)數(shù)據(jù)集，各個數(shù)據(jù)集的主要屬性描述如表1 所示。其中，SINE1數(shù)據(jù)集的分類函數(shù)為y=sinx，CIRCLES數(shù)據(jù)集的分類函數(shù)為(x-a)2+(y-b)2=r2。實(shí)驗中的a、b、r的值分別設(shè)為＜（0.2，0.5），0.15＞，＜0.4，0.5），0.2＞，＜（0.6，0.5），0.25＞，＜（0.8，0.5），0.3＞。

表1 實(shí)驗數(shù)據(jù)集

4.1.2 評價指標(biāo)

當(dāng)發(fā)生漂移時，檢測算法很難在第一時間檢測出來，通常會存在漂移檢測延遲現(xiàn)象。為了有效評估漂移檢測的及時性，可以對漂移檢測的延遲設(shè)定一個閾值。當(dāng)檢測出的延遲點(diǎn)數(shù)Dj在真實(shí)延遲點(diǎn)數(shù)Dt閾值范圍內(nèi)則認(rèn)為正確檢測，否則，判定為錯誤檢測。錯誤率和漂移延遲越小，漂移檢測算法的性能越好。本文使用正確率Pc和延遲度wd兩個指標(biāo)來評估算法的性能，計算方法分別如公式（9）和（10）所示：

若當(dāng)前數(shù)據(jù)流實(shí)際發(fā)生概念漂移的次數(shù)為m，漂移延遲D的計算方法如公式（11）所示：

4.2 算法性能比較

4.2.1 錯誤率和延遲度分析

為驗證本文提出的NFHDDM算法在錯誤率和延遲度上的優(yōu)勢，這里選擇DDM、EDDM、CUSUM、ADWIN等算法進(jìn)行了實(shí)驗比較。為了驗證算法的普遍適用性，分別在突變漂移數(shù)據(jù)集SINE1 和漸變漂移數(shù)據(jù)集CIRCLES上進(jìn)行了實(shí)驗。為了分析噪聲對算法性能的影響，實(shí)驗中在相關(guān)數(shù)據(jù)集中加入了10%的噪聲點(diǎn)，實(shí)驗結(jié)果如表2所示。

從表2 中可以看出，在SINE1 數(shù)據(jù)集上，EDDM 的錯誤率和延遲度最高，本文提出的NFHDDM 算法在錯誤率上比表現(xiàn)最好的FHDDMS 算法下降了0.01，漂移延遲度降低了2.75；在CIRCLES 數(shù)據(jù)集上，NFHDDM算法錯誤率比FHDDM算法下降了0.06，延遲度也下降了18.67。FHDDM、FHDDMS 和NFHDDM 算法都使用基于Hoeffding 不等式的漂移閾值設(shè)定方法，但是，NFHDDM 算法在SINE1 數(shù)據(jù)集和CIRCLES 數(shù)據(jù)集上的錯誤率和延遲度表現(xiàn)均優(yōu)于其他基于Hoeffding不等式的算法，這主要是因為NFHDDM 算法采用的四分位距窗口能夠獲得當(dāng)前數(shù)據(jù)流段的典型特征，并減少了檢測數(shù)據(jù)的總數(shù)，提高了概念漂移檢測的及時性。從表2的結(jié)果對比中可以看出延遲度越低，錯誤率也越低。因此，減小延遲度可以有效提升算法的正確率。

表2 錯誤率和延遲度對比表

4.2.2 噪聲對算法性能的影響分析

為了驗證NFHDDM 算法對噪聲的敏感性，本文通過在兩個人工數(shù)據(jù)集上增加不同比例的噪聲進(jìn)行實(shí)驗。算法對噪聲具有一定的敏感度，當(dāng)噪聲率過大時，應(yīng)適當(dāng)考慮對噪聲的重新分類而不是忽略不計。圖2（a）和（b）分別展示了不同算法在SINE1數(shù)據(jù)集和CIRCLES數(shù)據(jù)集上的錯誤率隨噪聲率的變化情況。總體上看，在這兩個數(shù)據(jù)集上，噪聲率對所有算法錯誤率的影響基本一致，即噪聲率越高，錯誤率也越高。在對比的各種算法中，EDDM 算法的錯誤率最高，其他算法的錯誤率基本一致。同時，從圖2 中可以看出，本文提出的NFHDDM算法在不同的噪聲率下都能獲得最好的錯誤率結(jié)果。

圖3（a）和（b）分別展示了不同算法在SINE1 數(shù)據(jù)集和CIRCLES數(shù)據(jù)集上的漂移延遲度隨噪聲率的變化情況。從圖3 中可以看出，本文提出的NFHDDM 算法在漂移延遲度上受噪聲的干擾最小，漂移延遲度明顯低于其他比較算法。這主要是因為NFHDDM 算法使用滑動的四分位距窗口，能夠更好地提取當(dāng)前數(shù)據(jù)流段的概念特征分布并且引入動態(tài)系數(shù)能更好的適應(yīng)噪聲對分類器的影響，從而使分類器能夠保持較好的穩(wěn)定性。

4.2.3 算法消融對比分析

圖2 不同噪聲率下的錯誤率對比

圖3 不同噪聲率下漂移延遲度對比

為了驗證四分位距窗口和動態(tài)系數(shù)分別對改進(jìn)算法的影響，本文在數(shù)據(jù)量較大的人工數(shù)據(jù)集CIRCLES上做了兩個對比實(shí)驗，選擇人工數(shù)據(jù)集是為了能夠明確分辨漂移延遲點(diǎn)。其中，第一個實(shí)驗FHDDM_IQR只在FHDDM算法中使用四分位距窗口，用于驗證四分位距窗口對概念漂移檢測的影響；第二個實(shí)驗FHDDM_λ只在FHDDM算法中引入動態(tài)調(diào)整系數(shù)，用于驗證動態(tài)系數(shù)對概念漂移檢測的影響，實(shí)驗結(jié)果如圖4所示。從圖4（a）和（b）的結(jié)果對比可以看出，四分位距窗口對延遲度的影響更大，但是，使用動態(tài)系數(shù)可以獲得更低的錯誤率，因為動態(tài)系數(shù)的使用可以更好地適應(yīng)噪聲對分類器的影響。同時，從圖4 結(jié)果的對比中可以明顯看出，只使用四分位距窗口或動態(tài)系數(shù)都不能獲得理想的概念漂移檢測延遲度，而結(jié)合二者的NFHDDM 算法在分類錯誤率和概念漂移檢測延遲度兩個評價指標(biāo)均獲得了最好的結(jié)果。因此，在NFHDDM 算法中同時使用四分位距窗口和動態(tài)調(diào)整系數(shù)是必要的。

4.2.4 算法綜合性能對比

為了進(jìn)一步驗證NFHDDM 算法在不同評估指標(biāo)上的整體優(yōu)勢，本文提出了一種基于加權(quán)平均的綜合性能評估指標(biāo)方法。對每個數(shù)據(jù)流，這里使用權(quán)重向量W={w1,w2,w3,w4,w5,w6} 計算出一個整體分?jǐn)?shù)Score，向量中的屬性分別代表錯誤率、漂移延遲、假陽性數(shù)、假陰性數(shù)、內(nèi)存占用量和運(yùn)行時間，若用vi表示每個屬性賦予的權(quán)重，則將Score 的計算方法描述如公式（12）所示：

圖4 消融實(shí)驗結(jié)果對比

本文為六個屬性設(shè)置相同的權(quán)重，圖5展示了在人工數(shù)據(jù)集上的各個算法的綜合性能評估指標(biāo)分?jǐn)?shù)。從圖5可以看出，NFHDDM在綜合指標(biāo)Score上總能保持最優(yōu)狀態(tài)，這說明NFHDDM 在定義的六個指標(biāo)屬性上都有上佳的表現(xiàn)，符合上述實(shí)驗的結(jié)果。

圖5 基于人工數(shù)據(jù)集的綜合評估指標(biāo)分?jǐn)?shù)比較

真實(shí)數(shù)據(jù)集的實(shí)驗與人工數(shù)據(jù)集不同之處在于，真實(shí)數(shù)據(jù)集不知道具體的漂移點(diǎn)在哪里，只能通過錯誤率來驗證檢測漂移的有效性。同時，在大規(guī)模數(shù)據(jù)流分類應(yīng)用中，算法運(yùn)行時的時間效率和內(nèi)存需求也是影響其性能的重要指標(biāo)。因此，對真實(shí)數(shù)據(jù)集，本文使用三個綜合性能評估屬性：錯誤率、運(yùn)行時間和運(yùn)行時占用的內(nèi)存。并為這三個屬性設(shè)置相同的權(quán)重，各個算法在真實(shí)數(shù)據(jù)集Elecnormnew[19]和Poker-lsn[20]上的綜合評估指標(biāo)實(shí)驗結(jié)果如圖6 所示。從圖6 的對比中可以看出，DDM、CUSUM 算法Score 分?jǐn)?shù)普遍較低，F(xiàn)HDDM、FHDDMS、NFHDDM 算法分?jǐn)?shù)能夠保持在較高水平上，并且，NFHDDM算法的分?jǐn)?shù)總體上處于最高狀態(tài)。由于Poker-lsn 的數(shù)據(jù)集較大，使得圖6（b）中的分?jǐn)?shù)分層更加明顯，NFHDDM 算法在綜合性能上的優(yōu)勢更加明顯。

通過圖5和圖6對比可以發(fā)現(xiàn)，本文提出的NFHDDM算法在綜合性能指標(biāo)上的優(yōu)勢明顯，因此可以得出結(jié)論，添加四分位距窗口不僅沒有增加算法運(yùn)行的時間和內(nèi)存消耗，還進(jìn)一步提高了漂移檢測的正確率，減小了漂移檢測的延遲度。

圖6 基于真實(shí)數(shù)據(jù)集的綜合評估指標(biāo)分?jǐn)?shù)比較

5 結(jié)束語

針對目前主要的概念漂移檢測算法中存在的漂移檢測延遲度過高的問題，本文提出了基于改進(jìn)Hoeffding不等式的NFHDDM 算法，該算法使用四分位距的方法選擇檢測的數(shù)據(jù)，同時在Hoeffding 不等式中引入概念漂移檢測的動態(tài)系數(shù)，使算法能更好的適應(yīng)有噪聲情況下的真實(shí)數(shù)據(jù)集。實(shí)驗結(jié)果表明，NFHDDM 算法能夠在較少的運(yùn)行時間和較低的內(nèi)存使用量情況下有效降低漂移檢測延遲度，進(jìn)一步提升隱含概念漂移的數(shù)據(jù)流分類的正確率。