序列模式

簡介

序列模式的概念最早是由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以客戶號為主鍵交易時間為次鍵進行排序。這個階段將原來的事務資料庫轉換成由客戶序列組成的資料庫。

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

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

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

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

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