基于模式增长的不确定数据的频繁模式挖掘算法

为提高不确定数据频繁模式(FP)挖掘算法的时空效率,提出了基于最大概率的不确定频繁模式挖掘(UFPM-MP)算法。首先,利用事务项集中的最大概率值预估期望支持数;然后,使用该期望支持数与最小期望支持数阈值进行比较,以确定某一项集是否为候选频繁项集,并对候选项集建立子树以递归挖掘频繁模式。实验中,UFPM-MP算法与AT-Mine算法进行了对比,并在6个典型的数据集上进行实验验证。实验结果表明,UFPM-MP算法的时空效率得到了提高,稀疏数据集上提高约30%,稠密数据集上的效率提高更为明显(约3~4倍)。预估期望支持数的策略有效地减少了子树和头表项的数量,从而提高了算法的时空效率;且最小期望支持数越小,或需要挖掘的频繁模式越多的时候,算法的时间效率提高越多。     

基于模式增长方式的高效用模式挖掘算法

高效用模式挖掘是数据挖掘领域的一个重要研究内容; 由于其计算过程包含对模式的内、外效用值的处理, 计算复杂度较大, 因此挖掘算法的主要研究热点问题就是提高算法的时间效率.针对此问题, 本文给出一个基于模式增长方式的高效用模式挖掘算法HUPM-FP, 该算法可以从全局树上挖掘高效用模式, 避免产生候选项集.实验中, 采用6个典型数据集进行实验, 并和目前效率较好的算法FHM (Faster high-utility itemset mining)做了对比, 实验结果表明本文给出的算法时空效率都有较大的提高, 特别是时间效率提高较大, 可以达到1个数量级以上.     

一种基于Spark的频繁项集快速挖掘算法

如何在海量数据集中提高频繁项集的挖掘效率是目前研究的热点.随着数据量的不断增长,使用传统算法产生频繁项集的计算代价依然很高.为此,提出一种基于Spark的频繁项集快速挖掘算法（fast mining algorithm of frequent itemset based on spark,Fmafibs）,利用位运算速度快的特点,设计了一种新颖的模式增长策略.该算法首先采用位串表达项集,利用位运算来快速生成候选项集;其次,针对超长位串计算效率低的问题,考虑将事务垂直分组处理,将同一事务不同组之间的频繁项集通过连接获得候选项集,最后进行聚合筛选得到最终频繁项集.算法在Spark环境下,以频繁项集挖掘领域基准数据集进行实验验证.实验结果表明所提方法在保证挖掘结果准确的同时,有效地提高了挖掘效率.     

基于模式增长的高效用序列模式挖掘算法

高效用序列模式挖掘是数据挖掘领域的一项重要内容, 在生物信息学、消费行为分析等方面具有重要的应用.与传统基于频繁项模式挖掘方法不同, 高效用序列模式挖掘不仅考虑项集的内外效用, 更突出项集的时间序列含义, 计算复杂度较高.尽管已经有一定数量的算法被提出应用于解决该类问题, 挖掘算法的时空效率依然成为该领域的主要研究热点问题.鉴于此, 本文提出一个基于模式增长的高效用序列模式挖掘算法HUSP-FP.依据高效用序列项集必须满足事务效用闭包属性要求, 算法首先在去除无用项后建立全局树, 进而采用模式增长方法从全局树上获取全部高效用序列模式, 避免产生候选项集. 在实验环节与目前效率较好的HUSP-Miner、USPAN、HUS-Span三类算法进行了时空计算对比, 实验结果表明本文给出算法在较小阈值下仍能有效挖掘到相关序列模式, 并且在计算时间和空间使用效率两方面取得了较大的提高.     

基于快速高效用项集挖掘的大规模消息流预测算法研究与应用

为了提高大规模消息流话题预测的准确性与效率,提出基于高效用项集挖掘的消息流话题预测算法。计算时间窗口中词汇的内部效用与外部效用,根据会话内所有词汇的效用计算最小效用值;采用高效用项集挖掘算法产生候选话题模式集,随之提取最终的话题模式。为了提高高效用项集挖掘的时间效率与存储效率,设计三角项集效用树保存项集的效用信息,设计话题搜索树保存候选话题模式集。最终基于真实消息流数据集进行实验,结果显示该算法有效地提高了话题预测的准确率,并且实现了较快的响应时间。     

基于矩阵的数据流Top-k频繁项集挖掘算法

传统的数据挖掘算法在挖掘频繁项集时会产生大量的冗余项集,影响挖掘效率。为此,提出一种基于矩阵的数据流Top-k频繁项集挖掘算法。引入2个0-1矩阵,即事务矩阵和二项集矩阵。采用事务矩阵表示滑动窗口模型中的事务列表,通过计算每行的支持度得到二项集矩阵。利用二项集矩阵得到候选项集,将事务矩阵中对应的行做逻辑与运算,计算出候选项集的支持度,从而得到Top-k频繁项集。把挖掘的结果存入数据字典中,当用户查询时,能够按支持度降序输出Top-k频繁项集。实验结果表明,该算法在挖掘过程中能避免冗余项集的产生,在保证正确率的前提下具有较高的时间效率。     

一种基于单事务项集组合的频繁项集挖掘算法

Apriori是挖掘频繁项集的基本算法,目前该算法及其优化变种都没有解决候选项及重复扫描事务数据库的问题.文章通过对Apriori及其优化算法的深入探究,提出了一种基于单事务组合项集的挖掘算法,该算法在一个事务内部对"数据项"进行组合,在事务数据库中对所有相同"项集"进行计数.不经过迭代过程,不产生候选项集,所有频繁项集的挖掘过程只需对事务数据库一次扫描,提高了频繁项集挖掘效率.     

基于多效用阈值的分布式高效用序列模式挖掘

针对序列模式的高效用模式挖掘过程中搜索空间大、计算复杂度高的问题,提出一种基于多效用阈值的分布式高效用序列模式挖掘算法。采用数组结构保存模式的效用信息,解决效用矩阵导致的内存消耗大的缺点。设计1-项集与2-项集的深度剪枝策略,深入地缩小候选模式的搜索空间,减少搜索时间成本与缓存成本。提出挖掘算法的分布式实现方案,通过并行处理进一步降低模式挖掘的时间。基于中等规模与大规模的序列数据集分别进行实验,实验结果表明,该算法有效减少了候选模式的数量,降低了挖掘的时间成本与存储成本,对于大数据集表现出较好的可扩展能力与稳定性。     

频繁和高效用项集挖掘

对从事务数据库中挖掘有意义的项集的研究已超过10年.然而,大多数的研究要么使用频繁度或支持度(如频繁项集挖掘),要么使用效用值或利润(如高效用项集挖掘)作为主要的衡量标准.单独使用这两种衡量方式都有各自的局限性,比如频繁度很高的项集其效用值有可能很低,而效用值很高的项集其频繁度往往很低,将这些项集推荐给用户没有意义.将这两种衡量标准综合考虑,希望找出那些频繁度和效用值都很高的项集.该项工作最大的挑战是效用值既不满足单调性也不满足反单调性.因此,提出了高效算法FHIMA.FHIMA采用PrefixSpan的思想,挖掘时能避免产生非频繁的候选项集.此外,还根据效用和质量上界的一些性质,有效地缩小了搜索空间,极大地提高了FHIMA算法的效率.     

一种基于条件矩阵的最大频繁项集挖掘算法

在数据挖掘问题的研究中,为减少候选最大频繁项集数量和降低超集存在判断的开销,为了优化算法,提出了一种基于条件矩阵挖掘最大频繁项集的算法(conditional matrix for maximal frequent itemsets,CMMFI).将压缩频繁模式树表示的频繁项集信息投影到条件矩阵,采用最大顺序尾项排序和扩展2项集剪枝,有效削减了搜索空间,提高了算法的空间效率.使用标号数组优化超集检测的过程,减少了频繁项集比较的次数,减少了花费时间.最后,选用了两个模式长度不同的数据集,将算法与FPMax算法进行性能比较,实验结果验证了算法的有效性和优越性.     

目标频繁模式挖掘算法研究

通用的频繁模式挖掘算法通常产生庞大的频繁模式集,其中很多是用户不感兴趣的非目标模式。要排除这些非目标模式,用户必须进行"二次挖掘"。TFP-growth虽然生成所有最大目标频繁模式,但要从中获得目标频繁模式,还需经过"二次挖掘"。若在挖掘的早期就对非目标频繁模式的产生加以限制,则有望提高算法的效率。本文在TFP-growth和SFP-growth的基础上,提出一种目标频繁模式挖掘算法STFP-growth,通过对TFP-树的排序、根据树根结点的不同情形采用不同的建子树方法和目标频繁模式筛选方法等来提高算法的效率。STFP-growth挖掘的结果是所有满足用户需求的目标频繁模式,不需"二次挖掘"。实验表明,STFP-growth的效率高于TFP-growth,也明显优于Apriori和Eclat。     

Efficient Mining of Frequent Patterns Using Ascending Frequency Ordered Prefix-Tree

Mining frequent patterns, including mining frequent closed patterns or maximal patterns, is a fundamental and important problem in data mining area. Many algorithms adopt the pattern growth approach, which is shown to be superior to the candidate generate-and-test approach, especially when long patterns exist in the datasets. In this paper, we identify the key factors that influence the performance of the pattern growth approach, and optimize them to further improve the performance. Our algorithm uses a simple while compact data structure—ascending frequency ordered prefix-tree (AFOPT) to store the conditional databases, in which we use arrays to store single branches to further save space. The AFOPT structure is traversed in top-down depth-first order. Our analysis and experiment results show that the combination of the top-down traversal strategy and the ascending frequency order achieves significant performance improvement over previous works.     

一种基于压缩前缀树的频繁模式挖掘算法

针对FP-growth算法存在动态维护复杂、在挖掘过程中需要递归地创建大量的条件频繁模式树,导致时空效率不高等不足,本算法在压缩前缀树的基础上,通过调整树中节点信息和节点链,采用深度优先的策略挖掘频繁模式,无需任何附加的数据结构,极大地减少了系统资源的消耗,减少树的规模和遍历次数,挖掘效率大大提高。     

基于相邻模式段组合的生物序列模式挖掘算法

传统的序列模式挖掘算法应用在生物序列上有其局限性,根据生物序列的特点,提出了基于相邻频繁模式段的模式挖掘算法－JPS。首先产生相邻频繁模式段,然后对这些频繁模式段进行组合,产生新的频繁模式。通过实验分析,该方法在相似性很强的序列数据库中比传统的PrefixSpan算法效率高。通过对真实的蛋白质序列家族库的处理,证明该算法能有效处理生物序列数据。     

An algorithm for Fast Mining Top-rank-k Frequent Patterns Based on Node-list Data Structure

Frequent pattern mining usually requires much run time and memory usage. In some applications, only the patterns with top frequency rank are needed. Because of the limited pattern numbers, quality of the results is even more important than time and memory consumption. A Frequent Pattern algorithm for mining Top-rank-K patterns, FP_TopK, is proposed. It is based on a Node-list data structure extracted from FTPP-tree. Each node is with one or more triple sets, which contain supports, preorder and postorder transversal orders for candidate pattern generation and top-rank-k frequent pattern mining. FP_ TopK uses the minimal support threshold for pruning strategy to guarantee that each pattern in the top-rank-k table is really frequent and this further improves the efficiency. Experiments are conducted to compare FP_TopK with iNTK and BTK on four datasets. The results show that FP_TopK achieves better performance.     

一种无阈值的频繁模式生成算法

在数据挖掘的关联规则挖掘算法中,传统的频繁模式挖掘算法需要用户指定项集的最小支持度。引入Top-k模式挖掘概念的改进算法虽然无需指定最小支持度,但仍需指定阈值k。针对上述问题,对传统挖掘算法进行改进,提出一种新的频繁模式挖掘算法(TNFP- growth)。该算法无需指定最小支持度或阈值,按照支持度降序排列进行模式挖掘,有序地返回频繁模式给用户。实验结果证明,该算法的执行效率更高,具有更强的伸缩性。     

一种基于升序FP-tree的频繁模式挖掘算法

本文提出了一种基于升序FP-tree的频繁模式挖掘算法,该算法按照支持度升序构造升序FP-tree,并通过在其中搜索扩展频繁集及归并子树来挖据频繁模式。实验表明,与FP-growth算法相比,算法的挖掘速度提高了将近2倍,此外新算法还具有比较好的伸缩性。     

基于FP—tree的最大频繁项集挖掘新算法

研究挖掘关联规则的一个重要工作就是找出所有的频繁项集。基于FP—tree的最大频繁项集挖掘算法要多次生成大量的FP—tree,并且需要对其多次遍历,消耗了大量的时间。针对以上缺点,提出一种基于FP—tree并利用数组和矩阵技术进行优化的最大频繁项集挖掘算法（Mining Maximal Frequent Itemset。简称MMFI）,它既减少创建FP—tree的数量,又节省遍历FP—tree的时间,实验证明本算法是有效的。     

频繁模式挖掘的约束算法

在频繁模式挖掘过程中能够动态改变约束的算法比较少.提出了一种基于约束的频繁模式挖掘算法MCFP.MCFP首先按照约束的性质来建立频繁模式树,并且只需扫描一遍数据库,然后建立每个项的条件树,挖掘以该项为前缀的最大频繁模式,并用最大模式树来存储,最后根据最大模式来找出所有支持度明确的频繁模式.MCFP算法允许用户在挖掘频繁模式过程中动态地改变约束.实验表明,该算法与iCFP算法相比是很有效的.