梁 斌 李光輝 代成龍

(江南大學(xué)人工智能與計(jì)算機(jī)學(xué)院 江蘇無(wú)錫 214122)(1634113866@qq.com)

信息的爆炸性增長(zhǎng)導(dǎo)致數(shù)據(jù)流廣泛出現(xiàn)在各個(gè)應(yīng)用領(lǐng)域中，如無(wú)線(xiàn)傳感器數(shù)據(jù)流、銀行交易數(shù)據(jù)流等[1-3].數(shù)據(jù)流中的潛在分布或目標(biāo)概念隨著時(shí)間推移發(fā)生變化，這種現(xiàn)象被稱(chēng)為“概念漂移”[4-5].概念漂移會(huì)導(dǎo)致在過(guò)去數(shù)據(jù)上訓(xùn)練的分類(lèi)模型性能顯著下降，無(wú)法適應(yīng)當(dāng)前的新概念，這給傳統(tǒng)的數(shù)據(jù)挖掘算法帶來(lái)新的挑戰(zhàn).另一方面，當(dāng)數(shù)據(jù)流中存在類(lèi)別不平衡現(xiàn)象時(shí)，即某一類(lèi)的實(shí)例數(shù)量顯著多于其他類(lèi)，數(shù)據(jù)流分類(lèi)會(huì)變得更加困難，因?yàn)樯兕?lèi)實(shí)例(minority class instance)[6-7]出現(xiàn)頻率過(guò)低導(dǎo)致分類(lèi)模型對(duì)它們學(xué)習(xí)不充分，而我們通常更關(guān)注少類(lèi)的分類(lèi)情況，因?yàn)檎`分類(lèi)一個(gè)少類(lèi)實(shí)例的代價(jià)通常遠(yuǎn)大于誤分類(lèi)一個(gè)多類(lèi)實(shí)例(majority class instance)的代價(jià)，例如在癌癥診斷中，將患癌人群診斷為健康會(huì)帶來(lái)嚴(yán)重后果.

目前可以同時(shí)處理概念漂移和類(lèi)別不平衡問(wèn)題的數(shù)據(jù)流分類(lèi)方法大多是基于集成學(xué)習(xí)的思想，主要包括在線(xiàn)集成和基于數(shù)據(jù)塊的集成方法[8].在線(xiàn)集成方法以Wang等人[9]提出的OOB(oversampling online bagging)和UOB(undersampling online bagging)為代表，它們將過(guò)采樣和欠采樣技術(shù)與Online Bagging[10]相結(jié)合，動(dòng)態(tài)調(diào)整采樣頻率，有效解決了數(shù)據(jù)流中類(lèi)別不平衡問(wèn)題.在線(xiàn)集成方法通常還與針對(duì)不平衡數(shù)據(jù)流設(shè)計(jì)的漂移檢測(cè)方法結(jié)合，例如Wang等人[11]提出的DDM-OCI(drift detection method for online class imbalance learning)結(jié)合Online Bagging，通過(guò)監(jiān)測(cè)少類(lèi)召回率的變化在不平衡數(shù)據(jù)流中檢測(cè)漂移.但DDM-OCI假設(shè)數(shù)據(jù)流服從高斯分布，因而在實(shí)際應(yīng)用中存在較高的誤報(bào)率.為此，Wang等人[12]又提出了LFR(linear four rates)使用統(tǒng)計(jì)學(xué)檢驗(yàn)分析中的TPR(true positive rate)，TNR(true negative rate)，PPV(positive predicted value)，NPV(negative predicted value)4個(gè)指標(biāo)的變化顯著性來(lái)檢測(cè)漂移，有效降低了DDM-OCI的誤報(bào)率.而Wang等人[13]提出的HLFR(hierarchical linear four rate)使用分層假設(shè)檢測(cè)框架，在第1層使用LFR檢測(cè)漂移，第2層使用排列檢驗(yàn)(permutation test)驗(yàn)證漂移的真實(shí)性，進(jìn)一步降低了LFR檢測(cè)漂移的誤報(bào)率.在所有基于數(shù)據(jù)塊的集成方法中，Gao等人[14]提出的UB(uncorrelated bagging)是第一個(gè)解決數(shù)據(jù)流中類(lèi)別不平衡的方法.UB使用集成框架，不斷累積數(shù)據(jù)流中的少類(lèi)實(shí)例，然后添加到當(dāng)前數(shù)據(jù)塊中平衡數(shù)據(jù)分布.然而這種策略不僅需要大量的內(nèi)存空間來(lái)存儲(chǔ)累積的少類(lèi)實(shí)例，而且沒(méi)有考慮少類(lèi)實(shí)例上可能發(fā)生概念漂移的問(wèn)題，有較大的局限性.為此，Chen等人[15]提出的SERA(selectively recursive approach)改進(jìn)了UB，它使用馬氏距離計(jì)算累積的少類(lèi)實(shí)例和當(dāng)前數(shù)據(jù)塊中少類(lèi)實(shí)例的相似度，只選擇相似度較高的少類(lèi)實(shí)例平衡當(dāng)前數(shù)據(jù)塊的類(lèi)別分布.進(jìn)一步，Chen等人[16]又提出了REA(recursive ensemble approach)，該方法使用KNN(k-nearest neighbors)計(jì)算相似度，替換SERA中的馬氏距離度量，解決了少類(lèi)實(shí)例中的子概念問(wèn)題.而針對(duì)重采樣過(guò)程存在的一些困難因素，例如異常數(shù)據(jù)，類(lèi)別重疊等，Ren等人[17]提出了GRE(gradual recursive ensemble)，它使用DBSCAN聚類(lèi)技術(shù)將當(dāng)前少類(lèi)實(shí)例分為若干個(gè)簇，然后分別計(jì)算各個(gè)簇中實(shí)例和過(guò)去數(shù)據(jù)塊中少類(lèi)實(shí)例的相似度，選擇部分少類(lèi)實(shí)例填充至當(dāng)前數(shù)據(jù)塊，解決了重采樣過(guò)程中數(shù)據(jù)異常和類(lèi)別重疊問(wèn)題.Wu等人[18]提出的DFGW-IS(dynamic feature group weighting with importance sampling)通過(guò)分析當(dāng)前數(shù)據(jù)塊和過(guò)去數(shù)據(jù)塊的海林格距離差異來(lái)檢測(cè)概念漂移，同時(shí)結(jié)合重要性采樣處理類(lèi)別不平衡問(wèn)題.基于數(shù)據(jù)塊的集成方法存在一個(gè)共性問(wèn)題：它們都假設(shè)少類(lèi)實(shí)例的概念不會(huì)發(fā)生變化，即過(guò)去數(shù)據(jù)塊中的少類(lèi)實(shí)例可以繼續(xù)使用.然而在實(shí)際情況中，類(lèi)的先驗(yàn)概率隨時(shí)間也會(huì)發(fā)生變化，過(guò)去數(shù)據(jù)塊中少類(lèi)實(shí)例可能就是當(dāng)前數(shù)據(jù)塊中的多類(lèi)實(shí)例.另外，重復(fù)訪(fǎng)問(wèn)歷史數(shù)據(jù)也不符合數(shù)據(jù)流挖掘的要求.因此，以Ditzler等人[19]的Lean++CDS和Lean++NIE為代表，一些不需要保存歷史數(shù)據(jù)的集成方法被提出.Lean++CDS是Learn++NSE和SMOTE(synthetic minority class oversampling technique)的簡(jiǎn)單結(jié)合，其中Learn++NSE用于處理概念漂移，而SMOTE產(chǎn)生新的少類(lèi)實(shí)例以平衡當(dāng)前數(shù)據(jù)塊的類(lèi)別分布，無(wú)需保存任何歷史數(shù)據(jù).Lean++NIE也不需要訪(fǎng)問(wèn)歷史數(shù)據(jù)，在每個(gè)數(shù)據(jù)塊上對(duì)多類(lèi)實(shí)例進(jìn)行欠采樣，結(jié)合Bagging技術(shù)生成一個(gè)由多個(gè)成員分類(lèi)器組成的子集成模塊，并根據(jù)成員分類(lèi)器在過(guò)去和當(dāng)前數(shù)據(jù)塊上的G-mean性能分配權(quán)重，有效平衡每個(gè)類(lèi)別的重要性.此外，Lu等人[20]提出的DWMIL(dynamic weighted majority for imbalance learning)在集成模型中只保留有限數(shù)量的成員分類(lèi)器，每個(gè)成員分類(lèi)器的權(quán)重根據(jù)在當(dāng)前數(shù)據(jù)塊上的G-mean性能決定，并隨著時(shí)間衰減，直至小于某個(gè)閾值被移除，兼顧了效率和性能.

基于上述分析，目前已有的方法主要存在2個(gè)問(wèn)題：一是需要大量空間保存過(guò)去的少類(lèi)實(shí)例進(jìn)行重復(fù)使用，且沒(méi)有考慮類(lèi)先驗(yàn)概率變化的情況；二是集成方法中的成員分類(lèi)器權(quán)重是基于數(shù)據(jù)塊更新的，缺乏在線(xiàn)更新機(jī)制，面對(duì)突變型漂移或發(fā)生在數(shù)據(jù)塊內(nèi)的漂移時(shí)，難以快速應(yīng)對(duì).為此，針對(duì)二分類(lèi)數(shù)據(jù)流，本文在基于數(shù)據(jù)塊集成方法上引入了在線(xiàn)更新機(jī)制，提出了一種基于G-mean加權(quán)的在線(xiàn)不平衡數(shù)據(jù)流分類(lèi)方法(online G-mean update ensemble for imbalance learning, OGUEIL)，以集成框架為基礎(chǔ)，每到達(dá)1個(gè)新實(shí)例，增量更新每個(gè)成員分類(lèi)器及其權(quán)重，并對(duì)少類(lèi)實(shí)例隨機(jī)過(guò)采樣，無(wú)須保存歷史數(shù)據(jù)，同時(shí)周期性地訓(xùn)練多個(gè)具有差異性的候選分類(lèi)器以提高集成模型的泛化能力.與同類(lèi)方法相比，本文主要貢獻(xiàn)有3個(gè)方面：

1) 提出了一種基于G-mean的在線(xiàn)加權(quán)策略，可以根據(jù)當(dāng)前數(shù)據(jù)分布及時(shí)調(diào)整每個(gè)成員分類(lèi)器的權(quán)重，有效解決不平衡數(shù)據(jù)流中的概念漂移問(wèn)題.

2) 在集成模型在線(xiàn)更新過(guò)程中引入了對(duì)少類(lèi)實(shí)例的隨機(jī)過(guò)采樣策略，既提高了少類(lèi)實(shí)例的召回率，又增加了集成的多樣性.

3) 基于混合采樣和自適應(yīng)滑動(dòng)窗口技術(shù)提出了一種候選分類(lèi)器訓(xùn)練策略，周期性地對(duì)當(dāng)前窗口上的數(shù)據(jù)同時(shí)使用邊界人工少類(lèi)實(shí)例合成技術(shù)[21]和隨機(jī)欠采樣技術(shù)生成多個(gè)具有差異性的候選分類(lèi)器，并將它們選擇性地添加至當(dāng)前集成模型中，提高泛化能力.

1 相關(guān)知識(shí)

1.1 數(shù)據(jù)流概述

在數(shù)據(jù)流分類(lèi)領(lǐng)域，數(shù)據(jù)流由大量按時(shí)間順序到達(dá)的實(shí)例組成，表示為S={s1,s2,…,st,…}，其中st=(Xt,yt)表示時(shí)刻t到達(dá)的實(shí)例，Xt=(d1,d2,…,dn)代表n維向量，意味著數(shù)據(jù)流S是n維的，yt∈{c1,c2,…,ck}表示實(shí)例st真實(shí)類(lèi)別，k為數(shù)據(jù)流S中所有類(lèi)別數(shù)量.

1.2 概念漂移定義和分類(lèi)

概念漂移是指數(shù)據(jù)流中的目標(biāo)概念隨時(shí)間發(fā)生改變，在數(shù)據(jù)流分類(lèi)領(lǐng)域，目標(biāo)概念一般指當(dāng)前分類(lèi)模型學(xué)習(xí)到的決策邊界.具體而言，假設(shè)數(shù)據(jù)流S服從某分布Ft(X,y)，P(y|X)表示y關(guān)于X的條件概率分布，代表決策邊界，若在時(shí)刻t+1有Ft(X,y)≠Ft+1(X,y)且Pt(y|X)≠Pt+1(y|X)，表明原有的決策邊界發(fā)生變化，這種現(xiàn)象稱(chēng)為概念漂移[8,22].

概念漂移的分類(lèi)普遍是基于概念變化的速度[22-23].當(dāng)新舊概念過(guò)渡很快，舊的概念突然被另一個(gè)數(shù)據(jù)分布完全不同的新概念取代，這種漂移屬于突變型概念漂移(abrupt concept drift)；反之，新舊概念過(guò)渡較慢時(shí)，舊概念被新概念逐漸替換，且二者在漂移前后或多或少有些相似，則屬于漸變型概念漂移(gradual concept drift).

1.3 在線(xiàn)過(guò)采樣集成算法OOB

針對(duì)數(shù)據(jù)流中的類(lèi)別不平衡問(wèn)題，Wang等人在OB(online bagging)[10]基礎(chǔ)上提出了在線(xiàn)過(guò)采樣集成算法OOB(oversampling OB)[9].OB將傳統(tǒng)的集成學(xué)習(xí)算法Bagging從靜態(tài)數(shù)據(jù)領(lǐng)域擴(kuò)展到了數(shù)據(jù)流領(lǐng)域.Bagging算法首先對(duì)所有樣本放回隨機(jī)采樣，然后得到多個(gè)訓(xùn)練集，最后訓(xùn)練多個(gè)不同的成員分類(lèi)器.因此每個(gè)樣本會(huì)被重復(fù)選擇k次，且k服從二項(xiàng)分布，如式(1)所示:

(1)

2 基于G-mean加權(quán)的在線(xiàn)不平衡數(shù)據(jù)流分類(lèi)方法

針對(duì)二分類(lèi)數(shù)據(jù)流中的概念漂移和類(lèi)別不平衡問(wèn)題，本文提出了一種基于G-mean加權(quán)的數(shù)據(jù)流分類(lèi)方法(OGUEIL).OGUEIL屬于在線(xiàn)集成方法，其主要思想是通過(guò)使用在線(xiàn)決策樹(shù)Hoeffding tree[24]和基于G-mean的在線(xiàn)加權(quán)機(jī)制，在基于數(shù)據(jù)塊的集成方法中引入在線(xiàn)更新機(jī)制，避免數(shù)據(jù)塊大小難以選擇的問(wèn)題，可以有效處理各種類(lèi)型的概念漂移，包括突變型、漸變型以及發(fā)生在數(shù)據(jù)塊內(nèi)部的漂移，提高分類(lèi)性能.在線(xiàn)更新過(guò)程中，OGUEIL結(jié)合OOB[9]對(duì)少類(lèi)實(shí)例進(jìn)行隨機(jī)過(guò)采樣，既提高了少類(lèi)實(shí)例的召回率，又增加了集成的多樣性，且不需要保存任何歷史數(shù)據(jù).此外，OGUEIL會(huì)周期性地添加和淘汰集成中的成員分類(lèi)器以維持集成模型的分類(lèi)效率和性能.OGUEIL包含更新、淘汰、候選分類(lèi)器訓(xùn)練、加權(quán)和決策5個(gè)過(guò)程，下面分別詳細(xì)介紹各過(guò)程的算法思路與偽代碼.

2.1 在線(xiàn)更新和淘汰機(jī)制

在OGUEIL中，每獲得一個(gè)新實(shí)例(xt,yt)，所有成員分類(lèi)器更新一次.為解決數(shù)據(jù)流中類(lèi)別不平衡導(dǎo)致少類(lèi)召回率過(guò)低的問(wèn)題，OGUEIL結(jié)合OOB[9]算法對(duì)少類(lèi)實(shí)例隨機(jī)過(guò)采樣，即對(duì)每個(gè)少類(lèi)實(shí)例學(xué)習(xí)k次，且k服從參數(shù)為ξ的泊松分布，ξ為當(dāng)前數(shù)據(jù)流中多類(lèi)實(shí)例與少類(lèi)實(shí)例的數(shù)量比，OOB偽代碼如算法1所示.由于數(shù)據(jù)流的不穩(wěn)定性，類(lèi)的先驗(yàn)分布可能發(fā)生變化，甚至少類(lèi)和多類(lèi)發(fā)生角色互換，因此OGUEIL需要實(shí)時(shí)監(jiān)測(cè)數(shù)據(jù)流中多類(lèi)實(shí)例和少類(lèi)實(shí)例的分布情況.

算法1.OOB[9].

輸入:時(shí)刻t到達(dá)的實(shí)例(xt,yt)，當(dāng)前集成模型Ω，當(dāng)前多類(lèi)實(shí)例數(shù)量|Ymaj|，當(dāng)前少類(lèi)實(shí)例數(shù)量|Ymin|;

輸出:更新后的集成模型Ω.

① while到達(dá)一個(gè)新實(shí)例

② 對(duì)于當(dāng)前集成模型Ω中的每一個(gè)分類(lèi)器Ci：

③ 計(jì)算當(dāng)前數(shù)據(jù)流的不平衡率ξ←|Ymaj|/|Ymin|；

④ if當(dāng)前實(shí)例屬于少類(lèi)

⑤ 根據(jù)式(3)設(shè)置k～Poisson(ξ)；

⑥ else

⑦ 設(shè)置k～Poisson(1)；

⑧ end if

⑨ 更新k次分類(lèi)器Ci；

⑩ end while

(2)

如果xt的真實(shí)類(lèi)別是正類(lèi)cp，那么[(xt,cp)]=1，否則[(xt,cp)]=0，對(duì)于負(fù)類(lèi)cn也是同理，而λ為預(yù)設(shè)的時(shí)間衰減因子.區(qū)別于傳統(tǒng)累加每個(gè)類(lèi)別實(shí)例的方式，這種方式使用時(shí)間衰減因子進(jìn)行指數(shù)平滑，強(qiáng)調(diào)當(dāng)前數(shù)據(jù)的影響同時(shí)弱化舊數(shù)據(jù)的影響，更適合用在數(shù)據(jù)流中.然后根據(jù)式(3)確定少類(lèi)和多類(lèi)，其中δ為預(yù)設(shè)的閾值.若滿(mǎn)足式(3)，正類(lèi)cp被標(biāo)記為多類(lèi)，負(fù)類(lèi)cn為少類(lèi)，反之亦然.

(3)

在本文中，參數(shù)δ是通過(guò)大量實(shí)驗(yàn)獲得的經(jīng)驗(yàn)值，δ過(guò)大或過(guò)小均會(huì)影響到算法性能.在第3節(jié)實(shí)驗(yàn)中，本文將詳細(xì)介紹各個(gè)參數(shù)的設(shè)置.為保證集成分類(lèi)的效率和準(zhǔn)確率，OGUEIL使用淘汰機(jī)制優(yōu)化集成結(jié)構(gòu)：每當(dāng)創(chuàng)建一個(gè)新候選分類(lèi)器時(shí)，若集成模型的成員數(shù)量沒(méi)有達(dá)到預(yù)設(shè)的最大值m，直接添加成員，否則替換權(quán)重最小的成員，這樣保證了集成模型的成員不會(huì)隨時(shí)間無(wú)限增加，降低內(nèi)存消耗.

2.2 候選分類(lèi)器訓(xùn)練

如何訓(xùn)練泛化能力強(qiáng)的候選分類(lèi)器是克服多類(lèi)別不平衡、提高少類(lèi)分類(lèi)準(zhǔn)確率的關(guān)鍵.普遍的解決方案是對(duì)多類(lèi)實(shí)例欠采樣或?qū)ι兕?lèi)實(shí)例過(guò)采樣，這2種方法都有各自的優(yōu)點(diǎn)和缺陷.本文結(jié)合過(guò)采樣和欠采樣，提出了一種基于混合采樣的候選分類(lèi)器訓(xùn)練方法(candidate classifier training, CCT)，如算法2所示.OGUEIL每隔固定周期檢測(cè)當(dāng)前窗口中各類(lèi)實(shí)例的數(shù)量是否均超過(guò)預(yù)設(shè)值β，若滿(mǎn)足則開(kāi)始訓(xùn)練T(T>1)個(gè)新候選分類(lèi)器.首先確定當(dāng)前窗口中所有類(lèi)實(shí)例數(shù)量的最大值(max)和最小值(min)，然后在min和max之間隨機(jī)取值N作為之后每類(lèi)實(shí)例的重采樣數(shù)量.對(duì)于實(shí)例數(shù)量少于N的類(lèi)，OGUEIL使用邊界人工合成少類(lèi)樣本方法(BorderlineSMOTE)[21]將其數(shù)量過(guò)采樣至N，值得注意的是，它屬于過(guò)采樣方法的一種，通過(guò)在決策邊界附近人工合成少類(lèi)樣本來(lái)平衡數(shù)據(jù)分布，既增強(qiáng)了決策邊界，又降低了過(guò)擬合的風(fēng)險(xiǎn)；而對(duì)于實(shí)例數(shù)量大于N的類(lèi)，通過(guò)隨機(jī)欠采樣(RUS)將其數(shù)量削減，最終使用類(lèi)分布相對(duì)平衡的數(shù)據(jù)集訓(xùn)練候選分類(lèi)器.由于OGUEIL每次生成不止一個(gè)候選分類(lèi)器，且每次的采樣數(shù)量都是隨機(jī)選取，因此可以最大限度減少有價(jià)值的信息的丟失.同時(shí)，由于訓(xùn)練每個(gè)候選分類(lèi)器的數(shù)據(jù)集都不同，OGUEIL會(huì)得到一組具有足夠多樣性的候選分類(lèi)器，可以增強(qiáng)整體集成分類(lèi)器的泛化能力.生成T個(gè)候選分類(lèi)器后，此時(shí)如果當(dāng)前集成規(guī)模|Ω|與T之和小于預(yù)設(shè)的集成最大成員數(shù)m，直接添加成員分類(lèi)器，否則移除集成中權(quán)重最小的成員分類(lèi)器，直至滿(mǎn)足|Ω|+T

算法2.CCT.

輸入:當(dāng)前窗口W中的數(shù)據(jù)D；

輸出:新的候選分類(lèi)器.

① 確定D中所有類(lèi)實(shí)例數(shù)量的最大值max和最小值min；

② 在[min，max]內(nèi)隨機(jī)取值N作為之后每個(gè)類(lèi)實(shí)例的重采樣數(shù)量；

③ 對(duì)實(shí)例數(shù)量少于N的類(lèi)使用Borderline-SMOTE過(guò)采樣至N；

④ 對(duì)實(shí)例數(shù)量大于N的類(lèi)使用RUS欠采樣至N；

⑤ 使用處理后的數(shù)據(jù)集D訓(xùn)練一個(gè)新的候選分類(lèi)器.

2.3 加權(quán)和決策機(jī)制

數(shù)據(jù)流集成分類(lèi)方法的加權(quán)機(jī)制大都是基于數(shù)據(jù)塊的，即每到達(dá)一個(gè)數(shù)據(jù)塊，集成中每個(gè)成員分類(lèi)器的權(quán)重由在當(dāng)前數(shù)據(jù)塊上的分類(lèi)精度決定.當(dāng)面對(duì)突變型漂移或發(fā)生在數(shù)據(jù)塊內(nèi)的漂移時(shí)，基于數(shù)據(jù)塊的加權(quán)機(jī)制難以快速調(diào)整成員分類(lèi)器的權(quán)重.此外，基于分類(lèi)精度的加權(quán)機(jī)制容易受到類(lèi)分布的影響，導(dǎo)致成員分類(lèi)器偏向多類(lèi)，忽略少類(lèi).為此本文提出了一種基于G-mean的在線(xiàn)加權(quán)機(jī)制，它的特點(diǎn)是每到達(dá)一個(gè)新實(shí)例而不是一個(gè)完整的數(shù)據(jù)塊，所有成員分類(lèi)器的權(quán)重更新一次且不受類(lèi)分布的影響.更新成員分類(lèi)器時(shí)既考慮該分類(lèi)器創(chuàng)建的時(shí)間，又考慮它在最近d個(gè)數(shù)據(jù)上的G-mean性能.二分類(lèi)數(shù)據(jù)流中，G-mean就是正類(lèi)cp上的準(zhǔn)確率PR和負(fù)類(lèi)cn上的準(zhǔn)確率NR的幾何平均值，如式(4)所示：

(4)

(5)

(6)

(7)

在時(shí)刻t，每個(gè)成員分類(lèi)器的權(quán)重通過(guò)式(8)～(11)更新:

(8)

(9)

(11)

(12)

其中,sgn(·)為符號(hào)函數(shù)，若括號(hào)中結(jié)果大于0，返回1，代表正類(lèi)cp；否則返回-1，代表負(fù)類(lèi)cn.OGUEIL的偽代碼如算法3所示：

算法3.OGUEIL.

輸入:數(shù)據(jù)流S、檢測(cè)周期d、集成模型容量m、成員分類(lèi)器Ci、少類(lèi)實(shí)例數(shù)量最小值β、滑動(dòng)窗口W、候選分類(lèi)器個(gè)數(shù)T；

輸出:加權(quán)集成模型Ω.

① while每到達(dá)一個(gè)新實(shí)例(xt,yt)

③ 根據(jù)式(2)增量計(jì)算每個(gè)類(lèi)的實(shí)例大?。?/p>

④ 根據(jù)式(3)確定當(dāng)前數(shù)據(jù)流中的少類(lèi)和多類(lèi)；

⑤ 把新實(shí)例(xt,yt)添加到窗口W中；

⑥ 根據(jù)式(8)～(11)，使用(xt,yt)更新集成中每個(gè)成員分類(lèi)器Ci的權(quán)重；

⑦ 每隔d個(gè)實(shí)例：

⑧ if窗口W中的少類(lèi)實(shí)例數(shù)量大于β：

⑨ 調(diào)用CCT算法T次，訓(xùn)練T個(gè)新的候選分類(lèi)器；

⑩ end if

2.4 計(jì)算復(fù)雜度分析

OGUEIL集成模型使用Hoeffding tree做基分類(lèi)器，Hoeffding tree學(xué)習(xí)每個(gè)實(shí)例的時(shí)間復(fù)雜度為O(1)，故含有m個(gè)Hoeffding tree的集成模型學(xué)習(xí)時(shí)間復(fù)雜度為O(m).OOB使每個(gè)Hoeffding tree訓(xùn)練k次，k服從泊松分布，OGUEIL的時(shí)間復(fù)雜度變?yōu)镺(km).每個(gè)類(lèi)的數(shù)量計(jì)算均通過(guò)增量計(jì)算，所以時(shí)間復(fù)雜度為O(1).CCT算法創(chuàng)建T個(gè)候選分類(lèi)器的時(shí)間復(fù)雜度為O(2TN)，N代表采樣數(shù)量，而每個(gè)基分類(lèi)器通過(guò)式(8)～(11)加權(quán)需要O(1)時(shí)間，對(duì)m個(gè)基分類(lèi)器加權(quán)的時(shí)間復(fù)雜度為O(m).綜上，OGUEIL的時(shí)間復(fù)雜度為O(km+2TN+m)，由于k，m，N，T均與輸入數(shù)據(jù)流的規(guī)模無(wú)關(guān)，故OGUEIL關(guān)于數(shù)據(jù)流規(guī)模的時(shí)間復(fù)雜度可解析為O(1).

關(guān)于方法的空間復(fù)雜度，由于OGUEIL使用滑動(dòng)窗口處理數(shù)據(jù)，創(chuàng)建分類(lèi)器時(shí)需存儲(chǔ)N個(gè)樣本數(shù)據(jù).因此方法的空間復(fù)雜度為O(TN)，這里T為候選分類(lèi)器個(gè)數(shù).顯然，滑動(dòng)窗口大小、采樣數(shù)量和分類(lèi)器個(gè)數(shù)均與輸入數(shù)據(jù)流的規(guī)模無(wú)關(guān)，故關(guān)于輸入數(shù)據(jù)流規(guī)模的空間復(fù)雜度仍可視為O(1).

3 實(shí)驗(yàn)結(jié)果及其分析

為驗(yàn)證OGUEIL方法的性能，本節(jié)將OGUEIL和其他5種同類(lèi)方法在人工和真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)比較.對(duì)比方法可分為2類(lèi)：一類(lèi)是基于數(shù)據(jù)塊的集成方法：DWMIL[20]，Learn++NIE[19](后面簡(jiǎn)稱(chēng)為L(zhǎng)PN)和REA[16];另一類(lèi)是在線(xiàn)集成方法：OAUE[26]，OOB[9].實(shí)驗(yàn)環(huán)境:1臺(tái)處理器為Intel Core i7-7700HQ，內(nèi)存為16 GB的筆記本電腦，運(yùn)行Windows 10系統(tǒng)和python3.7.在該環(huán)境下，分別實(shí)現(xiàn)了本文方法和對(duì)比方法,對(duì)比方法的參數(shù)設(shè)置均各參照對(duì)應(yīng)文獻(xiàn).OGUEIL的參數(shù)設(shè)置為：成員分類(lèi)器使用python的scikit-multiflow包[27]的Hoeffding tree使用默認(rèn)設(shè)置；時(shí)間衰減因子λ和類(lèi)別不平衡檢測(cè)閾值δ設(shè)置參照文獻(xiàn)[9]，分別設(shè)為0.9和0；p根據(jù)大量實(shí)驗(yàn)確定，設(shè)為500；集成最大成員數(shù)量m=15；創(chuàng)建候選分類(lèi)器所需的最小少類(lèi)實(shí)例數(shù)量β=15；ε=0.000 000 1.

3.1 性能評(píng)價(jià)指標(biāo)

本文利用以下指標(biāo)對(duì)方法進(jìn)行評(píng)價(jià)，包括二分類(lèi)數(shù)據(jù)流中的分類(lèi)準(zhǔn)確率ACC(accuracy)、幾何均值Gmean(geometry mean)、少類(lèi)召回率MCR(minority class recall)，其具體定義如式(13)(14)所示.

(14)

Table 1 Confusion Matrix表1 混淆矩陣

3.2 數(shù)據(jù)集介紹

實(shí)驗(yàn)共用到6個(gè)人工數(shù)據(jù)集和2個(gè)真實(shí)數(shù)據(jù)集，詳情如下：

Sine數(shù)據(jù)集[4].該數(shù)據(jù)集生成器有2個(gè)屬性x和y.分類(lèi)函數(shù)是y=sin(x)，在第1次漂移之前，函數(shù)曲線(xiàn)下方的實(shí)例被標(biāo)記為正類(lèi)，曲線(xiàn)上方的實(shí)例被標(biāo)記為負(fù)類(lèi)，共有2個(gè)類(lèi)別.在漂移點(diǎn)，通過(guò)反轉(zhuǎn)分類(lèi)規(guī)則來(lái)產(chǎn)生漂移.Sine共包含100 000個(gè)實(shí)例，每隔20 000個(gè)實(shí)例產(chǎn)生1次漂移，類(lèi)分布平衡，含10%噪聲.

Sea數(shù)據(jù)集[28].該數(shù)據(jù)集生成器有3個(gè)屬性，其中第3個(gè)屬性與類(lèi)別無(wú)關(guān)，如果x1+x2<α,實(shí)例分類(lèi)為正，否則為負(fù)，x1，x2表示前2個(gè)屬性.通過(guò)欠采樣生成2個(gè)新的數(shù)據(jù)集：1)Seaac通過(guò)欠采樣產(chǎn)生類(lèi)別不平衡，不平衡率(指少類(lèi)實(shí)例所占百分比)初始化為0.05，在數(shù)據(jù)流中某處會(huì)突然上升至0.95，即多類(lèi)實(shí)例變?yōu)樯兕?lèi)實(shí)例；2)Seanc通過(guò)欠采樣產(chǎn)生類(lèi)別不平衡，不平衡率固定為0.05.

Circle數(shù)據(jù)集[4].該數(shù)據(jù)集生成器有2個(gè)屬性x和y.4個(gè)不同圓方程表示4個(gè)不同概念.圓內(nèi)的實(shí)例被分類(lèi)為正，圓外為負(fù)，共2個(gè)類(lèi)別.在漂移點(diǎn)通過(guò)更換圓的方程來(lái)產(chǎn)生漂移.Circle數(shù)據(jù)集共包含50 000個(gè)實(shí)例，每隔12 500個(gè)實(shí)例產(chǎn)生1次漂移，類(lèi)分布平衡，含10%噪聲.

Hyper Plane數(shù)據(jù)集[28].該數(shù)據(jù)集生成器有10個(gè)屬性，通過(guò)連續(xù)旋轉(zhuǎn)決策超平面產(chǎn)生漂移.Hyper Planenc包含50 000個(gè)實(shí)例，不平衡率固定為0.05.

Gaussian數(shù)據(jù)集[28].該數(shù)據(jù)集生成器有2個(gè)屬性，通過(guò)改變高斯成分的均值和方差產(chǎn)生漂移.本實(shí)驗(yàn)中通過(guò)欠采樣產(chǎn)生類(lèi)別不平衡數(shù)據(jù)集Gaussiangc，不平衡率初始化為0.05，然后逐漸上升至0.95.

Electricity數(shù)據(jù)集[4].該數(shù)據(jù)集為真實(shí)數(shù)據(jù)集，收集了澳大利亞新南威爾士州電力市場(chǎng)的45 312個(gè)電價(jià)數(shù)據(jù)，包含8個(gè)屬性和2個(gè)類(lèi)別.

Weather數(shù)據(jù)集[20].該數(shù)據(jù)集為真實(shí)數(shù)據(jù)集，包含貝爾維尤和內(nèi)布拉斯加州50多年來(lái)的天氣信息.任務(wù)是預(yù)測(cè)一天是否下雨.本實(shí)驗(yàn)中通過(guò)欠采樣實(shí)現(xiàn)類(lèi)別不平衡[20]，不平衡固定為0.05，包含18 159個(gè)實(shí)例，有8個(gè)屬性和2個(gè)類(lèi)別.

表2總結(jié)了所有數(shù)據(jù)集的信息.實(shí)驗(yàn)用到的8個(gè)數(shù)據(jù)集進(jìn)一步可分為四大類(lèi)，模擬4種不同場(chǎng)景：1)概念漂移的類(lèi)平衡數(shù)據(jù)集，包括Sine，Circle，Electricity；2)有概念漂移的類(lèi)別不平衡數(shù)據(jù)集且包含不平衡率突然變化的情況，包括Seaac；3)有概念漂移的類(lèi)別不平衡數(shù)據(jù)集且包含不平衡率逐漸變化的情況，包括Gaussiangc；4)有概念漂移的類(lèi)別不平衡數(shù)據(jù)集且不平衡率固定不變，包括Seanc，Hyper Planenc.

Table 2 Description of Datasets表2 數(shù)據(jù)集的描述

3.3 參數(shù)實(shí)驗(yàn)

本節(jié)用OGUEIL的參數(shù)p(基分類(lèi)器更新周期)的不同值對(duì)算法G-mean性能進(jìn)行了實(shí)驗(yàn)，結(jié)果如表3所示.

由表3中數(shù)據(jù)可知，參數(shù)p的不同取值對(duì)OGUEIL的G-mean性能影響較小，同時(shí)p=500時(shí)在8個(gè)數(shù)據(jù)集上的平均排名最高，所以最終OGUEIL的參數(shù)p設(shè)置為500.

Table 3 G-Mean Results of OGUEIL Under Different p Values表3 不同p值下的OGUEIL的G-mean結(jié)果

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

本節(jié)比較了OGUEIL和其他5種方法在上述8個(gè)數(shù)據(jù)集上的分類(lèi)準(zhǔn)確率，G-mean和少類(lèi)召回率，結(jié)果如表4～6所示.表4給出了所有方法的8個(gè)數(shù)據(jù)集上的準(zhǔn)確率結(jié)果.根據(jù)表4可以看出：其一，Sine，Circle，Electricity 3個(gè)數(shù)據(jù)集的類(lèi)分布相對(duì)平衡，準(zhǔn)確率可以較好地反映每種方法的性能，OGUEIL在這3個(gè)數(shù)據(jù)集上準(zhǔn)確率均排在第1，表明OGUEIL可以很好地處理各種類(lèi)型概念漂移，緊接著是OAUE和DWMIL，二者結(jié)果相近；其二，在其余類(lèi)分布不平衡數(shù)據(jù)集上，OAUE均排名第1，但這不能表明OAUE處理類(lèi)別不平衡數(shù)據(jù)流中概念漂移的能力強(qiáng)于其他方法，因?yàn)閿?shù)據(jù)流的類(lèi)分布嚴(yán)重不平衡時(shí)，準(zhǔn)確率會(huì)偏向于多類(lèi)，意味著一個(gè)方法只有把所有實(shí)例預(yù)測(cè)為多類(lèi)就可以獲得很高的準(zhǔn)確率，嚴(yán)重忽略少類(lèi)實(shí)例，不能合理地反映方法性能.表5給出了各方法G-mean的實(shí)驗(yàn)結(jié)果，G-mean對(duì)類(lèi)分布不敏感，在平衡或不平衡數(shù)據(jù)流中都可很好地反映一個(gè)方法的性能.結(jié)果顯示：OGUEIL在7個(gè)數(shù)據(jù)集上平均排名最高，DWMIL次之，而OAUE的G-mean性能很差，在Weather上甚至為0，但它的準(zhǔn)確率很高，這表明它的多類(lèi)性能很好而少類(lèi)性能很差，主要因?yàn)樗鼪](méi)有處理類(lèi)別不平衡的機(jī)制，容易將少類(lèi)實(shí)例誤分類(lèi)為多類(lèi)實(shí)例.REA是針對(duì)不平衡數(shù)據(jù)流的方法，但它的G-mean性能很差，甚至弱于OAUE，主要因?yàn)樗４孢^(guò)去所有數(shù)據(jù)塊中的少類(lèi)實(shí)例，然后通過(guò)KNN(k-nearest neighbors)選擇部分少類(lèi)實(shí)例平衡當(dāng)前數(shù)據(jù)塊的類(lèi)分布，這種機(jī)制很容易受到概念漂移的影響，當(dāng)少類(lèi)上的概念發(fā)生漂移時(shí)，少類(lèi)實(shí)例會(huì)和多類(lèi)實(shí)例大量重疊，嚴(yán)重影響方法G-mean性能.少類(lèi)召回率的結(jié)果如表6所示，OGUEIL和DWMIL的平均排名并列第1，特別地，在Sine，Circle，Electricity這3個(gè)類(lèi)分布相對(duì)平衡的數(shù)據(jù)集上，OGUEIL的少類(lèi)召回率高于DWMIL，而在剩下的類(lèi)分布不平衡數(shù)據(jù)集上OGUEIL的少類(lèi)召回率低于DWMIL.結(jié)合表4，5，OGUEIL在準(zhǔn)確率和G-mean上的表現(xiàn)均優(yōu)于DWMIL，表明OGUEIL在維持少類(lèi)性能的同時(shí)沒(méi)有過(guò)多犧牲多類(lèi)的性能，在2個(gè)類(lèi)上的性能達(dá)到了最佳平衡.

Table 4 Accuracy Results of All Datasets表4 所有數(shù)據(jù)集上的準(zhǔn)確率結(jié)果

Table 5 G-Mean Results of All Datasets表5 所有數(shù)據(jù)集上G-mean結(jié)果

Table 6 Minority Class Recall Results of All Datasets表6 所有數(shù)據(jù)集上少類(lèi)召回率結(jié)果

Fig. 1 Experimental results on the Sine dataset圖1 Sine數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

Fig. 2 Experimental results on the Hyper Planenc dataset圖2 Hyper Planenc數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

圖1為Sine數(shù)據(jù)集上的結(jié)果，該數(shù)據(jù)集為類(lèi)分布平衡數(shù)據(jù)集，可以發(fā)現(xiàn)各方法在準(zhǔn)確率、G-mean和少類(lèi)召回率上的性能變化曲線(xiàn)基本一致，以圖1(a)的準(zhǔn)確率結(jié)果為例，可以得到以下觀測(cè)結(jié)果:1)OGUEIL的準(zhǔn)確率最高，OAUE和DWMIL次之，REA的準(zhǔn)確率最低，表明OGUEIL，OAUE和DWMIL的抵抗概念漂移能力較強(qiáng).2)Sine數(shù)據(jù)集每隔全部數(shù)據(jù)的20%，通過(guò)反轉(zhuǎn)分類(lèi)規(guī)則產(chǎn)生一次突變型概念漂移，OGUEIL，OAUE，DWMIL受影響較小，準(zhǔn)確率輕微下降后迅速恢復(fù)，其中OGUEIL得益于它的在線(xiàn)更新和在線(xiàn)加權(quán)機(jī)制，發(fā)生漂移后迅速更新所有成員分類(lèi)器及其權(quán)重值，最先完成新概念的學(xué)習(xí)，準(zhǔn)確率曲線(xiàn)率先上升.3)LPN，OOB，REA受概念漂移影響嚴(yán)重，尤其是REA，準(zhǔn)確率甚至下降至0.5左右，這主要因?yàn)镽EA所有成員分類(lèi)器無(wú)法增量更新，集成模型缺少成員分類(lèi)器的淘汰機(jī)制，遭遇概念漂移時(shí)，在舊概念上訓(xùn)練的大量成員分類(lèi)器既不能增量更新，也不被淘汰，從而嚴(yán)重影響性能.LPN和REA類(lèi)似，所有成員分類(lèi)器也無(wú)法增量更新，集成模型也沒(méi)有淘汰機(jī)制，但它有獨(dú)特的加權(quán)機(jī)制，LPN中每個(gè)成員分類(lèi)根據(jù)分類(lèi)性能調(diào)整權(quán)重時(shí)，會(huì)使用sigmoid函數(shù)對(duì)它在當(dāng)前數(shù)據(jù)塊上的性能和過(guò)去所有數(shù)據(jù)塊上的性能加權(quán)，可以快速地消除舊概念對(duì)當(dāng)前集成模型的影響，同時(shí)若發(fā)現(xiàn)某個(gè)成員分類(lèi)器的性能弱于隨機(jī)分類(lèi)器，該成員分類(lèi)器的權(quán)重置則被設(shè)置為0，消除它對(duì)最終決策的負(fù)面影響，故它處理概念漂移的能力強(qiáng)于REA.OOB沒(méi)有加權(quán)機(jī)制和成員分類(lèi)器淘汰機(jī)制，但它的成員分類(lèi)器是在線(xiàn)分類(lèi)器，遭遇概念漂移時(shí)通過(guò)在線(xiàn)更新緩慢適應(yīng)新的概念，整體效果略好于REA.

圖2為Hyper Planenc上的結(jié)果，該數(shù)據(jù)集是類(lèi)分布不平衡的且不平衡率固定為5%，包含漸變型概念漂移.OAUE的準(zhǔn)確率始終保持較高水平，但這以嚴(yán)重犧牲少類(lèi)上的性能為前提，它的少類(lèi)召回率遠(yuǎn)低于其他方法.OGUEIL在3個(gè)評(píng)價(jià)指標(biāo)上的性能曲線(xiàn)都沒(méi)有較大波動(dòng)，始終保持著較高的水平，表現(xiàn)出較強(qiáng)的抗概念漂移能力.并且它在準(zhǔn)確率和少類(lèi)召回率上排名第2，在G-mean上排名第1，這表明OGUEIL很好地平衡了在每個(gè)類(lèi)上的性能.DWMIL在少類(lèi)召回率上性能很好，排名第1，但它準(zhǔn)確率排在第5，這表明DWMIL以大幅犧牲多類(lèi)上的性能為代價(jià)提高它在少類(lèi)上的性能，處理類(lèi)分布不平衡的策略有些激進(jìn).LPN的G-mean曲線(xiàn)和DWMIL的G-mean曲線(xiàn)十分接近，但它的少類(lèi)召回率低于DWMIL少類(lèi)召回率而準(zhǔn)確率高于LPN的準(zhǔn)確率，表明LPN處理類(lèi)分布不平衡的策略較DWMIL保守一些，沒(méi)有為了提高少類(lèi)上的性能而過(guò)多犧牲多類(lèi)上的性能.OOB和REA在少類(lèi)召回率上保持穩(wěn)定，都高于OAUE的少類(lèi)召回率，但在準(zhǔn)確率和G-mean上低于OAUE的且存在較大的波動(dòng)，主要因?yàn)樗鼈儗?duì)概念漂移的響應(yīng)較慢，影響了在多類(lèi)上的性能.

Fig. 3 Experimental results on the Seaac dataset圖3 Seaac數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

Fig. 4 Experimental results on the Gaussiangc dataset圖4 Gaussiangc數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果

圖3給出了各方法在Seaac上的實(shí)驗(yàn)結(jié)果，該數(shù)據(jù)集是包含漸變漂移的類(lèi)分布不平衡數(shù)據(jù)集，而且不平衡率會(huì)在數(shù)據(jù)集中發(fā)生突變，導(dǎo)致多類(lèi)實(shí)例和少類(lèi)實(shí)例的角色互換，因此在不平衡率變化處重置所有評(píng)價(jià)指標(biāo)，如圖3中虛線(xiàn)所示(數(shù)據(jù)流40%的位置，虛線(xiàn)和實(shí)線(xiàn)部分重合).OGUEIL在各項(xiàng)性能指標(biāo)上一直比較穩(wěn)定，不平衡率突變后，它會(huì)根據(jù)當(dāng)前數(shù)據(jù)流中類(lèi)分布快速識(shí)別出多類(lèi)實(shí)例和少類(lèi)實(shí)例，然后調(diào)整集成中的所有成員分類(lèi)器過(guò)采樣的目標(biāo)，性能恢復(fù)最快，最終在準(zhǔn)確率上排名第2，G-mean上排名第1，少類(lèi)召回率上排名第4.而LPN，DWMIL，OOB，REA的恢復(fù)速度依次遞減.至于OAUE，它在準(zhǔn)確率上受不平衡率突變影響最小，始終保持較高水平，原因與Hyper Planenc數(shù)據(jù)集上的相同，但它在G-mean和少類(lèi)召回率上波動(dòng)很大，在不平衡率突變前，隨著少類(lèi)實(shí)例的增加，各項(xiàng)性能逐漸上升，突變后，由于缺乏處理類(lèi)分布不平衡機(jī)制，一直處在下降狀態(tài).值得注意的是，REA的少類(lèi)召回率在不平衡率突變前很低，突變后，少類(lèi)召回率大幅上升，甚至最后排名第1，這是因?yàn)橥蛔兦癛EA將大量多類(lèi)實(shí)例預(yù)測(cè)為少類(lèi)實(shí)例，突變后，多類(lèi)實(shí)例變?yōu)樯兕?lèi)實(shí)例，從而獲得了較高的少類(lèi)召回率.

圖4為Gaussiangc上的結(jié)果，該數(shù)據(jù)集是包含漸變漂移的類(lèi)分布不平衡數(shù)據(jù)集，而且不平衡率會(huì)在數(shù)據(jù)集中逐漸發(fā)生變化，數(shù)據(jù)流的狀態(tài)由不平衡逐漸變到平衡然后又到不平衡，因此在2次不平衡率變化處重置所有評(píng)價(jià)指標(biāo)，如圖4中虛線(xiàn)所示.在第1次不平衡率變化后，數(shù)據(jù)流狀態(tài)由類(lèi)分布嚴(yán)重不平衡逐步過(guò)渡到平衡狀態(tài)，除REA外所有方法的性能都保持穩(wěn)定或上升狀態(tài).第2次變化后，數(shù)據(jù)流又從平衡狀態(tài)轉(zhuǎn)變至不平衡狀態(tài)，多類(lèi)實(shí)例變?yōu)樯兕?lèi)實(shí)例，而少類(lèi)實(shí)例變?yōu)槎囝?lèi)實(shí)例，由于類(lèi)分布的變化，所有方法的性能都有所下跌，然后隨數(shù)據(jù)流增加逐漸上升.OGUEIL的準(zhǔn)確率基本保持穩(wěn)定，最終排名第2，在G-mean和少類(lèi)召回率上在短暫下降后迅速恢復(fù)，最終排名分別為第1和第3，整體上在3個(gè)性能指標(biāo)上沒(méi)有出現(xiàn)較大波動(dòng)，始終保持較高水平，表明OGUEIL有效地降低了概念漂移和類(lèi)分布變化對(duì)集成性能的影響.除了少類(lèi)召回率，REA和LPN在準(zhǔn)確率和G-mean上均顯著低于沒(méi)有處理類(lèi)分布不平衡機(jī)制的OAUE的準(zhǔn)確率和G-mean，可能的原因是該數(shù)據(jù)集上的概念漂移嚴(yán)重影響了REA和LPN在多類(lèi)實(shí)例上的準(zhǔn)確率.

3.5 運(yùn)行時(shí)間比較

8個(gè)數(shù)據(jù)集上，所有方法的運(yùn)行時(shí)間如表7所示.平均運(yùn)行時(shí)間最短的是OOB，主要因?yàn)镺OB的方法結(jié)構(gòu)簡(jiǎn)單，它沒(méi)有加權(quán)機(jī)制，沒(méi)有成員分類(lèi)器的添加和淘汰機(jī)制，也無(wú)需保存任何歷史數(shù)據(jù)，只需維護(hù)集成模型在線(xiàn)更新和對(duì)少類(lèi)實(shí)例的過(guò)采樣.OGUEIL在所有數(shù)據(jù)集上的運(yùn)行時(shí)間都慢于OAUE，二者的加權(quán)和集成模型成員的創(chuàng)建、添加和淘汰操作的耗時(shí)相近，主要差別在于OGUEIL整合了OOB，集成模型的在線(xiàn)更新比OAUE增加了少類(lèi)實(shí)例的過(guò)采樣.REA集成模型的成員分類(lèi)器為靜態(tài)批處理方法，無(wú)法在線(xiàn)更新，減少了時(shí)間消耗，但是它的集成模型沒(méi)有淘汰機(jī)制，會(huì)保留所有成員分類(lèi)器，同時(shí)它需要從歷史數(shù)據(jù)塊中尋找k個(gè)最近鄰用以平衡當(dāng)前數(shù)據(jù)塊的類(lèi)分布，這些機(jī)制導(dǎo)致了REA在小規(guī)模數(shù)據(jù)集上的運(yùn)行效率較高，例如Electricity,Gaussianac等，而大規(guī)模的數(shù)據(jù)集上效率較低，例如Sine，Circle等，因?yàn)閿?shù)據(jù)量越大，REA創(chuàng)建的成員分類(lèi)器越多，搜索k個(gè)最近鄰的耗時(shí)也越高.DWMIL和LPN的運(yùn)行時(shí)間明顯高于其他方法，主要因?yàn)槎叨际褂糜扇舾伸o態(tài)批處理分類(lèi)器組成的集成分類(lèi)器作為集成模型的成員分類(lèi)器，不過(guò)DWMIL的集成模型有剪枝策略，LPN沒(méi)有，這就意味著LPN的規(guī)模會(huì)隨數(shù)據(jù)流無(wú)限擴(kuò)大，導(dǎo)致決策時(shí)間消耗越來(lái)越大.此外，LPN在權(quán)重計(jì)算階段，不僅要考慮每個(gè)成員分類(lèi)器在當(dāng)前數(shù)據(jù)塊上的性能，還要考慮它在之前每個(gè)數(shù)據(jù)塊上的性能，這也會(huì)嚴(yán)重增加時(shí)間消耗.

Table 7 Comparison of Running Time表7 運(yùn)行時(shí)間對(duì)比 s

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

本文針對(duì)數(shù)據(jù)流中存在概念漂移和類(lèi)別不平衡的問(wèn)題，提出了一種新的不平衡數(shù)據(jù)流分類(lèi)方法OGUEIL，它基于集成學(xué)習(xí)框架，綜合基于數(shù)據(jù)塊的方法和在線(xiàn)方法的優(yōu)點(diǎn)，可以有效處理不平衡數(shù)據(jù)流中的概念漂移.OGUEIL是基于完全增量的方法，無(wú)需保存任何歷史數(shù)據(jù)，使用在線(xiàn)分類(lèi)器作為成員分類(lèi)器，每到達(dá)一個(gè)實(shí)例，對(duì)集成模型中的所有成員在線(xiàn)更新的同時(shí)根據(jù)每個(gè)成員在最近若干數(shù)據(jù)上的G-mean性能加權(quán)，性能越好的成員獲得權(quán)重值也越大.每隔固定周期，OGUEIL檢查當(dāng)前是否滿(mǎn)足創(chuàng)建新候選分類(lèi)器條件，若滿(mǎn)足就通過(guò)混合采樣創(chuàng)建多個(gè)具有差異性的候選分類(lèi)器，然后選擇性地添加至集成中，并使用2種淘汰機(jī)制控制集成模型的規(guī)模，保持決策的高效性和準(zhǔn)確性.

本文利用6個(gè)人工數(shù)據(jù)集和2個(gè)真實(shí)數(shù)據(jù)集模擬了4種不同場(chǎng)景，對(duì)OGUEIL與5種主流的同類(lèi)方法進(jìn)行了全面的對(duì)比實(shí)驗(yàn).結(jié)果表明，OGUEIL在少類(lèi)數(shù)據(jù)上保持良好性能的同時(shí)沒(méi)有犧牲在多類(lèi)數(shù)據(jù)上的性能，在平衡與不平衡數(shù)據(jù)流下都可以有效處理概念漂移，綜合性能優(yōu)于其它方法，具有較強(qiáng)的魯棒性.

作者貢獻(xiàn)聲明：梁斌提出了算法思路和實(shí)驗(yàn)方案，完成實(shí)驗(yàn)并撰寫(xiě)論文；李光輝和代成龍?zhí)岢隽酥笇?dǎo)意見(jiàn)并修改論文.