韓成成,增思濤,林 強,曹永春,滿正行

(1.西北民族大學(xué) 數(shù)學(xué)與計算機科學(xué)學(xué)院,甘肅 蘭州 730124；2.西北民族大學(xué) 動態(tài)流數(shù)據(jù)計算與應(yīng)用實驗室，甘肅 蘭州 730124；3.西北民族大學(xué) 中國民族信息技術(shù)研究院,甘肅 蘭州 730030)

0 引言

隨著信息通信技術(shù)(Information and Communication Technology,ICT)的日益成熟，物聯(lián)網(wǎng)和無線通信已經(jīng)廣泛應(yīng)用于工農(nóng)業(yè)生產(chǎn)、生態(tài)環(huán)境保護、公共安全監(jiān)測和人體健康跟蹤等領(lǐng)域，用以實時記錄并傳輸狀態(tài)數(shù)據(jù).

不同于可長期存放在大容量存儲設(shè)備中的靜態(tài)數(shù)據(jù)，承載實時狀態(tài)及其變化的數(shù)據(jù)具有數(shù)量無限、有序到達和富含變化的特征，形象地稱作流數(shù)據(jù)(Streaming data)或數(shù)據(jù)流(Data stream).正是因為流數(shù)據(jù)無限且實時到達，所以需要給予實時響應(yīng).

從數(shù)據(jù)挖掘的角度講，流數(shù)據(jù)的處理包括分類、聚類、關(guān)聯(lián)規(guī)則提取、序列模式發(fā)現(xiàn)和異常檢測.其中，流數(shù)據(jù)分類用于將當前數(shù)據(jù)流(段)劃分到某個事先確定的類別當中，是流數(shù)據(jù)挖掘的重要研究分支，已經(jīng)引起了學(xué)術(shù)界的普遍關(guān)注.

基于傳統(tǒng)靜態(tài)數(shù)據(jù)挖掘技術(shù)開發(fā)流數(shù)據(jù)分類模型、算法和方法是學(xué)術(shù)界普遍采用的做法，其中決策樹在流數(shù)據(jù)分類研究中扮演著重要角色.目前，學(xué)術(shù)界已經(jīng)提出了一批基于傳統(tǒng)決策樹的流數(shù)據(jù)分類算法，用于不同應(yīng)用領(lǐng)域的流數(shù)據(jù)實時分類.

為全面概述基于決策樹的流數(shù)據(jù)分類算法，本文首先簡要介紹數(shù)據(jù)挖掘及主要任務(wù)、流數(shù)據(jù)及其特征；然后，依照算法是否考慮概念漂移將現(xiàn)有工作劃分為兩大類，針對每一個算法，給出其主要工作流程、優(yōu)缺點和典型應(yīng)用；最后，基于現(xiàn)有研究，指出基于決策樹的流數(shù)據(jù)分類算法存在的研究挑戰(zhàn)和未來的研究方向.

1 數(shù)據(jù)挖掘及流數(shù)據(jù)概述

1.1 數(shù)據(jù)挖掘及其主要任務(wù)

數(shù)據(jù)挖掘(Data Mining)是人工智能和數(shù)據(jù)庫領(lǐng)域的熱點研究問題，在數(shù)據(jù)庫中的知識發(fā)現(xiàn)(Knowledge Discovery in Database,KDD)中扮演著重要角色.數(shù)據(jù)挖掘就是要從隨機產(chǎn)生的、富含噪聲的大量不完整數(shù)據(jù)中獲取事先未知但潛在有用的信息和知識，以提取出數(shù)據(jù)的模型及數(shù)據(jù)之間的關(guān)聯(lián)，進而實現(xiàn)數(shù)據(jù)變化趨勢和規(guī)律的預(yù)測.

數(shù)據(jù)挖掘主要包括數(shù)據(jù)準備、規(guī)律尋找和規(guī)律表示三個步驟.其中，數(shù)據(jù)準備從相關(guān)的數(shù)據(jù)源(如商品交易記錄、環(huán)境監(jiān)測數(shù)據(jù)、經(jīng)濟運行數(shù)據(jù)等)中選取所需的數(shù)據(jù)，并經(jīng)清洗、轉(zhuǎn)換、整合等處理生成用于數(shù)據(jù)挖掘的數(shù)據(jù)集；規(guī)律尋找應(yīng)用某種方法(如機器學(xué)習(xí)和統(tǒng)計方法)發(fā)現(xiàn)數(shù)據(jù)集中隱含的規(guī)律；規(guī)律表示以用戶盡可能理解的方式(如可視化)將從數(shù)據(jù)中發(fā)現(xiàn)的規(guī)律表示出來.

數(shù)據(jù)挖掘的任務(wù)主要包括分類、聚類、關(guān)聯(lián)規(guī)則挖掘、序列模式挖掘和異常點檢測.其中，分類(Classification)是指通過在給定的一組已標記數(shù)據(jù)集上訓(xùn)練模型，預(yù)測未標記的新數(shù)據(jù)所屬類別的過程.分類問題可形式化表示為：給定由n個數(shù)據(jù)構(gòu)成的集合I= {x1,x2,…,xn}以及這些數(shù)據(jù)的m個類別集合C= {y1,y2,…,ym}，其中m≤n，求解映射y=f(x)，使得任意xi∈I，且僅有一個yi∈C對于yi=f(xi)成立，稱f為分類器.在機器學(xué)習(xí)(Machine Learning)領(lǐng)域，分類問題屬于監(jiān)督學(xué)習(xí)(Supervised Learning)的范疇.

不同于分類問題，聚類(Clustering)[1]能夠在不給定數(shù)據(jù)標簽(Lable)的情況下，實現(xiàn)數(shù)據(jù)的類別劃分.由于聚類操作不需要對輸入數(shù)據(jù)做預(yù)先標記處理，完全根據(jù)數(shù)據(jù)自身的屬性實現(xiàn)類別的劃分，因此屬于無監(jiān)督學(xué)習(xí)(Unsupervised Learning)的范疇.關(guān)聯(lián)規(guī)則挖掘(Association Rule Mining)[2]用于發(fā)現(xiàn)事物(如商品的購買)之間的某種關(guān)聯(lián)關(guān)系.序列模式挖掘(Sequential Pattern Mining)[3]是從序列數(shù)據(jù)庫中發(fā)現(xiàn)高頻子序列的過程.異常點檢測(Outlier Detection)[4]用于自動發(fā)現(xiàn)數(shù)據(jù)集中不同其他數(shù)據(jù)的“異?！睌?shù)據(jù).

1.2 流數(shù)據(jù)及其特性

流數(shù)據(jù)(Streaming Data)，也稱數(shù)據(jù)流(Data Stream)，是不同于靜態(tài)數(shù)據(jù)的新的數(shù)據(jù)形態(tài)，它隨著時間的推移而不斷產(chǎn)生.令t表示時間戳，可將流數(shù)據(jù)形式地表示為：{…,at-1,at,at+1,…}，其中at為t時刻產(chǎn)生的數(shù)據(jù)[5].概括而言，流數(shù)據(jù)具有如下主要特性[6]：

1)實時性：流數(shù)據(jù)實時產(chǎn)生和到達.例如，在實時監(jiān)測系統(tǒng)中，隨著時間的推移不斷有新的數(shù)據(jù)產(chǎn)生.

2)時序性：數(shù)據(jù)的到達順序由其產(chǎn)生的時間先后順序所確定，不受應(yīng)用系統(tǒng)的控制.例如，在股票交易系統(tǒng)中，前后兩位消費者購買股票A和B的順序是時間上確定的.

3)多變性：數(shù)據(jù)的分布是動態(tài)變化的，例如，股票的價格會隨著市場的動態(tài)變化而隨之改變.

4)潛在無限：流數(shù)據(jù)是現(xiàn)實世界的真實記錄，因而具有無限性，例如，用于環(huán)境監(jiān)測的傳感器網(wǎng)絡(luò)，監(jiān)測過程的持續(xù)進行使得記錄的流數(shù)據(jù)不斷增加.

5)單趟處理：流數(shù)據(jù)一經(jīng)處理，不易甚至不能被再次取出，因為流數(shù)據(jù)的存儲代價昂貴，通常一經(jīng)處理就被丟棄.

除了上述特性外，流數(shù)據(jù)還時常伴有概念漂移.概念漂移(Concept Drift)是指流數(shù)據(jù)隨時間推移而發(fā)生改變的現(xiàn)象，它的存在嚴重影響著算法的分類性能.如圖1所示，若c1和c2代表兩種不同的概念(對應(yīng)于分類問題的類別)，常見的概念漂移主要有如下幾種類型[7]：

1)突變型(Sudden)：概念漂移立即發(fā)生且不可逆轉(zhuǎn)，如圖1(a)中的c1立刻且永久地改變?yōu)閏2.

2)增量型(Incremental)：概念漂移平穩(wěn)緩慢且不可逆地產(chǎn)生，如圖1(b)中的c1逐漸且持久地改變?yōu)閏2.

3)漸變型(Gradual)：概念漂移緩慢且不可逆地產(chǎn)生，但中間可能存在往復(fù)，如圖1(c)中從c1改變?yōu)閏2的過程中經(jīng)過了幾次往復(fù).

4)可恢復(fù)型或暫時型(Recurring)：從一個概念暫時改變?yōu)榱硪粋€概念且經(jīng)過一段時間后會恢復(fù)到原始概念，如圖1(d)中c1暫時改變?yōu)閏2后又恢復(fù)到c1.

5)罕見型(Blip)：概念的異常改變，如圖1(e)中c1是異常，而非真正改變到c2.

6)噪聲型(Noise)：數(shù)據(jù)的隨機波動，不是真正的概念漂移.

圖1 概念漂移的主要類型

由于傳統(tǒng)分類算法只能處理可供多次訪問的有限靜態(tài)數(shù)據(jù)，與流數(shù)據(jù)的處理要求不相一致，因此，傳統(tǒng)分類算法不能直接用于解決流數(shù)據(jù)的分類問題.為了實現(xiàn)流數(shù)據(jù)的分類，現(xiàn)有研究通常在傳統(tǒng)分類算法的基礎(chǔ)上加入適應(yīng)流數(shù)據(jù)處理要求的相關(guān)功能.

決策樹作為一類經(jīng)典的傳統(tǒng)分類算法，能夠基于已知數(shù)據(jù)構(gòu)建具有多個分支的樹狀模型，實現(xiàn)數(shù)據(jù)的分類與預(yù)測.與神經(jīng)網(wǎng)絡(luò)等其他方法相比，決策樹具有較低的時間復(fù)雜度和較好的分類性能[8].當前，學(xué)術(shù)界已經(jīng)提出了大量基于決策樹的流數(shù)據(jù)分類算法.因此，為了確保完整性，本文在詳細介紹基于決策樹的流數(shù)據(jù)分類算法之前，先對傳統(tǒng)決策樹分類算法做一簡要概述.

2 傳統(tǒng)決策樹分類算法

決策樹分類過程通過應(yīng)用一系列規(guī)則，實現(xiàn)對數(shù)據(jù)的分類.依據(jù)樹中最優(yōu)劃分屬性選擇的不同，決策樹分類算法主要有ID3和C4.5兩類算法.此外，還有用于同時解決分類和回歸問題的CART算法.本文首先描述決策樹的構(gòu)造過程，然后分別介紹ID3、C4.5和CART算法.

2.1 決策樹

決策樹是由根結(jié)點、內(nèi)部結(jié)點和葉子結(jié)點構(gòu)成的樹狀結(jié)構(gòu).其中，根結(jié)點包含了待分類樣本的全集，內(nèi)部結(jié)點對應(yīng)于測試屬性，葉結(jié)點對應(yīng)于決策結(jié)果.算法1給出了決策樹的構(gòu)造過程[9].

算法首先從根結(jié)點開始，根據(jù)屬性的取值將樣本數(shù)據(jù)分成不同的子結(jié)點(從第1行到第7行)，直到當前結(jié)點屬于同一個類或者取相同的屬性值；然后根據(jù)屬性的取值，計算得到最優(yōu)劃分屬性并將該屬性作為當前結(jié)點；接著遞歸調(diào)用此方法，直到當前結(jié)點屬于一個類或者沒有屬性可以劃分，算法停止并完成決策樹的構(gòu)造.

算法1的核心步驟是最優(yōu)劃分屬性的選擇(第8行)，通常以信息增益、信息增益率和基尼指數(shù)作為其選擇依據(jù).其中，信息增益是指屬性劃分前后熵(熵是度量樣本中屬性不確定性的指標)的差值，信息增益率是指信息增益與某一特征熵的比值，基尼指數(shù)是指樣本被選中的概率與樣本被錯分的概率的乘積.

算法1：TreeGenerate_DT(D,A)

Inputs：D= {(x1,y1),(x2,y2),…,(xm,ym)} ——訓(xùn)練集；

A={a1,a2,…,ad}——屬性集

Output： 以node為根結(jié)點的一棵決策樹

Process：

1.生成結(jié)點node；

2.ifD中樣本全屬于同一類別Cthen

3. 將node標記為C類葉結(jié)點；return

4.endif

5.ifA=?orD中樣本在A上取值相同then

6. 將 node 標記為葉結(jié)點，其類別標記為D中樣本數(shù)最多的類； return

7.endif

8.從A中選擇最優(yōu)劃分屬性a*；

11.ifDv為空then

12. 將分支結(jié)點標記為葉結(jié)點，其類別標記為D中樣本最多的類；return

13.else

14. 以TreeGenerate (Dv,A{a*})為分支結(jié)點

15.endif

16.endfor

2.2 決策樹分類算法

如前所述，因最優(yōu)劃分屬性選擇的不同，決策樹分類主要有ID3、C4.5和CART等幾類.其中，ID3采用信息增益，C4.5采用信息增益率，CART采用基尼指數(shù).

2.2.1 ID3算法

ID3算法[10]運用信息熵理論，每次選擇當前樣本中具有最大信息增益的屬性作為測試屬性a*.令pk代表樣本集D中屬于類別k樣本的比率，|y|代表類別數(shù)，信息熵可計算如下：

(1)

雖然ID3算法有著清晰的理論基礎(chǔ)，但是，每個屬性的取值一定程度上影響著信息增益的大小，因而計算訓(xùn)練集的信息增益就會出現(xiàn)偏差.此外，ID3算法對噪聲較為敏感，而且當訓(xùn)練集增加時，決策樹的規(guī)模也隨之增加，不利于漸進學(xué)習(xí).

表1 西瓜數(shù)據(jù)集

以表1給出的數(shù)據(jù)集[11]為例，運用信息熵理論構(gòu)建一棵判斷是否為好瓜的決策樹.其中，類別數(shù)|y|=2，即有好瓜和差瓜兩類，正例(好瓜)p1= 8/17，反例(差瓜)p2= 9/17.根據(jù)式(1)計算根結(jié)點的信息熵為：

=0.998

計算當前屬性集合{色澤，根蒂，敲聲，紋理，臍部，觸感}的信息增益，以屬性“根蒂”為例，它有3個可能的取值：{卷縮，稍蜷，硬挺}.通過該屬性對樣本集進行劃分，得到“根蒂=卷縮”、“根蒂=稍蜷”、“根蒂=硬挺”.其中，在“根蒂=卷縮”中，正例占p1=5/8，反例占p2=3/8；在“根蒂=稍蜷”中，正例占p1=3/7，反例占p2=4/7；在“根蒂=硬挺”中，正例占p1=0，反例占p2=1.根據(jù)式(1)可計算出根蒂劃分后所獲得的3個分支的信息熵為：

E(根蒂=硬挺)=0

最后，可計算出屬性“根蒂”的信息增益為0.143.類似地，計算出所有其他屬性，找到信息增益最大的是“紋理”，即把“紋理”作為根結(jié)點，再對“紋理”的各個分支做進一步劃分，最后即可得到判定西瓜好差的決策樹.

2.2.2 C4.5算法

C4.5算法[12]雖然繼承了ID3算法的優(yōu)點，有著與ID3相同的算法思想，但又有如下幾個方面的改進：

1)用信息增益率而非信息增益作為劃分屬性選擇的依據(jù).

2)在樹的構(gòu)建過程中做剪枝處理.

3)可以對連續(xù)屬性進行離散化處理.

4)能夠?qū)Σ煌暾麛?shù)據(jù)進行處理，即可應(yīng)用于缺失值的處理.

信息增益率主要指在信息增益的基礎(chǔ)上引入分裂信息值，信息增益率定義如下：

(2)

其中，G(D,a)是信息增益，IV(a)是屬性a的分裂信息.例如，對表1西瓜數(shù)據(jù)集，有IV(觸感)=0.874(V=2)，IV(色澤)=1.580(V=3).

由于信息增益傾向于那些有著更多取值的屬性，為了降低這種因素的影響，C4.5采用信息增益率選擇劃分屬性.首先選擇信息增益高于平均水平的屬性，然后從中選擇增益率高的屬性.但是，在樹的構(gòu)建過程中，需要對數(shù)據(jù)集進行多次順序掃描和排序，因而導(dǎo)致較高的時間復(fù)雜度.雖然C4.5同ID3解決類似的問題，但C4.5的準確度更高.

2.2.3 CART算法

針對C4.5算法時間復(fù)雜度偏高的不足，Breiman等[13]提出了一種分類回歸樹算法(Classification And Regression Tree,CART)，該算法由決策樹的構(gòu)建和決策樹的剪枝兩部分構(gòu)成.其中，決策樹的構(gòu)建過程就是生成二叉決策樹的過程.CART算法既可以用于分類，也可用于回歸；既可處理離散問題，也可處理連續(xù)問題.

CART采用基尼指數(shù)選擇劃分屬性，基尼指數(shù)越小，數(shù)據(jù)集的純度越高.基尼純度表示在子集中正確選擇一個隨機樣本的可能性.基尼指數(shù)定義如下：

(3)

其中，G(Dv)是樣本集中的隨機樣本.

CART可充分運用全部的數(shù)據(jù)，能夠處理孤立點、空缺值.需要注意的是，CART更適用于較大的樣本量，相反，當樣本量較小時模型不夠穩(wěn)定.

3 基于決策樹的流數(shù)據(jù)分類

基于傳統(tǒng)決策樹算法，針對流數(shù)據(jù)的特性，學(xué)術(shù)界提出了一系列基于決策樹的流數(shù)據(jù)分類算法.根據(jù)算法是否考慮流數(shù)據(jù)中的概念漂移，本文將基于決策樹的流數(shù)據(jù)分類算法分為不含概念漂移的算法和包含概念漂移的算法兩大類.

3.1 不含概念漂移的分類算法

快速決策樹(Very Fast Decision Tree,VFDT)是不含概念漂移分類算法的典型代表，也是基于決策樹的流數(shù)據(jù)分類算法的基礎(chǔ).基于VFDT，學(xué)術(shù)界提出了一系列分類算法，主要包括VFDTc、FVFDT、ocVFDT、VFDTs、uVFDTc和SVFDT等.

3.1.1 VFDT算法

Domingos和Hulten[14]提出了VFDT算法，該算法采用信息熵和基尼指數(shù)作為選擇分裂屬性的標準，以Hoeffding不等式[15]作為判定結(jié)點分裂的條件.VFDT算法的詳細流程見算法2.

算法2：TreeGenerate_VFDT(T,G,δ,τ)

Inputs：T——離散流數(shù)據(jù)；

G——信息增益；

δ——置信度；

τ——分裂系數(shù)

Output：動態(tài)決策樹

Process：

1.初始化決策樹，此時只包含根結(jié)點root

2.for所有的訓(xùn)練樣本do

3. 樣本從根結(jié)點開始，按照最佳屬性選擇分支，直至到達葉子結(jié)點；

4. 更新葉子結(jié)點的統(tǒng)計信息(初值設(shè)為0)

5. 更新葉子結(jié)點的實例數(shù)(nl)

6.ifnlmod nmin=0 and 實例不屬于同一個類，其中nmin是人為設(shè)定閾值

7. 計算該葉子結(jié)點l所有屬性的信息增益Gl

8. 設(shè)Xa是Gl最大的屬性

9. 設(shè)Xb是Gl次大的屬性

10. 計算Hoeffding值

11.ifXa≠Xφand (Gl(Xa)-Gl(Xb)) >εORε<τthen

12. 葉子結(jié)點將作為內(nèi)部結(jié)點，屬性Xa作為該結(jié)點的決策屬性

13. 由Xa的取值數(shù)目確定新葉子結(jié)點數(shù)目

14.for所有的分支do

15. 生成新的葉子結(jié)點，同時含有分裂結(jié)點

16.endfor

17.endif

18.endif

19.endfor

算法2中的信息增益與決策樹算法中的定義相同，在決策樹的葉子結(jié)點中存儲數(shù)據(jù)的統(tǒng)計信息，用于信息增益的計算.該算法依據(jù)屬性不斷劃分結(jié)點，葉子結(jié)點的統(tǒng)計值會隨著在樣本的遍歷而不斷更新.

Hoeffding邊界能夠很好地解決流數(shù)據(jù)樣本過多的問題，其形式化定義如下：

(4)

其中，R代表信息增益的范圍，n代表觀察值，1-δ代表可信度.

VFDT的一個典型應(yīng)用是通過統(tǒng)計高校的Web頁面請求流，預(yù)測高校在將來請求哪些主機和頁面.首先將日志分割成一系列相等的時間片，通過在一定時間內(nèi)訪問主機的情況，建立VFDT算法模型，從而預(yù)測未來訪問主機的情況.

VFDT處理流數(shù)據(jù)時效果良好，且在時間復(fù)雜度和準確度上要優(yōu)于傳統(tǒng)的分類算法.該算法還解決了Hoeffding樹沒有提到的實際問題，即當兩個屬性的信息增益近似相等時，權(quán)衡兩個屬性需要花費大量的時間和空間，而VFDT提供了一個人為設(shè)定的閾值來解決這種問題.但VFDT不能處理概念漂移問題，同時，此算法沒有考慮處理具有連續(xù)值屬性的問題.

3.1.2 基于VFDT的擴展算法

針對VFDTc算法計算開銷大的不足，Wang等[19][20]提出了模糊VFDT算法FVFDE(Fuzzy VFDT).該算法采用模糊決策樹T-S模型分類方法，首先利用T算子計算出所有葉結(jié)點的類別隸屬度，然后利用S算子計算出該樣本對所有類別的隸屬度，最后利用去模糊化方法確定該樣本的最終分類.FVFDT減少了算法的時間復(fù)雜度，有效解決了噪聲問題，提高了分類精度.

由于流數(shù)據(jù)分類屬于監(jiān)督學(xué)習(xí)的范疇，同傳統(tǒng)的分類問題一樣，數(shù)據(jù)標記依然是流數(shù)據(jù)分類需要解決的耗時而棘手的問題.文獻[21]在VFDT的基礎(chǔ)上提出了一種單類快速決策樹分類算法ocVFDT(oneclass VFDT)，該算法沿著樹遍歷樣本到達葉子結(jié)點，結(jié)點處可生長出新的葉子.對于結(jié)點上的每個可用屬性，算法計算信息增益.如果滿足分割條件，則生成新的葉結(jié)點.在計算新葉結(jié)點時，正樣本和未標記樣本的計數(shù)均來自父結(jié)點.即便是當流數(shù)據(jù)中有80%的樣本尚未做標記的情況下，算法仍然具有出色的分類性能.該算法在信用欺詐檢測的案例中，將造成不良經(jīng)濟影響的用戶行為視作正樣本，而那些尚未造成不良影響的行為可視作未標記的樣本.此外，ocVFDT算法也可用于網(wǎng)絡(luò)入侵行為的檢測.

VFDTs算法[22](VFDT stream)是專為流數(shù)據(jù)問題而設(shè)計的增量式?jīng)Q策樹，該算法在VFDT的基礎(chǔ)上進行了改進，能夠處理非常復(fù)雜的數(shù)據(jù)(如維度較高的數(shù)據(jù)).當?shù)竭_葉結(jié)點時，算法將更新所有統(tǒng)計信息.如果有足夠的統(tǒng)計支持度，那么葉子將被轉(zhuǎn)換為決策結(jié)點，并創(chuàng)建兩個新的子代.VFDTs算法應(yīng)用廣泛，例如CRPGs游戲，玩家在每一輪戰(zhàn)斗中有多種選擇，使得游戲中的決策變成了一項復(fù)雜的推理任務(wù).

VFDT算法假定流數(shù)據(jù)是確定的，然而這種假設(shè)在實際應(yīng)用中并不總是成立的.由于測量的不精確、數(shù)值的缺失及隱私保護等問題，數(shù)據(jù)不確定性在流數(shù)據(jù)中普遍存在.例如，在信用卡欺詐檢測、環(huán)境監(jiān)測、傳感器網(wǎng)絡(luò)方面，有效信息可能會被不確定的值所掩蓋.uVFDTc算法[21](uncertain VFDT classification)在處理不確定數(shù)據(jù)方面進行了嘗試，能夠用于解決不確定性數(shù)據(jù)的分類和數(shù)值類型數(shù)據(jù)的分類.在uVFDTc樹的構(gòu)建過程中，將一個新的不確定訓(xùn)練樣本分割成若干個子樣本，并從根結(jié)點開始，遞歸劃分生成子結(jié)點.在葉結(jié)點中，從該葉結(jié)點的不確定樣本中收集到足夠的統(tǒng)計信息，對這些統(tǒng)計數(shù)據(jù)進行Hoeffding檢驗.如果通過測試，則選擇分裂屬性并將葉結(jié)點拆分為一個內(nèi)部結(jié)點.

針對VFDT算法的存儲空間消耗過大的問題，SVFDT算法[23](Strict VFDT)通過在不斷降低預(yù)測性能的前提下，對樹的生長施以強行控制以修改VFDT.SVFDT算法在VFDT的基礎(chǔ)上引入了一個函數(shù)，該函數(shù)可以判斷給定的葉子是否應(yīng)該被分割.當滿足VFDT的分割條件時，所有統(tǒng)計數(shù)據(jù)都會被更新.由于SVFDT創(chuàng)建的樹比VFDT要淺，因此SVFDT可以獲得更高的處理效率.SVFDT算法可以處理垃圾郵件等大數(shù)據(jù)量的分類問題.未來若能夠?qū)煞N算法合成一個整體，可在提高預(yù)測精度的同時，確保較低的內(nèi)存需求和訓(xùn)練時間.

3.2 含概念漂移的分類算法

3.2.1 CVFDT算法

2001年提出了概念自適應(yīng)的快速決策樹CVFDT(Concept adaptive VFDT)算法，該算法在VFDT算法中集成了固定大小的滑動窗口，從而有效解決了概念漂移問題.其中，概念漂移又有虛擬(Virtual)概念漂移和真實(Real)概念漂移之分[24].算法3給出了CVFDT算法的偽代碼.

算法3:TreeGenerate CVFDT((X,Y),nijk,ΔG,nmin,w)

Inputs：(X,Y) ——流數(shù)據(jù)；

nijk——初始化結(jié)點統(tǒng)計數(shù)；

ΔG——任意結(jié)點上選擇正確屬性的期望概率；

nmin——檢查樹增長的樣例數(shù)；

w——窗口大小

Output：HT——決策樹

Process：

1.ifW>wthen

2. Forget Example //釋放空間

3. Remove Example //從窗口中刪除樣例

4.endif

5. CVFDTGrow((x,y),HT,δ) //CVFDT增長過程

6. 將(x,y)存入葉子結(jié)點L中

7.for(x,y)經(jīng)過的每個結(jié)點Lido

8. 更新各結(jié)點的統(tǒng)計信息nijk;

9. 遞歸調(diào)用CVFDTGrow

10.endfor

11.ifL中樣例不都屬于同一類別 and 在當前結(jié)點樣例數(shù)大于nmin;

12.if選擇最佳與次佳分裂屬性的信息熵ΔG>εorΔG<ε<τ

13.Aa為最佳分裂屬性，Ab為次最佳分裂屬性，在結(jié)點L中分裂；

14.endif

15.endif

18. 遞歸調(diào)用CheckSplitValidity

19.endfor

20.if屬性Aa與Ab的觀測值G的差值，即G(Aa)-G(Ab) >ε

21.Aa成為當前的最佳分裂屬性

22.endif

由算法3可知，CVFDT算法主要包括四個步驟：樹的構(gòu)建(CVFDTGrow)、釋放空間(Forget Example)、樣本移除(Remove Example)和分裂檢測(Check Split Validity)等四個過程.該算法的主要思想是在VFDT算法的基礎(chǔ)上引入滑動窗口，使得建立的決策樹能夠被不斷更新.假設(shè)窗口的大小w，在任一時間點n(n通常是當前時間點)，滑動窗口的查詢范圍表示為{max(0,n-w+1)}.模型使用當前的流數(shù)據(jù)建立臨時子樹，之后用新的流數(shù)據(jù)不斷優(yōu)化建好的決策樹.

CVFDT有效地解決了由于流數(shù)據(jù)樣本的不斷變化而可能引發(fā)的概念漂移問題，且能夠反映當前流數(shù)據(jù)的分布情況，還可以不斷更新算法建立的模型.然而，當舊的概念再次出現(xiàn)時，CVFDT需要重新遍歷樹，使得算法的效率有所下降；其次，CVFDT算法無法自動檢測概念漂移的發(fā)生.

3.2.2 基于CVFDT的擴展算法

葉愛玲[25]提出了一種多概念自適應(yīng)快速決策樹算法mCVFDT(multiple Concept adaptive VFDT)，該算法采用多重選擇機制，將所有最佳預(yù)測屬性和最近到達屬性加入到結(jié)點結(jié)構(gòu)中，不需要備選子樹.當舊的概念出現(xiàn)時，mCVFDT可從自身結(jié)點重新選擇合適的子樹，避免對樹的重復(fù)遍歷.在選擇屬性加入結(jié)點結(jié)構(gòu)的過程中，將預(yù)測屬性的精度與當前屬性的分類精度進行動態(tài)比較，從而實現(xiàn)了概念漂移的檢測.相對于CVFDT，mCVFDT在處理大量樣本時的性能更佳.然而，mCVFDT算法的實際應(yīng)用案例缺乏，其性能需要進一步驗證.

iOVFDT(incrementally Optimized VFDT)算法[26,27]在VFDT的基礎(chǔ)上進行了擴展，提出了針對精度、模型大小和速度的增量優(yōu)化機制，使VFDT算法能夠更好的適應(yīng)概念漂移.iOVFDT是一種新的增量樹歸納方法，具有優(yōu)化的自適應(yīng)學(xué)習(xí)能力的結(jié)點劃分機制.在樹的構(gòu)建過程中，對每個分裂結(jié)點做優(yōu)化處理，通過對功能葉子的預(yù)測實現(xiàn)對精度的監(jiān)控，通過更新樹的結(jié)構(gòu)適應(yīng)可能存在的概念漂移.相比樸素貝葉斯(Naive Bayes)、加權(quán)樸素貝葉斯(Weighted Naive Bayes)等方法，iOVFDT的分類準確度更高.事實上，iOVFDT提供了一種尋找平衡解決方案的機制，它的模型小、內(nèi)存占用少，同時具有較好的分類精度.

Liu等[28]提出了E-CVFDT(Efficiency CVFDT)的算法，該算法能夠處理不同類型的概念漂移.在樹的構(gòu)建過程中，當樣本的數(shù)目超過窗口大小時，表示窗口已滿，此時將對窗口中的所有樣本計算信息增益.此外，需要手工指定一個閾值，用于表示最大丟棄的樣本數(shù)占流入分類模型的樣本總數(shù)的比重.由于E-CVFDT只對數(shù)據(jù)分布做了重新分組處理，因此其時間復(fù)雜度是線性的.

Ren等[29]提出了iCVFDT算法(imbalanced CVFDT)，該算法通過將CVFDT與一種有效的重采樣技術(shù)集成，實現(xiàn)類不平衡數(shù)據(jù)問題的解決.當每個樣本(x,y)到達時，首先檢查類的分布；若當前到達的樣本總數(shù)大于滑動窗口的大小w，窗口向前滑動，產(chǎn)生一個以新到達的樣本(x,y)為開始的新窗口.iCVFDT分類算法有著與CVFDT類似的穩(wěn)定性能，同時可適用于不平衡數(shù)據(jù)的分類處理，如P2P流量數(shù)據(jù)的分類.

4 研究挑戰(zhàn)與方向

從已有研究可以看出，基于決策樹的流數(shù)據(jù)分類算法已經(jīng)引起了學(xué)術(shù)界的關(guān)注，也有了代表性的研究成果.相對而言，不含概念漂移的流數(shù)據(jù)分類算法取得了較多的研究成果.然而，基于決策樹的流數(shù)據(jù)分類仍然存在如下幾個方面的研究挑戰(zhàn)：

首先，由于流數(shù)據(jù)是現(xiàn)實世界的真實記錄，是否包含、何時包含概念漂移不受人為控制.為了實現(xiàn)含有概念漂移的流數(shù)據(jù)分類，需要在對概念漂移做深入探究的基礎(chǔ)上構(gòu)建可靠的分類算法，做到概念漂移與概念演化(Concept evolution)及異常改變的可靠區(qū)分.

其次，流數(shù)據(jù)不同于靜態(tài)數(shù)據(jù)，無法實現(xiàn)完整的持續(xù)存儲.因此數(shù)據(jù)標記將是影響流數(shù)據(jù)分類的突出問題之一[30]，因為基于決策樹的流數(shù)據(jù)分類屬于監(jiān)督學(xué)習(xí)的范疇，而大量真實數(shù)據(jù)缺乏有效標記.

最后，現(xiàn)實世界中的數(shù)據(jù)往往呈現(xiàn)出高維和不平衡特性，同時含有多種冗余信息.因此，從富含冗余信息的高維不平衡數(shù)據(jù)中提取有用信息，同樣極具挑戰(zhàn)性.基于稀疏矩陣的數(shù)據(jù)壓縮技術(shù)，在去除數(shù)據(jù)中的無用信息方面具有一定的作用，從而可以實現(xiàn)流數(shù)據(jù)低維模型的構(gòu)建.

5 總結(jié)

在傳統(tǒng)決策樹的基礎(chǔ)上，針對流數(shù)據(jù)的獨特處理需求，研究流數(shù)據(jù)分類問題，是數(shù)據(jù)挖掘領(lǐng)域的重要分支.本文首先簡要概述了傳統(tǒng)數(shù)據(jù)挖掘及其主要任務(wù)，然后詳述了流數(shù)據(jù)及其特征，特別是突出介紹了概念漂移；接著根據(jù)算法是否考察概念漂移，將現(xiàn)有基于決策樹的流數(shù)據(jù)分類算法劃分為不含概念漂移的算法和包含概念漂移的算法兩大類.就每一類算法，詳細介紹算法的基本原理和主要應(yīng)用，同時指出了其優(yōu)缺點.最后，指出了基于決策樹的流數(shù)據(jù)分類算法的研究方向.