基于多元索引后继树的序列模式挖掘方法

唐 雁，吴绍春

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

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

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

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

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

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

1.1 前驱和后继

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

1.2 索引

在一序列中，每一个字符在序列中出现的位置就定义为该字符在序列中的索引。

1.3 后继表达式

设序列T是由一字符串a0，a1，…，an组成的，其索引分别为0，1，…，n。若其中ai1、ai2、…、aim为一组相同的字符，这里统一记为ai，则ai1+1、ai2+1、…、aim+1都是ai的后继，而ai1+1、ai2+1、…、aim+1的索引分别为i1+1、i2+1、…、im+1。对ai每一个后继，建立形如aiai1+1的后继项，对ai的所有后继项根据不同的后继字符（假定为ak、a1、…、az）进行合并，形成ai的后继表达式ai((ak,k1,k2,…,km),(a1,l1,l2,…,ln),…,(az,z1,z2,…,zt))。

1.4 多元索引后继树

序列T中，任一ai的后继表达式可以用一棵2级多叉树来表示，如图1。我们定义为多元索引后继树，它是一颗深度为2的树。

图1中多元索引后继树的根节点为ai，第一个叶节点(ak,k1,k2,…,km)表示ai的一个后继ak，后继ak在序列中出现次数（即字符串aiak出现的次数）为m，k1、k2、…、km为aiak在序列中ak出现的索引位置。

图1 多元索引后继树结构

1.5 多元索引后继树模型

若全文a0，a1，…，an（以#为结束标记）中共有k个不同的字符，则k个字符对应于k棵不同的多元索引后继树。由于一个序列包含多个字符，每个字符有多个不同的后继，每个不同的后继用一个叶节点表示多个索引的集合，将一个序列对应的所有多元索引后继树的森林定义为序列的多元索引后继树（Mul t i-Index Successive Tree），记为MIST，它是序列的一种等价的描述模型，即对任意的一序列都能构造其MIST，同时对于MIST也能还原其对应的原始序列。

例1：对于序列abcabaabc#，其中#为结束符，共有3个不同的字符a、b、c，a的后继表达式为：{（b,1,4,7）,(a,6)},b的后继表达式为：{(c,2,8),(5,6)},c的后继表达式为：{（a,3）,(#,9)}。该序列对应的多元索引后继树如图2。

图2 MIST示例

从图2的第一棵树a（索引为0）开始遍历，查找到索引为1的叶节点b，按照叶节点的后继符b开始，遍历后继树b，找到索引为2的叶节点c，以此类推，将遍历整个MIST，那么遍历路径上的根项所组成的字符便可以还原初始的序列。

例2：在例1中，如果查询字符串”abc”，从a的分支查找后继符b，发现b存在于原文1、4、7位置处，再根据b的分支查找后继符c，发现存在于2、8位置处，并且abc有2个匹配（1,2）和（7,8）；则查询字符串”abc”是在索引库存在2个匹配。

1.6 基础频繁项集

后继树中每一个叶节点的计数定义为此叶节点上的后继字符在序列中作为后继出现的次数。假设最小支持度为Suppor t，则计数满足最小支持度要求即为频繁项，由此产生的频繁项集合就称为基础频繁项集，它是频繁2项集。

例3：在例1中，a的后继表达式a(b，1,4,7)表示a的后继符b出现在原序列中1、4、7索引位置，即频繁项ab在序列中出现过3次，其频繁项计数为3；同理a(b,c,1,2,7,8)可看做a的后继bc分别在索引1、2，7、8位置，即频繁项abc在序列出现2次，其频繁项计数为2。

例4：对于序列abcabaabc#，假设支持度Suppor t=2，多元索引后继树a的第一个叶节点（b,1,4,7）的支持度为3，满足要求；第二个叶节点（a,6）的支持度为1，因为不满足支持度要求不做考虑，从而多元索引后继树a满足支持度要求的叶节点为（b,1,4,7）；因此，基础频繁项集为{a(b,1,4,7,b(c,2,8)}。

2 基于MIST的频繁序列模式挖掘

采用MIST发现频繁序列模式主要有2个步骤完成：（1）生成基础频繁项集；（2）生成所有频繁序列模式。

生成基础频繁项的具体过程是从每一颗索引后继树的根出发，遍历它的叶节点，判断此叶节点是否满足最小支持度要求，满足则保留，否则舍去。

生成所有频繁序列模式的具体过程包括：访问满足最小支持度要求的叶节点，根据此叶节点的后继符访问相应基础频繁项集中的索引后继树，查找树中是否存在距离为1的叶节点，如存在，并且同时满足最小支持度要求，则加入到被访问的叶节点中，对不满足要求的索引则舍去。以此类推，直至生成最大频繁序列。

例5：对于序列abcabaabc#，假设支持度Suppor t=2，则满足要求的节点集合为{a(b,1,4,7),b(c,2,8)}。从多元索引后继树a中最后一个后继符b开始访问基础频繁项集中对应的多元索引后继树b(c,2,8)，得到满足要求的频繁项集{a(b,c,1,2,7,8)}，即abc为最大频繁序列，其支持度为2。

下面给出获取满足支持度Suppor t的k项频繁序列的算法：

输入：基础频繁项集L2，k-1项频繁序列Lk-1，最小支持度Supoor t

输出：k项频繁序列Lk

算法：

Foreach(each item in Lk-1)

{

For(i=k-1;i

{

Char c= Lk-1.item(i);// Lk-1中需要匹配的字符

Foreach(each item in L2)

{

int count=0;//计数

Char ch= the root of Lk-1.item;//基础频繁项集的根

If(c==ch)

For( j=0;j< L2.count;j++)

{

If(L2.item(j)-Lk-1.item(i)==1)

Count++;

}

If(Count≥Support) insert L2.item into Lk-1;

}

i+=k-1;

}

}

Lk= Lk-1;

Return Lk;

例6：如果查询字符串“abc”是否为频繁项，查找频繁项集{a(b,c,1,2,7,8)}，可以发现有2个匹配项（1,2）和（7,8），满足最小支持度条件，因此字符串”abc”是频繁项。

3 实验与结果分析

为了对上述算法效果进行考察，本文采用从2002年1月1日到2010年1月1日的崇明地电数据进行模拟试验，如图3。

图 3 地电数据模拟生成的部分原始序列

对崇明地电数据进行分段符号化处理生成字符串序列，采用机器CPU主频为1.66Hz×2，内存为1 G，操作系统为Windows XP的实验环境进行实验分析。

本文分别考察了MIST和Pref ixSpan，并对2种算法的挖掘效果进行了对比分析。图4是在不同的支持度阈值下，2种方法所花费的时间消耗。从图中可以看出，MIST有明显的性能优势。其主要原因是：由于此时Pref ixSpan在重复投影和重复扫描过程中花费的了较多的时间，而MIST使用索引创建树和生成频繁模式，同时将相同的后继字符合并，有效地提高了算法效率。

图 4 MIST与Pref ixSpan时间性能比较

把MIST与Pref ixSpan算法的实验结果进行比较表明，MIST在空间性能方面也占优势。这是由于MIST算法避免了重复投影数据库的构建，放弃了对非频繁项的存储，从而使得MIST算法占据的内存空间小于Pref ixSpan算法，如图5。

图 5 MIST与Pref ixSpan空间性能比较

4 结束语

本文提出一种新的序列挖掘模型—多元索引后继树，与其他方法相比，MIST的优点体现在：（1）无需生成候选模式，节省存储空间，提高时间效率。（2）直接使用字符在原始序列的索引位置，使得频繁项生成过程中速度更快。不管是创建还是生成都很方便快捷。（3）查询和匹配时无需进行字符串分解，因此可以查询和匹配任意长度的字符串。（4）在发现频繁项过程中，使用基础频繁项，不需要使用字符串匹配和频繁计数，从而生成过程简化，速度更快。

多元索引后继树作为一种被初步证明有效的数据挖掘模型，在理论上还需作进一步发展，给出完整体系；在实践上，对本文提出的多元索引后继树的数据结构和频繁模式挖掘算法，还应扩大其实验范围，增加不同条件和状态的实验数据，以准确、全面地评估其有效性，认识其特征，探索更多实际应用领域。

[1]金 灿，朱绍文. 序列模式的增量式挖掘算法研究[D]. 武汉：华中师范大学硕士论文，2004.

[2]王 虎，丁世飞. 序列模式挖掘研究与发展[J].计算机科学，2009.

[3]吕 锋，张炜玮. 4种序列模式挖掘算法的特性研究[J]. 武汉理工大学学报，2006，2.

[4]张圆圆，胡学刚. 序列模式发现模型的研究[D]. 合肥：合肥工业大学硕士论文，2007.

[5]冯文超，吴绍春，王 炜. 基于IRST的并行时序模式挖掘算法[J]. 计算机工程应用研究，2007.