唐 雁，吴绍春

（上海大学 计算机工程与科学学院， 上海 200072）

随着科学技术的飞速发展，在各个领域产生了大量的历史数据，如何有效地管理和利用这些海量数据序列，发现和理解这些数据序列背后隐含的规律和知识，已经受到越来越多数据挖掘研究者的广泛关注。序列模式挖掘由此应运而生，并已经成为数据挖掘领域中一个重要研究方向。

目前的序列模式挖掘方法主要分为2类：（1）基于Apr iori的算法，其基本思想是频繁模式的子模式也一定是频繁模式，如Apr ior iALL、GSP算法；（2）基于模式增长方法，采用分而治之的原理,反复把数据库投影到比它小的数据集里，在较小的数据集上进行模式扩展的序列挖掘，如Freespan、Pref ixSpan算法。

本文提出一种新型的序列挖掘模型—多元索引后继树，具有创建速度快， 检索速度快，空间效率高等特点。该模型使用索引方法通过一遍扫描创建描述一个序列的多元索引后继树，可以完全抛弃原始序列，然后使用模式增长的方式生成频繁模式，无需生成候选模式，同时也可以通过索引快速生成原始序列。本文通过试验分析证明多元索引后继树模型多方面性能均优于其他的序列挖掘模型。

1 多元索引后继树（MIST）模型

使用多元索引后继树模型的前提是需要对序列进行符号化等相关的预处理，将序列转换成用符号表示的字符串序列。

1.1 前驱和后继

对任意序列T中的任意字符串a1a2，a1称为a2的前驱；a2称为a1的后继，序列T最后一个字符的后继（假定为#）为序列结束符。……