综述：序列模式挖掘算法综述
序列模式挖掘算法综述
贺亮 王科人 韩杰思
摘要：如何利用已有数据库挖掘出有价值的规律进而指导决策，已经成为当今数据
挖掘领域研究的热点。序列模式挖掘可以从已有数据库中挖掘出频繁出现的模式规律。
介绍目前比较常见的序列模式挖掘算法的基本思想和步骤，对比各个算法在实现上采用 的优化策略和数据结构，分析比较几种较为常见的序列模式挖掘工具，最后结合实验数 据对算法进行对比和分析。
关键词：序列模式挖掘；频繁模式；闭合模式；生成器模式
１ 引言
数据挖掘（Ｄａｔａ ｍｉｎｉｎｇ）是从海量数据中
挖掘出有价值的可以被利用的信息和知识的过
程。序列模式挖掘（Ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ） 是数据挖掘中的一个重要研究领域，是指从庞
大的事务记录中寻找出具有一定发生顺序的频
繁事件序列。目前序列模式挖掘已经广泛应用 于ＤＮＡ序列分析、顾客购物行为分析、网站
访问规律分析以及网络行为规律分析等领域。
已有的序列模式挖掘算法有很多，其火
体可按照如图１分类方式划分。ＴＫＳ （Ｔｏｐ．ｋｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ）算法【 Ｊ和
ＴＳＰ（Ｔｏｐ．ｋ ｃｌｏｓｅｄ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎｓ）算法【 Ｊ 主要用于挖掘前ｋ个支持度的序列模式。对于 单维的序列模式挖掘，ＧＳＰ（Ｇｅｎｅｒａｌｉｚｅｄ
ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ）算法 、ＰｒｅｆｉｘＳｐａｎ
（Ｐｒｅｆｉｘ－ｐｒｏｊ ｅｃｔｅｄ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ） 算法Ｉ们、ＳＰＡＤＥ（Ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ ｄｉｓｃｏｖｅｒｙ
ｕｓｉｎｇ ｅｑｕｉｖａｌｅｎｃｅ ｃｌａｓｓｅｓ）算法 ，ＳＰＡＭ （Ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎｍｉｎｉｎｇ）算法【６Ｊ以及其改
进算法都是找到全部支持度大于最小支持度
的序列模式，算法给出的结果往往存在较多 的冗余， 需要用户自行筛选。ＢＩＤＥ （Ｂｉ．ｄｉｒｅｃｔｉｏｎａｌ ｅｘｔｅｎｓｉｏｎ）算法【 、ＣｌｏＳｐａｎ （Ｃｌｏｓｅｄ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ）算法 以 及ＣｌａＳＰ（Ｃｌｏｓｅｄ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎｓ ａｌｇｏｒｉｔｈｍ） 算法 】则是给出闭合序列模式，所得到的序
列模式更加贴近用户的需求。ＭａｘＳＰ （Ｍａｘｉｍａｌ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ ｍｉｎｅｒ）算法【１０】
以及ＶＭＳＰ（Ｖｅｒｔｉｃａｌ ｍｉｎｉｎｇ ｏｆ ｍａｘｉｍａｌ ｓｅ— ｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎｓ）算法…】贝０是求出最大序列
模式，即所得的序列是最长的序列，序列之
间不存在包含关系。与闭合模式对应，ＦＳＧＰ
（Ｆｒｅｑｕｅｎｔ ｓｅｑｕｅｎｔｉａｌ ｇｅｎｅｒａｔｏｒｓ ｐａｔｔｅｒｎｓ） 和ＶＧＥＮ（Ｖｅｒｔｉｃａｌ ｓｅｑｕｅｎｔｉａｌ ｇｅｎｒａｔｏｒ ｍｉｎｅｒ） Ｄ３］等算法得到的是序列生成器。
本文针对现有序列模式挖掘算法及其发展
进行阐述，并在仿真数据集和公开数据集上对
其性能进行测试比较，最后对序列模式挖掘技 术当前面临的问题进行总结与展望。
２序列模式挖掘的相关定义描述
序列模式挖掘是在有序事件数据集中挖掘 频繁序列模式的过程，最初由Ａｇｒａｗａｌ和 Ｓｒｉｋａｎｔ［１４］针对超市购物篮数据的分析而提出。
为便于问题描述，引入如下基本定义。
定义１：事务数据库（Ｔｒａｎｓａｃｔｉｏｎ ｄａｔａｂａｓｅ）， 由待处理过程的记录所组成的数据库。
定义２：项（Ｉｔｅｍ），事务数据库中事件内
・４５’
总第３９０期 电信技术研究 ＲＥＳＥＡＲＣＨ ＯＮ ＴＥＬＥＣＯＭＭＵＮＩＣＡＴＩＯＮ ＴＥＣＨＮＯＬＯＧＹ ２０１ ５年第２期
图ｌ 序列模式挖掘算法的分类方式
容所涉及的具体单元，在序列挖掘中作为最小
单冗。 定义３：项集（Ｉｔｅｍｓｅｔ），由项组成的集合，
集合中各个项无顺序关系。
定义４：序列（Ｓｅｑｕｅｎｃｅ），项集的有序排 列。序列 Ｓ１ …．， ，，其中 ，（１≤Ｊ ，）为序列
ｓ的元素，即为一个项集。
定义５：序列长度（Ｌｅｎｇｔｈ ｏｆ ｓｅｑｕｅｎｃｅ）， 序列中项集的数目。 定义６：支持度（Ｓｕｐｐｏｒｔ）和最小支持度
（Ｍｉｎｉｍｕｍ ｓｕｐｐｏｒｔ），序列ｓ的支持数是指数据
库中能够匹配该序列的事务数量，这些序列的
数目占总事务数的比例称为支持度，记为 ｓｕｐ（ｓ１。最小支持度是支持度的一个阈值，在
实际应用中一般人为设定，记为ｍｉｎｓｕｐ。
・４６・ 定义７：序列模式（Ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ）， 称序列Ｓ为序列模式， 当且仪当 ｓｕｐｓｕｐ（ｓ１ ｍｉｎｓｕｐ。
定义８：前缀（Ｐｒｅｆｉｘ），给定序列
口＝ｅｌ，ｅ２…．， ， ＝ ，ｅ ，．．．， ，ｍ ） ， 若
ｅｌ＝ （ｉ ｍ一１），ｅｍ ｅｍ，且 一 中的项目均
在 后，则 是 的前缀。
定义９：子序列（Ｓｕｂｓｑｕｅｎｃｅ），称序列
＝ ，ｅ ，．．．， 是 ＝ｅＩ，ｅ２ ．，ｅｎ（ｍ 刀）的子序
列，当且仪当ｅ ｅｊ，１ Ｊ ｍ成立。 定义１０：投影（Ｐｒｏｊｅｃｔｉｏｎ），若序列 是
序列 的子序列，则 关于 的投影 是 满足
是 前缀这一条件的最大子序列。 定义１１：后缀（Ｓｕｆｆｉｘ），序列 ＝ｅＩ，ｅ２…．，ｅｎ
综述：序列模式挖掘算法综述
关于子序列 ＝ｅＩ，ｅ２…．， 的斤缀为
，ｅｍ …，ｅｎ，其中 ＝ 一 。 定义１２：投影数据Ｊ牢（Ｐｒｏｊｅｃｔｉｏｎ ｄａｔａｂａｓｅ），
所有以序列模式 为前缀的序列相对ｆ 的后 缀组成的数据库。
定义ｌ３：序列Ｓ是闭合序列模式（Ｃｌｏｓｅｄ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ）［１５】，当且仪当不存在序列
Ｓ’ Ｓ，使得ｆ（ ）＝ （ ’），即 ’ ，ｆ（ ）≠ｆ（ ’）。
其中ｔ（ｓ１表示序列模式 匹配上的事务集。
定义１４：序列Ｓ是序列生成器（Ｓｅｑｕｅｎｔｉａｌ ｇｅｎｅｒａｔｏｒ）［ ，当且仅当不存在序列Ｓ’ Ｓ，
使得ｔ（ｓ）＝ｆ（ ’），即ＶＳ’ ， （ ）≠ｆ（ ’）。
序列模式挖掘的主要目的是，从事务数据
库中挖掘出支持度高于最小支持度的序列，即 挖掘出相应的序列模式，该序列模式一定程度
上表征了事务发展的内在规律。
３典型序列模式挖掘算法
早期序列模式挖掘算法多基于Ａｐｒｉｏｒｉ原 理，出现了多种Ａｐｒｉｏｒｉ类算法。之后，针对此
类算法存在的各种影响挖掘性能的问题，基于 投影数据库、垂直数据库和闭合序列模式以及
序列生成器模式的挖掘算法相继涌现出来。本
节将针对具有代表性的序列模式挖掘算法及其 特点进行阐述。
３．１ Ａｐｒｉｏｒｉ算法
文献［１４］最早提出了序列模式挖掘问题， 并给出了 ＡｐｒｉｏｒｉＡｌｌ、 ＡｐｒｉｏｒｉＳｏｍｅ和
ＤｙｎａｍｉｃＳｏｍｅ三种挖掘算法。
上述三种挖掘算法的主要思想基本相同， 在每一次扫描数据库的过程中，将利用前一次
得到的序列模式增加一项生成候选序列，并计
算候选序列的支持度，大于最小支持度阈值的 候选序列作为序列模式，成为下一次扫描数据
库时用于扩充的序列。ＡｐｒｉｏｒｉＡｌｌ采用该方式 得到所有序列模式，但在该过程中 易产生庞
人的候选序列模式集，并且每次对序列模式增
加一项的操作都需要重新扫描数据Ｊ年，计算支
持度。与ＡｐｒｉｏｒｉＡｌｌ不同，ＡｐｒｉｏｒｉＳｏｍｅ和 ＤｙｎａｍｉｃＳｏｍｅ只求取最大序列模式。
ＤｙｎａｍｉｃＳｏｍｅ’ｆｉ－先确定需要计数的序列长度， 但是在产生候选序列的过程中不重复扫描数据
库，不对候选序列进行删减，在算法后 部分
才开始剪枝，在开始的时候会产生大量的候选
序列。ＡｐｒｉｏｒｉＳｏｍｅ则是将ＤｙｎａｍｉｃＳｏｍｅ和 ＡｐｒｉｏｒｉＡｌｌ的思路相结合，在确定需要计数的
序列长度后，先删除已找到的非最大序列模式。
一般情况下，ＡｐｒｉｏｒｉＳｏｍｅ算法优＿－ｒ ＤｙｎａｍｉｃＳｏｍｅ和ＡｐｒｉｏｒｉＡｌｌ算法。
需要注意的是，Ａｐｒｉｏｒｉ类算法不擅长处理
长序列模式的挖掘，因为此类算法均通过短序 列的逐步增长来获得候选序列。随着序列长度
的不断增加，候选序列数将急剧膨胀，冈而可
能使得挖掘长序列模式的时间复杂度难以接受。
３．２ ＧＳＰ算法
ＧＳＰ算法［３】在Ａｐｒｉｏｒｉ的基础上对算法进行
改进。与Ａｐｒｉｏｒｉ不同的是，ＧＳＰ引入了约束
条件（时间约束、滑动时间窗和扫描约束等） 来提高算法的执行效率。引入时间约束后，序
列中的项需在满足最大或最小间隔的条件下才
能构成序列模式，滑动窗Ｕ允许挖掘出的序列
模式的项来自不同的事务。通过引入这些约束， 可以降低候选序列个数，减少无用的候选模式
的生成，产生的结果更加贴近用户的需求。
在计算模式的支持度时，需要考虑时问间
隔约束，ＧＳＰ算法在实现时采用ｈａｓｈ树结构， 将项集存在叶子节点中，当叶子节点中的项集
较多时，叶子节点生长出子节点成为内部节点 存储ｈａｓｈ表，其子节点成为新的叶子节点存储
项集。可以看出，该结构会重复存储具有相同 前缀的序列。
ＧＳＰ通过组合已有序列模式获得候选序列
・４７・ 电信技术研究 总第３９０期 ＲＥＳＥＡＲＣＨ ＯＮ ＴＥＬＥＣｏＭＭＵＮＩＣＡＴｌｏＮ ＴＥＣＨＮｏＬｏＧＹ ２０ １ ５年第２期
后，需要对候选序列在数据集中的支持数进行 计数。该过程需要结合用户提供的约束条件，
在数据Ｊ＝孛序列中寻找满足约束条件的序列支持
数。ＧＳＰ计算候选模式支持度的过程分为两个 阶段：向前阶段（Ｆｏｒｗａｒｄ ｐｈａｓｅ）和向后阶段
（Ｂａｃｋｗａｒｄ ｐｈａｓｅ）。在检验某个序列是否包含
序列模式时，首先进入向前阶段：一个连续序
列的开始时间和结束时间间隔小于问隔约束，
从某个项开始，若时间间隔大于间隔约束，则 转到向后阶段；向后阶段：算法返回之前的项，
重新扫描，将时间戳调整为当前时间减去时间
间隔，检查该时间段后满足条件约束的项，如 果都满足时间间隔，则调整时间戳为之前一项
的时间减去时间间隔。依此类推，直到所有之
前的项都满足时问问隔或者第一个项目被处理，
算法进入向前阶段。在向前阶段中，如果没有 找到任何项，则说明数据序列不包含序列模式；
在向后阶段中，如果没有项能够用于调整时间 戳，则数据序列不包含序列模式。ＧＳＰ算法在 上面的两个阶段中来回转换，直到序列模式中
的全部项都在数据序列中被找到。
ＧＳＰ算法是Ａｐｒｉｏｒｉ算法的拓展，仍具有
Ａｐｒｉｏｒｉ算法的缺点，算法的过程需要多次扫描 数据库，并且随着算法的进行，候选序列的个
数急剧增长，尤其对于较大的原始数据库，仍
然会产生较多的候选序列。ＭＦＳ（Ｍｉｎｉｎｇ ｆｒｅｑｕｅｎｔ ｓｅｑｕｅｎｃｅ）算法¨６Ｊ是基于ＧＳＰ算法的
改进算法，算法避免了多次遍历数据库，而是 通过粗劣评估和细化结果的方式获得全部序列
模式。
３．３ ＳＰＡＤＥ算法
ＳＰＡＤＥ算法 也是基于Ａｐｒｉｏｒｉ原理的格
搜索（Ｌａｔｔｉｃｅ ｓｅａｒｃｈ ｔｅｃｈｎｉｑｕｅ）方法。算法的
基本思想是，通过使用垂直数据库的结构，利 用格将原始数据库分解成若干小搜索空间以减
小搜索量。算法只处理分解后的数据库，不需
要扫描原始数据库，减少了Ｉ／Ｏ的开销，同时
・４８・ 避免使用复杂结构，简化支持度计算，提高了 挖掘效率。
ＳＰＡＤＥ算法的具体步骤为：①第一次扫描
数据 『车，生成１一序列模式。②第■次扫描数据 库，生成新的垂直数据库并生成２．序列模式。
③将具有相同前缀的序列放在同一个格内，作
为一个类。④扫描数据库，通过对类进行下面
三种连接方法产生全部频繁序列：①项集和项
集连接，②项集和序列连接，③序列和序列连 接。
由上面的步骤可以看出，ＳＰＡＤＥ方法具有
如下的特点：该方法一共只需要扫描三次数据 库；ＳＰＡＤＥ产生新序列的方法是合并已有的类，
方法较为简单快速；算法的实现不需要ｈａｓｈ树
或者搜索子序列。但是该算法在原始数据库很 大时，将数据库转换成垂直结构的效率将会较
低。
３．４ ＦｒｅｅＳｐａｎ算法
ＦｒｅｅＳｐａｎ算法ＨＴ］是基于投影的模式增长
算法，其基本思想是根据已有的频繁项迭代产 生相应的投影数据库，由投影数据库再产生频
繁子序列片段，进而产生全部模式序列。 ＦｒｅｅＳｐａｎ算法的具体步骤为：①扫描数据
库，找出满足支持数的频繁１．项集，将数据库
按照该项集投影，得到若干子数据库。②扫描 得到的子数据库产生频繁２．项集，再投影产生
相应的投影数据库。③重复上面的过程，直到 得到的投影数据库不能再产生频繁项集为止。
在ＦｒｅｅＳｐａｎ算法中，由于采用了投影数据 库的方法，无需产生候选序列，但是算法的实
现过程中可能会生成较多的投影数据库，如果
某个模式在数据库中的每个序列都出现，则这
个模式的投影数据库不会减小。在模式增长的
过程中，ＦｒｅｅＳｐａｎ是自由拓展的，其增长的位 置不同定，这会影响算法的效率。此外，还有 基于图模式生长的结构模式挖掘算法ｇＳｐａｎ【１引。
