维普资讯 http://www.cqvip.com 第２５卷第７期 ２００８年７月 计算机应用研究 Ａｐｐｌｉｃａｔｉｏｎ Ｒｅｓｅａｒｃｈ ｏｆ Ｃｏｍｐｕｔｅｒｓ Ｖ０１．２５ Ｎｏ．７ Ｊｕ１．２０ＨＤ８ 序列模式挖掘综述 陈摘卓，杨炳儒，宋威，宋泽锋 （北京科技大学信息工程学院，北京１０００８３） 要：综述了序列模式挖掘的研究状况。首先介绍了序列模式挖掘背景与相关概念；其次总结了序列模式挖 掘的一般方法，介绍并分析了最具代表性的序列模式挖掘算法；最后展望序列模式挖掘的研究方向。便于研究 者对已有算法进行改进，提出具有更好性能的新的序列模式挖掘算法。 关键词：数据挖掘；序列模式；周期模式；增量式挖掘 中图分类号：ＴＰ３１ｌ 文献标志码：Ａ 文章编号：１００１—３６９５（２００８）０７—１９６０—０４ Ｓｕｒｖｅｙ ｏｆ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ ＣＨＥＮ Ｚｈｕｏ，ＹＡＮＧ Ｂｉｎｇ—ｒｌｌ，ＳＯＮＧ Ｗｅｉ，ＳＯＮＧ Ｚｅ—ｆｅｎｇ （Ｓｃｈｏｏｌ ｏｆＩｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｂｅｉｉｆｎｇ Ｕｎｉｖｅｒｓｉｔｙ ０厂Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ １０００８３，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｖｉｄｅｄ ａ ｒｅｖｉｅｗ ｏｆ ｔｈｅ ｒｅｓｅａｒｃｈ ｏｆ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ．Ｆｉｒｓｔｌｙ，ｉｎｔｒｏｄｕｃｅｄ ｔｈｅ ｂａｃｋｇｒｏｕｎｄ ａｎｄ ｃｏｎｔｅｘｔ．Ｓｅｃｏｎｄｌｙ，ｓｕｍｍａｒｉｚｅｄ ｔｈｅ ｇｅｎｅｒａｌ ｍｅｔｈｏｄｓ ｏｆ ｓｅｑｕｅｎｃｅ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ，ｉｎｔｒｏｄｕｃｅｄ ａｎｄ ａｎａｌｙｚｅｄ ｔｈｅ ｍｏｓｔ ｒｅｐｒｅｓｅｎｔａｔｉｖｅ ａｌｇｏｒｉｔｈｍ ｔｏ ｐｒｏｖｉｄｅ ａ ｂａｓｉｓ ｆｏｒ ｉｍｐｒｏｖｉｎｇ ｏｌｄ ａｌｇｏｒｉｔｈｍｓ ｏｒ ｄｅｖｅｌｏｐｉｎｇ ｎｅｗ ｅｆｆｅｃｔｉｖｅ ｏｎｅｓ．Ｆｉｎａｌｌｙ，ｄｉｓｃｕｓｓｅｄ ｓｏｍｅ ｆｕｔｕｒｅ ｒｅ— ｓｅａｒｃｈ ｔｒｅｎｄｓ ｏｎ ｔｈｉｓ ａｒｅａ． Ｋｅｙ ｗｏｒｄｓ：ｄａｔａ ｍｉｎｉｎｇ；ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ；ｐｅｒｉｏｄｉｃ ｐａｔｔｅｒｎ；ｉｎｃｒｅｍｅｎｔａｌ ｍｉｎｉｎｇ 数据挖掘作为知识发现的核心步骤，旨在从海量数据中提 取有效的、新颖的、潜在有用的、易被理解的知识。序列模式挖 掘（ｓｅｑｕｅｎｔｉ￣ｐａｔｔｅｒｎ ｍｉｎｉｎｇ）是数据挖掘中非常重要的一个研 究领域，最早是由Ｒａｋｅｓｈ Ａｇｒａｗａｌ和Ｒａｍａｋｆｉｓｈｎａｎ Ｓｒｉｋａｎｔ在针 对超市中购物篮数据的分析提出来的。序列模式挖掘是要找 出序列数据库中所有超过最小支持度阈值的序列模式ｕ 。它 有着广泛的应用领域：商业组织利用序列模式挖掘去研究客户 购买行为模式特征、计算生物学中序列模式挖掘用来分析不同 氨基酸突变模式、用户Ｗｅｂ访问模式预测以及ＤＮＡ序列分析 定义６序列的包含：设存在两个序列ａ， 。其中：ａ＝ （。，，。 ，…，。 ），卢＝（ｂ，，ｂ ，…，ｂ ）。如果存在整数ｌ≤＿『，＜ ＜…＜ ≤ｍ，使得０ｌ ｂｊｌ，ｎ２ ６ ，…，ｎ ６ ，则称序列ａ是 ＩＢ的子序列，又称ＩＢ序列包含ａ，记为ａｃ＿／３。 定义７支持数：序列ａ在序列数据库Ｓ的支持数为序列 数据库Ｓ中包含ａ的序列个数。 定义８支持度：序列的支持度是一个预先设定的阈值。 定义９频繁序列：给定最小支持度阈值，如果序列ａ在序 列数据库中的支持数不低于该阈值，则称序列ａ为频繁序列。 定义ｌ０序列模式：最大的频繁序列称为序列模式，最大 序列就是不被其他任何序列所包含的序列。 Ａｇｒａｗａｌ等人 将序列模式挖掘定义为在序列数据库中挖 和谱分析。序列模式挖掘与关联规则挖掘在许多方面相似，但 它更关心数据之间顺序的关联性。 １ 序列模式挖掘任务定义 基本概念： 掘那些支持数超过预先定义支持度的序列模式的过程。 ２序列模式挖掘方法 ２．１ 基本序列模式挖掘 定义ｌ事务数据库（ｔｒａｎｓａｃｔｉｏｎ ｄａｔａｂａｓｅ）：以超市数据为 例来说明，即由顾客交易记录组成的数据库。Ｃｕｓｔｏｍ—ＩＤ、 ＴｒａｎｓａｃｔｉｏｎＴｉｍｅ、ｈｅｍｓｅｔ分别代表顾客标志、交易时间和交易 大多数早期序列模式挖掘算法都是基于Ａｇｒａｗａｌ提出的 关联规则挖掘算法Ａｐｉｆｏｉ，它的特性是频繁模式的任何子模式 ｆ物品集合。 定义２项集（ｉｔｅｍｓｅｔ）：各个项（ｉｔｅｍ）组成的集合。 都是频繁的。基于这个启发，研究者提出一系列类Ａｐｆｉｏｆｉ算 法，如ＡｐｒｉｏｒｉＡｌｌ、ＡｐｒｉｏｒｉＳｏｍｅ、ＤｙｎａｍｉｃＳｏｍｅ。Ｓｒｉｋａｎｔ等人 提 出了ＧＳＰ（ｇｅｎｅｒａｌｉｚｅｄ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ）方法。Ｚａｋｉｌ３ 提出了 定义３序列（ｓｅｑｕｅｎｃｅ）：不同项集的有序排列。序列Ｓ 可以表示为Ｓ＝（ｓ，，ｓ ，…，ｓ ）。其中：Ｓｊ（１≤ ≤ ）为项集，也 称为序列Ｓ的元素。 定义４序列的元素（ｅｌｅｍｅｎｔ）：表示为（ ，， ，…， ）。 其中： （１≤ｋ≤ｍ）为不同的项。 定义５序列长度：一个序列包含的所有项集的个数，长 度为ｌ的序列记为ｌ一序列。 收稿日期：２００７—０８—２４；修回日期：２００７—１１—１７ ＳＰＡＤＥ方法。这两个方法同样是基于Ａｐｒｉｏｒｉ的。随后学者们 又提出了一系列基于数据投影的算法，它们包括韩家炜在 ２０００年提出的ＦｒｅｅＳｐａｎ和Ｐｅｉ在２００１年提出的ＰｒｅｆｉｘＳｐａｎ。 Ｈａｎ于２００４年提出了一种结合了图模式生长和频繁计数，形 成了结构模式挖掘的算法ｇＳｐａｎ。Ｌｉｎ和Ｌｅｅ于２００２年提出的 作者简介：陈卓，博士，主要研究方向为数据挖掘（ｃｈｅｎｚｈｏｕ６１３＠ｓｉｎａ．ｃｏｎ）；杨炳儒，教授，博导，主要研究方向为数据挖掘、推理机制与知识发 现等 维普资讯 http://www.cqvip.com 第７期 陈卓，等：序列模式挖掘综述 ・ｌ９６ｌ・ ＭＥＭＩＳＰ算法则是基于内存索引的。Ｇａｒｏｆａｌａｋｉｓ等人通过利用 正则表达式约束方法提出了ＳＰＩＲＩＴ算法。 ２ １ １ 类Ａｐ￣ｏｆｉ算法：ＡｐｒｉｏｒｉＡｌｌ、ＡｐｒｉｏｒｉＳｏｍｅ、ＤｙｎａｍｉｃＳｏｍｅ 候选序列的方法上：ＧＳＰ每次相同长度的候选集是通过连接在 前一次扫描得到的频繁序列来产生的；而ＭＦＳ候选集则是通 过连接不同长度的所有已知频繁序列来产生的。实验结果表 明ＭＦＳ与ＧＳＰ产生相同的频繁序列集合，但在降低１／０消耗 方面要比ＧＳＰ高效。 此外，文献［５］介绍了一个通用的序列模式挖掘框架。它 文献［１］中提出的类Ａｐｆｉｏｆｉ序列模式挖掘算法是经典的 关联规则挖掘算法Ａｐｆｉｏｆｉ算法的变形。它将序列模式挖掘分 为五个阶段。假定事务数据库有三个属性：顾客ＩＤ、交易时间 和购买商品。第一阶段为排序阶段，原始事务数据库进行索 引，顾客ＩＤ是主键，交易时间是辅助键，结果是顾客序列的集 合。第二阶段为频繁项集阶段，即找出所有的频繁项集，每个 大项集对应着一个频繁１一序列。第三阶段为转换阶段，将原 始数据库中的顾客序列转换为它们相应的频繁项集。第四阶 将不同的约束，如结构、时间、项以及概念层次等都集成到一个 统一的系统中，而且也提出了相应的序列模式计算方法和阈值 的设置方法。 ２，１ ３ ＰｒｅｉｆｘＳｐａｎ算法 文献［６］提出的ＰｒｅｉｆｘＳｐａｎ算法是一种使用数据库投影技 段找出所有的频繁序列。第五阶段为最大化阶段，是从频繁序 列集合中找出最大序列集即频繁模式集。 算法ＡｐｒｉｏｒｌＡｌｌ与Ａｐｒｉｏｒｌ类似，首先遍历数据生产候选序 列并利用Ａｐ６ｏｆｉ的特性进行剪枝来得到频繁序列。每次遍历 时通过连接上一次得到频繁序列来生成新的长度加１的候选 序列。然后对每个候选序列进行扫描，按照最小支持度来确定 哪些序列是频繁序列模式。它的主要缺点是遍历数据库次数 太多，而且产生了太多的候选序列，因此它的效率并不高。 算法ＡｐｆｉｏｆｉＳｏｍｅ与ＡｐｒｉｏｒｉＡｌ１只是在序列阶段有所不同， ＡｐｒｉｏｒｉＡｌｌ是首先生成所有的频繁序列后再在最大化序列阶段 删除那些非最大的序列。ＡｐｆｉｏｆｉＳｏｍｅ将序列分成两个部分分 别计数：前半部分只对一定长度的序列计数；后半部分跳过已 经计数的序列。在实际过程中两个部分是混合在一起的，以减 少候选序列占用的资源。 算法ＤｙｎａｍｉｃＳｏｍｅ与ＡｐｆｉｏｆｉＳｏｍｅ相似，仅多了一个初始 化阶段。在前半部分跳过对预先设定好的一定长度的候选序 列的计数；后半部分的算法与ＡｐｆｉｏｆｉＳｏｍｅ完全相同。其效率 不及ＡｐｒｉｏｒｉＡｌｌ和ＡｐｆｉｏｆｉＳｏｍｅ高，是由于在前半部分产生太多 的候选。后两者的优点是可避免计数许多非最大序列。 ２，１．２ ＧＳＰ算法 文献［２］提出的ＧＳＰ算法也是一个基于Ａｐｒｉｏｒｉ的频繁模 式挖掘算法。它在以下三个方面进行改进：ａ）增加了时间约 束，在序列的邻近元素之间增加了最大和最小间隔。如果邻近 元素没有介于它们两者之间，则认为这两个元素不是在序列中 连续的元素。ｂ）定义了一个滑动窗口来弱化事务的定义，允 许项来自不同的事务，只要这些事务在指定的滑动窗口范围 内。Ｃ）对序列中的项使用了概念层次进行分层，使得挖掘过 程可以在多个概念层上进行。在ＧＳＰ中候选序列的数目大大 减少了，而且在挖掘过程中引入了时问约束和概念分层来生成 更多知识，因此ＧＳＰ相对于ＡｐｒｉｏｒｉＡｌｌ有着较好的性能。 ＡｐｒｉｏｒｉＡｌｌ中所有在数据库中的序列都被表示为它们包含 的子序列，所以很容易得到候选序列的支持数。由于在ＧＳＰ 中引入了最大和最小时间间隔，得到候选序列的支持数相对较 困难。在此ＧＳＰ在计算候选序列支持数时采用了ｈａｓｈ树来提 高算法的效率。 由于ＧＳＰ与ＡｐｆｉｏｆｉＡｌｌ一样都需要多次遍历数据，为了提 高挖掘效率，文献［４］中提出一种基于ＧＳＰ的算法ＭＦＳ（ｍｉ— ｎｉｎｇ ｆｒｅｑｕｅｎｔ ｓｅｑｕｅｎｃｅ），它不需要多次遍历数据库。ＭＦＳ提出 了一个两阶段的算法，首先挖掘样本数据库来获得频繁序列的 一个粗糙评价。基于这些评价，遍历数据库去检查并细化候选 序列直到没有频繁序列再产生。ＭＦＳ与ＧＳＰ的区别是在生成 术的序列模式挖掘算法，其性能优于ＧＳＰ与ＡｐｒｉｏｒｉＡｌｌ，且拥有 能够处理非常大的序列数据库的能力。ＰｒｅｆｉｘＳｐａｎ主要使用数 据库投影方法来使下一次遍历的数据库变得更小，它不需要产 生候选序列，只要根据它们的前缀递归地将后缀投影到投影数 据库中，然后对投影数据库进行挖掘来得到频繁序列模式。为 了提高算法性能，它研究了三种投影技术：逐层投影、隔层投影 以及伪投影。 逐层投影第一步是扫描序列数据库来得到长度为１的序 列，实际上也就是１一频繁序列。然后根据１一频繁序列将数据 库分为不同的部分。每一个部分是将相应的１一频繁序列作为 前缀序列数据库的投影。投影数据库仅包含这些序列的后缀， 通过遍历投影数据库产生所有以１一序列模式作为前缀的２一序 列模式；投影数据库再次根据２一频繁模式分成各个部分。递 归地执行上述步骤直到投影数据库为空或者再没有频繁序列 模式产生。 隔层投影用来减少投影数据库的大小和数目，它首先扫描 序列数据库，产生所有长度为１的序列模式，再次扫描序列数 据库，构造相应的下三角矩阵来得到所有长度为２的序列模 式。接下来构造长度为２的序列模式所对应的投影数据库，对 每个投影数据库重复上面的操作，直到没有新的序列模式产生 为止。 当投影数据库能够存储在内存时可使用伪投影技术。事 实上它并没有构建物理投影数据库。每一个后缀用一对指针 和偏移量来表示。由于避免了复制数据库，伪投影比其他两种 投影方法更加高效，然而它的限制是数据库的大小必须能存储 在内存中。 文献［７］提出的ＦｒｅｅＳｐａｎ同样是基于投影数据库的算法。 其基本思想是将频繁序列的挖掘与频繁模式的挖掘结合起来， 并投影序列数据库以精简搜索空间，并减少候选子序列的数 目。它只需在原始数据库进行三次扫描，基于当前已经得到的 频繁集，递归地将数据库投影到一系列较小的数据库上，在投 影数据上进行子序列挖掘。这样产生了较少的候选序列。文 献［８］中提出的ｇＳｐａｎ算法结合了图模式生长和频繁计数，形 成了有效的结构模式挖掘算法。文献［９］中提出一种ＳＰＭＤＳ 算法通过对投影数据库的伪投影作单项杂凑函数，检测是否存 在重复的投影，避免大量重复扫描数据库。 ２．１．４ ＳＰＡＤＥ算法 文献［３］提出的ＳＰＡＤＥ算法是利用格技术和简单的连接 方法来挖掘频繁序列模式的一种高效算法。它仅需扫描三次 数据库即可挖掘出所有的频繁序列；同时利用格技术将挖掘搜 索空问分解为若干个较小的搜索空间，每个小的搜索空间可以 维普资讯 http://www.cqvip.com ・１９６２・ 计算机应用研究 第２５卷 存储在内存中。实验表明，ＳＰＡＤＥ方法性能要优于ＡｐｒｉｏｒｉＡｌｌ 则是首先挖掘多维信息的模式，然后再挖掘多维信息投影下的 和ＧＳＰ。 数据库序列模式。由于通常多维序列模式的长度较短，投影数 在该算法中，序列数据库被转换为垂直数据库格式，通过 据库仅包含那些带频繁序列模式的元组，多维序列模式挖掘更 扫描垂直数据库来生成１一频繁序列，第二次遍历数据库时生 加高效多产。实验结果表明，多数情况下Ｓｅｑ—Ｄｉｍ有着良好的 成新的垂直数据库以及２一序列，用生成的２一序列来构建格，使 性能；当维数较低时多维模式也较短，ＵｎｉＳｅｑ较其他两种方法 得具有相同前缀项的序列在同一格内，这样格被分解为足够小 高效；Ｄｉｍ—Ｓｅｑ在挖掘过程中许多模式并未形成多维序列模 并能存入内存中。在第三次扫描数据库过程中，通过用时态连 式，因此效率较低。 接的方法产生所有的频繁序列。同时该算法采用广度优先搜 ２．３ 增量式序列模式挖掘算法 索（ＢＦＳ）和深度优先搜索（ＤＦＳ）策略来产生频繁序列。与 现实世界中序列数据集往往是实时更新的。相应地，有趣 ＧＳＰ生成候选过程一样利用Ａｐｒｉｏｒｉ特性进行剪枝。 模式在多次挖掘时也会随时间呈现出某种变化，已有的规则可 ２．１．５ ＭＥＭＩＳＰ算法 能不再有效，而新的有趣模式还有待进一步发现。通常有两种 在文献［１０］中提出的ｍｅｍｏ￣ｉｎｄｅｘｉｎｇ ｆｏｒ ｓｅｑｕｅｎｔｉａｌ ｐａｔ— 维护规则的方式：第一种方法是强更新，重新进行挖掘，用新的 ｔｅｒｎ ｍｉｎｉｎｇ（ＭＥＭＩＳＰ）是基于内存索引的序列模式挖掘方法。 规则来替换所有旧的规则；第二种是弱更新，仅重新计算与增 ＭＥＭＩＳＰ只需要遍历一次或最多两次数据库，并且它避免生成 量有关的数据，替换不适用的旧规则。考虑到序列模式挖掘的 候选序列和投影数据库。实验结果表明，ＭＥＭＩＳＰ比ＧＳＰ和 复杂性，更加倾向于采用弱更新的方式。增量式序列模式挖掘 ＰｒｅｆｉｘＳｐａｎ要高效，而且对于数据库大小和数据序列数目有着 关注于当数据持续增加或减少时来维护序列模式。 良好的线性可伸缩性。 文献［１３］提出了一种基于ＧＳＰ和一种基于ＭＦＳ的增量 对于那些能够存储在内存中的数据库，该算法首先扫描数 式挖掘算法。在文献［１４］提出了一种基于ＳＰＡＤＥ的增量挖 据库并把它写到内存中形成ＭＤＢ（ｍｅｍｏ￣ｄａｔａｂａｓｅ），在这个 掘算法ＩＳＭ。文献［１５，１６］分别给出了ＩＳＥ和ＩＵＳ算法。同时 过程中计算１一序列的支持数来得到１一频繁序列；然后再利用 文献［１６］还讨论了在何时需要更新序列模式。增量式序列模 １一频繁序列以及构造内存索引来生产序列模式；最后用索引以 式挖掘定义为：给定序列数据库，通过插入或删除序列形成新 及ＭＤＢ根据支持度大小找到频繁模式。循环执行直到再没有 的序列数据库，在新的序列数据库中寻找所有的最大频繁序列 新的序列模式产生为止。 模式。 对于那些较大的不能装入内存的数据库，该算法把它分解 文献［１３］中提到的ＧＳＰ＋与ＭＦＳ＋算法是基于ＧＳＰ算法 为各个能够存储在内存中的部分，然后每个部分分别应用 的增量式序列模式挖掘算法。ＧＳＰ＋与ＧＰＳ有着相同的结构， ＭＥＭＩＳＰ来得到频繁模式，整个候选序列模式从各个部分集成 根据在前一次扫描中生成的频繁序列来得到候选序列；不同的 得到。最终的频繁序列模式的确定需要根据实际的支持度再 是ＧＰＳ＋采用了不同的剪枝策略，它仅仅去遍历更新的那部分 次遍历数据库。大型数据库仅需遍历两次。 数据库来检测候选序列的支持数，同时文献给出了两个剪枝策 ２．１．６ ＳＰＩＲＩＴ算法 略的定理，基于这两个定理的剪枝技术，减少了候选序列的数 在文献［１１］中提出的ＳＰＩＲＩＴ（ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ 目。同样的剪枝策略亦用于ＭＦＳ＋算法中，它首先将在旧的数 ｗｉｔｈ ｒｅｇｕｌａｒ ｅｘｐｒｅｓｓｉｏｎ ｃｏｎｓｔｒａｉｎｔｓ）算法是在通过正则表达式约 据库中得到频繁序列作为新数据库的频繁序列集的评价。将 束来挖掘用户特定序列模式的一种挖掘算法。这种方法避免 所有可能的１一序列看做候选序列，通过扫描新旧数据集能够 了挖掘用户不感兴趣的模式的浪费，同时也避免了挖掘那些潜 得到所有这些候选序列的支持数。利用最小支持度阈值，将最 在的并无用处的模式。 大频繁序列放入集合中。在数据集上进行剪枝，并循环这个过 传统的序列模式挖掘用户参与挖掘只是给定了一个最小 程直到再没有生成候选或者再没有频繁序列模式产生。 支持度，用户参与对特定的问题作出经验判断，此外还会产生 文献［１４］中提出一种基于ＳＰＡＤＥ方法的增量式序列模 大量的无用结果。ＳＰＩＲＩＴ算法是受用户限制的挖掘，将用户 式挖掘算法ＩＳＭ。ＩＳＭ算法在数据库更新时不仅能获得频繁 指定的正则表达式也加入到算法中，使用户参与到模式挖掘过 模式，而且它提供一个与用户交互的接口，用于修正最小支持 程中，算法本身与ＧＳＰ算法非常相似，只是在其中加入了一系 度与包含或不包含项等的限制。ＩＳＭ算法假定在旧的数据库 列能够读取和中断正则表达式限制的操作。最终形成的序列 所有序列模式均已计算出支持数，并且这些序列的反向边界以 模式综合考虑了最小支持度与用户的约束条件。针对不同的 及支持数可用在一个格里。通过构建一个增量序列格（ｉｎｃｒｅ— 约束程度，文中形成了四种不同的算法，ＳＰＩＲＩＴ［Ｎ］、ＳＰＩＲＩＴ ｍｅｎｔｌａ ｓｅｑｕｅｎｃｅ ｌａｔｔｉｃｅ，ＩＳＬ）并利用其特性，为潜在的新的序列 ［Ｌ］、ＳＰＩＲＩＴ［Ｖ］、ＳＰＩＲＩＴ［Ｒ］，它们的约束程度依次增强。 缩小了搜索空间。使用垂直数据存储方式在建立数据结构方 ２．２多维序列模式挖掘 面的花销要比其他大多数序列模式挖掘算法在速度上有所 单维挖掘序列模式只关心一个带有时间戳的属性，多维序 提高。 列模式的挖掘目的则是寻找不同维度属性具有更多信息的有 ＩＳＭ算法仅仅考虑了增加新的序列情况，文献［１５］中同时 用模式。文献［１２］中阐述了多维序列模式挖掘的思想，并提 考虑了增加新序列以及在序列中增加新后缀的情况，并提出一 出了三种挖掘多维序列模式的方法，分别是Ｓｅｑ—Ｄｉｍ、Ｄｉｍ—Ｓｅｑ 种新算法ＩＳＥ。假定旧数据库中最大频繁模式的长度为ｋ，ＩＳＥ 以及ＵｎｉＳｅｑ算法。ＵｎｉＳｅｑ算法将多维信息融入到序列中形成 算法将挖掘过程分为两个子问题，对于那些长度大于ｋ的候选 新的序列数据库，然后按照ＰｒｅｆｉｘＳｐａｎ方法对新的序列数据库 序列，直接应用ＧＳＰ算法。而对于那些长度小于或等于ｋ的 进行挖掘。Ｓｅｑ—Ｄｉｍ算法首先挖掘原始序列的序列模式，然后 序列进行如下操作：第一次遍历新增数据库，并计算每个单独 对序列投影下的数据库多维信息的模式进行挖掘。Ｄｉｍ—Ｓｅｑ 项的支持数。利用先前挖掘结果，能够得到在旧数据库中并不 维普资讯 http://www.cqvip.com
第７期 陈卓，等：序列模式挖掘综述 ・１９６３・ 频繁的频繁序列集合，定义为Ｌｄｂｌ。通过连接Ｌｄｂｌ生成２候 选序列进行后检测它们是否存在于新增数据库中。遍历数据 库从２候选序列中得到２．频繁序列。将那些按照时间顺序的 Ｌｌｄｂ的序列与相应的序歹Ｉｊ关联起来。依次循环，直到再没有 小于等于ｋ＋１的候选序列生成。两种剪枝技术用于优化ＩＳＥ 算法，旨在利用当前信息在早期减少生成候选序列的数量。 １ＳＥ仅考虑在原始数据库中扩展频繁序列的后缀，而文献 大模式算法非常相似。在第一次扫描时生成所有周期的１一频 繁模式和候选频繁模式；第二次扫描时生成所有周期的命 中集。 实验证明在单周期与多周期模式挖掘中，用最大子模式命 中集方法要优于基于Ａｐｒｉｏｒｉ算法。原因是扫描时间序列数据 库的次数和所需空问存储明显减少，同时基于最大子模式命中 集算法仅扫描两次数据库，而Ａｐｒｉｏｒｉ则需多次扫描数据库，对 于挖掘非常大的数据库时基于Ａｐ６ｏｆｉ算法需要很大的磁盘存 ［１６］中提出的ＩＵＳ算法同时考虑了扩展前缀和后缀，它也像 ＩＳＭ算法一样应用了反向边界，但ＩＳＭ中没有内存管理方法。 ＩＵＳ定义了反向边界的最小约束，只有那些支持度超过这个约 储空间和Ｉ／０操作。 束的序列才能被反向边界包含，因此ＩＵＳ算法需要的内存空间 较小。 文献［１７］中提出一种ＩｎｃＳｐａｎ算法，引入近似频繁序列 集、逆向匹配和共享投影等新思路进行增量挖掘。在文献 ［１８］中提出了一种可迭代的移动序列模式挖掘及增量更新方 法，该方法基于投影技术，只需要对数据库进行一次扫描。文 献［１９］中提出了分布式序列模式挖掘的思想并给出相应的算 法。文献［２０］给出了序列模式图的概念，并由此来挖掘序列 模式。 ２．４周期模式挖掘 周期模式挖掘可看做序列模式挖掘的延伸，它旨在时间序 列数据库发现所有的再生模式。周期模式挖掘有以下三种任 务：ａ）全周期模式挖掘，在时间序列中的每一个点都为时间序 列周期模式做出贡献。ｂ）部分周期模式挖掘，时间序列的其 中部分为周期模式做出贡献。Ｃ）周期关联规则挖掘，关联规 则是周期发生的事件集合。 大多数全周期模式挖掘可以用统计分析方法或者转换为 序列模式挖掘。部分周期模式挖掘在现实世界中普遍发生，因 此周期模式挖掘大多数有意义的问题集中在此。部分周期模 式挖掘定义为时间序列在一个时期内或者在一个特定周期范 围内挖掘序列所有频繁模式。文献［２１—２４］讨论了部分周期 模式挖掘。其中文献［２１］中韩家炜介绍了部分周期模式挖掘 的难点，并提出了单周期与多周期模式的两种挖掘算法。 单周期模式挖掘旨在对于给定周期、支持度约束和可信度 约束，在时间序列中发现所有的部分周期模式。一种方法是将 序列分割成周期片断后直接应用传统的Ａｐｒｉｏｒｉ算法来进行挖 掘，使用Ａｐｒｉｏｒｉ特性来进行剪枝大序列的候选，发现频繁序列 的问题与在关联规则中找到频繁项集类似。在此算法中扫描 的总数不多于周期的长度。在这个方法中最坏情况下需要的 存储空间为２ 一１，Ｆ是１一频繁模式的数目。另一种方法叫做 最大子模式命中集方法。在周期片断中候选模式中的最大子 模式即为命中集。整个时问序列Ｓ的命中集是所有在Ｓ中的 频繁最大子模式的集合。与Ａｐｒｉｏｒｉ算法中一样在第～次扫描 时产生１一频繁模式，在第二次扫描，生成每个周期片断的命中 集以及支持数，并存储在树结构中。序列频繁模式从带有计数 的命中集中得到。在这个算法中仅需扫描两次数据库，存储空 间为ｒａｉｎ｛ｍ，２ 一１｝，ｍ是时间序列的周期总和。 以单周期利用基于命中集方法为原始方法，部分周期模式 的多周期模式挖掘直接将最大模式命中集方法应用到序列的 每一个周期。该方法由于序列中有ｋ个循环，ｋ为在特定范围 的周期数目，扫描次数是２ Ｘ ｋ，需要的空间为∑ ｋ。ｒａｉｎ｛ｍ，， ２ ｝。多周期模式挖掘的另外一种方法与单周期模式挖掘最 由于时间序列数据库随时变化，在文献［２２］中提出部分 周期模式的增量挖掘算法。该挖掘算法结合了两个挖掘数据 库。上述周期模式的研究焦点在于挖掘同步的周期模式，但是 实际上由于存在随机性和噪声干扰，有一些周期模式不能被识 别。文献［２３］提出时问序列数据异步周期模式挖掘，用于发 现那些在子序列频繁发生但可能随干扰而变化的模式。文献 ［２４］中介绍在噪声环境下的序列模式挖掘相关研究。ＭＯＷ— ＣＡＴＬ（ｍｉｎｉｍａｌ ｏｃｃｕｒｒｅｎｃｅｓ ｗｉｔｈ ｃｏｎｓｔｒａｉｎｔｓ ａｎｄ ｔｉｍｅ ｌａｇｓ）方 法 从序列中找出周期性片段的事件相关模式，并应用于预 测其他序列的类似事件。 ３结束语 近些年来，序列模式挖掘取得了长足进步，但处于发展阶 段，面临着不少问题：ａ）序列模式挖掘过程中如何让用户有效 参与到挖掘过程中，与相关领域知识相结合进行有指导的挖 掘，避免挖掘的盲目性。ｂ）序列模式挖掘的评价还没有一个 统一的标准和框架。Ｃ）阈值的设定还没有好的方法来评判， 如可信度、支持度与感兴趣度。ｄ）针对海量数据，序列模式挖 掘在挖掘效率上还不高。 ． 本文认为，以下几个方面是序列模式挖掘今后的发展方 向：将先验知识、领域知识与计算智能算法相结合来指导挖掘 过程，以缩小搜索空间，提高算法效率以及规则的兴趣度；多维 序列模式挖掘，寻找不同维度属性具有更多信息的有用模式； 增量式挖掘，进行规则的更新与维护；周期模式的关联规则挖 掘的高效算法；分布式序列模式挖掘以及序列模式图的研究； 设计面向非关系数据库（面向对象数据库、多维数据库、数据 仓库）的序列模式挖掘算法。 参考文献： ［１］ＡＧＲＡＷＡＬ Ｒ，ＳＲＩＫＡＮＴ Ｒ．Ｍｉｎｉｎｇ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｎｒ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ １ １ ｔＩｌ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ．Ｔａｉｐｅｉ：［Ｓ． ｎ，］，１９９５， ［２］ＳＲＩＫＡＮＴ Ｒ，ＡＧＲＡＷＡＬ Ｒ．Ｍｉｍｎｇ ｓｅｑｕｅｎｔｉｌａ ｐａａｅｒｎｓ：Ｇｅｎｅｒａｌｉｚａｔｉｏｎｓ ａｎｄ ｐｅｒｆｏｒｍａｎｃｅ ｉｍｐｒｏｖｅｍｅｎｔｓ［Ｃ］／／Ｐｒｏｅ ｏｆ ｔｈｅ ５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎ— ｆｅｒｅｎｃｅ ｏｎ Ｅｘｔｅｎｄｉｎｇ Ｄａｔａｂａｓｅ Ｔｅｃｈｎｏｌｏｇｙ．Ａｖｉｇｎｏｎ：［Ｓ．ｎ．］，１９９６． ［３］ＺＡＫＩ Ｍ Ｊ．ＳＰＡＤＥ：Ａｎ ｅｆｆｉｃｉｅｎｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｉｎｉｎｇ ｆｒｅｑｕｅｎｔ ｓｅ— ｑｕｅｎｃｅｓ［Ｊ］．Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ。２００１，４１（１）：３１—６０． ［４］ＺＨＡＮＧ Ｍ，ＫＡＯ Ｂ，ＹＩＰ Ｃ，ｅｔ ａ１．Ａ ＧＳＰ—ｂａｓｅｄ ｅｆｉｆｃｉｅｎｔ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｉｎｉｎｇ ｆｅｑｕｅｎｔ ｓｅｑｕｅｎｃｅｓ［Ｃ］／／Ｐｉｎｅ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｉｆｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ．Ｎｅｖａｄａ：［Ｓ．ｎ．］，２００１． ［５］ＪＯＳＨＩ Ｍ，ＫＡＲＹＰＩＳ Ｇ，ＫＵＭＡＲ Ｖ．Ａ ｕｎｉｖｅｒｓａｌ ｆｏｍｒｕｌａｔｉｏｎ ｏｆ ｓｅ— ｑｕｅｎｔｉｌａ ｐａｔｔｅｍｓ［Ｃ］／／Ｐｒｏｅ ｏｆ ｔｈｅ ＫＤＤ’２００１ Ｗｏｒｋｓｈｏｐ ｏｎ Ｔｅｍｐｏｒａｌ Ｄａｔａ Ｍｉｎｉｎｇ、Ｓａｎ Ｆｒａｎｃｉｓｃｏ：［ｓ．ｎ．］，２００１． （下转第１９７６页） 维普资讯 http://www.cqvip.com ・１９７６・ 计算机应用研究 第２５卷 蘑 （ａ）Ｅｉ１５１ （ｂ）Ｅｉ１７６ （ｃ）Ｋｒｏａｌ００ （ｄ）Ｌｉｎ３１８ 局部优化加快了蚂蚁算法的收敛速度，避免了早熟和停滞现象 的发生，增强了寻优能力。经过多个ＴＳＰ实例测试，实验结果 表明：对中小规模的ＴｓＰ，该算法基本上能找到最优解；对大规 模的ＴＳＰ，也能明显地改善解的质量。 参考文献： ｆ １ ｆ ＤＯＲＩＧＯ Ｍ，ＧＡＭＢＡＲＤＥＬＩ Ａ Ｉ Ｍ．Ａｎｔ ｃｏｌｏｎｙ ｓｙｓｔｅｍ：ａ ｃｏｏｐｅｒａｔｉｖｅ 图２各ＴＳＰ实例的最好路径 对Ｋｒｏａ１００、ＬＯＡＣＡ和ＡＣＡ算法的收敛特性比较如图３ 所示。从图中可以看出，对于基本蚁群算法，路径长度变化大 （２２ ２８８～３８ ２１８，前五次迭代在图中未列出），收敛速度慢；而 优化算法路径长度变化小（２１ ２８２～２１ ６１０），收敛速度快，仅 用了２５轮即取得已知最优解２１ ２８２。 ｌｅａｒｎｉｎｇ ａｐｐｒｏａｃｈ ｔｏ ｔｈｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ，１９９７，１（１）：５３—６６． ［２］ＴＡＬＢＩ Ｈ，ＤＲＡＡ Ａ，ＢＡＴＯＵＣＨＥ Ｍ．Ａ ｎｅｗ ｑｕａｎｔｕｍ—ｉｎｓｐｉｒｅｄ ｇｅｎｅｔｉｃ ａｌ— ｇｏｒｉｔｈｍ ｆｏｒ ｓｏｌｖｉｎｇ ｔｈｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ［Ｃ］／／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｄｕｓｔｉａｒｌ Ｔｅｃｈｎｏｌｏｇｙ．２００４：１ １９２—１ １９７． ［３］ＳＯＮＧ Ｃｈｉ—ｈｕａ，ＬＥＥ Ｋ，ＬＥＥ Ｗ Ｄ．Ｅｘｔｅｎｄｅｄ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ｆｏｒ ａｕｇｍｅｎｔｅｄ ＴＳＰ ａｎｄ ｍｕｌｔｉ—ｓａｌｅｓｍｅｎ ＴＳＰ［ｃ］／／Ｐｒｃｏ ｏｆ Ｉｎｔｅｎａｒｉｔｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ．２００３：２３４０－２３４３． ［４］ＭＩＣＨＥＬ Ｇ，ＧＩＬＢＥＲＴ Ｌ，ＦＲＥＤＥＲＩＣ Ｓ．Ａ ｔａｂｕ ｓｅａｒｃｈ ｈｅｕｒｉｓｔｉｃ ｆｏｒ ｔｈｅ ｕｎｄｉｒｅｃｔｅｄ ｓｅｌｅｃｔｉｖｅ ｔｒａｖｅｌｉｎｇ ｓａｌｅｓｍａｎ ｐｒｏｂｌｅｍ［Ｊ］．Ｅｕｒｏｐｅａｎ Ｊ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ，１９９８，１Ｏ６（１）：５３９—５４５． ［５］ＹＡＮＧ Ｈａｉ—ｑｉｎｇ，ＹＡＮＧ Ｈａｉ—ｈｏｎｇ．Ａｎ ｓｅｌｆ－ｏｒｇａｎｉｚｉｎｇ ｎｅｕｒｌａ ｎｅｔｗｏｒｋ ６ ８ １４ １６ １７ ２５ ３４ ５Ｏ ５１ ４１７ １ ０００ ｉｔｅｒａｔｉｏｎ ｗｉｔｈ ｃｏｎｖｅｘ—ｈｕｌｌ ｅｘｐａｎｄｉｎｇ ｐｒｏｐｅｒｔｙ ｆｏｒ ＴＳＰ［ｃ］／／Ｐｒｏｃ ｏｆ Ｉｎｔｅｒｎａ— ｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒｌ Ｎｅｔａｗｏｒｋｓ ａｎｄ Ｂｒａｉｎ．２００５：３７９—３８３． 图３ ＬＯＡＣＡ和ＡＣＡ的收敛特性对比 ［６］王文峰，刘光远，温万惠．求解ＴＳＰ问题的混合离散粒子群算法 ［Ｊ］．西南大学学报：自然科学版，２００７，２９（１）：８５－８８． ［７］黄雪梅，李涛，徐春林，等．一种基于免疫遗传的ＴＳＰ求解方法 ４ 结束语 本文根据ＴＳＰ的特点，设计了三种局部优化算子，每一轮 搜索结束后，采用该算子对结果路径进行变异，以寻求更优解。 （上接第１９６３页） ［Ｊ］．四川大学学报：工程科学版，２００６，３８（１）：８６．９１． ［８］孙力娟，王良俊，王汝传．改进的蚁群算法及其在ＴＳＰ中的应用研 究［Ｊ］．通信学报，２００４，２５（１０）：１１１－１１６， Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ．１９９９：２５１－２５８． ［６］ＰＥＩ Ｊ，ＨＡＮ Ｊ．ＰｒｅｆｉｘＳｐａｎ：ｍｉｎｉｎｇ ｓｅｑｕｅｎｔｉｌａ ｐａｔｔｅｒｎｓ ｅｆｆｉｃｉｅｎｔｌｙ ｂｙ ｐｒｅｆｉｘ－ｐｒｏｊｅｃｔｅｄ ｐａｔｔｅｒｎ ｇｒｏｗｔｈ［ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ７ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ ＤＣ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏ— ｃｉｅｔｙ，２００１：２１５－２２４． ［１５］ＭＡＳＳＥＧＬＩＡ Ｆ，ＰＯＮＣＥＬＥＴ Ｐ，ＴＥＩＳＳＥＩＲＥ Ｍ．Ｉｎｃｒｅｍｅｎｔａｌ ｍｉｎｉｎｇ ｏｆ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎｓ ｉｎ ｌａｒｇｅ ｄａｔａｂａｓｅｓ［Ｊ］．Ｄａｔａ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｅｎ－ ｇｉｎｅｅｒｉｎｇ，２００３，４６（１）：９７—１２１． ［７］ＨＡＮ Ｊ，ＰＥＩ Ｊ，ＭＯＲＴＡＺＶＩ—ＡＳＬ Ｂ，ｅｔ ａ１．ＦｒｅｅＳｐａｎ：ｆｒｅｑｕｅｎｔ ｐａｔｔｅｒｎ－ ｐｒｏｊｅｃｔｅｄ ｓｅｑｕｅｎｔｉｌａ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ６ｔｈ ＡＣＭ ＳＩＧＫ－ ＤＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎ— ｉｎｇ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ，２０００：３５５－３５９． ［１６］ＺＨＥＮＧ Ｑｉｎｇ－ｇｕｏ，ＸＵ Ｋｅ，ＭＡ Ｓｈｉ—ｌｉｎｇ，ｅｔ ａ１．Ｔｈｅ ａｌｇｏｒｉｔｈｍｓ ｏｆ ｕｐｄａ— ｔｉｎｇ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎｓ［Ｃ］／／Ｐｒｃ ｏｆｏ ｔｈｅ ５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｗｏｒｋｓｈｏｐ ｏｎ Ｈｉｇｈ Ｐｅｒｆｏｒ—ｍａｎｃｅ Ｄａｔａ Ｍｉｎｉｎｇ．Ｗａｓｈｉｎ【ｔｏｎ ＤＣ：［ｓ．ｎ．］，２００２．ｇ ［１７］ＣＨＥＮＧ Ｈｏｎｇ，ＹＡＮ Ｘ，ＨＡＮ Ｊ．ＩｎｃＳｐａｎ：ｉｎｃｒｅｍｅｎｔｌａ ｍｉｎｉｎｇ ｏｆ ｓｅ— ｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎｓ ｉｎ ｌａｒｇｅ ｄａｔａｂａｓｅ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ｌＯｔｈ Ｉｎｔｅｒｎａｔｉｏ． ｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ．Ｎｅｗ Ｙｏｒｋ： ＡＣＭ Ｐｒｅｓｓ，２００４：５２７－５３２． ［８］ＨＡＮ Ｊ，ＰＥＩ Ｊ，ＹＡＮ Ｘ．Ｆｒｏｍ ｓｅｑｕｅｎｔｉｌａ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ ｔｏ ｓｔｒｕｃｔｕｒｅｄ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ：ａ ｐａｔｔｅｒｎ—ｇｒｏｗｔｈ ａｐｐｒｏａｃｈ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，２００４，１９（３）：２５７—２７９． ［１８］牛兴雯，杨冬青，唐世渭，等．ＯＳＡＦ２ｔｒｅｅ——可迭代的移动序列 模式挖掘及增量更新方法［Ｊ］．计算机研究与发展，２００４，４１ （１Ｏ）：１７６１－１７６７． ［９］张坤，朱杨勇．无重复投影数据库扫描的序列模式挖掘算法［Ｊ］． 计算机研究与发展，２００７，４４（１）：１２６—１３２． ［１０］ＬＩＮ Ｍｉｎｇ－ｙｅｎ，ＬＥＥ Ｓ Ｙ．Ｆａｓｔ ｄｉｓｃｏｖｅｒｙ ｏｆ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎｓ ｂｙ ｍｅｍｏｒｙ ｉｎｄｅｘｉｎｇ［ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ４ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｗａｒｅｈｏｕｓｉｎｇ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ．Ｌｏｎｄｏｎ，ＵＫ：Ｓｐｒｉｎｇｅｒ－ Ｖｅｒｌａｇ，２００２：１５０—１６０． ［１９］邹翔，张巍，刘洋，等．分布式序列模式发现算法的研究［Ｊ］．软件 学报，２００５，１６（７）：１２６２－１２６９． ［２Ｏ］吕静，王晓峰．序列模式图及其构造算法［Ｊ］．计算机学报，２００４， ２７（６）：７８２－７８７． ［１１］ＧＡＲＯＦＡＬＡＫＩＳ Ｍ Ｎ，ＲＡＳＴＯＧＩ Ｒ， ＳＨＩＭ Ｋ．Ｓｐｉｉｒｔ：ｓｅｑｕｅｎｔｉａｌ ｐａｔ－ ｔｅｒｎ ｍｉｎｉｎｇ ｗｉｔｈ ｒｅｇｕｌａｒ ｅｘｐｒｅｓｓｉｏｎ ｃｏｎｓｔｒａｉｎｔｓ［Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ２５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｖｅｒｙ Ｌａｒｇｅ Ｄａｔａｂａｓｅｓ．Ｓａｎ Ｆｒａｎｃｉｓｃｏ， ＣＡ：Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ Ｐｕｂｌｉｓｈｅｒｓ Ｉｎｃ，Ｉ９９９：２２３．２３４． ［２１］ＨＡＮ Ｊ，ＤＯＮＧ Ｇ，ＹＩＮ Ｙ．Ｅｆｉｃｉｆｅｎｔ ｍｉｎｉｎｇ ｏｆ ｐａｒｔｉｌａ ｐｅｒｉｏｄｉｃ ｐａｔｔｅｒｎｓ ｉｎ ｔｉｍｅ ｓｅｒｉｅｓ ｄａｔｂａａｓｅ［Ｃ】／／Ｐｒｃ ｏｏｆ ｔｈｅ １５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ．Ｗａｓｈｉｎｇｔｏｎ ＤＣ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，１９９９． ［２２］ＹＡＮＧ Ｊ，ＷＡＮＧ Ｗｅｉ，ＹＵ Ｐ Ｓ．Ｍｉｎｉｎｇ ａｓｙｎｃｈｒｏｎｏｕｓ ｐｅｒｉｏｄｉｃ ｐａｔｔｅｒｎｓ ｉｎ ｔｉｍｅ ｓｅｒｉｅｓ ｄａｔａ『Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ６ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ，２０００： ２７５．２７９． ［Ｉ２］ＰＩＮＴＯ Ｈ，ＨＡＮ Ｊ，ＰＥＩ Ｊ，ｅｔ ａ１．Ｍｕｌｔｉ—ｄｉｍｅｎｓｉｏｎａｌ ｓｅｑｕｅｎｔｉａｌ ｐａｔｔｅｒｎ ｍｉｎｉｎｇ『Ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ １０ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｍａｎａｇｅｍｅｎｔ． Ａｔｌａｎｔａ，Ｎｅｗ Ｙｏｒｋ：ＡＣＭ Ｐｒｅｓｓ，２００１： ８１．８８． ［２３］ＥＬＦＥＫＹ Ｍ Ｇ．Ｉｎｃｒｅｍｅｎｔｌａ ｍｉｎｉｎｇ ｏｆ ｐａｒｔｉａｌ ｐｅｒｉｏｄｉｃ ｐａｔｔｅｒｎｓ ｉｎ ｔｉｍｅ— ｓｅｒｉｅｓ ｄａｔａｂａｓｅｓ［ＥＢ／ＯＬ］．（２０００）．ｈｔｔｐ：／／ｃｉｔｅｓｅｅｒ．ｉｓｔ．ｐｓｕ．ｅｄｕ／ ４２１２９６．ｈｔｍ１． ［１３］ＺＨＡＮＧ Ｍｉｎｇ－ｈｕａ，ＫＡＯ Ｂ，ＣＨＥＵＮＧ Ｄ Ｗ，ｅｔ ａ１．Ｅｆｉｃｉｆｅｎｔ ａｌｇｏｒｉｔｈｍｓ ｏｒｆ ｉｎｃｒｅｍｅｎｔａｌ ｕｐｄａｔｅ ｏｆ ｆｒｅｑｕｅｎｔ ｓｅｑｕｅｎｃｅｓ［ｃ］／／Ｐｒｏｅ ｏｆ ｔｈｅ Ｐａｃｉ－ ｉｃ—Ａｓｉｆａ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ．Ｌｏｎ－ ｄｏｎ，ＵＫ：Ｓｐｒｉｎｇｅｒ－Ｖｅｒｌａｇ，２００２：１８６－１９７ ［２４］ＢＥＴＩ＇ＩＮＩ Ｃ，ＷＡＮＧ Ｘ Ｓ，ＪＡＪＯＤＩＡ Ｓ．Ｍｉｎｉｎｇ ｔｅｍｐｏｒａｌ ｒｅｌａｔｉｏｎｓｈｉｐｓ ｗｉｔｈ ｍｕｌｔｉｐｌｅ ｇｒａｎｕｌａｒｉｔｉｅｓ ｉｎ ｔｉｍｅ ｓｅｑｕｅｎｃｅｓ［Ｊ］．Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ Ｂｕｌｌｅｔｉｎ，１９９８，２１：３２—３８． ［１４］ＰＡＲＴＨＡｓＡＲＡＴＨＹ Ｓ，ＺＡＫＩ Ｍ Ｊ，ＯＧＩＨＡＲＡ Ｍ，ｅｔ ａ１．Ｉｎｃｒｅｍｅｎｔａｌ ａｎｄ ｉｎｔｅｒａｃｔｉｖｅ ｓｅｑｕｅｎｃｅ ｍｉｎｉｎｇ［ｃ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ８ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｍａｎａｇｅｍｅｎｔ．．Ｋａｎｓａｓ Ｃｉｔｙ， ［２５］ＨＡＲＭＳ Ｓ Ｋ，ＤＥＯＧＵＮ Ｊ Ｓ．Ｓｅｑｕｅｎｔｉａｌ ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅ ｍｉｎｉｎｇ ｗｉｔｈ ｔｉｍｅ ｌａｇｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ，２００４，２２ （１）：７．２２．
