增量序列模式挖掘研究进展

◆仝 瑶

（河北工业大学计算机科学与软件学院 天津 300130）

增量序列模式挖掘研究进展

◆仝 瑶

（河北工业大学计算机科学与软件学院 天津 300130）

序列模式挖掘是数据挖掘领域的一个重要研究分支，近年来在诸多领域得到了广泛地应用。由于现实应用中序列数据库是不断地更新的，仅采用静态数据的序列模式挖掘方法，不仅效率低下，而且是对先前的挖掘结果的极大浪费。有鉴于此，提出的增量序列模式挖掘算法能够适应数据库的动态性。本文总结近几年来增量模式挖掘取得的重大成果和进展，特别分析研究了其中几个经典算法，最后对增量序列模式挖掘发展趋势进行了展望。

增量序列模式挖掘; Apriori; 投影数据库

0 前言

序列模式挖掘是数据挖掘的一个重要研究领域，最初是由Agrawal和Srikant[1]两名研究者为了研究用户多次购买行为之间的关系提出的。序列模式挖掘是是指从序列数据库中寻找出现频率高的子序列的过程。它具有广阔应用领域，如客户购物交易分析、DNA序列破译、Web访问分析等等。

目前的序列模式挖掘算法都是基于静态的数据库进行挖掘，但在许多实际应用中，序列数据库是增量更新的，已有的挖掘结果或规则可能不再有效。为了提高挖掘效率，一般通过增量式序列模式挖掘算法（ISPM）对数据库中新增数据序列进行挖掘。例如，由于老顾客添加新购买的物品，或者插入新客户购物的新序列，顾客购物交易数据库会日益增长。在应用中存在两种数据库更新:

（1）插入新的序列;

（2）在已存在的序列后追加新的序列。

由于原始数据库的更新，一些现有的模式可能成为无效的，因为更新可能会使最小支持度变得不充分。也有可能会产生新的频繁模式。增量序列模式挖掘需要处理在数据库更新的情况下，不需要重新挖掘数据库，充分利用上一次的挖掘结果进行挖掘。下面我们将重点介绍几种增量模式挖掘。

1 基于Apriori的算法

早期的序列模式挖掘算法都广泛地应用了Apriori性质。基于Apriori特性的算法可以根据数据库类型被划分为两类:水平格式算法和垂直格式算法。水平数据库的每条记录由一个序列标识符和序列组成; 垂直数据库的每条记录由一个序列标识符、一个项集标识符和项集组成。水平数据库和垂直数据库之间可以相互转换。

1.1 水平格式挖掘算法

1.1.1 ISE算法

Masseglia等人提出了一种增量挖掘算法ISE[2]，可用于计算当原始交易数据库增加新的交易和新的客户时的频繁序列。它通过把增量数据库中的序列和原始数据库中的序列进行连接产生整个数据库的候选序列。因此当原始数据库中的数据被更新时不需要重新计算这些序列。

ISE是一种迭代算法。首先遍历数据库的增量部分db，计算所有至少出现一次的项集的支持度。结合之前原始数据库DB的项集，可以得知哪些项集在U（DB∪db）上是频繁的，称之为L1db。可以在此基础上生成新的频繁序列:1.将L1db加入到DB的频繁序列中; 2.DB中的频繁子序列可以作为L1db的前缀生成长度为2的候选序列; 3.遍历数据库从2-候选序列根据支持度阈值的判定方法得到 2-频繁序列。一直迭代这个过程直到没有候选集产生。

ISE算法的优势是内存消耗小，不用额外的空间存储潜在的频繁模式，但还是有一些限制，首先会产生大量的候选集，使得挖掘速度慢; 其次层次明确的计算方式需要对整个数据库进行多次扫描，当序列很长的时候这是非常耗费时间的。

1.1.2 IUS算法

IUS算法[3]的主要思想是,通过重用原始数据库中的负边界序列和频繁序列使计算开销达到最小。算法中除了最小支持度min _sup外,还定义了一个新的支持度——负边界序列最小支持度，用min_nbd_sup表示。只有支持度在min_sup和min_nbd_sup之间的序列才能加入负边界序列集中。通过调整min_nbd_sup的值，我们可以去掉负边界序列中那些支持度很小，对计算结果影响较小的序列，从而节约了负边界序列所消耗的内存空间。

IUS算法分为两个部分，第一部分将原始数据库和新增数据库中的频繁序列和负边界序列作为候选序列，将其中符合条件的部分插入到更新后数据库的频繁序列集和负边界序列集中。第二部分将用这两种方法产生新的负边界序列集，作为下一次循环的候选序列，并重新计算这些候选序列在更新后数据库中的支持集。

1.2 垂直格式挖掘算法

Parthasarathy等人提出了一个基于SPADE算法的增量挖掘算法ISM[4]。为了达到降低重新计算和重新扫描数据库的要求，ISM 使用垂直数据的存储方式，建立了一个增量序列格（IS L），序列格由原始数据库中所有频繁序列（FS）和负边界（NB）内的所有序列和组成。FS表示在更新数据库中的所有频繁序列集; 负边界是由非频繁序列但是其最大的两个子序列是频繁的所有序列组成的集合。同时序列格也存储了子序列的支持度。

ISM算法的优点是显而易见的，只需要扫描一次数据库的新增部分，而不用重新扫描整个数据库，与其他大多数序列模式挖掘算法相比在速度上有很大提升。但是ISM需要维护否定边界，如果序列数据库非常庞大，那么否定边界也会相应增大，这将会增加存储成本。另外ISM 算法仅考虑数据库增加新序列的情况。

2 基于投影的算法

Apriori 算法由于会产生大量的候选集并且需要多次扫描数据库，因此在挖掘长序列模式方面效率很低。为了克服这些缺点，Pei等人提出了一种投影算法PrefixSpan[5]，该算法采用完全不同的挖掘策略，通过对频繁前缀投影，产生频繁后缀项，进而连接产生新的模式。基于投影算法的优势在于仅扫描原始数据库两次，并且通过分而治之的思想，把数据库投影缩减成更小的数据库。每次迭代挖掘都限定在投影后的更小的数据库中，节省了运行时间。

2.1 IncSpan算法

Cheng等人[6]提出一种基于PrefixSpan算法的增量式挖掘算法IncSpan，该算法提出了半频繁序列的概念，半频繁模式不是频繁模式，但是却在更新的数据库中有可能成为频繁模式。在挖掘原始数据库时，将频繁序列和半频繁序列放入缓存中。在挖掘更新数据库时只计算在缓存中的序列的支持度。另外该算法引入两个优化方法，反转模式匹配和共享投影。反向模式匹配可以匹配一个序列中的序列模式，缩小搜索空间。共享投影用于降低数据库投影的占用的空间。

该算法利用最小支持阈值min_sup和因素μ将模式划分成三类:

频繁的序列:其支持度不小于min_sup;

半频繁的序列:其支持度小于min_sup且不小于μ*min_sup;

不频繁的序列:其支持度小于μ*min_sup。

本算法提出了一条重要理论:对于频繁模式p满足supLDB（p）〈（1-μ）*min_sup,那么就不存在由p作为前缀的序列p’，使p’从在D中不频繁变为在D’中频繁（LDB是更新后的数据库）。

Nguyen等人[7]发现IncSpan算法不能找出完备的序列模式，提出了IncSpan+算法，该算法延用了IncSpan的半频繁模式和剪枝策略，修正了IncSpan在生成频繁模式集和半频繁模式集上的一些错误。

2.2 IIMSP算法

IIMSP算法是由Liu等人[8]提出的一种基于频繁序列树的增量挖掘算法。频繁序列树是一种序列存储结构，存储满足频繁序列树支持度阈值tree_sup的所有序列模式及其支持度。

IIMSP算法在第一次挖掘过程中，把所有满足tree_sup的序列模式及其支持度存储在频繁序列树中。当数据发生变化时，II MSP算法分两种情况对频繁序列树进行更新。

（1）如果最小支持度min_sup大于等于频繁序列树的支持度阈值tree_sup,IIMSP只需要遍历频繁序列树就能得到所有序列模式;

（2）如果最小支持度小于频繁序列树的支持度阈值，IIMSP需要对原有数据库构造投影数据库，并找到满足支持度的所有序列模式，实现频繁序列树的更新操作。

频繁序列树的结构特点使IIMSP算法能够充分利用先前挖掘的结果，当数据库发生变化时，IIMSP算法不需要对原始数据库构造投影数据库，只需对与增量数据库相关的序列构造投影数据库，大大减小了投影数据库的规模。

2.3 PBIncSM算法

PBIncSM算法[9]是由Zhang等人提出的一种基于前缀树的增量序列挖掘算法。该算法和IncSpan算法一样，都是基于投影的算法。IncSpan和IncSpan+虽然在半频繁模式转化成频繁模式中节省了时间，但由于算法要保证可持续性，因此还需要维护半频繁模式。半频繁模式的维护难度不低于频繁模式的维护难度，利用半频繁模式来挖掘序列模式不能提高效率。

PBIncSM算法利用了PrefixSpan的前缀树结构，前缀树每条路径表示一个序列模式，并且每个结点都存储了对应的投影数据库，每个结点的子结点都通过扫描投影数据库得到。该算法提出了两种剪枝方法，广度剪枝和深度剪枝，并且给出了相关证明。

广度剪枝:如果某结点的投影数据库保持不变,可进行剪枝。

深度剪枝:假定p结点的父节点在扫描过程中未引入新的节点，且p的增量元素集与p及其兄弟结点的交集为空，则D’的p及其子树保持不变。

3 总结

序列模式挖掘早期的工作主要集中在利用新的数据结构或这在主存管理数据库来提高算法的效率。由于数据库的更新，先前挖掘出来的模式有可能会失效，并且可能产生新的模式。因此ISPM得到了广泛的研究，因为它利用已经被发现的知识来解决动态更新数据库的维护问题，而不用重新开始挖掘。本文详细介绍了基于Apriori和基于投影两大类增量模式挖掘算法。目前的多数增量算法都只考虑了更新的数据，没有考虑先前的挖掘数据可能会过时的问题，这也是增量序列挖掘的一个新的研究趋势。

[1]Agrawal R，Srikant R.Mining sequential patterns[C].In: Proceedings of the 11th International Conference on Data En gineering.Taipei,Taiwan,1995.

[2]Masseglia F,Poncelet P,Teisseire M.Incremental mining of sequential patterns in large databases[J].Data and Knowledge Engineering,2003.

[3]Zheng Q,Xu K,Ma S,et al.The algorithms of updating sequential patterns[C].In:Proceedings of 5th International Wor kshop on High Performance Data Mining（HPDM），in Conj unction with 2nd SIAM Conference on Data Mining USA,20 02.

[3]Parthasarathy S,Zaki M,Ogihara M,et al.Incremental an d interactive sequence mining[J].In:Proceedings of the 8th Inte rnational Conference on Information and Knowledge Manage ment,Kansas City,MO,USA,1999.

[4]Pei J,Han J,Mortazavi-Asl B.PrefixSpan:Mining Sequent ial Patterns Efficiently by Prefix-Projected Pattern Growth[C]. In:Proceedings of International Conference on Data Engineerin g，Heidelberg,Germany,2001.

[5]Cheng H,Yan X,Han J.IncSpan:Incremental mining of sequential patterns in large database[C].In:Proceedings of the te nth ACM SIGKDD international conference on Knowledge di scovery and data mining,Seattle,WA,USA,2004.

[6]Nguyen SN,Sun X,Orlowska ME.Improvements of Inc Span:Incremental mining of sequential patterns in large databas e[C].In:Proceedings of the 9th Pacific-Asia Conference on Kn owledge Discovery and Data Mining,Heidelberg,SpringerVerlag, 2005.

[7]刘佳新.一种高效的增量式序列模式挖掘算法[J].计算机工程，2012.

[8]张坤，陈越，朱杨勇.一种基于前缀树的增量序列挖掘算法[J].计算机工程，2007.