序列及Apriori生成候选算法(共48页).ppt

1、序 列 报告人：熊 赟 内容概要 根本概念根本概念 其他其他 类类AprioriApriori生成候选算法生成候选算法 相似性搜索相似性搜索 FreeSpanFreeSpan算法算法,PrefixSpan,PrefixSpan算法算法 第第6 6章章 序序 列列 w6.1 根本概念w6.2 原 理w6.3 核心算法w6.4 其 他 序列是不同项集的有序排列。序列是不同项集的有序排列。 定义定义1(1(序列序列) )：I=I=i1i2imi1i2im是项集，是项集，ikik1=k=m1=k=m是一是一个项，序列个项，序列S S记为记为S S，其中，其中sjsj1=j=n1=j=n为为项集也称序列

2、项集也称序列S S的元素，即的元素，即sjsjI I。每个元素由不同项。每个元素由不同项组成。序列的元素可表示为组成。序列的元素可表示为i1i2iki1i2ik，假设一个序列，假设一个序列只有一个项，那么括号可以省略。只有一个项，那么括号可以省略。 序列包含的所有项的个数称为序列的长度。长度为序列包含的所有项的个数称为序列的长度。长度为l l 的序列的序列记为记为l -l -序列。序列。 序序 列列n定义定义2(2(子序列子序列) )：序列：序列T T是另一是另一个序列个序列S S的子序列，满足下面条件：的子序列，满足下面条件：对于每一个对于每一个j j，1=j=m-11=j=m-1，有，有i

3、jij+1 ijij+1 且且 对于对于每一个每一个j j，1=j=m1=j=m，存在，存在1=k=n1=k=n，使得，使得tijtijsksk。即序列。即序列S S包含序列包含序列T T。用符号。用符号“表表示示“被包含于被包含于，序列，序列T T是序列是序列S S的子序列可记的子序列可记为为T TS S。称。称T T为为S S的子序列，的子序列，S S为为T T的超序列。的超序列。n假设一个序列假设一个序列S S不包含在任何其他的序列之中，不包含在任何其他的序列之中，那么称序列那么称序列S S是最大的。是最大的。 子子 序序 列列定义定义3 3支持度：序列数据库支持度：序列数据库D D是是

4、元组元组sidS的集合，的集合，sidsid为序列为序列标识号，如果序列标识号，如果序列T T是是S S的子序列的子序列即即T TS S称元组称元组包含序包含序列列T T；那么序列；那么序列T T在序列数据库在序列数据库D D中中的支持度是数据库中包含的支持度是数据库中包含T T的元组的元组数，即数，即supportD(T)supportD(T)|D DT TS |S |记作记作supportsupportT T。 序列支持度序列支持度定义定义4 4频繁序列模式：给定正整数频繁序列模式：给定正整数为支持度阈值，如果数据库中最少有为支持度阈值，如果数据库中最少有个元组包含序列个元组包含序列S S

5、，即，即supportsupportS S=，那么称序列，那么称序列S S为序列数据库为序列数据库D D中的中的一个频繁序列模式。一个频繁序列模式。长度为长度为l l 的序列模式称为的序列模式称为l l 模式。模式。 序列模式挖掘的任务就是找出数据库中所有的序列模式，即那些在序列集合中出现频率超过最小支持度用户指定最小支持度阈值的子序列。序列模式挖掘的任务就是找出数据库中所有的序列模式，即那些在序列集合中出现频率超过最小支持度用户指定最小支持度阈值的子序列。 频繁序列模式频繁序列模式 序列关联规那么序列关联规那么置信度置信度支持度支持度 序列关联规那么序列关联规那么序列关联规那么ST的支持度是

6、支持序列S和T的顾客数占总顾客数之比。序列关联规那么ST的置信度记为，是支持序列S和T的顾客数与仅支持S的顾客数之比。 交易发生的时间客户标识购买项June 1004June 1204June 1504June 2004June 2504June 2504June 2504June 3004June 3004July 25042522431144A，BHCD，F，GCC，E，GCHD，GH客户标识客户标识交易时间交易时间购买项购买项11June 2504June 3004CH222June 1004June 1504June 2004A,BCD,F,G3June 2504C,E,G444Jun

7、e 2504June 3004July 2504CD,GH5June 1204H由客户标识及交易发生的时间为关键字所排序的数据库客户客户号号客户序列客户序列12345客户序列描述数据库频繁项频繁项集集映射映射(C)(D)(G)(DG)(H)12345频繁项集分别是(C)、(D)、(G)、(D,G)和(H)客户标识客户标识原始客户序列原始客户序列转换后客户序列转换后客户序列映射后序列映射后序列12345转换后的数据库客户序列 核心算法核心算法 客户号客户号客户序列客户序列12345 AprioriAllAprioriAll算法算法 1-1-序列序列支持度支持度42444L12-2-序列序列支持度

8、支持度243322322L23-3-序列序列支持度支持度22322AprioriAllAprioriAll算法算法 4-4-序列序列支持度支持度2L3L4序列序列支持度支持度222AprioriAllAprioriAll算法算法 最大的频繁序列AprioriSomeAprioriSome算法算法 AprioriSomeAprioriSome算法算法 1-1-序列序列支持度支持度42444L12-2-序列序列支持度支持度243322322L2next(last)=2k不计数AprioriSomeAprioriSome算法算法 C3C4修剪修剪AprioriSomeAprioriSome算法算法

9、C5为空结束前阶段进入回溯阶段删除了L4的子序列后的C3再计数发现是最大3序列L44-4-序列序列支持度支持度2序列序列支持度支持度222AprioriSomeAprioriSome算法算法 最大的频繁序列除以外L2中所有的序列都被删除 L1中所有的序列都被删除 FreeSpanFreeSpan算法算法频繁模式投影的序列模式挖掘频繁模式投影的序列模式挖掘 Frequent pattern-projected Sequential pattern miningFreeSpanFreeSpan算法算法 序列序列idid序列序列项项10a,b,c,d20b,c,e,f,g30a,b,f,h40b,c

10、,d,e50a,b,c,d,e序列数据库序列数据库 最小支持度设为2 FreeSpanFreeSpan算法算法 FreeSpanFreeSpan算法算法4(4,3,0)1(3,2,0) (2,1,1) 2(2,2,2) (2,2,0)(1,2,1)1(3,1,1) (1,1,2)(1,0,1)(1,1,1)1(2,2,2) (1,1,0)(1,1,0)(0,0,0) (1,1,0)21b2c3a4d5e6f1b2c3a4d5e6f序列 FreeSpanFreeSpan算法算法 FreeSpanFreeSpan算法算法项长度为2的序列模式循环项标记投影数据库标记f:2,:2,:2b+ f+ e:

11、3,:2:bd:2, :2, :2:2, :2, :2b+ d : bccd: bacb:4 FreeSpanFreeSpan算法算法 FreeSpanFreeSpan算法算法标记:b : bccd: b: b投影数据库,序列模式:2:2:2:2:2:2:2:2。PrefixSpanPrefixSpan算法通过前缀投影挖掘序算法通过前缀投影挖掘序列模式列模式Prefix-projected Sequential Prefix-projected Sequential pattern mining pattern mining 例： 前缀：给定序列前缀：给定序列 = ， = (mn) ，如果，如

12、果ei = ei (i m - 1)， em em，并且，并且(em - em)中的工程均在中的工程均在em中工程的中工程的后面，后面， 那么称那么称是是的前缀的前缀.投影：给定序列投影：给定序列 和和 ，其中，其中 是是 的子序列，即的子序列，即。 的子序列的子序列 ， 被称为被称为 关于关于前缀前缀 的投影，当且仅当的投影，当且仅当1 是是 的前缀的前缀2不不存在存在 的超集的超集 /即即 /， /，使，使得得 /是是 的子序列并且的子序列并且 是是 /的前缀。的前缀。 后缀：后缀： 序列序列 关于子序列关于子序列 = 的的投影为投影为 = (n = m)，那么序列，那么序列 关于子序列关

13、于子序列 的后缀为的后缀为， 其其中中em = (em - em)算法描述：扫描序列数据库，生成所有长度为1的序列模式根据长度为1的序列模式，生成相应的投影数据库在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生序列模式为止SS1SmS11 S1n Sm1 Smp PrefixSpanPrefixSpan算法算法 PrefixSpanPrefixSpan算法算法序列号序列号序列序列10203040n定义1. 投影数据库：设为序列数据库S中的一个序列模式，那么的投影数据库为S中所有以为前缀的序列相对于的后缀，记为S|n例： 投影数据库，由4个后缀序列组成：，。 n投影数据库,nP

14、refixSpanPrefixSpan算法算法 PrefixSpanPrefixSpan算法算法 PrefixSpanPrefixSpan算法算法 n子程序子程序PrefixSpan(PrefixSpan(, L, S|, L, S|) )n 参数：参数： ：一个序列模式：一个序列模式 ；L L：序列模式：序列模式的长度的长度 n S|S| ： 如果如果不为空时，为不为空时，为投影数据投影数据库，否那么为投影数据库库，否那么为投影数据库S S，n1 1 扫描扫描S|S|，找到频繁项，找到频繁项b b，b b满足：满足：na)ba)b可以作为可以作为的最后一个元素，形成一个序列的最后一个元素，形成一个序列模式；或者模式；或者nb)b) 可以追加到可以追加到上，形成一个序列模式。上，形成一个序列模式。n2 2对于每个频繁项对于每个频繁项b b，追加到，追加到上，形成一个序上，形成一个序列模式列模式，输出，输出；n3 3对于每个对于每个，构建，构建投影数据库投影数据库S|S|，调用，调用PrefixSpan(PrefixSpan(,l+1,S|,l+1,S|)。 前缀前缀投影（后缀）数据库投影（后缀）数据库序列模式序列模式,(_d)c(b,c)(ae),aba,ad,c,(_c)(ae