基于模式增長(zhǎng)的序列模式挖掘算法的研究.pdf

1、基于模式增長(zhǎng)的序列模式挖掘算法是當(dāng)前最新的挖掘框架,其研究成果已經(jīng)被應(yīng)用于諸多領(lǐng)域,如分析購(gòu)物數(shù)據(jù),從 DNA序列中獲取重要的基因信息,從Web日志中獲取web訪問(wèn)模式等。然而對(duì)于序列較長(zhǎng),字母域較小,或者支持度閾值較小的數(shù)據(jù)集,傳統(tǒng)的基于模式增長(zhǎng)的算法需要建立大量的投影數(shù)據(jù)庫(kù),冗余計(jì)算成為了挖掘的最大瓶頸。
　　本文在對(duì)基于模式增長(zhǎng)的 PrefixSpan挖掘算法研究的基礎(chǔ)上,將樹(shù)形存儲(chǔ)結(jié)構(gòu)進(jìn)行變形,并對(duì)相同子樹(shù)進(jìn)行合并。給出了

2、一種新的數(shù)據(jù)表示方法W-PG-DAG,即基于前綴增長(zhǎng)的加權(quán)有向非循環(huán)圖。W-PG-DAG存儲(chǔ)結(jié)構(gòu)避免了前綴樹(shù)無(wú)法合并相同后綴的弱點(diǎn),對(duì)相似度較大的序列具有較高的壓縮率。
　　在PrefixSpan算法的基礎(chǔ)上,使用W-PG-DAG存儲(chǔ)結(jié)構(gòu)代替序列數(shù)據(jù)集。同時(shí)采用W-PG-DAG存儲(chǔ)結(jié)構(gòu)的節(jié)點(diǎn)共享優(yōu)點(diǎn),引進(jìn)了緩存機(jī)制,提出了改進(jìn)的挖掘算法,即 W-PG-DAGMiner算法。緩存機(jī)制完成了非頻繁序列預(yù)剪枝和中間結(jié)果重用,因此提高了挖