這前兩個算法真是出人意料地好理解

GSP算法

GSP算法是APRioriAll算法的擴展算法，其算法的執行過程和AprioriAll類似。

其核心思想是：在每一次掃描(pass)數據庫時,利用上一次掃描時產生的大序列生成候選序列,并在掃描的同時計算它們的支持度(support),滿足支持度的候選序列作為下次掃描的大序列。第1次掃描時,長度為1的頻繁序列模式作為初始的大1—序列。

接下來會演示一下GSP如何產生候選集的。

GSP算法最大的特點就在于，GSP引入了時間約束、滑動時間窗和分類層次技術，增加了掃描的約束條件，有效地減少了需要掃描的候選序列的數量，同時還克服了基本序列模型的局限性，更切合實際，減少多余的無用模式的產生。

另外GSP利用哈希樹來存儲候選序列，減小了需要掃描的序列數量，同時對數據序列的表示方法進行轉換，這樣就可以有效地發現一個侯選項是否是數據序列的子序列。

但是這些方法都不算是GSP的核心思想，只是一些剪枝的優化而已，與其他很多算法的方式極其類似，無論是ACM-ICPC還是其他機器學習、深度學習的算法都有類似的優化，所以不再贅述。

演示

我們現在有如下的數據庫，并設置最小支持度min_support = 2

我們先進行第一次掃描。

得到如下的序列

這全部的就是候選集，然后沒有打叉的就是序列模式。這里的思想和之前講過的Apriori算法完全一樣。

現在我們來產生長度為2的候選集，只是候選集而已。

我們來稍微解釋一下，如<aa>，這個的意思就是先發生了一次a再發生了一次a，而不是同時發生的。每個a都是一個元素。

這里就不存在類似于<(aa)>$<(aa)>$這樣的序列了，這里是產生只含有一個元素的序列。

我們這里總共產生了候選集6×6+6×5÷2=51$6/times 6 + 6/times 5 /div 2 = 51$個。

如果沒有使用剪枝，而是直接使用類似于廣度優先搜索(bfs)的算法生成，則會有8×8+8×7÷2=92$8/times 8 + 8/times 7 /div 2 = 92$個。

然后再進行篩選，直到不能進行了為止。

哈希樹

使用數據結構對序列進行存儲能夠方便管理，節約空間。就有一些類似蛤夫曼樹壓縮編碼那樣。

GSP采用哈希樹存儲候選序列模式。哈希樹的節點分為三類：

根節點和內部節點中存放的是一個哈希表，每個哈希表項指向其它的節點。而葉子節點內存放的是一組候選序列模式。

代碼請見

SPADE算法

SPADE算法依舊使用傳統的先驗性質，即連接步+剪枝步的經典組合，思想跟GSP大致相同，但是引入了垂直列表數據庫。

SPADE算法尋找1-序列和2-序列頻繁項集方法跟GSP完全形同，在之后的3-候選集及之后的頻繁項計算中，采取了一種“作弊”的辦法獲得候選集，該辦法套用了三種屢試不爽的公式，如下：

同時還要注意，如果想要A和F得出AF，那么A發生的序列號要與F發生的序列號相同，而且A的時間序列號要小于F的時間序列號。想相反的情況也是一樣的，要得出FA，則要F的時間序列號要小于A的時間序列號。

演示

現有如下的數據庫

其中時間序列號（或稱為元素序列號）表示在一個序列中排序的位置，因為越大的排序在越后面。

在本例中AB，AF是兩個頻繁的2成員項，那么有可能存在且僅存在ABF這樣的3成員頻繁項，經過10次計算遍歷了一遍data發現ABF確實是頻繁的。

然后這樣也是一點一點做直到沒有辦法。

PrefixSpan

算法思想：采用分治的思想，不斷產生序列數據庫的多個更小的投影數據庫，然后在各個投影數據庫上進行序列模式挖掘。

相關定義

前綴：設每個元素中的所有項目按照字典序排列。給定序列α=<e1e2…en>$/alpha = <e_1e_2…e_n>$，β=<e′1e′2…e′m>(m≤n)$/beta= <e_1’ e_2’… e_m’> (m/leq n)$ ，如果e′i=ei(i≤m?1)，e′m??em$e_i’ = e_i (i/leq m - 1)， e_m’/subseteq ? e_m$，并且(em?e′m)$(e_m - e_m’)$中的項目均在e′m$e_m’$中項目的后面， 則稱β$/beta$是α$/alpha$的前綴。

例：序列<(ab)>$<(ab)>$是序列<(abd)(acd)>$<(abd)(acd)>$ 的一個前綴；序列<(ad)>$<(ad)>$則不是。

投影：給定序列α$/alpha$和β$/beta$ ，如果β$/beta$是α$/alpha$的子序列，則α$/alpha$關于β$/beta$的投影α′$/alpha’$必須滿足： β$/beta$是α′$/alpha’$的前綴，α′$/alpha’$是α$/alpha$的滿足上述條件的最長子序列。 　 例：對于序列α=<(ab)(acd)>$/alpha=<(ab)(acd)>$，其子序列β=<(b)>$/beta= <(b)>$的投影是α′=<(b)(acd)>$/alpha’ = <(b)(acd)>$; <(ab)>$<(ab)>$的投影是原序列<(ab)(acd)>$<(ab)(acd)>$。

后綴：序列α$/alpha$關于子序列β=<e1e2…em?1e′m>$/beta= <e_1e_2… e_{m-1}e_m’>$的投影為α′=<e1e2…en>(n≥m)$/alpha’ = <e_1e_2… e_n> (n /geq m)$，則序列α$/alpha$關于子序列β$/beta$的后綴為<e′′mem+1…en>$<e_m''e_{m+1}… e_n>$， 其中e′′m=(em?e′m)$e_m'' = (e_m - e_m’)$ 　　 例：對于序列<(ab)(acd)>$<(ab)(acd)>$，其子序列<(b)>$<(b)>$的投影是<(b)(acd)>$<(b)(acd)>$，則<(ab)(acd)>$<(ab)(acd)>$對于<(b)>$<(b)>$的后綴為<(acd)>$<(acd)>$。

投影數據庫：設α$/alpha$為序列數據庫S中的一個序列模式，則α$/alpha$的投影數據庫為S中所有以α$/alpha$為前綴的序列相對于α$/alpha$的后綴，記為S|α$S|_{/alpha}$。

投影數據庫中的支持度：設α$/alpha$為序列數據庫S中的一個序列，序列β$/beta$以α$/alpha$為前綴，則β$/beta$在α$/alpha$的投影數據庫S|α$S|_{/alpha}$中的支持度為S|α$S|_{/alpha}$中滿足條件β?α.γ$/beta/subseteq/alpha . /gamma$的序列γ$/gamma$的個數。

演示

1-序列都是一如既往地計算。

然后就根據每一個1-序列得出對應的投影數據庫

再結合每一個投影數據庫中序列的前綴，從而得到2-序列。

Clospan

用來計算閉合序列模式的方法，大家可以看看論文。

閉合序列模式s$s$: 不存在一個超序列s′$s'$，其中s′?s$s' ?s$，而且s′$s'$和s$s$有著相同的支持度。

<abc>:20,<abcd>:20,<abcde>:15 $$: 20, :20, : 15$$

其中<abcd>和<abcde>是閉合序列模式。

用兩種算法Backward Subpattern和Backward Superpattern來合并數據庫，實現Clospan。

論文：Greatly enhances efficiency (Yan, et al., SDM’03)

如果大家看到MathJax的公式最后都有一個奇怪的豎線，應該是CSDN自己的解析出現了問題，看起來確實挺奇怪的。