序列模式挖掘算法

2001-8-15,1,序列模式挖掘算法简介,报告人：邓爱林,报告的主要内容,序列模式简介GSP算法PrefixSpan算法,2001-8-15,2,一、序列模式简介,序列模式的概念最早是由Agrawal和Srikant提出的序列模式定义：给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值,2001-8-15,3,一、序列模式简介,例子1：在两年前购买了Ford牌轿车的顾客，很有可能在今年采取贴旧换新的购车行动例子2：在购买了自行车和购物篮的所有客户中，有70%的客户会在两个月后购买打气筒,2001-8-15,4,一、序列模式简介,应用领域：客户购买行为模式预测Web访问模式预测疾病诊断自然灾害预测DNA序列分析,2001-8-15,5,一、序列模式简介,符号化表示：项目集(Itemset)是各种项目组成的集合序列(Sequence)是不同项目集(ItemSet)的有序排列，序列s可以表示为s=，sj(1=j=l)为项目集(Itemset)，也称为序列s的元素序列的元素(Element)可表示为(x1x2xm)，xk(1=k=m)为不同的项目，如果一个序列只有一个项目，则括号可以省略一个序列包含的所有项目的个数称为序列的长度。长度为l的序列记为l-序列,2001-8-15,6,一、序列模式简介,符号化表示：设=，=，如果存在整数1=j1j2jn=m)，则序列关于子序列的后缀为，其中em”=(em-em),2001-8-15,17,三、PrefixSpan算法,例子：,a(ab),a(abc),2001-8-15,18,三、PrefixSpan算法,算法描述：扫描序列数据库，生成所有长度为1的序列模式根据长度为1的序列模式，生成相应的投影数据库在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生长度为1的序列模式为止,S,S1,Sm,S11,S1n,Sm1,Smp,2001-8-15,19,三、PrefixSpan算法,扫描序列数据库S，产生长度为1的序列模式有：:4,:4,:4,:3,:3,:3序列模式的全集必然可以分为分别以，和为前缀的序列模式的集合，构造不同前缀所对应的投影数据库，结果如下页图所示分别对不同的投影数据库重复上述过程，直到没有新的长度为1的序列模式产生为止,2001-8-15,20,三、PrefixSpan算法,2001-8-15,21,三、PrefixSpan算法,定义1.投影数据库：设为序列数据库S中的一个序列模式，则的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S|定义2.投影数据库中的支持数：设为序列数据库S中的一个序列模式，序列以为前缀，则在的投影数据库S|中的支持数为S|中满足条件.的序列的个数,2001-8-15,22,三、PrefixSpan算法,PrefixSpan算法输入：序列数据库S及最小支持度阈值min_sup输出：所有的序列模式方法：调用子程序PrefixSpan(,0,S),2001-8-15,23,三、PrefixSpan算法,子程序PrefixSpan(,L,S|)参数：.一个序列模式L.序列模式的长度S|.如果为空，则为S，否则为的投影数据库扫描S|，找到满足下述要求的长度为1的序列模式b：b可以添加到的最后一个元素中并为序列模式可以作为的最后一个元素并为序列模式对每个生成的序列模式b，将b添加到形成序列模式，并输出对每个,构造的投影数据库S|,并调用子程序PrefixSpan(,L+1,S|),2001-8-15,24,三、PrefixSpan算法,PrefixSpan算法分析：PrefixSpan算法不需要产生候选序列模式，从而大大缩减了检索空间相对于原始的序列数据库而言，投影数据库的规模不断减小PrefixSpan算法的主要开销在于投影数据库的构造,2001-8-15,25,三、PrefixSpan算法,PrefixSpan算法的主要改进：逐层投影：使用隔层投影代替逐层投影，从而可以有效减小投影数据库的个数伪投影：当序列数据库可以直接放入内存时，可以使用伪投影操作代替实际的投影数据库，从而可以有效减少构造投影数据库的开销,2001-8-15,26,三、PrefixSpan算法,隔层投影的例子：扫描序列数据库，产生所有长度为1的序列模式再次扫描序列数据库，构造如下图所示的下三角矩阵，得到所有长度为2的序列模式构造长度为2的序列模式所对应的扫描数据库，然后对每个投影数据库，重复上面的操作，直到没有新的序列模式产生为止,2001-8-15,27,三、PrefixSpan算法,伪投影：当数据库可以直接放入内层时，并不需要构造所有的序列模式对应的投影数据库，我们可以使用指向数据库中序列的指针及其偏移量作为伪投影例子：假设上述序