Sequential Pattern Mining

Sequence  Data(ch7 ppt 28)

• 討論有關與資料出現順序有關的 itemsets, 例如:生物的 DNA, ATGC 字母的出現順序是有關係
• 在 sequence 中的 elements 是有順序關係，但是在 elements 中的 itemsets 是沒有順序性，如同之前章節所討論的 itemsets 一樣，與順序無關
• 算 sequence 長度是計算其中 events 的個數，但是所謂 k-sequence 是計算 sequence 中所有 items 的個數，即 k-sequence 共有 k 個 events(items) 的 sequence, for example, <{a,b} {a,c} b {d, f}> sequence is 7-sequence.

Formal Definition of a subsequence(ppt 30)

• A sequence <a1 a2 … an> is contained in another sequence <b1 b2 … bm> (m >=n) if there exist integers i1 < i2 < … < in such that a1 \in bi1 , a2 \in bi1, …, an \in bin
• 在表第二列中，因為 {1},{2} 不同時間發生，所以不是<{1,2} {3,4}> 的 subsequence
  
• 檢查是否是某一個 sequence 的 subsequence 的方法
∘ 檢查順序是否相同
∘ 檢查是否為 sequence 的子集合

Contiguous Subsequences

s is a contiguous subsequence of  w = <e1>< e2>…< ek>
• if any of the following conditions hold:
∘ s is obtained from w by deleting an item from either e1 or ek
∘ s is obtained from w by deleting an item from any element ei that contains more than 2 items
∘ s is a contiguous subsequence of s’ and s’ is a contiguous subsequence of w (recursive definition)