周期間隙約束的序列模式挖掘研究.pdf

1、序列模式挖掘作為數(shù)據(jù)挖掘的一項(xiàng)重要研究?jī)?nèi)容，用于從各應(yīng)用領(lǐng)域的海量數(shù)據(jù)中發(fā)現(xiàn)所隱含的各種規(guī)律并從中獲取有價(jià)值的知識(shí)和信息。周期間隙約束的序列模式挖掘是一種帶有間隔約束的序列模式挖掘問(wèn)題。它要求模式的項(xiàng)與項(xiàng)之間滿(mǎn)足用戶(hù)指定的間隔約束，且間隔大小或范圍均相同，即挖掘形如p0[M,N]p1...[M,N]pj...[M,N]pm-1的頻繁模式（M和N分別表示最小和最大間隙）。與一般的序列模式挖掘問(wèn)題相比，周期間隙約束的頻繁模式更具靈活性和有效

2、性，因此周期間隙約束的序列模式挖掘成為了現(xiàn)代序列模式挖掘研究領(lǐng)域的一個(gè)重要研究方向。本文主要針對(duì)周期間隙約束的序列模式挖掘算法進(jìn)行研究，以進(jìn)一步提高頻繁模式的挖掘效率。
　　本文的主要研究?jī)?nèi)容和相關(guān)工作如下：
　　(1)總結(jié)了周期間隙約束的序列模式特點(diǎn)及一般的挖掘方法，詳細(xì)介紹并分析了已有的挖掘算法MPP、MGCS和AMin。針對(duì)已有算法所存在的缺陷，本文提出了采用不完全網(wǎng)樹(shù)結(jié)構(gòu)來(lái)計(jì)算模式支持度的方法并設(shè)計(jì)了相應(yīng)的算法INS

3、upport。
　　(2)依據(jù)算法INSupport，結(jié)合棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)提出了兩個(gè)高效的挖掘算法MAPB（Mining sequentiAl Pattern using incomplete Nettree with Breadth first search）和MAPD（Mining sequentiAl Pattern using incomplete Nettree with Depth first search）對(duì)現(xiàn)有算法

4、進(jìn)行改進(jìn)。實(shí)驗(yàn)結(jié)果表明，MAPB算法和MAPD算法較現(xiàn)有的挖掘算法在運(yùn)行時(shí)間性能上均具有大幅度地提高。其中，MAPD算法性能最佳，不僅運(yùn)行速度更快，而且空間消耗也最小，能夠?qū)荛L(zhǎng)的序列迅速地完成挖掘任務(wù)。
　　(3)詳細(xì)介紹了周期間隙約束的Top-K模式挖掘問(wèn)題及解決該問(wèn)題的方法，提出了基于MAPB的啟發(fā)式Top-K挖掘算法MAPBOK（MAPB for tOp-K）。雖然該算法不能準(zhǔn)確地得到各模式長(zhǎng)度下的前K種最頻繁模式，但當(dāng)序