序列模式挖掘綜述
2008-12-31 00:00:00陳卓楊炳儒宋威宋澤鋒
計算機應用研究 2008年7期
摘 要：綜述了序列模式挖掘的研究狀況。首先介紹了序列模式挖掘背景與相關概念；其次總結了序列模式挖掘的一般方法，介紹并分析了最具代表性的序列模式挖掘算法；最后展望序列模式挖掘的研究方向。便于研究者對已有算法進行改進，提出具有更好性能的新的序列模式挖掘算法。
關鍵詞：數(shù)據(jù)挖掘；序列模式；周期模式；增量式挖掘
中圖分類號：TP311 文獻標志碼：A
文章編號：1001-3695(2008)07-1960-04
Survey of sequential pattern mining
CHEN Zhuo，YANG Bingru，SONG Wei，SONG Zefeng
（School of Information Engineering， Beijing University of Science Technology， Beijing 100083， China）
Abstract:This paper provided a review of the research of sequential pattern mining. Firstly，introduced the background and context.Secondly，summarized the general methods of sequence pattern mining，introduced and analyzedthe most representative algorithm to provide a basis for improving old algorithms or developing new effective ones. Finally，discussed some future research trends on this area.
Key words:data mining；sequential pattern；periodic pattern；incremental mining
數(shù)據(jù)挖掘作為知識發(fā)現(xiàn)的核心步驟，旨在從海量數(shù)據(jù)中提取有效的、新穎的、潛在有用的、易被理解的知識。序列模式挖掘（sequential pattern mining）是數(shù)據(jù)挖掘中非常重要的一個研究領域，最早是由Rakesh Agrawal和Ramakrishnan Srikant在針對超市中購物籃數(shù)據(jù)的分析提出來的。序列模式挖掘是要找出序列數(shù)據(jù)庫中所有超過最小支持度閾值的序列模式[1]。它有著廣泛的應用領域：商業(yè)組織利用序列模式挖掘去研究客戶購買行為模式特征、計算生物學中序列模式挖掘用來分析不同氨基酸突變模式、用戶Web訪問模式預測以及DNA序列分析和譜分析。序列模式挖掘與關聯(lián)規(guī)則挖掘在許多方面相似，但它更關心數(shù)據(jù)之間順序的關聯(lián)性。
1 序列模式挖掘任務定義
基本概念：
定義1 事務數(shù)據(jù)庫（transaction database）：以超市數(shù)據(jù)為例來說明，即由顧客交易記錄組成的數(shù)據(jù)庫。Custom_ID、Transaction_Time、Itemset分別代表顧客標志、交易時間和交易物品集合。
定義2 項集（itemset）:各個項（item）組成的集合。
定義3 序列（sequence）：不同項集的有序排列。序列S可以表示為S=〈s1，s2，…，sn〉。其中：sj(1≤j≤n)為項集，也稱為序列S的元素。
定義4 序列的元素（element）：表示為(x1，x2，…，xn)。其中：xk(1≤k≤m)為不同的項。
定義5 序列長度：一個序列包含的所有項集的個數(shù)，長度為1的序列記為1序列。
定義6 序列的包含：設存在兩個序列α，β。其中：α=〈a1，a2，…，an〉，β=〈b1，b2，…，bn〉。如果存在整數(shù)1≤j1＜j2＜…＜jn≤m，使得a1bj1，a2bj2，…，anbjn，則稱序列α是β的子序列，又稱β序列包含α，記為αβ。
定義7 支持數(shù):序列α在序列數(shù)據(jù)庫S的支持數(shù)為序列數(shù)據(jù)庫S中包含α的序列個數(shù)。
定義8 支持度：序列的支持度是一個預先設定的閾值。
定義9 頻繁序列:給定最小支持度閾值，如果序列α在序列數(shù)據(jù)庫中的支持數(shù)不低于該閾值，則稱序列α為頻繁序列。
定義10 序列模式:最大的頻繁序列稱為序列模式，最大序列就是不被其他任何序列所包含的序列。
Agrawal等人[1]將序列模式挖掘定義為在序列數(shù)據(jù)庫中挖掘那些支持數(shù)超過預先定義支持度的序列模式的過程。
2 序列模式挖掘方法
2．1 基本序列模式挖掘
大多數(shù)早期序列模式挖掘算法都是基于Agrawal提出的關聯(lián)規(guī)則挖掘算法Apriori，它的特性是頻繁模式的任何子模式都是頻繁的。基于這個啟發(fā)，研究者提出一系列類Apriori算法，如AprioriAll、AprioriSome、DynamicSome。Srikant等人[2]提出了GSP（generalized sequential pattern）方法。Zaki[3]提出了SPADE方法。這兩個方法同樣是基于Apriori的。隨后學者們又提出了一系列基于數(shù)據(jù)投影的算法，它們包括韓家煒在2000年提出的FreeSpan和Pei在2001年提出的PrefixSpan。Han于2004年提出了一種結合了圖模式生長和頻繁計數(shù)，形成了結構模式挖掘的算法gSpan。Lin和Lee于2002年提出的 MEMISP算法則是基于內(nèi)存索引的。Garofalakis等人通過利用正則表達式約束方法提出了SPIRIT算法。
2．1．1 類Apriori算法：AprioriAll、AprioriSome、DynamicSome
文獻[1]中提出的類Apriori序列模式挖掘算法是經(jīng)典的關聯(lián)規(guī)則挖掘算法Apriori算法的變形。它將序列模式挖掘分為五個階段。假定事務數(shù)據(jù)庫有三個屬性：顧客ID、交易時間和購買商品。第一階段為排序階段，原始事務數(shù)據(jù)庫進行索引，顧客ID是主鍵，交易時間是輔助鍵，結果是顧客序列的集合。第二階段為頻繁項集階段，即找出所有的頻繁項集，每個大項集對應著一個頻繁1序列。第三階段為轉(zhuǎn)換階段，將原始數(shù)據(jù)庫中的顧客序列轉(zhuǎn)換為它們相應的頻繁項集。第四階段找出所有的頻繁序列。第五階段為最大化階段，是從頻繁序列集合中找出最大序列集即頻繁模式集。
算法AprioriAll與Apriori類似，首先遍歷數(shù)據(jù)生產(chǎn)候選序列并利用Apriori的特性進行剪枝來得到頻繁序列。每次遍歷時通過連接上一次得到頻繁序列來生成新的長度加1的候選序列。然后對每個候選序列進行掃描，按照最小支持度來確定哪些序列是頻繁序列模式。它的主要缺點是遍歷數(shù)據(jù)庫次數(shù)太多，而且產(chǎn)生了太多的候選序列，因此它的效率并不高。
算法AprioriSome與AprioriAll只是在序列階段有所不同，AprioriAll是首先生成所有的頻繁序列后再在最大化序列階段刪除那些非最大的序列。AprioriSome將序列分成兩個部分分別計數(shù)：前半部分只對一定長度的序列計數(shù)；后半部分跳過已經(jīng)計數(shù)的序列。在實際過程中兩個部分是混合在一起的，以減少候選序列占用的資源。
算法DynamicSome與AprioriSome相似，僅多了一個初始化階段。在前半部分跳過對預先設定好的一定長度的候選序列的計數(shù)；后半部分的算法與AprioriSome完全相同。其效率不及AprioriAll和AprioriSome高，是由于在前半部分產(chǎn)生太多的候選。后兩者的優(yōu)點是可避免計數(shù)許多非最大序列。
2．1．2 GSP算法
文獻[2]提出的GSP算法也是一個基于Apriori的頻繁模式挖掘算法。它在以下三個方面進行改進：a）增加了時間約束，在序列的鄰近元素之間增加了最大和最小間隔。如果鄰近元素沒有介于它們兩者之間，則認為這兩個元素不是在序列中連續(xù)的元素。b）定義了一個滑動窗口來弱化事務的定義，允許項來自不同的事務，只要這些事務在指定的滑動窗口范圍內(nèi)。c）對序列中的項使用了概念層次進行分層，使得挖掘過程可以在多個概念層上進行。在GSP中候選序列的數(shù)目大大減少了，而且在挖掘過程中引入了時間約束和概念分層來生成更多知識，因此GSP相對于AprioriAll有著較好的性能。
AprioriAll中所有在數(shù)據(jù)庫中的序列都被表示為它們包含的子序列，所以很容易得到候選序列的支持數(shù)。由于在GSP中引入了最大和最小時間間隔，得到候選序列的支持數(shù)相對較困難。在此GSP在計算候選序列支持數(shù)時采用了hash樹來提高算法的效率。
由于GSP與AprioriAll一樣都需要多次遍歷數(shù)據(jù)，為了提高挖掘效率，文獻[4]中提出一種基于GSP的算法MFS（mining frequent sequence），它不需要多次遍歷數(shù)據(jù)庫。MFS 提出了一個兩階段的算法，首先挖掘樣本數(shù)據(jù)庫來獲得頻繁序列的一個粗糙評價。基于這些評價，遍歷數(shù)據(jù)庫去檢查并細化候選序列直到?jīng)]有頻繁序列再產(chǎn)生。MFS與GSP的區(qū)別是在生成候選序列的方法上：GSP每次相同長度的候選集是通過連接在前一次掃描得到的頻繁序列來產(chǎn)生的；而MFS候選集則是通過連接不同長度的所有已知頻繁序列來產(chǎn)生的。實驗結果表明MFS與GSP產(chǎn)生相同的頻繁序列集合，但在降低I/O消耗方面要比GSP高效。
此外，文獻[5]介紹了一個通用的序列模式挖掘框架。它將不同的約束，如結構、時間、項以及概念層次等都集成到一個統(tǒng)一的系統(tǒng)中，而且也提出了相應的序列模式計算方法和閾值的設置方法。
2．1．3 PrefixSpan 算法
文獻[6]提出的PrefixSpan算法是一種使用數(shù)據(jù)庫投影技術的序列模式挖掘算法，其性能優(yōu)于GSP與AprioriAll，且擁有能夠處理非常大的序列數(shù)據(jù)庫的能力。PrefixSpan 主要使用數(shù)據(jù)庫投影方法來使下一次遍歷的數(shù)據(jù)庫變得更小，它不需要產(chǎn)生候選序列，只要根據(jù)它們的前綴遞歸地將后綴投影到投影數(shù)據(jù)庫中，然后對投影數(shù)據(jù)庫進行挖掘來得到頻繁序列模式。為了提高算法性能，它研究了三種投影技術：逐層投影、隔層投影以及偽投影。
逐層投影第一步是掃描序列數(shù)據(jù)庫來得到長度為1的序列，實際上也就是1頻繁序列。然后根據(jù)1頻繁序列將數(shù)據(jù)庫分為不同的部分。每一個部分是將相應的1頻繁序列作為前綴序列數(shù)據(jù)庫的投影。投影數(shù)據(jù)庫僅包含這些序列的后綴，通過遍歷投影數(shù)據(jù)庫產(chǎn)生所有以1序列模式作為前綴的2序列模式；投影數(shù)據(jù)庫再次根據(jù)2頻繁模式分成各個部分。遞歸地執(zhí)行上述步驟直到投影數(shù)據(jù)庫為空或者再沒有頻繁序列模式產(chǎn)生。
隔層投影用來減少投影數(shù)據(jù)庫的大小和數(shù)目，它首先掃描序列數(shù)據(jù)庫，產(chǎn)生所有長度為1的序列模式，再次掃描序列數(shù)據(jù)庫，構造相應的下三角矩陣來得到所有長度為2的序列模式。接下來構造長度為2的序列模式所對應的投影數(shù)據(jù)庫，對每個投影數(shù)據(jù)庫重復上面的操作，直到?jīng)]有新的序列模式產(chǎn)生為止。
當投影數(shù)據(jù)庫能夠存儲在內(nèi)存時可使用偽投影技術。事實上它并沒有構建物理投影數(shù)據(jù)庫。每一個后綴用一對指針和偏移量來表示。由于避免了復制數(shù)據(jù)庫，偽投影比其他兩種投影方法更加高效，然而它的限制是數(shù)據(jù)庫的大小必須能存儲在內(nèi)存中。
文獻[7]提出的FreeSpan同樣是基于投影數(shù)據(jù)庫的算法。其基本思想是將頻繁序列的挖掘與頻繁模式的挖掘結合起來，并投影序列數(shù)據(jù)庫以精簡搜索空間，并減少候選子序列的數(shù)目。它只需在原始數(shù)據(jù)庫進行三次掃描，基于當前已經(jīng)得到的頻繁集，遞歸地將數(shù)據(jù)庫投影到一系列較小的數(shù)據(jù)庫上，在投影數(shù)據(jù)上進行子序列挖掘。這樣產(chǎn)生了較少的候選序列。文獻[8]中提出的gSpan算法結合了圖模式生長和頻繁計數(shù)，形成了有效的結構模式挖掘算法。文獻[9]中提出一種SPMDS算法通過對投影數(shù)據(jù)庫的偽投影作單項雜湊函數(shù)，檢測是否存在重復的投影，避免大量重復掃描數(shù)據(jù)庫。
2．1．4 SPADE 算法
文獻[3]提出的SPADE算法是利用格技術和簡單的連接方法來挖掘頻繁序列模式的一種高效算法。它僅需掃描三次數(shù)據(jù)庫即可挖掘出所有的頻繁序列；同時利用格技術將挖掘搜索空間分解為若干個較小的搜索空間，每個小的搜索空間可以存儲在內(nèi)存中。實驗表明，SPADE方法性能要優(yōu)于AprioriAll 和GSP。
在該算法中，序列數(shù)據(jù)庫被轉(zhuǎn)換為垂直數(shù)據(jù)庫格式，通過掃描垂直數(shù)據(jù)庫來生成1頻繁序列，第二次遍歷數(shù)據(jù)庫時生成新的垂直數(shù)據(jù)庫以及2序列，用生成的2序列來構建格，使得具有相同前綴項的序列在同一格內(nèi)，這樣格被分解為足夠小并能存入內(nèi)存中。在第三次掃描數(shù)據(jù)庫過程中，通過用時態(tài)連接的方法產(chǎn)生所有的頻繁序列。同時該算法采用廣度優(yōu)先搜索（BFS）和深度優(yōu)先搜索（DFS）策略來產(chǎn)生頻繁序列。與GSP生成候選過程一樣利用Apriori特性進行剪枝。
2．1．5 MEMISP 算法
在文獻[10]中提出的memory indexing for sequential pattern mining（MEMISP）是基于內(nèi)存索引的序列模式挖掘方法。MEMISP只需要遍歷一次或最多兩次數(shù)據(jù)庫，并且它避免生成候選序列和投影數(shù)據(jù)庫。實驗結果表明，MEMISP比GSP和PrefixSpan 要高效，而且對于數(shù)據(jù)庫大小和數(shù)據(jù)序列數(shù)目有著良好的線性可伸縮性。
對于那些能夠存儲在內(nèi)存中的數(shù)據(jù)庫，該算法首先掃描數(shù)據(jù)庫并把它寫到內(nèi)存中形成MDB（memory database），在這個過程中計算1序列的支持數(shù)來得到1頻繁序列；然后再利用1頻繁序列以及構造內(nèi)存索引來生產(chǎn)序列模式；最后用索引以及MDB根據(jù)支持度大小找到頻繁模式。循環(huán)執(zhí)行直到再沒有新的序列模式產(chǎn)生為止。
對于那些較大的不能裝入內(nèi)存的數(shù)據(jù)庫，該算法把它分解為各個能夠存儲在內(nèi)存中的部分，然后每個部分分別應用MEMISP來得到頻繁模式，整個候選序列模式從各個部分集成得到。最終的頻繁序列模式的確定需要根據(jù)實際的支持度再次遍歷數(shù)據(jù)庫。大型數(shù)據(jù)庫僅需遍歷兩次。
2．1．6 SPIRIT 算法
在文獻[11]中提出的SPIRIT(sequential pattern mining with regular expression constraints)算法是在通過正則表達式約束來挖掘用戶特定序列模式的一種挖掘算法。這種方法避免了挖掘用戶不感興趣的模式的浪費，同時也避免了挖掘那些潛在的并無用處的模式。
傳統(tǒng)的序列模式挖掘用戶參與挖掘只是給定了一個最小支持度，用戶參與對特定的問題作出經(jīng)驗判斷，此外還會產(chǎn)生大量的無用結果。SPIRIT算法是受用戶限制的挖掘，將用戶指定的正則表達式也加入到算法中，使用戶參與到模式挖掘過程中，算法本身與GSP算法非常相似，只是在其中加入了一系列能夠讀取和中斷正則表達式限制的操作。最終形成的序列模式綜合考慮了最小支持度與用戶的約束條件。針對不同的約束程度，文中形成了四種不同的算法，SPIRIT[N]、SPIRIT[L]、SPIRIT[V]、SPIRIT[R]，它們的約束程度依次增強。
2．2 多維序列模式挖掘
單維挖掘序列模式只關心一個帶有時間戳的屬性，多維序列模式的挖掘目的則是尋找不同維度屬性具有更多信息的有用模式。文獻[12]中闡述了多維序列模式挖掘的思想，并提出了三種挖掘多維序列模式的方法，分別是SeqDim、DimSeq以及UniSeq算法。UniSeq算法將多維信息融入到序列中形成新的序列數(shù)據(jù)庫，然后按照PrefixSpan方法對新的序列數(shù)據(jù)庫進行挖掘。SeqDim算法首先挖掘原始序列的序列模式，然后對序列投影下的數(shù)據(jù)庫多維信息的模式進行挖掘。DimSeq則是首先挖掘多維信息的模式，然后再挖掘多維信息投影下的數(shù)據(jù)庫序列模式。由于通常多維序列模式的長度較短，投影數(shù)據(jù)庫僅包含那些帶頻繁序列模式的元組，多維序列模式挖掘更加高效多產(chǎn)。實驗結果表明，多數(shù)情況下SeqDim有著良好的性能；當維數(shù)較低時多維模式也較短，UniSeq較其他兩種方法高效；DimSeq在挖掘過程中許多模式并未形成多維序列模式，因此效率較低。
2．3 增量式序列模式挖掘算法
現(xiàn)實世界中序列數(shù)據(jù)集往往是實時更新的。相應地，有趣模式在多次挖掘時也會隨時間呈現(xiàn)出某種變化，已有的規(guī)則可能不再有效，而新的有趣模式還有待進一步發(fā)現(xiàn)。通常有兩種維護規(guī)則的方式：第一種方法是強更新，重新進行挖掘，用新的規(guī)則來替換所有舊的規(guī)則；第二種是弱更新，僅重新計算與增量有關的數(shù)據(jù)，替換不適用的舊規(guī)則。考慮到序列模式挖掘的復雜性，更加傾向于采用弱更新的方式。增量式序列模式挖掘關注于當數(shù)據(jù)持續(xù)增加或減少時來維護序列模式。
文獻[13]提出了一種基于GSP和一種基于MFS的增量式挖掘算法。在文獻[14]提出了一種基于SPADE的增量挖掘算法ISM。文獻[15，16]分別給出了ISE 和IUS算法。同時文獻[16]還討論了在何時需要更新序列模式。增量式序列模式挖掘定義為：給定序列數(shù)據(jù)庫，通過插入或刪除序列形成新的序列數(shù)據(jù)庫，在新的序列數(shù)據(jù)庫中尋找所有的最大頻繁序列模式。
文獻[13]中提到的GSP+與MFS+算法是基于GSP算法的增量式序列模式挖掘算法。GSP+與GPS有著相同的結構，根據(jù)在前一次掃描中生成的頻繁序列來得到候選序列；不同的是GPS+采用了不同的剪枝策略，它僅僅去遍歷更新的那部分數(shù)據(jù)庫來檢測候選序列的支持數(shù)，同時文獻給出了兩個剪枝策略的定理，基于這兩個定理的剪枝技術，減少了候選序列的數(shù)目。同樣的剪枝策略亦用于MFS+算法中，它首先將在舊的數(shù)據(jù)庫中得到頻繁序列作為新數(shù)據(jù)庫的頻繁序列集的評價。將所有可能的1序列看做候選序列，通過掃描新舊數(shù)據(jù)集能夠得到所有這些候選序列的支持數(shù)。利用最小支持度閾值，將最大頻繁序列放入集合中。在數(shù)據(jù)集上進行剪枝，并循環(huán)這個過程直到再沒有生成候選或者再沒有頻繁序列模式產(chǎn)生。
文獻[14]中提出一種基于SPADE方法的增量式序列模式挖掘算法ISM。ISM算法在數(shù)據(jù)庫更新時不僅能獲得頻繁模式，而且它提供一個與用戶交互的接口，用于修正最小支持度與包含或不包含項等的限制。ISM算法假定在舊的數(shù)據(jù)庫所有序列模式均已計算出支持數(shù)，并且這些序列的反向邊界以及支持數(shù)可用在一個格里。通過構建一個增量序列格（incremental sequence lattice，ISL）并利用其特性，為潛在的新的序列縮小了搜索空間。使用垂直數(shù)據(jù)存儲方式在建立數(shù)據(jù)結構方面的花銷要比其他大多數(shù)序列模式挖掘算法在速度上有所提高。
ISM算法僅僅考慮了增加新的序列情況，文獻[15]中同時考慮了增加新序列以及在序列中增加新后綴的情況，并提出一種新算法ISE。假定舊數(shù)據(jù)庫中最大頻繁模式的長度為k，ISE算法將挖掘過程分為兩個子問題，對于那些長度大于k的候選序列，直接應用GSP算法。而對于那些長度小于或等于k的序列進行如下操作：第一次遍歷新增數(shù)據(jù)庫，并計算每個單獨項的支持數(shù)。利用先前挖掘結果，能夠得到在舊數(shù)據(jù)庫中并不頻繁的頻繁序列集合，定義為Ldb1。通過連接Ldb1生成2候選序列進行后檢測它們是否存在于新增數(shù)據(jù)庫中。遍歷數(shù)據(jù)庫從2候選序列中得到2頻繁序列。將那些按照時間順序的L1db 的序列與相應的序列關聯(lián)起來。依次循環(huán)，直到再沒有小于等于k+1的候選序列生成。兩種剪枝技術用于優(yōu)化ISE算法，旨在利用當前信息在早期減少生成候選序列的數(shù)量。
ISE僅考慮在原始數(shù)據(jù)庫中擴展頻繁序列的后綴，而文獻[16]中提出的IUS算法同時考慮了 擴展前綴和后綴，它也像ISM算法一樣應用了反向邊界，但ISM中沒有內(nèi)存管理方法。IUS定義了反向邊界的最小約束，只有那些支持度超過這個約束的序列才能被反向邊界包含，因此IUS算法需要的內(nèi)存空間較小。
文獻[17]中提出一種IncSpan算法，引入近似頻繁序列集、逆向匹配和共享投影等新思路進行增量挖掘。在文獻[18]中提出了一種可迭代的移動序列模式挖掘及增量更新方法，該方法基于投影技術，只需要對數(shù)據(jù)庫進行一次掃描。文獻[19]中提出了分布式序列模式挖掘的思想并給出相應的算法。文獻[20]給出了序列模式圖的概念，并由此來挖掘序列模式。
2．4 周期模式挖掘
周期模式挖掘可看做序列模式挖掘的延伸，它旨在時間序列數(shù)據(jù)庫發(fā)現(xiàn)所有的再生模式。周期模式挖掘有以下三種任務：a）全周期模式挖掘，在時間序列中的每一個點都為時間序列周期模式做出貢獻。b）部分周期模式挖掘，時間序列的其中部分為周期模式做出貢獻。c）周期關聯(lián)規(guī)則挖掘，關聯(lián)規(guī)則是周期發(fā)生的事件集合。
大多數(shù)全周期模式挖掘可以用統(tǒng)計分析方法或者轉(zhuǎn)換為序列模式挖掘。部分周期模式挖掘在現(xiàn)實世界中普遍發(fā)生，因此周期模式挖掘大多數(shù)有意義的問題集中在此。部分周期模式挖掘定義為時間序列在一個時期內(nèi)或者在一個特定周期范圍內(nèi)挖掘序列所有頻繁模式。文獻[21~24]討論了部分周期模式挖掘。其中文獻[21]中韓家煒介紹了部分周期模式挖掘的難點，并提出了單周期與多周期模式的兩種挖掘算法。
單周期模式挖掘旨在對于給定周期、支持度約束和可信度約束，在時間序列中發(fā)現(xiàn)所有的部分周期模式。一種方法是將序列分割成周期片斷后直接應用傳統(tǒng)的Apriori算法來進行挖掘，使用Apriori特性來進行剪枝大序列的候選，發(fā)現(xiàn)頻繁序列的問題與在關聯(lián)規(guī)則中找到頻繁項集類似。在此算法中掃描的總數(shù)不多于周期的長度。在這個方法中最壞情況下需要的存儲空間為2F-1，F是1頻繁模式的數(shù)目。另一種方法叫做最大子模式命中集方法。在周期片斷中候選模式中的最大子模式即為命中集。整個時間序列S的命中集是所有在S中的頻繁最大子模式的集合。與Apriori算法中一樣在第一次掃描時產(chǎn)生1頻繁模式，在第二次掃描，生成每個周期片斷的命中集以及支持數(shù)，并存儲在樹結構中。序列頻繁模式從帶有計數(shù)的命中集中得到。在這個算法中僅需掃描兩次數(shù)據(jù)庫，存儲空間為min{m， 2F(xiàn)-1}，m是時間序列的周期總和。
以單周期利用基于命中集方法為原始方法，部分周期模式的多周期模式挖掘直接將最大模式命中集方法應用到序列的每一個周期。該方法由于序列中有k個循環(huán)，k為在特定范圍的周期數(shù)目，掃描次數(shù)是2×k，需要的空間為kj=1 min{mj，2Fj}。多周期模式挖掘的另外一種方法與單周期模式挖掘最大模式算法非常相似。在第一次掃描時生成所有周期的1頻繁模式和候選頻繁模式；第二次掃描時生成所有周期的命中集。
實驗證明在單周期與多周期模式挖掘中，用最大子模式命中集方法要優(yōu)于基于Apriori算法。原因是掃描時間序列數(shù)據(jù)庫的次數(shù)和所需空間存儲明顯減少，同時基于最大子模式命中集算法僅掃描兩次數(shù)據(jù)庫，而Apriori則需多次掃描數(shù)據(jù)庫，對于挖掘非常大的數(shù)據(jù)庫時基于Apriori算法需要很大的磁盤存儲空間和I/O操作 。
由于時間序列數(shù)據(jù)庫隨時變化，在文獻[22]中提出部分周期模式的增量挖掘算法。該挖掘算法結合了兩個挖掘數(shù)據(jù)庫。上述周期模式的研究焦點在于挖掘同步的周期模式，但是實際上由于存在隨機性和噪聲干擾，有一些周期模式不能被識別。文獻[23]提出時間序列數(shù)據(jù)異步周期模式挖掘，用于發(fā)現(xiàn)那些在子序列頻繁發(fā)生但可能隨干擾而變化的模式。文獻[24]中介紹在噪聲環(huán)境下的序列模式挖掘相關研究。MOWCATL(minimal occurrences with constraints and time lags)方法[25]從序列中找出周期性片段的事件相關模式，并應用于預測其他序列的類似事件。
3 結束語
近些年來，序列模式挖掘取得了長足進步，但處于發(fā)展階段，面臨著不少問題：a）序列模式挖掘過程中如何讓用戶有效參與到挖掘過程中，與相關領域知識相結合進行有指導的挖掘，避免挖掘的盲目性。b）序列模式挖掘的評價還沒有一個統(tǒng)一的標準和框架。c）閾值的設定還沒有好的方法來評判，如可信度、支持度與感興趣度。d）針對海量數(shù)據(jù)，序列模式挖掘在挖掘效率上還不高。
本文認為，以下幾個方面是序列模式挖掘今后的發(fā)展方向：將先驗知識、領域知識與計算智能算法相結合來指導挖掘過程，以縮小搜索空間，提高算法效率以及規(guī)則的興趣度；多維序列模式挖掘，尋找不同維度屬性具有更多信息的有用模式；增量式挖掘，進行規(guī)則的更新與維護；周期模式的關聯(lián)規(guī)則挖掘的高效算法；分布式序列模式挖掘以及序列模式圖的研究；設計面向非關系數(shù)據(jù)庫（面向?qū)ο髷?shù)據(jù)庫、多維數(shù)據(jù)庫、數(shù)據(jù)倉庫）的序列模式挖掘算法。
參考文獻：
［1］AGRAWAL R，SRIKANT R.Mining sequential pattern[C]//Proc of the 11th International Conference on Data Engineering.Taipei:[s.n.]，1995.
[2]SRIKANT R，AGRAWAL R.Mining sequential patterns: Generalizations and performance improvements[C]//Proc of the 5th International Conference on Extending Database Technology.Avignon:[s.n.]，1996.[3] ZAKI M J.SPADE:An efficient algorithm for mining frequent sequences[J].Machine Learning，2001，41(1):31-60.
[4]ZHANG M，KAO B，YIP C，et al.A GSPbased efficient algorithm for mining frequent sequences[C]//Proc of International Conference on Artificial Intelligence.Nevada:[s.n.]，2001.
[5]JOSHI M，KARYPIS G，KUMAR V.A universal formulation of sequential patterns[C]//Proc of the KDD’2001 Workshop on Temporal Data Mining.San Francisco:[s.n.]，2001.
[6]PEI J，HAN J.PrefixSpan:mining sequential patterns efficiently by prefixprojected pattern growth[C]//Proc of the 7th International Conference on Data Engineering.Washington DC:IEEE Computer Society，2001:215-224.
[7]HAN J，PEI J，MORTAZVIASL B，et al.FreeSpan:frequent patternprojected sequential pattern mining[C]//Proc of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM Press，2000:355-359.
[8]HAN J，PEI J，YAN X.From sequential pattern mining to structured pattern mining:a patterngrowth approach[J].Journal of Computer Science and Technology，2004，19(3):257-279.
[9]張坤，朱楊勇.無重復投影數(shù)據(jù)庫掃描的序列模式挖掘算法[J].計算機研究與發(fā)展，2007，44(1):126132.
[10]LIN Mingyen，LEE S Y.Fast discovery of sequential patterns by memory indexing[C]//Proc of the 4th International Conference on Data Warehousing and Knowledge Discovery.London，UK:SpringerVerlag，2002:150160.
[11]GAROFALAKIS M N，RASTOGI R， SHIM K.Spirit:sequential pattern mining with regular expression constraints[C]//Proc of the 25th International Conference on Very Large Databases.San Francisco，CA:Morgan Kaufmann Publishers Inc，1999:223-234.
[12]PINTO H，HAN J，PEI J，et al.Multidimensional sequential pattern mining[C]//Proc of the 10th International Conference on Information and Knowledge Management.Atlanta，New York:ACM Press，2001:81-88.
[13]ZHANG Minghua，KAO B，CHEUNG D W，et al.Efficient algorithms for incremental update of frequent sequences[C]//Proc of the PacificAsia Conference on Knowledge Discovery and Data Mining.London，UK:SpringerVerlag，2002:186197.
[14]PARTHASARATHY S，ZAKI M J， OGIHARA M，et al.Incremental and interactive sequence mining[C]//Proc of the 8th International Conference on Information and Knowledge Management.Kansas City，New York:ACM Press，1999:251-258.
[15]MASSEGLIA F，PONCELET P，TEISSEIRE M.Incremental mining of sequential patterns in large databases[J].Data and Knowledge Engineering，2003，46(1):97121.
[16]ZHENG Qingguo，XU Ke，MA Shiling，et al.The algorithms of updating sequential patterns[C]//Proc of the 5th International Workshop on High Performance Data Mining.Washington DC:[s.n.]，2002.
[17]CHENG Hong，YAN X，HAN J.IncSpan:incremental mining of sequential patterns in large database[C]//Proc of the 10th International Conference on Knowledge Discovery and Data Mining.New York:ACM Press，2004:527-532.
[18]牛興雯，楊冬青，唐世渭，等.OSAF2tree ——可迭代的移動序列模式挖掘及增量更新方法[J].計算機研究與發(fā)展，2004，41(10):17611767.
[19]鄒翔，張巍，劉洋，等.分布式序列模式發(fā)現(xiàn)算法的研究[J].軟件學報，2005，16(7):12621269.
[20]呂靜，王曉峰.序列模式圖及其構造算法[J].計算機學報，2004，27(6):782787.
[21]HAN J，DONG G，YIN Y.Efficient mining of partial periodic patterns in time series database[C]//Proc of the 15th International Conference on Data Engineering.Washington DC:IEEE Computer Society，1999.
[22]YANG J，WANG Wei，YU P S.Mining asynchronous periodic patterns in time series data[C]//Proc of the 6th International Conference on Knowledge Discovery and Data Mining.New York:ACM Press，2000:275-279.
[23]ELFEKY M G.Incremental mining of partial periodic patterns in timeseries databases[EB/OL].(2000).http://citeseer.ist.psu.edu/421296.html.
[24]BETTINI C，WANG X S，JAJODIA S.Mining temporal relationships with multiple granularities in time sequences[J].Data Engineering Bulletin，1998，21:32-38.
[25]HARMS S K，DEOGUN J S.Sequential association rule mining with time lags[J].Journal of Intelligent Information Systems，2004，22(1):7-22.
注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”
