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

1、自適應(yīng)模糊決策樹(shù)算法在數(shù)據(jù)流挖掘中的應(yīng)用朱參世，李響(空軍工程大學(xué)工程學(xué)院，陜西西安710038)0引言數(shù)據(jù)挖掘是從大量數(shù)據(jù)中“挖掘”知識(shí)，旨在從大量數(shù)據(jù)中提取隱藏的預(yù)測(cè)性信息，發(fā)掘數(shù)據(jù)間潛在的模式，找出某些被忽略的信息，作為決策的依據(jù)。在網(wǎng)絡(luò)的許多應(yīng)用中數(shù)據(jù)是以流形式存在的。傳統(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ù)流朱參世，李響(空軍工程大學(xué) 工程學(xué)院，陜西西安 710038)0引 言數(shù)據(jù)挖掘是從大量數(shù)據(jù)中“挖掘”知識(shí)，旨在從大量數(shù)據(jù)中提取隱藏的預(yù)測(cè)性信息，發(fā)掘數(shù)據(jù)

2、間潛在的模式，找出某些被忽略的信息，作為決策的依據(jù)。在網(wǎng)絡(luò)的許多應(yīng)用中數(shù)據(jù)是以流形式存在的。傳統(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算法，Han提出基于FP-growth的FP-stream算法等。數(shù)據(jù)流常用的處理與分析方法可歸納為數(shù)據(jù)流頻繁項(xiàng)集挖掘算法、分類(lèi)挖掘算法和聚類(lèi)挖掘算法。但這些算法在處

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

4、成決策樹(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的平均信息

5、增益Gain(Xa)最大，屬性Xb的平均信息增益次之，并令：若Gain，則由Hoeffding界可以保證選擇屬性X作為根節(jié)點(diǎn)的分裂屬性在概率1-下得到保證，且真正的信息增益之差GainGain-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ù)的最大深度或其他度量指

6、標(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ì)分類(lèi)決策影響最小的子節(jié)點(diǎn)所使用的空間。對(duì)于暫時(shí)失去活性的子節(jié)點(diǎn)，若后來(lái)其分類(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)化，在

7、步驟(3)中，傳統(tǒng)的Hoeffding樹(shù)算法會(huì)在每一個(gè)樣本到達(dá)時(shí)進(jìn)行一次分裂屬性測(cè)試，這將極大地影響系統(tǒng)的計(jì)算效率。VFDT系統(tǒng)引入了一個(gè)分裂屬性最小樣本數(shù)nmin(由用戶提供)，當(dāng)?shù)竭_(dá)節(jié)點(diǎn)的樣本數(shù)為nmin的整數(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ù)算法的分類(lèi)精度與單純樣本數(shù)量無(wú)關(guān)，其需要維護(hù)的惟一統(tǒng)計(jì)量是具有類(lèi)標(biāo)號(hào)yk屬性Ai值vj的計(jì)數(shù)nijk。因此，若d是屬性的個(gè)數(shù)，v是屬性值的最大個(gè)數(shù)，c是類(lèi)的個(gè)數(shù)，l是樹(shù)的最大深度，則內(nèi)存總需求為O

8、(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)行分類(lèi)時(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)分類(lèi)不準(zhǔn)，則在相應(yīng)節(jié)點(diǎn)旁派生出一顆替代子樹(shù)(Talt)。當(dāng)替代子樹(shù)生長(zhǎng)到足以對(duì)新到樣本進(jìn)行準(zhǔn)確分類(lèi)時(shí)，將替代原樹(shù)中相應(yīng)的子樹(shù)。2.1 優(yōu)化后算法的執(zhí)行過(guò)程(1)優(yōu)化后的算法核心決策樹(shù)仍然是Ho

9、effding樹(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è)最新的分類(lèi)模型，而不是一有新樣本到達(dá)就創(chuàng)建一個(gè)新模型。(3)優(yōu)化后的算法中對(duì)滑動(dòng)窗口進(jìn)行了改進(jìn)，對(duì)每個(gè)數(shù)據(jù)流樣本引入1個(gè)影響因子0，1。

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

11、窗口周期內(nèi)保持穩(wěn)定，此時(shí)以W2增量遞歸擴(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)在向下分類(lèi)且滑動(dòng)窗口中相應(yīng)樣本點(diǎn)的影響因子較前一樣本點(diǎn)快速趨于0時(shí)，說(shuō)明在對(duì)該樣本點(diǎn)進(jìn)行分類(lèi)時(shí)發(fā)生了概念漂移。這說(shuō)明該節(jié)點(diǎn)的屬性測(cè)試出現(xiàn)了偏差，此時(shí)將有1棵替代子樹(shù)產(chǎn)生。若一新樣本屬性Xnew的模糊信息增益高于當(dāng)前的分裂屬性Xcurr,則優(yōu)化后的算法將在相應(yīng)節(jié)點(diǎn)處以屬性Xnew為根節(jié)點(diǎn)生成1棵替代子樹(shù)。(5)對(duì)屬性分裂效用的判斷，將改進(jìn)VF

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

13、本數(shù)與流經(jīng)該節(jié)點(diǎn)總樣本之比來(lái)定義，即：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仿真后的效果圖如圖2所示，圖中標(biāo)出了隨著用于分類(lèi)的屬性增多，概念漂移的變化情況。4 結(jié) 語(yǔ)改進(jìn)算法引入了滑動(dòng)窗*術(shù)，滑動(dòng)窗口中的所有樣本都可以全部放入內(nèi)存，并通過(guò)窗口機(jī)制來(lái)實(shí)時(shí)判斷系統(tǒng)對(duì)外圍數(shù)據(jù)的分類(lèi)效果。因此，其效率與樣本總數(shù)無(wú)關(guān)。另外，滑動(dòng)窗口的引入也使得改進(jìn)系統(tǒng)所生成的分類(lèi)模型始終與當(dāng)前情況相適應(yīng)，改善了概念漂移對(duì)前面分類(lèi)模型的影響。另