12.7 序列模式挖掘近似算法
数据中通常蕴含大量的频繁模式。确定性算法能够挖掘出所有频繁的模式，具有最高的准确性，但通常会花费大量计算时间，并且消耗大量内存。而序列模式挖掘近似算法是适应大数据的另一种方式。但是，近似算法所挖掘的结果中却存在着误差。因此，错误误差的估计通常是近似算法重点关注的对象。其中，Manku 等人[41]提出的 LCA（LowestCommon Ancestors）算法是一个代表性的从流数据中挖掘频繁模式的近似算法。在 LCA 算法中，增量数据以大小为 B 的块更新。对于第 n 批数据，LCA 先计算新增数据中的数据模式及其频率，然后更新到历史的结果中。但是，对于那些发生次数小于 n 的模式，LCA 会将它们从内存中删除。因此，LCA 算法存在少计算项集频率的情况，这个误差的上界是 εn ，这里 ε 是用户设定的一个误差率参数。类似地，如 Carma 算法[42] 、estDec 算法 [43] 、FP-Stream 算法[44]和 FDPM 算法[45]都考虑了类似的挖掘问题并借鉴了类似思想设计算法。又如前文所述的文献[39]中的算法也是一种近似算法，用于动态数据中的频繁情景模式挖掘。此外，Kum等人[46]则对序列模式的形式进行近似，提出了近似序列模式挖掘的概念，它的基本思想是挖掘那些可能被多个序列共享的近似的序列模式，而不是找到那些确定的序列模式。
