摘 要:在網(wǎng)絡(luò)的許多應(yīng)用中數(shù)據(jù)是以流的形式存在的，例如網(wǎng)絡(luò)流、傳感器數(shù)據(jù)，以及網(wǎng)頁(yè)點(diǎn)擊流等，分析和挖掘這類數(shù)據(jù)，可以發(fā)現(xiàn)某中有價(jià)值的信息。在此，針對(duì)數(shù)據(jù)流挖掘算法中出現(xiàn)的一些問(wèn)題(如概念漂移問(wèn)題)，提出了一種自適應(yīng)模糊決策樹(shù)的優(yōu)化算法。該算法對(duì)于解決處理數(shù)據(jù)流概念中的漂移問(wèn)題有較好的效果。

關(guān)鍵詞:數(shù)據(jù)流; 概念漂移; 模糊決策樹(shù); 數(shù)據(jù)挖掘

中圖分類號(hào):TP301 文獻(xiàn)標(biāo)識(shí)碼:B

文章編號(hào):1004-373X(2010)10-0063-03

Application of Adaptive Fuzzy Decision Tree Algorithm in Data Stream Mining

ZHU Can-shi， LI Xiang

(Engineering College， Air Force Engineering University， Xi’an 710038， China)

Abstract:The data was existed in many applications of network as a form of stream， such as network flow， sensor data， Web click-stream and so on， some valuable information can be found by analysing and mining such data. An adaptive fuzzy decision tree optimization algorithm is proposed according to the problems (concept drift problem) of data stream mining algorithm. The method has better results for solving the concept driftprocessing data stream.

Keywords:data stream; concept drift; fuzzy decision tree; data mining

0 引 言

數(shù)據(jù)挖掘是從大量數(shù)據(jù)中“挖掘”知識(shí)，旨在從大量數(shù)據(jù)中提取隱藏的預(yù)測(cè)性信息，發(fā)掘數(shù)據(jù)間潛在的模式，找出某些被忽略的信息，作為決策的依據(jù)。在網(wǎng)絡(luò)的許多應(yīng)用中數(shù)據(jù)是以流形式存在的[1]。傳統(tǒng)的數(shù)據(jù)挖掘方法是基于靜態(tài)數(shù)據(jù)庫(kù)的頻繁模式，挖掘算法可以對(duì)數(shù)據(jù)庫(kù)進(jìn)行多次掃描，多次查找等。然而，數(shù)據(jù)流是大量連續(xù)到達(dá)、潛在無(wú)限的數(shù)據(jù)集合，其特點(diǎn)是:數(shù)據(jù)高速到達(dá)，數(shù)據(jù)流無(wú)法再現(xiàn)，實(shí)時(shí)性要求高以及數(shù)據(jù)量無(wú)限增長(zhǎng)等。因此，傳統(tǒng)的數(shù)據(jù)挖掘不適合對(duì)數(shù)據(jù)流的挖掘。在數(shù)據(jù)流挖掘研究中，有許多經(jīng)典算法，譬如:Manku提出的Lossy Counting算法[2]，Han提出基于FP-growth的FP-stream[3] 算法等。數(shù)據(jù)流常用的處理與分析方法可歸納為數(shù)據(jù)流頻繁項(xiàng)集挖掘算法、分類挖掘算法和聚類挖掘算法[4]。但這些算法在處理數(shù)據(jù)流時(shí)不同程度地產(chǎn)生概念漂移現(xiàn)象[5]，在分類挖掘數(shù)據(jù)流時(shí)，必須考慮數(shù)據(jù)流的變化特征，要及時(shí)刪除過(guò)時(shí)的類定義模式。 在聚類算法中，數(shù)據(jù)流隨著時(shí)間在不斷地變化，其隱含的聚類可能隨時(shí)間的動(dòng)態(tài)變化而導(dǎo)致聚類質(zhì)量的降低。本文提出一種改進(jìn)的基于概念自適應(yīng)模糊決策樹(shù)算法，以解決數(shù)據(jù)挖掘中的概念漂移問(wèn)題。

1 快速?zèng)Q策樹(shù)算法及其性能分析

快速?zèng)Q策樹(shù)算法[6](very fast decision tree，VFDT)的目標(biāo)是通過(guò)已有的訓(xùn)練樣本得出一個(gè)分類模型y=f(x)，對(duì)新測(cè)試樣本進(jìn)行正確分類。VFDT是一種基于Hoeffding不等式[7]，并針對(duì)數(shù)據(jù)流挖掘環(huán)境建立分類決策樹(shù)的方法，它通過(guò)不斷地將葉節(jié)點(diǎn)替換為分支節(jié)點(diǎn)，而生成決策樹(shù)，其所研究的樣本屬性為離散屬性。

1.1 快速?zèng)Q策樹(shù)算法的過(guò)程

快速?zèng)Q策樹(shù)算法過(guò)程如下:

(1) 快速?zèng)Q策樹(shù)(VFDT)的構(gòu)建是從根節(jié)點(diǎn)開(kāi)始的，根節(jié)點(diǎn)即為最初的葉節(jié)點(diǎn)。若s為一數(shù)據(jù)流序列，包含潛在無(wú)限多的樣本數(shù)據(jù)，則誤差參數(shù)δ由用戶在初始時(shí)刻給出。樣本的不同屬性字段由屬性集合{X1，X2，…，Xk}表示，k表示屬性的個(gè)數(shù)。

(2) 當(dāng)樣本數(shù)據(jù)依次流入VFDT系統(tǒng)時(shí)，起初所有的樣本數(shù)據(jù)都聚集在決策樹(shù)的根節(jié)點(diǎn)。隨著根節(jié)點(diǎn)樣本數(shù)據(jù)的增多，信息增益不斷增長(zhǎng)。用nt表示從零時(shí)刻到t時(shí)刻流入的樣本總數(shù)。

(3)以信息增益為屬性選擇度量，當(dāng)t時(shí)刻聚集在根節(jié)點(diǎn)的樣本數(shù)量為nt時(shí)，可以計(jì)算各屬性的信息增益。若屬性Xa的平均信息增益Gain(Xa)最大，屬性Xb的平均信息增益次之，并令:

ΔGain=Gain(Xa)-Gain(Xb)(1)

若ΔGain>ε，則由Hoeffding界可以保證選擇屬性Xa作為根節(jié)點(diǎn)的分裂屬性在概率1-δ下得到保證，且真正的信息增益之差ΔGain≥ΔGain-ε>0在概率1-δ下得到保證。因此，根據(jù)Hoeffding界便可以確定在根節(jié)點(diǎn)聚集的樣本數(shù)量nt，可進(jìn)行屬性分裂，這便是Hoeffding樹(shù)算法通過(guò)小樣本選擇最佳分裂屬性的過(guò)程。

(4) 決策樹(shù)生長(zhǎng)。若式(1)得到滿足，則根節(jié)點(diǎn)將根據(jù)最佳分裂屬性Xa生長(zhǎng)出子節(jié)點(diǎn)，并在其子節(jié)點(diǎn)中的備選屬性集中刪除屬性Xa，此過(guò)程遞歸進(jìn)行。由于數(shù)據(jù)流的潛在無(wú)限性，如果不加限制，決策樹(shù)將無(wú)限制增長(zhǎng)下去，若確定了樹(shù)的最大深度或其他度量指標(biāo)后，VFDT將通過(guò)最新到來(lái)的樣本數(shù)據(jù)對(duì)決策樹(shù)進(jìn)行增量更新，以保持其判斷的準(zhǔn)確性。

(5) 對(duì)內(nèi)存進(jìn)行優(yōu)化。在Hoeffding樹(shù)算法的基礎(chǔ)上，通過(guò)VFDT在內(nèi)存的優(yōu)化方面做出改進(jìn)，在當(dāng)前數(shù)據(jù)占滿內(nèi)存空間時(shí)，VFDT系統(tǒng)將暫時(shí)解除對(duì)分類決策影響最小的子節(jié)點(diǎn)所使用的空間。對(duì)于暫時(shí)失去活性的子節(jié)點(diǎn)，若后來(lái)其分類準(zhǔn)確率較之當(dāng)前的活躍節(jié)點(diǎn)高，將再次恢復(fù)其活性。

(6) 打破平局。當(dāng)最佳分裂屬性與次佳分裂屬性的平均信息增益之差很小時(shí)，傳統(tǒng)的Hoeffding樹(shù)算法將在屬性選擇上花費(fèi)大量的時(shí)間。VFDT算法引入了一個(gè)界限參數(shù)τ(由用戶提供)，若ΔGain≤ε<τ時(shí)，選擇增益最大的屬性為分裂屬性。

(7) 處理速度優(yōu)化，在步驟(3)中，傳統(tǒng)的Hoeffding樹(shù)算法會(huì)在每一個(gè)樣本到達(dá)時(shí)進(jìn)行一次分裂屬性測(cè)試，這將極大地影響系統(tǒng)的計(jì)算效率。VFDT系統(tǒng)引入了一個(gè)分裂屬性最小樣本數(shù)nmin(由用戶提供)，當(dāng)?shù)竭_(dá)節(jié)點(diǎn)的樣本數(shù)為nmin的整數(shù)倍時(shí)才進(jìn)行測(cè)試。

1.2 快速?zèng)Q策樹(shù)算法分析

VFDT算法利用Hoeffding界，以高概率確定在1個(gè)節(jié)點(diǎn)選擇分裂屬性時(shí)需要的樣本最小數(shù)量，這個(gè)屬性將與使用無(wú)限樣本得到的屬性一樣。由于快速?zèng)Q策樹(shù)算法的分類精度與單純樣本數(shù)量無(wú)關(guān)，其需要維護(hù)的惟一統(tǒng)計(jì)量是具有類標(biāo)號(hào)yk屬性Ai值vj的計(jì)數(shù)nijk。因此，若d是屬性的個(gè)數(shù)，v是屬性值的最大個(gè)數(shù)，c是類的個(gè)數(shù)，l是樹(shù)的最大深度，則內(nèi)存總需求為O(ldvc)。與其他決策樹(shù)算法相比，這一內(nèi)存需求是適度的，因此可實(shí)現(xiàn)對(duì)實(shí)時(shí)增量數(shù)據(jù)流的處理。

但是，由于VFDT算法沒(méi)有考慮概念漂移問(wèn)題，因此將VFDT算法直接對(duì)廣泛存在概念漂移的網(wǎng)絡(luò)數(shù)據(jù)流進(jìn)行分類時(shí)，會(huì)出現(xiàn)很大偏差。另外，隨著時(shí)間的推移和概念漂移的產(chǎn)生，VFDT樹(shù)中將積累大量過(guò)時(shí)的樣例，使得VFDT樹(shù)變得非常臃腫。

2 快速?zèng)Q策樹(shù)算法優(yōu)化方法

對(duì)于概念漂移問(wèn)題，可在原決策樹(shù)的生長(zhǎng)過(guò)程中予以解決，即若有節(jié)點(diǎn)出現(xiàn)分類不準(zhǔn)，則在相應(yīng)節(jié)點(diǎn)旁派生出一顆替代子樹(shù)(Talt)。當(dāng)替代子樹(shù)生長(zhǎng)到足以對(duì)新到樣本進(jìn)行準(zhǔn)確分類時(shí)，將替代原樹(shù)中相應(yīng)的子樹(shù)。

2.1 優(yōu)化后算法的執(zhí)行過(guò)程

(1) 優(yōu)化后的算法核心決策樹(shù)仍然是Hoeffding樹(shù)。其原因是Hoeffding決策樹(shù)能夠依靠Hoeffding界原理，以小樣本替換無(wú)限樣本，構(gòu)建高效增量決策樹(shù)，并只需對(duì)數(shù)據(jù)流進(jìn)行一次掃描，這符合應(yīng)用需求。

(2) 優(yōu)化后的算法保持了VFDT系統(tǒng)的處理速度和準(zhǔn)確度，并引入了對(duì)新到樣本發(fā)生概念漂移時(shí)的響應(yīng)機(jī)制。在算法中，加入了滑動(dòng)窗口W，當(dāng)新樣本到達(dá)時(shí)，將其加入滑動(dòng)窗口?；瑒?dòng)窗口的任務(wù)是當(dāng)有新樣本到達(dá)時(shí)，靠增加決策樹(shù)相應(yīng)節(jié)點(diǎn)中的計(jì)數(shù)來(lái)回應(yīng)新樣本特性。與此同時(shí)，減少舊樣本或過(guò)時(shí)樣本中相應(yīng)的計(jì)數(shù)來(lái)維持一個(gè)最新的分類模型，而不是一有新樣本到達(dá)就創(chuàng)建一個(gè)新模型[8]。

(3) 優(yōu)化后的算法中對(duì)滑動(dòng)窗口進(jìn)行了改進(jìn)，對(duì)每個(gè)數(shù)據(jù)流樣本引入1個(gè)影響因子β∈[0，1]。β值的作用是用來(lái)判斷決策樹(shù)的分類效用，并根據(jù)其取值的不同來(lái)影響滑動(dòng)窗口中樣本的計(jì)數(shù)值，進(jìn)而對(duì)滑動(dòng)窗口的大小進(jìn)行動(dòng)態(tài)調(diào)整[9]。在改進(jìn)的滑動(dòng)窗口中，對(duì)流過(guò)樣本的計(jì)數(shù)則基于影響因子的計(jì)數(shù)nijkβ。當(dāng)決策樹(shù)中，某個(gè)樣本分類出現(xiàn)偏差時(shí)，該樣本在滑動(dòng)窗口中的影響因子β將在0≤β<1的范圍內(nèi)，β趨于0的程度正比于偏差節(jié)點(diǎn)與根節(jié)點(diǎn)的距離，可以用樹(shù)深l(出現(xiàn)偏差的層數(shù))來(lái)表示，即β∝l。相反，當(dāng)實(shí)際分類為正確分類時(shí)，β=1。在滑動(dòng)窗口中設(shè)定1個(gè)閾值ζ(如0.5)，設(shè)|W|為滑動(dòng)窗口中的樣本計(jì)數(shù)，|W|∈[0，nijk]，并規(guī)定當(dāng)滿足:

|W|=nijkβ≤ζ (2)

說(shuō)明發(fā)生明顯概念漂移，鎖定出錯(cuò)節(jié)點(diǎn)，構(gòu)造替代子樹(shù)，并縮小滑動(dòng)窗口的大小，直到下式成立;

|W|>ζ(3)

當(dāng):

|W|=nijkβ>ζ(4)

成立，并至少在T(人為界定)個(gè)窗口周期內(nèi)保持穩(wěn)定，此時(shí)以|W|/2增量遞歸擴(kuò)大滑動(dòng)窗口的大小，直到到達(dá)式(2)的臨界點(diǎn)時(shí)停止。

(4) 優(yōu)化后的算法將根據(jù)滑動(dòng)窗口中有效樣本的數(shù)量來(lái)判斷分裂的有效性，即:若式(2)滿足，將重新計(jì)算在滑動(dòng)窗口出現(xiàn)嚴(yán)重分裂偏差的節(jié)點(diǎn)中各屬性的模糊信息增益。若當(dāng)內(nèi)部某節(jié)點(diǎn)在向下分類且滑動(dòng)窗口中相應(yīng)樣本點(diǎn)的影響因子β較前一樣本點(diǎn)快速趨于0時(shí)，說(shuō)明在對(duì)該樣本點(diǎn)進(jìn)行分類時(shí)發(fā)生了概念漂移。這說(shuō)明該節(jié)點(diǎn)的屬性測(cè)試出現(xiàn)了偏差，此時(shí)將有1棵替代子樹(shù)產(chǎn)生。若一新樣本屬性Xnew的模糊信息增益高于當(dāng)前的分裂屬性Xcurr，則優(yōu)化后的算法將在相應(yīng)節(jié)點(diǎn)處以屬性Xnew為根節(jié)點(diǎn)生成1棵替代子樹(shù)。

(5) 對(duì)屬性分裂效用的判斷，將改進(jìn)VFDT算法中的方法。使用模糊信息增益的方法可周期性地檢測(cè)最佳分裂屬性。由于現(xiàn)實(shí)網(wǎng)絡(luò)數(shù)據(jù)流中存在大量的噪聲數(shù)據(jù)或非確定信息，即便是對(duì)于某些離散屬性字段，采用傳統(tǒng)的陡峭屬性分裂方法也會(huì)導(dǎo)致分類界限不清晰。因此，改進(jìn)后的算法，對(duì)于離散屬性和連續(xù)屬性都采用模糊信息增益作為屬性選擇度量。

(6) 替代子樹(shù)生長(zhǎng)過(guò)程控制。

為提高內(nèi)存利用率，替代子樹(shù)也需要控制其規(guī)模，并進(jìn)行適當(dāng)剪枝。剪枝的判斷標(biāo)準(zhǔn)以原子樹(shù)與替代子樹(shù)間分類的準(zhǔn)確度增量大小為依據(jù)。優(yōu)化后的算法規(guī)定，若替代子樹(shù)滿足式(5)，將對(duì)其保留;否則，將刪除該替代子樹(shù)。

Δaccuracy(litest，lialt)/litest(accuray)≥λ (5)

式中:i為原樹(shù)和替代樹(shù)中的節(jié)點(diǎn)編號(hào);λ為替代子樹(shù)保留的閾值。

式(5)中，準(zhǔn)確度可用該節(jié)點(diǎn)正確分類樣本數(shù)與流經(jīng)該節(jié)點(diǎn)總樣本之比來(lái)定義，即:

litest(accuray)=niright/niall (6)

2.2 優(yōu)化流程如圖

優(yōu)化流程如圖1所示。

3 優(yōu)化算法驗(yàn)證

由于本文研究的是數(shù)據(jù)流環(huán)境下的挖掘算法，為了驗(yàn)證算法的有效性，必須對(duì)靜態(tài)數(shù)據(jù)集進(jìn)行動(dòng)態(tài)化處理。根據(jù)流數(shù)據(jù)區(qū)別于靜態(tài)數(shù)據(jù)的潛在無(wú)限、動(dòng)態(tài)變化，以及對(duì)流數(shù)據(jù)的處理單遍掃描、實(shí)時(shí)處理等特點(diǎn)及要求進(jìn)行動(dòng)態(tài)處理。另外，由于在網(wǎng)絡(luò)傳輸過(guò)程中傳輸數(shù)據(jù)將受到自然環(huán)境和電磁環(huán)境的干擾，因此在實(shí)驗(yàn)中將向每組實(shí)驗(yàn)數(shù)據(jù)加入5%的噪聲數(shù)據(jù)。

在實(shí)際操作中，從數(shù)據(jù)集中隨機(jī)順序抽取100萬(wàn)條樣本作為測(cè)試數(shù)據(jù)，初始屬性數(shù)為5，每增加10個(gè)屬性檢測(cè)1次結(jié)果，經(jīng)Matlab[10]仿真后的效果圖如圖2所示，圖中標(biāo)出了隨著用于分類的屬性增多，概念漂移的變化情況。

圖1 改進(jìn)后的算法流程

圖2 2種算法實(shí)驗(yàn)對(duì)比圖和樣本概念漂移百分比變化情況

4 結(jié) 語(yǔ)

改進(jìn)算法引入了滑動(dòng)窗口技術(shù)，滑動(dòng)窗口中的所有樣本都可以全部放入內(nèi)存，并通過(guò)窗口機(jī)制來(lái)實(shí)時(shí)判斷系統(tǒng)對(duì)外圍數(shù)據(jù)的分類效果。因此，其效率與樣本總數(shù)無(wú)關(guān)。另外，滑動(dòng)窗口的引入也使得改進(jìn)系統(tǒng)所生成的分類模型始終與當(dāng)前情況相適應(yīng)，改善了概念漂移對(duì)前面分類模型的影響。另一方面，通過(guò)構(gòu)建屬性二叉樹(shù)的方法使得當(dāng)新樣本插入時(shí)算法只需更新一個(gè)節(jié)點(diǎn)，時(shí)間

復(fù)雜度為O(nlog n)，比VFDT的O(n2)要好(其中n為當(dāng)前節(jié)點(diǎn)上所觀察到連續(xù)屬性i的不同取值數(shù)目)。從仿真圖可以看出，由于改進(jìn)后的算法是基于數(shù)據(jù)挖掘的動(dòng)態(tài)增量決策樹(shù)算法，隨著流入樣本的增多，規(guī)則將被逐條建立，而且分類決策樹(shù)會(huì)隨著分類屬性字段的增多而變得更精確。隨著分類屬性的增多，發(fā)生概念漂移的樣本數(shù)會(huì)增加，這才顯示出解決概念漂移的能力強(qiáng)。

參考文獻(xiàn)

[1]徐國(guó)愛(ài).網(wǎng)絡(luò)安全[M].北京:北京郵電大學(xué)出版社，2004.

[2]MANKU G S，MOTWANI R. Approximate frequency counts over streaming data[C]//The 28th International Conference on Very Large Databases. Santiago: [s.n.]， 2002: 93-101.

[3]GIANNELLA C， HAN J， PEI J. Mining frequent patterns in data streams at multiple time granularities[J].Next Ge-neration Data Mining，2003，45(17): 217-221.

[4]史金成，胡學(xué)剛.數(shù)據(jù)流挖掘研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2007，17(1):11-14.

[5]王建濤，蔡淮.流數(shù)據(jù)慣例若干關(guān)鍵問(wèn)題的研究[J].成都信息工程學(xué)院學(xué)報(bào)，2008，23(3):269-274.

[6]DOMINGOS P， HULTEN G. Mining high-speed data streams[C]//International Conference on Knowledge Discovery and Data Mining， [S.l.]: [s.n.]， 2000:37-42.

[7]HULTEN G， SPENCER L， DOMINGOS P.Mining time-changing data stream[C]//International Conference on Knowledge Discovery and Data Mining. [S.l.]: [s.n.]， 2001:216-219.

[8][美]HOROWITZ Ellis， SAHNI Sartaj. 計(jì)算機(jī)算法(C++版)[M].馮博琴，葉茂，譯.北京:機(jī)械工業(yè)出版社，2006.

[9]李國(guó)徽，陳輝.挖掘數(shù)據(jù)流任意滑動(dòng)時(shí)間窗口內(nèi)頻繁模式[J].軟件學(xué)報(bào)，2008，19(10):13-15.

[10]陳杰.Matlab寶典[M].北京:電子工業(yè)出版社，2007.