基于McDiarmid不等式的決策樹分類算法

賈濤,韓萌,王少峰,邢成

(北方民族大學 計算機科學與工程學院,寧夏 銀川 750021)

0 引言

近年來,隨著信息技術(shù)和大數(shù)據(jù)的不斷發(fā)展,產(chǎn)生了大量的數(shù)據(jù)流。因此數(shù)據(jù)流的收集和分析就變得至關(guān)重要。數(shù)據(jù)流量的爆炸式增長,勢必需要更大的內(nèi)存來存儲這些數(shù)據(jù)流,所以傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)很難滿足社會的需求，而數(shù)據(jù)流的處理技術(shù)將發(fā)揮越來越重要的作用。常見用于處理數(shù)據(jù)流的分類方法包括決策樹[1-2]、神經(jīng)網(wǎng)絡[3-4]、關(guān)聯(lián)/分類規(guī)則、支持向量機等[5-6]。其中決策樹分類算法是最有效的分類方法之一。如今決策樹算法已經(jīng)成功地應用于許多應用領域的分類,如在醫(yī)療診斷、天氣預報、金融分析、顧客分類、身份識別、網(wǎng)絡安全和行為分析等領域逐漸發(fā)揮著越來越重要的作用。與此同時,國內(nèi)外研究工作者也在不斷豐富決策樹算法的理論知識。

決策樹分類算法是一種非常經(jīng)典的、處理效率很高的分類方法。它是一種類似于樹的結(jié)構(gòu),其中每個內(nèi)部節(jié)點表示一個屬性值的決策。每個分支代表決策的結(jié)果,樹的葉節(jié)點代表類。在數(shù)據(jù)挖掘和機器學習中,決策樹是一種預測模型;也就是說,從觀察一個項目到關(guān)于它的目標值的結(jié)論的映射[7]。用于數(shù)據(jù)流挖掘的傳統(tǒng)技術(shù)需要多次掃描數(shù)據(jù)以提取信息,這對于流數(shù)據(jù)是不可行的。與傳統(tǒng)的數(shù)據(jù)集不同,數(shù)據(jù)流具有高速流動、有序變化、實時處理等特征[8]。不同于數(shù)據(jù)倉庫,它是實時產(chǎn)生,且一般不被存儲,所以要求快速地處理,盡量短時間內(nèi)挖掘出其中有用的信息。因此傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)已不再適合數(shù)據(jù)流環(huán)境。從而,數(shù)據(jù)流環(huán)境下的數(shù)據(jù)挖掘研究具有更大的機遇和挑戰(zhàn)性[9]。

本文研究并設計了一種基于McDiarmid不等式的數(shù)據(jù)流決策樹分類算法,該算法可以處理非數(shù)值數(shù)據(jù),并且在處理數(shù)據(jù)流屬性分裂度量方面具有一定優(yōu)勢。為了進一步提高分類性能,設計使用ε/2進行屬性分類度量。McTree算法與經(jīng)典算法相比,在分類準確率升高或者幾乎保持不變的情況下,生成決策樹的節(jié)點數(shù)與層數(shù)明顯降低。

1 研究現(xiàn)狀

為了處理數(shù)據(jù)流問題，Domingos等人最初提出了快速決策樹(VFDT)算法[10],VFDT是一種基于Hoeffding樹的經(jīng)典數(shù)據(jù)流分類算法,首先將決策樹學習應用于數(shù)據(jù)流挖掘[11],解決了構(gòu)建決策樹過程中訓練不足的問題,也在數(shù)據(jù)流環(huán)境中能夠取得不錯的分類效果。這開辟了決策樹算法處理數(shù)據(jù)流問題的先河。

1.1 Hoeffding決策樹的研究現(xiàn)狀

針對VFDT不能很好地處理概念漂移問題并且只能處理離散屬性,Gama等人提出了基于VFDT的VFDTc算法[12],該算法不僅可以處理離散數(shù)據(jù)流,而且還可以處理連續(xù)數(shù)據(jù)流。Hulten等人提出了CVFDT算法[13],CVFDT算法在VFDT算法的基礎上做了一些優(yōu)化,能夠很好地適應概念漂移數(shù)據(jù)流,并且與VFDT相比提高了分類性能[14]。Pfahringer等人提出的霍夫丁選項樹(Hoeffding Option Tree,HOT)是一個常規(guī)的Hoeffding樹,除了內(nèi)部決策節(jié)點和葉子外,還包含額外的選項節(jié)點。并且允許應用多個測試,從而將多個Hoeffding樹作為單獨的路徑。這個結(jié)構(gòu)使得一個例子可以通過多個不同路徑到達多個不同的樹節(jié)點[15]。Bifet等人提出了霍夫丁自適應樹(Hoeffding Adaptive Tree,HAT),該方法作為一種從Hoeffding Window Tree演化而來的新方法,自適應地學習隨時間變化而不需要固定大小的滑動窗口?；瑒哟翱诘淖顑?yōu)大小是用戶很難猜測的參數(shù),因為它取決于數(shù)據(jù)流分布的變化率。為了避免參數(shù)大小的選擇,文獻[16]提出了一種管理節(jié)點統(tǒng)計信息的新方法。其基本思想很簡單:在每個節(jié)點上放置頻率統(tǒng)計估計器的實例,即用估計器的Aijk實例替換Hoeffding Window Tree中的每個nijk計數(shù)器。Yang等人提出了一種增量優(yōu)化快速決策樹(iOVFDT)算法[17-18],用于處理噪聲數(shù)據(jù)流。雖然在處理大數(shù)據(jù)流時,該算法很難全面地實現(xiàn)預處理和抽樣，但該算法在較高的精度和較小的模型尺寸方面具有很大優(yōu)勢。Cazzolato等人描述了一種基于VFDT系統(tǒng)的增量決策樹算法StARMiner Tree(ST)[19],該算法處理數(shù)值型數(shù)據(jù)流,采用基于統(tǒng)計的方法作為啟發(fā)式算法來決定何時分割節(jié)點,以及選擇測試節(jié)點中使用的最佳屬性。韓萌等人提出了一種處理可變數(shù)據(jù)流的頻繁模式?jīng)Q策樹算法(PatHT),與其他同類算法相比,該方法對穩(wěn)態(tài)數(shù)據(jù)流處理時可以明顯提高正確率或可以明顯縮短訓練時間,在處理不同概念漂移特性的可變數(shù)據(jù)流時也具有很好的分類效果[20]。Jankowski等人提出了一種利用概念漂移對數(shù)據(jù)流進行分類的數(shù)據(jù)流挖掘算法,稱為基于決策樹的進化算法(EVO-Tree)。它不需要任何的知識環(huán)境,比如數(shù)據(jù)流的數(shù)量和速度。這種方法的新穎之處在于將樹學習機制和進化算法結(jié)合在一起。在這種算法中,決策樹是增量的,所有信息都存儲在樹的內(nèi)部結(jié)構(gòu)中。該算法在減少樹大小的同時也減小了分類誤差[21]。針對當前數(shù)據(jù)流挖掘應用中的隱私泄露問題,陳煜等人提出了一種基于決策樹隱私保護的數(shù)據(jù)流分類算法PPFDT。該算法通過采用添加隨機噪聲的方法對數(shù)據(jù)加以隱私保護,并使用閥值算法找到擾動數(shù)據(jù)流的最佳分裂屬性和最佳分裂點,從而直接在擾動數(shù)據(jù)流上構(gòu)造決策樹[22]。Song等人提出了MHFlexDT算法,該算法可以在降低模糊決策樹層數(shù)的同時獲得更高的分類精度,使屬性操作值的范圍更加靈活,提高了分類響應性。MHFlexDT 可以在決策樹的不同層次上添加新特征,這可以使模糊決策樹的構(gòu)造更加靈活,并且該方法與二進制HFlexDT算法相比減少了數(shù)據(jù)計算成本[23]。Gomes等人提出了自適應隨機森林(ARF)算法,用于分類演化數(shù)據(jù)流。與先前為數(shù)據(jù)流學習復制隨機森林的嘗試相比,ARF包括一種有效的重采樣方法和自適應算子,可以處理不同類型的概念漂移而無需對不同數(shù)據(jù)集進行復雜優(yōu)化[24]。Chaitanya等人提出的極速決策樹(Extremely Fast Decision Tree,EFDT)算法等同于Hoeffding樹,只是它使用Hoeffding邊界來確定最佳屬性上拆分的增益是否超過未拆分的增益或當前拆分屬性的增益。實際上,如果一個節(jié)點上不存在拆分屬性,而不是僅當?shù)谝缓蜻x拆分屬性的性能優(yōu)于第二好的候選者時才進行拆分。那么,當來自第一候選拆分的信息增益非零且具有所需的置信度時,EFDT將進行拆分。與HoeffdingTree相比,其運行時間變長,但準確率升高并且內(nèi)存需求明顯降低[25]。

在VFDT算法上優(yōu)化的數(shù)據(jù)流決策樹分類算法都是基于Hoeffding不等式設計的,這些算法中使用的主要數(shù)學工具是Hoeffding不等式[26],其中ε的計算形式如公式(2)所示。

定理1[27]如果X1,X2,…,Xn是獨立的隨機變量并且ai≤Xi≤bi(i=1,2,…,n),然后對于ε>0有如下不等式(1):

(1)

對于ai=a和bi=b,(i=1,2,…,n),它表明在n次觀察之后,范圍R=b-a的隨機變量的真實均值與估計均值的差異不超過

(2)

其中,R=log2C,C是類的數(shù)目,δ是分裂置信度,n是實例數(shù)。

(3)

(4)

公式(4)等價于

(5)

現(xiàn)在回顧一下Hoeffding不等式:

(6)

和

(7)

顯然,Hoeffding不等式只適用于實值數(shù)據(jù)流。

如果每個Yi來自相同的分布,則E[Y]=E[Y1]=…=E[YN],因此E[S]=N·E[Y].將Hoeffding不等式(6)應用于公式(5)得到

(8)

簡化分母并將公式(8)的右邊等于δ得到

(9)

關(guān)于ε求解公式(9),得到公式(2)。即完成了Hoeffding不等式的證明。

1.2 McDiarmid決策樹的研究現(xiàn)狀

基于Hoeffding不等式設計的決策樹方法是常見的分類決策樹方法之一。在Hoeffding不等式中,當n傾向于無窮大時,ε傾向于0。但是,通過分析可以看出Hoeffding不等式有一些缺陷:首先,只有數(shù)值數(shù)據(jù)流適用于Hoeffding不等式。在一般情況下,數(shù)據(jù)流不必全是數(shù)值數(shù)據(jù)。其次,在屬性分裂度量方面,如信息增益和基尼指數(shù),不能表示為元素Yi的和S[28]。因此,這個問題的解決方案似乎是應用McDiarmid不等式而不是Hoeffding不等式。

那么,針對Hoeffding不等式存在的不足,基于McDiarmid不等式的數(shù)據(jù)流決策樹算法也就隨之誕生了。下面將介紹基于McDiarmid不等式的數(shù)據(jù)流決策樹分類算法。Rutkowski等人2014年提出用于數(shù)據(jù)流的CART算法是基于泰勒定理和正態(tài)分布設計的[29]。同年Rutkowski等人提出了基于McDiarmid不等式的決策樹算法對ID3算法中使用的信息增益和CART算法中使用的Gini索引的約束。實驗結(jié)果保證了應用于數(shù)據(jù)流并基于McDiarmid不等式的決策樹學習系統(tǒng)的輸出幾乎與傳統(tǒng)學習系統(tǒng)相同[30]。Maciej等人提出了一種混合分裂準則,其結(jié)合了針對兩種不同分裂測量函數(shù)建立的兩個標準:基尼誤差增益和基于誤分類誤差的分裂測量?；旌戏至褬藴式沂玖似鋬蓚€組成部分的優(yōu)點。數(shù)值實驗表明,混合準則的在線決策樹的分類精度優(yōu)于單一分裂準則的在線決策樹的分類精度[31]。Bartosz等人提出了一種有效且快速,自適應成本敏感的決策樹學習方案,該解決方案能夠從二進制和多類不平衡數(shù)據(jù)流中學習,用于處理在線不平衡類。在樹的每個葉子中,訓練具有輸出適應性的感知器以補償偏斜的類分布,而McDiarmid不等式用于控制分裂屬性選擇[32]。

1.3 屬性選擇度量

屬性選擇度量是一種選擇分裂準則,把給定類標記的訓練元組的數(shù)據(jù)流分區(qū)D“最好地”劃分成單獨類的啟發(fā)式方法。屬性選擇度量又稱為分裂規(guī)則,因為它們決定給定結(jié)點上的元組如何分裂。本小節(jié)將介紹三種常用的屬性選擇度量——信息增益(Information Gain)、增益率(Gain Rate)和基尼指數(shù)(Gini index)[33],目前用于處理數(shù)據(jù)流問題的常用度量標準是信息增益和基尼指數(shù)。

符號定義:設數(shù)據(jù)分區(qū)D為標記類元組的訓練集。假定類標號屬性具有m個不同值,定義了m個不同的類Ci(i=1,2,3,…,m)。設Ci,d是D中Ci類元組的集合,|D|和|Ci,D|分別是D和Ci,D中元組的個數(shù)。

① 信息增益根據(jù)信息增益最大的屬性作為分裂節(jié)點。其計算公式如下:

(10)

其中,pi是D中任意元組屬于類Ci的非零概率,并用|Ci,D|/|D|估計。使用以2為底的對數(shù)函數(shù)是因為信息用二進制編碼。Info(D)是識別D中元組的類標號所需要的平均信息量。Info(D)又稱為信息熵。

(11)

信息增益定義為原來的信息需求(僅基于類比例)與新的信息需求(對A劃分后)之間的差。即

Gain(A)=Info(D)-InfoA(D) .

(12)

② 增益率根據(jù)信息增益率最大的屬性作為分裂節(jié)點。C4.5[33]使用一種稱為增益率(gain ratio)的信息增益擴充,它用“分裂信息(split information)”值將信息增益規(guī)范化。分裂信息類似于Info(D),定義如下:

(13)

該值代表由訓練集D劃分成對應于屬性A測試的v個輸出的v個分區(qū)產(chǎn)生的信息。信息增益率定義為:

(14)

③ 基尼指數(shù)根據(jù)基尼指數(shù)最小的屬性作為分裂節(jié)點?；嶂笖?shù)度量數(shù)據(jù)分區(qū)或訓練元組集D的不純度,定義為:

(15)

其中,pi是D中元組屬于Ci類的概率,并用|Ci,D|/|D|估計。對m個類求和。

基尼指數(shù)考慮每個屬性的二元劃分。當考慮二元劃分裂時,計算每個結(jié)果分區(qū)的不純度加權(quán)和。若A的二元劃分將D劃分成D1和D2,則給定該劃分,D的基尼指數(shù)為:

(16)

屬性A的二元劃分導致的不純度降低為:

ΔGini(A)=Gini(D)-GiniA(D) .

(17)

2 基于McDiarmid不等式的分類算法研究

已有的數(shù)據(jù)流決策樹分類方法中,基于Hoeffding不等式設計的決策樹方法是常見的方法之一。在公式(2)中,當n趨向于無窮大時,ε趨向于0。但是,通過1.1節(jié)的證明分析可以容易地看出Hoeffding不等式存在一些不足:首先,Hoeffding不等式只適合數(shù)值屬性的處理。其次,在屬性分裂度量方面,如信息增益和基尼指數(shù),不能使用S表示元素Yi的和[28]。因此,這個問題使用McDiarmid不等式處理似乎比Hoeffding不等式更加合理和可行。因此,本文研究并設計出一種基于McDiarmid不等式的數(shù)據(jù)流決策樹分類算法(McTree)。

2.1 McDiarmid不等式的證明

由于在第1節(jié)中提到Hoeffding不等式處理數(shù)據(jù)流存在很多不足。因此,本文利用Hoeffding不等式的推廣McDiarmid不等式[34]作為決策樹分割準則統(tǒng)計工具的思想在[27]中被提出。下面給出了McDiarmid定理如下:

定理2[31](McDiarmid不等式)設X1,…,Xn是一組獨立的隨機變量,讓f(x1,…,xn)成為滿足以下不等式(18)的函數(shù):

(18)

然后對于任何ε>0,以下不等式(19)為真

(19)

Hoeffding不等式(6)是McDiarmid不等式(19)的一個特例,當Xi∈Ai=[ai,bi]時,對于i=1,…,N,是實值隨機變量。

由于f(X1,…,XN)是隨機變量的函數(shù),因此它也是隨機變量。E[f(X1,…,XN)]是其預期值。為了獲得與公式(2)中相同形式的ε,應滿足以下條件如公式(20)

(20)

對于某個常數(shù)C,則有公式(21)

(21)

如果C=R,我們可以得到公式(2)給出的ε?；喒?21),得到公式(22):

(22)

通過多次實驗表明,使用信息增益進行分裂度量得到的實驗結(jié)果明顯比基尼指數(shù)的好,因此本文也將采用信息增益作為分裂度量。下面定理3保證了一個應用于數(shù)據(jù)流的決策樹學習方法,它的輸出幾乎與傳統(tǒng)學習的輸出相同。

定理3[27](McDiarmid定理)令Z={X1,…,Xn}為獨立隨機變量的集合,其中每個隨機變量取值于集合A×B×…×Λ。對于任何固定的δ與任何一對屬性a和b,有f(Z)=Gaina(Z)-Gainb(Z)>0,若

(23)

則有

Pr(f(Z)-E[f(Z)]>ε)≤δ，

(24)

其中,

CGain(K,n)=6(Klog2en+log22n)+2log2K.

(25)

由于文獻[10]中考慮一個實值隨機變量r,其范圍是R(例如概率范圍為1,而對于信息增益范圍是logK,其中K是類的數(shù)目),則有關(guān)系式K=2R代入(25)中有如下公式(26):

C=6(2Rlog2en+log22n)+2R.

(26)

通過對文[10]的學習過程中看到使用ε2<τ作為屬性分裂判斷,從而得到靈感,將(22)進行變形,得到一種新的用于分裂判斷的度量標準(27):

(27)

將公式(26)代入,則有(28):

(28)

2.2 基于McDiarmid不等式的決策樹

針對Hoeffding不等式在屬性分裂度量方面存在的不足,本文使用Hoeffding不等式的擴展,提出了一種基于McDiarmid不等式的數(shù)據(jù)流決策樹分類算法(McTree)來解決Hoeffding不等式存在的不足,并使用McTree 算法提高處理性能。

在McTree算法中,首先當新的示例到達之后便放入到葉節(jié)點l中,從而更新統(tǒng)計信息nl,當滿足nmin可以整除nl并且葉節(jié)點都不是同一類才計算每個屬性的信息增益差進行分裂,如圖1中算法步驟①-⑥所示。在進行分裂的過程中,影響分裂的主要因素是nmin,ε和τ。其中,nmin直接影響屬性的信息增益,即影響的是最大信息增益與次大信息增益的差值。τ是當⑨ 中的Gl(Xa)-Gl(Xb)>ε/2不滿足時候才會執(zhí)行后半部分ε/2 <τ,所以決定是否分裂的直接因素是ε和τ。而τ是直接取值即可(本文中τ取值為默認值0.05),但是ε是由步驟⑧ 計算而來的。因此,本算法首先對ε的計算公式進行優(yōu)化,使得該算法的分類性能更好。但是在實驗中,使用ε進行分裂判斷得到的分類精度并不盡人意,因此本算法采用ε/2作為分裂判斷,將得到更高的分類精度。該算法的具體實現(xiàn)偽代碼如圖1所示。

輸入:數(shù)據(jù)流實例S, 屬性集X, 分裂評價函數(shù)G(X), 分裂置信度δ, 主動分裂閾值τ, 最小分裂實例數(shù)nmin;輸出:決策樹McTree。算法步驟:① McTree是一棵具有單一葉子(根)的樹② 對于所有訓練示例,使用McTree將例子放入到葉節(jié)點l中③ 更新葉子l的統(tǒng)計信息④ 在l中觀察到的實例統(tǒng)計數(shù)量,遞增nl⑤ nmin可以整除nl并且在l處得到的例子不全是同一類⑥ 對每個屬性計算Gl(Xi)⑦ 設Xa是最大信息增益的屬性,Xb是次大信息增益的屬性⑧ 計算McDiarmid不等式ε=[6(2Rlog2en+log22n)+2R]ln(1/δ)2n()2⑨ 如果Gl(Xa)-Gl(Xb)> ε/2 或者 ε/2 < τ⑩ 在l下面添加一個在Xa拆分的節(jié)點,屬性Xa為該節(jié)點的決策屬性 將產(chǎn)生一個新的分支,產(chǎn)生新的葉子節(jié)點 實例統(tǒng)計數(shù)量nl=0

Fig.1 pseudo-code of McTree algorithm

圖1 McTree算法偽代碼

本節(jié)主要針對Hoeffding不等式存在的不足,提出并設計了一種基于McDiarmid不等式的數(shù)據(jù)流決策樹分類算法(McTree)。在進行分類的時候,得到的結(jié)果并不是很理想。然而為了得到更好的分類精度,本算法設計使用ε/2進行屬性分類度量,最終使得實驗分類效果更好。實驗的對比結(jié)果將在第3節(jié)重點描述和分析。

3 實驗設計與分析

為了驗證McTree算法的可行性和分類性能,本節(jié)進行了相應的7組實驗。實驗運行環(huán)境的CPU為2.2 GHz,內(nèi)存為16 GB,操作系統(tǒng)是Win10專業(yè)版,所有的實驗采用Java語言實現(xiàn)。實驗中采用兩類數(shù)據(jù)。一是來自于UCI[35]數(shù)據(jù)集的真實數(shù)據(jù)流,二是通過在MOA(大規(guī)模在線分析平臺)生成的數(shù)據(jù)流。本文使用VFDT[14]、HOT[15]、ARFHoeffdingTree[24]、EFDT[25]和McTree算法分別在8個數(shù)據(jù)流上運行,實驗結(jié)果將在3.2節(jié)重點描述與分析。

3.1 真實與虛擬數(shù)據(jù)流

本文使用各種各樣的數(shù)據(jù)流進行評估,其中有真實數(shù)據(jù)流和生成數(shù)據(jù)流,大部分是MOA數(shù)據(jù)流生成的數(shù)據(jù)流,以彌補缺乏大型公開可用的真實數(shù)據(jù)流。

本實驗共用到8個數(shù)據(jù)流:其中kddcup99是真實數(shù)據(jù)流,來自于UCI數(shù)據(jù)集。kddcup99數(shù)據(jù)流共1 000 000條數(shù)據(jù),就是KDD競賽在1999年舉行時采用的數(shù)據(jù)流。其余7個數(shù)據(jù)流分別是RTS、RTC、LED、Wave、RRBFS、RRBFC和Hyperplane,均是1 000 000條數(shù)據(jù)。它們是通過數(shù)據(jù)流在線分析平臺MOA生成的合成數(shù)據(jù)流。RTS和RTC是簡單和復雜的隨機樹概念,基于文獻[10]中描述的生成方法,添加10%的噪聲。RTS的最大層數(shù)為5,葉節(jié)點從3級開始,之后出現(xiàn)葉節(jié)點的概率為0.15;最后一棵樹有741個節(jié)點,其中509個是葉子。RTC的最大層數(shù)為10,葉節(jié)點從5級開始;最后一棵樹有127 837個節(jié)點,其中90 259個是葉子。每個名稱屬性有5個可能的值。Hyperplane數(shù)據(jù)流由10個數(shù)值屬性組成,兩個類別,共1 000 000條數(shù)據(jù)流。LED數(shù)據(jù)流包含25個屬性,其中17個屬性為無關(guān)屬性,在該數(shù)據(jù)流中前7個屬性為漂移屬性維,共包含1 000 000個事例及10個不同的類標簽[36]。Wave數(shù)據(jù)流包含22個屬性,前21個屬性在實數(shù)范圍內(nèi)取值,共含有3個不同的類標簽及1 000 000條事例,該數(shù)據(jù)流含有5%的噪聲。RRBFS是一個簡單的隨機RBF(徑向基函數(shù))數(shù)據(jù)流,由100個中心、10個屬性和2個類組成。RRBFC是一個包含1 000個中心,50個屬性和2個類的復雜版本[15]。表1列出了實驗中各個數(shù)據(jù)流的屬性類型、屬性數(shù)量和類數(shù)目。

表1 數(shù)據(jù)流屬性

3.2 實驗結(jié)果

在下列實驗中,VFDT[14]、HOT[15]、ARFHoeffdingTree[24]、EFDT[25]和McTree均在MOA上運行。同時分別在7組參數(shù)下運行得出實驗結(jié)果。本實驗參數(shù)設置分別為:①nmin=100,δ=1.0E-4;②nmin=200,δ=1.0E-4;③nmin=300,δ=1.0E-4;④nmin=400,δ=1.0E-4;⑤nmin=500,δ=1.0E-4;⑥nmin=1 000,δ=0.1.0E-4;⑦nmin=200,δ=1.0E-7。其中,nmin代表葉節(jié)點最小分裂數(shù),δ代表分裂置信度。決策樹算法主要從生成樹規(guī)模(tree (nodes)、tree (leaves)、tree (depth))、運行時間(Time)、分類準確率(accuracy(%))等幾個方面對算法性能進行評價。

在實驗過程中,不同參數(shù)下的實驗結(jié)果大同小異,因此本實驗對結(jié)果進行抽取記錄。即在LED數(shù)據(jù)運行得到的結(jié)果來自參數(shù)①,在Wave、RRBFC數(shù)據(jù)運行得到的結(jié)果來自參數(shù)②,在kddcup99數(shù)據(jù)運行得到的結(jié)果來自參數(shù)④,在RTS數(shù)據(jù)運行得到的結(jié)果來自參數(shù)⑤,在RRBFS數(shù)據(jù)運行得到的結(jié)果來自參數(shù)⑥,在Hyperplane、RTC數(shù)據(jù)運行得到的結(jié)果來自參數(shù)⑦。因此,VFDT、HOT、ARFHoeffdingTree、EFDT和McTree使用上述數(shù)據(jù)流在MOA上運行得到的分類結(jié)果如表2和表3所示。

(1)生成樹規(guī)模對比實驗

McTree和VFDT算法[14]分別在8個不同數(shù)據(jù)流上進行實驗對比。首先,RTC、RRBFC和Hyperplane數(shù)據(jù)流生成的樹規(guī)模減小最明顯,生成樹節(jié)點和葉節(jié)點均基本變?yōu)樵瓉淼?0%左右;RRBFC數(shù)據(jù)流生成的樹層數(shù)變?yōu)樵瓉淼?0.2%、Hyperplane數(shù)據(jù)流生成的樹減少4層、RTC數(shù)據(jù)流生成樹減少1層。其次,Wave和RRBFS數(shù)據(jù)流生成的樹規(guī)模減小也特別明顯,生成樹節(jié)點和葉節(jié)點變?yōu)樵瓉淼?0%左右;生成樹層數(shù)分別減少7層和12層。LED、RTS和kddcup99數(shù)據(jù)流生成的樹節(jié)點和葉節(jié)點數(shù)目相比原算法基本減少50%,RTS和kddcup99數(shù)據(jù)流生成樹分別減少2層。

McTree和HOT[15]算法分別在7個不同數(shù)據(jù)流上進行實驗對比。除了LED數(shù)據(jù)流生成樹規(guī)模為原算法的28%。在其它數(shù)據(jù)流上,生成樹節(jié)點均為原算法的10%左右,同時生成樹層數(shù)也明顯減少。其中,RRBFC數(shù)據(jù)流生成樹層數(shù)減少35層,RRBFS和Wave數(shù)據(jù)流生成樹層數(shù)也分別減少了58%和56%。

McTree和ARFHoeffdingTree[24]算法(后面出現(xiàn)使用ARF)分別在8個數(shù)據(jù)流上進行實驗。通過觀察,除了kddcup99數(shù)據(jù)流生成樹減小為原算法的一半,RTS和RRBFS數(shù)據(jù)流生成樹為原算法的20%。在其它數(shù)據(jù)流的生成樹節(jié)點數(shù)均為原算法的10%以下。

McTree和EFDT[25]算法分別在8個數(shù)據(jù)流上進行實驗。首先,Hyperplane、Wave和RRBFC數(shù)據(jù)流生成樹節(jié)點減小最明顯,基本變?yōu)樵惴涔?jié)點數(shù)目的20%左右,Hyperplane和RRBFC數(shù)據(jù)流生成樹層數(shù)均減少4層。在kddcup99數(shù)據(jù)流生成樹規(guī)模減小不是很明顯,但是也減少為原算法的68%?？傮w而言,McTree算法生成樹規(guī)模還是比原算法減小一半以上。VFDTHOT、ARFHoeffdingTree、EFDT和McTree算法生成樹規(guī)模比較如表2所示(其中生成樹規(guī)模最小的數(shù)據(jù)已加粗標注)。

(2)算法分類性能對比實驗

首先,ARF[24]與其他4個算法相比,雖然在運行時間上用時最少,但是生成樹規(guī)模與其它算法相比大很多,而且分類精度均低于其它算法。因此,McTree算法與ARF相比,除了運行時間長,在精度和生成樹規(guī)模方面均好于ARF算法。

McTree和VFDT[14]算法分別在8個不同數(shù)據(jù)流上進行實驗。首先從運行時間上去分析,除了RRBFC和kddcup99數(shù)據(jù)流的運行時間比VFDT算法的時間略微變長,其余6個數(shù)據(jù)流的運行時間均是減少或者不變的,并且RTC數(shù)據(jù)流的運行時間減少最為明顯,相比減少了6 s。通過觀察各個數(shù)據(jù)流在VFDT和McTree算法上的分類精度,除了RTS數(shù)據(jù)流分類精度降低1.25%,RRBFS和RRBFC的精度降低2%左右,在其它數(shù)據(jù)流上準確率均升高。

表2 VFDT, HOT, ARF, EFDT與McTree生成樹規(guī)模比較

McTree和HOT[15]算法分別在7個不同數(shù)據(jù)流上進行實驗。McTree算法在所有數(shù)據(jù)流的運行時間均降低,平均運行時間降低50%左右。通過觀察各個數(shù)據(jù)流在HOT和McTree算法上的分類精度,除了在RTS、RRBFS和RRBFC 3個數(shù)據(jù)流的分類精度降低2%左右,在其它四個數(shù)據(jù)流上的分類精度均升高。

McTree和EFDT[25]算法分別在8個數(shù)據(jù)流上進行實驗。McTree算法在所有數(shù)據(jù)流的運行時間均降低,其中最明顯的是在RRBFC數(shù)據(jù)流上從79 s降低到43.91 s,減少了35.09 s的運行時間。然而在分類精度方面,除了在RTS數(shù)據(jù)流分類精度降低1.43%,在RRBFS數(shù)據(jù)流降低0.89%之外,在其它6個數(shù)據(jù)流上均精度升高,其中在RRBFC數(shù)據(jù)流上精度提升2.59%。VFDT、HOT、ARFHoeffdingTree、EFDT和McTree算法性能比較如表3所示(其中運行時間最短、分類精度最高的數(shù)據(jù)已加粗標注)。

表3 VFDT, HOT, ARF, EFDT和McTree算法的性能比較

以上兩組實驗是在七組不同參數(shù)下得出,在McTree和經(jīng)典算法性能對比實驗中,除了RRBFS和RRBFC兩個數(shù)據(jù)流在實驗中分類精度有所下降(2%左右),其它數(shù)據(jù)流的分類精度均提升。其次觀察生成樹規(guī)模,無論是節(jié)點數(shù)目和生成樹層數(shù)、運行時間都降低特別明顯,因此在一定程度上減小算法的時間復雜度和內(nèi)存。通過對比VFDT、HOT、ARFHoeffdingTree、EFDT和McTree算法,得出在分類精度基本不變的情況下,生成樹節(jié)點數(shù)平均降低70%左右,樹層數(shù)平均降低50%左右。

4 結(jié)束語

數(shù)據(jù)流處理問題在近十幾年來得到了一定的發(fā)展。本文針對Hoeffding不等式存在的缺陷,在前人研究的基礎上提出了一種基于McDiarmid不等式的數(shù)據(jù)流決策樹分類算法。該算法中使用了McDiarmid不等式來作為決策樹分割準則的統(tǒng)計工具；設計使用ε/2進行屬性分類度量。對比VFDT、HOT、ARFHoeffdingTree、EFDT和McTree算法的實驗結(jié)果,明顯看出在使得生成的決策樹大小明顯降低的情況下,分類準確率提高或者幾乎保持不變,本文的不足之處是在生成決策樹大小明顯降低的情況下,其中有個別數(shù)據(jù)流的準確率略有下降。這是下一步工作中需要解決的問題。預期目標是在生成模型樹的尺寸明顯降低的情況下,使得算法準確率普遍提高。