基于位圖的閉序列模式挖掘.pdf

1、序列模式是數(shù)據(jù)挖掘研究中一個(gè)重要的研究課題，其主要研究目的是從大型時(shí)序數(shù)據(jù)庫中發(fā)現(xiàn)事件之間存在的隱藏的、有趣的序列關(guān)系。經(jīng)典序列模式挖掘算法大都致力于挖掘序列模式全集，其空間效率低。挖掘閉序列集合能在保持信息完備性的前提下，比挖掘序列模式全集更加精簡有效。本文著重對此進(jìn)行了研究，研究內(nèi)容主要包括以下幾個(gè)部分： 1.深入研究了序列模式挖掘經(jīng)典算法。主要對基于前綴投影數(shù)據(jù)庫的無候選序列生成的算法(PrefixSpan，CloSpan

2、)和基于位圖的SPAM算法進(jìn)行了研究。對這些算法做了定性分析，比較了算法的運(yùn)行效率，總結(jié)了每種算法的優(yōu)點(diǎn)及不足。 2.在對閉序列模式經(jīng)典算法CloSpan的研究基礎(chǔ)上，參考SPAM算法所采用的數(shù)據(jù)結(jié)構(gòu)，將序列數(shù)據(jù)庫用位圖來表示，設(shè)計(jì)了基于位圖的閉序列模式挖掘算法CSPBB。該算法是一個(gè)深度優(yōu)先算法，采用前綴投影方法，處理的對象是用位圖表示的序列數(shù)據(jù)庫。通過算法分析和實(shí)驗(yàn)比較可知：對于長序列模式數(shù)據(jù)，CSPBB算法在時(shí)間和空間開銷