基于動(dòng)態(tài)加權(quán)函數(shù)的集成分類(lèi)算法

王 樂(lè)，韓 萌，李小娟，張 妮，程浩東

（北方民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，銀川 750021）

0 引言

在動(dòng)態(tài)變化和非平穩(wěn)環(huán)境中數(shù)據(jù)以流的形式到達(dá)，要從大量的數(shù)據(jù)中獲取有用的知識(shí)，數(shù)據(jù)流挖掘方法在大數(shù)據(jù)領(lǐng)域起著重要的作用。為了適應(yīng)不斷變化的數(shù)據(jù)流，將數(shù)據(jù)流更有效地轉(zhuǎn)變?yōu)橛杏玫男畔⒐┤藗冊(cè)谏钪惺褂茫煞诸?lèi)無(wú)疑是一種優(yōu)秀的挖掘數(shù)據(jù)流的方法。集成分類(lèi)算法之所以受到眾多研究者的青睞，是因?yàn)榧煞诸?lèi)器由多個(gè)準(zhǔn)確而多樣的基分類(lèi)器組成，可以形成分類(lèi)決策，采用不同的加權(quán)方式可以構(gòu)建多種多樣的決策，從而使其性能優(yōu)于單個(gè)分類(lèi)器。在集成方法中，Bagging和Boosting被認(rèn)為是最流行和最有效的方法。Bagging 是一種引導(dǎo)聚集算法，生成不同的模型并使用這些模型獲得集成分類(lèi)器的方法。它通過(guò)降低基分類(lèi)器的方差改善了泛化誤差，使用不同的模型對(duì)實(shí)例進(jìn)行預(yù)測(cè)，在預(yù)測(cè)類(lèi)別時(shí)進(jìn)行多數(shù)票投票對(duì)模型進(jìn)行平均操作，最后提高整個(gè)分類(lèi)器的準(zhǔn)確性。Boosting 通過(guò)對(duì)樣本集進(jìn)行操作得到樣本子集，將弱分類(lèi)算法作為基分類(lèi)器放入Boosting 框架中然后對(duì)訓(xùn)練樣本集進(jìn)行訓(xùn)練生成基分類(lèi)器，重復(fù)運(yùn)行給定的弱學(xué)習(xí)算法，這樣經(jīng)過(guò)

n

輪迭代就會(huì)產(chǎn)生

n

個(gè)基分類(lèi)器，把這樣的分類(lèi)器集成在一起就可以提高弱分類(lèi)算法的識(shí)別率。除去Bagging 和Boosting 這兩個(gè)經(jīng)常被提及使用的算法，Stacking 同樣受到眾多研究學(xué)者的青睞，Stacking 是集成學(xué)習(xí)的第三類(lèi)，廣泛應(yīng)用于有監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)領(lǐng)域，基分類(lèi)器的輸入屬性和學(xué)習(xí)策略對(duì)Stacking 的性能有很大的影響。例如，Todorovski 等提出了一種稱(chēng)為元決策樹(shù)（Meta Decision Tree，MDT）的Stacking 方法來(lái)改進(jìn)集成學(xué)習(xí)過(guò)程。Zhu 等還提出了一種稱(chēng)為Stacking 數(shù)據(jù)包絡(luò)分析（Data Envelopment Analysis，DEA）的方法來(lái)找出最佳Stacking 方式。David 等提出了一種新穎的通用面向?qū)ο笸镀焙图訖?quán)自適應(yīng)Stacking 框架，用于利用分類(lèi)器集成進(jìn)行預(yù)測(cè)。這個(gè)通用框架基于任何一組基礎(chǔ)學(xué)習(xí)器的概率的加權(quán)平均值運(yùn)行，最終預(yù)測(cè)是它們各自投票的總和。

雖然集成分類(lèi)算法已經(jīng)可以處理一些數(shù)據(jù)流的分類(lèi)問(wèn)題，但是在基分類(lèi)器的加權(quán)以及動(dòng)態(tài)更新以及基分類(lèi)器的選擇上仍然存在一些問(wèn)題，在分類(lèi)的過(guò)程中產(chǎn)生的這些問(wèn)題仍然會(huì)影響分類(lèi)的準(zhǔn)確率和時(shí)空效率。所以針對(duì)現(xiàn)有的集成分類(lèi)算法，本文設(shè)計(jì)了一種基于動(dòng)態(tài)加權(quán)函數(shù)的集成分類(lèi)算法，主要工作如下：

1）本文提出了一個(gè)加權(quán)函數(shù)

F

（

x

，

y

，

d

，

θ

）調(diào)節(jié)基分類(lèi)器權(quán)重，將其應(yīng)用于基分類(lèi)器的評(píng)價(jià)以選擇更適合的分類(lèi)器，其中：

x

表示實(shí)例，

y

表示實(shí)例的類(lèi)別，

d

表示數(shù)據(jù)塊中的樣本個(gè)數(shù)，

θ

表示兩個(gè)權(quán)重的折中系數(shù)；該加權(quán)函數(shù)采用精度權(quán)重和性能權(quán)重按一定比例計(jì)算的綜合權(quán)重來(lái)對(duì)基分類(lèi)器進(jìn)行加權(quán)，通過(guò)這個(gè)加權(quán)函數(shù)的評(píng)價(jià)結(jié)果選出最優(yōu)的分類(lèi)器增加集成的性能。2）為更好地提升集成分類(lèi)器的性能，本文還設(shè)置了候選分類(lèi)器對(duì)基分類(lèi)器進(jìn)行替換，并提出了一個(gè)權(quán)重函數(shù)

G

（

x

，

y

，

θ

），其中：

x

表示最新數(shù)據(jù)塊上的實(shí)例，

y

表示

x

的類(lèi)別，

θ

表示兩個(gè)權(quán)重的折中系數(shù)；通過(guò)這個(gè)函數(shù)可以得到候選分類(lèi)的權(quán)重，候選分類(lèi)器替換集成中最差的分類(lèi)器，就可以得到更好的分類(lèi)結(jié)果。

3）本文提出了一種基于動(dòng)態(tài)加權(quán)函數(shù)的集成分類(lèi)算法（Ensemble classification algorithm based on Dynamic Weighting function，EDW），使用不斷更新的數(shù)據(jù)塊訓(xùn)練分類(lèi)器，使用候選分類(lèi)器來(lái)替換集成中最差的分類(lèi)器，采用了兩個(gè)加權(quán)函數(shù)動(dòng)態(tài)更新基分類(lèi)器，其中基分類(lèi)器選用泰勒定理和正態(tài)分布性質(zhì)的不等式的決策樹(shù)。

1 相關(guān)工作

在集成分類(lèi)算法的相關(guān)研究中，除了基于Bagging、Boosting 和Stacking 的算法，基于塊的算法在集成分類(lèi)中仍然是一個(gè)研究熱點(diǎn)。基于塊的集成輸入固定大小的樣本塊重新評(píng)估集成分類(lèi)器，并用根據(jù)最新樣本訓(xùn)練的分類(lèi)器替換最差的基分類(lèi)器。動(dòng)態(tài)加權(quán)多數(shù)不平衡學(xué)習(xí)（Dynamic Weighted Majority for Imbalance Learning，DWMIL）逐塊處理不平衡的數(shù)據(jù)流使其更加穩(wěn)定。DWMIL 為每個(gè)塊創(chuàng)建一個(gè)基分類(lèi)器，并根據(jù)在當(dāng)前塊上測(cè)試的性能來(lái)衡量它們。因此，最近訓(xùn)練的分類(lèi)器或類(lèi)似于當(dāng)前塊的概念將在集成中獲得高權(quán)重。因此，如果當(dāng)前的概念與創(chuàng)建分類(lèi)器時(shí)的概念相似，則分類(lèi)器可以持續(xù)更長(zhǎng)的時(shí)間來(lái)對(duì)預(yù)測(cè)作出貢獻(xiàn)?；谧赃m應(yīng)塊的動(dòng)態(tài)加權(quán)多數(shù)（Adaptive Chunk-based Dynamic Weighted Majority，ACDWM）是一種基于塊的增量學(xué)習(xí)方法，可以處理包含概念漂移的不平衡流數(shù)據(jù)。ACDWM 利用集成框架，根據(jù)當(dāng)前數(shù)據(jù)塊的分類(lèi)性能動(dòng)態(tài)加權(quán)各個(gè)分類(lèi)器。通過(guò)統(tǒng)計(jì)假設(shè)檢驗(yàn)自適應(yīng)地選擇數(shù)據(jù)塊大小，以判斷基于當(dāng)前數(shù)據(jù)塊構(gòu)建的分類(lèi)器是否足夠穩(wěn)定。因?yàn)锳CDWM是完全增量的所以不需要存儲(chǔ)之前的數(shù)據(jù)，并且在概念漂移環(huán)境下可以自適應(yīng)地選擇塊的大小，相較于最先進(jìn)的基于塊的方法和在線(xiàn)方法ACDWM 效果都很出色。Ren 等提出了一種基于塊的數(shù)據(jù)流分類(lèi)器稱(chēng)為知識(shí)最大化集成（Knowledge-Maximized Ensemble，KME），KME 算法結(jié)合了在線(xiàn)集成和基于塊的集成的元素，可以用有限的標(biāo)記觀測(cè)來(lái)解決各種各樣的漂移場(chǎng)景，保存過(guò)去塊中的標(biāo)簽，被重復(fù)使用以提高候選分類(lèi)器的識(shí)別能力，可以最大限度地利用數(shù)據(jù)流中的相關(guān)信息，這對(duì)于訓(xùn)練數(shù)據(jù)有限的模型是至關(guān)重要的。KME 算法還可以使用監(jiān)督知識(shí)和非監(jiān)督知識(shí)識(shí)別周期性概念，評(píng)估集成成員的權(quán)重。精度更新集成（Accuracy Updated Ensemble，AUE2）結(jié)合了精確的基于塊的加權(quán)機(jī)制和Hoeffding 樹(shù)的增量特性，在訓(xùn)練樣本中固定大小的塊中順序地生成基分類(lèi)器，當(dāng)一個(gè)新塊到達(dá)集成時(shí)，現(xiàn)有的基分類(lèi)器被評(píng)估并更新它們的組合權(quán)重。在集成中加入從最近塊中學(xué)習(xí)到的分類(lèi)器，并根據(jù)評(píng)價(jià)結(jié)果刪除最弱的分類(lèi)器。

動(dòng)態(tài)加權(quán)多數(shù)（Dynamic Weighted Majority，DWM）算法是一種增量集成算法，在每個(gè)樣本輸入后，根據(jù)遞增的分類(lèi)器的準(zhǔn)確率對(duì)其進(jìn)行加權(quán)。每當(dāng)DWM 的一個(gè)基分類(lèi)器分類(lèi)錯(cuò)誤，它的權(quán)重就會(huì)按用戶(hù)指定的因子降低。動(dòng)態(tài)更新集成（Dynamic Updated Ensemble，DUE）算法循序漸進(jìn)地學(xué)習(xí)新的概念，不需要訪(fǎng)問(wèn)以前的知識(shí)，同時(shí)采用分段加權(quán)法加權(quán)，先前集成成員的權(quán)重基于其在最新實(shí)例和穩(wěn)定性水平上的表現(xiàn)，通過(guò)使用動(dòng)態(tài)調(diào)整基準(zhǔn)組權(quán)重的方法還可以解決概念漂移問(wèn)題。Zhao 等提出了一種加權(quán)混合Boosting集成方法（Weighted Hybrid Ensemble Method on Boosting，WHMBoost）對(duì)二值分類(lèi)數(shù)據(jù)集進(jìn)行分類(lèi)并結(jié)合了兩種數(shù)據(jù)采樣方法和兩種基本分類(lèi)器，每個(gè)采樣方法和每個(gè)基分類(lèi)器都分配有相應(yīng)的權(quán)重，以便它們?cè)谀Ｐ陀?xùn)練中有不同的貢獻(xiàn)。該算法綜合了多采樣方法和多基分類(lèi)器的優(yōu)點(diǎn)，提高了系統(tǒng)的整體性能。Ancy 等提出了一種基于權(quán)值機(jī)制的集成成員更新的方法來(lái)處理概念漂移，集成分類(lèi)器利用增量分類(lèi)器作為加權(quán)組件，根據(jù)數(shù)據(jù)類(lèi)別為候選模型分配權(quán)重，較高的權(quán)重表示分類(lèi)器可以獲得更好的準(zhǔn)確性，如果分類(lèi)器表現(xiàn)不佳，則分配一個(gè)較低的權(quán)重。當(dāng)達(dá)到集成大小時(shí)，候選分類(lèi)器將替換最差的分類(lèi)器，否則直接將候選分類(lèi)器附加為集合的成員。Sidhu 等提出了一種多樣化動(dòng)態(tài)加權(quán)多數(shù)（Diversified Dynamic Weighted Majority，DDWM）的在線(xiàn)集成方法，來(lái)分類(lèi)具有不同概念分布的新數(shù)據(jù)實(shí)例，以便準(zhǔn)確地處理各種類(lèi)型的概念漂移。如果集成中的分類(lèi)器錯(cuò)誤的分類(lèi)了給定的實(shí)例，那么就將該分類(lèi)器的權(quán)重減少一個(gè)固定的乘數(shù)，如果在后續(xù)訓(xùn)練中該分類(lèi)器仍然表現(xiàn)不佳，當(dāng)其權(quán)重達(dá)到一個(gè)固定的閾值，就將該分類(lèi)器從集成中刪除，還使用了一個(gè)固定的參數(shù)來(lái)控制權(quán)重的更新以及分類(lèi)器的創(chuàng)建和修剪，使其在具有概念漂移的數(shù)據(jù)集中取得更好的分類(lèi)效果。

2 本文算法

為了使算法更易描述，現(xiàn)對(duì)算法要用到的一些問(wèn)題進(jìn)行符號(hào)化，其中

B

表示第

i

個(gè)數(shù)據(jù)塊，數(shù)據(jù)塊中包含

n

個(gè)實(shí)例，分別為(

x

，

y

)，(

x

，

y

)，…，(

x

，

y

)，

x

是特征向量，

y

是類(lèi)標(biāo)簽，

ε

表示分類(lèi)器的集合，其中分類(lèi)器有

k

個(gè)。隨著數(shù)據(jù)塊的不斷更新，數(shù)據(jù)流也在不斷變化，舊的數(shù)據(jù)已經(jīng)不能代表最新的概念，訓(xùn)練出的分類(lèi)器也不能得到一個(gè)很好的結(jié)果，所以算法就要對(duì)基分類(lèi)器進(jìn)行更新與代替，本文采用的集成成員的更新方法是使用精度權(quán)重以及性能權(quán)重的綜合權(quán)重來(lái)對(duì)其分類(lèi)器進(jìn)行調(diào)整，以替換掉效果不好的分類(lèi)器使整個(gè)集成算法達(dá)到最優(yōu)的效果。

2.1 權(quán)重更新方法與基分類(lèi)器

2.1.1 集成成員精度權(quán)重更新新方法

精度更新集成算法維護(hù)一個(gè)加權(quán)的基分類(lèi)器池，并通過(guò)使用加權(quán)投票規(guī)則，結(jié)合基分類(lèi)器的預(yù)測(cè)結(jié)果來(lái)預(yù)測(cè)傳入樣本的類(lèi)別。在處理完每個(gè)數(shù)據(jù)塊之后，創(chuàng)建一個(gè)分類(lèi)器，替換性能最差的集成成員。根據(jù)在最新數(shù)據(jù)塊中對(duì)樣本數(shù)據(jù)估計(jì)其預(yù)期的預(yù)測(cè)誤差，可以評(píng)估每個(gè)基分類(lèi)器的性能。在替換了表現(xiàn)最差的分類(lèi)器后，對(duì)其余的集成成員進(jìn)行更新，即增量訓(xùn)練，并根據(jù)它們的精度調(diào)整其權(quán)重。

傳統(tǒng)的精度集成更新算法使用均方誤差（Mean Square Error，MSE）用來(lái)計(jì)算分類(lèi)器的均方誤差進(jìn)而計(jì)算權(quán)重，例如精度更新集成AUE2，MSE 顯示了實(shí)際類(lèi)標(biāo)簽

y

的估計(jì)概率的誤差，一個(gè)給出精確概率估計(jì)的模型可以降低該誤差。雖然它使用真后驗(yàn)概率

P

(

y

|

x

)作為初始定義的答案，但在真實(shí)數(shù)據(jù)集中通常不知道

P

（

x|y

）。一般情況下，MSE是根據(jù)經(jīng)驗(yàn)計(jì)算的假設(shè)

P

(

y

|

x

)=1。在文獻(xiàn)［15］中，提出了MSE 分類(lèi)器評(píng)價(jià)指標(biāo)計(jì)算公式：

MSE

通常被用作估計(jì)概率的度量，其中分子為誤差平方和，分母的值為自由度；但是如果概率估計(jì)不穩(wěn)定，即使模型能夠正確地預(yù)測(cè)出所有的類(lèi)標(biāo)簽，

MSE

仍然會(huì)變得很高，計(jì)算出的值無(wú)法更好地選擇分類(lèi)器，所以，F(xiàn)an 等引入了改進(jìn)后的平方誤差（Integrated Square Error，ISE）。ISE 僅在模型對(duì)樣本分類(lèi)錯(cuò)誤時(shí)才會(huì)解釋概率誤差。也就是說(shuō)，ISE 將準(zhǔn)確率和

MSE

結(jié)合成一個(gè)值，并且假設(shè)二進(jìn)制分類(lèi)中估計(jì)概率的預(yù)測(cè)閾值固定為0.5。ISE 分類(lèi)器評(píng)價(jià)指標(biāo)計(jì)算公式為：

使用改進(jìn)后的平方誤差I(lǐng)SE 作為新的度量方法，就可以避免使用MSE 時(shí)出現(xiàn)概率估計(jì)不穩(wěn)定產(chǎn)生錯(cuò)誤的情況。將改進(jìn)后的均方誤差公式代入基于塊的數(shù)據(jù)流的思想中就可以得到式（3）：

其中：函數(shù)

P

(

y

|

x

)表示分類(lèi)器

C

給出的

x

是屬于類(lèi)

y

的實(shí)例的概率，數(shù)據(jù)塊

B

上有

d

個(gè)樣本，不考慮單個(gè)類(lèi)的預(yù)測(cè)，而是考慮所有類(lèi)的概率；

ISE

的值表示在塊

B

上的分類(lèi)器

C

的預(yù)測(cè)誤差，數(shù)據(jù)塊

B

上有

d

個(gè)樣本。AUE2 算法中提出的隨機(jī)預(yù)測(cè)的分類(lèi)器的均方誤差

MSE

公式為：

其中：

p

(

y

)是類(lèi)別

y

的分布，可以通過(guò)式（3）～（4）計(jì)算數(shù)據(jù)塊上的分類(lèi)器的預(yù)測(cè)誤差和隨機(jī)預(yù)測(cè)分類(lèi)器的均方誤差，從而提出并計(jì)算基分類(lèi)器的權(quán)重公式

f

(

x

，

y

，

d

)：

ISE

的值表示在塊

B

上的分類(lèi)器

C

的預(yù)測(cè)誤差，而

MSE

是隨機(jī)預(yù)測(cè)的分類(lèi)器的均方誤差，并用作當(dāng)前類(lèi)別分布的參考點(diǎn)。另外一個(gè)非常小的正值

ε

是為了避免被零除的問(wèn)題。式（5）中給出的權(quán)重公式旨在結(jié)合分類(lèi)器的準(zhǔn)確率信息和當(dāng)前的類(lèi)分布情況，因?yàn)楸疚氖褂玫臋?quán)重公式是非線(xiàn)性函數(shù)，與類(lèi)似于精度加權(quán)集成（Accuracy Weighted Ensemble，AWE）算法中使用的線(xiàn)性函數(shù)相比，本文提出的EDW 可以高度區(qū)分基分類(lèi)器。除了給集成成員分配新的權(quán)重，每個(gè)數(shù)據(jù)塊

B

都用一個(gè)被記為

C

′的候選分類(lèi)器，這個(gè)分類(lèi)器是從最近塊中的樣本中創(chuàng)建的。

C

′在最近的數(shù)據(jù)上訓(xùn)練，并且把它當(dāng)作為一個(gè)“完美”分類(lèi)器，同時(shí)根據(jù)如下公式分配一個(gè)精度權(quán)重。EDW 不但為集成中的成員分配權(quán)重，同時(shí)還維護(hù)一個(gè)候選分類(lèi)器池，為每個(gè)數(shù)據(jù)塊

B

都分配一個(gè)候選分類(lèi)器

C

′，并且把這個(gè)候選分類(lèi)器

C

′默認(rèn)為一個(gè)沒(méi)有誤差的分類(lèi)器，其中，候選分類(lèi)器的權(quán)重計(jì)算公式如式（6）所示：

與用于給當(dāng)前的集成成員分配權(quán)重的函數(shù)相比，候選分類(lèi)器的權(quán)重沒(méi)有考慮

C

′在

B

數(shù)據(jù)塊上的預(yù)測(cè)誤差，這種方法是基于最近的數(shù)據(jù)塊能夠最好地表示當(dāng)前和未來(lái)的數(shù)據(jù)分布的假設(shè)決定的。因?yàn)?p>C

′是在最近的數(shù)據(jù)上訓(xùn)練的，它應(yīng)該被視為可能是最佳的分類(lèi)器。

2.1.2 集成成員性能權(quán)重更新方法

在對(duì)基分類(lèi)器的精度權(quán)重進(jìn)行了計(jì)算之后，下面將對(duì)基分類(lèi)器的性能權(quán)重進(jìn)行計(jì)算，因?yàn)樵谙惹皵?shù)據(jù)塊上訓(xùn)練的基分類(lèi)器的權(quán)重是基于最新數(shù)據(jù)塊中樣本的分類(lèi)性能的，由此本文提出了式（7）對(duì)最新數(shù)據(jù)中的基分類(lèi)器進(jìn)行性能權(quán)重的更新，性能權(quán)重用

h

（

x，y

）表示：

式（7）中給出的績(jī)效權(quán)重結(jié)合了分類(lèi)績(jī)效和當(dāng)前類(lèi)別分布的因素，之前的基分類(lèi)器的性能權(quán)重應(yīng)與

ISE

成反比。因此，保留的先前基分類(lèi)器的性能權(quán)重需要評(píng)估當(dāng)前數(shù)據(jù)塊的均方誤差。通常認(rèn)為最新塊的數(shù)據(jù)分布是當(dāng)前和未來(lái)一段時(shí)間概念的最佳代表，因此，可以不管其分類(lèi)性能如何將候選分類(lèi)器

C

′的性能權(quán)重直接設(shè)定為最優(yōu)值。用

f

′(

y

)表示的候選分類(lèi)器

C

′的性能權(quán)重可以表示為：

候選分類(lèi)器

C

′的性能權(quán)重與隨機(jī)預(yù)測(cè)的均方誤差成正比。因此，候選集成成員的判別能力僅考慮當(dāng)前的類(lèi)分布。因?yàn)樵谑剑?）提出的性能權(quán)重不需要計(jì)算模型的均方誤差，所以不需要額外的驗(yàn)證集來(lái)驗(yàn)證

C

′的分類(lèi)性能。因此該算法的加權(quán)機(jī)制不需要交叉驗(yàn)證過(guò)程，該過(guò)程適合處理快速數(shù)據(jù)流。同時(shí)，如果將候選分類(lèi)器視為最佳成員，則該算法可以很好地應(yīng)對(duì)突然的概念漂移。

最后提出式（9）～（10），通過(guò)公式可以得到的集成的綜合權(quán)重，其定義為精度權(quán)重和穩(wěn)定性權(quán)重的組合，如下所示：

其中：

F

(

x

，

y

，

d

，

θ

)計(jì)算分類(lèi)器的權(quán)重，

G

(

x

，

y

，

θ

)計(jì)算候選分類(lèi)器

C

′的權(quán)重；

f

(

x

，

y

，

d

)和

h

(

x

，

y

)分別是基分類(lèi)器精度權(quán)重和性能權(quán)重函數(shù)；

g

(

x

，

y

)和

w

(

x

，

y

)分別是候選分類(lèi)器的精度權(quán)重和性能權(quán)重函數(shù)；

θ

是性能權(quán)重和基分類(lèi)器的穩(wěn)定性之間的折中系數(shù)，通常取

θ

=0.5。

2.1.3 基分類(lèi)器的選擇

本文提出的集成算法使用基于泰勒定理和正態(tài)分布的性質(zhì)推導(dǎo)出的不等式來(lái)作為分裂節(jié)點(diǎn)判斷標(biāo)準(zhǔn)的決策樹(shù)作為基分類(lèi)器，這種決策樹(shù)不僅適用于數(shù)值型數(shù)據(jù)也適用于具有名稱(chēng)型屬性值的數(shù)據(jù)，而且還易于解決概念漂移問(wèn)題，該不等式可以根據(jù)有限的數(shù)據(jù)樣本進(jìn)行分割并且辨別當(dāng)前節(jié)點(diǎn)的最佳屬性其是否也是整個(gè)數(shù)據(jù)流的最佳屬性。分裂節(jié)點(diǎn)的判斷標(biāo)準(zhǔn)公式為：

其中：

Z

(1 -

α

)是標(biāo)準(zhǔn)正態(tài)分布（0，1）的第1 -

α

個(gè)分位數(shù)；改進(jìn)后的決策樹(shù)中用到的不等式（式（11））對(duì)數(shù)據(jù)集的適應(yīng)性更高，所以可以使用式（12）來(lái)控制分裂標(biāo)準(zhǔn)：

其中：

k

為類(lèi)的數(shù)目；那么

G

(

x

)大于

G

(

x

)的概率為1 -

α

。

下面對(duì)節(jié)點(diǎn)進(jìn)行信息增益的計(jì)算，信息增益根據(jù)信息增益最大的屬性作為分裂點(diǎn)，其公式為：

信息增益定義為原來(lái)的信息需求與新的信息需求之間的差。即

定理1

考慮兩個(gè)屬性

x

和

x

，經(jīng)過(guò)計(jì)算得到信息增益函數(shù)的值，如果這些值的差滿(mǎn)足以下條件：

當(dāng)兩個(gè)信息增益差值大于通過(guò)式（11）計(jì)算得到的

μ

時(shí)，就對(duì)該節(jié)點(diǎn)進(jìn)行分裂，生成新的葉子節(jié)點(diǎn)。這種節(jié)點(diǎn)分裂判定方法可以根據(jù)有限的數(shù)據(jù)樣本得到分割節(jié)點(diǎn)并判斷該最佳屬性是否也是整個(gè)數(shù)據(jù)流的最佳屬性。結(jié)合基于泰勒定理和正態(tài)分布的不等式和更精確的分裂準(zhǔn)則研究與設(shè)計(jì)一種新的數(shù)據(jù)流決策樹(shù)分類(lèi)算法以獲得更佳的分類(lèi)性能，該公式允許確定數(shù)據(jù)流元素的最小數(shù)量，這樣樹(shù)節(jié)點(diǎn)就可以根據(jù)所考慮的屬性進(jìn)行劃分。

EDW 偽代碼如下所示。

算法1 EDW。

輸入 被劃分為塊的數(shù)據(jù)流

S

集成成員個(gè)數(shù)

k

；內(nèi)存限制

m

；

k

個(gè)權(quán)重增量分類(lèi)器的集合

ε

。輸出：

k

個(gè)分類(lèi)器。

算法2 基分類(lèi)器的訓(xùn)練。

輸入 數(shù)據(jù)流實(shí)例

S

，屬性集

X

，分裂評(píng)價(jià)函數(shù)

G

（

X

），分類(lèi)置信度

δ

，主動(dòng)分裂閾值

τ

，最小分裂實(shí)例數(shù)

n

。

輸出 決策樹(shù)DT。

綜上所述，本文提出的基于動(dòng)態(tài)加權(quán)函數(shù)的集成分類(lèi)算法，首先向集成分類(lèi)器中傳入被分為塊的數(shù)據(jù)流，如果當(dāng)前分類(lèi)器集合為空，則在這個(gè)塊上使用訓(xùn)練后的分類(lèi)器構(gòu)建候選分類(lèi)器，使用

B

上的分類(lèi)器

C

的值計(jì)算

ISE

，使用改進(jìn)后的平方誤差I(lǐng)SE 作為新的度量方法，避免使用MSE 時(shí)出現(xiàn)概率估計(jì)不穩(wěn)定產(chǎn)生錯(cuò)誤的情況，計(jì)算分類(lèi)器的權(quán)重以及候選分類(lèi)器的權(quán)重。當(dāng)當(dāng)前分類(lèi)器集合

ε

中分類(lèi)器的數(shù)量小于

k

，就將候選分類(lèi)器加入當(dāng)前分類(lèi)器集合中，否則就用候選分類(lèi)器代替原分類(lèi)器集合

ε

中的最差的分類(lèi)器；使用下一個(gè)數(shù)據(jù)塊

B

再次訓(xùn)練分類(lèi)器，當(dāng)集合

ε

中的分類(lèi)器數(shù)量達(dá)到

k

時(shí)，則比較分類(lèi)器權(quán)重使用候選分類(lèi)器替換

ε

中權(quán)重最低的分類(lèi)器。在最后如果內(nèi)存的使用超過(guò)了限制，就對(duì)分類(lèi)器進(jìn)行修剪，最后就可以得到訓(xùn)練好的集合分類(lèi)器，使用訓(xùn)練好的集成分類(lèi)器對(duì)數(shù)據(jù)進(jìn)行分類(lèi)得到一個(gè)可觀的分類(lèi)結(jié)果。其中EDW 訓(xùn)練分類(lèi)器的流程如圖1 所示。

圖1 EDW訓(xùn)練分類(lèi)器流程Fig.1 EDW algorithm training classifier flow

2.2 EDW實(shí)例

在2.1 節(jié)已經(jīng)對(duì)EDW 的思想和流程進(jìn)行了詳細(xì)的介紹，為方便對(duì)算法性能的理解，本節(jié)將以實(shí)例介紹。因?yàn)樵撍惴ㄊ腔趬K的集成，所以該算法給定一個(gè)數(shù)值屬性的數(shù)據(jù)集，在后續(xù)演示中將對(duì)其進(jìn)行詳細(xì)的介紹，樣本點(diǎn)表示該點(diǎn)數(shù)據(jù)信息的坐標(biāo)值，類(lèi)標(biāo)是該數(shù)據(jù)集的標(biāo)簽。

其中3 個(gè)數(shù)據(jù)塊中，每個(gè)數(shù)據(jù)塊設(shè)有6 個(gè)樣本，具體樣本實(shí)例如表1 所示。

表1 數(shù)據(jù)塊實(shí)例樣本Tab 1 Data block instance samples

1）第一個(gè)數(shù)據(jù)塊到達(dá)。

權(quán)重最終為：

2）第二個(gè)數(shù)據(jù)塊到達(dá)。

權(quán)重最終為：

其權(quán)重最終為：

3）第三個(gè)數(shù)據(jù)塊到達(dá)。

權(quán)重最終為：

其權(quán)重最終為：

其權(quán)重最終為：

表2 分類(lèi)器訓(xùn)練過(guò)程Tab 2 Classifier training process

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

本文實(shí)驗(yàn)硬件環(huán)境是Intel Core i5 1.4 GHz 8 GB RAM，軟件環(huán)境是在線(xiàn)分析開(kāi)源平臺(tái)（Massive Online Analysis，MOA），所有實(shí)驗(yàn)均采用Java 語(yǔ)言實(shí)現(xiàn)。所有實(shí)驗(yàn)數(shù)據(jù)流全部由MOA 生成。本文使用提升在線(xiàn)學(xué)習(xí)集成（Boosting-like Online Learning Ensemble，BOLE）算法，基于適應(yīng)性多樣性的在線(xiàn)提升（Adaptable Diversity-based Online Boosting，ADOB）算法、LimAttClassifier（Combining Restricted Hoeffding Trees using Stacking）、OzaBoost（Oza and Russell’s online Boosting）、AUE2、OzaBoostAdwin（Boosting for evolving data streams using ADWIN）、LeveringBag（Leveraging Bagging）、OzaBag（Oza and Russell’s online Bagging）和自適應(yīng)隨機(jī)森林（Adaptive Random Forests，ARF）共9 種算法分別在10 個(gè)數(shù)據(jù)流上運(yùn)行，實(shí)驗(yàn)結(jié)果在3.2 節(jié)詳細(xì)介紹。

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

本文采用10 個(gè)數(shù)據(jù)流，它們均由MOA 生成，分別為SEA、LED（Light Emitting Diode）、徑向基函數(shù)（Radial Basis Function，RBF）數(shù)據(jù)集、Waveform、Hyperplane1、Hyperplane2、Hyperplane3、Agrawal1、Agrawal2 和Agrawal3 數(shù)據(jù)集。

SEA 數(shù)據(jù)集由三個(gè)隨機(jī)生成的屬性

x

，

x

，

x

∈［0，10］來(lái)描述，并根據(jù)一個(gè)特定的方程來(lái)指定一個(gè)類(lèi)標(biāo)簽；如果滿(mǎn)足方程，則指定為一類(lèi)，否則指定為另一類(lèi)。LED 數(shù)據(jù)集的目標(biāo)是預(yù)測(cè)七段式LED 顯示屏上顯示的數(shù)字，每個(gè)屬性具有10%的反轉(zhuǎn)機(jī)會(huì)，它具有74%的最佳貝葉斯分類(lèi)。用于實(shí)驗(yàn)的發(fā)生器的特定配置產(chǎn)生24 個(gè)二進(jìn)制屬性，其中17 個(gè)無(wú)關(guān)。RBF 數(shù)據(jù)集為徑向基函數(shù)生成器生成的數(shù)據(jù)集，其生成固定數(shù)量的隨機(jī)質(zhì)心，每個(gè)中心都有一個(gè)隨機(jī)位置、一個(gè)標(biāo)準(zhǔn)偏差、分類(lèi)標(biāo)簽和權(quán)重，所選的質(zhì)心還確定實(shí)例的類(lèi)標(biāo)簽。這有效地創(chuàng)建了圍繞每個(gè)中心點(diǎn)且密度不同的實(shí)例的正態(tài)分布的超球體，它僅生成數(shù)字屬性。Waveform 數(shù)據(jù)集，其任務(wù)的目標(biāo)是區(qū)分三種不同的波形，每種波形是由兩個(gè)或三個(gè)基波的組合生成的。最佳貝葉斯分類(lèi)率已知為86%。該數(shù)據(jù)集有22 個(gè)屬性，前21 個(gè)屬性在實(shí)數(shù)范圍內(nèi)取值。Hyperplane 數(shù)據(jù)集共有11 個(gè)屬性，前10 個(gè)為數(shù)值屬性，共包含100 萬(wàn)個(gè)數(shù)據(jù)實(shí)例及2 個(gè)不同類(lèi)標(biāo)簽。Agrawal 數(shù)據(jù)流共有10 個(gè)屬性，共包含100 萬(wàn)個(gè)數(shù)據(jù)實(shí)例及2 個(gè)不同類(lèi)標(biāo)簽。

其中Hyperplane2 和Hyperplane3 是通過(guò)修改Hyperplane1的參數(shù)得到的，同樣的Agrawal2 和Agrawal3 是通過(guò)修改Agrawal1 數(shù)據(jù)流的參數(shù)生成。因EDW 在Agrawal 和Hyperplane 兩個(gè)數(shù)據(jù)流中表現(xiàn)明顯優(yōu)于對(duì)比算法，因此在修改不同參數(shù)生成的數(shù)據(jù)流上實(shí)驗(yàn)可以更加證實(shí)算法適用此數(shù)據(jù)流及更復(fù)雜的數(shù)據(jù)流情況。Agrawal 和Hyperplane 數(shù)據(jù)流的參數(shù)修改情況如表3～4 所示。其中，Hyperplane 數(shù)據(jù)流中相同參數(shù)為InstanceRandomSeed：1；NumClasses：2；NumAtts：10；MagChange：0；SigmaPercentage：10。以上參數(shù)的修改都是經(jīng)過(guò)大量的實(shí)驗(yàn)結(jié)果證明，修改對(duì)應(yīng)的參數(shù)可以使數(shù)據(jù)流明顯不同，使算法間的差異性可以明顯比較。

表3 Agrawal數(shù)據(jù)流參數(shù)Tab 3 Parameters of Agrawal data streams

表4 Hyperplane數(shù)據(jù)流參數(shù)Tab 4 Parameters of Hyperplane data streams

3.2 實(shí)驗(yàn)

實(shí)驗(yàn)遵循MOA 中的先訓(xùn)練后測(cè)試的方法，測(cè)試和訓(xùn)練的數(shù)據(jù)流均由1 000 000 個(gè)數(shù)據(jù)實(shí)例組成。將本文算法與BOLE、ADOB、LimAttClassifier、OzaBoost、AUE2、OzaBoostAdwin、LeveringBag、OzaBag 和ARF 共10 種算法在不同的數(shù)據(jù)流中進(jìn)行對(duì)比實(shí)驗(yàn)，本實(shí)驗(yàn)在多指標(biāo)上對(duì)10 種算法進(jìn)行了比較，包括塊的大小對(duì)實(shí)驗(yàn)的影響、生成樹(shù)的規(guī)模（葉子數(shù)、節(jié)點(diǎn)數(shù)以及樹(shù)深度）、準(zhǔn)確率以及運(yùn)行時(shí)間。其中在Hyperplane1、Hyperplane2、Hyperplane3、Agrawal1、Agrawal2和Agrawal3 這6 個(gè)數(shù)據(jù)流對(duì)算法進(jìn)行了生成樹(shù)規(guī)模的比較。在 Hyperplane1、Hyperplane2、Hyperplane3、Agrawal1、Agrawal2、Agrawal3、SEA、LED、RBF 和Waveform10 個(gè)數(shù)據(jù)集上對(duì)算法在準(zhǔn)確率和時(shí)間上的比較，其中在準(zhǔn)確率的比較中，所有值均是100 萬(wàn)條實(shí)例每10 萬(wàn)條輸出一次結(jié)果的均值。

3.2.1 塊的大小對(duì)EDW的影響

因?yàn)镋DW 是基于塊的增量集成算法，在本節(jié)中研究塊的大小對(duì)EDW 性能的影響，數(shù)據(jù)塊是根據(jù)時(shí)間戳劃分的大小相等的劃分的塊，當(dāng)達(dá)到一定時(shí)間后實(shí)現(xiàn)了一個(gè)新的數(shù)據(jù)塊，算法便會(huì)建立一定數(shù)量的候選分類(lèi)器，與此同時(shí)更新后的數(shù)據(jù)樣本也會(huì)在一定的時(shí)間內(nèi)調(diào)整先前的集成成員，這樣先前集成中的分類(lèi)器就會(huì)隨著時(shí)間不斷擴(kuò)大，通常認(rèn)為最新的數(shù)據(jù)塊樣本最新的概念，所以認(rèn)為這種更新機(jī)制可以迅速對(duì)概念漂移作出反應(yīng)。

塊的大小很可能影響到塊集成的分類(lèi)性能，塊過(guò)大將引入過(guò)多的概念漂移，但使用較小的塊也會(huì)限制分類(lèi)器中的數(shù)據(jù)流信息。在最新數(shù)據(jù)塊上建立候選分類(lèi)器的塊集成可以分為兩類(lèi)，一種是由數(shù)據(jù)塊中的樣本數(shù)決定訓(xùn)練集的大小，其將所有的集成成員都建立在候選塊上，另一種是使用最新的數(shù)據(jù)塊來(lái)訓(xùn)練候選分類(lèi)器。本節(jié)的實(shí)驗(yàn)?zāi)康氖球?yàn)證塊的大小是否會(huì)影響EDW 的準(zhǔn)確率，實(shí)驗(yàn)結(jié)果如表5 所示，在上述的10 個(gè)數(shù)據(jù)集中對(duì)EDW 進(jìn)行了實(shí)驗(yàn)，數(shù)據(jù)塊大小

d

分別設(shè)置為500、800、100、1 500 和2 000，每個(gè)數(shù)據(jù)集中的最優(yōu)結(jié)果用黑體加粗表示。從表5 中可以看出，在不同的

d

下，EDW 的性能沒(méi)有太大的差異，EDW 的準(zhǔn)確率不受塊的大小的影響。在之后比較實(shí)驗(yàn)中，塊的大小設(shè)置為一個(gè)固定的值，確保后續(xù)實(shí)驗(yàn)的準(zhǔn)確性。

表5 各數(shù)據(jù)集下不同塊大小EDW的準(zhǔn)確率Tab 5 EDW accuracies of different block sizes on each dataset

3.2.2 生成樹(shù)規(guī)模對(duì)比實(shí)驗(yàn)

本節(jié)將對(duì)提出的EDW 以及8 個(gè)對(duì)比算法在6 個(gè)數(shù)據(jù)集上進(jìn)行生成樹(shù)規(guī)模的對(duì)比，選擇這6 個(gè)數(shù)據(jù)集做生成樹(shù)規(guī)模對(duì)比實(shí)驗(yàn)是因?yàn)榻?jīng)過(guò)大量的實(shí)驗(yàn)后，本文算法在這些數(shù)據(jù)集上表現(xiàn)良好，然后在此基礎(chǔ)上進(jìn)行空間上生成樹(shù)的比較，觀察其效果。實(shí)驗(yàn)結(jié)果如表6 所示，其中最優(yōu)的數(shù)據(jù)已經(jīng)用粗體顯示。

表6 生成樹(shù)規(guī)模比較Tab 6 Spanning tree scale comparison

由表6 可以得知，在Hyperplane1 和Hyperplane3 數(shù)據(jù)集中與其他幾個(gè)算法相比，EDW 的生成的節(jié)點(diǎn)數(shù)、葉子數(shù)以及樹(shù)的深度均是最少的。以Hyperplane3 為例，與LimAttClassifier、ARF 和OzaBoostAdwin 相比，節(jié)點(diǎn)數(shù)分別減少 了7 187.6、7 226.8 和29 016.2，分別減少了98.3%、98.4%和99.6%；從葉子數(shù)觀察，以相同的算法進(jìn)行舉例，葉子數(shù)分別減少了3 593.8、3 613.4 和14 508.1，分別減少了98.4%、98.38%和99.6%；同樣，本文算法在樹(shù)的深度層面上分別降低了17.1 層、13.7 層和11 層，分別減少了73.1%、69%和63.6%。與對(duì)比算法相比，EDW 的樹(shù)規(guī)模數(shù)據(jù)很有優(yōu)勢(shì)。

在Agrawal 數(shù)據(jù)集及其變體的實(shí)驗(yàn)下可以看到，本文算法在Agrawal2 和Agrawal3 數(shù)據(jù)集上與其他對(duì)比算法相比取得了最好的效果。以Agrawal2 數(shù)據(jù)集舉例，與OzaBoostAdwin、LimAttClassifier 和ARF 三個(gè)算法相比，節(jié)點(diǎn)數(shù)分別減少了34 621.4、2 609.52 和4 694.3，分別減少了99.6%、94.4%和99.6%；從葉子數(shù)觀察，以相同的算法進(jìn)行舉例，葉子數(shù)分別減少了20 524.8、1 561.2 和3 439.2，分別減少了99.4%、92.3%和996.3%；同樣，本文算法在樹(shù)的深度層面上分別降低了4.5 層、24.19 層和7.3 層，分別減少了40.2%、78.1%和52.1%。EDW 減少了相當(dāng)多的節(jié)點(diǎn)數(shù)與葉子數(shù)，樹(shù)深度的效果也很可觀；即使在Agrawal1 數(shù)據(jù)集下，樹(shù)規(guī)模的數(shù)據(jù)與最優(yōu)數(shù)據(jù)相比稍有落后，但是相差甚微，縱觀所有算法的樹(shù)規(guī)模數(shù)據(jù)還是很有優(yōu)勢(shì)的。

3.2.3 算法準(zhǔn)確率對(duì)比實(shí)驗(yàn)

本節(jié)將對(duì)提出的EDW 以及9 個(gè)對(duì)比算法在10 個(gè)數(shù)據(jù)集上進(jìn)行準(zhǔn)確率和時(shí)間上的對(duì)比，如表7～8 所示。在準(zhǔn)確率方面，EDW 在除Hyperplane2、Hyperplane3 和LED 三個(gè)數(shù)據(jù)集外準(zhǔn)確率均優(yōu)于其他9 個(gè)對(duì)比算法，相較于ADOB 算法平均提高了25%左右。在Hyperplane2、Hyperplane3 和LED 這三個(gè)數(shù)據(jù)集上也僅與對(duì)比算法的最優(yōu)準(zhǔn)確率相差1%～2%。在Agrawal1 數(shù)據(jù)集中EDW 高于ARF 算法近20%的準(zhǔn)確率。在LED 數(shù)據(jù)集中EDW 相較于ARF 算法有著45.52%的優(yōu)勢(shì)?？偟膩?lái)說(shuō)，EDW 雖僅在7 個(gè)數(shù)據(jù)集上取得最優(yōu)準(zhǔn)確率，但是在其他3 個(gè)數(shù)據(jù)集與其他對(duì)比算法的最優(yōu)準(zhǔn)確率相差甚微，這在空間大幅減少的前提下，是一個(gè)不錯(cuò)的表現(xiàn)。

表7 各算法準(zhǔn)確率對(duì)比 單位：%Tab 7 Accuracy comparison of different algorithms unit：%

如表8 所示，在時(shí)間對(duì)比實(shí)驗(yàn)中，雖然ARF 算法運(yùn)行的時(shí)間最短，但是因?yàn)槠洳皇羌伤惴?，?duì)于不斷變化的數(shù)據(jù)流準(zhǔn)確率也很低，所以在這里不與它進(jìn)行比較。除了ARF算法以外的算法中EDW 在10 個(gè)數(shù)據(jù)集中均取得了不錯(cuò)的效果，雖然在其中一些數(shù)據(jù)集中EDW 中不是使用最短的時(shí)間，這是因?yàn)樵趯?duì)數(shù)據(jù)分類(lèi)的過(guò)程中該算法對(duì)基分類(lèi)器重新計(jì)算權(quán)重等過(guò)程中耗費(fèi)了一些時(shí)間，但是在提高了準(zhǔn)確率和減少空間占比的前提下，處理1 000 000 條數(shù)據(jù)的數(shù)據(jù)集中與用時(shí)更少的對(duì)比算法相比僅多出幾秒甚至零點(diǎn)幾秒是可以接受的結(jié)果。

表8 各算法時(shí)間代價(jià)對(duì)比 單位：sTab.8 Time cost comparison of different algorithms unit：s

因?yàn)楸疚乃惴ㄔ贖yperplane 和Agrawal 數(shù)據(jù)集中取得了很好的準(zhǔn)確率，這也是在之前集中研究這兩個(gè)數(shù)據(jù)集以及其對(duì)參數(shù)進(jìn)行修改后的變體進(jìn)行實(shí)驗(yàn)的原因。生成樹(shù)規(guī)模對(duì)比實(shí)驗(yàn)是在上一個(gè)實(shí)驗(yàn)算法準(zhǔn)確率相差不大的情況下進(jìn)行的，因?yàn)锳DOB 算法在實(shí)驗(yàn)中的幾個(gè)數(shù)據(jù)集上準(zhǔn)確率都不是太理想，所以在進(jìn)行生成樹(shù)規(guī)模的實(shí)驗(yàn)中就沒(méi)有考慮該算法。圖2 代表了在同樣兩個(gè)數(shù)據(jù)集下生成樹(shù)的節(jié)點(diǎn)數(shù)和葉子數(shù)，因?yàn)镺zaBoostAdwin 產(chǎn)生了極大的節(jié)點(diǎn)數(shù)和葉子數(shù)，所以擴(kuò)大了整個(gè)柱狀圖的比例，導(dǎo)致OzaBoost、OzaBag 和BOLE的實(shí)驗(yàn)數(shù)據(jù)在圖中看似與本文提出的算法相差不多，但實(shí)際在數(shù)量上仍然相差5 到7 倍。所以可以看出在這兩個(gè)數(shù)據(jù)集上，EDW 生成的節(jié)點(diǎn)數(shù)和葉子數(shù)極少，這在有限的內(nèi)存中節(jié)省了大量空間。

圖2 各算法數(shù)據(jù)流生成樹(shù)的節(jié)點(diǎn)數(shù)和葉子數(shù)對(duì)比Fig.2 Comparison of nodes and leaves of data stream spanning trees in different algorithms

圖3 代表Hyperplane3 和Agrawal3 兩個(gè)數(shù)據(jù)集下的生成樹(shù)的深度對(duì)比，在這兩個(gè)數(shù)據(jù)集中可以清晰地看到本文提出的EDW 在樹(shù)的深度上始終保持著最小的深度，與LimAttClassifier 算法相差了十幾層樹(shù)深度，在產(chǎn)生大量葉子數(shù)和節(jié)點(diǎn)數(shù)的情況，減少樹(shù)深度可以減小很多內(nèi)存的使用。

圖3 各算法數(shù)據(jù)流生成樹(shù)的深度對(duì)比Fig.3 Comparison of depth of data stream spanning trees in different algorithms

圖4 為EDW 以及其他8 個(gè)對(duì)比算法在100 萬(wàn)條的數(shù)據(jù)集下的精度繪制了折線(xiàn)圖，代表了各種算法在兩個(gè)數(shù)據(jù)集下準(zhǔn)確率對(duì)比?？梢钥吹皆趦蓚€(gè)數(shù)據(jù)集上，本文算法均在最優(yōu)的范圍內(nèi)，其中在圖4（b）中，為了更好地展示幾個(gè)較高準(zhǔn)確率的算法中的差異，LimAttClassifier 和ARF 算法因?yàn)闇?zhǔn)確率過(guò)低，為66.65%與77.35%，缺少可比性，就沒(méi)有顯示在圖中。從這兩張圖中可以得出，EDW 在大幅減小樹(shù)規(guī)模的同時(shí)，準(zhǔn)確率仍然保持在最優(yōu)范圍內(nèi)，是一個(gè)效果較好的集成算法。

圖4 各算法數(shù)據(jù)流準(zhǔn)確率對(duì)比Fig.4 Comparison of accuracy of data streams for different algorithms

4 結(jié)語(yǔ)

本文提出了一個(gè)可以計(jì)算基分類(lèi)器的權(quán)重的算法，調(diào)節(jié)分類(lèi)器的權(quán)重對(duì)其進(jìn)行一個(gè)合理的選擇，根據(jù)在最新數(shù)據(jù)塊中對(duì)樣本數(shù)據(jù)估計(jì)其預(yù)期的預(yù)測(cè)誤差，評(píng)估每個(gè)基分類(lèi)器的性能。同時(shí)本文使用基于泰勒定理和正態(tài)分布的性質(zhì)的決策樹(shù)作為基分類(lèi)器，使其可以根據(jù)有限的數(shù)據(jù)樣本進(jìn)行分割并且辨別當(dāng)前節(jié)點(diǎn)的最佳屬性其是否也是整個(gè)數(shù)據(jù)流的最佳屬性，提出了一種基于動(dòng)態(tài)加權(quán)函數(shù)的集成分類(lèi)算法。實(shí)驗(yàn)結(jié)果表明，本文提出的算法的性能不受塊的大小影響，大幅地減小了生成樹(shù)的規(guī)模，準(zhǔn)確率方面效果較好，也能很好地適應(yīng)帶有概念漂移和噪聲的數(shù)據(jù)流。未來(lái)將對(duì)該算法的運(yùn)行時(shí)間上進(jìn)行進(jìn)一步的研究，盡可能地減少不必要的計(jì)算，提升計(jì)算效率，更好地節(jié)省運(yùn)算時(shí)間。