序列模式挖掘PPT课件.ppt

序列模式挖掘1.知识背景：序列模式是神马？1.1.顾客购买产品X X，很可能在一段时间内购买购买产品Y Y；（时间序列模型）2.2.在某个点发现了现象X X，很可能在下一个点发现现象Y Y；（空间序列模型）2.知识背景：序列模型VS关联规则关联规则序列模型序列模型=关联规则+时间（空间）维度3.知识背景：序列模型VS时间序列模型时间序列模型序列模型序 列 模 型：一系列研究对象在某段时间内的行为模式 分析，如顾客购买序列模式的发现；时间序列模型：一个特定对象（变量）在某段时间内的变化 趋势，具有时间自相关性，如股票分析；4.知识框架：1.概念与定义1.1 概念1.2 定义2.2.经典算法经典算法2.1 GSP算法和SPADE算法2.2PrefixSpan算法3.拓展研究3.1 多维、多层次的序列模式挖掘3.2 基于约束的序列模式挖掘4.应用案例应用案例5.1.1 概念定性：序列模式挖掘是挖掘频繁出现的有序事件或子序列；定量：给定一个正整数min_sup，表示最小支持度阈值，如果序列在序列数据库S中存在support（S）（）min_sup，则序列是频繁序列，也叫做序列模式。6.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则称序列为序列的子序列，又称序列包含序列，记为 ；序列数据库对象（SID）时间戳（EID）事务A A1 11 1，2 2，4 4A A2 22 2，3 3，4 4A A3 34 4，5 5B B1 11 1，2 2B B2 22 2，3 3B B3 35 5CC1 11 1，2 2CC2 24 4包含3 3个序列：S S1 1=S S2 2=S S3 3=（假设有S S4 4=）S S1 1包含3 3个事务，8 8个项，长度即为8 8，成为8 8序列；S S2 2以及S S3 3都为S S1 1的子序列；S S4 4则不是S S1 1的子序列；7.2.1 GSP算法和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 8.2.1 GSP算法和SPADE算法连接操作：如果去掉序列模式S1的第一个项与去掉序列模式S2的最后一个项所得到的序列相同，则可以将S1于S2进行连接，即将S2的最后一个项目添加到S1中。其中：（1）若S2的最后两个项本来属于同一个事务，则合并后与S1序列的最后一个项合并为同一个同一个事务；（2）否则，S2最后一项则单独成为一个事务。剪切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除。频繁3 3序列：候选产生：14131 25 候选剪枝：9.2.1 GSP算法和SPADE算法GSP:GSP:水平数据格式序列ID（SID）序列1234GSPVSSPADESPADESPADE：垂直数据格式SIDEID项111121，2，3131，3144153，6211，4223232，3241，5463区别在于数据库中存储数据的结构不一样，因此扫描数据库的效率不一样。1 1序列的ID_listID_list12SIDEIDSIDEID1112122313422135244532432 2序列的ID_listID_listSIDEID(1)EID(2)11221332543510.2.1 GSP算法和SPADE算法如果序列数据库的规模比较大，则有可能会产生大量的候选序列模式需要对序列数据库进行循环扫描对于序列模式的长度比较长的情况，由于其对应的短的序列模式规模太大，本算法很难处理类Apriori算法存在的问题11.2.2 PrefixSpan算法算法介绍：基于FP增长算法采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘;前缀与后缀：假定序列S=，则序列、等都是S的前缀。S关于的后缀为;S关于的后缀为;S关于的后缀为12.2.2 PrefixSpan算法投影数据库：设为序列数据库S中的一个序列模式，则的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S|例：序列模式的投影数据库为：,序列ID（SID）序列123413.2.2 PrefixSpan算法主要步骤：(1)得到长度为1的序列模型；（2）划分搜索空间；（3）找出序列模式的子集；（a）找出序列数据库D关于的投影数据库；（b）扫描投影数据库，得到局部频繁项；（c）递归过程；（4）汇集SS1SmS11 S1n Sm1 Smp 14.2.2 PrefixSpan算法序列ID（SID）序列1234（1）1序列模型为：4次，：4次，：4次，：3次，：3次，：3次；（2）划分搜索空间：根据（1）中的结果划分前缀为的子集；前缀为的子集；前缀为的子集等15.2.2 PrefixSpan算法（3）找出序列模型的子集：(a)建立的投影数据库；(b)扫描上述投影数据库，找出局部频繁项，分别为：,;(c)递归地寻找以,为前缀的序列模型;（4）汇总以上挖掘的序列模型子集；16.2.2 PrefixSpan算法PrefixSpan算法分析PrefixSpan算法不需要产生候选序列模式，从而大大缩减了检索空间相对于原始的序列数据库而言，投影数据库的规模不断减小PrefixSpan算法的主要开销在于投影数据库的构造17.3.1 多维、多层次的序列模式挖掘“购买数码相机的退休顾客很可能在一个月内购买彩色打印机”、“购买笔记本的年轻人很可能在两周内购买打印机”这些例子的序列模式挖掘都是多维、多层次的。多维体现在：“年轻人”与“老人”；多层次体现在：“彩色打印机”与“打印机”18.3.2 基于约束的序列模式挖掘1.序列的长度例：顾客在1周内购买的商品序列；2.序列间事务的最大间隔例：用户的Web页面浏览序列，但每个页面要在3次点击之内3.序列间事务的最小间隔例：天气的变化序列，但每个现象需要1天的间隔19.4.1应用案例应用领域：客户购买行为模式预测Web访问模式预测自然灾害预测DNA序列分析疾病病症预测20.Thank you！谢谢21.