《序列模式挖掘》PPT课件.ppt

2001-8-15,1,第七章 序列模式挖掘,2010.4,2,内容概要,基本概念,类Apriori生成候选算法,3,一、基本概念,1.定义 序列模式概念最早由Agrawal和Srikant 提出 序列模式与关联模式相仿，但它把数据之间的关联性与时间联系起来。 例如: 如“在购买彩电的人们中，60%的人会在3个月内购买影碟机”,4,例子1：在两年前购买了Ford 牌轿车的顾客，很有可能在今年采取贴旧换新的购车行动 例子2：在购买了自行车和购物篮的所有客户中，有70%的客户会在两个月后购买打气筒,基本概念,5,返回,6,符号化表示： 项目(Item)： -如前所示，顾客购买的商品就是项目 项目集(Itemset): -各种项目组成的集合 序列(Sequence): 不同项目集的有序排列，序列s可以表示为: s = ，s j (1 ,基本概念,7,序列的元素(Element): -如 S1= 序列的长度 -一个序列包含的所有项目的个数 长度为l的序列记为l-序列,基本概念,8,序列 属于序列 如果存在整数 i1 ,基本概念,例如 ,9,思考: 是否属于? 注意:并不属于,反之亦然 因为后者代表项目3及5,是购买一个之后购买另外一个，而前者是代表两个一起购买,基本概念,10,序列在序列数据库S中的支持数为序列数据库S中包含序列的序列个数，记为Support() 给定支持度阈值，如果序列在序列数据库中的次数不低于，则称序列为序列模式 长度为l的序列模式记为l-模式,基本概念,11,例子3：设序列数据库如下图所示，并设用户指定的最小支持度min-support = 2。,序列是否的子序列?,基本概念,-是 序列是长度为3的序列模式(10, 30),12,例子4:对于开始的数据表，可以得到它的客户序列如下,基本概念,13,设最小支持度为25%，即最小支持计数（5x25%=1.25，取上整为2） 可以看出两个序列满足最小支持度 不满足最小支持度的序列之一是,基本概念,14,2. 应用领域： 客户购买行为模式预测 Web访问模式预测 疾病诊断 自然灾害预测 DNA序列分析 故障诊断系统 ,基本概念,15,应用案例1：客户购买行为模式分析,B2C电子商务网站可以根据客户购买纪录来分析客户购买行为模式，从而进行有针对性的营销策略。,图书交易网站将用户购物纪录整合成用户购物序列集合,得到用户购物行为序列模式,相关商品推荐：如果用户购买了书籍“UML语言”, 则推荐“Visio2003实用技巧”,16,应用案例2：Web访问模式分析,大型网站的网站地图(site map)往往具有复杂的拓扑结构。用户访问序列模式的挖掘有助于改进网站地图的拓扑结构。比如用户经常访问网页web1然后访问web2,而在网站地图中二者距离较远，就有必要调整网站地图，缩短它们的距离，甚至直接增加一条链接。,Index 网站入口,web1,web2,17,应用案例3：疾病诊断,医疗领域的专家系统可以作为疾病诊断的辅助决策手段。 对应特定的疾病，众多该类病人的症状按时间顺序被记录。自动分析该纪录可以发现对应此类疾病普适的症状模式。 每种疾病和对应的一系列症状模式被加入到知识库后，专家系统就可以依此来辅助人类专家进行疾病诊断。,18,应用案例3：疾病诊断,例: 通过分析大量曾患A类疾病的病人发病纪录，发现以下症状发生的序列模式： 如果病人具有以上症状，则有可能患A类疾病,19,应用案例4：查询扩展,查询扩展是搜索领域一个重要的问题。用户提交的查询往往不能完全反映其信息需求。一些研究工作尝试用用户的查询序列模式来辅助原始查询，其主要思想是： 1）挖掘用户的查询序列模式 2）用这些序列模式构造查询词关系图 3）找到每个极大全连通图作为一个”概念” 4) 对于一个查询，和它同处于一个”概念”的查询可以作为查询扩展的选项,20,应用案例4：查询扩展,给定一组查询模式：, , 查询关系图如上图：,概念1：汽车品牌,概念2：汽车,21,3. 问题描述： 给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式 4. 系统规定： 由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列,基本概念,22,二、序列模式挖掘算法,1、序列模式挖掘的5个阶段 排序阶段 发现频繁项集阶段 转换阶段 序列阶段 最大阶段,23,(1) 排序阶段 利用客户标识customer-id作为主关键字以及事务发生时间transaction-time作为次关键字对数据库D排序 该步骤将原始的事务数据库转换成客户序列的数据库,序列模式挖掘算法-排序,24,25,由客户标识及交易发生的时间为关键字所排序的数据库,排序阶段,26,客户序列描述数据库,频繁项集分别是(C)、(D)、(G)、(D,G)和(H),(2) 发现频繁项集阶段,27,转换后的数据库（客户序列）,(3)转换阶段,28,需要将每一个顾客序列转换成一个替换的代表 在一个已经转换的客户序列中，每一个事务被包含于该事物中的所有频繁项目集来替换 如果一个序列不包含任何频繁项目集，则在已经转换的序列中就不应该保留这项事务,转换规则,29,AprioriAll, AprioriSome算法 FreeSpan，PrefixSpan算法,(4) 序列阶段 (5) 最大阶段,2.核心算法,30,序列阶段算法,给出的算法分为两个系列： count-all和count-some 通用结构是遍历数据多遍，在每一遍都利用一个频繁序列的种子集合作为开始，利用种子集合来产生新的潜在频繁序列，称作候选序列(Candidate Sequence),31,两个系列,count-all AprioriAll算法 count-some AprioriSome算法和DynamicSome算法,32,类Apriori算法-AprioriAll算法,在每一遍中都利用前一遍的频繁序列产生候选序列，然后在完成遍历整个数据库后测试它们的支持度。 遍历结束时，候选者的支持度用来确定频繁序列。 在第一遍, 输出用来初始化1序列模式的集合,33,AprioriAll候选序列的产生,(1) 首先进行 Lk-1 与 Lk-1 的连接运算 比如与连接成为 要注意的是和是两个序列 (2)其次进行修剪 对于一个连接过后的序列，如果它的任意一个子列不在Lk-1 中，那么删除该序列，这个过程称为修剪,34,产生候选序列示例,序列 支持度 连接结果 2 2 3 2 2 修剪后得到最后结果,35,应用AprioriAll算法例子（一）,例：如下给出一个数据库（转换阶段已经完成），最小支持度是40%，如下为客户序列 ,36,应用AprioriAll算法例子（二）,序列 支持度 4 2 4 4 2 1序列模式,37,应用AprioriAll算法例子（三）,序列 支持度 2 4 2 2,38,应用AprioriAll算法例子(四),序列 支持度 2 2 3 2 2 3序列模式,39,应用AprioriAll算法例子（五）,序列 支持度 2 4序列模式 至此算法结束，得到结果最大序列,40,类Apriori算法有以下缺点： 有可能生成庞大众多的候选序列 多遍扫描数据库 不易发生长度较大的序列模式,序列模式越长，所需要生成的序列就越多。,41,序列模式 VS 关联规则,42,PrefixSpan算法,相关定义 前缀：设每个元素中的所有项目按照字典序排列。给定序列 = ， = (mn) ，如果ei = ei (i m - 1)， em em，并且(em - em)中的项目均在em中项目的后面， 则称是的前缀,43,投影：给定序列和 ，如果是的子序列，则关于的投影必须满足： 是的前缀，是的满足上述条件的最大子序列 后缀： 序列关于子序列 = 的投影为 = (n = m)，则序列关于子序列的后缀为， 其中em” = (em - em),44,三、PrefixSpan算法,例子： ,a(ab),a(abc),45,三、PrefixSpan算法,算法描述： 扫描序列数据库，生成所有长度为1的序列模式 根据长度为1的序列模式，生成相应的投影数据库 在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生长度为1的序列模式为止,S,S1 ,Sm,S11 ,S1n ,Sm1 ,Smp ,46,三、PrefixSpan算法,扫描序列数据库S，产生长度为1的序列模式有： : 4, :4, : 4, : 3, : 3, : 3 序列模式的全集必然可以分为分别以，和为前缀的序列模式的集合，构造不同前缀所对应的投影数据库，结果如下页图所示 分别对不同的投影数据库重复上述过程，直到没有新的长度为1的序列模式产生为止,47,三、PrefixSpan算法,48,三、PrefixSpan算法,定义1. 投影数据库：设为序列数据库S中的一个序列模式，则的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S| 定义2. 投影数据库中的支持数：设为序列数据库S中的一个序列模式，序列以为前缀，则在的投影数据库S|中的支持数为S|中满足条件 .的序列的个数,49,三、PrefixSpan算法,PrefixSpan算法 输入：序列数据库S及最小支持度阈值min_sup 输出：所有的序列模式 方法：调用子程序PrefixSpan(, 0, S),50,三、PrefixSpan算法,子程序PrefixSpan(, L, S|) 参数： . 一个序列模式 L. 序列模式的长度 S| . 如果为空，则为S，否则为的投影数据库 扫描S|，找到满足下述要求的长度为1的序列模式b： b可以添加到的最后一个元素中并为序列模式 可以作为的最后一个元素并为序列模式 对每个生成的序列模式b，将b添加到形成序列模式，并输出 对每个,构造的投影数据库S| ,并调用子程序PrefixSpan(, L + 1, S|),51,三、PrefixSpan算法,PrefixSpan算法分析： PrefixSpan算法不需要产生候选序列模式，从而大大缩减了检索空间 相对于原始的序列数据库而言，投影数据库的规模不断减小 PrefixSpan算法的主要开销在于投影数据库的构造,52,三、PrefixSpan算法,PrefixSpan算法的主要改进： 逐层投影：使用隔层投影代替逐层投影，从而可以有效减小投影数据库的个数 伪投影：当序列数据库可以直接放入内存时，可以使用伪投影操作代替实际的投影数据库，从而可以有效减少构造投影数据库的开销,53,三、PrefixSpan算法,隔层投影的例子： 扫描序列数据库，产生所有长度为1的序列模式 再次扫描序列数据库，构造如下图所示的下三角矩阵，得到所有长度为2的序列模式 构造长度为2的序列模式所对应的扫描数据库，然后对每个投影数据库，重复上面的操作，直到没有新的序列模式产生为止,54,三、PrefixSpan算法,伪投影：当数据库可以直接放入内层时，并不需要构造所有的序列模式对应的投影数据库，我们可以使用指向数据库中序列的指针及其偏移量作为伪投影 例子：假设上述序列数据库可以放入内层，在构造a投影数据库时，序列 S1 = 所对应的伪投影为：一个指向S1的指针，指针偏移设定为2。同样的，