基于動態加權函數的集成分類算法

王 樂，韓 萌，李小娟，張 妮，程浩東

（北方民族大學計算機科學與工程學院，銀川 750021）

0 引言

在動態變化和非平穩環境中數據以流的形式到達，要從大量的數據中獲取有用的知識，數據流挖掘方法在大數據領域起著重要的作用。為了適應不斷變化的數據流，將數據流更有效地轉變為有用的信息供人們在生活中使用，集成分類無疑是一種優秀的挖掘數據流的方法。集成分類算法之所以受到眾多研究者的青睞，是因為集成分類器由多個準確而多樣的基分類器組成，可以形成分類決策，采用不同的加權方式可以構建多種多樣的決策，從而使其性能優于單個分類器。在集成方法中，Bagging和Boosting被認為是最流行和最有效的方法。Bagging 是一種引導聚集算法，生成不同的模型并使用這些模型獲得集成分類器的方法。它通過降低基分類器的方差改善了泛化誤差，使用不同的模型對實例進行預測，在預測類別時進行多數票投票對模型進行平均操作，最后提高整個分類器的準確性。Boosting 通過對樣本集進行操作得到樣本子集，將弱分類算法作為基分類器放入Boosting 框架中然后對訓練樣本集進行訓練生成基分類器，重復運行給定的弱學習算法，這樣經過

n

輪迭代就會產生

n

個基分類器，把這樣的分類器集成在一起就可以提高弱分類算法的識別率。除去Bagging 和Boosting 這兩個經常被提及使用的算法，Stacking 同樣受到眾多研究學者的青睞，Stacking 是集成學習的第三類，廣泛應用于有監督學習和無監督學習領域，基分類器的輸入屬性和學習策略對Stacking 的性能有很大的影響。例如，Todorovski 等提出了一種稱為元決策樹（Meta Decision Tree，MDT）的Stacking 方法來改進集成學習過程。Zhu 等還提出了一種稱為Stacking 數據包絡分析（Data Envelopment Analysis，DEA）的方法來找出最佳Stacking 方式。David 等提出了一種新穎的通用面向對象投票和加權自適應Stacking 框架，用于利用分類器集成進行預測。這個通用框架基于任何一組基礎學習器的概率的加權平均值運行，最終預測是它們各自投票的總和。

雖然集成分類算法已經可以處理一些數據流的分類問題，但是在基分類器的加權以及動態更新以及基分類器的選擇上仍然存在一些問題，在分類的過程中產生的這些問題仍然會影響分類的準確率和時空效率。所以針對現有的集成分類算法，本文設計了一種基于動態加權函數的集成分類算法，主要工作如下：

1）本文提出了一個加權函數

F

（

x

，

y

，

d

，

θ

）調節基分類器權重，將其應用于基分類器的評價以選擇更適合的分類器，其中：

x

表示實例，

y

表示實例的類別，

d

表示數據塊中的樣本個數，

θ

表示兩個權重的折中系數；該加權函數采用精度權重和性能權重按一定比例計算的綜合權重來對基分類器進行加權，通過這個加權函數的評價結果選出最優的分類器增加集成的性能。2）為更好地提升集成分類器的性能，本文還設置了候選分類器對基分類器進行替換，并提出了一個權重函數

G

（

x

，

y

，

θ

），其中：

x

表示最新數據塊上的實例，

y

表示

x

的類別，

θ

表示兩個權重的折中系數；通過這個函數可以得到候選分類的權重，候選分類器替換集成中最差的分類器，就可以得到更好的分類結果。

3）本文提出了一種基于動態加權函數的集成分類算法（Ensemble classification algorithm based on Dynamic Weighting function，EDW），使用不斷更新的數據塊訓練分類器，使用候選分類器來替換集成中最差的分類器，采用了兩個加權函數動態更新基分類器，其中基分類器選用泰勒定理和正態分布性質的不等式的決策樹。

1 相關工作

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

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

2 本文算法

為了使算法更易描述，現對算法要用到的一些問題進行符號化，其中

B

表示第

i

個數據塊，數據塊中包含

n

個實例，分別為(

x

，

y

)，(

x

，

y

)，…，(

x

，

y

)，

x

是特征向量，

y

是類標簽，

ε

表示分類器的集合，其中分類器有

k

個。隨著數據塊的不斷更新，數據流也在不斷變化，舊的數據已經不能代表最新的概念，訓練出的分類器也不能得到一個很好的結果，所以算法就要對基分類器進行更新與代替，本文采用的集成成員的更新方法是使用精度權重以及性能權重的綜合權重來對其分類器進行調整，以替換掉效果不好的分類器使整個集成算法達到最優的效果。

2.1 權重更新方法與基分類器

2.1.1 集成成員精度權重更新新方法

精度更新集成算法維護一個加權的基分類器池，并通過使用加權投票規則，結合基分類器的預測結果來預測傳入樣本的類別。在處理完每個數據塊之后，創建一個分類器，替換性能最差的集成成員。根據在最新數據塊中對樣本數據估計其預期的預測誤差，可以評估每個基分類器的性能。在替換了表現最差的分類器后，對其余的集成成員進行更新，即增量訓練，并根據它們的精度調整其權重。

傳統的精度集成更新算法使用均方誤差（Mean Square Error，MSE）用來計算分類器的均方誤差進而計算權重，例如精度更新集成AUE2，MSE 顯示了實際類標簽

y

的估計概率的誤差，一個給出精確概率估計的模型可以降低該誤差。雖然它使用真后驗概率

P

(

y

|

x

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

P

（

x|y

）。一般情況下，MSE是根據經驗計算的假設

P

(

y

|

x

)=1。在文獻［15］中，提出了MSE 分類器評價指標計算公式：

MSE

通常被用作估計概率的度量，其中分子為誤差平方和，分母的值為自由度；但是如果概率估計不穩定，即使模型能夠正確地預測出所有的類標簽，

MSE

仍然會變得很高，計算出的值無法更好地選擇分類器，所以，Fan 等引入了改進后的平方誤差（Integrated Square Error，ISE）。ISE 僅在模型對樣本分類錯誤時才會解釋概率誤差。也就是說，ISE 將準確率和

MSE

結合成一個值，并且假設二進制分類中估計概率的預測閾值固定為0.5。ISE 分類器評價指標計算公式為：

使用改進后的平方誤差ISE 作為新的度量方法，就可以避免使用MSE 時出現概率估計不穩定產生錯誤的情況。將改進后的均方誤差公式代入基于塊的數據流的思想中就可以得到式（3）：

其中：函數

P

(

y

|

x

)表示分類器

C

給出的

x

是屬于類

y

的實例的概率，數據塊

B

上有

d

個樣本，不考慮單個類的預測，而是考慮所有類的概率；

ISE

的值表示在塊

B

上的分類器

C

的預測誤差，數據塊

B

上有

d

個樣本。AUE2 算法中提出的隨機預測的分類器的均方誤差

MSE

公式為：

其中：

p

(

y

)是類別

y

的分布，可以通過式（3）～（4）計算數據塊上的分類器的預測誤差和隨機預測分類器的均方誤差，從而提出并計算基分類器的權重公式

f

(

x

，

y

，

d

)：

ISE

的值表示在塊

B

上的分類器

C

的預測誤差，而

MSE

是隨機預測的分類器的均方誤差，并用作當前類別分布的參考點。另外一個非常小的正值

ε

是為了避免被零除的問題。式（5）中給出的權重公式旨在結合分類器的準確率信息和當前的類分布情況，因為本文使用的權重公式是非線性函數，與類似于精度加權集成（Accuracy Weighted Ensemble，AWE）算法中使用的線性函數相比，本文提出的EDW 可以高度區分基分類器。除了給集成成員分配新的權重，每個數據塊

B

都用一個被記為

C

′的候選分類器，這個分類器是從最近塊中的樣本中創建的。

C

′在最近的數據上訓練，并且把它當作為一個“完美”分類器，同時根據如下公式分配一個精度權重。EDW 不但為集成中的成員分配權重，同時還維護一個候選分類器池，為每個數據塊

B

都分配一個候選分類器

C

′，并且把這個候選分類器

C

′默認為一個沒有誤差的分類器，其中，候選分類器的權重計算公式如式（6）所示：

與用于給當前的集成成員分配權重的函數相比，候選分類器的權重沒有考慮

C

′在

B

數據塊上的預測誤差，這種方法是基于最近的數據塊能夠最好地表示當前和未來的數據分布的假設決定的。因為

C

′是在最近的數據上訓練的，它應該被視為可能是最佳的分類器。

2.1.2 集成成員性能權重更新方法

在對基分類器的精度權重進行了計算之后，下面將對基分類器的性能權重進行計算，因為在先前數據塊上訓練的基分類器的權重是基于最新數據塊中樣本的分類性能的，由此本文提出了式（7）對最新數據中的基分類器進行性能權重的更新，性能權重用

h

（

x，y

）表示：

式（7）中給出的績效權重結合了分類績效和當前類別分布的因素，之前的基分類器的性能權重應與

ISE

成反比。因此，保留的先前基分類器的性能權重需要評估當前數據塊的均方誤差。通常認為最新塊的數據分布是當前和未來一段時間概念的最佳代表，因此，可以不管其分類性能如何將候選分類器

C

′的性能權重直接設定為最優值。用

f

′(

y

)表示的候選分類器

C

′的性能權重可以表示為：

候選分類器

C

′的性能權重與隨機預測的均方誤差成正比。因此，候選集成成員的判別能力僅考慮當前的類分布。因為在式（8）提出的性能權重不需要計算模型的均方誤差，所以不需要額外的驗證集來驗證

C

′的分類性能。因此該算法的加權機制不需要交叉驗證過程，該過程適合處理快速數據流。同時，如果將候選分類器視為最佳成員，則該算法可以很好地應對突然的概念漂移。

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

其中：

F

(

x

，

y

，

d

，

θ

)計算分類器的權重，

G

(

x

，

y

，

θ

)計算候選分類器

C

′的權重；

f

(

x

，

y

，

d

)和

h

(

x

，

y

)分別是基分類器精度權重和性能權重函數；

g

(

x

，

y

)和

w

(

x

，

y

)分別是候選分類器的精度權重和性能權重函數；

θ

是性能權重和基分類器的穩定性之間的折中系數，通常取

θ

=0.5。

2.1.3 基分類器的選擇

本文提出的集成算法使用基于泰勒定理和正態分布的性質推導出的不等式來作為分裂節點判斷標準的決策樹作為基分類器，這種決策樹不僅適用于數值型數據也適用于具有名稱型屬性值的數據，而且還易于解決概念漂移問題，該不等式可以根據有限的數據樣本進行分割并且辨別當前節點的最佳屬性其是否也是整個數據流的最佳屬性。分裂節點的判斷標準公式為：

其中：

Z

(1 -

α

)是標準正態分布（0，1）的第1 -

α

個分位數；改進后的決策樹中用到的不等式（式（11））對數據集的適應性更高，所以可以使用式（12）來控制分裂標準：

其中：

k

為類的數目；那么

G

(

x

)大于

G

(

x

)的概率為1 -

α

。

下面對節點進行信息增益的計算，信息增益根據信息增益最大的屬性作為分裂點，其公式為：

信息增益定義為原來的信息需求與新的信息需求之間的差。即

定理1

考慮兩個屬性

x

和

x

，經過計算得到信息增益函數的值，如果這些值的差滿足以下條件：

當兩個信息增益差值大于通過式（11）計算得到的

μ

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

EDW 偽代碼如下所示。

算法1 EDW。

輸入 被劃分為塊的數據流

S

集成成員個數

k

；內存限制

m

；

k

個權重增量分類器的集合

ε

。輸出：

k

個分類器。

算法2 基分類器的訓練。

輸入 數據流實例

S

，屬性集

X

，分裂評價函數

G

（

X

），分類置信度

δ

，主動分裂閾值

τ

，最小分裂實例數

n

。

輸出 決策樹DT。

綜上所述，本文提出的基于動態加權函數的集成分類算法，首先向集成分類器中傳入被分為塊的數據流，如果當前分類器集合為空，則在這個塊上使用訓練后的分類器構建候選分類器，使用

B

上的分類器

C

的值計算

ISE

，使用改進后的平方誤差ISE 作為新的度量方法，避免使用MSE 時出現概率估計不穩定產生錯誤的情況，計算分類器的權重以及候選分類器的權重。當當前分類器集合

ε

中分類器的數量小于

k

，就將候選分類器加入當前分類器集合中，否則就用候選分類器代替原分類器集合

ε

中的最差的分類器；使用下一個數據塊

B

再次訓練分類器，當集合

ε

中的分類器數量達到

k

時，則比較分類器權重使用候選分類器替換

ε

中權重最低的分類器。在最后如果內存的使用超過了限制，就對分類器進行修剪，最后就可以得到訓練好的集合分類器，使用訓練好的集成分類器對數據進行分類得到一個可觀的分類結果。其中EDW 訓練分類器的流程如圖1 所示。

圖1 EDW訓練分類器流程Fig.1 EDW algorithm training classifier flow

2.2 EDW實例

在2.1 節已經對EDW 的思想和流程進行了詳細的介紹，為方便對算法性能的理解，本節將以實例介紹。因為該算法是基于塊的集成，所以該算法給定一個數值屬性的數據集，在后續演示中將對其進行詳細的介紹，樣本點表示該點數據信息的坐標值，類標是該數據集的標簽。

其中3 個數據塊中，每個數據塊設有6 個樣本，具體樣本實例如表1 所示。

表1 數據塊實例樣本Tab 1 Data block instance samples

1）第一個數據塊到達。

權重最終為：

2）第二個數據塊到達。

權重最終為：

其權重最終為：

3）第三個數據塊到達。

權重最終為：

其權重最終為：

其權重最終為：

表2 分類器訓練過程Tab 2 Classifier training process

3 實驗與結果分析

本文實驗硬件環境是Intel Core i5 1.4 GHz 8 GB RAM，軟件環境是在線分析開源平臺（Massive Online Analysis，MOA），所有實驗均采用Java 語言實現。所有實驗數據流全部由MOA 生成。本文使用提升在線學習集成（Boosting-like Online Learning Ensemble，BOLE）算法，基于適應性多樣性的在線提升（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）和自適應隨機森林（Adaptive Random Forests，ARF）共9 種算法分別在10 個數據流上運行，實驗結果在3.2 節詳細介紹。

3.1 數據流

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

SEA 數據集由三個隨機生成的屬性

x

，

x

，

x

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

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

表3 Agrawal數據流參數Tab 3 Parameters of Agrawal data streams

表4 Hyperplane數據流參數Tab 4 Parameters of Hyperplane data streams

3.2 實驗

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

3.2.1 塊的大小對EDW的影響

因為EDW 是基于塊的增量集成算法，在本節中研究塊的大小對EDW 性能的影響，數據塊是根據時間戳劃分的大小相等的劃分的塊，當達到一定時間后實現了一個新的數據塊，算法便會建立一定數量的候選分類器，與此同時更新后的數據樣本也會在一定的時間內調整先前的集成成員，這樣先前集成中的分類器就會隨著時間不斷擴大，通常認為最新的數據塊樣本最新的概念，所以認為這種更新機制可以迅速對概念漂移作出反應。

塊的大小很可能影響到塊集成的分類性能，塊過大將引入過多的概念漂移，但使用較小的塊也會限制分類器中的數據流信息。在最新數據塊上建立候選分類器的塊集成可以分為兩類，一種是由數據塊中的樣本數決定訓練集的大小，其將所有的集成成員都建立在候選塊上，另一種是使用最新的數據塊來訓練候選分類器。本節的實驗目的是驗證塊的大小是否會影響EDW 的準確率，實驗結果如表5 所示，在上述的10 個數據集中對EDW 進行了實驗，數據塊大小

d

分別設置為500、800、100、1 500 和2 000，每個數據集中的最優結果用黑體加粗表示。從表5 中可以看出，在不同的

d

下，EDW 的性能沒有太大的差異，EDW 的準確率不受塊的大小的影響。在之后比較實驗中，塊的大小設置為一個固定的值，確保后續實驗的準確性。

表5 各數據集下不同塊大小EDW的準確率Tab 5 EDW accuracies of different block sizes on each dataset

3.2.2 生成樹規模對比實驗

本節將對提出的EDW 以及8 個對比算法在6 個數據集上進行生成樹規模的對比，選擇這6 個數據集做生成樹規模對比實驗是因為經過大量的實驗后，本文算法在這些數據集上表現良好，然后在此基礎上進行空間上生成樹的比較，觀察其效果。實驗結果如表6 所示，其中最優的數據已經用粗體顯示。

表6 生成樹規模比較Tab 6 Spanning tree scale comparison

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

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

3.2.3 算法準確率對比實驗

本節將對提出的EDW 以及9 個對比算法在10 個數據集上進行準確率和時間上的對比，如表7～8 所示。在準確率方面，EDW 在除Hyperplane2、Hyperplane3 和LED 三個數據集外準確率均優于其他9 個對比算法，相較于ADOB 算法平均提高了25%左右。在Hyperplane2、Hyperplane3 和LED 這三個數據集上也僅與對比算法的最優準確率相差1%～2%。在Agrawal1 數據集中EDW 高于ARF 算法近20%的準確率。在LED 數據集中EDW 相較于ARF 算法有著45.52%的優勢。總的來說，EDW 雖僅在7 個數據集上取得最優準確率，但是在其他3 個數據集與其他對比算法的最優準確率相差甚微，這在空間大幅減少的前提下，是一個不錯的表現。

表7 各算法準確率對比 單位：%Tab 7 Accuracy comparison of different algorithms unit：%

如表8 所示，在時間對比實驗中，雖然ARF 算法運行的時間最短，但是因為其不是集成算法，對于不斷變化的數據流準確率也很低，所以在這里不與它進行比較。除了ARF算法以外的算法中EDW 在10 個數據集中均取得了不錯的效果，雖然在其中一些數據集中EDW 中不是使用最短的時間，這是因為在對數據分類的過程中該算法對基分類器重新計算權重等過程中耗費了一些時間，但是在提高了準確率和減少空間占比的前提下，處理1 000 000 條數據的數據集中與用時更少的對比算法相比僅多出幾秒甚至零點幾秒是可以接受的結果。

表8 各算法時間代價對比 單位：sTab.8 Time cost comparison of different algorithms unit：s

因為本文算法在Hyperplane 和Agrawal 數據集中取得了很好的準確率，這也是在之前集中研究這兩個數據集以及其對參數進行修改后的變體進行實驗的原因。生成樹規模對比實驗是在上一個實驗算法準確率相差不大的情況下進行的，因為ADOB 算法在實驗中的幾個數據集上準確率都不是太理想，所以在進行生成樹規模的實驗中就沒有考慮該算法。圖2 代表了在同樣兩個數據集下生成樹的節點數和葉子數，因為OzaBoostAdwin 產生了極大的節點數和葉子數，所以擴大了整個柱狀圖的比例，導致OzaBoost、OzaBag 和BOLE的實驗數據在圖中看似與本文提出的算法相差不多，但實際在數量上仍然相差5 到7 倍。所以可以看出在這兩個數據集上，EDW 生成的節點數和葉子數極少，這在有限的內存中節省了大量空間。

圖2 各算法數據流生成樹的節點數和葉子數對比Fig.2 Comparison of nodes and leaves of data stream spanning trees in different algorithms

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

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

圖4 為EDW 以及其他8 個對比算法在100 萬條的數據集下的精度繪制了折線圖，代表了各種算法在兩個數據集下準確率對比。可以看到在兩個數據集上，本文算法均在最優的范圍內，其中在圖4（b）中，為了更好地展示幾個較高準確率的算法中的差異，LimAttClassifier 和ARF 算法因為準確率過低，為66.65%與77.35%，缺少可比性，就沒有顯示在圖中。從這兩張圖中可以得出，EDW 在大幅減小樹規模的同時，準確率仍然保持在最優范圍內，是一個效果較好的集成算法。

圖4 各算法數據流準確率對比Fig.4 Comparison of accuracy of data streams for different algorithms

4 結語

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