自適應(yīng)模糊決策樹算法在數(shù)據(jù)流挖掘中的應(yīng)用

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

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

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

文章編號: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ù)據(jù)中提取隱藏的預(yù)測性信息，發(fā)掘數(shù)據(jù)間潛在的模式，找出某些被忽略的信息，作為決策的依據(jù)。在網(wǎng)絡(luò)的許多應(yīng)用中數(shù)據(jù)是以流形式存在的[1]。傳統(tǒng)的數(shù)據(jù)挖掘方法是基于靜態(tài)數(shù)據(jù)庫的頻繁模式，挖掘算法可以對數(shù)據(jù)庫進(jìn)行多次掃描，多次查找等。然而，數(shù)據(jù)流是大量連續(xù)到達(dá)、潛在無限的數(shù)據(jù)集合，其特點(diǎn)是:數(shù)據(jù)高速到達(dá)，數(shù)據(jù)流無法再現(xiàn)，實(shí)時性要求高以及數(shù)據(jù)量無限增長等。因此，傳統(tǒng)的數(shù)據(jù)挖掘不適合對數(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ù)流時不同程度地產(chǎn)生概念漂移現(xiàn)象[5]，在分類挖掘數(shù)據(jù)流時，必須考慮數(shù)據(jù)流的變化特征，要及時刪除過時的類定義模式。 在聚類算法中，數(shù)據(jù)流隨著時間在不斷地變化，其隱含的聚類可能隨時間的動態(tài)變化而導(dǎo)致聚類質(zhì)量的降低。本文提出一種改進(jìn)的基于概念自適應(yīng)模糊決策樹算法，以解決數(shù)據(jù)挖掘中的概念漂移問題。

1 快速決策樹算法及其性能分析

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

1.1 快速決策樹算法的過程

快速決策樹算法過程如下:

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

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

(3)以信息增益為屬性選擇度量，當(dāng)t時刻聚集在根節(jié)點(diǎn)的樣本數(shù)量為nt時，可以計算各屬性的信息增益。若屬性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樹算法通過小樣本選擇最佳分裂屬性的過程。

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

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

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

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

1.2 快速決策樹算法分析

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

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

2 快速決策樹算法優(yōu)化方法

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

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

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

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

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

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

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

|W|>ζ(3)

當(dāng):

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

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

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

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

(6) 替代子樹生長過程控制。

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

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

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

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

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

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

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

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

4 結(jié) 語

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

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

參考文獻(xiàn)

[1]徐國愛.網(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ī)技術(shù)與發(fā)展，2007，17(1):11-14.

[5]王建濤，蔡淮.流數(shù)據(jù)慣例若干關(guān)鍵問題的研究[J].成都信息工程學(xué)院學(xué)報，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ī)算法(C++版)[M].馮博琴，葉茂，譯.北京:機(jī)械工業(yè)出版社，2006.

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

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