GSP算法

GSP算法是AprioriAll算法的擴展算法,而AprioriAll算法為Apriori類算法,故GSP算法也是一個Apriori類算法。在GSP算法中,引入了時間約束、滑動時間窗和分類層次技術,增加了掃描的約束條件,有效地減少了需要掃描的候選序列的數量,同時還克服了基本序列模型的局限性,更切合實際,減少多餘的無用模式的產生。另外,GSP利用哈希樹來存儲候選序列,減少了需要掃描的序列數量,同時對數據序列的表示方法進行了轉換,這樣就可以有效地發現一個候選項是否是數據序列的子序列。

算法思想

類似於Apriori算法,採用冗餘候選模式的剪除策略和特殊的數據結構-----哈希樹來實現候選模式的快速訪存。

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、根節點;
2、內部節點;
3、葉子節點
根節點和內部節點中存放的是一個哈希表,每個哈希表項指向其它的節點。而葉子節點記憶體放的是一組候選序列模式。

添加候選序列模式

從根節點開始,用哈希函式對序列的第一個項目做映射來決定從哪個分支向下,依次在第n層對序列的第n個項目作映射來決定從哪個分支向下,直到到達一個葉子節點。將序列儲存在此葉子節點。
初始時所有節點都是葉子節點,當一個葉子節點所存放的序列數目達到一個閾值,它將轉化為一個內部節點。

計算候選序列模式的支持度

給定一個序列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算法存在的主要問題

果序列資料庫的規模比較大,則有可能會產生大量的候選序列模式
需要對序列資料庫進行循環掃描
對於序列模式的長度比較長的情況,由於其對應的短的序列模式規模太大,本算法很難處理

相關詞條

相關搜尋

熱門詞條

聯絡我們