新型含噪數據流集成分類的算法

袁 泉，郭江帆

(1.重慶郵電大學通信新技術應用研究中心，重慶400065; 2.重慶信科設計有限公司，重慶401121)(*通信作者電子郵箱502420381@qq.com)

0 引言

隨著大數據、云計算的深入發展，每個行業都產生了海量的數據，這些數據的形式發生了變化，從傳統的靜態數據演變成動態數據。現實中的數據流不僅具有海量性、實時性、動態變化等特征，通常還伴隨著噪聲和概念漂移，這些特征無形中加大了對數據流挖掘的難度。所謂概念漂移指的是隨著數據流的不斷增加，隱含在數據流中的知識隨著時間的變化而發生變化［1］，另外，真實環境中的數據流噪聲問題也是無法避免的。雖然傳統的靜態數據挖掘技術對概念漂移和噪聲問題也有所研究，但效果不佳。為了能更快速、有效地利用數據流，目前有單一和集成兩種形式的分類算法，集成模型算法分類精度要比單一模型算法高，因此集成模型成為主流研究方向之一。

1 相關工作

在數據流分類中關于概念漂移和噪聲問題的研究，國外比國內要早。其中在數據流概念漂移問題研究中:Street等［2］在2001年提出適應概念漂移的集成分類(Streaming Ensemble Algorithm，SEA)算法，該算法采用集成決策樹方法檢測概念漂移;Kolter等［3］在2003年提出了weighted-bagging算法，該算法引入集成分類器思想，采用投票方式檢測概念漂移;Kuncheva等［4］在2009年提出了基于窗口機制的分類算法，該算法能夠有效區分概念漂移，但只適用于突變式概念漂移。在關于數據流中漸進式概念漂移問題中:Domingos等［5］在2001年提出了基于快速決策樹(Very Fast Decision Tree，VFDT)算法，該算法利用給定的空間和時間可以訓練出一個漸進于傳統算法的學習器，但是它只能處理范疇型的屬性;Liu等［6］在 2009年提出以自適應快速決策樹(Conceptadapting Very Fast Decision Tree，cVFDT)算法為基礎的基于模糊決策樹的數據流分類算法，該算法可以很好地解決數據流中的概念漂移問題，但分類精度并不是很高。

在數據流中的噪聲處理中:Chu等［7］在2004年提出集成數據流分類算法是一種期望最大化(Expectation Maximization，EM)框架，該算法是求解極大似然估計的迭代算法，精度提高的同時增加了時間代價;Gama等［8］在2006年提出的分類算法是基于伯努利數據分布，該算法適合于處理突變型概念漂移，而對于漸變型漂移效果并不明顯;Baena-García等［9］在2006年根據分類錯誤率設計了一種數據流分類算法，該方法依據模型錯誤率變化和錯誤率之間的距離來判斷概念漂移;Hashemi等［10］在2009年根據模糊邏輯理論設計了一種分類算法，該算法克服了傳統噪聲清理方法需要多次掃描的缺點，避免了噪聲對分類的影響;琚春華等［11］在2015年提出基于信息熵差異性度量的數據流增量集成分類算法，該算法引入信息熵差異性度量對分類模型進行優化，但系統開銷較大;Mirza等［12］在2015年提出極限學習機集成算法，該算法分類精度較低，泛化能力較差;呂艷霞等［13］在2016年提出了不確定數據流在線分類算法，該算法采用Hoeffding分解定理構造決策樹模型，但主要針對不確定數據流有較高的精度;陳煜等［14］在2017年提出基于紅黑樹的連續屬性數據流快速決策樹分類算法，該算法利用紅黑樹有效地處理樣本的插入，主要處理連續屬性數據流，但對離散屬性效果并不好。

以往研究中提出了大量集成分類算法，但是在對數據流中的概念漂移檢測和噪聲過濾，以及分類精度的提高等方面的研究不足。針對以上問題，本文提出了一種新型的過濾噪聲和檢測概念漂移數據流集成分類算法。該算法集成分類模型中的基分類器選擇增量式C4.5決策樹，噪聲過濾機制采用貝葉斯分類器，用μ檢驗方法檢測數據流中的概念漂移。本文進行了大量實驗和算法仿真，驗證了本文算法的分類精度 比 傳 統 算 法 ( 如 OzaBag［15］、OzaBoost［15］、Weightbagging［16］)有較大的提升。

2 數據流分類算法

本文提出了一種新型的面向噪聲和概念漂移數據流的集成分類算法(Ensemble Classification Algorithm for data streams with Noise and Concept Drifts，ECANCD)。該算法首先將數據流分成M個數據塊，根據M個數據塊建立M個增量式C4.5決策樹基分類器并進行水平集成，然后對M個數據塊建立一個噪聲過濾機制，采用貝葉斯分類器用來過濾噪聲數據的影響，利用μ檢驗方法進行概念漂移的檢測，此時模型中共有M+1個分類器。對每個增量式C4.5決策樹基分類器進行動態的加權，基分類器加權策略是將分類器的分類精度設置為權值，將分類精度最小的基分類器舍棄，以完成分類模型的更新和分類器性能的提升。

2.1 增量式C4.5決策樹

2.1.1 增量式學習方式

因C4.5算法不具有增量學習的能力，當C4.5利用當前數據塊學習訓練好模型后，如果有新到來數據塊，C4.5必須利用上一數據塊和當前數據塊重新訓練模型，因此必須對C4.5算法進行改進才能具有增量學習能力。所謂增量學習即在有新數據塊到來時，會在已有分類器的基礎上對新數據塊訓練并更新分類器，得到增量式C4.5決策樹分類器。在這個學習過程中增量式C4.5決策樹算法大幅減少了時空開銷，并且在一個集成分類器投入使用之前，很難得到所有學習訓練實例。因此，一個集成分類器具有增量學習能力是非常重要的。

2.1.2 對 C4.5 算法的改進

喬增偉等［17］在C4.5決策樹算法的增量式改進方法中曾提到，C4.5決策樹算法是單向鏈表，可以通過兩點結構改動實現增量學習過程:第一，將單向鏈表修改為雙向鏈表，在結構體里添加一個指針變量FatherNode指向父節(FatherNode=NULL時為根節點)，以實現在增量學習過程中更新某些節點屬性值;第二，通過記錄葉節點包含的實例，實現增量學習功能，即葉節點知識更新，可以添加一個動態數組DynaArray，只有NodeType=0時動態數組才分配內存。

但改進后的C4.5決策樹算法在單分類器中分類精度并不是很理想，因此本文采用集成分類算法，選擇增量式C4.5決策樹算法作為基分類器，以提高分類精度。

2.1.3 增量式C4.5算法流程

C4.5算法改進后就可以實現增量式學習，具體算法流程如圖1所示。

圖1 增量式C4.5算法流程Fig.1 Flow chart of incremental C4.5 algorithm

從圖1中分析可知:當數據流輸入時在當前模型下進行增量學習，通過決策節點判決后，當決策類別與實例類別相同時更新判決節點、實例數以及類別分布，并在動態數組中添加實例;否則，重新尋找最優屬性和分割閾值，然后生成葉節點并將其父指針指向判決節點，最后更新判決節點，刪除原節點包含的實例數。通過上述過程實現增量學習。

2.2 概念漂移檢測方法

本文檢測概念漂移的方法是大樣本檢驗母體平均數的μ檢驗方法。該檢測方法是判斷某一隨機變量的數學期望是否等于已知值的假設驗證法。

μ檢驗定義:設母體X分布是任意的，且一、二階距存在，記 EX=u，DX= δ2(δ2未知)，在母體上作假設H0:u=u0(u0是已知數)［18］。用x珋作檢驗，當無限大時，統計量U=(x珋－μ0)/(S/)近似服從標準正態分布N(0，1)，其中:x珋表示樣本平均數，S表示樣本標準差。

假設給定顯著水平 α，則存在 uα/2，使 P{|U|≥ uα/2} ≈α，即P{(X珔－ μ0)/(S/)≥ uα/2} ≈ α。

假設單個樣本被誤分類概率P{X=1}=p，正確分類的概率為P{X=0}=1－p，則可知X服從兩點分布B(1，p)。設樣本數為n，被錯誤分類數為m，則 X=m/n，S2=X(1－X)。

以上原理可以判斷數據流是否發生概念漂移。假如設當前數據塊的分類錯誤率為 error，當uα/2(其中uα/2為前M個數據塊的平均分類錯誤率)時，當前數據塊的分類錯誤率大于前M個數據塊的平均錯誤率，從而說明數據流發生了概念漂移;反之認為概念分布平穩。

2.3 ECANCD 描述

對算法中要使用的符號進行說明，設數據流中當前數據塊為S，當前數據塊S中的第i個實例為Ei，基分類器的集合為Ec，Ec基分類器的總數為M，Ec中第i個實例為Ci，Ec中當前分類器的個數為num，一個數據塊包含的實例的個數為n。

ECANCD的具體構建過程流程如下:

1)構建集成分類器。新的數據塊S通過滑動窗口到達后，判斷基分類器個數num是否小于基分類器總數M，如果num ＜M，則在S上建立一個新基分類器，并把其放入基分類器的集合Ec中;否則，在緩沖區最新的M*n條實例上建立一個噪聲過濾機制，即貝葉斯分類器。

2)過濾噪聲。當集成分類器建立完成后，使用M個基分類器和噪聲過濾機制對S中的實例進行分類，若此實例被半數以上的基分類器和貝葉斯分類器誤分類，則將這個實例放置到誤分類緩沖區。

3)檢驗概念漂移。計算Ec在數據塊S上的分類錯誤率均值error，利用μ值檢驗法對概念漂移進行檢測。

4)分類器更新。若檢測到概念漂移，則將誤分類區中所有實例讀入到數據塊S，并建立一個新的基分類器Cnew，更新每個基分類器的權值(均為S上的分類精度)。若Cnew大于基分類器中最小的權值Cmin，作則用Cnew替換Cmin，完成基分類器動態更新。

ECANCD偽代碼如下。

輸入 數據流DS;

輸出 分類模型Ec。

BEGIN

While(new data streams){

通過滑動窗口讀入一個包含n個實例的數據塊;

if(num＜M)

每個數據塊建立一個基分類器;并將其放入Ec中;

else

在讀入M個數據塊M*n個實例后建立一個噪聲過濾機制;}

for(Ei∈S){

if(Ei被Ec和噪聲過濾機制誤分類)

則把實例Ei放入誤分類區;

}

把Ec中基分類器的權值更新為S上的分類精度

if(concept drifts and num==M{

將被誤分類的實例和部分新實例構建一個新基分類器Cnew，更

新所有分類器的權值，找出權值最小的基分類器Cmin。

if(Cnew＞Cmin)

用Cnew替換Cmin;

}

}END

3 實驗結果與分析

本文實驗硬件環境為2.6 GHz處理器、8 GB內存的PC，操作系統為Windows 10，開發環境為Weka3.8和大規模在線分析系統(Massive Online Analysis，MOA)。本文分別從檢測概念漂移的準確性、抗噪性、分類精度、基分類器性能等方面在 KDDCup、Hyper Plane、Kaggle 數據集［19］進行了驗證，并和OzaBag、OzaBoost、Weight-bagging等其他經典的數據流分類算法進行了嚴格比較。實驗中使用的概念漂移基準數據集均由開源工具MOA中的數據生成器生成。

3.1 實驗參數分析

本文提出的ECANCD采用集成框架，其中包括M個基分類器和1個噪聲處理機制，數據緩沖塊的大小是很難從理論上確定。若緩沖數據塊過多，則不可避免地會增加算法的時空開銷，甚至降低該算法的分類精度;相反的，如果緩沖數據塊過小，則噪聲干擾就會難以消除。基于此，本文對數據緩沖塊M的取值大小進行了大量的實驗驗證，結果表明當M=10個緩沖數據塊，每個數據塊包含500個實例，誤分類緩沖區實例個數的閾值為100，μ檢驗方法中α=0.95時，分類效果較優，算法其他相關參數均采用相應文獻中設置的參數值。

3.2 概念漂移檢驗

對于概念漂移的檢測，本次實驗選取含噪率在0%～30%(間隔5%遞增)的KDDCup數據集，在不同噪聲的情況下觀察分析ECANCD分類精度來驗證對概念漂移的檢測效果。圖2描述的是對KDDCup數據集進行學習，對該數據集的10% ～100%(間隔10%遞增)進行測試的結果，其中測試集百分比為實驗數據集占整個數據集的比例。

圖2 ECANCD概念漂移檢測Fig.2 Concept drift detection with ECANCD

從圖2中可以看出，當數據噪聲為零時，分類精度基本保持在91%～97%;并且當含噪率從0%增加到30%的過程中，分類器的分類效率在逐漸降低，且波動很大。分析其原因是:當噪聲的比例增加，噪聲數據在數據集中所占的比例就會增大，則真實數據就會減少，ECANCD的過濾效果就會變弱;但是當集成分類器檢測到概念漂移后就會對分類器作出調整以適應于當前概念的數據流，分類精度就會隨之提高。如圖2所示，隨著數據集的增加，該算法的分類精度可以達到95% ～97%。ECANCD能在含噪數據流中檢測概念漂移，并能不斷更新分類數據模型，提高分類精度。

3.3 抗噪性能檢測

為了驗證本文所提ECANCD的抗噪聲性能，在含噪率為5%、10%、15%、20%、25%、30% 的 Hyper Plane、KDDCup、Kaggle數據集上進行大量的實驗，實驗結果如圖3所示。從圖3綜合分析可以得出以下結論:

1)從圖3(a)中得出，在HyperPlane數據集上隨著數據流中噪聲比例的逐漸增加，每種算法的分類精度都在逐漸減少。

2)從圖3(b)中得出，KDDCup數據集上含噪率相同的情況下，ECANCD比其他三種算法分類精度高。

3)從圖3(c)中得出，Kaggle數據集上在含噪率較低的情況下，各算法分類精度差別不大，ECANCD并不比其他算法有明顯優勢;但隨著噪聲數據的增長，ECANCD的分類精度明顯優于其他算法。

4)從圖3中得出，ECANCD的分類精度隨著噪聲的增加波動并不明顯，但其他算法波動較為明顯。

圖3 不同數據集上分類精度對比Fig.3 Comparison of classification accuracy on different datasets

從圖3中可以看出，ECANCD的分類精度始終保持在90%以上，而其他三種算法的分類精度均有所下降，部分已下降到70%以下。分類精度之所以有所下降，是因為數據流中噪聲數據逐漸增加，真實數據的比例會逐漸降低，分類器如果不能及時適應于當前概念，則分類精度會越來越低。一旦當分類器檢測到概念漂移之后，噪聲過濾機制會過濾掉噪聲，分類模型進行增量式學習并更新模型，因此分類模型一經更新后會迅速適應于當前數據流環境，進而提高了分類精度。

由上述分析可以得出，ECANCD對概念漂移數據流具有較強的抗噪性。

3.4 分類精度分析

ECANCD 和 OzaBag、Ozaboost、Weight-bagging等經典數據流分類算法在 HyperPlane、KDDCup、Kaggle含噪率為10%的數據集上的實驗結果如表1所示。從表1可以得出，ECANCD在分類精度上要比其他三種算法更優:在數據集HyperPlane上，ECANCD的分類精度比OzaBag算法高出5.83個百分點，比 Ozaboost算法高出7.36個百分點，比 Weightbagging算法高 23.25個百分點;在數據集 KDDCup上，ECANCD的分類精度比OzaBag算法高出6.93個百分點，比Ozaboost算法高出6.53個百分點，比Weight-bagging算法高23.6個百分點;在數據集Kaggle上，ECANCD的分類精度比OzaBag算法高出8.92個百分點，比 Ozaboost算法高出7.32個百分點，比Weight-bagging算法高13.23個百分點。

表1 含噪率為10%時，不同算法的分類精度 %Tab.1 Classification accuracy of different algorithms when noise ratio is 10% %

ECANCD 在 HyperPlane、KDDCup、Kaggle三個數據集上都能很好地作出分類，并且明顯要優于其他三種算法;OzaBag、Ozaboost算法在 HyperPlane、KDDCup、Kaggle三個數據集上的分類精度相差不大，Weight-bagging算法分類精度較低，其原因可能是這三個數據集的數據分布不平衡，不利于Weight-bagging算法分類能力的提高。由上述分析可得，ECANCD對含有噪聲和概念漂移的數據流分類效果更好。

3.5 基分類器性能比較

在本文ECANCD的基礎上，將基分類器替換成經典的支持向量機分類器和增量式C4.5決策樹分類器在KDDCup數據集10%的子數據集上進行基分類器基本統計量和時間性能上的比較。本節實驗使用的實驗平臺為MOA，該平臺是基于WEKA的數據流在線分析平臺，可以將KDDCup數據集模擬成數據流，以此達到動態真實數據的效果。實驗結果如表2和圖4所示。

表2 KDDCup數據集上基本統計量比較Tab.2 Comparison of basic statistics on dataset KDDCup

圖4 KDDCup數據集上的時間性能比較Fig.4 Comparison of time performance on dataset KDDCup

從表2中可以看出:在分類正確率上，增量C4.5決策樹分類器比支持向量機分類器高了2.67個百分點，分類器性能有所提高;在Kappa統計量上，增量C4.5分類器比支持向量機分類器高了0.0023，Kappa統計量越大則分類器性能越好，反之越差;在誤差值上，增量C4.5分類器比支持向量機分類器在平均絕對誤差上高0.0184，在均方根誤差上低0.0078，在相對均方根誤差低3.85個百分點，誤差值越低分類模型準確度越高。

從圖4中分析出，當基分類器選擇支持向量機時，分類算法較基分類器為增量C4.5時運行的時間較長，可以看出基分類器選擇增量C4.5時在時間有效性更優越。從時間和空間復雜度上分析，支持向量機并不適合于處理過大的數據。核化后的SVM的時間復雜度為O(mn2)，m為樣本數，n為特征數。當數據量過大時，還要面臨空間復雜度的問題;而增量C4.5通過剪枝減少空間復雜度。圖4中實際實驗運行時間可以有效印證增量C4.5在復雜度上的優勢。

通過上述分析可以得出:增量C4.5決策樹分類器在真實動態數據中的分類時間、分類精度、Kappa統計量、均方根誤差和相對均方根誤差均比支持向量機分類器優越，因此本文所提的ECANCD分類算法確實在數據流挖掘中效果更好、性能更優。

4 結語

針對數據流中噪聲問題和概念漂移問題，本文提出了一種新型的含噪數據流集成分類算法(ECANCD)。為了能夠實現對概念漂移檢測和噪聲過濾，引入噪聲過濾機制和假設檢驗方法，采用增量式學習方式構成集成分類器。通過大量實驗的分析與比較，該算法不僅能夠檢測概念漂移和過濾噪聲，并且具有較高的分類精度。但是真實數據流中的大量數據是無標簽的實例，因此下一步的主要研究方向是利用半監督學習技術在不完全標記的數據流環境中實現概念漂移的檢測與分類。