下载文档原格式
数据挖掘中的序列模式作者：孙冬梅来源：《大东方》2015年第09期数据挖掘的任务是从数据中发现模式，模式时空一个用语言L来表示的一个表达式E，它可用来描述数据集F中数据的特性，E所描述的数据时机和F的一个子集FE。
E作为一个模式要求它比数据子集FE中所有元素的描述方法简单，在实际应用中，往往根据模式的实际作用细分为分类模式、回归模式、时间序列模式、聚类模式、关联模式和序列模式6种。
给定一个由客户交易之城的数据库DB，挖掘序列模式的问题就是在那些具有客户指定最小支持度（minimum support）的序列中找出最大序列（maximal sequence），而每个这样的最大序列就代表了一个序列模式（sequence pattern）一、序列模式挖掘参数1.时间序列T的时间长度可以讲数据库中的整个序列或用户所选择的序列（如2003你那）作为时间序列的长度，序列模式（挖掘）将仅限于在之一序列长度之内进行。
2.时间窗口W一系列在时间内发生的事件在特定的分析中可以看成是一起发生的。
如果一个时间窗口W呗设置为同序列T一样长，那就会发现对时间不敏感的频繁模式，也就是基本关联模式。
如：“2000年，一个购买电脑的顾客也买了数码相机”其中不再关系哪个先买哪个后买）；若一个事件窗口W被设置为0，那就会发现一个序列事件是作为单个时间发生（来处理的）如：“一个顾客购买了电脑，然后又购买了内存，最后悔购买CD-ROM”。
若一个事件窗口W被设置为上述两者之间的某个值（即0与T总长度之间），如：若W设为一个月，那么在同一月发生的交易事务，将被认为是同一时间发生的，而被合在一起进行分析。
3.发现模式中事件发生的时间间隔int。
若将int设为0，就意味着没有间隔，也就是发现严格连续时间序列。
这里也可以将参数W考虑进来。
若W设为一周，也就是要发现连续各周频繁模式。
DNA分析经常需要发现无间隔的连续序列。
而min_interval int大多挖掘频繁序列模式的研究都是针对不同的参数设置，以及采用Aprior启发知识和与Apriori类似。
Prefixspan算法设计与实现摘要：序列模式挖掘算法有AprioriAll、GSP、FreeSpan、Prefixspan，本文将对PrefixSpan算法进行研究，来对序列模式挖掘有更深入的剖析。
关键字：序列模式挖掘，Prefixspan算法一. Prefixspan算法思想：采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。
PrefixSpan算法就是基于序列投影的一种模式增长算法。
PrefixSpan算法是一种深度优先搜索算法，其基本思想是使用频繁前缀划分搜索空间和投影序列数据库，并搜索相关的序列。
首先检查前缀子序列，只将其相应的后缀子序列投影到数据库中。
该算法同时采用分治(divide and conquer)的策略，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。
二.算法描述：(1)扫描序列数据库，生成所有长度为1的序列模式。
(2)根据长度为1的序列模式，构造不同前缀所对应的投影数据库。
(3)在相应的投影数据库上重复上述步骤，直到在相应的投影数据库上不能产生长度为1的序列模式为止。
三、Prefixspan算法的具体实现完整算法实现程序见附录。
用程序实现理论过程：以下是程序各模块的实现：a.数据的读取和存储:本程序数据信息存放在ccc.txt中。
读入到两个数据结构中：transaction 相当于一个二维数组保存了所有数据，按照字符形式读入；record里保存的是序列中每一个元素包含项的个数，例如<a(abc)(ac)d(cf)>，在record 中保存形式为：1 3 2 1 2。
b.提取长度为1 的序列模式:对每一行进行扫描，用counter向量保存每一个项和其出现的位置。
数据的格式为’a’,[4] (1,0) (2,0) (3,1) (4,1) ，表明a的支持度为4，在向量中出现的位置为第1行的第0个，和第2行的第0个数据等。
