數(shù)據(jù)挖掘的任務是從數(shù)據(jù)中發(fā)現(xiàn)模式，模式時空一個用語言L來表示的一個表達式E，它可用來描述數(shù)據(jù)集F中數(shù)據(jù)的特性，E所描述的數(shù)據(jù)時機和F的一個子集FE。E作為一個模式要求它比數(shù)據(jù)子集FE中所有元素的描述方法簡單，在實際應用中，往往根據(jù)模式的實際作用細分為分類模式、回歸模式、時間序列模式、聚類模式、關(guān)聯(lián)模式和序列模式6種。給定一個由客戶交易之城的數(shù)據(jù)庫DB，挖掘序列模式的問題就是在那些具有客戶指定最小支持度（minimum support）的序列中找出最大序列（maximal sequence），而每個這樣的最大序列就代表了一個序列模式（sequence pattern）

一、序列模式挖掘參數(shù)

1.時間序列T的時間長度

可以講數(shù)據(jù)庫中的整個序列或用戶所選擇的序列（如2003你那）作為時間序列的長度，序列模式（挖掘）將僅限于在之一序列長度之內(nèi)進行。

2.時間窗口W

一系列在時間內(nèi)發(fā)生的事件在特定的分析中可以看成是一起發(fā)生的。如果一個時間窗口W唄設置為同序列T一樣長，那就會發(fā)現(xiàn)對時間不敏感的頻繁模式，也就是基本關(guān)聯(lián)模式。如：“2000年，一個購買電腦的顧客也買了數(shù)碼相機”其中不再關(guān)系哪個先買哪個后買）；若一個事件窗口W被設置為0，那就會發(fā)現(xiàn)一個序列事件是作為單個時間發(fā)生（來處理的）如：“一個顧客購買了電腦，然后又購買了內(nèi)存，最后悔購買CD-ROM”。若一個事件窗口W被設置為上述兩者之間的某個值（即0與T總長度之間），如：若W設為一個月，那么在同一月發(fā)生的交易事務，將被認為是同一時間發(fā)生的，而被合在一起進行分析。

3.發(fā)現(xiàn)模式中事件發(fā)生的時間間隔int。

若將int設為0，就意味著沒有間隔，也就是發(fā)現(xiàn)嚴格連續(xù)時間序列。這里也可以將參數(shù)W考慮進來。若W設為一周，也就是要發(fā)現(xiàn)連續(xù)各周頻繁模式。DNA分析經(jīng)常需要發(fā)現(xiàn)無間隔的連續(xù)序列。而min_interval int大多挖掘頻繁序列模式的研究都是針對不同的參數(shù)設置，以及采用Aprior啟發(fā)知識和與Apriori類似。但做了相應改動的挖掘方法。

二、序列模式發(fā)現(xiàn)算法

1.基于Apriori性質(zhì)的逐層發(fā)現(xiàn)方法

Apriori性質(zhì)是指頻繁項集的所有非空子集必須也是頻繁的。即在交易數(shù)據(jù)庫中，如果某一長度為K的序列不是頻繁的，那么它的任何長度為k+1的超序列也不可能是頻繁的。這種基于Apriori[8]性質(zhì)的逐層搜索的迭代方法，主要包括AprioriAll算法和GSP算法等。此類算法的思想是在已經(jīng)生成頻繁序列中搜尋更長的頻繁序列，并在此過程中對待檢查的序列集進行有效的修建。

（1）AprioriAll算法。AprioriAll算法將序列模式發(fā)現(xiàn)的過程分為以下五個階段：排序階段：數(shù)據(jù)庫中的元組按照“顧客號”為主鍵，“交易時間”為次主鍵排序。頻繁項集發(fā)現(xiàn)階段：用頻繁集合發(fā)現(xiàn)算法，求出所有頻繁項集，以滅個頻繁項集為唯一元素的序列即為頻繁1-序列。轉(zhuǎn)化階段：每個事務被該事務中所有頻繁項集所替代，經(jīng)過轉(zhuǎn)化，事務序列唄表示成由頻繁項集的集合構(gòu)成的有序表。序列階段：這是算法的主要階段。在算法執(zhí)行中，需要多趟掃描原序列數(shù)據(jù)庫。最大序列階段：從頻繁序列中找出最大序列，在實現(xiàn)上，這一階段可以與上一階段合并。

（2）GSP算法?；镜男蛄心Ｊ侥Ｐ脱芯康氖窃谕蛔侄紊系男蛄心Ｊ郊磫尉S的序列模式。實踐應用中的數(shù)據(jù)集是一個多維的空間。基本序列模型存在缺少時間約束、對交易的定義死板、缺少分類層次等局限，因此為客服上述局限文獻7的作者將序列模式的基本模型進行了擴展，加入了時間約束、滑動窗口和分類層次，提出了泛化序列模式發(fā)現(xiàn)問題并給出了相應的GSP算法。GSP算法是一個迭代的過程，在每一次迭代中，首先生成候選序列，然后掃描序列數(shù)據(jù)庫計算候選序列的支持度以確定頻繁徐立。其中候選序列的生成階段包括連接階段和修剪階段。

2.基于序列模式增長的發(fā)現(xiàn)方法

基于序列模式增長（sequential patterns growth）方法，包括FreeSpan，PrefixSpan算法等。這類方法采取了一種分而治之（devide-and-conquer）的思想，挖掘過程中無需生成候選序列。其主要特征有：算法不生成大量的候選序列，而是以某種壓縮的形式保留了原數(shù)據(jù)庫的基本的數(shù)據(jù)分組。隨后的分析可以聚焦于計算相關(guān)數(shù)據(jù)集而非候選序列的頻率。算法的每一次迭代不是掃描完整的原數(shù)據(jù)庫來匹配相應的全部候選序列，而是通過數(shù)據(jù)庫投影來對將要檢查的數(shù)據(jù)集和序列模式進行劃分，這樣分而治之的方法將減小搜索空間，提高算法性能。FreeSpan算法是在基于任何頻繁子序列對數(shù)據(jù)庫投影，并在子序列的任何位置上增長；而PrefixSpan算法僅僅基于頻繁前綴子序列投影并通過在其后添加后綴來實現(xiàn)序列的增長。PrefixSpan算法因包含更少的投影庫和子序列連接而比FreeSpan算法性能更優(yōu)。

本文主要講述了序列模式的挖掘問題，并對序列模式挖掘的經(jīng)典算法進行描述。肅立惡魔是與管理模式相仿，只不過把數(shù)據(jù)之間的關(guān)聯(lián)性與時間聯(lián)系起來。為了發(fā)現(xiàn)序列模式，不僅需要知道事件是否發(fā)生，而且需要確定事件發(fā)生的時間。由此看出，序列模式挖掘是很有價值的，他在網(wǎng)絡通信、氣象分析、商業(yè)零售、金融證劵等領(lǐng)域有廣闊的應用前景。同時對于一般的大型數(shù)據(jù)庫，序列模式挖掘算法的時空開銷往往都很大，這就要求我們在經(jīng)典算法的基礎(chǔ)上設計出高校挖掘算法。

作者簡介：

孫冬梅（（1978—），女，長春市房產(chǎn)檔案館，學士，研究方向：人工智能。

（作者單位：長春市房產(chǎn)檔案館）