多數(shù)據(jù)流頻繁項(xiàng)集挖掘算法研究.pdf

1、隨著互聯(lián)網(wǎng)技術(shù)在眾多領(lǐng)域飛速地發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)的存在形式也呈現(xiàn)出多樣化的趨勢(shì)。其中，數(shù)據(jù)流作為一種新型的數(shù)據(jù)形式已在眾多應(yīng)用領(lǐng)域廣泛地出現(xiàn)。例如，傳感器網(wǎng)絡(luò)環(huán)境中的數(shù)據(jù)、金融應(yīng)用中的財(cái)務(wù)數(shù)據(jù)和GPS定位系統(tǒng)所獲取的地理位置等數(shù)據(jù)。面對(duì)無(wú)限、連續(xù)和高速的海量數(shù)據(jù)，傳統(tǒng)的數(shù)據(jù)挖掘技術(shù)難以直接應(yīng)用于發(fā)現(xiàn)海量數(shù)據(jù)流中的有效信息。因此，數(shù)據(jù)流挖掘問(wèn)題具有重要的研究意義。本文將多數(shù)據(jù)流頻繁項(xiàng)集挖掘算法作為研究對(duì)象。首先，闡述了課題的研究背景以及研究意

2、義，同時(shí)概括總結(jié)了國(guó)內(nèi)外關(guān)于該課題的研究現(xiàn)狀。其次，闡述了在數(shù)據(jù)處理過(guò)程中所應(yīng)用的相關(guān)技術(shù)。最后，提出了兩種基于多數(shù)據(jù)流環(huán)境的頻繁項(xiàng)集挖掘算法。
　　本研究主要內(nèi)容包括：⑴研究了多數(shù)據(jù)流頻繁項(xiàng)集挖掘算法的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)了一種基于FP-Tree的壓縮頻繁模式樹(shù)。本文對(duì)數(shù)據(jù)流的特點(diǎn)和表現(xiàn)形式進(jìn)行了深入地分析研究，設(shè)計(jì)了一種基于字典序列的前綴樹(shù)存儲(chǔ)結(jié)構(gòu)，并在該結(jié)構(gòu)中引入了對(duì)數(shù)傾斜時(shí)間窗口模型。該窗口模型能夠增量地更新、保留頻繁項(xiàng)集的

3、計(jì)數(shù)值，在一定程度上提高了內(nèi)存空間的利用率以及算法的空間復(fù)雜度。⑵研究了多數(shù)據(jù)流協(xié)同頻繁項(xiàng)集挖掘問(wèn)題，改進(jìn)了一種基于滑動(dòng)窗口模型的多數(shù)據(jù)流協(xié)同頻繁項(xiàng)集挖掘算法。本文引入了多數(shù)據(jù)流協(xié)同頻繁項(xiàng)集挖掘問(wèn)題，多數(shù)據(jù)流協(xié)同頻繁項(xiàng)集是指一組對(duì)象在很短的時(shí)間內(nèi)以伴隨的狀態(tài)頻繁地出現(xiàn)在一條數(shù)據(jù)流或多條數(shù)據(jù)流中。首先，通過(guò)基于字節(jié)序列的滑動(dòng)窗口挖掘算法發(fā)現(xiàn)數(shù)據(jù)流中的潛在頻繁項(xiàng)集和頻繁項(xiàng)集；其次，構(gòu)建頻繁模式樹(shù)用以存儲(chǔ)多數(shù)據(jù)流中的潛在頻繁項(xiàng)集和頻繁項(xiàng)集，并

4、增量地更新樹(shù)結(jié)構(gòu)中對(duì)數(shù)傾斜時(shí)間表內(nèi)對(duì)應(yīng)項(xiàng)集出現(xiàn)的頻數(shù)；最后，通過(guò)匯總分析得出多數(shù)據(jù)流中的協(xié)同頻繁項(xiàng)集。⑶研究了分布式環(huán)境中的多數(shù)據(jù)流協(xié)同頻繁項(xiàng)集挖掘算法，將多數(shù)據(jù)流協(xié)同頻繁項(xiàng)集挖掘算法并行化計(jì)算。在當(dāng)前的大數(shù)據(jù)背景下，數(shù)據(jù)流的規(guī)模呈現(xiàn)急劇增長(zhǎng)的趨勢(shì)，其到達(dá)速度非常快且對(duì)處理結(jié)果的實(shí)時(shí)性要求非常高。單個(gè)計(jì)算節(jié)點(diǎn)的計(jì)算能力難以承受規(guī)模如此巨大的數(shù)據(jù)。因此，傳統(tǒng)的集中式頻繁項(xiàng)集挖掘算法無(wú)法應(yīng)對(duì)規(guī)模日益劇增的數(shù)據(jù)流。為了解決這一問(wèn)題，本文采用了