分布式序列模式挖掘算法研究.pdf

1、目前信息主導(dǎo)的時(shí)代，海量數(shù)據(jù)存儲(chǔ)在數(shù)據(jù)庫(kù)或者數(shù)據(jù)倉(cāng)庫(kù)中。面對(duì)這種“信息爆炸”的現(xiàn)實(shí)，如何從海量數(shù)據(jù)中提取有價(jià)值的信息已顯得尤為重要。數(shù)據(jù)挖掘技術(shù)的出現(xiàn)和發(fā)展為人們解決了這一難題。所謂數(shù)據(jù)挖掘技術(shù)是利用各種分析工具從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的實(shí)際應(yīng)用數(shù)據(jù)中，提取潛在有用的信息和知識(shí)的過(guò)程。 在本文中，我們對(duì)序列模式挖掘技術(shù)做了深入研究。序列模式挖掘是數(shù)據(jù)挖掘研究的一個(gè)重要課題，挖掘基于時(shí)間或者其他順序出現(xiàn)頻率高的模

2、式，是對(duì)關(guān)聯(lián)規(guī)則挖掘的進(jìn)一步推廣，但克服了關(guān)聯(lián)規(guī)則中不能反映事件在時(shí)間順序上的前后相關(guān)性。序列模式挖掘技術(shù)已在顧客購(gòu)買行為的分析、網(wǎng)絡(luò)訪問(wèn)模式分析、科學(xué)實(shí)驗(yàn)的分析、疾病治療的早期診斷、自然災(zāi)害的預(yù)測(cè)、DNA序列模式的分析等方面廣泛應(yīng)用。 在研究現(xiàn)有的單機(jī)和分布式序列模式挖掘算法的基礎(chǔ)上，本文圍繞著單機(jī)下基于位圖序列模式挖掘、分布式序列模式挖掘以及分布式多維序列模式的近似挖掘等幾方面做了深入研究，主要?jiǎng)?chuàng)新點(diǎn)如下： 1)基于

3、傳統(tǒng)序列模式挖掘方法不能有效地解決候選序列費(fèi)時(shí)難題，本文提出一種基于位圖的序列模式挖掘方法SMBR(sequential patterns mining based on bitmap representation)。SMBR算法采用一種簡(jiǎn)化的位圖表示結(jié)構(gòu)表示數(shù)據(jù)庫(kù)的方法。該方法首先由序列擴(kuò)展和項(xiàng)擴(kuò)展產(chǎn)生候選序列，然后通過(guò)原序列位圖和被擴(kuò)展項(xiàng)位圖位置快速運(yùn)算生成頻繁序列，有效地獲得序列模式。 2)由于分布式環(huán)境下挖掘全局序列模式

4、常常產(chǎn)生過(guò)多候選序列，加大了網(wǎng)絡(luò)通信代價(jià)。為此提出一種基于分布式環(huán)境下的挖掘全局序列模式算法-FMGSP(fast mining of global sequential pattern)。FMGSP算法將各站點(diǎn)得到的局部序列模式壓縮到一種語(yǔ)法序列樹(shù)上，避免了重復(fù)的序列前綴傳輸；基于合并樹(shù)中結(jié)點(diǎn)序列規(guī)則、簡(jiǎn)單的特點(diǎn)，提出一種I／S-E(Item Extension and Sequence Extension)剪枝策略，有效地約減了候選

5、序列，減少了網(wǎng)絡(luò)傳輸量，從而快速生成全局序列模式。 3)提出一種多維序列模式近似挖掘算法AMSP(Approximate Mining of Global Multidimensional Sequential Patterns)，以解決分布式環(huán)境中大型數(shù)據(jù)庫(kù)中多維序列模式挖掘問(wèn)題。該方法不同于傳統(tǒng)的分布式多維序列模式挖掘方法，具備較好的伸縮性。首先將維度信息嵌入相應(yīng)序列中，使多維序列模式挖掘轉(zhuǎn)化為序列模式挖掘；然后在各分站點(diǎn)對(duì)