序列模式

序列模式的概念最早是由Agrawal和Srikant 提出的。

動機：大型連鎖超市的交易數據有一系列的用户事務數據庫，每一條記錄包括用户的ID，事務發生的時間和事務涉及的項目。如果能在其中挖掘涉及事務間關聯關係的模式，即用户幾次購買行為間的聯繫，可以採取更有針對性的營銷措施。

例：一個事務數據庫，一個事務代表一筆交易，一個單項代表交易的商品，單項屬性中的數字記錄的是商品ID。

序列（Sequence）：以SID表示，一個序列即是一個完整的信息流。

項目（Item）：序列中最小組成單位的集合，比如在這個樣例中的項目為{A, B, C}。

事件（Event）：通常用時間戳標誌，標識事件之間的前後關係。又叫Itemset，是Item的集合，樣例中以EID表示。

k頻繁序列：如果頻繁序列的項目個數為k，則稱之為k頻繁序列，以Fk表示（圖1的F1,F2,F3）。

序列的包含關係：對於序列x和y，如果存在着一個保序的映射，使得x中的每個事件都被包含於y中的某個事件，則稱為x被包含於y（x是y的子序列），例如序列B->AC是序列AB->E->ACD的子序列。

支持度（support）：某序列x的支持度是指在整個序列集中包含x的序列的頻次。

給定一個由不同序列組成的集合，其中，每個序列由不同的元素按順序有序排列，每個元素(交易)由不同項目組成，同時給定一個用户指定的最小支持度閾值，序列模式挖掘就是找出所有的頻繁子序列，即該子序列在序列集中的出現頻率不低於用户指定的最小支持度閾值。

項目集(Itemset)是各種項目組成的集合

序列(Sequence)是不同項目集(ItemSet)的有序排列，序列s可以表示為s = <s1s2…sl>，sj(1 <= j <= l)為項目集(Itemset)，也稱為序列s的元素

序列的元素(Element)可表示為(x1x2…xm)， xk(1 <= k <= m)為不同的項目，如果一個序列只有一個項目，則括號可以省略

一個序列包含的所有項的個數稱為序列的長度。長度為l的序列記為l-序列

1) 排序階段。數據庫D以客户號為主鍵交易時間為次鍵進行排序。這個階段將原來的事務數據庫轉換成由客户序列組成的數據庫。 ^[1] 

2) 頻繁項集階段。找出所有頻繁項集組成的集合L。也同步得到所有頻繁1-序列組成的集合。 ^[1] 

3) 轉換階段。在找序列模式的過程中要不斷地進行檢測一個給定的頻繁集是否包含於一個客户序列中。 ^[1] 

4) 序列階段利用已知的頻繁集的集合來找到所需的序列。類似於關聯的Apriori算法。 ^[1] 

AprioriAll算法與Apriori算法的執行過程是一樣的，不同點在於候選集的產生，具體候選者的產生如下：

候選集生成的時候需要區分最後兩個元素的前後，因此就有<p.item1,p.item2,…,p.,q.>和<p.item1,p.item2,…, q.,p.>兩個元素。 ^[1] 

AprioriSome算法可以看做是AprioriAll算法的改進，具體可以分為兩個階段：

（1）Forward階段：找出置頂長度的所有大序列，在產生Li後，根據判斷函數j=next(last)，此時last=i，j>i，下個階段不產生i+1的候選項，而是產生j的候選項，如果j=i+1，那麼就根據Li生成Cj，如果j>i+1，那麼Cj就有Cj-1產生。然後掃描數據庫計算Cj的支持度。

（2）Backward階段：根據Lj中的大項集，去掉Ci（i<j）中出現的Lj項，然後計算Ci中的支持度，判斷那些在Forward階段被漏判的項集。

AprioriAll算法和AprioriSome算法的比較：

（1）AprioriAll用去計算出所有的候選Ck，而AprioriSome會直接用去計算所有的候選，因為包含，所以AprioriSome會產生比較多的候選。

（2）雖然AprioriSome跳躍式計算候選，但因為它所產生的候選比較多，可能在回溯階段前就佔滿內存。

（3）如果內存佔滿了，AprioriSome就會被迫去計算最後一組的候選。

（4）對於較低的支持度，有較長的大序列，AprioriSome算法要好些。 ^[1] 

GSP(Generalized Sequential Patterns)算法，類似於Apriori算法大體分為候選集產生、候選集計數以及擴展分類三個階段。與AprioriAll算法相比，GSP算法統計較少的候選集，並且在數據轉換過程中不需要事先計算頻繁集。

GSP的計算步驟與Apriori類似，但是主要不同在於產生候選序列模式,GSP產生候選序列模式可以分成如下兩個步驟：

（1）連接階段：如果去掉序列模式S1的第一個項目與去掉序列模式S2的最後一個項目所得到的序列相同，則可以將S1和S2進行連接，即將S2的最後一個項目添加到S1中去。

（2）剪枝階段：若某候選序列模式的某個子集不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除。 ^[1] 

SAS Enterprise Miner：提供的數據挖掘包括迴歸、分類和統計分析包。它的特色是具有多種統計分析工具。 ^[2] 

SGI的MineSet：提供的挖掘算法有關聯和分類以及高級統計和可視化工具。特色是具有強大的圖形工具包括規則可視化工具、樹可視化工具、地圖可視化工具和多維數據分散可視化工具它們用於實現數據和數據挖掘結果的可視化。 ^[2] 

ISL的Clementine：為終端用户和開發者提供了一個集成的數據挖掘開發環境。系統集成了多種數據挖掘算法如規則歸納、神經網絡、分類和可視化工具。Clementine現已被SPSS公司收購。 ^[2]