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

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

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

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