新型含噪數(shù)據(jù)流集成分類的算法

袁 泉，郭江帆

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

0 引言

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

1 相關工作

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

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

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

2 數(shù)據(jù)流分類算法

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

2.1 增量式C4.5決策樹

2.1.1 增量式學習方式

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

2.1.2 對 C4.5 算法的改進

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

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

2.1.3 增量式C4.5算法流程

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

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

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

2.2 概念漂移檢測方法

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

μ檢驗定義:設母體X分布是任意的，且一、二階距存在，記 EX=u，DX= δ2(δ2未知)，在母體上作假設H0:u=u0(u0是已知數(shù))［18］。用x珋作檢驗，當無限大時，統(tǒng)計量U=(x珋－μ0)/(S/)近似服從標準正態(tài)分布N(0，1)，其中:x珋表示樣本平均數(shù)，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)。設樣本數(shù)為n，被錯誤分類數(shù)為m，則 X=m/n，S2=X(1－X)。

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

2.3 ECANCD 描述

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

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

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

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

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

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

ECANCD偽代碼如下。

輸入 數(shù)據(jù)流DS;

輸出 分類模型Ec。

BEGIN

While(new data streams){

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

if(num＜M)

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

else

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

for(Ei∈S){

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

則把實例Ei放入誤分類區(qū);

}

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

if(concept drifts and num==M{

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

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

if(Cnew＞Cmin)

用Cnew替換Cmin;

}

}END

3 實驗結果與分析

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

3.1 實驗參數(shù)分析

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

3.2 概念漂移檢驗

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

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

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

3.3 抗噪性能檢測

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

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

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

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

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

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

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

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

3.4 分類精度分析

ECANCD 和 OzaBag、Ozaboost、Weight-bagging等經(jīng)典數(shù)據(jù)流分類算法在 HyperPlane、KDDCup、Kaggle含噪率為10%的數(shù)據(jù)集上的實驗結果如表1所示。從表1可以得出，ECANCD在分類精度上要比其他三種算法更優(yōu):在數(shù)據(jù)集HyperPlane上，ECANCD的分類精度比OzaBag算法高出5.83個百分點，比 Ozaboost算法高出7.36個百分點，比 Weightbagging算法高 23.25個百分點;在數(shù)據(jù)集 KDDCup上，ECANCD的分類精度比OzaBag算法高出6.93個百分點，比Ozaboost算法高出6.53個百分點，比Weight-bagging算法高23.6個百分點;在數(shù)據(jù)集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三個數(shù)據(jù)集上都能很好地作出分類，并且明顯要優(yōu)于其他三種算法;OzaBag、Ozaboost算法在 HyperPlane、KDDCup、Kaggle三個數(shù)據(jù)集上的分類精度相差不大，Weight-bagging算法分類精度較低，其原因可能是這三個數(shù)據(jù)集的數(shù)據(jù)分布不平衡，不利于Weight-bagging算法分類能力的提高。由上述分析可得，ECANCD對含有噪聲和概念漂移的數(shù)據(jù)流分類效果更好。

3.5 基分類器性能比較

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

表2 KDDCup數(shù)據(jù)集上基本統(tǒng)計量比較Tab.2 Comparison of basic statistics on dataset KDDCup

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

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

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

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

4 結語

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