序列模式挖掘算法.ppt

《序列模式挖掘算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、序列模式挖掘算法简介报告人：邓爱林2001-8-151报告的主要内容序列模式简介GSP算法PrefixSpan算法2001-8-152一、序列模式简介序列模式的概念最早是由Agrawal和Srikant提出的序列模式定义：给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值2001-8-153一、序列模式简介例子1：在两年前购买了Ford牌轿车的顾客，很有可能在今年采取贴旧换新的

2、购车行动例子2：在购买了自行车和购物篮的所有客户中，有70%的客户会在两个月后购买打气筒2001-8-154一、序列模式简介应用领域：客户购买行为模式预测Web访问模式预测疾病诊断自然灾害预测DNA序列分析2001-8-155一、序列模式简介符号化表示：项目集(Itemset)是各种项目组成的集合序列(Sequence)是不同项目集(ItemSet)的有序排列，序列s可以表示为s=，sj(1<=j<=l)为项目集(Itemset)，也称为序列s的元素序列的元素(Element)可表示为(x1x2…xm)，xk(1<=k<=m)为不同的项目

3、，如果一个序列只有一个项目，则括号可以省略一个序列包含的所有项目的个数称为序列的长度。长度为l的序列记为l-序列2001-8-156一、序列模式简介符号化表示：设=，=，如果存在整数1<=j1

4、-模式2001-8-157一、序列模式简介例子：设序列数据库如下图所示，并设用户指定的最小支持度min-support=2。Sequence_idSequence1020<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40序列是序列的子序列序列<(ab)c>是长度为3的序列模式2001-8-158一、序列模式简介问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式系统规定：由于同一个元素中的项目

5、之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列2001-8-159一、序列模式简介序列模式挖掘的主要算法GSP(GeneralizedSequentialPatterns)算法：类似于Apriori算法PrefixSpan(Prefix-projectSequentialPatternmining)算法：采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘2001-8-1510一、序列模式简介上述算法存在的主要问题：缺少时间限制：用户可能需要指定序列模式的相邻元素之间的时间间隔

6、。例如，一个序列模式可能会发现客户在购买了物品A后的第三年购买物品B。我们需要的却是给定时间间隔内用户的购买意向事务的定义过于严格：一个事务中包含在客户的一次购买行为中所购买的所有物品。可能需要指定一个滑动时间窗口，客户在滑动时间窗口的时间段内的所有的购买行为均作为一个事务缺少分类层次：只能在项目的原始级别上进行挖掘2001-8-1511二、GSP算法GSP算法描述：扫描序列数据库，得到长度为1的序列模式L1，作为初始的种子集根据长度为i的种子集Li通过连接操作和剪切操作生成长度为i+1的候选序列模式Ci+1；然后扫描序列数据库，计算每个候选序列模式的支持

7、数，产生长度为i+1的序列模式Li+1，并将Li+1作为新的种子集重复第二步，直到没有新的序列模式或新的候选序列模式产生为止L1C2L2C3L3C4L4……2001-8-1512二、GSP算法产生候选序列模式主要分两步：连接阶段：如果去掉序列模式s1的第一个项目与去掉序列模式s2的最后一个项目所得到的序列相同，则可以将s1于s2进行连接，即将s2的最后一个项目添加到s1中剪切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选序列模式不可能是序列模式，将它从候选序列模式中删除L1C2L2C3L3C4L4……2001-8-15

8、13二、GSP算法例子：下图演示了如何从长度为3的序列模式产生长度