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

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

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

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

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

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