AprioriAll

基本思想

在每一次扫描(pass) 数据库时,利用上一次扫描时产生的大序列生成候选序列,并在扫描的同时计算它们的支持度( support) ,满足支持度的候选序列作为下次扫描的大序列。第1 次扫描时,长度为1 的频繁序列模式作为初始的大1 —序列。

算法思路

1) 排序阶段 利用客户标识customer 2id作为主关键字以及事务发生的时间transaction 2 time作为次关键字对数据库D排序,该步骤将原始的事务数据库转换成客户序列的数据库.

2) 发现频繁项集阶段 利用关联规则挖掘算法找出所有的频繁项目集.

3) 转换阶段 在已经转换的客户序列中,每一个事务被包含于该事物中的所大项目集来替换,如果一个序列不包含任何大项目集,则在已经转换的序列中不应该保留这项事务.

4) 序列阶段 利用核心算法找出所有的序列模式.

算法实现

AprioriAll算法

输入：大项集阶段转换后的序列数据库

输出：所有最长序列

(1) L1={large1- sequence}；//大项集阶段得到的结果

(2) For（k=2；Lk-1≠0；k++）do begin

(3) Ck=Candidate – generate（Lk-1）//Ck是从Lk-1中产生的新的候选者

(4) For each customer – sequence c in thedatabase do//对数据库中的每一个顾客序列c

(5) Increment the count of all candidates in Ck that arecontained in c；//对包含于c中Ck内的所有候选者计数

(6) Lk=Candidates in Ckwithminimumsuport；//Lk为Ck中满足最小支持度的候选者

(7) End

(8) Answer=Maximal Sequences in ∪kLk

其中候选集生成算法Ck=Candidate –generate（Lk-1）如下：

输入：所有的大（k – 1）序列的集合

输出：候选Ck

(1) Insert into Ck//首先进行Lk-1与Lk-1的连接运算

select p.litemset1,…,p.litemseti-1,q.litemseti-1

from LK-1p,Lk-1q//p和q是Lk-1 中两个不同的序列串

wherep.litemset1=q.litemset1,…,

p.litemsetk-2=q.litemsetk-2;