Abstract

许多真实生活中的序列数据库都呈现递增趋势。当一小部分序列增长或将一些新序列添加到数据库中时，我们不希望从头开始挖掘序列模式。因此应该开发序列模式挖掘增量算法，以便挖掘能够适应增量数据库更新。然而，增量挖掘序列模式并不是重要的，特别是当现有序列增量增长时，因为由于增长的子序列与原始子序列的相互作用，这种增长可能导致许多新模式的生成。在本研究中，本文开发了一个有效的算法IncSpan，通过探索一些有趣的属性，为序列模式的增量挖掘。实验研究表明，IncSpan的性能优于以前提出的一些增量算法，以及一个具有很大边际的非增量算法。

Introduction

Preminlinary concepts

序列模式树 T T T是表示数据库中频繁子序列集合的树。 T T T中的每个节点p都有一个标记为s或i的标记，表示节点是项目集中的起始项目；我的意思是节点是项目集中的中间项。每个节点 p p p都有一个支持值，它表示从 T T T的根开始到以节点 p p p结束的子序列的支持值。

问题声明。给定一个序列数据库 D D D， m i n s u p minsup minsup、频繁的子序列 F S FS FS，和一个附加序列数据库 D ′ D^{prime} D′，增量序列模式挖掘的问题是从 D ′ D^{prime} D′挖掘频繁的子序列 F S ′ FS^{prime} FS′基于 F S FS FS而不是挖掘 D ′ D^{prime} D′从头开始。

Buffer semi-frequent patterns

本文将提出缓冲半频繁模式的想法，研究其特性，并设计了如何逐步挖掘和维护FS和SFS的解决方案。

Buffering Semi-frequent Patterns

该文缓冲了半频繁的模式，这可以被认为是一种基于统计数据的方法。这个技术是降低最低支持缓冲比 µ ≤ 1 µ ≤ 1 µ≤1和保持一组 S F S SFS SFS原始数据库 D D D。这是因为因为 S F S SFS SFS序列“几乎频繁”，大多数频繁的子序列附加数据库将来自 S F S SFS SFS或他们已经频繁在原始数据库。通过对原始数据库进行一次小的更新，预计只有一小部分以前不常见的子序列会变得频繁。这是基于对原始数据库的更新在项目上具有统一的概率分布的假设。预计数据库更新的部分引入的大部分频繁子序列将来自 S F S SFS SFS。 S F S SFS SFS在频繁的子序列和不频繁的子序列之间形成了一种边界（或“缓冲区”）。

( 1 − µ ) (1−µ) (1−µ) * m i n s u p minsup minsup， µ µ µ越小，我们保留的缓冲区就越大，算法需要的数据库投影就越少。 µ µ µ的选择是启发式的。如果 µ µ µ太高，那么缓冲区就很小，我们必须做大量的数据库投影来发现缓冲区之外的序列。如果 µ µ µ设置得很低，我们将在缓冲区中保留许多子序列。但是使用 µ ∗ m i n s u p µ∗minsup µ∗minsup挖掘缓冲模式比使用 m i n s u p minsup minsup挖掘效率低得多。

INCSPAN: DESIGN AND IMPLEMENTATION

IncSpan: Algorithm Outline

Reverse Pattern Matching

反向模式匹配是一种新的优化技术。它与从结尾到前面的序列匹配一个序列模式。这是用来检查在LDB中，一个序列模式支持度的增加。由于附加的项目总是在原始序列的末端部分，反向模式匹配将比从前面的投影更有效。

Shared Projection

CONCLUSION

该文研究了大型数据库中序列模式的增量挖掘问题，并解决了从头开始挖掘附加数据库的低效问题。通过探索几种平衡效率和可重用性的新技术，我们提出了一种IncSpan算法。IncSpan的性能大大优于非增量方法(使用预固定的Span)和之前提出的增量挖掘算法ISM。它是一种很有前途的算法来解决许多实际应用的实际问题。 有许多与IncSpan相关的有趣的研究问题有待进一步研究。例如，增量挖掘的封闭序列模式，结构化的数据库/或数据流中的模式是未来研究中的有趣问题。