改進(jìn)Hoeffding不等式的概念漂移檢測(cè)方法

徐清妍，何 麗，朱泓西

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

1 引言

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

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

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

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

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

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

2 FHDDM的基礎(chǔ)理論

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

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

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

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

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

3.1 NFHDDM的窗口設(shè)定

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

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

圖1 窗口解釋圖

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

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

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

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

3.3 NFHDDM算法

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

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

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

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

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

考慮到概念漂移包括突變漂移和漸變漂移，實(shí)驗(yàn)中使用了兩個(gè)人工數(shù)據(jù)集：存在突變漂移的SINE1數(shù)據(jù)集和存在漸變漂移的CIRCLES 數(shù)據(jù)集，以及兩個(gè)真實(shí)數(shù)據(jù)集，各個(gè)數(shù)據(jù)集的主要屬性描述如表1 所示。其中，SINE1數(shù)據(jù)集的分類(lèi)函數(shù)為y=sinx，CIRCLES數(shù)據(jù)集的分類(lèi)函數(shù)為(x-a)2+(y-b)2=r2。實(shí)驗(yàn)中的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í)驗(yàn)數(shù)據(jù)集

4.1.2 評(píng)價(jià)指標(biāo)

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

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

4.2 算法性能比較

4.2.1 錯(cuò)誤率和延遲度分析

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

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

表2 錯(cuò)誤率和延遲度對(duì)比表

4.2.2 噪聲對(duì)算法性能的影響分析

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

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

4.2.3 算法消融對(duì)比分析

圖2 不同噪聲率下的錯(cuò)誤率對(duì)比

圖3 不同噪聲率下漂移延遲度對(duì)比

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

4.2.4 算法綜合性能對(duì)比

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

圖4 消融實(shí)驗(yàn)結(jié)果對(duì)比

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

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

真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)與人工數(shù)據(jù)集不同之處在于，真實(shí)數(shù)據(jù)集不知道具體的漂移點(diǎn)在哪里，只能通過(guò)錯(cuò)誤率來(lái)驗(yàn)證檢測(cè)漂移的有效性。同時(shí)，在大規(guī)模數(shù)據(jù)流分類(lèi)應(yīng)用中，算法運(yùn)行時(shí)的時(shí)間效率和內(nèi)存需求也是影響其性能的重要指標(biāo)。因此，對(duì)真實(shí)數(shù)據(jù)集，本文使用三個(gè)綜合性能評(píng)估屬性：錯(cuò)誤率、運(yùn)行時(shí)間和運(yùn)行時(shí)占用的內(nèi)存。并為這三個(gè)屬性設(shè)置相同的權(quán)重，各個(gè)算法在真實(shí)數(shù)據(jù)集Elecnormnew[19]和Poker-lsn[20]上的綜合評(píng)估指標(biāo)實(shí)驗(yàn)結(jié)果如圖6 所示。從圖6 的對(duì)比中可以看出，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)勢(shì)更加明顯。

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

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

5 結(jié)束語(yǔ)

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