基于網(wǎng)格和密度的數(shù)據(jù)流聚類方法研究.pdf

1、隨著硬件技術(shù)的不斷發(fā)展，人們遇到了大量無法利用數(shù)據(jù)庫進行存儲的海量數(shù)據(jù)。這些數(shù)據(jù)數(shù)量非常巨大，并且產(chǎn)生速度很快。為了對這些數(shù)據(jù)進行有效處理，人們提出了數(shù)據(jù)流數(shù)據(jù)模型。作為數(shù)據(jù)挖掘在新環(huán)境的延伸，面向數(shù)據(jù)流的數(shù)據(jù)挖掘(簡稱數(shù)據(jù)流挖掘)問題已成為當(dāng)前國內(nèi)外研究的焦點，而數(shù)據(jù)流聚類方法則是數(shù)據(jù)流挖掘的一個重要研究方向。 本文的研究目標(biāo)是以研究傳統(tǒng)聚類方法為基礎(chǔ)，通過對傳統(tǒng)方法的改進，實現(xiàn)對數(shù)據(jù)流的聚類處理。通過研究，發(fā)現(xiàn)基于網(wǎng)格和密度

2、的聚類方法具有很多適用于處理數(shù)據(jù)流的特征，有利于實現(xiàn)對數(shù)據(jù)流的聚類處理。因此，本文在對基于網(wǎng)格和密度的傳統(tǒng)聚類方法進行研究與改進的基礎(chǔ)上，從聚類過程所處理數(shù)據(jù)集合的動態(tài)性角度出發(fā)，將基于網(wǎng)格和密度的數(shù)據(jù)流聚類方法分類為靜態(tài)方法和動態(tài)方法，對其進行了一系列研究。 圍繞著數(shù)據(jù)流聚類問題，論文主要做了以下四方面的理論研究及應(yīng)用工作： 1．對基于網(wǎng)格和密度的數(shù)據(jù)流靜態(tài)聚類方法進行了討論，通過對傳統(tǒng)的基于網(wǎng)格和密度的聚類方法進行分

3、析與改進，提出了一種新的網(wǎng)格單元密度計算方法。研究發(fā)現(xiàn)，已有方法基本使用數(shù)據(jù)點計數(shù)方式計算網(wǎng)格單元的密度。這種方法會造成數(shù)據(jù)點對其周圍空間影響信息(innuence)的部分丟失，容易導(dǎo)致同屬一類的相鄰數(shù)據(jù)點被分配到不同的數(shù)據(jù)類中。針對此問題，提出了“貢獻度”概念?！柏暙I度”即是指在網(wǎng)格化的特征空間中，數(shù)據(jù)點對相鄰網(wǎng)格單元(即數(shù)據(jù)點的周圍空間)的影響程度。在此基礎(chǔ)上，提出了一種新的網(wǎng)格單元密度計算方法。實驗結(jié)果證明，與利用數(shù)據(jù)對象個數(shù)計算

4、網(wǎng)格單元密度的方法相比，這種方法能夠有效減少數(shù)據(jù)點對周圍空間影響信息的丟失。 2．針對已有的基于網(wǎng)格和密度的聚類方法在稠密單元判定方式以及聚類生成過程方面的不足進行了改進，最終提出了一種新的基于網(wǎng)格和密度的微粒群混合聚類方法?，F(xiàn)有方法基本使用單一閾值來判定稠密網(wǎng)格單元。這種方法限制了對聚類數(shù)據(jù)與噪音數(shù)據(jù)進行區(qū)分的能力。同時，已有方法都將首個遇到的稠密單元作為聚類生成過程的起始點。這種操作對生成的數(shù)據(jù)類缺乏選擇性，使數(shù)據(jù)類的生成順

5、序具有不確定性，進而影響對結(jié)果的可控性。針對這些問題，使用了新的參數(shù)一“核心單元密度下限”。此參數(shù)限定了聚類中密度極大值的最小允許取值，對能夠生成的聚類進行了限制，增強了區(qū)分聚類數(shù)據(jù)和噪音數(shù)據(jù)的能力。同時，通過將微粒群算法引入聚類過程，使得數(shù)據(jù)類能夠根據(jù)本身的密度極大值有序生成，解決了聚類生成順序的不確定性問題。最終，提出了基于網(wǎng)格和密度的微粒群混合聚類方法(CGDP)。 3．討論了動態(tài)的網(wǎng)格空間環(huán)境下對聚類進行追蹤的方法，提出

6、了動態(tài)環(huán)境下改進的自適應(yīng)微粒群算法。通過將網(wǎng)格單元密度轉(zhuǎn)化評估函數(shù)取值的方式，把對聚類密度極值的搜索問題轉(zhuǎn)化為優(yōu)化問題，然后利用微粒群算法解決此優(yōu)化問題。針對數(shù)據(jù)流的動態(tài)性特征，分析了已有的動態(tài)環(huán)境下微粒群算法，發(fā)現(xiàn)已有方法的環(huán)境變化檢測能力仍然存在不足，具體表現(xiàn)為微粒種群容易停滯在動態(tài)環(huán)境中靜止的局部極點，進而失去對其他區(qū)域中全局極點的追蹤能力。針對此問題，使用“活性因數(shù)”概念及分布式處理模式，解決了微粒種群在動態(tài)環(huán)境中的停滯問題。進

7、一步的，提出了動態(tài)環(huán)境下改進的自適應(yīng)微粒群算法(IAPSO)。實驗證明，該方法能夠適應(yīng)更多類型的復(fù)雜動態(tài)環(huán)境，具有更為普遍的實際意義，為論文對數(shù)據(jù)流聚類方法的研究提供了技術(shù)支撐。 4．以入侵檢測為代表的具體數(shù)據(jù)流環(huán)境為研究對象，對基于網(wǎng)格和密度的數(shù)據(jù)流動態(tài)聚類方法進行了研究，提出了數(shù)據(jù)流中孤立點識別方法。在此類數(shù)據(jù)流環(huán)境中，可以認(rèn)為只存在一個主要聚類，并且與其他數(shù)據(jù)相比，屬于主要聚類的數(shù)據(jù)具有相對更高的密集程度。這種環(huán)境的基本需

8、求就是判斷新出現(xiàn)的數(shù)據(jù)對象是否屬于主要聚類。針對這種情況，首先擴展了“孤立點”的含義，將不屬于主要聚類的數(shù)據(jù)對象定義為相對于主要聚類而言的“孤立點”。然后，將本文的前三項工作成果進行綜合，提出了一種面向數(shù)據(jù)流的動態(tài)聚類方法一數(shù)據(jù)流中孤立點識別方法(ODODS)。設(shè)計并實現(xiàn)了數(shù)據(jù)流分析原型系統(tǒng)，并在此基礎(chǔ)上，以入侵檢測的標(biāo)準(zhǔn)測試數(shù)據(jù)為基準(zhǔn)進行實驗，以滿足具體數(shù)據(jù)流環(huán)境的應(yīng)用需求為目標(biāo)，通過與以往基于聚類的入侵檢測方法進行結(jié)果對比，說明了O