序列模式挖掘算法

第6卷第6期 智能计算机与应用 V

〇1.6 N

“

2

〇 1

6 年 12

月 INTELLIGENT COMPUTER AND APPLICATIONS

2016

序列模式挖掘算法的研究

王晓雪

(

吉林师范大学计算机学院，吉林四平136000)

摘要：序列模式挖掘是数据挖掘领域中的重要技术之一,

应用非常广泛。利用序列模式挖掘算法能够发现具有一定商业价值的模式规律,

因此近年很多学者也对序列模式挖掘算法提出了改进。本文首先介绍了序列模式挖掘算法的相关背景及应用，然后对于各个算法进行介绍和

对比，最后,

对序列模式挖掘的未来发展进行了展望。

关键词：序列模式挖掘；Apriori; PrefixSpan; SPADE; MEMISP; SPIRIT

中图分类号：TP311 文献标志码：A 文章编号：2095-2163(2016)06-0132-03

Research on sequential pattern mining algorithms

WANG Xiaoxue

(Computer

School,

Jilin

Nor^nal

University,

Siping

Jilin 136000,

China)

Abstract ：

Sequential

pattern

mining

is

one

important

technolog^^

of

data

mining,

which

is

always

used

widely.

Sequential

pattern

mining

algorithms

can

be

implemented

to

discover

valuable

patterns

in

the

business

field.

Therefore

in

recent

years

many

scholars

have

been

devoted

to

improvement

of

sequential

pattern

第６卷第６期　２００７年１２月　江南大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｊｉａｎｇｎａｎ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｖｏ１．６　Ｄｅｃ．　Ｎｏ．６　２００７　

文章编号：１６７１—７１４７（２００７）０６—０７６３—０６　

基于数据流的序列模式挖掘算法　

俞单庆，　吉根林　

（南京师范大学数学与计算机科学学院，江苏南京２１００９７）　

摘　要：为了实现对数据流的序列模式挖掘，提出了基于数据流的序列模式挖掘算法ＭＦＳＤＳ一１和　ＭＦＳＤＳ一２，它们均通过调整入选度的大小来调整保存信息的粒度．算法ＭＦＳＤＳ一２利用分层存储结　构，不仅能更好地保存序列信息，而且可以通过与全局序列模式的对比得到当前活动的一些异常　

序列模式．实验结果表明，基于分层存储的算法ＭＦＳＤＳ一２的效率比算法ＭＳＦＤＳ一１高．　

关键词：序列模式挖掘；频繁序列；数据流　中图分类号：ＴＰ　３１１　文献标识码：Ａ　

Ｍｉｎｉｎｇ　Ｆｒｅｑｕｅｎｔ　Ｓｅｑｕｅｎｃｅ　ｆｒｏｍ　Ｄａｔａ　Ｓｔｒｅａｍ　

ＹＵ　Ｓｈａｎ—ｑｉｎｇ，　ＪＩ　Ｇｅｎ—ｌｉｎ　（Ｓｃｈｏｏｌ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｎａｎｊｉｎｇ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ　２１００９７，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ａｌｔｈｏｕｇｈ　ｓｅｑｕｅｎｃｅ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　ｈａｓ　ｂｅｅｎ　ｄｅｅｐｌｙ　ｓｔｕｄｉｅｄ，ｉｔ　ｉｓ　ａ　ｃｈａｌｌｅｎｇｅ　ｔｏ　ｅｘｔｅｎｄ　ｔｏ　

ｄａｔａ　ｓｔｒｅａｍｓ．Ｉｎ　ｔｈｅ　ｐａｐｅｒ，ａｌｇｏｒｉｔｈｍ　ＭＦＳＤＳ一１　ａｎｄ　ＭＦＳＤＳ一２　ａｒｅ　ｐｒｅｓｅｎｔｅｄ　ｆｏｒ　ｍｉｎｉｎｇ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎｓ　ｆｒｏｍ　ｄａｔａ　ｓｔｒｅａｍ．Ｂｏｔｈ　ｏｆ　ｔｈｅ　ａｌｇｏｒｉｔｈｍｓ　ｕｓｅ　ｔｈｅ　ｓｔｏｒａｇｅ　ｏｆ　ｅｌｅｃｔｅｄ　ｓｅｑｕｅｎｃｅｓ　

第２７卷第１期　

Ｖ０１．２７　Ｎ０．１　长春师范学院学报（自然科学版Ｊ　

Ｊｏｕｍａｌ　ｏｆ　Ｃｉｍｎ￣ｈｕｎ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　２ＯＯ８年２月　

Ｆｌ出．２０ｏ８　

序列模式挖掘算法在生物序列的应用研究　

董　萍　．　Ｉ　

（三门峡职业技术学院机电工程系，河南－－Ｈ峡４７２０００）　

［摘要】生物序列相对于传统序列来说具有自己的特征。不同的序列模式挖掘算法应用到生物序列　

中有不同的特点和效率。本文分析目前比较流行的五种模式挖掘算法的运行过程，当应用到生物序列　

中时，分析了各个算法的性能，从而可以得出哪种算法更适应于不同类型的生物序列频繁模式挖掘。　

［关键词］模式挖掘；生物序列；频繁集　

［中图分类号】ＴＰ３０１．６　［文献标识码】Ａ　【文章编号】１００８—１７８ｘ（２０ｏ８）Ｏ１—００３５—０３　

０前言　从生物序列中挖掘其共同存在的模式，即序列频繁模式挖掘，可以研究生物体的进化信息，同时也可以　

对新的序列进行预测。目前比较流行的序列模式挖掘方法分为两大类：第一种是采用序列比对的方法进行频　繁模式挖掘，例如ＢＬＡＳＴ￣　、ＦａｓｔＡＬ２　等。但是，序列比对是建立在序列同源性的基础上的，即所比对的序　

列是来自于同一个家族；如果来自于不同的家族，所比对的序列间的相似性会很低，因此比对的代价会很　

大，至今还是一个ＮＰ难题。第二种序列频繁模式挖掘方法是采用数据挖掘领域中的频繁模式挖掘算法进行　模式挖掘，最初应用于事务序列，例如，对顾客购物进行分析以及对网站点击流进行分析等等。序列模式首　

先是由Ａｇｒａｗａｌ　Ｒ和Ｓｒｉｋａｎｔ　Ｒ　提出的，研究者在随后的几年提出的算法都是基于Ａ谢　原理的改进算法。　Ｚａｋｉ等人提出了基于垂直数据表示的ＳＰＡＤＥ算法　ｊ。Ｈａｎ等提出了不产生候选集的基于模式增长的ＦＰ—　

Ｇｒｏｗｔｈ算法　。接着Ｈａｎ等又研究出了基于投影数据库的ＦｒｅｅＳｐａｎＬ７　和ＰｒｅｆｉｘＳｐａｎＬ８　算法。但是，直接将这些　

总第２５３期　２０１０年第１１期　计算机与数字工程　Ｃｏｍｐｕｔｅｒ＆．Ｄｉｇｉｔａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　ＶＯ１．３８　Ｎｏ．１１　４　

一种改进的加权序列模式挖掘算法　

孙粮磊李云尹江陈峻　（扬州大学信息工程学院扬州　２２５００９）　

摘要在加权序列模式挖掘中，基于候选码生成一测试方法的ＭＷＳＰ是目前应用性最好的算法之一，然而在挖掘过　程中容易出现候选组合爆炸的情况，为此文章提出了一种高效的加权序列模式挖掘算法（ＰＷＳＭ）。ＰＷＳＭ算法引入点一最　小加权支持数概念并利用前缀投影数据库原理有效地避免了候选组合爆炸的发生．并且在挖掘的过程中充分利用最小加　权支持数，再次对算法进行优化。实验表明，该算法较ＭＷＳＰ算法能更加有效地从序列数据库中挖掘加权序列模式。　关键词数据挖掘；加权序列模式；加权支持数　中图分类号ＴＰ３０１．６　

Ａｎ　Ｉｍｐｒｏｖｅｄ　Ｗｅｉｇｈｔｅｄ　Ｓｅｑｕｅｎｔｉａｌ　Ｐａｔｔｅｒｎ　Ｍｉｎｉｎｇ　Ａｌｇｏｒｉｔｈｍ　

Ｓｕｎ　Ｌｉａｎｇｌｅｉ　Ｌｉ　Ｙｕｎ　Ｙｉｎ　Ｊｉａｎｇ　Ｃｈｃｎ　Ｌｉｎｇ　（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｙａｎｇｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ，Ｙａｎｇｚｈｏｕ　２２５００９）　

Ａｂｓｔｒａｃｔ　Ｉｎ　ｔｈｅ　ｗｅｉｇｈｔｅｄ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ，ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ＭＷＳＰ　ｉｓ　ｏｎｅ　ｏｆ　ｔｈｅ　ｂｅｓｔ　ａｌｇｏｒｉｔｈｍｓ，ｂｕｔ　ｄｕｒｉｎｇ　ｔｈｅ　ｍｉｎｉｎｇ　ｐｒｏｃｅｓｓ，ｉｔ　ｗｉｌｌ　ｅａｓｉｌｙ　ｇｅｎｅｒａｔｅ　ｔｈｅ　ｓｉｔｕａｔ　ｉｏｎ　ｏｆ　ｃａｎｄｉｄａｔｅ　ｃｏｍｂｉｎａｔｏｒｉａｌ　ｅｘｐｌｏｓｉｏｎ　ｂｅｃａｕｓｅ　ｏｆ　ｂａｓｉｎｇ　ｏｎ　ｔｈｅ　ｃａｎｄｉｄａｔｅ　ｇｅｎｅｒａｔｉｏｎ－ａｎｄ—ｔｅｓｔ　ａｐｐｒｏａｃｈ，ｔｈｅｒｅｆｏｒｅ，ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａｎ　ｅｆｆｉｃｉｅｎｔ　ａｌｇｏｒｉｔｈｍ　ＰＷＳＭ，ｗｈｉｃｈ　ｉｎｔｒｏｄｕｃｅｓ　ｔｈｅ　ｃｏｎｃｅｐｔ　ｏｆ　Ｋ　ｍｉｎｉｍｕｍ　ｗｅｉｇｈｔｅｄ　ｓｕｐｐｏｒｔ，ｕｔｉｌｉｚｅｓ　ｔｈｅ　ｐｒｉｎｃｉｐｌｅ　ｏｆ　ｐｒｅｆｉｘ　ｐｒｏｊ　ｅｃｔｉｏｎ　ｄａｔａｂａｓｅ　ｔＯ　ａｖｏｉｄ　ｔｈｅ　ｏｃｃｕｒｒｅｎｃｅ　ｏｆ　ｃａｎｄｉｄａｔｅ　ｅｏｍｂｉ—　ｎａｔｏｒｉａｌ　ｅｘｐｌｏｓｉｏｎ，ａｎｄ　ｔａｋｅｓ　ｆｕｌｌ　ａｄｖａｎｔａｇｅ　ｏｆ　ｔｈｅ　ｍｉｎｉｍｕｍ　ｗｅｉｇｈｔｅｄ　ｓｕｐｐｏｒｔ　ｔＯ　ｏｐｔｉｍｉｚｅ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ＰＷＳＭ　ｉｓ　ｍｏｒｅ　ｅｆｆｅｃｔｉｖｅ　ｔｈａｎ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ＭＷＳＰ　ｏｎ　ｍｉｎｉｎｇ　ｗｅｉｇｈｔｅｄ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎｓ　ｆｒｏｍ　ｔｈｅ　ｓｅｑｕｅｎｃｅ　ｄａｔａｂａｓｅ．　Ｒｅｙ　Ｗｏｒｄｓ　ｄａｔａ　ｍｉｎｉｎｇ，ｗｅｉｇｈｔｅｄ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎ，ｗｅｉｇｈｔｅｄ　ｓｕｐｐｏｒｔ　Ｃｌａｓｓ　Ｎｕｍｂｅｒ　ＴＰ３０］．６　

基于Ｈ—ｔｒｅｅ的多维序列模式挖掘算法　

程银波任家东司菁菁　

（燕山大学现代教育技术中心，秦皇岛０６６００４）　

Ｅ—ｍａｉｌ：ｃｙｂ＠ｙｓｕ．ｅｄｕ．ｃｎ　

摘　要　提出了一种基于Ｈ—ｔｒｅｅ的多维序列模式挖掘算法，首先在序列信息中挖掘序列模式．然后针对每个序列模式．　根据包舍此模式的所有元组中的多维信息构造Ｈ—ｔｒｅｅ树．挖掘出相应的多维模式，从而得到了多维序列模式。该算法将　

多维分析方法与序列模式挖掘算法有效地结合在一起，当维度较高时具有较高的性能。　

关键词　数据挖掘序列模式　多雏序列模式　

文章编号１００２—８３３１～（２００６）０６—０１９３—０３　文献标识码Ａ　中图分类号ＴＰ３０１　

Ａ　Ｍｕｌｔｉ－ｄｉｍｅｎｓｉｏｎａｌ　Ｓｅｑｕｅｎｔｉａｌ　Ｐａｔｔｅｒｎ　Ｍｉｎｉｎｇ　

Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｈ－ｔｒｅｅ　

Ｃｈｅｎｇ　Ｙｉｎｂｏ　Ｒｅｎ　Ｊｉａｄｏｎｇ　Ｓｉ　Ｊｉｎｇｊｉｎｇ　

（Ｍｏｄｅｒｎ　Ｅｄｕｃａｔｉｏｎ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　Ｃｅｎｔｅｒ，Ｙａｎｓｈａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｑｉｎｈｕａｎｇｄａｏ　０６６００４）　

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｐｏｓｅｓ　ａｎ　ａｌｇｏｒｉｔｈｍ　ｂａｓｅｄ　ｏｎ　Ｈ－ｔｒｅｅ　ｆｏｒ　ｍｉｎｉｎｇ　ｍｕｌｔｉ—ｄｉｍｅｎｓｉｏｎａｌ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎｓ．Ｔｈｅ　ａｌｇｏ—　

ｒｌｔｈｍ　ｆｉｒｓｔ　ｍｉｎｅｓ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎｓ　ｉｎ　ｔｈｅ　ｄａｔａｓｅｔ，ｔｈｅｎ　ｃｏｎｓｔｒｕｃｔｓ　ｔｈｅ　ｃｏｒｒｅｓｐｏｎｄｉｎｇ　Ｈ－ｔｒｅｅ　ｔｏ　ｍｉｎｅ　ｔｈｅ　ｍｕｌｔｉ—ｄｉｍｅｎ—　

ｓｉｏｎａｌ　ｐａｔｔｅｒｎｓ．Ｂｙ　ｃｏｍｂｉｎｇ　ｅｆｆｉｃｉｅｎｔ　ｍｕｌｔｉ—ｄｉｍｅｎｓｉｏｎａｌ　ａｎａｌｙｓｔｓ　ｗｉｔｈ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　ｍｅｔｈｏｄｓ，ｔｈｅ　ａｌｇｏｒｉｔｈｍ　

第２６卷　第４期　湖北师范学院学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｈｕｂｅｉ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　Ｖｏｌ＿２６　Ｎｏ．４，２００６　

序列模式挖掘的两种典型算法及比较　

吕　橙　，张　兵　

（１．北京建筑工程学院计算机科学与技术系，北京　１０００４４；　

２．江苏行政学院现代科技部，南京　２１０００４）　

摘要：序列模式挖掘是数据挖掘的重要分支，ＧＳＰ算法与ＰＳＰ算法是序列模式挖掘中的两种典型算法。本　文介绍了这两种算法并对其进行了分析与比较。　关键词：数据挖掘；序列模式；ＧＳＰ算法；ＰＳＰ算法　中图分类号：ＴＰ　３１１　文献标识码：Ａ　文章编号：１００９－２７１４（２００６）０４—００３３　０５　

序列模式挖掘是数据挖掘的重要分支，主要用于捕获与时间相关的、重复出现从而可以用于决策　

的行为。Ａｇｒａｗａｌ等首先提出了序列模式挖掘问题　¨，后又提出了ＧＳＰ（Ｇｅｎｅｒａｌｉｚｅｄ　Ｓｅｑｕｅｎｔｉａｌ　Ｐａｔ　

ｔｅｒｎｓ）算法　。ＰＳＰ（Ｐｅｒｆｅｃｔｌｙ　Ｓｅｑｕｅｎｔｉａｌ　Ｐａｔｔｅｒｎｓ）算法　由Ｆ．Ｍａｓｓｅｇｌｉａ等提出。本文介绍了这两个序　

列模式挖掘典型算法，并对其进行了分析与比较。　

基本概念和问题描述　

相关基本概念见文献［２］。给定序列数据库、最小支持度阈值和时间约束，序列模式挖掘的目标　是找出序列数据库中所有的序列模式。　

２　ＧＳＰ算法　

给定一个事务数据库，ＧＳＰ算法需要对事务数据库进行多遍扫描。ＧＳＰ算法挖掘序列模式的基　

本架构如下：第一遍扫描确定该数据库中每一项的支持度，即确定该事务数据库中包含每一项的数据　序列的数目。在第一遍扫描结束后，该算法知道哪些项是频繁的，即产生了频繁１项集，而每个频繁　

１项集即形成了频繁１序列。由频繁　序列集合　可产生候选（后＋１）序列集合ｃ　，候选（　＋１）序　列集合中的每条候选序列均包含相同个数的项，且其项的个数均比其对应的种子频繁序列集合Ｌ　中　

第４２卷第５期　２０１５年５月　计算机科学　ＣｏｍＤｕｔｅｒ　Ｓｃｉｅｎｃｅ　Ｖｏ１．４２　Ｎｏ．５　Ｍａｙ　２０１５　

一种基于逻辑的频繁序列模式挖掘算法　

刘端阳冯建李晓粉　

（浙江工业大学计算机科学与技术学院杭州３１００２３）　

摘要传统的类Ａｐｒｉｏｒｉ频繁序列模式挖掘算法都是基于支持度框架理论，需要预先设定支持度阂值，而这通常需　

要较深的领域知识或大量的实践，因此目前仍没有一种很好的设定方法。同时，序列模式的挖掘结果往往数量很大且　

不易理解，可用性较低。针对上述问题，提出了一种基于逻辑的频繁序列模式挖掘算法即ＬＦＳＰＭ算法，并首次在频　繁序列模式挖掘算法中引入了逻辑的思想，通过逻辑规则过滤，大大优化了结果集。实验证明，该算法较好地解决了　

支持度设置问题及挖掘结果可理解性不高的问题。　关键词频繁序列模式，数据挖掘，逻辑，支持度阈值　

中图法分类号ＴＰ３１１　文献标识码Ａ　ＤＯＩ　１０．１１８９６／ｊ．ｉｓｓｎ．１００２—１３７Ｘ　２０１５．５．０５２　

Ｌｏｇｉｃ－ｂａｓｅｄ　Ｆｒｅｑｕｅｎｔ　Ｓｅｑｕｅｎｔｉａｌ　Ｐａｔｔｅｒｎ　Ｍｉｎｉｎｇ　Ａｌｇｏｒｉｔｈｍ　

ＬＩＵ　Ｄｕａｎ－ｙａｎｇ　ＦＥＮＧ　Ｊｉａｎ　Ｌ１　Ｘｉａｏ－ｆｅｎ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｚｈｅｊｉａｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｎｇｚｈｏｕ　３１００２３，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ　Ｔｒａｄｉｔｉｏｎａｌ　Ａｐｒｉｏｒｉ－ｌｉｋｅ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ａｒｅ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｔｈｅｏｒｅｔｉｃａｌ　ｆｒａｍｅｗｏｒｋ　ｏｆ　ｓｕｐ—　

ｐｏｒｔ，ｗｈｉｃｈ　ｎｅｅｄ　ｐｒｅ－ｓｅｔ　ｓｕｐｐｏｒｔ　ｔｈｒｅｓｈｏｌｄ，ｂｕｔ　ｔｈｉｓ　ｏｆｔｅｎ　ｒｅｑｕｉｒｅｓ　ｉｎ－ｄｅｐｔｈ　ｄｏｍａｉｎ　ｋｎｏｗｌｅｄｇｅ　ｏｒ　ａ　ｌｏｔ　ｏｆ　ｐｒａｃｔｉｃｅ．Ｃｏｎ—　

序列模式挖掘算法的比较与研究

摘要序列模式挖掘是数据挖掘中的一个重要研究方向,即在序列数据库中找出所有的频繁子序列。对序列模式挖掘中的典型算法的执行过程及其特点进行研究,并对其时空执行效率进行分析比较,并且做出适当的评价。

关键词序列模式挖掘;算法分析;定性比较

序列挖掘是数据挖掘中的一个研究重点,是从序列数据库中发现相对时间或者其他顺序所出现的频率子序列作为模式。其应用范围包括顾客购物行为的分析、网络访问模式分析、科学实验的分析、自然灾害的预测、DNA序列的破译等。本文以AprioriAll,GSP,FreeSpan和PrefixSpan四个典型算法为例,对两类算法进行介绍、分析和总结。

1序列模式挖掘中的典型算法

Apriori算法是关联规则挖掘的经典算法。它的思想扩展到序列挖掘中,形成了以AprioriAll和GSP为代表的经典序列挖掘算法。Pei Jian等人提出模式扩展(patter - growth) 的概念,并开发了FreeSpan和PrefixSpan等算法。下面直接引入以上四种算法进行描述和分析。

1.1AprioriAll算法描述和分析

AprioriAll 算法描述如下:

输入:大项集阶段转换后的序列数据库;

输出:所有最长序列。

1)L1={large1-seqence};//大项集阶段得到的结果。

2)For(k=2;Lk-1≠￠;k++)do begin。

3)Ck=Candidate-generate(Lk-1)//Ck是从Lk-1中产生的新的候选者。

4)For each customer-sequence c in the database do//对数据库中的每一个顾客序列c。

5)Increment the count of all candidates in Ck that are contained in c ;//对包含于c中Ck内的所有候选者计数。

第２８卷第２期　２００６年６月　湖北大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｈｕｂｅｉ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　Ｖ０１．２８　Ｎｏ．２　Ｊｕｎ．．２００６　

文章编号：１０００—２３７５（２００６）０２—０１３８—０６　

序列模式挖掘算法的分析与比较　

马传香，张凌　

（湖北大学数学与计算机科学学院，湖北武汉４３００６２）　

摘要：序列模式挖掘是数据挖掘中一个非常活跃的研究主题．迄今为止，围绕算法效率这个主题，人们　作了大量的工作．一方面，从算法的设计策略人手；另一方面在实现算法所采用的数据结构上做文章；也有的　甚至通过对所挖掘的模式进行限制以达到提高算法效率的目的．并对目前已有的各种典型算法作了详细的　分析与比较，而且做出了适当的评价．　关键词：序列模式；串行算法；并行算法　中图分类号：ＴＰ３０１．６　文献标志码：Ａ　

１　介绍　

序列挖掘是数据挖掘中的一个研究重点，其目的在于从序列数据库中挖掘出具有时序关系的模式．　这类模式有着广泛的应用，如顾客的购物习惯、ｗｅｂ页面的访问顺序、ＤＮＡ序列的分析等等［　．深入理　

解高效的序列模式挖掘方法对在大型数据库中高效挖掘频繁子树、格、子图以及其他结构模式等有着重　

要意义．迄今为止，围绕算法效率这个主题，人们作了大量的工作．一方面，从算法的设计策略人手；另一　

方面从实现算法所采用的数据结构上做文章；也有的甚至通过对所挖掘的模式进行限制以达到提高算　法效率的目的［・，　．　

按照所挖掘的模式，序列挖掘可分为频繁序列挖掘、频繁闭序列挖掘　’４Ｊ和最大序列挖掘；按照挖　

掘的策略可分为串行挖掘和并行挖掘．而我们重点对频繁序列挖掘算法（包括串行算法和并行算法）进　

行比较和分析，并对它们进行评价．　

２预备知识　

令，＝｛ｉ１，ｉ２，…，ｉ　｝，其中，０（　＝１，２，…，ｎ）是不同的项，项的集合称为项集．　定义１一个序列Ｓ即是项集的有序列表，记为Ｓ＝（　ｓ２，…，ｓ　），其中Ｓ　（ｉ＝１，２，…，ｍ）是一　

第

10卷第

1期

2007年

2月扬州大学学报(自然科学版)

JournalofYangzhouUniversity(

NaturalScienceEdition)Vol.10No.1

Feb.2007

序列模式挖掘算法综述

张长海

,胡孔法3

,陈　凌

(扬州大学信息工程学院

,江苏扬州

225009)

摘　要

:目前的主要序列模式挖掘算法可以分为

3类

:①基于

Apriori

的候选码生成

-测试的方法

;②基于

垂直格式的候选码生成

-测试的方法

;③基于模式增长的方法

.在介绍序列模式挖掘基本概念的基础上

,描

述了典型的挖掘算法

,着重分析第②类序列模式挖掘算法的关键技术

,并对各种算法进行详细的分析与比较

,

总结出它们的优缺点

:前两类方法因产生巨大的候选序列而致挖掘代价剧增

,而第③类模式增长方法避免了

候选序列的产生

,但挖掘长模式效率低

.

关键词

:序列模式挖掘

;候选码生成

-测试

;数据分布

;模式增长

中图分类号

:

TP3011

6 文献标识码

:

A 文章编号

:1007-824

X(

2007)

01-0041-06

序列模式挖掘是数据挖掘研究的一个重要课题

,而且应用广泛

,包括顾客购买行为的分析、网络访

问模式分析、科学实验的分析、疾病治疗的早期诊断、自然灾害的预测、

DNA序列模式的分析等

.序列

模式挖掘是对关联规则挖掘的进一步推广

,它挖掘出序列数据库中项集间的时序关联规则是数据挖掘

研究的一个重要内容

.早先的很多关联规则挖掘研究[124]

都有助于挖掘序列模式或者与时间相关的频

繁模式

.

SRIKANT和

AGRAWAL[5]

对序列规定了时间限制、滑动时间窗口和用户规定的分类

,并总结

了序列模式的定义

,提出一种基于

Apriori的改进算法

GSP(

generalizedsequentialpatterns)算法

.以上

这些都是基于

Apriori的水平格式的序列模式挖掘或者与时间相关的频繁模式挖掘

.后来

,ZAKI[6]

提

出了一种基于垂直格式存储的序列模式挖掘方法

SPADE算法

,该算法由基于垂直格式的频繁项挖掘

第ｌ６卷第４期　２００６年４月　计算机技术与发展　ＣＯＭＰＵＴＥＲ　ＴＦ（１Ｉｌ｛ＮＯ１０［Ｘ；Ｙ　ＡＮＴ）ＤＥ、，ＥＬ（－）Ｐ～　ＮＴ　Ｖｏ１．１６　ＮＯ．４　Ａｐｒ．２００６　

序列模式挖掘算法研究　

夏明波　，王晓川　，孙永强２，金士尧　

（１．国防科学技术大学计算机学院并行与分布式国家重点实验室，湖南长沙４１００７３；　

２．国防科学技术大学计算机学院，湖南长沙４１００７３）　

摘要：数据挖掘领域一个活跃的研究分支就是序列模式的发现，即在序列数据库中找出所有的频繁子序列。目前的序列　模式挖掘方法主要分为两类，一类是候选集生成测试方法：另一类是模式扩展方法。先介绍序列模式挖掘中的基本概　

念，然后描述几个重要算法，最后给出性能分析。　关键词：序列模式挖掘；候选集生成一测试；模式扩展；算法分析　

中图分类号：ＴＰ３Ｏ１．６　文献标识码：Ａ　文章编号：１００５—３７５１（２００６）０４—０００４一Ｏ３　

Ｒｅｓｅａｒｃｈ　ｏｎ　Ｓｅｑｕｅｎｔｉａｌ　Ｐａｔｔｅｒｎ　Ｍｉｎｉｎｇ　Ａｌｇｏｒｉｔｈｍｓ　

ＸＩＡ　Ｍｉｎｇ　ｂｏ　，ＷＡＮＧ　Ｘｉａｏ－ｃｈｕａｎ　，ＳＵＮ　Ｙｏｎｇ—ｑｉａｎｇ２，Ｊ　ＩＮ　Ｓｈｉ—ｙａｏ　

（１．Ｎａｔｉｏｎａｌ　Ｋｅｙ　Ｌａｂ．ｆｏｒ　Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｐｒｏｃｅｓｓｉｎｇ，Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ，　

Ｎａｔｉｏｎａｌ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｄｅｆｅｎｓｅ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ　４１００７３，Ｃｈｉｎａ；　

２．Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ，Ｎａｔｉｏｎａｌ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｄｅｆｅｎｓｅ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ　４１００７３，Ｃｈｉｎａ）　

Ａｔ　ｒａｃｔ：Ａｎ　ａｃｔｉｖｅ　ｒｅｓｅａｒｃｈ　ｉｎ　ｄａｔａ　ｍｉｎｉｎｇ　ａｒｅａ　ｉｓ　ｔｈｅ　ｄｉ￣ｏｖｅｒｙ　ｏｆ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎｓ．ｗｈｉｃｈ　ｆｉｎｄｓ　ａｌｌ　ｆｒｅｑｕｅｎｔ　ｓｕｂ—ｓｅｑｕｅｎｃｅｓ　ｉｎ　ａ　ｓｅ—　ｑｕｅｎｅｅ　ｄａｔａｂａｓｅ．Ｒｅｃｅｎｔ　ｓｔｕｄｉｅｓ　ｃａＩ１　ｂｅ　ｄｉｖｉｄｅｄ　ｉｎｔｏ　ｔｗｏ　ｍａｊｏｒ　ｃｌａｓｓｅｓ　ｏｆ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｍ　ｍｉｎｉｎｇ　ｍｅｔｈｏｄｓ：ａ　ｃａｎｄｉｄａｔｅ　ｇｅｎｅｒａｔｉｏｎ—ａｎｄ—　ｔｅｓｔ　ａｐｐｒｏａｃｈ；ａ　ｐａｔｔｅｒｎ—ｇｒｏｗｔｈ　ｍｅｔｈｏｄ．Ｔｈｉｓ　ｐａｐｅｒ　ｆｉｒｓｔｌｙ　ｉｎｔｒｏｄｕｃｅｓ　ｔｈｅ　ｂａｓｉｃ　ｃｏｎｃｅｐｔ　ｏｆ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ，ｔｈｅｎ　ｄｅｓｃｒｉｂｅｓ　ｔｈｅ　ｍａｉｎ　ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　ｆｉｎａｌｌｙ　ａｎａｌｙ￣ｓ　ｔｈｅｉｒ　ｐｅｒｆｏｒｍａｎｃｅ，　Ｋｅｙ　ｗｏｒｄｓ：ｓｅｑｕｅｎｔｉａｌ￣ｔｔｅｍｍｉｎｉｎｇ；ｃａｎｄｉｄａｔｅ　ｇｅｎｅｒａｔｉｏｎ——ａｎｄ——ｔｅｓｔ；ｐａｔｔｅｒｎ——ｇｒｏｗｔｈ；ａｌｇｏｒｉｔｈｍ　ａｎａｌｙｓｉｓ　

序列模式挖掘及其算法的研究

姜晚云胡学钢(合肥工业大学计算机信息学院230000摘要:数据挖掘在最近几年里已被数据库界所广泛研究，而序列模式挖掘是数据挖掘中最重要的研究课题之一，本文介绍了序列模式挖掘的概念，并重点分析了序列模式挖掘的一种经典算法。一、序列模式的提出顾客交易序列中的知识发现问题是近年来数据挖掘的一个活跃的研究领域。近几年来，随着数据库中数据挖掘研究和应用的不断深人，序列中的知识发现问题正引起越来越多的人工智能和数据库界研究者的兴趣。序列模式的概念最早是由Agrawal和Srikant提出的，给定一个序列集，其中每一个序列由项集构成，然后给定由用户确定的最小支持度阑值，序列模式挖掘就是去发现所有的频繁子序列(即:这些子序列的出现频率不小于给定的最小支持度)。举例来说，顾客租借录像带的一个典型的顺序是先租“星球大战”，然后是“帝国反击战”，再是“杰达武士归来”(这三部影片是以故事发生的时间先后而情节连续的)。值得注意的是租借这三部电影的行为并不一定需要是连续的。在任意两部之间插租了任何电影，仍然满足这个序列模式，并且扩展一下，序列模式的元素也可以不只是一个物品(如一部电影)，它也可以是一个物品的集合。1.序列模式相关概念及定义给出有关序列模式的基本概念如下:在交易数据库DB中，每个商品称为一个数据项(item，以下简称项)，非空集合1=(iI,i2，二，im}称为数据项集(itemset，以下简称项集)，其中每个ik(l--k--m)是一个项。长度为k的项集称为k项集。DB中每个交易(transaction)由顾客号、交易时间和该交易所购买的项集构成。不考虑顾客购买项的数量并假定同一时间一位顾客只进行一次交易。定义1序列(sequence)是项集的有序表，记作和B=,如果存在一组整数i,，这里T;(1i--n)是某顾客的第i次交易时间，itemset(T;)为该次交易中顾客购买的项集。由全部顾客序列组成的数据库称为顾客序列数据库，记作SDB。通常，得到SDB需要对原交易数据库DB重构。定义3顾客支持序列s指序列s包含于该顾客序列中。序列s的支持度指顾客序列数据库SDB中支持8的顾客数

第２５卷第７期　２００８年７月　计算机应用研究　Ａｐｐｌｉｃａｔｉｏｎ　Ｒｅｓｅａｒｃｈ　ｏｆ　Ｃｏｍｐｕｔｅｒｓ　Ｖ０１．２５　Ｎｏ．７　Ｊｕ１．２０ＨＤ８　

序列模式挖掘综述　

陈卓，杨炳儒，宋威，宋泽锋　

（北京科技大学信息工程学院，北京１０００８３）　

摘要：综述了序列模式挖掘的研究状况。首先介绍了序列模式挖掘背景与相关概念；其次总结了序列模式挖　掘的一般方法，介绍并分析了最具代表性的序列模式挖掘算法；最后展望序列模式挖掘的研究方向。便于研究　

者对已有算法进行改进，提出具有更好性能的新的序列模式挖掘算法。　

关键词：数据挖掘；序列模式；周期模式；增量式挖掘　

中图分类号：ＴＰ３１ｌ　文献标志码：Ａ　文章编号：１００１—３６９５（２００８）０７—１９６０—０４　

Ｓｕｒｖｅｙ　ｏｆ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ　

ＣＨＥＮ　Ｚｈｕｏ，ＹＡＮＧ　Ｂｉｎｇ—ｒｌｌ，ＳＯＮＧ　Ｗｅｉ，ＳＯＮＧ　Ｚｅ—ｆｅｎｇ　（Ｓｃｈｏｏｌ　ｏｆＩｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｂｅｉｆｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　０厂Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ　１０００８３，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｉｓ　ｐａｐｅｒ　ｐｒｏｖｉｄｅｄ　ａ　ｒｅｖｉｅｗ　ｏｆ　ｔｈｅ　ｒｅｓｅａｒｃｈ　ｏｆ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ．Ｆｉｒｓｔｌｙ，ｉｎｔｒｏｄｕｃｅｄ　ｔｈｅ　ｂａｃｋｇｒｏｕｎｄ　ａｎｄ　ｃｏｎｔｅｘｔ．Ｓｅｃｏｎｄｌｙ，ｓｕｍｍａｒｉｚｅｄ　ｔｈｅ　ｇｅｎｅｒａｌ　ｍｅｔｈｏｄｓ　ｏｆ　ｓｅｑｕｅｎｃｅ　ｐａｔｔｅｒｎ　ｍｉｎｉｎｇ，ｉｎｔｒｏｄｕｃｅｄ　ａｎｄ　ａｎａｌｙｚｅｄ　ｔｈｅ　ｍｏｓｔ　ｒｅｐｒｅｓｅｎｔａｔｉｖｅ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｐｒｏｖｉｄｅ　ａ　ｂａｓｉｓ　ｆｏｒ　ｉｍｐｒｏｖｉｎｇ　ｏｌｄ　ａｌｇｏｒｉｔｈｍｓ　ｏｒ　ｄｅｖｅｌｏｐｉｎｇ　ｎｅｗ　ｅｆｆｅｃｔｉｖｅ　ｏｎｅｓ．Ｆｉｎａｌｌｙ，ｄｉｓｃｕｓｓｅｄ　ｓｏｍｅ　ｆｕｔｕｒｅ　ｒｅ—　ｓｅａｒｃｈ　ｔｒｅｎｄｓ　ｏｎ　ｔｈｉｓ　ａｒｅａ．　Ｋｅｙ　ｗｏｒｄｓ：ｄａｔａ　ｍｉｎｉｎｇ；ｓｅｑｕｅｎｔｉａｌ　ｐａｔｔｅｒｎ；ｐｅｒｉｏｄｉｃ　ｐａｔｔｅｒｎ；ｉｎｃｒｅｍｅｎｔａｌ　ｍｉｎｉｎｇ　

第ｌＯ卷第１期　２００７年２月　扬州大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｙａｎｇｚｈｏｕ　Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｖｏ１．１０　Ｎｏ．１　Ｆｅｂ．２００７　

序列模式挖掘算法综述　

张长海，胡孔法　，陈　咬　

（扬州大学信息工程学院，江苏扬州２２５００９）　

摘　要：目前的主要序列模式挖掘算法可以分为３类：①基于Ａｐｒｉｏｒｉ的候选码生成一测试的方法；②基　于垂直格式的候选码生成一测试的方法；③基于模式增长的方法．在介绍序列模式挖掘基本概念的基础　上，描述了典型的挖掘算法．着重分析第②类序列模式挖掘算法的关键技术，并对各种算法进行详细的分　析与比较，总结出它们的优缺点：前两类方法因产生巨大的候选序列而致挖掘代价剧增，而第③类模式增　长方法避免了候选序列的产生，但挖掘长模式效率低．　

关键词：序列模式挖掘；候选码生成一测试；数据分布；模式增长　

中图分类号：ＴＰ　３０１．６　文献标识码：Ａ　文章编号：１００７—８２４Ｘ（２００７）０１—００４１—０６　

序列模式挖掘是数据挖掘研究的一个重要课题，而且应用广泛，包括顾客购买行为的分析、网络　访问模式分析、科学实验的分析、疾病治疗的早期诊断、自然灾害的预测、ＤＮＡ序列模式的分析等．　

序列模式挖掘是对关联规则挖掘的进一步推广，它挖掘出序列数据库中项集间的时序关联规则是数　

据挖掘研究的一个重要内容．早先的很多关联规则挖掘研究［１－４］都有助于挖掘序列模式或者与时间　相关的频繁模式．ＳＲＩＫＡＮＴ和ＡＧＲＡＷＡＬＩｓ］对序列规定了时间限制、滑动时间窗口和用户规定的　

分类，并总结了序列模式的定义，提出一种基于Ａｐｒｉｏｒｉ的改进算法ＧＳＰ（ｇｅｎｅｒａｌｉｚｅｄ　ｓｅｑｕｅｎｔｉａｌ　ｐａｔ—　

ｔｅｒｎｓ）算法．以上这些都是基于Ａｐｒｉｏｒｉ的水平格式的序列模式挖掘或者与时间相关的频繁模式挖　

掘．后来，ＺＡＫＩＩｓ］提出了一种基于垂直格式存储的序列模式挖掘方法ＳＰＡＤＥ算法，该算法由基于　垂直格式的频繁项挖掘演化而来．近几年，ＨＡＮ等人［７　又提出一种基于投影的模式增长算法——　

１１６　应用科学　科２０１　０　年第２嗍露重Ｉ　

序列模式挖掘算法的比较与研究　

孙浩　

（９１５５０部队９１分队　董雷　

辽宁大连１１６０２３）　

摘要序列模式挖掘是数据挖掘中的一个重要研究方向，即在序列数据库中找出所有的频繁子序列。对序列模式挖掘中的典型算法的执　

行过程及其特点进行研究，并对其时空执行效率进行分析比较．并且做出适当的评价。　

关键词序列模式挖掘；算法分析；定性比较　

中图分类号１１）　文献标识码Ａ　文章编号１６７３—９６７１一（２０１０）１０２—０１　１６一叭　

序列挖掘是数据挖掘中的～个研究重点，足从序列数据库中发现相　

对时间或者其他顺序所出现的频率子序列作为模式。其应用范围包括顾　

客购物行为的分析、网络访问模式分析、科学实验的分析、自然灾害的　

预测、ＤＮＡ序列的破译等。本文以ＡｐｆｉｏｆｉＭ１，ＧＳＰ，ＦｍｅＳｐａｎ和ＰｒｅｆｉｘＳｐａｎ　

四个典型算法为例，对两类算法进行介绍、分析和总结。　

１序列模式挖掘中的典型算法　

Ａｐ６ｏｎ算法是关联规则挖掘的经典算法。它的思想扩展到序列挖掘　

中，形成了以ＡｐｒｉｏｒｉＡｌｌ和ＧＳＰ为代表的经典序列挖掘算法。Ｐｅｉ　Ｊｉａｎ等人　

提出模式扩展（ｐａｔｔｅｒ—ｇｒｏｗｔｈ）的概念，并开发了ＦｍｅＳｐａｎ和ＰｒｅｆｉｘＳｐａｎ　

等算法。下面直接引入以上四种算法进行描述和分析。　

１．１　Ａｐｒｉｏｒ　Ａ¨算法描述和分析　

ＡｐｆｉｏｆｉＭｌ算法描述如下：　

输入：大项集阶段转换后的序列数锯库；　

输出：所有最长序列。　

１）Ｌ．＝｛ｌａｒｇｅｌ—ｓｅｑｅｎｃｅ｝；／／大项集阶段得到的结果。　

２）Ｆ０ｒ（　２；三ｋ１≠　；　＋）ｄｏｂｅｇｉｎ。　

３）Ｃ￣＝Ｃａｎｄｉｄａｔｅ－ｇｅｎｅｍｔｅ（Ｌｋ．），／ｃ　中产生的新的候选者。　４）　＿Ｆｏｒ　ｅａｃｈ　ｅｕｓｔｏｍｅｒ－，￣ｑｕｅｎｅｅ　Ｃｉｎｔｈｅ　ｄａｔａｂａｓｅｄｏ，，对数据库中的每一　

个顾客序列Ｃ。　

５）Ｉｎｃｒｅｍｅｎｔｔｈｅｃｏｕｎｔｏｆａｌｌ　ｃａｎｄｉｄａｔｅｓｉｎＣｋｔｈａｔａｍｃｏｎｔａｉｎｅｄｉｎ　ｃ；　包　

科学论坛　序列模式数据挖掘算法研究　刘智萍　（ｇｌｉ西科技学院，江西南昌３３００９８）　摘要：序列模式的发现是数据挖掘领域一个活跃的研究分支，即在序列数据库中找出所有的频繁子序列。本文先介绍序列模式挖掘中的一些基本　概念，然后详细描述ＦｒｅｅＳｐａｎ和ＰｒｅｆｉｘＳｐａｎ２个基于投影、分治的模式增长的重要算法　关键词：序列模式；算法　、基本术语和定义　设Ｉ：｛ｉ１，ｉ２，……，ｉｎ１是一个项目集合，项目集或者项集（ｉｔｅｍｓ）就是　各种项目组成的集合，即Ｉ的所有子集。一个序列就是若干项集的有序列　表，一个序列ｓ可表示为（Ｓ１，ｓ２，……，ｓ　，其中ｓｉ为项集，也称作Ｓ的元　素。元素由不同的项组成，可表示为（ｘ１，ｘ２，……，ｘｎ）。当元素只包含一项　时，一般省去括号，如（ｘ２）一般表示为ｘ２。元素之间是有顺序的，但元素内　的项是无序的，一般定义为词典序。序列包含项的个数称为序列的长度，　长度为Ｌ的序列记为Ｌ一序列．序列数据库就是元组（ｔｕｐｌｅｓ）（ｓｉｄ，Ｓ）的集　合，其中Ｓ是序列，ｓｉｄ是该序列的序列号，元组的个数称为序列数据库的　大小，记作ｌＳＤＢＩ。　１、ＦｒｅｅＳｐａｎ算法思想　ＦｒｅｅＳｐａｎ，即频繁模式投影的序列模式挖掘，其基本思想为：利用频繁　项递归地将序列数据库投影到更小的投影数据库集中，在每个投影数据库　中生成子序列片段．这一过程对数据和待检验的频繁模式集进行了分割，并　且将每一次检验限制在与其相符合的更小的投影数据库中．　２、ＦｒｅｅＳｐａｎ算法分析：　它、　频繁序列和频繁模式的挖掘统一起来，把挖掘工作限制在投影数　据库中，还能限制序列分片的增长．它能有效地发现完整的序列模式，同时　大大减少产生候选序列所需的开销，比基于Ａｐｒｉｏｒｉ的ＧＳＰ算法快很多．不　足之处，它可能会产生许多投影数据库，如果一个模式在数据库中的每个序　列中出现，该模式的投影数据库将不会缩减；另外，一个长度为ｋ的序列可　能在任何位置增长，那么长度为ｋ＋１的候选序列必须对每个可能的组合　情况进行考察，这样所需的开销是比较大的．对ＦｒｅｅＳｐａｎ中频繁项矩阵Ｆ　占用存储空间的定量分析如下：设序列数据库中有ｍ个频繁项，频繁项矩　阵共需要ＩＭ　Ｊ＝ｍ＋３２ｘ（ｍ一１）×ｍ－２）个计数单元。例如，ｍ＝１０００，『Ｍ　Ｊ：　１．５ｘ１０６＝３Ｍｂ（￣设每个计数单元占用２ｂ的空间），目前一般的计算机就很　容易满足这个要求Ｈ。　３、ＰｒｅｆｉｘＳｐａｎ算法的提出　许多应用中，如ＤＮＡ分析和股市序列分析等，数据库常包含大量的　序列模式，而且许多模式很长，此时有必要重新审视序列模式挖掘问题，以　探索一些更加有效、易于扩展的方法．通过观察发现，基于Ａｐｒｉｏｒｉ算法的瓶　颤存于每一步的候选集生成和测试，能否找到一种方法，既能吸取Ａｐｒｉｏｒｉ　的灵魂义能避免或者充分减少昂贵的候选集生成和测试．顺着这个思路，　ＰｅｉＪｉａｎ，Ｈａｎ　１ｉａｗｅｉ及Ｗａｎｇ　１ｉａｎｙｏｎｇ等人基于分治和模式扩展的原理提出　了模式扩展方法，代表性的算法有ＦｒｅｅＳｐａｎ和ＰｒｅｆｉｘＳｐａｎ，其中ＰｒｅｆｉｘＳｐａｎ　改进法采用了伪投影技术，性能比ＦｒｅｅＳｐａｎ好．Ｆ面描述并分析ＰｒｅｆｉｘＳｐａｎ　算法．　４、ＰｒｅｆｉｘＳｐａｎ算法思想及描述　该算法就是通过前缀投影来挖掘序列模式，进行投影时，并不考虑所　有出现的频繁子序列．而是找出前缀序列，把相应的后缀投影成为一系列　的投影数据库．对于每一个投影数据库，只须找出局部频繁模式，且不产　生候选码，它的丰要步骤如下：　①　拙数据库一次，找出频繁Ｌ２序列，假设为ｋ个；　②划分研究空间：把完整的序列模式划分为ｋ个研究空间，分别以频　繁Ｌ２序列为前缀：　③构造相应的数据库，也就是对应前缀的后缀集合；　④在这些后缀集合中递归地发现频繁模式的子集．　算法形式化描述如下：　输入：序列数据库Ｓ和最小支持度ｍｉｎ　ｓｕｐ．　输出：所有的序列模式．　方法：调用子程序ＰｒｅｆｉｘＳｐａｎ（＜＞，０，Ｓ）　其中子程序ＰｒｅｆｉｘＳｐａｎ（ｏＬ，Ｌ，Ｓｌｄ）描述如下：　（１）扫描ｓ『ｄ，找到满足下述要求的长度为１的序列模式ｂ：　１）ｂ可以添加到ｏＬ的最后一个元素中并为序列模式；　２）＜ｂ＞可以作为ｄ的最后一个元素并为序列模式．　（２）对每个生成的序列模式ｂ，将ｂ添加到ｄ形成序列模式０Ｌ　，并输出　０【　：　（３）对每个ｏＬ　，构造ｏＬ　的投影数据库ＳｌＱ　，并调用子程序ＰｒｅｆｉｘＳｐａｎ　（ｄ　，Ｌ＋１，Ｓ１　０【　）．子程序参数说明：　为一个序列模式；Ｌ为序列模式ｏ【的长　度；ＳＩｄ为ｏＬ的投影数据库（当ｏＬ为空时，ｓ１　０Ｌ就是ｓ）．　５、ＰｒｅｆｉｘＳｐａｎ算法的主要改进：　（１）逐层投影：使用隔层投影代替逐层投影，从而可以有效减小投影数　据库的个数．　（２）伪投影：当序列数据库可以直接放入内存时，可以使用伪投影操作　代替实际的投影数据库，从而可以有效减少构造投影数据库的开销．其主　要思想就是用指针指向对应序列，用偏移量表示后缀起始位置，这样就可　用指针和偏移量代替真实投影，从而在投影数据库中不重复出现后缀，节　省不少的空问．例如：序列数据库只有序列（ａ（ａｂｃ）（ａｃ）ｄ（ｃｔ）），关于（ａｂ）的　投影数据库为（（一ｃ）（ａｃ）ｄ（ｃＯ），这时可以用（ｅ，４）代替Ｓ　Ｉ（ａｂ），指针指向　对应的序列，而４表示后缀从第４位置开始，即从字符ｃ开始．可见利用　虚拟投影节省了空间，进一步提高了该类算法的性能　．　６、ＰｒｅｆｉｘＳｐａｎ算法与Ａｐｆｉｏｆｉ算法的比较　经过测试比较，ＰｒｅｆｉｘＳｐａｎ算法性能比基于Ａｐｆｉｏｆｉ的算法（ＧＳＰ和　ＳＰＡＤＥ１明显要好，原因在于：　１）模式扩展方式不生成候选序列。ＰｒｅｆｉｘＳｐａｎ是一一个基于模式扩展的　方法，就象Ｆｐ—ｇｒｏｗｔｈ一样。用传统的候选集生成一测试方法来处理一个　比较小的数据库（例如只有ｌＯｋ的序列），需要相当多的时间来生成和测试　大量的候选序列模式。　２）基于投影的分治是数据缩减（ｒｅｄｕｃｔｉｏｎ）的有效方法。序列模式　的投影数据库包含且仅包含用来挖掘那些由ｎ扩展得到的模式的必需信　息，投影数据库的大小随着挖掘过程向更长的序列模式进行而迅速缩减。　３）ＰｒｅｆｉｘＳｐａｎ需要的内存空间相对稳定。原因在于它采用分治的方法，　不生成候选集。而ＧＳＰ和ＳＰＡＤＥ，当支持度阈值（ｓｕｐｐｏ￣ｔｈｒｅｓｈｏｌｄ）降低　时．由于需要容纳大量候选序列，需要相当数量的内存。基于模式扩展的方　法，可以应用到多层次、多维数的序列模式中，也可以挖掘其他结构化的模　式。一　作者简介：刘智萍（１９７８一），女，江西南昌人，江西科技学院，硕　ｔ，研究　方向：软件工程　【３】杨德礼，郭琼，何勇，，徐经意供应链契约研究进展管理学报２００６　年１月　［４１千振兴，潘李剑，欧涉远供应链契约研究进展综述商业经济２０１２　４２　年第８期　【５】朱晓东报童模型下的供应链契约研究企业管理２０１１年第１