GSP算法是AprioriAll算法的擴展算法，而AprioriAll算法為Apriori類算法，故GSP算法也是一個Apriori類算法。在GSP算法中，引入了時間約束、滑動時間窗和分類層次技術，增加了掃描的約束條件，有效地減少了需要掃描的候選序列的數量，同時還克服了基本序列模型的局限性，更切合實際，減少多餘的無用模式的產生。另外，GSP利用哈希樹來存儲候選序列，減少了需要掃描的序列數量，同時對數據序列的表示方法進行了轉換，這樣就可以有效地發現一個候選項是否是數據序列的子序列。
基本介紹
- 中文名：GSP算法
- 外文名：Generalized Sequential Pattern mining algorithm
- 類似於：Apriori算法
- 1、：根節點
- 2、：內部節點
算法思想,GSP算法描述,算法步驟,哈希樹,候選序列模式,算法缺點,
算法思想
GSP算法描述
算法步驟
GSP算法基本步驟如下：
1）掃描序列資料庫，得到長度為1的序列模式L1，作為初始的種子集
2）根據長度為i 的種子集Li ，通過連線操作和修剪操作生成長度為i+1的候選序列模式Ci+1；然後掃描序列資料庫，計算每個候選序列模式的支持度，產生長度為i+1的序列模式Li+1，並將Li+1作為新的種子集
3）重複第二步，直到沒有新的序列模式或新的候選序列模式產生為止
產生候選序列模式主要分兩步：
連線階段：如果去掉序列模式s1的第一個項目與去掉序列模式s2的最後一個項目所得到的序列相同，則可以將s1與s2進行連線，即將s2的最後一個項目添加到s1中
修切階段：若某候選序列模式的某個子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除
候選序列模式[的支持度計算：對於給定的候選序列模式集合C，掃描序列資料庫，對於其中的每一條序列s,找出集合C中被s所包含的所有候選序列模式，並增加其支持度計數
GSP需要多次掃描序列資料庫，在第一次掃描中，對所有的單個項目(1—序列模式)進行計數。利用頻繁1—序列模式生成候選頻繁2—序列模式，進行第二次掃描並求候選頻繁2—序列模式的支持數。使用頻繁2—序列模式生成候選頻繁3—序列模式，重複以上過程，直到找出所有的頻繁序列模式。
哈希樹
哈希樹GSP採用哈希樹存儲候選序列模式。哈希樹的節點分為三類： 1、根節點；
2、內部節點；
3、葉子節點。
候選序列模式
初始時所有節點都是葉子節點，當一個葉子節點所存放的序列數目達到一個閾值，它將轉化為一個內部節點。
候選序列模式支持度的計算
給定一個序列s是序列資料庫的一個記錄：
1）對於根節點，用哈希函式對序列s的每一個單項做映射來並從相應的表項向下疊代的進行操作 2）。
2）對於內部節點，如果s是通過對單項x做哈希映射來到此節點的，則對s中每一個和x在一個元素中的單項以及在x所在元素之後第一個元素的第一個單項做哈希映射，然後從相應的表項向下疊代做操作 2）或 3）。
3）對一個葉子節點，檢查每個候選序列模式c是不是s的子序列.如果是相應的候選序列模式支持度加一。
這種計算候選序列的支持度的方法避免了大量無用的掃描，對於一條序列，僅檢驗那些最有可能成為它子序列的候選序列模式。掃描的時間複雜度由O(n*m)降為O(n*t),其中n表示序列數量，m表示候選序列模式的數量，t代表哈希樹葉子節點的最大容量
算法缺點
GSP算法還有好多缺點和不能解決的問題，如果序列資料庫的規模比較大，則有可能會產生大量的候選序列模式
需要對序列資料庫進行循環掃描
對於序列模式的長度比較長的情況，由於其對應的短的序列模式規模太大，本算法很難處理
