# Sequence Pattern

在前一章節的 Association Analysis 中， itemset 都是固定一筆一筆所出現

若我們想要更了解 Item 之間的 association rule

勢必要加上時間軸，得到順序與因果關係

## Sequence Data

我們將一般 Dataset 加上 Timeline 取得 sequence data table

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LqfXlLWW5EOuHsJq4i_%2F-LqfXo0FeeLA-TF9dueF%2Fsequence_database.png?generation=1570541095352092\&alt=media)

| Object | Timestamp | Events  |
| ------ | --------- | ------- |
| A      | 10        | 2,3,5   |
| A      | 20        | 6,1     |
| A      | 23        | 1       |
| B      | 11        | 4,5,6   |
| B      | 17        | 2       |
| B      | 21        | 7,8,1,2 |
| B      | 28        | 1,6     |
| C      | 14        | 1,8,7   |

## Definition

* **Sequence** : 我們的時間軸，時間軸上有許多 elements
* **Element** : 即 transaction，一個 transaction 有許多 events
* **Event** : 每個 events 代表一個 item
* **Length of sequence** : 用 $$\lvert s\rvert$$ 表達 sequence 上的 elements 有幾個
  * k-sequence 代表該 sequence 上共有 k 個 events
* 例如下圖是一個 **8-sequence with length 5** 的 sequence data

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LqfXlLWW5EOuHsJq4i_%2F-LqfXo0M6WAqoV3nMUbZ%2Fsequence_data.png?generation=1570541095449403\&alt=media)

* 還有許多的例子
  * web sequence `<{Homepage} {Electronics} {Cameras} {Shopping Cart} ... >`
  * library checkout books `<{Fellowship of the Ring} {The Two Towers} {Return of the King}>`

## Subsequence

若 sequence A 的每個 elements 的 events

都是另一個 sequence B 對應的 elements 的 subset

那 sequence A 就是 B 的 subsequence

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LqfXlLWW5EOuHsJq4i_%2F-LqfXo0O27R8crx8424i%2Fsubsequence_example.png?generation=1570541095142077\&alt=media)

* 一個 subsequence 的 support = data sequences 包含該 subsequence 的 fraction
* **Sequential pattern** : Frequent subsequence
  * 該 subsequence 的 support $$\ge$$ minsup

## Sequential Pattern Mining

從一群 sequences 中找出所有的 frequent subsequences

我們這邊使用 `<a(bc)dc>` 來表示有四個 elements 分別為 a, bc, d, c

而他是 `<a(abc)(ac)d(cf)>` 的 subsequence，原因如下

```
<a( bc)    d c>
<a(abc)(ac)d(cf)>
```

現在我們要從這個 sequence database 找出 sequential pattern

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LqfXlLWW5EOuHsJq4i_%2F-LqfXo0SbTEj676jLITN%2Ffind_sequential_pattern.png?generation=1570541095153395\&alt=media)

假設 minsup = 2，那我們可以找到 `<(ab)c>` 是一個 sequential pattern

因為 (ab) 跟 c 都有出現過兩次

### Definition of Sequential Pattern Mining

正式的來定義一下 **Sequential Pattern Mining**

```
Given :
    1. a database of sequences
    2. a minsup

Task :
    1. find all subsequences with support >= minsup
```

#### Extracting sequential patterns method

我們首先可以想到用 candidates + apriori 的方法來找出 subsequences

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LqfXlLWW5EOuHsJq4i_%2F-LqfXo0WIP6uje0MjZQE%2Fextract_subsequences.png?generation=1570541095277592\&alt=media)

* 這類的算法有
  * Apriori\* (Apriori All, Apriori Some)
  * Apriori-based SP algorithm (GSP)
* 但想也知道有非常多的問題
  * 會產生過多的 candidate sequences
  * database scans 次數過多
  * 要找的 sequential patterns 長度越大越困難

## Sequential Pattern Mining Algorithm

1. 首先將 data 進行 sorting
2. 計算 large itemset 也就是 support 值
3. 進行 transformation (Replacement)
4. sequence phase
5. maximal phase

### Example

* 進行 sorting 後的資料

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcmX8VkR7wejG9B2%2Fsequential_pattern_1.jpg?generation=1573290679727150\&alt=media)

* 找出滿足 support 的 large itemset
  * 並給他們定義一個新 id

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcmZ7Uu4glE49Slf%2Fsequential_pattern_2.jpg?generation=1573290679297721\&alt=media)

* Transformation Phase
  * 刪除原本資料不滿足 support 的 item
  * 將滿足的資料能攤開的攤開
  * 然後設定新 id

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcmaKijDpRq3HC-B%2Fsequential_pattern_3.jpg?generation=1573290679195732\&alt=media)

* Sequence Phase
  * 將 after mapping 的 items 攤開成 Maximal Large Sequence
  * Apriori-like

```
<1 2 3> : support = 2
<1 2 4> : support = 2

Generate <1 2 3 4>
```

* Maximal Sequence
  * 一個 sequence 沒有包含在其他 sequence 即為 maximal sequence

```
e.g.

<(3) (4 5) (8)> is contained by <(7) (3 8) (9) (4 5 6) (8)>

<(3) (5)> is not contained by <(3 5)>
```

## Episode Mining

* Episode : A partially ordered collection of events occurring&#x20;

  together
* 以 sliding window 方式來抓出 sequence
* discover all frequent episodes from a given class(ex. all parallel or all serial) of episodes&#x20;

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcmcVMq3NDDzECag%2Fepisode_mining.jpg?generation=1573290680308044\&alt=media)

## FreeSpan

* Frequent pattern-projected Sequential pattern mining
  * 將 sequence database 投影成**較小**的 projected database
  * grow subsequence fragments in each projected database
  * **Divide-and-conquer**

### Example

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcmeEST67AOHTHpu%2Ffreespan_1.jpg?generation=1573290679679421\&alt=media)

* a 皆出現在這四筆所以 a : 4
* 以此類推求出所有 support > 2 的 item 並排序

```python
f_list = a:4, b:4, c:4, d:3, e:3, f:3
```

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcmg4O09YNqgvRAy%2Ffreespan_2.jpg?generation=1573290680347539\&alt=media)

* 先對 a 投影
  * aaa 只出現 1 次所以不拿
  * aa 出現 2 次
  * a 出現 4 次

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcmiai82CKtnRSOt%2Ffreespan_3.jpg?generation=1573290678611865\&alt=media)

* 以 a 為底，接著對 b 投影
  * 可以抓出 b 出現 4 次
  * ab 出現 4 次
  * (ab) 出現 2 次
  * 要注意 ab 和 (ab) 是不同的

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcmkEdyJmSjC3fzJ%2Ffreespan_4.jpg?generation=1573290679159209\&alt=media)

* 以 a, b 為底，接著對 c 投影

## PrefixSpan

* Prefix-projected Sequential pattern mining
  * 一樣是 Projection-based
  * less projections and quickly shrinking sequences&#x20;
* PrefixSpan 有三個核心，分別是 **prefix, postfix, projection**
  * 假設有一 sequence 為 `<a(abc)(ac)d(cf)>`
  * Prefix
    * `<a>, <aa>, <a(ab)>, <a(abc)> ...`
    * 一定要從每一個 item 的頭開始
    * 所以 `<ab>, <a(bc)>` 這些都不算在 prefix
  * Postfix
    * 對於 `<aa>` 來說他的 postfix 為
      * `<(_bc)(ac)d(cf)>`
    * 對於 `<bd>` 來說他的 postfix 為
      * `<(cf)>`
  * Projection
    * projection 讓我們可以 groupby
    * `<bd>` 的 projection 是 `<bd(cf)>`

### Example

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcmmfmHr9nzZh1al%2Fprefixspan_1.jpg?generation=1573290678644960\&alt=media)

* 先對 a 投影，就可以找出所有有 prefix a 的 length 2 sequence
  * `<aa>:2  <ab>:4  <(ab)>:2  <ac>:4  <ad>:2  <af>:2`
  * 接著就可以對這 6 個 subsets 遞迴投影

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcmoUJu0kyFMXZBO%2Fprefixspan_2.jpg?generation=1573290680612813\&alt=media)

* 例如對 `<aa>` 投影，有兩筆可以繼續遞迴
* 對 `<ab>` 投影，有三筆可以繼續遞迴
* 同時也可以刪去不滿足 support 的 item

![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LtEQbL2UX2cyCOM31AT%2F-LtEQcmqB-s4d9sSsE-B%2Fprefixspan_3.jpg?generation=1573290679834116\&alt=media)

* 將 a 及其 subsets 進行一輪後
* 接著就可以對 b 及他的 subsets 投影
