所谓序列模式,我的定义是:在一组有序的数据列组成的数据集中,经常出现的那些序列组合构成的模式。跟我们所熟知的关联规则挖掘不一样,序列模式挖掘的对象以及结果都是有序的,即数据集中的每个序列的条目在时间或空间上是有序排列的,输出的结果也是有序的。
举个简单的例子来说明,关联规则一个经典的应用是计算超市购物中被共同购买的商品,它把每个顾客的一次交易视作一个transaction,计算在不同transaction中不同item组合的规律性。而如果我们考虑一个用户多次在超市购物的情况,那么这些不同时间点的交易记录就构成了一个购买序列,N个用户的购买序列就组成一个规模为N的序列数据集。考虑这些时间上的因素之后,我们就能得到一些比关联规则更有价值的规律,比如关联挖掘经常能挖掘出如啤酒和尿布的搭配规律,而序列模式挖掘则能挖掘出诸如《育儿指南》->婴儿车这样带有一定因果性质的规律。所以,序列模式挖掘比关联挖掘能得到更深刻的知识。
在实际当中,序列模式挖掘被广泛地应用于各种序列数据集中,如生物信息学上的基因微阵列数据,从中挖掘哪些基因组合模式在某类病人中会频繁出现;以单词作为item的文档序列,研究在不同文档中单词序列的出现模式;用户点击流数据,用于挖掘用户的频繁点击模式,建立用户模型,完善网站功能与UI结构。除此之外还有很多,只要是序列数据集,都可以考虑利用序列模式挖掘获得规律。
图1是一个序列数据库,及其以0.75作为最小阈值(min_sup)的频繁序列模式。借此介绍序列挖掘中的几个主要概念。
- 序列(Sequence):以SID表示,一个序列即是一个完整的信息流。
- 项目(Item):序列中最小组成单位的集合,比如在这个样例中的项目为{A, B, C}。
- 事件(Event):通常用时间戳标志,标识事件之间的前后关系。又叫Itemset,是Item的集合,样例中以EID表示。
- k频繁序列:如果频繁序列的项目个数为k,则称之为k频繁序列,以Fk表示(图1的F1,F2,F3)。
- 序列的包含关系:对于序列x和y,如果存在着一个保序的映射,使得x中的每个事件都被包含于y中的某个事件,则称为x被包含于y(x是y的子序列),例如序列B->AC是序列AB->E->ACD的子序列。
- 支持度(support):某序列x的支持度是指在整个序列集中包含x的序列的频次。
有了以上概念之后,序列模式挖掘的问题就定义为:给定一个序列数据库以及最小支持度min_sup,找出所有支持度大于min_sup的序列模式。
解决这个问题的一个著名的算法叫SPADE,以及加入各种约束限制后的cSPADE,它们来自同一个作者Zaki。SPADE是无约束的序列频繁模式挖掘算法,其基本思想是利用一个S后缀等价类(suffix equivalence class)的概念[S],从F1开始计算,由F1张出以F1中的频繁序列为[S]的F2,再以F2张出以F2中的频繁序列为[S]的F3,以此类推。由于引入了后缀等价类这个概念,使得整个算法对数据库的遍历次数与计算量大大降低,是一个现实中有效的算法。cSPACE在前者的基础上引入了对序列模式的约束,其中包括:
- 序列长度与宽度的约束(序列的长度是指序列中事件的个数,宽度是指最长事件的长度);
- 最小间隔的约束,即事件之间的最小时间间隔;
- 最大间隔的约束,即事件之间的最大时间间隔;
- 时间窗的约束,即整个序列都必须发生在某个时间窗内;
- 其它,如只限制为某些Item,序列数据库存在分类标签。
以上的约束基本已经覆盖了实际应用中所有可能碰到的限制情况,实际上约束并不常用到,通常SPADE算法已经够用了。
由于数学表述过多,而且整个过程比较繁琐,这里不打算详细叙述两个算法的计算流程,有兴趣的可以参看文后附上的参考文献。
很幸运的是,万能的R已经有序列挖掘的包,对SPADE算法与cSPADE算法有了完整的实现,即使对算法并不充分了解,也可以把它们用于自己的场景中。它就是arulesSequences,以下以一个例子简单介绍一下它的用法。
1 2 3 4 5 6 7 |
library(arulesSequences) data(zaki) s1 <- cspade(zaki, parameter = list(support = 0.4), control = list(verbose = TRUE)) summary(s1) as(s1, "data.frame") s2 <- cspade(zaki, parameter = list(support = 0.4, maxwin = 5)) as(s2, "data.frame") |
第2行导入数据库zaki,它的结构类似于图1所示的那种序列-事件集,第3行设定最小支持度为0.4,并用无约束的SPADE算法搜索频繁序列模式,第6行引入了时间窗的限制,用cSPADE算法进行搜索。整个过程十分简洁明了。
更多使用的例子可在R的终端用?cspade命令查看。
参考文献:
Sequence Mining in Categorical Domains: Incorporating Constraints, Mohammed J. Zaki, 2000 ACM
相关推荐
序列模式挖掘的PrefixSpan算法源代码
针对传统GSP算法需要多次扫描数据库、I/O开销巨大的缺点,提出了一种基于MapReduce编程框架的序列模式挖掘算法MR-GSP(GSP algorithm based on MapReduce)。MR-GSP算法将原序列数据库划分为多个子序列数据库并分发...
本算法为数据挖掘中序列模式挖掘中的GSP算法的基本实现,可依托此算法进行算法的优化操作。
综述了序列模式挖掘的研究状况。首先介绍了序列模式挖掘背景与相关概念; 其次总结了序列模式挖 掘的一般方法, 介绍并分析了最具代表性的序列模式挖掘算法; 最后展望序列模式挖掘的研究方向。便于研究 者对已有算法...
序列模式是给定一个由不同序列组成的集合,其中,每个序列由不同的元素按顺序有序排列,每个元素由不同项目组成,同时给定一个用户指定的最小支持度阈值,序列模式挖掘就是找出所有的频繁子序列,即该子序列在序列...
综述了序列模式挖掘的研究状况。首先介绍了序列模式挖掘背景与相关概念;其次总结了序列模式挖掘的一般方法,介绍并分析了最具代表性的序列模式挖掘算法;最后展望序列模式挖掘的研究方向。便于研究者对已有算法进行...
序列模式挖掘 数据生成器 及源代码 资源共享
GSP是序列模式挖掘的一种算法。其主要描述如下: l 根据长度为i 的种子集Li 通过连接操作和剪切操作生成长度为i+1的候选序列模式Ci+1;然后扫描序列数据库,计算每个候选序列模式的支持数,产生长度为i+1的序列模式...
消费者对不同种类的产品具有不同的价格偏好,而传统的序列模式挖掘算法仅考虑序列中不同项目的出现顺序,使得挖掘到的序列模式没有包含产品价格以及种类等重要信息。为了克服传统算法的这一缺陷,在序列模式中体现更...
对于不确定数据的频繁序列模式挖掘,会导致可能频繁模式数量的指数级出现,其中有些无用的挖掘结果会引起频繁序列的冗余。针对上述不足,提出了可能频繁闭序列模式(p-FCSPs)的定义,以及一种基于不确定数据的可能...
针对PrefixSpan算法中反复扫描投影数据库寻找局部频繁项并重复构造挖掘大量重复投影数据库的不足, 提出一种基于序列末项位置信息的序列模式挖掘算法SPM-LIPT。通过连接2-序列位置信息表LIPT找到序列模式的下一项, ...
目前,已提出了一些关联规则挖掘中的隐私保护方法,而对序列模式挖掘中隐私保护的研究却很少。为此,提出了一种有效的敏感序列隐藏算法CLSDA(current least sequences delete algorithm),该算法对候选序列加权,在...
序列模式挖掘算法SPAM的改进 序列模式 sequential pattern mining SPAM 序列模式 sequential pattern mining SPAM
序列模式挖掘及其应用研究的毕业论文
数据挖掘|序列模式挖掘及其算法的python实现
针对完井移动平台Web访问模式中用户对整体上符合完井业务流程习惯的序列模式更加感兴趣的特点,提出一种基于完井业务流程的加权序列模式挖掘算法。通过对完井业务流程模型和完井Web访问日志作分析,确定完井业务依赖...
为了在多核处理器上充分利用多核资源以提升挖掘性能,提出了一种动态与静态任务分配机制相结合的基于多核的并行序列模式挖掘算法。该算法采用数据并行与任务并行相结合的策略,在各处理器核生成局部序列模式后,再与...
DMBIT:一种有效的序列模式挖掘算法,逄玉俊,宁嘉,大量候选序列模式支持度的计算所带来的时间消耗是序列模式挖掘主要问题之一,为此本文提出了一种有效的序列模式挖掘算法:DMBIT(D
序列模式挖掘综述,包含经典挖掘算法思路,伪代码,以及优劣势比较