流數(shù)據(jù)的頻繁項挖掘及聚類的關(guān)鍵技術(shù)研究.pdf

1、隨著信息技術(shù)的快速發(fā)展,流式數(shù)據(jù)以不同方式出現(xiàn)在了眾多領(lǐng)域的應(yīng)用之中。包括網(wǎng)絡(luò)流量的監(jiān)測、金融應(yīng)用、通信數(shù)據(jù)管理、網(wǎng)絡(luò)安全監(jiān)控、傳感器網(wǎng)絡(luò)等等。在這些應(yīng)用中,對新型的流數(shù)據(jù)形式以及相關(guān)技術(shù)進(jìn)行研究顯得非常重要。因此,數(shù)據(jù)流上的數(shù)據(jù)挖掘成為當(dāng)前數(shù)據(jù)挖掘領(lǐng)域的研究熱點。
　　 當(dāng)前對于數(shù)據(jù)流上的挖掘主要集中在:頻繁項(集)挖掘、聚類分析、分類、異常分析等。本文分析了當(dāng)前國內(nèi)外各種流數(shù)據(jù)挖掘算法,針對數(shù)據(jù)流上的頻繁項挖掘、單條及多條數(shù)

2、據(jù)流上的聚類分析中存在的問題,提出了更為有效的算法。本論文的主要貢獻(xiàn)如下:
　　 (1)現(xiàn)有大多數(shù)的數(shù)據(jù)流頻繁項挖掘算法并沒有足夠強(qiáng)調(diào)當(dāng)前數(shù)據(jù)的重要性?；瑒哟笆且环N對最近一段時間內(nèi)的數(shù)據(jù)進(jìn)行挖掘的有效技術(shù)。因此,我們提出了一種基于滑動窗的流數(shù)據(jù)頻繁項挖掘算法。該算法采用了鏈表隊列策略得以大大簡化算法,從而提高了挖掘的效率。對于給定的閾值S、誤差ε和窗口長度n,算法可在εn的誤差內(nèi)檢測窗內(nèi)頻度超過Sn的數(shù)據(jù)流頻繁項,且其復(fù)雜度為O

3、(ε-1),處理和查詢每個數(shù)據(jù)項的時間均為O(1)。在此基礎(chǔ)上,我們還將該算法進(jìn)行了擴(kuò)展,通過參數(shù)的變化得到不同的流數(shù)據(jù)頻繁項挖掘算法,使得算法在時間和空間復(fù)雜度之間可以進(jìn)行調(diào)節(jié)。通過大量的實驗證明,本文算法比其它類似算法具有更好的精度及時空效率。
　　 (2)通過強(qiáng)調(diào)近期數(shù)據(jù)而弱化“舊”數(shù)據(jù)重要性的時間衰減模型,提出了流數(shù)據(jù)頻繁項挖掘算法FCl及其改進(jìn)的算法FC2來檢測數(shù)據(jù)流上ε-近似頻繁項。FC2算法的空間復(fù)雜度為O(ε-1

4、),每個數(shù)據(jù)項的處理時間為O(1)。通過大量的實驗證明,FC2比其他類似方法有較高的正確率,較快的處理速度以及較少的內(nèi)存需求。接著,提出了一種更加簡潔快速的挖掘數(shù)據(jù)流頻繁項的λ-Count算法。算法可以在O(logλε)空間復(fù)雜度下,檢測ε-近似頻繁項,對每個數(shù)據(jù)項的處理時間為O(1)。通過大量的實驗證明,λ-Count在正確率、內(nèi)存要求和處理速度上都優(yōu)于其他類似方法。
　　 (3)大多數(shù)現(xiàn)存的實時流數(shù)據(jù)上的聚類算法如CluSt

5、ream等,都是基于k-means算法的。這些算法在挖掘任意形狀的聚類以及處理孤立點問題上都存在難度,而且這些算法需要先驗知識來確定聚類的個數(shù)七以及用戶定義的時間窗口長度。為了解決這些問題,我們提出了一種基于密度的流數(shù)據(jù)聚類算法框架D-Stream,并相繼提出了基于此框架的算法DSO和引入吸引度策略的算法DSl。通過探索衰減系數(shù)、吸引度、數(shù)據(jù)密度以及聚類結(jié)構(gòu)之間的潛在聯(lián)系,算法可以有效地生成聚類并進(jìn)行實時調(diào)整,探測并移除那些由孤立點映射

6、的奇異單元格來動態(tài)地提高系統(tǒng)的空間和時間效率。實驗結(jié)果證明,算法具有較高的質(zhì)量和效率,可以準(zhǔn)確地反映實時數(shù)據(jù)流的進(jìn)化過程。
　　 (4)多數(shù)據(jù)流聚類的研究通常都是利用歐幾里德距離來衡量數(shù)據(jù)流間的相似性。而歐幾里德距離具有很大的局限性,它忽略了數(shù)據(jù)流的變化趨勢和序列模式。而對用戶來說,這些信息往往更加重要。為此,我們提出基于Kendall相關(guān)系數(shù)的多數(shù)據(jù)流聚類算法。該算法利用AU統(tǒng)計量將多數(shù)據(jù)流的原始數(shù)據(jù)快速壓縮成一個統(tǒng)計概要。根

7、據(jù)這些統(tǒng)計概要可增量式地計算Kendall相關(guān)系數(shù)來衡量數(shù)據(jù)間的相似度。我們還提出了一種動態(tài)的k-means算法來生成聚類結(jié)果。動態(tài)的k-means算法可動態(tài)、實時地調(diào)整聚類數(shù)目,及時檢測數(shù)據(jù)流的發(fā)展變化。算法被應(yīng)用到按照用戶要求的聚類問題(COD),使用戶可在任意時間區(qū)間上查詢聚類結(jié)果。通過一種合理的時間片斷劃分機(jī)制,可使用戶指定的任意時間區(qū)間都可以由這些時間片斷組合而成。實驗結(jié)果證明,算法比其他類似方法具有更好的聚類質(zhì)量、速度和穩(wěn)定