序列模式挖掘的并行算法研究.pdf

1、序列模式挖掘是指從序列數(shù)據(jù)庫中發(fā)現(xiàn)相對于時間或者其它順序的高頻率序列。其最初動機是想通過在帶有交易時間屬性的交易數(shù)據(jù)庫中發(fā)現(xiàn)頻繁項目序列以發(fā)現(xiàn)一個時間段內(nèi)的客戶購買行為規(guī)律。近年來序列模式挖掘已經(jīng)成為數(shù)據(jù)挖掘的一個重要方向，其應(yīng)用范圍已不局限于交易數(shù)據(jù)庫，在DNA分析等尖端科學(xué)研究領(lǐng)域、Web訪問等新型應(yīng)用數(shù)據(jù)源等眾多方面都得到了針對性研究。 文中結(jié)合R.Agrawal和R.Srikant提出的序列模式挖掘的有關(guān)定義和R.Wil

2、le提出的概念格理論，提出了頻繁概念的定義；根據(jù)序列模式并行挖掘的需要提出了搜索空間劃分理論，其中包括搜索空間、子搜索空間、等價子搜索空間和最大子搜索空間的定義。 序列模式挖掘的數(shù)據(jù)有如下特點：數(shù)據(jù)量大，數(shù)據(jù)分布存儲。已有的大部分序列模式挖掘算法沒有綜合考慮到數(shù)據(jù)的上述特點。本文針對序列模式挖掘數(shù)據(jù)的這些特點，結(jié)合并行理論，提出了一個分布式并行算法SPP(Sequential Pattern Parallel)。本算法遵循模式縮

3、減的原則，利用分治策略實現(xiàn)并行操作，在每臺處理器上運用搜索空間劃分理論和頻繁概念構(gòu)造頻繁項集，運用圖深度優(yōu)先搜索方法構(gòu)造頻繁序列。算法只需掃描數(shù)據(jù)庫兩遍，不需要生成候選序列，大大減少了數(shù)據(jù)庫訪問時間，提高了序列模式挖掘的效率。不過本文采用是靜態(tài)負(fù)載平衡，還有待改進。 基于自己設(shè)計的隨機數(shù)據(jù)生成程序和不同的消息結(jié)構(gòu)，本文在具體的并行環(huán)境中模擬了算法SPP，并在單機中實現(xiàn)了AprioriAll算法。實驗證明，相比于AprioriAl