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

1、自適應模糊決策樹算法在數(shù)據(jù)流挖掘中的應用朱參世，李響(空軍工程大學工程學院，陜西西安710038)0引言數(shù)據(jù)挖掘是從大量數(shù)據(jù)中“挖掘”知識，旨在從大量數(shù)據(jù)中提取隱藏的預測性信息，發(fā)掘數(shù)據(jù)間潛在的模式，找出某些被忽略的信息，作為決策的依據(jù)。在網(wǎng)絡的許多應用中數(shù)據(jù)是以流形式存在的。傳統(tǒng)的數(shù)據(jù)挖掘方法是基于靜態(tài)數(shù)據(jù)庫的頻繁模式，挖掘算法可以對數(shù)據(jù)庫進行多次掃描，多次查找等。然而，數(shù)據(jù)流是大量連續(xù)到達、潛在無限的數(shù)據(jù)集合，其特點是：數(shù)據(jù)高速到達，數(shù)據(jù)流朱參世，李響(空軍工程大學 工程學院，陜西西安 710038)0引 言數(shù)據(jù)挖掘是從大量數(shù)據(jù)中“挖掘”知識，旨在從大量數(shù)據(jù)中提取隱藏的預測性信息，發(fā)掘數(shù)據(jù)

2、間潛在的模式，找出某些被忽略的信息，作為決策的依據(jù)。在網(wǎng)絡的許多應用中數(shù)據(jù)是以流形式存在的。傳統(tǒng)的數(shù)據(jù)挖掘方法是基于靜態(tài)數(shù)據(jù)庫的頻繁模式，挖掘算法可以對數(shù)據(jù)庫進行多次掃描，多次查找等。然而，數(shù)據(jù)流是大量連續(xù)到達、潛在無限的數(shù)據(jù)集合，其特點是：數(shù)據(jù)高速到達，數(shù)據(jù)流無法再現(xiàn)，實時性要求高以及數(shù)據(jù)量無限增長等。因此，傳統(tǒng)的數(shù)據(jù)挖掘不適合對數(shù)據(jù)流的挖掘。在數(shù)據(jù)流挖掘研究中，有許多經(jīng)典算法，譬如：Manku提出的Lossy Counting算法，Han提出基于FP-growth的FP-stream算法等。數(shù)據(jù)流常用的處理與分析方法可歸納為數(shù)據(jù)流頻繁項集挖掘算法、分類挖掘算法和聚類挖掘算法。但這些算法在處

3、理數(shù)據(jù)流時不同程度地產(chǎn)生概念漂移現(xiàn)象，在分類挖掘數(shù)據(jù)流時，必須考慮數(shù)據(jù)流的變化特征，要及時刪除過時的類定義模式。在聚類算法中，數(shù)據(jù)流隨著時間在不斷地變化，其隱含的聚類可能隨時間的動態(tài)變化而導致聚類質(zhì)量的降低。本文提出一種改進的基于概念自適應模糊決策樹算法，以解決數(shù)據(jù)挖掘中的概念漂移問題。1 快速決策樹算法及其性能分析快速決策樹算法(very fast decision tree，VFDT)的目標是通過已有的訓練樣本得出一個分類模型y=f(x)，對新測試樣本進行正確分類。VFDT是一種基于Hoeffding不等式，并針對數(shù)據(jù)流挖掘環(huán)境建立分類決策樹的方法，它通過不斷地將葉節(jié)點替換為分支節(jié)點，而生

4、成決策樹，其所研究的樣本屬性為離散屬性。1.1 快速決策樹算法的過程快速決策樹算法過程如下：(1)快速決策樹(VFDT)的構建是從根節(jié)點開始的，根節(jié)點即為最初的葉節(jié)點。若s為一數(shù)據(jù)流序列，包含潛在無限多的樣本數(shù)據(jù)，則誤差參數(shù)由用戶在初始時刻給出。樣本的不同屬性字段由屬性集合X1，X2，Xk表示，k表示屬性的個數(shù)。(2)當樣本數(shù)據(jù)依次流入VFDT系統(tǒng)時，起初所有的樣本數(shù)據(jù)都聚集在決策樹的根節(jié)點。隨著根節(jié)點樣本數(shù)據(jù)的增多，信息增益不斷增長。用nt表示從零時刻到t時刻流入的樣本總數(shù)。(3)以信息增益為屬性選擇度量，當t時刻聚集在根節(jié)點的樣本數(shù)量為nt時，可以計算各屬性的信息增益。若屬性Xa的平均信息

5、增益Gain(Xa)最大，屬性Xb的平均信息增益次之，并令：若Gain，則由Hoeffding界可以保證選擇屬性X作為根節(jié)點的分裂屬性在概率1-下得到保證，且真正的信息增益之差GainGain-0在概率1-下得到保證。因此，根據(jù)Hoeffding界便可以確定在根節(jié)點聚集的樣本數(shù)量nt，可進行屬性分裂，這便是Hoeffding樹算法通過小樣本選擇最佳分裂屬性的過程。(4)決策樹生長。若式(1)得到滿足，則根節(jié)點將根據(jù)最佳分裂屬性Xa生長出子節(jié)點，并在其子節(jié)點中的備選屬性集中刪除屬性Xa，此過程遞歸進行。由于數(shù)據(jù)流的潛在無限性，如果不加限制，決策樹將無限制增長下去，若確定了樹的最大深度或其他度量指

6、標后，VFDT將通過最新到來的樣本數(shù)據(jù)對決策樹進行增量更新，以保持其判斷的準確性。(5)對內(nèi)存進行優(yōu)化。在Hoeffding樹算法的基礎上，通過VFDT在內(nèi)存的優(yōu)化方面做出改進，在當前數(shù)據(jù)占滿內(nèi)存空間時，VFDT系統(tǒng)將暫時解除對分類決策影響最小的子節(jié)點所使用的空間。對于暫時失去活性的子節(jié)點，若后來其分類準確率較之當前的活躍節(jié)點高，將再次恢復其活性。(6)打破平局。當最佳分裂屬性與次佳分裂屬性的平均信息增益之差很小時，傳統(tǒng)的Hoeffding樹算法將在屬性選擇上花費大量的時間。VFDT算法引入了一個界限參數(shù)(由用戶提供)，若Gain<時，選擇增益最大的屬性為分裂屬性。(7)處理速度優(yōu)化，在

7、步驟(3)中，傳統(tǒng)的Hoeffding樹算法會在每一個樣本到達時進行一次分裂屬性測試，這將極大地影響系統(tǒng)的計算效率。VFDT系統(tǒng)引入了一個分裂屬性最小樣本數(shù)nmin(由用戶提供)，當?shù)竭_節(jié)點的樣本數(shù)為nmin的整數(shù)倍時才進行測試。1.2 快速決策樹算法分析VFDT算法利用Hoeffding界，以高概率確定在1個節(jié)點選擇分裂屬性時需要的樣本最小數(shù)量，這個屬性將與使用無限樣本得到的屬性一樣。由于快速決策樹算法的分類精度與單純樣本數(shù)量無關，其需要維護的惟一統(tǒng)計量是具有類標號yk屬性Ai值vj的計數(shù)nijk。因此，若d是屬性的個數(shù)，v是屬性值的最大個數(shù)，c是類的個數(shù)，l是樹的最大深度，則內(nèi)存總需求為O

8、(ldvc)。與其他決策樹算法相比，這一內(nèi)存需求是適度的，因此可實現(xiàn)對實時增量數(shù)據(jù)流的處理。但是，由于VFDT算法沒有考慮概念漂移問題，因此將VFDT算法直接對廣泛存在概念漂移的網(wǎng)絡數(shù)據(jù)流進行分類時，會出現(xiàn)很大偏差。另外，隨著時間的推移和概念漂移的產(chǎn)生，VFDT樹中將積累大量過時的樣例，使得VFDT樹變得非常臃腫。2 快速決策樹算法優(yōu)化方法對于概念漂移問題，可在原決策樹的生長過程中予以解決，即若有節(jié)點出現(xiàn)分類不準，則在相應節(jié)點旁派生出一顆替代子樹(Talt)。當替代子樹生長到足以對新到樣本進行準確分類時，將替代原樹中相應的子樹。2.1 優(yōu)化后算法的執(zhí)行過程(1)優(yōu)化后的算法核心決策樹仍然是Ho

9、effding樹。其原因是Hoeffding決策樹能夠依靠Hoeffding界原理，以小樣本替換無限樣本，構建高效增量決策樹，并只需對數(shù)據(jù)流進行一次掃描，這符合應用需求。(2)優(yōu)化后的算法保持了VFDT系統(tǒng)的處理速度和準確度，并引入了對新到樣本發(fā)生概念漂移時的響應機制。在算法中，加入了滑動窗口W，當新樣本到達時，將其加入滑動窗口?；瑒哟翱诘娜蝿帐钱斢行聵颖镜竭_時，靠增加決策樹相應節(jié)點中的計數(shù)來回應新樣本特性。與此同時，減少舊樣本或過時樣本中相應的計數(shù)來維持一個最新的分類模型，而不是一有新樣本到達就創(chuàng)建一個新模型。(3)優(yōu)化后的算法中對滑動窗口進行了改進，對每個數(shù)據(jù)流樣本引入1個影響因子0，1。

10、值的作用是用來判斷決策樹的分類效用，并根據(jù)其取值的不同來影響滑動窗口中樣本的計數(shù)值，進而對滑動窗口的大小進行動態(tài)調(diào)整。在改進的滑動窗口中，對流過樣本的計數(shù)則基于影響因子的計數(shù)nijk。當決策樹中，某個樣本分類出現(xiàn)偏差時。該樣本在滑動窗口中的影響因子將在01的范圍內(nèi)，趨于0的程度正比于偏差節(jié)點與根節(jié)點的距離，可以用樹深z(出現(xiàn)偏差的層數(shù))來表示，即l。相反，當實際分類為正確分類時，=1。在滑動窗口中設定1個閾值(如0.5)，設W為滑動窗口中的樣本計數(shù)，W0，nijk，并規(guī)定當滿足：說明發(fā)生明顯概念漂移，鎖定出錯節(jié)點，構造替代子樹，并縮小滑動窗口的大小，直到下式成立；成立，并至少在T(人為界定)個

11、窗口周期內(nèi)保持穩(wěn)定，此時以W2增量遞歸擴大滑動窗口的大小，直到到達式(2)的臨界點時停止。(4)優(yōu)化后的算法將根據(jù)滑動窗口中有效樣本的數(shù)量來判斷分裂的有效性，即：若式(2)滿足，將重新計算在滑動窗口出現(xiàn)嚴重分裂偏差的節(jié)點中各屬性的模糊信息增益。若當內(nèi)部某節(jié)點在向下分類且滑動窗口中相應樣本點的影響因子較前一樣本點快速趨于0時，說明在對該樣本點進行分類時發(fā)生了概念漂移。這說明該節(jié)點的屬性測試出現(xiàn)了偏差，此時將有1棵替代子樹產(chǎn)生。若一新樣本屬性Xnew的模糊信息增益高于當前的分裂屬性Xcurr,則優(yōu)化后的算法將在相應節(jié)點處以屬性Xnew為根節(jié)點生成1棵替代子樹。(5)對屬性分裂效用的判斷，將改進VF

12、DT算法中的方法。使用模糊信息增益的方法可周期性地檢測最佳分裂屬性。由于現(xiàn)實網(wǎng)絡數(shù)據(jù)流中存在大量的噪聲數(shù)據(jù)或非確定信息，即便是對于某些離散屬性字段，采用傳統(tǒng)的陡峭屬性分裂方法也會導致分類界限不清晰。因此，改進后的算法，對于離散屬性和連續(xù)屬性都采用模糊信息增益作為屬性選擇度量。(6)替代子樹生長過程控制。為提高內(nèi)存利用率，替代子樹也需要控制其規(guī)模，并進行適當剪枝。剪枝的判斷標準以原子樹與替代子樹間分類的準確度增量大小為依據(jù)。優(yōu)化后的算法規(guī)定，若替代子樹滿足式(5)，將對其保留；否則，將刪除該替代子樹。式中：i為原樹和替代樹中的節(jié)點編號；為替代子樹保留的閾值。式(5)中，準確度可用該節(jié)點正確分類樣

13、本數(shù)與流經(jīng)該節(jié)點總樣本之比來定義，即：2.2 優(yōu)化流程如圖優(yōu)化流程如圖1所示。3優(yōu)化算法驗證由于本文研究的是數(shù)據(jù)流環(huán)境下的挖掘算法，為了驗證算法的有效性，必須對靜態(tài)數(shù)據(jù)集進行動態(tài)化處理。根據(jù)流數(shù)據(jù)區(qū)別于靜態(tài)數(shù)據(jù)的潛在無限、動態(tài)變化，以及對流數(shù)據(jù)的處理單遍掃描、實時處理等特點及要求進行動態(tài)處理。另外，由于在網(wǎng)絡傳輸過程中傳輸數(shù)據(jù)將受到自然環(huán)境和電磁環(huán)境的干擾，因此在實驗中將向每組實驗數(shù)據(jù)加入5的噪聲數(shù)據(jù)。在實際操作中，從數(shù)據(jù)集中隨機順序抽取100萬條樣本作為測試數(shù)據(jù)，初始屬性數(shù)為5，每增加10個屬性檢測1次結(jié)果，經(jīng)Matlab仿真后的效果圖如圖2所示，圖中標出了隨著用于分類的屬性增多，概念漂移的變化情況。4 結(jié) 語改進算法引入了滑動窗*術，滑動窗口中的所有樣本都可以全部放入內(nèi)存，并通過窗口機制來實時判斷系統(tǒng)對外圍數(shù)據(jù)的分類效果。因此，其效率與樣本總數(shù)無關。另外，滑動窗口的引入也使得改進系統(tǒng)所生成的分類模型始終與當前情況相適應，改善了概念漂移對前面分類模型的影響。另