12.6 增量序列模式挖掘
在动态更新的流式数据中进行数据挖掘的需求由来已久[34] ，对于序列模式挖掘来说，当数据发生少量更新时对全体数据重新进行挖掘是不可取的。因此，一些增量序列挖掘算法被提出以适应不断增长的数据，这类算法在更新迅速的大数据中显得十分重要。
Parthasarathy 等人[35]提出的 ISM 增量序列模式挖掘算法，基于 SPADE 算法进行扩展，以最小的 I/O 和计算代价处理新增数据。具体地，一种增量序列晶格的结构被用于存储所有频繁序列 , 以及原数据库中位于负边界中的所有序列。这些位于负边界中的序列可能由于新增数据的加入 , 而变成频繁序列模式。Masseglia 等人[36]则提出了一种基于Apriori 思想的增量序列模式挖掘算法 ISE。ISE 利用尽可能少的老频繁序列模式的信息最小化计算代价，挖掘出新增数据中的频繁模式。Cheng 等人[37]提出的 IncSpan，通过维护一个“几乎频繁”的序列集合作为新增数据中可能成为频繁序列模式的候选集 , 高效地进行增量挖掘。Gao 等人[38]则提出了 StreamCloSeq 算法增量，挖掘频繁闭序列模式。
对于频繁情景模式挖掘，Patnaik 等人[39]较早在频繁情景挖掘问题中考虑了数据动态问题。在Patnaik所描述的问题中，事件序列以批量方式更新；然后，对于一段新的事件序列，首先使用已有的频繁情景挖掘算法在增量序列上挖掘候选的情景模式。他们工作的主要贡献是提出了一个频率的下界，凡是频率超过此下界的情景模式很有可能在更新后的序列中是一个 top k 的频繁情景模式。我们[40]率先将频繁情景模式发现算法推广到在线形式，提出的MESELO 算法从动态更新的序列中 , 不断快速地挖掘出最新的频繁情景集合。这里，事件序列总是一个时刻接一个时刻地连续不断更新，而不是批量的更新数据。这个问题中数据更新更快，对算法的响应时间要求更加严格。具体地，在 MESELO 算法中，一种最后情景发生的概念被提出，基于最后情景发生，动态更新的事件序列中的情景最小发生可以快速地被找到。另外，一种高度压缩的场景 trie 则被提出用来高效存储事件序列的更新信息，辅助算法快速计算。MESELO 算法是首个单遍历的频繁情景模式挖掘算法，较传统的方法提高了 1~2 数量级，响应时间通常不超过 1 s。