• AprioriAll, AprioriSome算法 • FreeSpan，PrefixSpan算法
AprioriAll算法
• 基本思想
AprioriAll算法
客户号
客户序列
1
<{1 5}{2}{3}{4}>
2
<{1}{3}{4}{3 5}>
3
<{1}{2}{3}{4}>
4
<{1}{3}{5}>
5
<{4}{5}>
AprioriAll算法
L1
1-序列
支持度
<1> 4 <2> 2 <3> 4 <4> 4 <5> 4
L2
2-序列
<1 2> <1 3> <1 4> <1 5> <2 3> <2 4> <3 4> <3 5> <4 5>
支持度
2 4 3 3 2 2 3 2 2
AprioriAll算法
序列包含的所有项的个数称为序列的长度。长度
为l 的序列记为l -序列。
子序列ቤተ መጻሕፍቲ ባይዱ
定义2(子序列)：序列T＝<ti1ti2…tim>是另一 个序列S＝<s1s2…sn>的子序列，满足下面条 件：对于每一个j，1<=j<=m-1，有ij<ij+1 且 对于每一个j，1<=j<=m，存在1<=k<=n， 使得tijsk。即序列S包含序列T。用符号“” 表示“被包含于”，序列T是序列S的子序列可 记为TS。称T为S的子序列，S为T的超序列。
2
A，B
5
H
2
C
2
D，F，G
4
C
3
C，E，G
1
C
1
H
4
D，G
4
H
排序阶段
客户标识
1 1
2 2 2 3
4 4 4 5
交易时间
June 25’04 June 30’04
June 10’04 June 15’04 June 20’04 June 25’04
June 25’04 June 30’04 July 25’04 June 12’04
频繁序列模式
定义4（频繁序列模式）：给定正整数为支持 度阈值，如果数据库中最少有个元组包含序列 S，即support（S）>=，则称序列S为序列 数据库D中的一个（频繁）序列模式。
长度为l 的序列模式称为l –模式。
序列模式挖掘的任务就是找出数据库中所有的 序列模式，即那些在序列集合中出现频率超过 最小支持度（用户指定最小支持度阈值）的子 序列。
序列
报告人：熊 赟
内容概要
基本概念 类Apriori生成候选算法 FreeSpan算法,PrefixSpan算法 相似性搜索 其他
第6章 序 列
6.1 基本概念 6.2 原 理 6.3 核心算法 6.4 其 他
序列
序列是不同项集的有序排列。
定义1(序列)：I=｛i1i2…im｝是项集，ik （1<=k<=m）是一个项，序列S记为S＝ <s1s2…sn>，其中sj（1<=j<=n）为项集（也称 序列S的元素），即sjI。每个元素由不同项组成。 序列的元素可表示为（i1i2…ik），若一个序列只 有一个项，则括号可以省略。
序列模式挖掘阶段
•排序阶段 •发现频繁项集阶段 •转换阶段 •序列阶段 •最大阶段
交易发生的时间 客户标识 购买项
June 10’04 June 12’04 June 15’04 June 20’04 June 25’04 June 25’04 June 25’04 June 30’04 June 30’04 July 25’04
(D,F,G) >
3
< (C,E,G) >
<{(C),(G)}>
<{1,3}>
4
< (C) (D,G) (H) > <{(C)}{(D),(G),(D,G)}{( <{1}{2,3,4}{5
< (H) >
H)}>
}>
5
<{(H)}>
<{5}>
转换后的数据库（客户序列）
核心算法
•序列阶段 •最大阶段
购买项
C H
A,B C D,F,G C,E,G
C D,G H H
由客户标识及交易发生的时间为关键字所排序的数据库
客户 号
客户序列
1
< (C) (H) >
2
< (A,B) (C)
3
(D,F,G) >
4
< (C,E,G) >
5 < (C) (D,G) (H) >
< (H) >
频繁项 集
(C) (D) (G) (DG) (H)
AprioriSome算法
next(last)=2k
L1
1-序列
支持度
<1> 4 <2> 2 <3> 4 <4> 4 <5> 4
L2
2-序列
<1 2> <1 3> <1 4> <1 5> <2 3> <2 4> <3 4> <3 5> <4 5>
L3
3-序列
<1 2 3> <1 2 4> <1 3 4> <1 3 5> <2 3 4>
支持度
2 2 3 2 2
L4
4-序列
<1 2 3 4>
支持度
2
AprioriAll算法
最大的频繁序列
序列
<1 2 3 4> <1 3 5> <4 5>
支持度
2 2 2
AprioriSome算法
• 基本思想： • 算法分为两个阶段： • 前阶段：只对一定长度的序列计数 • －－next（k）函数 即Ck生成Lk • 后阶段： • 对前阶段已确定的Lk确定为最大序列 • 对前阶段没有生成Lk，先删除所有在Ck中 包含在Li中的序列，再对Ck计数生成Lk。
序列关联规则
定义5: （序列关联规则）对于给定 的项集I=｛i1i2…im｝以及序列S,T， 形如ST的表达式称为序列关联规则。
序列关联规则
支持度 置信度
序列关联规则ST的置信度 序 是 总 记 的列 支 顾 为 顾关 持 客 （ 客联 序 数 数）规 列 之 与，则 比 仅S和是。支ST支持的T持的S顾的序支客顾列持数客S度占和数T 之比。
若一个序列S不包含在任何其他的序列之中，则 称序列S是最大的。
序列支持度
定义3（支持度）：序列数据库D是元组<sid， S>的集合，sid为序列标识号，如果序列T 是S的子序列（即TS）称元组<sid,S>包 含序列T；则序列T在序列数据库D中的支持 度是数据库中包含T的元组数，即 supportD(T)＝ |{<sid,S>|<sid,S>DTS }|记作 support（T）。
映射
1 2 3 4 5
频繁项集分别是(C)、(D)、(G)、(D,G)和(H) 客户序列描述数据库
发现频繁项集阶段
转换阶段
客户标识
原始客户序列
转换后客户序列
映射后序列
1
< (C) (H) >
<{(C)}{(H)}>
<{1}{5}>
2
< (A,B) (C)
<{(C)}{(D),(G),(D,G)}> <{1}{2,3,4}>