基于準(zhǔn)確率爬坡的動態(tài)加權(quán)集成分類算法

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

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

0 引言

集成學(xué)習(xí)由于其較高的分類準(zhǔn)確性和能夠快速適應(yīng)概念漂移等特點，成為了數(shù)據(jù)流分類研究的主要方法之一［1］。它使用多個弱分類器構(gòu)成一個強分類器，弱分類器有決策樹、支持向量機、神經(jīng)網(wǎng)絡(luò)等［2］；基分類器之間的整合方式有簡單加權(quán)投票、多數(shù)投票、隨機投票等［3］。與僅僅使用單個算法相比，集成學(xué)習(xí)方法能獲得更好的性能［4］。集成學(xué)習(xí)一般分為Bagging、Boosting 及Stacking 三類。

杠桿裝袋（Leveraging Bagging）算法［5］是一個比較經(jīng)典的數(shù)據(jù)流集成分類算法，其將裝袋（Bagging）的簡單性與向分類器的輸入和輸出添加更多隨機化相結(jié)合，可以更好地降低相關(guān)性、增加多樣性，具有更高的準(zhǔn)確率。推算特征選擇裝袋（Imputed Feature selected Bagging，IFBag）算法［6］使用多重插補、特征選擇和裝袋集成學(xué)習(xí)方法來構(gòu)造基分類器，以對新的不完整實例進行分類。權(quán)重更新分類（Weight Update Classifiers，WUC）［7］是對自適應(yīng)裝袋方法的修改，這種修改不會在每次迭代中更新部分分類器，而是基于計算出的權(quán)重，采用性能最差的n個分類器（具有最高錯誤率）并僅更新那些分類器，其他集成成員保持不變。基于概念漂移檢測的網(wǎng)絡(luò)數(shù)據(jù)流自適應(yīng)分類算法［8］通過比較滑動窗口中的數(shù)據(jù)與歷史數(shù)據(jù)之間分布差異來檢測概念漂移，然后對窗口數(shù)據(jù)進行過采樣以減少樣本之間的不平衡，最后將處理后的數(shù)據(jù)集用于在線學(xué)習(xí)的分類器，它更新分類器以應(yīng)對數(shù)據(jù)流中的概念漂移。Voting-Boosting［9］是一種使用投票和Boosting 的集成方法，用于特征的最佳選擇和預(yù)測。為了進行特征選擇，除投票、Boosting 之外，還使用了最佳優(yōu)先搜索算法。在線Boosting（Online Boosting，OLBoost）算法［10］使用極快決策樹（Extremely Fast Decision Tree，EFDT）作為基學(xué)習(xí)器，以便將它們整合為一個強大的在線學(xué)習(xí)器。DSTARS（Deep Structure for Tracking Asynchronous Regressor Stacking）［11］是一種新穎的多目標(biāo)回歸（Multi-Target Regression，MTR）方法，將多個堆疊回歸器組合到一個深層結(jié)構(gòu)中來擴展堆疊單目標(biāo)（Stacked Single-Target，SST）方法；通過不斷改進對目標(biāo)的預(yù)測來提高預(yù)測性能。此外，DSTARS 通過跟蹤異步數(shù)量的堆疊回歸量來單獨利用每個目標(biāo)的依賴性。FASE-AL（Fast Adaptive Stacking of Ensembles using Active Learning）算法［12］是對快速自適應(yīng)Stacking 集成（Fast Adaptive Stacking of Ensembles，F(xiàn)ASE）算法的改進，使用主動學(xué)習(xí)誘導(dǎo)具有未標(biāo)記實例的分類模型。SSEM（Self-adaptive Stacking Ensemble Model）［13］是一種新的自適應(yīng)Stacking 集成算法，該算法選擇性地集成了不同基學(xué)習(xí)器，并通過遺傳算法自動選擇了最佳基學(xué)習(xí)器組合和超參數(shù)。

盡管現(xiàn)有的集成分類算法能夠很好地處理數(shù)據(jù)流問題，但是，在數(shù)據(jù)流集成分類中仍有很多問題需要解決，例如：集成數(shù)目的更新方式、為基分類器分配合適的權(quán)值等。針對上述問題，本文提出了兩種新的集成分類算法，主要工作如下：

1）設(shè)計了一種準(zhǔn)確率爬坡集成分類算法（accuracy Climbing Ensemble Classification Algorithm，C-ECA）。C-ECA改變了傳統(tǒng)集成學(xué)習(xí)方法中基分類器的更新方式，不再替換相同數(shù)量的基分類器。該算法首先會初始化一個分類器池Π，大小設(shè)置為N（N＞1）；然后，向大于N的方向（上坡）和小于N的方向（下坡）進行搜索，確定最佳集成數(shù)目。

2）設(shè)計了基于爬坡的動態(tài)加權(quán)集成分類算法（Dynamic Weighted Ensemble Classification Algorithm based on Climbing，C-DWECA）。在實際訓(xùn)練實例時，不同基分類器在不同數(shù)據(jù)流上的預(yù)測性能存在差異，所以，需要對不同基分類器分配合適的權(quán)值。因此，本文在C-ECA 的基礎(chǔ)上，設(shè)計了一個新的加權(quán)函數(shù)w(x)，從而得到C-DWECA，算法在分類準(zhǔn)確率方面得到了很大的提升。

3）采用快速霍夫丁漂移檢測方法（Fast Hoffding Drift Detection Method，F(xiàn)HDDM）來檢測概念漂移。

1 相關(guān)工作

數(shù)據(jù)流具有許多固有屬性，包括連續(xù)有序到達、無限長度、概念漂移等［14］。因此，構(gòu)建更健壯的模型以迅速有效地從數(shù)據(jù)中提取有意義的信息變得更加重要。

數(shù)據(jù)流中的概念漂移問題是指數(shù)據(jù)流的基礎(chǔ)分布會隨時間動態(tài)變化?，F(xiàn)有的分類方法主要采用兩種策略來解決概念漂移問題：一種是被動方法，該方法基于遺忘機制（即動態(tài)窗口或衰減函數(shù)）或定期檢測每個傳入數(shù)據(jù)實例分類器的分類性能，以決定何時更新過時的分類器［15-16］。另一種是主動方法，該方法側(cè)重基于分布的檢測或基于序列的方法［17-18］。

在處理實際問題的時候，會出現(xiàn)不同類型的概念漂移。當(dāng)分類決策邊界改變時發(fā)生的概念漂移稱為真實概念漂移，當(dāng)分類決策邊界不發(fā)生變化時稱為虛擬概念漂移，真實概念漂移與虛擬概念漂移分布類型如圖1 所示。

圖1 真實概念漂移與虛擬概念漂移分布類型Fig.1 Distribution types of real concept drift and virtual concept drift

現(xiàn)階段對于概念漂移的研究還沒有一個統(tǒng)一的描述，除真實概念漂移和虛擬概念漂移之外，研究人員還根據(jù)概念漂移變化速度將概念漂移分為突變漂移、漸變漂移、重復(fù)漂移和增量漂移［19］。突變漂移是指數(shù)據(jù)流發(fā)生巨大的變化從一種狀態(tài)變換到另外一種狀態(tài)；漸變漂移是指隨著時間的變化數(shù)據(jù)流逐漸變化；重復(fù)漂移是指概念在特定的時間段反復(fù)出現(xiàn)；增量漂移是指隨著時間的推移概念緩慢變化?；谧兓俣鹊母拍钇品植碱愋腿鐖D2 所示。

圖2 基于變化速度的概念漂移類型Fig.2 Types of concep drift based on speed of change

2 C-ECA和C-DWECA

為了方便對算法進行描述，本文首先對問題進行了規(guī)范化。設(shè)數(shù)據(jù)流S={x1，x2，…，xt}是一個批處理序列，其中xt表示第t個傳入集成中的數(shù)據(jù)實例。數(shù)據(jù)流傳入集成中之后，通過m個基分類器進行訓(xùn)練，將m個結(jié)果融合共同決策，得到最終的決策結(jié)果。

2.1 C-ECA

C-ECA通過準(zhǔn)確率對集成數(shù)目進行更新。圖3（a）展示了傳統(tǒng)集成分類算法中基分類器的更新方式，在更新前后，基分類器數(shù)目保持不變；圖3（b）、圖3（c）展示了本文基分類的更新方式。其中，在上坡學(xué)習(xí)時，訓(xùn)練基分類器后，基分類器數(shù)目增加；在下坡學(xué)習(xí)時，訓(xùn)練基分類器之后，基分類器數(shù)目減少。

圖3 基分類器更新方式Fig.3 Base classifier update methods

C-ECA 與一些傳統(tǒng)的集成分類方法一樣，都是使用霍夫丁樹作為基分類器構(gòu)建集成。在傳統(tǒng)集成分類算法中，集成數(shù)目設(shè)置為固定值，通過替換相同數(shù)量的基分類器對集成進行更新。例如，在自適應(yīng)多樣性的在線增強（Adaptable Diversity-based Online Boosting，ADOB）算法［19］中，集成數(shù)目為10，在基分類器更新時，通過比較準(zhǔn)確率，添加一個新的基分類器，并且刪除一個性能最差的基分類器；在IBS 算法［20］中，在比較準(zhǔn)確率之后，一次添加多個基分類器，同時刪除相同數(shù)量的基分類器。C-ECA 則是以分類器池中N個基分類器為起始，在基分類器更新時，通過比較準(zhǔn)確率，一次添加一個基分類器，在右邊區(qū)間內(nèi)確定準(zhǔn)確率最高時集成數(shù)目；同時，在左邊區(qū)間確定準(zhǔn)確率最高時集成數(shù)目，在進行比較之后，確定最佳集成數(shù)目。

圖4 是C-ECA 示意圖，該算法首先創(chuàng)建一個分類器池Π，對實例進行訓(xùn)練；在輸入數(shù)據(jù)流時使用FHDDM 概念漂移檢測器進行檢測，如果發(fā)生概念漂移，則將當(dāng)前的數(shù)據(jù)流實例緩存到窗口，重置當(dāng)前基分類器，使用窗口中的實例重新訓(xùn)練基分類器，加入分類器池。C-ECA 根據(jù)準(zhǔn)確率對基分類器進行更新，在增加基分類器時，遵循一次增加一個基分類器的原則，在增加的同時也會將權(quán)值小于閾值Θ的基分類器進行刪除；在減少基分類器時，根據(jù)閾值刪除性能最差的基分類器；最后，確定最佳集成數(shù)目。

圖4 C-ECA示意圖Fig.4 Schematic diagram of C-ECA algorithm

2.2 C-DWECA

相較于C-ECA，C-DWECA 同樣根據(jù)準(zhǔn)確率來判斷是否向集成中添加或刪除基分類器。C-DWECA 在C-ECA 的基礎(chǔ)上提出了一個加權(quán)函數(shù)w(x)，w(x)為不同數(shù)據(jù)流對應(yīng)的基分類器最佳權(quán)值，根據(jù)數(shù)據(jù)實例被正確分類權(quán)值和被錯誤分類權(quán)值對權(quán)值進行調(diào)整，改變基分類器原來的權(quán)值，從而達到提高算法準(zhǔn)確率的目的。

AWDOB（Accuracy Weighted Diversity-based Online Boosting）［21］是基于準(zhǔn)確率加權(quán)的集成分類算法，在數(shù)據(jù)流中頻繁發(fā)生目標(biāo)分布變化時提高基分類器的準(zhǔn)確率，通過引入一個準(zhǔn)確率加權(quán)方案，使用當(dāng)前基分類器的準(zhǔn)確率以及所有基分類器正確分類和錯誤分類的實例總和，將當(dāng)前基分類器的權(quán)值分配給數(shù)據(jù)流中當(dāng)前實例。基分類器的權(quán)值計算如式（1）、（2）所示：

C-DWECA 通過對基分類器權(quán)值w(x)的控制，在不同數(shù)據(jù)流上依據(jù)準(zhǔn)確率對w(x)進行動態(tài)調(diào)節(jié)，根據(jù)實例xt被正確分類權(quán)值Wr和錯誤分類權(quán)值Wc，向其中添加加權(quán)函數(shù)w(x)，如式（3）、（4）所示：

其中：Wr表示正確分類實例的權(quán)值，Wc表示錯誤分類實例的權(quán)值表示基分類器正確分類的實例總數(shù)，表示基分類器錯誤分類的實例總數(shù)；N表示到目前為止在數(shù)據(jù)流中看到的實例數(shù)；accm表示當(dāng)前基分類器的準(zhǔn)確率；M表示集成數(shù)目。

式（3）、（4）是對基分類器權(quán)值更改的具體過程，式（6）是式（5）的推算過程。數(shù)據(jù)流實例被正確分類和被錯誤分類所占的比例是通過追蹤每個基模型正確分類和錯誤分類的訓(xùn)練實例（分別為Wr和Wc）的總權(quán)重并使用它們來更新每個基模型的誤差εe來完成的。μt是對誤差率εe歸一化處理，wf是第t個基分類器通過加權(quán)函數(shù)最終分配權(quán)值，分別如式（7）、（8）。

進行歸一化處理：

加權(quán)函數(shù)w(x)是不同數(shù)據(jù)流中基分類器對應(yīng)的最佳權(quán)值，w(x)函數(shù)如式（9）所示：

算法第1）～6）行先傳入數(shù)據(jù)流S，初始化分類器池的數(shù)量N，初始化權(quán)值w，創(chuàng)建新的基分類器m，并利用分類器池進行預(yù)測，然后使用FHDDM 進行概念漂移檢測。第7）～16）行是上坡的過程，先創(chuàng)建一個新的基分類器，加入分類器池中，根據(jù)本文所提出的式（3）、（4）計算正確分類實例的權(quán)值和錯誤分類實例的權(quán)值；之后判斷分類器池中是否存在權(quán)值小于閾值Θ的基分類器，如果存在則刪除此基分類器，否則直接進行預(yù)測；最后利用更新后的基分類器池進行預(yù)測并進行概念漂移的檢測。第17）～26）行是下坡的過程，算法直接根據(jù)閾值來刪除性能最差的基分類，利用更新后的分類器池進行預(yù)測并檢測概念漂移。最后，輸出分類器池中基分類器的數(shù)量，即集成數(shù)目Nm與準(zhǔn)確率。

2.3 概念漂移的處理

本文使用了FHDDM 概念漂移檢測方法作為概念漂移檢測器，具有更好的性能。其中處理概念漂移的偽代碼如算法2 所示。

算法2 FHDDM概念漂移檢測方法。

算法第1）行將窗口大小設(shè)置為n；第2）行初始化delta；第3）行計算閾值ε；第4）行重置窗口與μm值（μm為正確分類的最大平均值）；第5）～8）行如果窗口為滿，則從尾部丟棄一個實例，并在窗口頭部插入一個實例；第9）行計算窗口內(nèi)正確分類的平均值；第10）～12）行更新μm值；第13）～18）行如果窗口內(nèi)正確分類平均值與最大平均值之差大于閾值ε，則表明發(fā)生了漂移，執(zhí)行重置過程。

3 實驗結(jié)果與分析

本文實驗硬件環(huán)境是Intel Core i7 2600k+256 GB RAM的PC，操作系統(tǒng)是Windows 10 專業(yè)版，軟件環(huán)境是大規(guī)模在線分析（Massive Online Analysis，MOA）開源平臺［22］，所有實驗數(shù)據(jù)流全部由MOA 生成。

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

Agrawal 數(shù)據(jù)流包含了1 000 000 條數(shù)據(jù)實例，10 條屬性，2 個類標(biāo)簽（groupA，groupB），數(shù)據(jù)流Agrawal-1、Agrawal-2、Agrawal-3 是對Agrawal 數(shù)據(jù)流中的某些參數(shù)修改之后得到。function 表示使用的分類功能；InstanceRandomSeed 表示隨機生成實例的種子；peturbFraction 表示引入數(shù)字值的干擾量（噪聲）。其中，各個參數(shù)的具體設(shè)置值如表1 所示。Hyperplane-1 數(shù)據(jù)流包含了500 000 條數(shù)據(jù)實例，11 條屬性，2個類標(biāo)簽（class1，class2）；Hyperplane-2、Hyperplane-3 也是通過數(shù)據(jù)流Hyperplane 得到的，其中，具體的參數(shù)設(shè)置如表2 所示。InstanceRandomSeed 表示隨機生成實例的種子，numAtts表示要生成的屬性數(shù)，默認(rèn)值為2；numDriftAtts 表示具有概念漂移的屬性；noisePercentage 表示要添加數(shù)據(jù)中的噪聲比，默認(rèn)值為5。Wave 數(shù)據(jù)流包含了22 條屬性，3 個類標(biāo)簽（class1，class2，class3）；其中，前面的21 個屬性均在實數(shù)的范圍內(nèi)取值。SEA 數(shù)據(jù)流是合成數(shù)據(jù)流，包含了4 條屬性，2個類標(biāo)簽（groupA，groupB）；它是由3 個隨機生成的實數(shù)特征和2 個正負(fù)類別組成的，可以通過改變參數(shù)的值來引入概念漂移。LED（Light Emitting Diode）數(shù)據(jù)流具有概念漂移的特性，包含25 條屬性，其中前24 條屬性是布爾類型。RandomRBF 數(shù)據(jù)流包含了500 000 條實例，11 條屬性，以及5個不同的類標(biāo)簽。

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

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

3.2 分析結(jié)果

3.2.1 集成數(shù)目對準(zhǔn)確率的影響

在傳統(tǒng)的集成學(xué)習(xí)算法中，不管是一次更新一個基分類器還是一次更新多個基分類器，都是對基分類器進行了替換，更新前后集成數(shù)目不變。本文提出的算法不是對基分類器進行替換，而是根據(jù)準(zhǔn)確率對基分類器進行更新，確定最佳集成數(shù)目。

圖5（a）～（d）是C-ECA 在Wave、SEA、Hyperplane-1、Agrawal-1 數(shù)據(jù)流上對準(zhǔn)確率的影響。從圖中可以看出在Wave 數(shù)據(jù)流上，當(dāng)集成數(shù)目為6 的時候，算法的準(zhǔn)確率最高（85.38%）；在SEA 數(shù)據(jù)流上，集成數(shù)目為5 時，準(zhǔn)確率最高（89.65%），在Hyperplane-1 數(shù)據(jù)流上，集成數(shù)目為2 時，算法的準(zhǔn)確率最高（91.72%）；C-ECA 在Agrawal-1 數(shù)據(jù)流上，集成數(shù)目為12 時算法準(zhǔn)確率最高（94.64%）。圖5（e）～（g）是C-DWECA 在Agrawal-2、SEA、隨機徑向基函數(shù)數(shù)據(jù)流（Ramdom Radial Basis Function，RamdomRBF）上對準(zhǔn)確率的影響。當(dāng)集成數(shù)目為17 時，算法在Agrawal-2 數(shù)據(jù)流上準(zhǔn)確率最高，為94.24%；在SEA 數(shù)據(jù)流上，當(dāng)集成數(shù)目為12 時，算法準(zhǔn)確率最高；在RamdomRBF 數(shù)據(jù)流上，集成數(shù)目為11時，算法準(zhǔn)確率最高。總體來說，C-ECA 大多在集成數(shù)目小于10 的時候，算法準(zhǔn)確率能達到最高，但在Agrawal-1 數(shù)據(jù)流上集成數(shù)目大于10 的時候算法準(zhǔn)確率最高；S-DWECA 算法則是在集成數(shù)目大于10 的時候，算法準(zhǔn)確率達到最高。

圖5 集成數(shù)目對準(zhǔn)確率的影響Fig.5 Influence of ensemble number on accuracy

3.2.2 算法準(zhǔn)確率對比

將C-ECA 與12 個對比算法在11 種不同的數(shù)據(jù)流上進行實驗，詳細(xì)結(jié)果見表3，其中，準(zhǔn)確率最高的數(shù)值都用粗體表示。從準(zhǔn)確率方面來進行分析，C-ECA 在Agrawal數(shù)據(jù)流上集成數(shù)目為12時，除了C-DWECA、LimAttClassifier 算法之外，準(zhǔn)確率均高于其余的算法 ；在 RandomRBF（RandomRBFGenerator）數(shù)據(jù)流上集成數(shù)目為10 時，除CDWECA、杠桿裝袋（Leveraging Bagging，LevBag）、自適應(yīng)隨機森林（Adaptive Random Forest，ARF）算法之外，算法準(zhǔn)確率均高于其余算法。在Wave 數(shù)據(jù)流上準(zhǔn)確率高于ADOB、BOLE（Boosting-like Online Learning Ensemble）、OzaBoost（Oza and Russell’s online Boosting）、AUE2（Accuracy Updated Ensemble）、OAUE（Online Accuracy Updated Ensemble）、LevBag（Leveraging Bagging）、OCBoost（Online Coordinate Boosting）、ADACC（Anticipative and Dynamic Adaptation to Concept Changes）、LimAttClassifier（combining restricted hoeffding tees using stacking）。在SEA（SEAGenerator）數(shù)據(jù)流上C-ECA 的集成數(shù)目為9，算法的準(zhǔn)確率高于ADOB、BOLE、OzaBoost、ADACC、LimAttClassifier。在LED 數(shù)據(jù)流上算法的集數(shù)目小為10 時，準(zhǔn)確率高于ADOB、BOLE、OzaBoost、OAUE、LevBag、OCBoost、ADACC、LimAttClassifier。

表3 C-ECA、C-DWECA與不同對比算法的準(zhǔn)確率對比 單位：%Tab.3 Accuracy comparison among C-ECA，C-DWECA and different comparison algorithms unit：%

C-DWECA 是在C-ECA 的基礎(chǔ)上進行修改的，算法在準(zhǔn)確率方面得到了很大的提升。C-DWECA 在本文所提到的11個數(shù)據(jù)流中準(zhǔn)確率均最高。在Agrawal、Agrawal-1、RandomRBF 數(shù)據(jù)流中，C-DWECA 的準(zhǔn)確率分別達到了97.24%、97.29%、97.44%；在Agrawal-3 數(shù)據(jù)流上，算法的準(zhǔn)確率比ADACC 算法提升了49%，比BOLE 算法提升了21%，比OCBoost 提升了26%，比LimAttClassifier 提升了30%；在Hyperplane-1 數(shù)據(jù)流中，算法的準(zhǔn)確率比ADOB 提升了近86%，比LimAttClassifier 提升了18%；在Hyperplane-2 數(shù)據(jù)流上，算法的準(zhǔn)確率比ADOB 提升了50%，比ADACC 提升了15%，比LimAttClassifier 提升了21%；在Hyperplane-3 數(shù)據(jù)流上，算法的準(zhǔn)確率比ADOB 提升了85%，比LimAttClassifier 提升了18%；在Wave 數(shù)據(jù)流上，算法的準(zhǔn)確率比ADOB 提升了175%，比ADACC 提升了17%；在LED 數(shù)據(jù)流上，C-DWECA的準(zhǔn)確率達到了80.42%，而對比算法中，ADOB 的準(zhǔn)確率僅有9.98%，準(zhǔn)確率相對較高的是ARF 算法（74.21%），并且比ADACC 的準(zhǔn)確率提升了39%；在SEA 數(shù)據(jù)流上，C-DWECA的準(zhǔn)確率達到了91.07%，均高于其余的對比算法。

Agrawal 數(shù)據(jù)流中，peturbFraction 表示具有噪聲屬性，C-ECA、C-DWECA 能很好地處理噪聲數(shù)據(jù)，在Agrawal 數(shù)據(jù)流上，除C-DWECA、LimAttClassifier 算法外，C-ECA 的準(zhǔn)確率均高于其余算法；C-DWECA 的準(zhǔn)確率則高于所有對比算法。同樣地，在數(shù)據(jù)流Agrawal-1、Agrawal-2、Agrawal-3 數(shù)據(jù)流上，兩個算法也表現(xiàn)出了很好的性能。Hyperplane 數(shù)據(jù)流具有概念漂移、噪聲屬性，C-ECA、C-DWECA 在Hyperplane 數(shù)據(jù)流上也表現(xiàn)出很好的性能。SEA、LED 數(shù)據(jù)流都有概念漂移的屬性，C-ECA、C-DWECA 均可以很好地處理概念漂移，在SEA、LED 數(shù)據(jù)流上準(zhǔn)確率都比較高。

表4 展示了算法在11 個數(shù)據(jù)流上的平均準(zhǔn)確率，從表中可以看出本文所提出的C-DWECA 的平均準(zhǔn)確率達到了92.60%，其中，C-DWECA 的平均準(zhǔn)確率比ADOB 提升了40%，比OCBoost 算法提升了18%，比ADACC 算法提升了18%，比LimAttClassifier 算法提升了14%。為了能更直觀地對算法的準(zhǔn)確率進行比較分析，繪制了在數(shù)據(jù)流Agrawal-1、Agrawal-2 上的折線圖。其中，在圖6 中考慮到圖示的效果，所以一些準(zhǔn)確率較低的算法沒有在圖中進行展示；從圖6 中可以看出，本文所提出的C-DWECA 在準(zhǔn)確率方面明顯優(yōu)于其他對比算法，并且可以同時適應(yīng)帶有概念漂移和噪聲的流數(shù)據(jù)，整體性能表現(xiàn)優(yōu)異。

表4 不同算法的平均準(zhǔn)確率Tab.4 Average accuracies of different algorithms

圖6 不同算法準(zhǔn)確率對比Fig.6 Accuracy comparison of different algorithms

3.2.3 生成樹的規(guī)模以及時間效率比較

在實驗的過程中發(fā)現(xiàn)，生成樹規(guī)模的大小也是衡量算法性能的一個重要的指標(biāo)，本節(jié)的主要目的是驗證C-ECA 在各個數(shù)據(jù)流上樹生成規(guī)模表現(xiàn)出來的優(yōu)異性能。ADOB 算法在幾種數(shù)據(jù)流上準(zhǔn)確率表現(xiàn)得相對較低，ARF、ADACC 以及LimAttClassifier 算法在實驗過程中樹的性能表現(xiàn)不穩(wěn)定。由于樹規(guī)模的研究是在準(zhǔn)確率差別不大，以及生成樹的規(guī)模相對穩(wěn)定的條件下進行研究的，所以，本節(jié)不對這幾種算法進行研究。算法分別在Agrawal、Hyperplane、Wave、SEA、LED、RandomRBF 數(shù)據(jù)流上進行了實驗，數(shù)據(jù)實例均為50 000 條，實驗結(jié)果如圖7 所示。

圖7 不同算法的生成樹深度對比Fig.7 Spanning tree depth comparison of different algorithms

C-ECA 在5 個數(shù)據(jù)流上樹的深度表現(xiàn)都很優(yōu)秀；在Agrawal-2 數(shù)據(jù)流上，C-ECA 樹的深度為5.1，相較其余的算法均小一點，比起OAUE 算法，C-ECA 表現(xiàn)出了令人驚喜的結(jié)果；同樣在Hyperplane 數(shù)據(jù)流上，C-ECA 在樹的深度方面也表現(xiàn)得最優(yōu)異，比起AUE2 算法，C-ECA 樹的深度減小了6.7；在SEA 和LED 數(shù)據(jù)流上，C-ECA 也表現(xiàn)出了令人欣喜的優(yōu)勢。在RandomRBF 數(shù)據(jù)流上，C-ECA 的樹的深度也比AUE2、OAUE、LevBag 和OzaBag 算法表現(xiàn)得要好。

表5 主要展示了算法的時間效率的結(jié)果，從表中可以看出C-DWECA 在時間效率上表現(xiàn)并不是很好，這是由于在對集成數(shù)目進行更新時，隨著集成數(shù)目的改變，算法的運行時間會更長；并且在對基分類器分配不同權(quán)值之后，訓(xùn)練時也對算法的時間效率有影響。

表5 C-ECA、C-DWECA與不同對比算法的時間效率對比 單位：sTab.5 Comparison of time efficiency between C-ECA，C-DWECA algorithms and different comparison algorithms unit：s

為了能更直觀地觀察實驗結(jié)果的情況，通過圖的形式對實驗結(jié)果進行了展示。其中圖7（a）～（d）分別展示了在Agrawal-2、Hyperplane、Hyperplane-1 以及SEA 數(shù)據(jù)流上生成樹深度的大小，從圖7（a）和圖7（d）可以很直觀地看出本文所提出的C-ECA 在生成樹的深度上表現(xiàn)出了很優(yōu)異的結(jié)果。

4 結(jié)語

隨著數(shù)據(jù)流的復(fù)雜性日益增加，在現(xiàn)實生活中對集成分類算法的要求越來越嚴(yán)格。本文設(shè)計并研究了準(zhǔn)確率爬坡集成分類算法（C-ECA）和基于爬坡的動態(tài)加權(quán)集成分類算法（C-DWECA），用于解決數(shù)據(jù)流問題?；趥鹘y(tǒng)算法中集成數(shù)目設(shè)置為固定值的思想，C-ECA 依據(jù)準(zhǔn)確率對集成數(shù)目進行更新。C-DWECA 是對C-ECA 的改進，通過加權(quán)函數(shù)w(x)來對基分類器的權(quán)值進行更新，為每個基分類器分配合適的權(quán)值，從而達到提高分類準(zhǔn)確率的目的。通過實驗結(jié)果表明，C-ECA 和C-DWECA 在分類準(zhǔn)確率方面優(yōu)于其他算法，C-DWECA 在RandomRBF 數(shù)據(jù)流上準(zhǔn)確率更是達到了97.44%；但是，在時間效率方面，C-ECA 和C-DWECA 相對低一點，這是因為集成數(shù)目在相對多的時候，運行時間也相對久一點，并且權(quán)值的分配也會消耗一定的時間。在未來的工作中，將著重于提高改進算法的時間效率，在保證準(zhǔn)確性的前提下，使算法的執(zhí)行時間更短。