柳京秀,梅 穎,盧誠波

(1. 浙江理工大學(xué)理學(xué)院,浙江 杭州 310018;2. 麗水學(xué)院工學(xué)院,浙江 麗水 323000)

1 引言

概念漂移[1]是指數(shù)據(jù)所蘊(yùn)含的知識(shí)或概念隨著時(shí)間的變化而變化。針對(duì)穩(wěn)定數(shù)據(jù)流設(shè)計(jì)的分類方法,不具有抵抗流式數(shù)據(jù)概念漂移的能力,因此需要有針對(duì)性地研究面向概念漂移數(shù)據(jù)流的分類方法。

根據(jù)模型中基分類器的個(gè)數(shù),概念漂移數(shù)據(jù)流分類算法可以分為單分類器算法和集成算法。單分類器算法通常在分類算法中加入增量學(xué)習(xí)的需求以及遺忘舊數(shù)據(jù)的功能。Geoff提出了VFDT[2]的算法和CVFDT算法[3],前者只能處理穩(wěn)定數(shù)據(jù)流,后者依賴于窗口的大小。H.He提出的解決方案[4]需要在實(shí)驗(yàn)開始前設(shè)置內(nèi)核參數(shù),故算法易受到概念漂移的影響。相比單分類算法,集成算法具有更好的泛化能力[5]。其中精度加權(quán)集成算法(AWE)[6]和Learn++.NSE[7]算法是經(jīng)典的集成算法之一。AWE通過當(dāng)前數(shù)據(jù)塊的性能來設(shè)置權(quán)重。Learn++.NSE則由基分類器生命周期與分類準(zhǔn)確率的變化來計(jì)算權(quán)重。通過AWE的思想構(gòu)建的HDWE[1],使用Hellinger距離來修剪集成。AiRStream[8]定期抽樣活躍與非活躍基分類器的分類情況來提高模型性能。CALMID[9]設(shè)置了集成分類器、漂移檢測(cè)器、標(biāo)簽滑動(dòng)窗口等綜合的在線主動(dòng)學(xué)習(xí)框架。

這些算法在處理分類問題時(shí)通常只考慮利用分類準(zhǔn)確率作為評(píng)判模型分類效果的指標(biāo)。事實(shí)上,只簡(jiǎn)單地使用某個(gè)單一評(píng)價(jià)指標(biāo)來評(píng)估基分類器的性能,不能全面客觀地反映其在集成中的價(jià)值。在集成學(xué)習(xí)中,基分類器的分類性能評(píng)價(jià)指標(biāo)是分類器權(quán)值調(diào)整策略及分類器替換策略的主要依據(jù),因此需要考慮多個(gè)指標(biāo)[10],才能全面反映該基分類器在集成中的整體價(jià)值。

基于以上目的,本文提出一種基于差異性綜合評(píng)價(jià)指標(biāo)的集成算法AE-Div。該算法首先比較樣本數(shù)據(jù)均值來判斷當(dāng)前數(shù)據(jù)分布是否發(fā)生變化;其次利用不一致度量、Kohavi-Wolpert方差作為差異性度量指標(biāo)來計(jì)算集成的差異性,同時(shí)結(jié)合時(shí)間因子、基分類器的分類準(zhǔn)確率并以加權(quán)的方式融合成“基分類器的綜合評(píng)價(jià)指標(biāo)”;最后根據(jù)概念漂移的檢測(cè)結(jié)果,對(duì)基分類器采取不同的調(diào)整策略。實(shí)驗(yàn)表明,本文提出的算法對(duì)比其它算法更具穩(wěn)定性和適應(yīng)性。

2 基于差異性度量的集成算法

集成算法由多個(gè)基分類器相結(jié)合來完成學(xué)習(xí)任務(wù)構(gòu)建而成,一般結(jié)構(gòu)為:先產(chǎn)生一組基分類器,再利用某種策略將它們結(jié)合起來。因此基分類器之間可能存在相關(guān)性[11]。如下表1所示,將基分類器C1,C2,C3利用簡(jiǎn)單投票法策略結(jié)合起來,當(dāng)C1,C2,C3有相同的準(zhǔn)確率時(shí),由于(a)中的基分類器具有差異性,故由準(zhǔn)確率為66.7%的基分類器組成的集成模型的分類準(zhǔn)確率達(dá)到了100%;如(b),若由三個(gè)完全相同且分類準(zhǔn)確率為66.7%的分類器組成,則對(duì)集成模型的分類結(jié)果沒有幫助,其模型準(zhǔn)確率仍為66.7%。然而,即使基分類器間具有差異性,由于各個(gè)基分類器的分類準(zhǔn)確率偏低,同樣會(huì)影響集成分類器的分類結(jié)果,見(c)。因此本文提出一種兼顧準(zhǔn)確率和差異性的集成算法,使得集成算法中的基分類器更具獨(dú)立性、互補(bǔ)性[11]。若數(shù)據(jù)流發(fā)生概念漂移,在集成池中,由于基分類器間具有差異,總有若干個(gè)基分類器能更好的應(yīng)對(duì)數(shù)據(jù)變化。

表1 基分類器間的差異性和分類準(zhǔn)確性對(duì)集成分類結(jié)果的影響

2.1 差異性度量指標(biāo)及權(quán)重計(jì)算方法

度量差異性的指標(biāo)有兩類[12]:成對(duì)度量和非成對(duì)度量。成對(duì)度量是度量?jī)蓚€(gè)基分類器之間的成對(duì)相似度或不相似度,然后對(duì)所有的成對(duì)指標(biāo)取均值。常用的成對(duì)度量有Q-統(tǒng)計(jì)量、不一致度量、雙錯(cuò)度量等。非成對(duì)度量則直接度量集成的差異性。代表性的非成對(duì)度量有Kohavi-Wolpert方差、評(píng)分者間一致度、熵等。成對(duì)度量指標(biāo)偏重集成分類的局部最優(yōu),而非成對(duì)度量指標(biāo)則更強(qiáng)調(diào)集成分類的整體最優(yōu),因此本文將成對(duì)度量和非成對(duì)度量作為基分類器的差異性綜合評(píng)價(jià)指標(biāo)。下面介紹本文選取的度量指標(biāo)。

不一致度量是指基分類器Ci,Cj給出不同預(yù)測(cè)結(jié)果的樣本數(shù)目占比,公式如下

(1)

其中:Nab表示分類器Ci分類結(jié)果為a,分類器Cj分類結(jié)果為b的樣本數(shù)目,1表示分類結(jié)果正確,0表示分類結(jié)果錯(cuò)誤。根據(jù)公式計(jì)算,disi.j的值域在[0,1]之間,disi.j值越高,代表兩個(gè)基分類器的差異性越大。當(dāng)有T個(gè)基分類器參與集成時(shí),集成學(xué)習(xí)的整體差異性通過求基分類器兩兩之間的disi.j平均值得到,即

(2)

Kohavi-Wolpert方差源于誤差的偏差-方差分解,通過考慮兩個(gè)基分類器的輸出情況來度量差異性,即統(tǒng)計(jì)集成E中基分類器對(duì)每個(gè)樣本(xi,yi)的正確分類與錯(cuò)誤分類的數(shù)目,即

(3)

其中ρ(x)表示對(duì)樣本(x,y)分類正確的基分類器數(shù)目。KW度量的值越大,代表集成差異越大。

當(dāng)數(shù)據(jù)分布發(fā)生變化時(shí),新分類器與舊分類器不相關(guān),因此本文的權(quán)重的設(shè)置形式為

(4)

(5)

其中ρ是權(quán)重關(guān)于時(shí)間的因子。由新數(shù)據(jù)生成的基分類器在集成E中意義更大,故在模型中增設(shè)時(shí)間因子。且由當(dāng)前數(shù)據(jù)塊生成的分類器對(duì)該數(shù)據(jù)塊的分類效果最佳,故Acc分別設(shè)為

(6)

(7)

其中MSEi為預(yù)測(cè)誤差,MSEr為均方誤差。

2.2 AW-Div方法介紹及流程

S1={(x1,y1),…,(xt,yt)},S2={(xt+1,yt+1),…,(xm,ym)}分別表示數(shù)據(jù)流中的兩組樣本,其樣本總體均值為μ1,μ2。由假設(shè)檢驗(yàn)可知,若S1,S2服從相同分布,則接受原假設(shè)H0:μ1=μ2;否則接受備擇假設(shè)H1:μ1≠μ2。故本文通過比較兩個(gè)數(shù)據(jù)塊的樣本均值的差異程度來判斷數(shù)據(jù)流是否發(fā)生概念漂移。對(duì)比其它檢測(cè)機(jī)制更易操作。該檢測(cè)算法的關(guān)鍵在于闕值的選擇。闕值的選擇將影響檢測(cè)機(jī)制的結(jié)果、基分類器的替換和權(quán)重更新的頻率,故應(yīng)根據(jù)具體問題來決定闕值的大小。

AW-Div算法步驟可總結(jié)如下:

1) 當(dāng)數(shù)據(jù)流經(jīng)緩存區(qū)時(shí),按時(shí)間順序?qū)?shù)據(jù)塊D分成Dold,Dnew兩個(gè)子數(shù)據(jù)塊,計(jì)算兩個(gè)子數(shù)據(jù)塊的樣本均值μold,μnew;

2) 若μold,μnew的變化程度大于漂移闕值,表明當(dāng)前數(shù)據(jù)發(fā)生概念漂移。將數(shù)據(jù)塊D用K-Means聚成k簇,跳轉(zhuǎn)5);

3) 若μold,μnew的變化程度小于警告闕值,表明當(dāng)前數(shù)據(jù)的分布未發(fā)生改變,用數(shù)據(jù)塊D按式(4)對(duì)舊基分類器進(jìn)行更新;

4) 若μold,μnew的變化程度在兩個(gè)闕值之間,說明Dnew中部分?jǐn)?shù)據(jù)的分布發(fā)生了變化,跳轉(zhuǎn)6);

5) 用K-Means按數(shù)據(jù)特征將數(shù)據(jù)聚集成k簇并訓(xùn)練生成k個(gè)分類器。用式(5)設(shè)置權(quán)重;按式(4)對(duì)舊基分類器進(jìn)行更新,跳轉(zhuǎn)8);

6) 用數(shù)據(jù)Dnew創(chuàng)建基分類器并由式(5)計(jì)算其權(quán)重,用數(shù)據(jù)塊D按式(4)計(jì)算并調(diào)整舊基分類器的權(quán)重,跳轉(zhuǎn)8);

7) 若集成中基分類器的個(gè)數(shù)溢出,由分類性能高的基分類器代替過時(shí)基分類器;

8) 保留分布發(fā)生變化的部分?jǐn)?shù)據(jù)與新數(shù)據(jù)構(gòu)成數(shù)據(jù)塊D′進(jìn)入下一輪檢測(cè)直至結(jié)束。

3 仿真研究

本文分別在合成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行仿真。實(shí)驗(yàn)環(huán)境如下:Intel UHD Graphics 617GPU,4 GB內(nèi)存;操作系統(tǒng)為 MacBook Air;仿真環(huán)境為基于Python語言的PyCharm平臺(tái),編譯運(yùn)行環(huán)境為Python3.8。

3.1 數(shù)據(jù)集

針對(duì)AE-Div算法仿真,本文選取了3個(gè)人工合成的數(shù)據(jù)集和3個(gè)真實(shí)數(shù)據(jù)集。其中人工合成數(shù)據(jù)集由ConceptDriftStream構(gòu)造,真實(shí)數(shù)據(jù)集由UCI數(shù)據(jù)庫獲取。具體信息描述見表2。

表2 數(shù)據(jù)集的基本信息

3.2 仿真分析

本文選取AWE、批量增量集成分類器(Batch Incremental ensemble classifier,BIEC)、Learn++.NSE作對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)統(tǒng)一選取決策樹作為基分類器。設(shè)置集成分類器的最大容量為30,數(shù)據(jù)塊大小為200,設(shè)置AE-Div算法中的參數(shù):ρ=1.1,θ=0.75。

表3為4種算法在6個(gè)數(shù)據(jù)集上運(yùn)行10次后得到的平均分類準(zhǔn)確率,為了方便比較,已將結(jié)果轉(zhuǎn)化為百分比。從表中可以看出,在6個(gè)數(shù)據(jù)集上,本文提出的AE-DiV算法的平均分類準(zhǔn)確率要優(yōu)于其它3個(gè)算法,且高于其它算法至少7%。為了更詳細(xì)地展示AE-DiV算法在不同數(shù)據(jù)集上的對(duì)比結(jié)果,接下來將分別展示4個(gè)算法在不同數(shù)據(jù)集上實(shí)時(shí)分類準(zhǔn)確率情況。

表3 實(shí)驗(yàn)結(jié)果

圖1、圖2分別為4 種算法在AGRAWAL、Hyperplane數(shù)據(jù)集上的實(shí)時(shí)分類情況。從圖中可以看出,當(dāng)數(shù)據(jù)發(fā)生概念漂移時(shí),4個(gè)算法的分類準(zhǔn)確率都受到了影響。由于AE-DiV在每次檢測(cè)到概念漂移時(shí),會(huì)生成適應(yīng)數(shù)據(jù)變化的k個(gè)新分類器,使模型具有較好分類效果。在AGRAWAL數(shù)據(jù)集中,當(dāng)發(fā)生第1次、第3次概念漂移時(shí),相比其它算法,AE-DiV更快地恢復(fù)分類準(zhǔn)確性。從表3可看出,AE-DiV的平均分類準(zhǔn)確率最高,其次為BIEC和Learn++.NSE。而在Hyperplane數(shù)據(jù)集上,AE-DiV的分類效果一直優(yōu)于AWE、Learn++.NSE。綜合表3,對(duì)于該數(shù)據(jù)集,AE-DiV的平均分類準(zhǔn)確性最高,其次為BIEC。

圖1 AGRAWAL數(shù)據(jù)集運(yùn)行結(jié)果

圖2 Hyperplane數(shù)據(jù)集運(yùn)行結(jié)

圖3為4 種算法在LED數(shù)據(jù)集上的分類準(zhǔn)確率。由于LED數(shù)據(jù)分布變化較為緩慢,4個(gè)算法都很穩(wěn)定,AE-DiV、AWE的分類準(zhǔn)確率接近90%,Learn++.NSE的分類準(zhǔn)確率高于75%,而BIEC的分類準(zhǔn)確率只在10%左右。

圖3 LED數(shù)據(jù)集運(yùn)行結(jié)果

圖4展示了4 種算法在waveform數(shù)據(jù)集上訓(xùn)練時(shí)各個(gè)階段的實(shí)時(shí)分類準(zhǔn)確率。AE-DiV、AWE的分類效果明顯優(yōu)于Learn++.NSE和BIEC,。從表3可以看出,對(duì)于waveform數(shù)據(jù)集,AE-DiV的分類效果最優(yōu),其次為AWE。

圖4 waveform數(shù)據(jù)集運(yùn)行結(jié)果

圖5、圖6為 4 種算法在connect數(shù)據(jù)集、Creditcard數(shù)據(jù)集上的實(shí)時(shí)分類準(zhǔn)確率?？梢钥闯?當(dāng)數(shù)據(jù)分布發(fā)生變化時(shí),相對(duì)于其它算法的分類效果,AE-DiV均能更快地恢復(fù)分類能力,維持較高的分類準(zhǔn)確率。結(jié)合表3,對(duì)于connect數(shù)據(jù)集,AE-DiV的分類效果最優(yōu)。對(duì)于Creditcard數(shù)據(jù)集,AE-DiV、BIECE的分類準(zhǔn)確率明顯優(yōu)于AWE、Learn++.NSE。

圖5 connect數(shù)據(jù)集運(yùn)行結(jié)果

圖6 Creditcard數(shù)據(jù)集運(yùn)行結(jié)果

綜合以上可以得出,當(dāng)測(cè)試數(shù)據(jù)發(fā)生變化時(shí),AE-DiV利用新數(shù)據(jù)訓(xùn)練出新分類器代替過時(shí)的冗余分類器調(diào)整模型使其更快地適應(yīng)數(shù)據(jù)的變化,對(duì)比其它算法具有更強(qiáng)的泛化能力和穩(wěn)定性。

4 總結(jié)

本文提出的AE-DiV算法首先通過監(jiān)測(cè)數(shù)據(jù)塊中樣本均值的變化來檢測(cè)數(shù)據(jù)是否發(fā)生概念漂移。該算法僅在數(shù)據(jù)流分布發(fā)生變化時(shí)才生成新的基分類器,解決了基分類器在集成模型中的冗余問題。為了使基分類器更好的處理概念漂移,將基分類器的分類準(zhǔn)確率和差異性與時(shí)間因子相結(jié)合融合成權(quán)重對(duì)模型進(jìn)行優(yōu)化。最后與其它幾種概念漂移分類算法進(jìn)行仿真實(shí)驗(yàn),結(jié)果表明AE-DiV模型具有更好的分類準(zhǔn)確性和穩(wěn)定性,能更快地適應(yīng)概念漂移。