序列模式挖掘.ppt

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