论文部分内容阅读
序列模式挖掘是数据挖掘领域的一个重要研究方向,在各个领域具有广泛的应用。现有序列模式挖掘方法挖掘出的频繁序列模式往往缺乏可解释性,在支持度较低或者当数据集比较稠密的时候,挖掘出的频繁序列模式数量往往呈指数级增长。这使得用户难以从众多的序列模式中找出底层数据潜藏的知识和规律,另一方面,大量的序列模式也对序列模式挖掘算法的效率,序列模式的存储以及动态维护带来了很大压力。
本文着重研究如何在静态以及动态序列数据环境中挖掘精简序列模式(CompactSequentialPattern)的理论及方法。研究内容包括挖掘压缩序列模式,动态序列数据库中的封闭序列模式维护(包括序列数据库的动态插入和追加、动态删除、动态修改和动态支持度调整等),另外还包括数据流环境下的动态精简序列模式挖掘问题的研究。针对精简序列模式挖掘的各个问题给出了解决方法及相关算法,并通过大量的实验证明了方法的有效性。本文主要贡献如下:
1.提出了一种基于SP-Feature序列表达模型的序列模式压缩方法本文设计了一种新的概率序列表达模型SP-Feature来精简表示一个序列模式的集合,该表达模型是一个三元组,包括代表模式、模式轮廓和支持度。使用该表达模型压缩一个序列模式的集合后,可以近似恢复序列模式的支持度信息。基于该表达模型,本文设计了一种可以有效压缩序列模式的算法CSP(CompressingSequentialPatterns),算法的输出为一棵层次结构树,可以方便使用者在不同粒度查看和分析序列模式。同时本文也设计了多种优化技术来进一步降低算法的内存使用和提高算法的效率。并在真实和模拟数据集上做了广泛的实验,验证了CSP算法在压缩序列模式方面的有效性。
2.提出并设计了基于CSTtree的精简序列模式动态维护方法本文提出了一种精简封闭序列模式动态维护方法,该方法基于一种新颖的封闭序列树结构CSTree(ClosedSequenceTree)。CSTree中的节点具有四种不同的状态,从不同状态节点之间的转换约束中可以得到很多有用的性质,这些性质可以用于动态维护算法提高算法的性能。IMCSA和IMCSD算法被设计用来处理序列数据库的APPEND和DELETE操作,其它操作(例如INSERT等)可以通过APPEND和DELETE实现。算法充分利用了初始数据库中的封闭序列模式信息和CSTree的性质达到了快速增量计算新的封闭序列模式集合的目的。另外本文还给出了动态支持度变化的处理方法。大量的实验结果表明本文提出的算法要比现有算法(包括PrefixSpan、CloSpan、BIDE和IncSpan)快大约4-10倍。
3.提出了一种使用逆序列树概要结构的数据流滑动窗口精简序列模式挖掘方法本文设计了一种数据流滑动窗口概要结构IST(InverseSequenceTree,逆序列树)用来在内存中保存序列模式。IST是一种前缀树,具有三种类型的节点,它保存了当前滑动窗口中的逆序列集合中的封闭序列模式。因为一个序列数据库中的封闭序列模式集合和其逆序列数据库中的封闭序列模式集合具有双射关系,所以可以通过在IST中保存逆封闭序列模式,把滑动窗口的滑动操作从向序列尾部追加和头部删除数据流元素的操作转化成向序列头部添加和从尾部删除数据流元素的操作。这种转化大大减少了费时的节点扩展操作,从而提高了滑动操作的性能。基于逆序列树结构,本文设计了高效的SeqStream算法来挖掘滑动窗口中的封闭序列模式。同时还提出了多种优化剪枝技术和高效计数技术来提高算法的性能。另外,该算法还易于并行化。真实和模拟数据上的大量实验表明SeqStream算法比现有算法要快大约1到2个数量级。
结合数据挖掘原型系统BusinessMiner的研制及移动通信数据仓库联合实验室的研究成果试点工作,本文提出的方法在海量移动通信数据上的实际运行和应用进一步验证了本文提出的方法的有效性。