序列及apriori生成候选算法

《序列及apriori生成候选算法》由会员分享，可在线阅读，更多相关《序列及apriori生成候选算法（48页珍藏版）》请在金锄头文库上搜索。

1、序 列,报告人：熊 赟,内容概要,基本概念,其他,类Apriori生成候选算法,相似性搜索,FreeSpan算法,PrefixSpan算法,第6章 序 列,6.1 基本概念 6.2 原 理 6.3 核心算法 6.4 其 他,序列是不同项集的有序排列。 定义1(序列)：I=i1i2im是项集，ik（1，其中sj（1=j=n）为项集（也称序列S的元素），即sjI。每个元素由不同项组成。序列的元素可表示为（i1i2ik），若一个序列只有一个项，则括号可以省略。 序列包含的所有项的个数称为序列的长度。长度为l 的序列记为l -序列。,序 列,定义2(子序列)：序列T是另一个序列S的子序列，满足下面条件

2、：对于每一个j，1=j=m-1，有ijij+1 且 对于每一个j，1=j=m，存在1=k=n，使得tijsk。即序列S包含序列T。用符号“”表示“被包含于”，序列T是序列S的子序列可记为TS。称T为S的子序列，S为T的超序列。 若一个序列S不包含在任何其他的序列之中，则称序列S是最大的。,子 序 列,定义3（支持度）：序列数据库D是元组的集合，sid为序列标识号，如果序列T是S的子序列（即TS）称元组包含序列T；则序列T在序列数据库D中的支持度是数据库中包含T的元组数，即supportD(T)|DTS |记作support（T）。,序列支持度,定义4（频繁序列模式）：给定正整数为支持度阈值，如

3、果数据库中最少有个元组包含序列S，即support（S）=，则称序列S为序列数据库D中的一个（频繁）序列模式。 长度为l 的序列模式称为l 模式。 序列模式挖掘的任务就是找出数据库中所有的序列模式，即那些在序列集合中出现频率超过最小支持度（用户指定最小支持度阈值）的子序列。,频繁序列模式,定义5: （序列关联规则）对于给定的项集I=i1i2im以及序列S,T，形如ST的表达式称为序列关联规则。,序列关联规则,置信度,支持度,序列关联规则,序列关联规则ST的支持度 是支持序列S和T的顾客数占 总顾客数之比。,序列关联规则ST的置信度 记为（），是支持序列S和T 的顾客数与仅支持S的顾客数 之比。

4、,序列模式挖掘阶段,排序阶段 发现频繁项集阶段 转换阶段 序列阶段 最大阶段,由客户标识及交易发生的时间为关键字所排序的数据库,排序阶段,客户序列描述数据库,频繁项集分别是(C)、(D)、(G)、(D,G)和(H),发现频繁项集阶段,转换后的数据库（客户序列）,转换阶段,核心算法,AprioriAll, AprioriSome算法 FreeSpan，PrefixSpan算法,序列阶段 最大阶段,AprioriAll算法,基本思想,AprioriAll算法,AprioriAll算法,L1,L2,AprioriAll算法,L3,L4,AprioriAll算法,最大的频繁序列,AprioriSome

5、算法,基本思想： 算法分为两个阶段： 前阶段：只对一定长度的序列计数 next（k）函数 即Ck生成Lk 后阶段： 对前阶段已确定的Lk确定为最大序列 对前阶段没有生成Lk，先删除所有在Ck中包含在Li中的序列，再对Ck计数生成Lk。,AprioriSome算法,L1,L2,next(last)=2k,AprioriSome算法,C3,C4,修剪,AprioriSome算法,C5为空结束前阶段进入回溯阶段,删除了L4的子序列后的C3 再计数发现是最大3序列,L4,AprioriSome算法,最大的频繁序列,除以外L2中所有的序列都被删除 L1中所有的序列都被删除,类Apriori算法有以下缺点

6、： 有可能生成庞大众多的候选序列。 多遍扫描数据库。 不易发生长度较大的序列模式。序列模式越长，所需要生成的序列就越多。,FreeSpan算法频繁模式投影的序列模式挖掘 Frequent pattern-projected Sequential pattern mining,基本思想（基于数据库投影和分片技术） 利用频繁项递归地将序列数据库投影到更小 的投影数据库集中，在每个投影数据库中生 成子序列片段。,FreeSpan算法,序列数据库 最小支持度设为2,FreeSpan算法,1.找到频繁项集L1 频繁项按支持度降序排列形成频繁项列表， f_list= 根据f_list，序列模式集被分为不相

7、交的六个子集：1）只包含项f； 分而自治策略,FreeSpan算法,2.A.构造频繁项矩阵F用于生成长度为2的序列模式，投影数据库集用于生成长度为3及更长的序列模式 F是一个三角矩阵Fj,k（1jm，1kj）。其中Fj,j（1jm）仅有一个计数值，而其他每个Fj,k（1jm，1kj）有三个计数值：（A,B,C）,序列模式的投影数据库是含有的序列集的子序列，非频繁项及后的项也被删除。,F矩阵图,1b,2c,3a,4d,5e,6f,1b,2c,3a,4d,5e,6f,Fj,j 仅有一个计数值， Fj,k 有三个计数值：（A,B,C） ,序列 ,FreeSpan算法,2.B.生成长度为2的序列模式

8、标记循环项模式和投影数据库；,循环项模式标记形如$ij$，其中$表示两种形式，。 投影数据库标记形如$ij$：bp,bq，bp,bq表示在子序列挖掘过程中与$ij$合在一起生成长度更长的序列模式的频繁项集。,FreeSpan算法,FreeSpan算法,2.C.再次扫描数据库S，生成循环项模式和投影数据库； b+ f+ b+ d :2,:2,:2,:2, :2,:2,:2,:2, :2,:2,:2 四个投影数据库如下图：,FreeSpan算法,2.D.对生成的投影数据库递归调用矩阵投影挖掘算法挖掘更长的候选模式。,FreeSpan算法：给定序列数据库S及最小支持度阈值。 1. 扫描序列数据库S，

9、找到S中的频繁项集，并以降序排列生成f_list列表。 2. 执行下面步骤： a. 第一遍扫描数据库S，构造频繁项矩阵； b. 生成长度为2的序列模式及标记循环项模式和投影数据库； c. 再次扫描数据库S，生成循环项模式和投影数据库； d. 对生成的投影数据库递归调用矩阵投影挖掘算法挖掘更长的候选模式。,PrefixSpan算法（通过前缀投影挖掘序列模式） Prefix-projected Sequential pattern mining,基本思想：序列数据库投影时，并不考虑所有可能出现的频繁子序列，而只检验前缀序列，然后把相应的后缀序列投影成投影数据库。每个投影数据库中，只检查局部频繁模式

10、。 不需要生成候选序列。,例： ,前缀：给定序列 = ， = (mn) ，如果ei = ei (i m - 1)， em em，并且(em - em)中的项目均在em中项目的后面， 则称是的前缀.,投影：给定序列和，其中是的子序列，即。的子序列（），被称为关于前缀的投影，当且仅当1）是的前缀2）不存在的超集/（即 /， /），使得/是的子序列并且是/的前缀。,后缀： 序列关于子序列 = 的投影为 = (n = m)，则序列关于子序列的后缀为， 其中em” = (em - em),算法描述： 扫描序列数据库，生成所有长度为1的序列模式 根据长度为1的序列模式，生成相应的投影数据库 在相应的投影数

11、据库上重复上述步骤，直到在相应 的投影数据库上不能产生序列模式为止,S,S1 ,Sm,S11 ,S1n ,Sm1 ,Smp ,PrefixSpan算法,PrefixSpan算法,定义1. 投影数据库：设为序列数据库S中的一个序列模式，则的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S| 例： 投影数据库，由4个后缀序列组成：，。 投影数据库, ,PrefixSpan算法,PrefixSpan算法,查找长度为1的序列模式 :4,:4,:4,:3,:3,:3 分割搜索空间序列模式集可按6个前缀被划分为六个子集：1）包含前缀的子集；6）包含前缀的子集。 寻找序列模式的子集。构建并递归挖掘投影

12、数据库。,PrefixSpan算法,寻找具有前缀的序列模式。 投影数据库，由4个后缀序列组成：，。 扫描投影数据库一遍，找到含有前缀的长度为2的序列模式，包括：2，：4，：2，：4，：2，：2。 递归，所有具有前缀的序列划分为6个子集：1）包含前缀的子集；6）包含前缀的子集,投影数据库：。不产生任何频繁子序列，结束。 投影数据库：，包含前缀的序列模式有：，。 即， ， 投影数据库：，。序列模式：，（即，）。 ，投影数据库，投影数据库 投影数据库：， 包含前缀的序列模式有： 找到含有前缀的序列模式，包括：,子程序PrefixSpan(, L, S|) 参数： ：一个序列模式 ；L：序列模式的长度 S| ： 如果不为空时，为投影数据库，否则为投影数据库S， 1 扫描S|，找到频繁项b，b满足： a)b可以作为的最后一个元素，形成一个序列模式；或者 b) 可以追加到上，形成一个序列模式。 2）对于每个频繁项b，追加到上，形成一个序列模式，输出； 3）对于每个，构建投影数据库S|，调用PrefixSpan(,l+1,S|)。,PrefixSpan算法分析： PrefixSpan算法不需要产生候选序列模式，从 而大大缩减了检索空间 相对于原始的序列数据库而言，投影数据库 的规模不断减小 PrefixSpan算法的主要开销在于投影数据库的 构造,PrefixSpan算法,谢 谢！,