動態(tài)數(shù)據(jù)流挖掘關(guān)鍵技術(shù)研究.pdf

1、現(xiàn)實世界因計算機廣泛應(yīng)用而不斷產(chǎn)生的數(shù)據(jù)給在線數(shù)據(jù)處理和知識獲取帶來了新的挑戰(zhàn)。諸多應(yīng)用包括國家安全、普適計算、工業(yè)質(zhì)量監(jiān)測系統(tǒng)、通信和計算機網(wǎng)絡(luò)等都需要在線監(jiān)測和分析。而在這些應(yīng)用中，由單個或多個數(shù)據(jù)源并且以空前的速度產(chǎn)生的大量的數(shù)據(jù)即為數(shù)據(jù)流。由于數(shù)據(jù)流本身的特點，如不間斷性、數(shù)據(jù)分布的動態(tài)性和數(shù)據(jù)到達速率的波動性等，數(shù)據(jù)的大小可能趨于無窮而且數(shù)據(jù)也是不斷變化的，因此如何及時地從新到達的數(shù)據(jù)中檢測出有用的模式對實時決策分析和異常預(yù)警

2、至關(guān)重要。
　　本文首先綜述了數(shù)據(jù)流領(lǐng)域的最新進展，分析得知在該領(lǐng)域研究的問題往往與分類相關(guān)。決策樹算法是最先被運用到數(shù)據(jù)流中的分類算法之一。最早的數(shù)據(jù)流決策樹學(xué)習(xí)方法是以Hoeffding邊界作為節(jié)點的劃分準則。Hoeffding邊界由于其概率分布的獨立性而得到廣泛關(guān)注，在其分母（當前觀察的樣本數(shù)量）較大時結(jié)果可收斂。事實上也有相對于Hoeffding不等式來說更加嚴格的集中不等式。Bernstein和Benett不等式是非獨立

3、分布的，因為他們包含變化項。本文使用了Bernstein邊界代替Hoeffding邊界來進行決策樹學(xué)習(xí)EBT，結(jié)果表明其準確度更高，計算耗費更低，而且魯棒性更強。
　　多數(shù)現(xiàn)有的分類技術(shù)都假設(shè)用于訓(xùn)練分類器的已標記數(shù)據(jù)足夠大，然而這一假設(shè)不一定總是成立，原因是新型的科學(xué)與工程應(yīng)用總是以驚人的速度產(chǎn)生著不斷變化的數(shù)據(jù)。由于數(shù)據(jù)流固有的特性，新的概念將不斷產(chǎn)生。因此，分類器的訓(xùn)練通常是缺乏足夠多的已標記樣本。另一方面，對領(lǐng)域?qū)＜襾碚f，

4、人工標記所有的數(shù)據(jù)也是不現(xiàn)實的。本文提出了一種基于網(wǎng)格聚類的封裝器方法，用于標記新出現(xiàn)的訓(xùn)練數(shù)據(jù)。并在此基礎(chǔ)上提出了一種基于有限標記數(shù)據(jù)的數(shù)據(jù)流分類算法LLSC。通過實驗表明，在只有50％正確標記的訓(xùn)練集情況下，該算法也能達到和快速決策樹算法VFDT同樣的分類精度。由于LLSC算法需要利用單維網(wǎng)格的交集去確定一個特殊的網(wǎng)格，而該步驟的計算成本較大，從而導(dǎo)致LLSC存在訓(xùn)練時間較長的問題。為了進一步提高算法的分類效率，本文提出了一種改進的

5、LLSC算法LLSC+1。該算法是一個基于哈希表的網(wǎng)格識別方法，并將半監(jiān)督聚類技術(shù)引入到數(shù)據(jù)流分類中。相對于LLSC算法，改進的LLSC+1算法在保持較高的分類精度基礎(chǔ)上，有效地提高了算法的分類效率，特別是在較高維的數(shù)據(jù)上，它可以減少一半多的計算開銷。
　　最后，本文進一步修改了LLSC+1中的基于網(wǎng)格的聚類策略，提出了一種以超橢球聚類形狀表示類集的聚類算法。因為現(xiàn)有多數(shù)聚類算法都使用歐氏距離矩陣，這常常導(dǎo)致得到球狀類集，而橢球相

6、對于球來說更加的靈活?；谛陆岢龅腍yCARCE算法，本文設(shè)計了一種新穎的超橢球動態(tài)數(shù)據(jù)流聚類算法HECES，其包含兩個階段:在線和離線階段。在線階段，算法是讀取多維數(shù)據(jù)流進來，并且將其放入離散密度網(wǎng)格空間。用戶定義時間窗后，橢球?qū)Ω骶W(wǎng)格進行逼近，并將初始的橢球融合在一起形成最終的聚類集。這些橢球的融合是由馬氏距離度量所決定。最后，具有較小基數(shù)的橢球?qū)⒈粍h掉。相比于DenStream和CluStream來說，HECES的結(jié)果更好。此外