不产生候选的快速投影频繁模式树挖掘算法

1.概述近年来,对事务数据库、时序数据库和各种其它类型数据库中的频繁模式挖掘的研究越来越普及。许多先前的研究都是采用Apriori或类似的候选产生—检查迭代算法,使用候选项集来找频繁项集。这些算法都基于一种重要的反单调的Apriori性质:任何非频繁的(k—1)-项集都不可能是频繁k-项集的子集。因此,如果一个候选k-项集的(k—1)-子集不在频繁(k—1)-项集中,则该候选也不可能是频繁的,从而可     

挖掘频繁闭序列的一种改进算法

由于频繁闭序列在数量上要远小于频繁序列且与频繁序列有着相同的表达能力在近几年倍受关注．频繁闭序列挖掘过程中最耗时同时也是最关键的步骤是序列间的包容关系检查，作者分析了频繁闭序列自身的特点以及已有的频繁闭序列挖掘算法，提出了一个挖掘频繁闭序列的算法FCSeq，该算法通过引入快速包含检查策略大大减少了不必要的包容关系判断，对提高算法的性能有着显著的作用，实验表明该算法有效．     

Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach

Mining frequent patterns in transaction databases, time-series databases, and many other kinds of databases has been studied popularly in data mining research. Most of the previous studies adopt an Apriori-like candidate set generation-and-test approach. However, candidate set generation is still costly, especially when there exist a large number of patterns and/or long patterns.In this study, we propose a novel frequent-pattern tree (FP-tree) structure, which is an extended prefix-tree structure for storing compressed, crucial information about frequent patterns, and develop an efficient FP-tree-based mining method, FP-growth, for mining the complete set of frequent patterns by pattern fragment growth. Efficiency of mining is achieved with three techniques: (1) a large database is compressed into a condensed, smaller data structure, FP-tree which avoids costly, repeated database scans, (2) our FP-tree-based mining adopts a pattern-fragment growth method to avoid the costly generation of a large number of candidate sets, and (3) a partitioning-based, divide-and-conquer method is used to decompose the mining task into a set of smaller tasks for mining confined patterns in conditional databases, which dramatically reduces the search space. Our performance study shows that the FP-growth method is efficient and scalable for mining both long and short frequent patterns, and is about an order of magnitude faster than the Apriori algorithm and also faster than some recently reported new frequent-pattern mining methods.     

Cherry:一种无须子集检查的闭合频繁集挖掘算法

通过对一些著名的闭合频繁集挖掘算法(如CLOSET ,FP-CLOSE,DCI-CLOSED和LCMv2等)的研究并结合挖掘理论分析,提出了一种新的挖掘算法Cherry,它基于FP-tree结构,并采用了新颖的CherryItem检测技术,无须在内存中保留闭合频繁集而直接检测出会导致重复的频繁项前缀,从而极大地提高了挖掘效率.性能实验的比较和测试表明,该Cherry算法在低支持度的测试中要优于目前的一些主流挖掘算法,如LCMv2,DCI-CLOSE和FP-CLOSE等.     

结合项约束的闭合模式挖掘研究

事务数据库中频繁模式的挖掘研究作为关联规则等许多数据挖掘问题的核心工作,已经研究了许多年。然而,频繁模式挖掘算法经常产生大量的模式和规则,不但降低了算法的执行效率,同时也使用户从频繁模式产生有用的规则变得很困难。针对这个问题,最近的研究主要集中于两点,一种方法是允许用户附加约束来引导挖掘的过程,通过把约束条件下推到挖掘的底层来缩小模式搜索的空问,提高性能;另一种方法是仅挖掘闭合模式,只产生大于其超集支持度的频繁模式。两种方式都可以大量缩小结果集合的大小,使结果集合更容易被用户理解和使用。那么,把这两种方式相结合,挖掘满足用户约束的闭合频繁模式,理论上来说应该更为高效,更方便理解和使用。基于以上的考虑,做了一些细致的研究,把用户约束分类,并主要讨论了结合项约束的闭合模式生成问题。     

数据流中频繁闭合模式的挖掘

频繁闭合模式集可唯一确定频繁模式完全集。根据数据流的特点,提出一种挖掘频繁闭合项集的算法,该算法将数据流分段,用DSFCI_tree动态存储潜在频繁闭合项集,对每一批到来的数据流,建立局部DSFCI_tree,进而对全局DSFCI_tree进行更新并剪枝,从而有效地挖掘整个数据流中的频繁闭合模式。实验表明,该算法具有良好的时间和空间效率。     

一种基于MapReduce的频繁闭项集挖掘算法

频繁闭项集的挖掘是发现数据项之间关联规则的一种有效方式。当前以MapReduce模式为基础的云计算平台为解决海量数据中的关联规则挖掘问题提供新的解决思路。文中提出并实现一种基于Hadoop云计算平台的频繁闭项集的并行挖掘算法。该算法主要包括并行计数、构造全局频繁项表、并行挖掘局部频繁闭项集和并行筛选全局频繁闭项集四个步骤。在多个数据集上的实验表明,该方法能较大提高数据挖掘的效率,具有较好的加速比。     

挖掘闭合模式的高性能算法

频繁闭合模式集惟一确定频繁模式完全集并且尺寸小得多,然而挖掘频繁闭合模式仍然是时间与存储开销很大的任务.提出一种高性能算法来解决这一难题.采用复合型频繁模式树来组织频繁模式集,存储开销较小.通过集成深度与宽度优先策略,伺机选择基于数组或基于树的模式支持子集表示形式,启发式运用非过滤虚拟投影或过滤型投影,实现复合型频繁模式树的快速生成.局部和全局剪裁方法有效地缩小了搜索空间.通过树生成与剪裁代价的平衡实现时间效率与可伸缩性最大化.实验表明,该算法时间效率比其他算法高5倍到3个数量级,空间可伸缩性最佳.它可以进一步应用到无冗余关联规则发现、序列分析等许多数据挖掘问题.     

一种挖掘频繁闭项集的改进算法

频繁闭项集的挖掘是近年来频繁项集挖掘研究的热点。本文引入了共生项集的概念,从一个新的角度看待频繁闭项集的挖掘问题。利用共生项集的性质,本文提出了一种新的无需遍历结果集的闭合性检查方法,并在此基础上对CLOSET算法进行改进,实验证明,取得了良好的效果。     

一种改进的频繁闭项集挖掘算法

频繁闭项集惟一确定频繁项集且规模小得多,但挖掘频繁闭项集仍是很费时的.为提高挖掘效率,提出了一种改进的频繁闭项集挖掘算法DCI-Closed-Index.该算法用"索引数组"来组织数据,通过为每个项目增加包含索引,找到频繁共同出现的项集.利用二进制位图技术,给出了一个求包含索引的快速算法.然后根据项目在包含索引中出现的频率由高到低进行排序,并利用包含索引作为启发信息,合并同时出现且支持度相等的频繁项,得到初始生成子,从而大大缩小了搜索空间.同时利用索引数组对每一个生成子的前序集和后序集进行约简,得到新的、较小的约简前序集和约简后序集.并证明了约简前序集和后序集与原来的前序集和后序集的功能是一样的.从而减少了候选生成子的集合包含判断的操作.实验结果表明,该算法的性能优于其他主流算法.     

基于FP-Tree的频繁闭合项目集挖掘算法的研究

目前频繁闭合项目集挖掘算法有很多,例如CLOSET[1]。CLOSET以FP-Growth为基础,采用FP-Tree来表示模式支持集,通过深度优先搜索来挖掘频繁闭合模式。其困难是,递归构造“条件FP-Tree”的CPU开销和存储开销很大。为解决上面的问题,论文提出一种基于FP-Tree和COFI-Tree的频繁闭合项目集挖掘算法,在该算法中引用了COFI-Tree结构,COFI-Tree无需递归地构造“条件FP-Tree”,并且某一时刻只有一个频繁项的COFI-Tree在内存,所以大大减少了内存消耗。通过实验证明:当挖掘大型数据库时,在执行时间方面,该算法比其它算法更有效。     

MFCPLG：微阵列数据中频繁闭合模式挖掘

微阵列数据集行少列多的特征，使得传统基于列枚举空间的算法应用于其中进行频繁闭合模式挖掘时其复杂性迅速增长。基于行枚举的CARPENTER算法较好解决了该问题。但CARPENTER算法使用映射转置表(TT)来完成频繁闭合模式完全集的挖掘效率不高。该文在CARPENTER算法基础上，提出LG-tree数据结构，并基于此结构提出挖掘频繁闭合模式的新算法MFCPLG。真实数据集的实验表明，MFCPLG算法的时间性能优于CARPENTER算法。     

一种改进的频繁闭项集挖掘算法

频繁闭项集惟一确定频繁项集且规模小得多,但挖掘频繁闭项集仍是很费时的.为提高挖掘效率,提出了一种改进的频繁闭项集挖掘算法DCI-Closed-Index. 该算法用“索引数组”来组织数据,通过为每个项目增加包含索引,找到频繁共同出现的项集.利用二进制位图技术,给出了一个求包含索引的快速算法.然后根据项目在包含索引中出现的频率由高到低进行排序,并利用包含索引作为启发信息,合并同时出现且支持度相等的频繁项,得到初始生成子,从而大大缩小了搜索空间.同时利用索引数组对每一个生成子的前序集和后序集进行约简,得到新的、较小的约简前序集和约简后序集.并证明了约简前序集和后序集与原来的前序集和后序集的功能是一样的.从而减少了候选生成子的集合包含判断的操作.实验结果表明,该算法的性能优于其他主流算法.     

Efficient Mining of Frequent Closed XML Query Pattern

Previous research works have presented convincing arguments that a frequent pattern mining algorithm should not mine all frequent but only the closed ones because the latter leads to not only more compact yet complete result set but also better efficiency. Upon discovery of frequent closed XML query patterns, indexing and caching can be effectively adopted for query performance enhancement. Most of the previous algorithms for finding frequent patterns basically introduced a straightforward generate-and-test strategy. In this paper, we present SOLARIA＊, an efficient algorithm for mining frequent closed XML query patterns without candidate maintenance and costly tree-containment checking. Efficient algorithm of sequence mining is involved in discovering frequent tree-structured patterns, which aims at replacing expensive containment testing with cheap parent-child checking in sequences. SOLARIA＊ deeply prunes unrelated search space for frequent pattern enumeration by parent-child relationship constraint. By a thorough experimental study on various real-life data, we demonstrate the efficiency and scalability of SOLARIA＊ over the previous known alternative. SOLARIA＊ is also linearly scalable in terms of XML queries＇ size.     

频繁闭合项目集的并行挖掘算法研究

频繁项目集挖掘因其在数据挖掘领域中的基础地位和广泛应用备受学术界和产业界的关注,用挖掘频繁闭合项目集代替挖掘频繁项目集是近年来提出的一个重要策略。不同于以往提出的挖掘所有频繁项目集的并行算法,本文针对频繁闭合项目集的特性及并行挖掘的特点,给出了共享存储器模型上(Shared Memory)基于频繁模式树(FP-tree)的挖掘频繁闭合项目集的并行算法(FCIPM)思想,提出了频繁闭合项目集直接判断法,性能分析表明所提技术对算法的性能提高起到了关键作用。     

一种不产生候选项挖掘频繁项集的新算法

Apriori算法是关联规则挖掘算法中应用最为广泛的一种算法,它的主要目的是从大量的事务数据中通过候选项集挖掘出有趣的频繁项集,从而为用户提供有意义的关联关系。但随着数据库规模的扩大,apriori算法可能会产生如下两大棘手问题:大量候选项集的产生将造成巨大计算量的浪费;为剪掉无用候选项如何设置阈值。这些问题相对于众多普通用户来说都具有挑战性。该文提出的代码与运算是一种无须候选项挖掘频繁项集的算法,用户无须为设置阈值而煞费苦心。同时事务压缩算法的加入大大减少了算法中的计算量。     

数据流上的频繁闭项集挖掘算法

针对频繁闭项集挖掘算法中数据结构与处理机制复杂的问题,提出窗口快速滑动的数据流频繁闭项集挖掘算法——MFWSR。算法通过采用紧致的数据结构和简化的判断过程提高时空效率,支持响应不同用户支持度阈值的查询。实验结果表明,在保持已有算法精度的情况下,MFWSR具有更高的时空效率。     

一种基于频繁模式树的最大频繁项目集挖掘算法

目前提出的频繁项目集挖掘算法大多基于Apriori算法思想,这类算法会产生巨大的候选集并且重复扫描数据库.针对这一问题,给出一种基于频繁模式树的最大频繁项目集挖掘算法FP-MFIA,该算法利用频繁模式树对最大频繁项目集进行检索,通过位图建树的方法有效的减少了扫描数据库的次数,从而节省了CPU的执行时间.另外,此算法运用独特的最大频繁项目集判断策略,同时运用投影技术进行超集检测,提高了遍历的效率,实验结果表明该算法是快速有效的.     

微阵列数据中Top-k频繁闭合项集挖掘

现有大部分微阵列数据中频繁闭合项集的挖掘需要事先给定最小支持度,但在实际应用中该最小支持度很难确定。针对该问题,提出top-k频繁闭合项集挖掘算法,基于自顶向下宽度优先搜索策略挖掘项集长度不小于min_l的top-k频繁闭合项集,并对搜索空间进行有效修剪,从而提高搜索速度。实验结果表明,该算法的时间性能在多数情况下优于CARPENTER算法。     

频繁闭项目集挖掘算法研究

目前已提出了许多基于Apriori算法思想的频繁项目集挖掘算法,这些算法可以有效地挖掘出事务数据库中的短频繁项目集,但对于长频繁项目集的挖掘而言,其性能将明显下降.为此,提出了一种频繁闭项目集挖掘算法MFCIA,该算法可以有效地挖掘出事务数据库中所有的频繁项目集,并对其更新问题进行了研究,提出了一种相应的频繁闭项目集增量式更新算法UMFCIA,该算法将充分利用先前的挖掘结果来节省发现新的频繁闭项目集的时间开销.实验结果表明算法MFCIA是有效可行的.