有效挖掘闭合组合序列模式

序列模式的挖掘是近年来的研究热点之一,目前很多研究都集中在闭合频繁项集与闭合序列模式的挖掘,较少涉及更加复杂、有重要应用价值的组合序列模式.针对任意长度和任意组合次数的频繁组合序列模式,提出了一种挖掘全部闭合的组合序列的算法CloCSP.为克服指数量级的候选序列进行闭合检验的困难,提出了既能生成频繁组合序列,又能有效剪枝,并同时完成闭合检验的混合扩展策略,该策略无需维护候选集.实验表明,CloCSP算法能够有效挖掘出隐藏在序列数据中,尤其是稠密数据集内的闭合组合序列模式,有助于揭示更加复杂的序列模式.     

一种无候选项的闭合序列模式挖掘算法

算法Clo Span在挖掘闭合序列模式时分两阶段进行,首先产生候选的闭合序列模式,然后在此基础上挖掘闭合序列模式。针对Clo Span算法中大量候选模式影响挖掘效率的问题,提出改进的算法ss Clo Span。该算法在序列模式增长时,利用支持度和末节点哈希表剪枝非闭合模式,同时利用频繁项头表进行闭合性检测。实验结果表明,对于不含项集项的序列,当存在较长频繁序列时,挖掘效率得到了有效的提高。     

基于闭合序列模式的减量挖掘算法

针对数据库减量时不断重复挖掘的问题,在已有闭合序列模式算法PosD*的基础上,提出一种减量挖掘算法 DePosD*。通过移动频繁和非频繁闭合序列集合之间的数据,在原有挖掘结果上直接进行更新,减少挖掘的时间。实验结果证明,在减量过程中该算法的时间效率与PosD*相比有所提高。     

基于相邻频繁模式段的闭合序列模式挖掘算法

直接对生物序列进行频繁模式挖掘会产生很多冗余模式,闭合模式更能表达出序列的功能和结构。根据生物序列的特点,提出了基于相邻闭合频繁模式段的模式挖掘算法－JCPS。首先产生闭合相邻频繁模式段,然后对这些闭合频繁模式段进行组合,同时进行闭合检测,产生新的闭合频繁模式。通过对真实的蛋白质序列家族库的处理,证明该算法能有效处理生物序列数据。     

一种用户行为模式的挖掘算法

最大频繁事件序列挖掘是数据挖掘中重要的研究课题之一。该文提出了一种新的挖掘用户行为模式的算法。该算法采用位图索引表的数据格式,使用一种有效的基于前缀树的频繁事件序列扩展方法,结合有效的剪枝技术,明显地加速了最大频繁事件序列的生成。     

一种新的工作流频繁闭合模式挖掘算法研究

为了提高工作流环境下频繁模式挖掘的准确性,提出了一种新的频繁闭合模式挖掘算法。首先扩展了依赖 矩阵的定义,即利用工作流日志建立包含直接依赖关系和交叠关系的依赖支持度矩阵。然后扩展了CHARM算法, 以在支持度矩阵的基础上自动挖掘频繁闭合活动集。最后对频繁闭合项集进行处理,以形成最终的工作流频繁闭合 模式。该算法对于并行和选择关系的处理能力优于同类算法。     

一种改进的PrefixSpan算法及其在Web用户行为模式挖掘中的应用

序列模式挖掘是从序列数据库中挖掘相对时间或其他模式出现频率高的模式。针对PrefixSpan算法构造投影数据库时开销巨大、扫描效率不高的问题,通过以序列扩展代替项集进行扩展、放弃挖掘序列数小于阈值min＿support的投影数据库以及直接递归局部频繁项等方式进行改进,并将改进方法应用于Web用户行为模式挖掘中,对日志记录中的规律进行分析和研究。实验分析表明,相比PrefixSpan算法,该改进算法在算法效率方面有一定的提高。     

缩减投影数据库规模的增量式序列模式算法

在增量式序列模式挖掘算法中,数据库更新只有插入和扩展2种操作,未考虑序列删除的情况。为此,提出一种基于频繁序列树的增量式序列模式更新算法(IUFST)。在数据库和支持度发生变化时,IUFST算法分不同情况对频繁序列树进行更新操作,缩减投影数据库的规模,提高算法效率。实验结果表明,该算法在时间性能上优于PrefixSpan算法和IncSpan算法。     

基于聚类和偏序序列的API用法模式挖掘

在软件开发过程中,开发人员经常需要遵循特定的API用法模式,而这些用法模式几乎没有相关文档作为参考。为了挖掘API用法模式,提出基于聚类和频繁闭合偏序序列的API用法模式挖掘途径。通过抽象语法树对源代码进行解析,对提取API方法调用序列进行层次聚类,最后使用频繁闭合偏序挖掘算法DFP进行API用法模式的挖掘。实验结果表明,在相同的数据集上,与SPADE算法和BIDE算法相比,所得候选API用法模式集更加精简。     

PrefixSpan算法与CloSpan算法的分析与研究

数据挖掘领域的一个活跃分支就是序列模式的发现,即在序列数据库中找出所有的频繁子序列。介绍序列模式挖掘的基本概念,然后对序列模式中的经典算法PrefixSpan算法和基于PrefixSpan框架的闭合序列模式CloSpan算法进行了描述,并对它们的执行过程及其特点进行了分析与比较,总结了各自的优缺点,指出PrefixSpan算法适用于短序列方面挖掘,而CloSpan算法在长序列或者阈值较低时胜过PrefixSpan算法且CloSpan算法挖掘大型的数据库有更好的性能,得出的结果对序列模式挖掘的设计有重要的参考价值。     

Closed inter-sequence pattern mining

Inter-sequence pattern mining can find associations across several sequences in a sequence database, which can discover both a sequential pattern within a transaction and sequential patterns across several different transactions. However, inter-sequence pattern mining algorithms usually generate a large number of recurrent frequent patterns. We have observed mining closed inter-sequence patterns instead of frequent ones can lead to a more compact yet complete result set. Therefore, in this paper, we propose a model of closed inter-sequence pattern mining and an efficient algorithm called CISP-Miner for mining such patterns, which enumerates closed inter-sequence patterns recursively along a search tree in a depth-first search manner. In addition, several effective pruning strategies and closure checking schemes are designed to reduce the search space and thus accelerate the algorithm. Our experiment results demonstrate that the proposed CISP-Miner algorithm is very efficient and outperforms a compared EISP-Miner algorithm in most cases.     

序列模式数据挖掘算法的并行化研究

序列模式在许多领域都有着重要的应用,大量的数据和模式需要高效的、可扩展的并行算法.针对目前序列模式挖掘算法存在的普遍问题,在对串行序列模式数据挖掘算法研究的基础上,本文提出了一种并行的序列模式数据挖掘算法.通过理论分析与实验验证可知:该并行数据挖掘算法,在海量数据的情形下,能很好地提高数据挖掘的效率.     

基于多核并行的海量数据序列模式挖掘*

为了在多核处理器上充分利用多核资源以提升挖掘性能,提出了一种动态与静态任务分配机制相结合的基于多核的并行序列模式挖掘算法。该算法采用数据并行与任务并行相结合的策略,在各处理器核生成局部序列模式后,再与其他处理器核协同,以最终获得所有的全局序列模式。算法通过并行局部归约技术消除了局部序列的重复生成与计算,并可结合静态与动态任务分配机制解决处理器的负载不均衡问题。理论分析和实验都证实了该算法可有效利用多核计算平台及多核体系结构优势,具有较高的运行效率和加速比。     

一种有效的并行序列模式挖掘算法

为解决共享存储的并行计算环境下挖掘序列模式时存在的处理器负载不平衡及缺少有效剪枝策略的问题,提出采用动态任务分配的办法来平衡处理器之间的工作负载,利用并行局部剪枝技术消除投影数据库的重复生成与计算以提高挖掘效率。设计一种基于共享存储SMP系统的并行序列模式挖掘算法PFSPAN。算法分析和实验结果表明,PFSPAN能够有效地挖掘序列模式。     

TSP: Mining top-k closed sequential patterns

Sequential pattern mining has been studied extensively in the data mining community. Most previous studies require the specification of a min_support threshold for mining a complete set of sequential patterns satisfying the threshold. However, in practice, it is difficult for users to provide an appropriate min_support threshold. To overcome this difficulty, we propose an alternative mining task: mining top-k frequent closed sequential patterns of length no less than min_, where k is the desired number of closed sequential patterns to be mined and min_ is the minimal length of each pattern. We mine the set of closed patterns because it is a compact representation of the complete set of frequent patterns. An efficient algorithm, called TSP, is developed for mining such patterns without min_support. Starting at (absolute) min_support=1, the algorithm makes use of the length constraint and the properties of top-k closed sequential patterns to perform dynamic support raising and projected database pruning. Our extensive performance study shows that TSP has high performance. In most cases, it outperforms the efficient closed sequential pattern-mining algorithm, CloSpan, even when the latter is running with the best tuned min_support threshold. Thus, we conclude that, for sequential pattern mining, mining top-k frequent closed sequential patterns without min_support is more preferable than the traditional min_support-based mining.     

挖掘闭合多维序列模式的可行方法

为了对闭合多维序列模式进行挖掘,研究了多维序列模式的基本性质,进而提出了挖掘闭合多雏序列模式的新方法.该方法集成了闭合序列模式挖掘方法和闭合项目集模式挖掘方法,通过证明该方法的正确性,指出闭合多维序列模式集合不大于多维序列模式集合,并且能够覆盖所有多维序列模式的结果集.最后分析了该方法所具备的两个明显优点,表明了在闭合多维序列模式挖掘中的可行性.     

基于广度优先的序列模式挖掘算法

序列模式挖掘的典型算法-GSP算法及其之后的许多相关算法的重点都是放在寻找所有的序列模式上面。CloSpan算法首先提出搜索封闭集合的思想。封闭集合比全集合更精简有效,并且和全集合有着相同的表达能力。文章的ERIC算法同样用于搜索封闭集合。然而不同于之前算法多采用深度优先的策略,ERIC算法是基于广度优先的。它利用列表来保存序列的位置数据,通过利用序列的有序性,以及基于后向超模式与等位置数据的两个修剪技巧来提高算法的搜索效率。为了确保储存最终结果列表的简洁,ERIC算法对一些特殊情况进行了分析。从最终的试验结果可以看出,ERIC算法在较小支持度的情况下对中大型数据库有很好的搜索效率。     

一种分布式全局频繁闭项目集快速挖掘更新算法

在数据挖掘研究中,频繁闭项目集挖掘成为重要的研究方向.目前已有的频繁闭项目集挖掘算法主要针对单机环境,有关分布式环境下的全局频繁闭项目集挖掘算法的研究尚不多见.针对无共享体系结构数据水平分布的情况,提出了一种分布式快速挖掘全局频繁闭项目集增量式更新算法,算法通过对各节点候选频繁项目集进行预处理,有效地降低网络通信量,提高全局频繁闭项目集挖掘算法的效率,该算法充分利用前次挖掘结果来发现新的全局频繁闭项目集,具有较高的效率.理论分析和实验结果表明算法是有效的.     

一种基于投影树的并行序列挖掘算法

在许多科学和商业领域,序列模式的发现技术发挥着越来越重要的作用,然而人们对于高效的基于投影树算法的并行模式关注较少。该文首先介绍了频繁序列挖掘模式的基本概念,然后基于投影树算法,提出了分布式存储并行序列挖掘算法,并对算法的性能进行了详细的分析。