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

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

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

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

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

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

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

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