序列模式挖掘若干問題研究.pdf

1、序列模式挖掘在Web日志挖掘、自然災害預測、DNA和蛋白質(zhì)序列模式發(fā)現(xiàn)等領域有著廣泛應用。基于頻繁模式增長的。PrefixSpan是目前性能最好的序列模式挖掘算法之一。然而在密數(shù)據(jù)集和長序列模式挖掘過程中，會出現(xiàn)大量的重復投影數(shù)據(jù)庫，使得這類算法性能下降。同時，序列數(shù)據(jù)庫往往是動態(tài)更新的，如果每次都是從原始數(shù)據(jù)庫中進行挖掘更新序列模式，將面臨巨大的搜索空間，效率低下，通過在已有的模式基礎上挖掘新的模式，可以減少挖掘原始數(shù)據(jù)庫的次數(shù)。

2、 本文針對序列模式挖掘搜索空間大，序列數(shù)據(jù)庫更新頻繁等特點，對序列模式挖掘算法及其相關算法進行了研究。主要工作成果為： 1) 給出了一種針對序列模式的壓縮表示方法，節(jié)省了基于頻繁模式增長的序列模式挖掘算法所需要的內(nèi)存空間。 2) 提出了一種序列模式挖掘算法，通過對投影數(shù)據(jù)庫的偽投影做單項雜湊函數(shù)，如。MD5等，檢查是否存在重復的投影數(shù)據(jù)庫，避免大量重復數(shù)據(jù)庫的掃描，從而生成了壓縮的前綴樹，并采用一些必要條件簡化壓縮前

3、綴樹結(jié)點的搜索。并根據(jù)壓縮前綴樹給出了一種構(gòu)造閉合序列模式的算法。 3) 證明了當前基于PrefixSpan的IrmSpan系列算法并不能挖掘出所有的序列模式，這類基于半頻繁模式的增量序列模式挖掘算法存在缺陷。并提出了一種新的增量序列模式挖掘算法，通過前綴樹來表示序列模式，然后不斷地掃描增量序列產(chǎn)生的增量集來維護這個樹的結(jié)構(gòu)，在掃描過程中通過廣度剪枝和深度剪枝算法來縮小搜索空間。然后結(jié)合壓縮前綴樹和增量剪枝策略，進一步提高增量序