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

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

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

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

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