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

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

0 引言

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

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

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

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

2）設(shè)計(jì)了基于爬坡的動(dòng)態(tài)加權(quán)集成分類算法（Dynamic Weighted Ensemble Classification Algorithm based on Climbing，C-DWECA）。在實(shí)際訓(xùn)練實(shí)例時(shí)，不同基分類器在不同數(shù)據(jù)流上的預(yù)測性能存在差異，所以，需要對不同基分類器分配合適的權(quán)值。因此，本文在C-ECA 的基礎(chǔ)上，設(shè)計(jì)了一個(gè)新的加權(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ù)有序到達(dá)、無限長度、概念漂移等［14］。因此，構(gòu)建更健壯的模型以迅速有效地從數(shù)據(jù)中提取有意義的信息變得更加重要。

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

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

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

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

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

2 C-ECA和C-DWECA

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

2.1 C-ECA

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

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

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

圖4 是C-ECA 示意圖，該算法首先創(chuàng)建一個(gè)分類器池Π，對實(shí)例進(jìn)行訓(xùn)練；在輸入數(shù)據(jù)流時(shí)使用FHDDM 概念漂移檢測器進(jìn)行檢測，如果發(fā)生概念漂移，則將當(dāng)前的數(shù)據(jù)流實(shí)例緩存到窗口，重置當(dāng)前基分類器，使用窗口中的實(shí)例重新訓(xùn)練基分類器，加入分類器池。C-ECA 根據(jù)準(zhǔn)確率對基分類器進(jìn)行更新，在增加基分類器時(shí)，遵循一次增加一個(gè)基分類器的原則，在增加的同時(shí)也會將權(quán)值小于閾值Θ的基分類器進(jìn)行刪除；在減少基分類器時(shí)，根據(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ǔ)上提出了一個(gè)加權(quán)函數(shù)w(x)，w(x)為不同數(shù)據(jù)流對應(yīng)的基分類器最佳權(quán)值，根據(jù)數(shù)據(jù)實(shí)例被正確分類權(quán)值和被錯(cuò)誤分類權(quán)值對權(quán)值進(jìn)行調(diào)整，改變基分類器原來的權(quán)值，從而達(dá)到提高算法準(zhǔn)確率的目的。

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

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

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

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

進(jìn)行歸一化處理：

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

2.3 概念漂移的處理

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

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

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

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

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

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

Agrawal 數(shù)據(jù)流包含了1 000 000 條數(shù)據(jù)實(shí)例，10 條屬性，2 個(gè)類標(biāo)簽（groupA，groupB），數(shù)據(jù)流Agrawal-1、Agrawal-2、Agrawal-3 是對Agrawal 數(shù)據(jù)流中的某些參數(shù)修改之后得到。function 表示使用的分類功能；InstanceRandomSeed 表示隨機(jī)生成實(shí)例的種子；peturbFraction 表示引入數(shù)字值的干擾量（噪聲）。其中，各個(gè)參數(shù)的具體設(shè)置值如表1 所示。Hyperplane-1 數(shù)據(jù)流包含了500 000 條數(shù)據(jù)實(shí)例，11 條屬性，2個(gè)類標(biāo)簽（class1，class2）；Hyperplane-2、Hyperplane-3 也是通過數(shù)據(jù)流Hyperplane 得到的，其中，具體的參數(shù)設(shè)置如表2 所示。InstanceRandomSeed 表示隨機(jī)生成實(shí)例的種子，numAtts表示要生成的屬性數(shù)，默認(rèn)值為2；numDriftAtts 表示具有概念漂移的屬性；noisePercentage 表示要添加數(shù)據(jù)中的噪聲比，默認(rèn)值為5。Wave 數(shù)據(jù)流包含了22 條屬性，3 個(gè)類標(biāo)簽（class1，class2，class3）；其中，前面的21 個(gè)屬性均在實(shí)數(shù)的范圍內(nèi)取值。SEA 數(shù)據(jù)流是合成數(shù)據(jù)流，包含了4 條屬性，2個(gè)類標(biāo)簽（groupA，groupB）；它是由3 個(gè)隨機(jī)生成的實(shí)數(shù)特征和2 個(gè)正負(fù)類別組成的，可以通過改變參數(shù)的值來引入概念漂移。LED（Light Emitting Diode）數(shù)據(jù)流具有概念漂移的特性，包含25 條屬性，其中前24 條屬性是布爾類型。RandomRBF 數(shù)據(jù)流包含了500 000 條實(shí)例，11 條屬性，以及5個(gè)不同的類標(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í)算法中，不管是一次更新一個(gè)基分類器還是一次更新多個(gè)基分類器，都是對基分類器進(jìn)行了替換，更新前后集成數(shù)目不變。本文提出的算法不是對基分類器進(jìn)行替換，而是根據(jù)準(zhǔn)確率對基分類器進(jìn)行更新，確定最佳集成數(shù)目。

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

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

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

將C-ECA 與12 個(gè)對比算法在11 種不同的數(shù)據(jù)流上進(jìn)行實(shí)驗(yàn)，詳細(xì)結(jié)果見表3，其中，準(zhǔn)確率最高的數(shù)值都用粗體表示。從準(zhǔn)確率方面來進(jìn)行分析，C-ECA 在Agrawal數(shù)據(jù)流上集成數(shù)目為12時(shí)，除了C-DWECA、LimAttClassifier 算法之外，準(zhǔn)確率均高于其余的算法 ；在 RandomRBF（RandomRBFGenerator）數(shù)據(jù)流上集成數(shù)目為10 時(shí)，除CDWECA、杠桿裝袋（Leveraging Bagging，LevBag）、自適應(yīng)隨機(jī)森林（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 時(shí)，準(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ǔ)上進(jìn)行修改的，算法在準(zhǔn)確率方面得到了很大的提升。C-DWECA 在本文所提到的11個(gè)數(shù)據(jù)流中準(zhǔn)確率均最高。在Agrawal、Agrawal-1、RandomRBF 數(shù)據(jù)流中，C-DWECA 的準(zhǔn)確率分別達(dá)到了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)確率達(dá)到了80.42%，而對比算法中，ADOB 的準(zhǔn)確率僅有9.98%，準(zhǔn)確率相對較高的是ARF 算法（74.21%），并且比ADACC 的準(zhǔn)確率提升了39%；在SEA 數(shù)據(jù)流上，C-DWECA的準(zhǔn)確率達(dá)到了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ù)流上，兩個(gè)算法也表現(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 個(gè)數(shù)據(jù)流上的平均準(zhǔn)確率，從表中可以看出本文所提出的C-DWECA 的平均準(zhǔn)確率達(dá)到了92.60%，其中，C-DWECA 的平均準(zhǔn)確率比ADOB 提升了40%，比OCBoost 算法提升了18%，比ADACC 算法提升了18%，比LimAttClassifier 算法提升了14%。為了能更直觀地對算法的準(zhǔn)確率進(jìn)行比較分析，繪制了在數(shù)據(jù)流Agrawal-1、Agrawal-2 上的折線圖。其中，在圖6 中考慮到圖示的效果，所以一些準(zhǔn)確率較低的算法沒有在圖中進(jìn)行展示；從圖6 中可以看出，本文所提出的C-DWECA 在準(zhǔn)確率方面明顯優(yōu)于其他對比算法，并且可以同時(shí)適應(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ī)模以及時(shí)間效率比較

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

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

C-ECA 在5 個(gè)數(shù)據(jù)流上樹的深度表現(xiàn)都很優(yōu)秀；在Agrawal-2 數(shù)據(jù)流上，C-ECA 樹的深度為5.1，相較其余的算法均小一點(diǎn)，比起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 主要展示了算法的時(shí)間效率的結(jié)果，從表中可以看出C-DWECA 在時(shí)間效率上表現(xiàn)并不是很好，這是由于在對集成數(shù)目進(jìn)行更新時(shí)，隨著集成數(shù)目的改變，算法的運(yùn)行時(shí)間會更長；并且在對基分類器分配不同權(quán)值之后，訓(xùn)練時(shí)也對算法的時(shí)間效率有影響。

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

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