一种基于投影数据库的SPAM算法

摘要:序列模式挖掘是数据挖掘的重要分支,关于序列模式挖掘的算法非常多,SPAM算法就是序列模式挖掘算法的一种,Perfixspan算法(基于投影的算法)也是序列模式挖掘算法的一种。SPAM算法和Perfixspan算法各有优缺点。研究这两种算法的基础上给出了一种结合这二种算法优点进行改进的算法。

关键词:SPAM算法;Perfixspan算法;序列模式;数据挖掘

中图分类号:TP311文献标识码:A 文章编号:1009-3044(2010)07-1537-03

An Algorithm of SPAM Based on Projected Database

CHEN Jing-qiang, WENG Zheng-qiu

(City College, Wenzhou University, Wenzhou 325035, China)

Abstract: Sequence pattern mining is an important part of Data Mining, and there are many algorithms on it. The algorithm of SPAM is one of most efficient algorithms, so as that of Perfixspan. SPAM and Perfixspan have their advantages and disadvantages respectively. Both algorithms is studied and a new efficient one is proposed.

Key words: SPAM; perfixspan; sequence mining; data mining

数据库中知识发现所感兴趣的数据中,有一类属于所谓的序列数据,即有序事件序列数据,如常见的时间和空间序列关系。数据间的序列关系中经常隐藏着有价值的信息。如证券市场上随时间变动的交易价格,存在着某些局部规律,掌握这些规律可以指导证券交易的参与者。关于序列模式挖掘算法,国内外很多人提出了不同的算法,其中最经典的是AprioriAll、Apriorisome、Dynamicsome三种算法[1],都基于Apriori性质,将Apriori改造而成使用序列模式挖掘应用的算法。之后又有AprioriAll的改进算法GSP,其时间效率大幅提高,候选集大幅减少。此外,文献[2]中提出了基于垂直数据库的SPADE算法、文献[3]中提出了基础投影的Prefixspan算法,首次将前缀以及投影的概念引入到了序列模式挖掘领域,通过实验和理论验证它可以发现数据库用户序列支持。

本文简要介绍基于垂直数据库的SPAM算法和基于投影数据库的PerfixSpan,文章的重点内容是将投影数据库的思想引入到SPAM算法,对SPAM算法进行改进,使其算法效率能在一定程度上提高。

1 关于SPAM算法

Ayres在文献[4]中提出的算法SPAM(Sequential Pattern Mining using Bitmap Representation),将文序列的表示方式和网格划分概念加以融合,将序列的表示改为了垂直位图的表示方式,更加便于统计序列的用户支持度。

算法在首次扫描数据库时,为数据库中的每一个项建立一个纵向的位图。每一项的位图中按用户ID排序,如果该项在用户序列的某位置上出现,则位图中对应该位置的位上置为1,否则置为0。序列的大小是指序列中包含的项集的个数,即同一用户的事务个数。如果序列大小在2k+1和2k+l的范围内,则其在数据库中对应的位图用2k+l位表示,K的最小值为1。即无论序列的长度是小于还是等于4,在数据库的位图表示中都是用的4位。

例如,用SRAM算法对表1中顾客序列数据库S进行初始化。

为表1进行SPAM算法处理,把它用位图表示如表2所示。

c001有4个项集,因此用4位二进制表示,c002只有3个项集,所以用4位二进制表示。

现设最小支持度为2,只要统计某项的1的个数就可以得出该项的支持度了,上表中a的支持度为4,b为1,c为3,d为2,所以只有b是不频繁的。在进行连接的时候也只对两个都是频繁项进行连接。比如,a和c两项都是频繁的项,可以对两项进行连接,连接的方式有两种,一种是序列扩展,简称SES,如对a和c进行连接时,序列扩展可以扩展成(a)(c),这种是序列扩展的方式;另一种是项扩展,简称IES,如对a和b进行项扩展,扩展的结果是(ac);以上就是2中连接的方式,在进行连接时要对这2种连接的方式分别考虑。

在对a和c这两个频繁项进行SES扩展时,a和c不能在同一个项集,并且c必须排在a的后面,c001和c002中都有满足条件的项,如c001中a出现在第一个项集中,c出现在第2个项集中;c002中a出现在第一个项集中,c出项在第二个项集中,因此可以进行项扩展。所以(a)(c)的支持度是2,(a)(c)是频繁的。

在对a和c进行IES扩展时,a和c必须出现在同一个cid的同一个项集中,c001中找不到这样的项集;c002中的第二个项集满足条件,一次(ac)的支持度是1

可以通过这种方法不断地进行扩展,找出所有的频繁项集。

2 关于PerfixSpan算法

Pei等在文献[3]中提出了基础投影的Prefixspan算法,在该算法首次将前缀以及投影的概念引入到了序列模式挖掘领域。Prefixspan算法通过实验和理论的验证可以发现数据库用户序列支持的所有的频繁序列,而且同时又极大的减小了在生成候选序列时的系统开销。更值得一提的是,Prefixspan算法在利用投影将原数据库进行分割的方式明显的提高了挖掘数据库序列模式的效率,所以目前而言,在需要对大型的序列数据库做序列模式挖掘的时候,Prefixspall算法以其在性能及效率等方面的优势都可能作为首选算法考虑。

1) 前缀

两个序列A=,B=,m

2) 投影

序列A和序列B,当且仅当B是A的一个前缀,C是A的子序列且也满足以B为前缀,而且对C而言不存在超序列D也是A的子序列且也以B为前缀,那么就称C是A关于B的投影。如A={(a)(a,b,c)(a,e)(d)},B={(b,c)},A关于B放入投影就是{(a,e)(d)}

Prefixspan算法与之前所有的算法不同之处在于,它并不以原数据库为参考来考虑所有可能出现的频繁序列。而只检验前缀序列是否频繁,如果前缀频繁,则把其相应的后缀序列建成投影数据库。同样在每个投影数据库中,只检查该投影数据库中前缀序列是否频繁,如此递归,整个过程中不需要生成候选序列。而且通过Prefixspan算法中的递归过程,前缀在不断的扩展,以此可以产生序列数据库中所有的频繁序列。

Prefixspan算法的执行步骤可以描述如下:1)对序列数据库扫描一次得到全部频繁项目n,即所有长度为1的频繁序列集合。2)将频繁序列完整的集分为n个具有不同前缀的频繁序列的子集。3)通过构造相应的投影数据库并在其中递归地挖掘发现频繁序列的子集。

对于表1中的数据库,考虑频繁项a和c的投影数据库如表3和表4所示:

表3 频繁项a的投影数据库

表4 频繁项c的投影数据库

3 利用PerfixSpan数据库投影的方法对SPAM算法进行改进

SPAM算法在其生成的位图能一次性存放到内存的时候效率是非常高的,但是这种假设对于大型的数据库或者是用户序列的长度大的时候,效率不是很高的。所以SPAM算法在实践中仍然具有局限性。因此我们考虑采用投影数据库的方法对SPAM算法进行改进,不以原数据库为参考来考虑所有可能出现的频繁序列。而只检验前缀序列是否频繁,如果前缀频繁,则把以其为前缀的投影建成投影数据库。同样在每个投影数据库中,只检查该投影数据库中前缀序列是否频繁,如此递归,整个过程中不需要生成候选序列。而且通过这种方法的递归过程,前缀在不断的扩展,以此可以产生序列数据库中所有的频繁序列。

对于之前的例子,a是一个频繁项,现在要对a进行扩展,首先求出a的投影数据库,如表5所示。

然后再对这个投影数据库生成SPAM算法用到的位图,如表6所示。

然后根据这个位图表求出频繁项,可以得知a(出现3次),c(出现3次)是频繁项,又知道这个投影数据库是以a为前缀的,所以进行SES扩展后{(a)(a)},{(a)(c)}是频繁项;再在此基础上对a进行投影得到表7。

然后再对这个投影数据库生成SPAM算法用到的位图,如表8所示。

根据这个位图表得知c是频繁项,又知前缀是{(a)(a)},进行IES扩展后结果为{(a)(ac)}。以下是这个算法的伪代码:

算法:Spam_Perfix算法结合投影数据库的方法对Spam算法进行改进

输入:S―投影数据库,初始为原始数据库;A―前缀;Min_sup――最小支持度

输出:Result―频繁序列集

Spam_Perfix(S,A,min_sup,Result)

Begin

找出S中的的频繁项B

If(B为空)返回

ForB中的每个频繁项bi

Begin

对A加上bi进行扩展得到A_,加入Result

在S上求以bi为前缀的投影数据库S_

Call SPAM_Prefix(S_,A_,min_sup,Result)

End

End

4 实验测试结果

本文采用www.cs.washington.edu/ai/adaptive-data/上的数据分别对改进后的算法和SPAM算法进行比较,图1是分别用两组不同数据测试后的结果:

图1 分别使用两组数据的测试结果

5 总结

SPAM算法是一种高效的序列模式挖掘算法,但是缺点是只在数据库能完全放入内存时效率较高,当数据库不能完全放入内存时效果就相对来说差点,本文为了解决这个问题,研究了PerfixSpan的投影数据库的方法,并将这种方法应用到了SPAM算法中来,投影数据库的好处是在处理过程中数据库是不断减小的,这种方法非常好地克服了SPAM算法对内存要求高的缺点。

参考文献:

[1] Agrawal R, Srikant R. Mining Sequential Patterns[J].In: Proc of the 11st lnt Conf. On Data Engineering.TaiPei,1995,3-14.

[2] Zaki M J, SPADE. An Efficient Algorithm for Mining Frequent Sequences[J], Machine Learning42(l),2001:31-60.

[3] Pei J, Han J W, Pinto H, et al. Prefix Span: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth[J]. Proceedings of IEEE Conference on Data Engineering,2001:215-224.

[4] Bonfield J W, Steden R. ZTR:A New Format NA Sequence Trace Data[J],2002:3-10.

[5] 张娥,冯秋红,宣慧玉,等.Web使用模式研究中的数据挖掘[J].计算机应用研究,2001(3).

[6] 陈宝树,党齐民.Web数据挖掘中的数据预处理[J].计算机工程,2002(7).

[7] 何炎祥,孔维强,向剑文,等.WebLog访问序列模式挖掘[J].计算机工程与应用,2003(27).

[8] 易明.基于Web挖掘的电子商务个性化推荐机理与方法研究[D].华中科技大学,2006.