序列模式挖掘（AprioriAll和AprioriSome算法）

序列模式（sequential pattern）挖掘最早由Agrawal等人提出，针对带有交易时间属性的交易数据库，获取频繁项目序列以发现某段时间内客户的购买活动规律。每一次交易包含customer-id，transaction-time和items（购置的商品内容）。

定义1 一个序列（sequence）是项集的有序表，序列s记为 ,其中每个 是一个项集（itemset），表示多次交易的组合。项集 i (itemset)记为，其中 代表一个项（item），表示一次交易。一个序列的长度（Length）是它所包含的项集个数，若具有长度k，则记为K-序列。

定义2  序列 包含在(is contained in)序列中，即存在 使。例如，包含在中，因为。注意:不包含于，因为前者表示两次交易分别是(3)和(5)，后者表示一次交易有(3, 5)。

定义3 最大序列(Maximal Sequence)表示不包含在任何其他序列中。

定义4 序列s的支持度（support）是指所有序列中包含序列s的个数（百分比）。满足最小支持度(minimum support)的序列称为大序列（large sequence）。大序列中的所有最长序列就称为序列模式（sequential pattern）。

定义5  项集i的支持度是指所有序列中包含项集i的个数。因此项集i和1-序列的支持度相同。满足最小支持度的项集称为大项集（large itemset）或者litemset。注意：大序列中的所有项集必须是大项集。因此，大序列就是litemset的列表。

对数据库进行排序整理，将原始数据库转换成序列数据库。例如交易数据库就以客户号（Cust_id）和交易时间（Tran_time）来排序。例如table1到table2 。

客户号（Cust_id）

交易时间

（Tran_time）

物品

（Item）

1

1

June 25’99

June 30’99

30

90

2

2

2

June 10’99

June 15’99

June 20’99

10，20

30

40，60，70

3

June 25’99

30，50，70

4

4

4

June 25’99

June 30’99

July 25’99

30

40，70

90

5

June 12’99

90

Table 1       带交易时间的交易数据源实例

客户号（Cust_id）

顾客序列（Customer Sequence）

1

2

3

4

5