知識背景 序列模式是神馬 1 顧客購買產品X 很可能在一段時間內購買購買產品Y 時間序列模型 2 在某個點發現了現象X 很可能在下一個點發現現象Y 空間序列模型 知識背景 序列模型VS關聯規則 關聯規則 序列模型 序列模型 關聯規則 時間 空間 維度 知識背景 序列模型VS時間序列模型 時間序列模型 序列模型 序列模型 一系列研究對象在某段時間內的行為模式分析 如顧客購買序列模式的發現 時間序列模型 一個特定對象 變量 在某段時間內的變化趨勢 具有時間自相關性 如股票分析 知識框架 1 1概念 定性 序列模式挖掘是挖掘頻繁出現的有序事件或子序列 定量 給定一個正整數min sup 表示最小支持度閾值 如果序列 在序列數據庫S中存在support S min sup 則序列 是頻繁序列 也叫做序列模式 1 2 定義 序列 將與對象A有關的所有事務按時間戳增序排序 就得到對象A的一個序列s 事務 序列是事務的有序列表 可以記作s 項 事務e是一個項集 可以記作e x1 x2 x3 xn 當只有1項時直接記作x1 序列包含的項的數量記作序列的長度 長度為L的序列記作L序列 序列數據庫 包含一個或多個序列數據的數據集 子序列 設序列 序列 ai和bi都是元素 如果存在整數1 j1 j2 jn m 使得a1 bj1 a2 bj2 an bjn則稱序列 為序列 的子序列 又稱序列 包含序列 記為 包含3個序列 S1 S2 S3 假設有S4 S1包含3個事務 8個項 長度即為8 成為8序列 S2以及S3都為S1的子序列 S4則不是S1的子序列 2 1GSP算法和SPADE算法 算法介紹 屬于類Apriori算法 基于原理 序列模式的每個非空子集都是序列模式 基于 候選產生 測試 模式進行挖掘 主要步驟 1 掃描序列數據庫 得到長度為1的序列模式L1 作為初始的種子集 2 根據長度為i的種子集Li 通過連接操作和修剪操作生成長度為i 1的候選序列模式Ci 1 然后掃描序列數據庫 計算每個候選序列模式的支持度 產生長度為i 1的序列模式Li 1 并將Li 1作為新的種子集 3 重復第二步 直到沒有新的序列模式或新的候選序列模式產生為止 L1 C2 L2 C3 L3 C4 L4 2 1GSP算法和SPADE算法 連接操作 如果去掉序列模式S1的第一個項與去掉序列模式S2的最后一個項所得到的序列相同 則可以將S1于S2進行連接 即將S2的最后一個項目添加到S1中 其中 1 若S2的最后兩個項本來屬于同一個事務 則合并后與S1序列的最后一個項合并為同一個同一個事務 2 否則 S2最后一項則單獨成為一個事務 剪切階段 若某候選序列模式的某個子序列不是序列模式 則此候選序列模式不可能是序列模式 將它從候選序列模式中刪除 頻繁3序列 候選產生 候選剪枝 2 1GSP算法和SPADE算法 GSPVSSPADE 區別在于數據庫中存儲數據的結構不一樣 因此掃描數據庫的效率不一樣 2 1GSP算法和SPADE算法 如果序列數據庫的規模比較大 則有可能會產生大量的候選序列模式需要對序列數據庫進行循環掃描對于序列模式的長度比較長的情況 由于其對應的短的序列模式規模太大 本算法很難處理 類Apriori算法存在的問題 2 2PrefixSpan算法 算法介紹 基于FP增長算法采用分治的思想 不斷產生序列數據庫的多個更小的投影數據庫 然后在各個投影數據庫上進行序列模式挖掘 前綴與后綴 假定序列S 則序列 等都是S的前綴 S關于的后綴為 S關于的后綴為 S關于的后綴為 2 2PrefixSpan算法 投影數據庫 設 為序列數據庫S中的一個序列模式 則 的投影數據庫為S中所有以 為前綴的序列相對于 的后綴 記為S 例 序列模式的投影數據庫為 2 2PrefixSpan算法 主要步驟 1 得到長度為1的序列模型 2 劃分搜索空間 3 找出序列模式的子集 a 找出序列數據庫D關于的投影數據庫 b 掃描投影數據庫 得到局部頻繁項 c 遞歸過程 4 匯集 S S1 Sm S11 S1n Sm1 Smp 2 2PrefixSpan算法 1 1序列模型為 4次 4次 4次 3次 3次 3次 2 劃分搜索空間 根據 1 中的結果劃分前綴為的子集 前綴為的子集 前綴為的子集等 2 2PrefixSpan算法 3 找出序列模型的子集 a 建立的投影數據庫 b 掃描上述投影數據庫 找出局部頻繁項 分別為 c 遞歸地尋找以 為前綴的序列模型 4 匯總以上挖掘的序列模型子集 2 2PrefixSpan算法 PrefixSpan算法分析 PrefixSpan算法不需要產生候選序列模式 從而大大縮減了檢索空間相對于原始的序列數據庫而言 投影數據庫的規模不斷減小PrefixSpan算法的主要開銷在于投影數據庫的構造 3 1多維 多層次的序列模式挖掘 購買數碼相機的退休顧客很可能在一個月內購買彩色打印機 購買筆記本的年輕人很可能在兩周內購買打印機 這些例子的序列模式挖掘都是多維 多層次的 多維體現在 年輕人 與 老人 多層次體現在 彩色打印機 與 打印機 3 2基于約束的序列模式挖掘 1 序列的長度例 顧客在1周內購買的商品序列 2 序列間事務的最大間隔例 用戶的Web頁面瀏