潘科學

（四川大學計算機學院，成都 610065）

0 引言

隨著電信、網絡等信息技術的迅速發(fā)展、時序應用不斷涌現，其中出現了大量的數據流，如電信通話記錄、網上購物交易記錄、股票交易記錄、文星探測和天文觀測數據等。這些數據流中隱含著豐富的、有價值的信息亟待挖掘。然而與傳統(tǒng)數據形式不同，數據流具有海量、實時、有序、動態(tài)等特點，若采用傳統(tǒng)的數據挖掘模型，則會丟失大量有價值的信息，而且會耗費大量的時間、空間，因此對數據流的分類成為機具挑戰(zhàn)的工作[1]。

為適應數據流海量、實時、動態(tài)等特點、分類模型應具有良好的時空性能、且在抗噪性、適應性方面也具有良好表現。H.X.Wang等[2]證明了與單模型相比，集成分類方法在分類性能尤其是抗噪性能方面具有一定的優(yōu)勢。諸多研究也表明構造一系列簡單的分類器比建立一個復雜的但分類器更加簡單可行，可以說，集成分類方法是一種有效的數據流分類方法。

針對數據流的特點，近年來學術界涌現出大量針對數據流集成分類的工作，Wang[3]等人提出了在數據流上的集成分類器，它把數據流分為不同的時間段，利用每一時段的訓練數據學習一個分類器，針對每一個分類模型，利用最新到達的數據決定他的權重，最后用多個分類器共同預測未來數據，與單分類器相比，集成分類器有更高的分類準確率。此后，Street[4]等人提出了SEA算法，它采用啟發(fā)式策略根據正確率和數據特征取代表現較差的分類器，以提高分類性能。Yu等人[5]使用集成學習方法對多標簽數據分類問題進行研究，并最終將所提出模型在生物蛋白功能判定領域進行應用，通過實驗驗證了有效性。Li等人[6]針對集成學習模型中的結果融合部分進行研究，提出一種基于權值的分類結果選擇方法（DCE.cc），通過對不同個體分離輸出結果進行判定，將個體分類器賦予不同的權重，并根據權重，對分類結果進行針對性匯總，從而避免誤分類模型對整體分類結果的影響。Omid等人針對數據流的動態(tài)性，將數據流劃分成不同的數據塊，根據模型在各數據塊的表現判斷概念漂移是否發(fā)生，通過更新模型提升分類精度[7]。Bieft等對近年來主流的數據流集成分類方法機型總結和分類[8]。

綜上所述，對于數據流的集成分類仍處于研究階段，現存的方法人存在各種各樣的弊端，如分類器組合、樣本選取、基分類器獨立性等。基于此，本文設計一種針對數據流的集成學習方法，通過與單一模型進行比較，發(fā)現集成模型確實有著單一模型不能比擬的性能。

1 集成學習

1.1 集成學習理論

集成學習是使用一系列弱學習器進行學習，并使用某種規(guī)則把各個學習結果進行整合從而獲得比單個學習器更好的學習效果的一種機器學習方法。它的思想非常簡單，集合多個模型的能力，達到“三個臭皮匠，賽過諸葛亮”的效果。

將一組學習方式、學習能力不同的同質或異質分類模型進行組合而獲得集成分類模型，其直觀感覺是所構成的集成模型分類性能應該介于最好的單模型分類器與最差的分類器之間。但是許多學者通過大量實驗證明，集成分類模型的學習性能要優(yōu)于最好的單體分類器[9]。首先，從統(tǒng)計的角度來看，由于學習任務的假設空間往往很大，可能有多個假設在訓練集達到同等性能，此時若使用單學習器可能會因誤選而導致泛化性能不佳，結合眾多策略則會減少這一風險；第二，從計算角度來看，學習算法往往會陷入局部極小，有的局部極小點所對應的泛化性能可能很糟糕，而通過多次運行之后進行結合，可降低陷入局部極小點的風險；第三，從表示的角度來看，某些學習任務的真實假設可能不在當前學習算法所考慮的假設空間中，此時若使用單學習器肯定無效，而通過結合多個學習器，由于相應假設空間有所擴大，有可能學的更好的近似結果。圖1為更直觀的示意圖：

圖1 集成學習分析的三種角度

1.2 集成策略

集成學習結合策略主要分為兩類：Averaging meth?ods和 Boosting methods。

●Averaging methods核心是引入隨機（對樣本、特征屬性隨機取樣）學習產生多個獨立的模型，然后平均所有模型的預測值。一般而言，這種方法，會減小方差（variance），不太會過擬合。主要包括bagging、RF。

●Boosting methods逐步加強方法，該方法集合學習多個模型，提高模型的準確率。不同的是，它是基于前面模型的訓練結果（誤差），生成新的模型，從而減小偏差（bias）。一般而言，這種方法會比上者的準確率高一點，但是也不是絕對的。它的缺點是有過擬合的風險，另外，由于它每個模型是“序列化”（有前后關系）產生的，不易并行化。它的代表是AdaBoost、GDBT。

Bagging:Bagging在原始樣本中隨機抽樣獲取子集，用隨機抽樣的子集訓練基學習器（base_estimator），然后對每個基學習器的結果求平均，最終得到的預測值。隨機獲取樣本子集的方法有很多中，最常用的是有放回抽樣的booststrap，也可以是不放回的抽樣?；鶎W習器可以是相同的模型，也可以是不同的，一般使用的是同一種基學習器，最常用的是DT決策樹。由于bagging提供了一種降低方差（variance）的方式，所以一般會使用易受樣本擾動的分類器。

隨機森林：用隨機的方式建立一個森林，森林里面有很多的決策樹組成，隨機森林的每一棵決策樹之間是沒有關聯(lián)的。在得到森林之后，當有一個新的輸入樣本進入的時候，就讓森林中的每一棵決策樹分別進行一下判斷，看看這個樣本應該屬于哪一類（對于分類算法），然后看看哪一類被選擇最多，就預測這個樣本為那一類。

AdaBoost：AdaBoost是一種 Boosting方法，與 Bag?ging不同的是，AdaBoost中不同的子模型必須是串行訓練獲得的，每個新的子模型都是根據已訓練出的模型性能來進行訓練的，而且Boosting算法中基學習器為弱學習器。AdaBoost中每個訓練樣本都有一個權重且每次迭代生成新的子模型使用的訓練數據都相同，但是樣本的權重會不一樣。AdaBoost會根據當前的錯誤率，增大錯誤樣本權重，減小正確樣本權重的原則更新每個樣本的權重。不斷重復訓練和調整權重，直到訓練錯誤率或弱學習器的個數滿足用戶指定的值為止。

2 基于權重的集成學習方法

集成分類方法是目前數據流分類的一種主要方法，通過在不同數據塊上構建分類器并對這些分類器進行組合，以達到比單一分類器性能更好的目標。本節(jié)基于權重集成方法設計了一個集成分類模型，研究表明，基于權重集成的方法[10]具有以下優(yōu)點：

（1）利用多個歷史數據塊的信息用于當前數據的測試。

（2）最終的決策是基于多個歷史數據塊訓練的結果，一定程度上減弱了噪聲數據對分類精度的影響。

2.1 基分類器選取

傳統(tǒng)分類方法都已應用于數據流集成分類方法中，本文模型在集成決策樹、KNN、SOM、SVM等多個分類方法基礎上，引入樸素貝葉斯提升模型的抗噪性能。

樸素貝葉斯是一種基于統(tǒng)計理論的分類方法，很多文獻將其引入決策樹的葉子結點，用以代替?zhèn)鹘y(tǒng)的最大類預測方法[11-12]，提升抗噪性能。這是因為樸素貝葉斯為增量式學習方法，對新數據不敏感，從而提升了模型的抗噪性能。因此本文集成方法引入樸素貝葉斯以提升分類性能。

2.2 基于權重的集成方法

本文模型的主要思想為：記數據流中t時刻到達的數據塊為Dt，基于權重集成分類方法選擇一種學習方法（如VFDT[13]，SVM，DT等）對每個數據塊進行獨立學習，得到n個基分類器fi=F（Di）,并通過不同的策略對基分類器賦權值，得到集成分類器few。圖2為基于權重的集成分類方法示意圖。

圖2 集成模型框架

基于權重的集成算法：

3 實驗結果

3.1 數據集

數據集分為兩類：人工數據集、真實數據集。

人工數據集:

LED漂移數據集，MOA封裝了LED數據集的生成器，即針對屬性維是24的LED數據集版本，最多可以設置7維屬性漂移，同時可以設置不同比例的噪音。

Wave數據集含有三個類標簽，根據含有24個連續(xù)屬性或40個連續(xù)屬性形成Wave21和Wave40兩個版本，常被作為檢測數據流分類算法性能的典型數據集。

真實數據集：

Forest Covertype數據集，源于UCI數據集，它是關于森林覆蓋方面的數據庫。該數據庫含有7個類標簽，54維屬性，共581012個實例。

Electricity數據集，該數據集來自澳大利亞新南部威爾士電力市場。該數據集的描述為：電力市場的電價是變化的，反映了市場的供求關系，電價每五分鐘調整一次。該數據集包含45312個實例，兩個類標簽up和down，以及7維屬性。

3.2 實驗結果

本文實驗通過將集成模型與單一分類器進行比較，對比標準采用分類常用指標accuracy，由于是集成分類模型，實驗時將數據分成連續(xù)大小相同的數據塊，這樣做也在一定程度上適應了數據流的動態(tài)變化特性。圖2、圖3為本文模型和單一分類模型在真實數據集上的Acc值。圖3、圖2為本文模型和單一分類模型在人工數據集上的Acc值。其中縱坐標為Acc值，橫坐標為不同窗口大小。由圖可見。集成模型比單一分類模型的準確度要高。這是因為通過調整集成模型基分類器的權值，選取分類結果較好的分類器，從而使得分類準確度較高。

4 結語

數據流分類為目前比較熱門的研究方向，由于數據流自身的海量實時動態(tài)等特點，使得如何在有限的時間和空間限制內實現較高的準確度成為數據流分類的巨大的挑戰(zhàn)。本文通過構建集成分類器對數據流進行分類，并與單一模型作比較，實驗結果顯示集成模型的分類準確度比單模型較優(yōu)。

數據流的動態(tài)性為數據流的核心特點之一，動態(tài)性主要體現為概念漂移的產生，概念漂移即數據分布或類別分布發(fā)生變化，使得當前模型不在適應當前數據集，如不能及時更新模型，則模型性能則會急劇下降，此外檢測概念漂移的產生也是數據流分類的核心難題。

圖2 單一和集成模型在ele上的Acc

圖3 單一和集成模型在Forest上的Acc

圖4 單一和集成模型在LED上的Acc

圖5 單一和集成模型在Wave上的Acc

[1]Zhang P.，Gao B.J.，Liu P.，et a1.A Framework for Application-Driven Classification of Data Streams[J].Neurocomputing，2012，92（0）：170-182．

[2]H X Wang,W Fan,P S Yu，J W Han.Mining Concept-Drifting Data Streams using Ensemble Classifiers[C].

[3]Wang,H.Fan,Yu.P.S.,et al.,2003.Mining Concept-Drifting Data Streams Using Ensemble Classifiers.Proc.9th ACM AIGKDD Int.Conf.on Knowledge Discovery and Data Mining,p.226-235.

[4]Street W N,Kim Y S.A Streaming Ensemble Algorithm（SEA）for Large-Scale Classification[C].Proceedings of the S eventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2001:377-382.

[5]Yu G.，Domeniconi C.，Rangwala H．，et a1.Transductive Multi-Label Ensemble Classification for Protein Function Prediction[C]．Proceedings of the 18th ACM SIGKDD Internation81 Conference on Knowledge di scovery and Data Mining，Bei Jing，China，Aug12-16，2012：1077-1085．

[6]Li L.J．，Zou B.，Hu Q.H．，et a1.Dynamic Classifier Ensemble Using Classification Confidence[J].Neurocomputing，2013，99（1）：581-591．

[7]Omid,Ali.An Ensemble Method for Data Stream Classification in the Presence of Concept Drift.Reversion Accepted Apr.15.2015.

[8]Heitor Murilo Gomes,Jean Paul Barddal,Fabr'?cio Enembreck,and Albert Bifet.2017.A Survey on Ensemble learning for data stream Classification.ACM Comput.Surv.50,2,Article 23（March 2017）,36 pages.

[9]周志華.機器學習

[10]胡學剛，李培培等.數據流分類.

[11]J Gama,P Medas,P Rodrigues.Concept Drift in Decision Trees Learning from Data Stream[C].In:Proceedings of 4th European Symposiumon Intelligent Technology and Their Implemention on Smart Adaptive Systems.pp218-225,2004.

[12]J Gama,R Fernandes,and R Rocha.Decision Trees for Mining Data Streams[J].Journal of Intelligent Data Analysis（10）,23-45,2006.

[13]Domingos P,Hulten G.Mining High-Speed Data Streams[C].Proceedings of the Sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2000:71-80.