序列模式挖掘.ppt

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