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

频繁闭项目集挖掘是数据挖掘研究中的一个重要研究课题.目前已有的频繁闭项目集挖掘算法主要针对单机环境,有关分布式环境下的全局频繁闭项目集挖掘算法的研究尚不多见.为此,本文提出了一种快速挖掘全局频繁闭项目集算法,并对其更新问题进行了研究;提出了一种相应的频繁闭项目集增量式更新算法,该算法将充分利用先前的挖掘结果来节省发现新的全局频繁闭项目集的时间开销.实验结果表明算法是有效的.     

基于FC-tree的频繁闭项目集挖掘算法

目前提出的频繁项目集挖掘算法大多基于Apriori算法思想,但这类算法会产生巨大的候选集并且重复扫描数据库.本文针对这一问题,给出了一种基于FC-tree的频繁闭项目集挖掘算法Max-FCIA,该算法将频繁项目集存储在哈希表中,节省了程序的搜索时间.此外,利用广度优先搜索和有效的剪枝策略,大大限制了候选项目集的生成,缩小了搜索空间从而提高了程序的性能.实验结果表明该算法是快速有效的.     

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

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

基于粒度计算的频繁闭项目集挖掘

针对现有频繁闭项目集挖掘算法存在的不足,提出了一种基于粒度计算的频繁闭项目集挖掘算法。通过混合进制数的变化来生成候选项目集,避免使用了复杂的数据结构,减少了内存和CPU的开销;利用粒度计算的分而治之思想来计算频繁闭项目集的支持度,避免了多次重复扫描数据库,减少了计算复杂度和I/O开销。实验结果表明该算法比经典的频繁闭项目集挖掘算法快速而有效。     

基于FP_tree的最大频繁项目集增量式更新算法

关联规则的更新是数据挖掘研究的一个重要内容,能否有效地挖掘出动态事务数据库中的最大频繁项目集是衡量一个关联规则更新算法好坏的关键因素。提出基于FP_tree的最大频繁项目集增量式更新(MFIUP)算法,以处理最小支持度和事务数据库同时发生变化之后相应频繁项目集的更新问题,其中事务数据库的变化同时包括增加和减少两种情况,并对其优越性进行了分析和测试。     

基于FP_tree的频繁项目集增量式更新算法

对频繁项目集的更新问题进行研究,提出一种基于频繁模式树的频繁项目集增量式更新算法。充分利用已有挖掘结果,有效解决最小支持度和事务数据库同时发生变化时相应频繁项目集的更新问题。在事务数据库变化同时包括增加和减少的情况下,对算法性能进行分析与测试,结果证明该算法高效可行。     

一种更新频繁项目集的快速算法

数据库的更新会引起数据库中的关联规则的更新,找出更新后的所有的频繁项目集,也就能生成更新后的关联规则,因此关联规则的更新就转化为频繁项目集的更新。UWEP算法 利用以前的挖掘结果来减少挖掘新的频繁项目集的开销,采用了一些优化技术来减少数据库的扫描次数和候选项目集的数量,但UWEP算法只能处理增加新事务的情况。本文提出 的UWEP2算法是UWEP算法的扩展,能处理数据库中事务的增加、删除、修改等情况。我们将它与另一种更新频繁项目集的算法FUP2比较,实验显示,UWEP2算法比FUP2算法生成的候选项目集要少,性能要高。     

一种快速挖掘频繁项目集算法

发现频繁项目集是多种数据挖掘应用中的的,最新的研究主要围绕减少事务数据库的扫描次数进而减少挖掘过程的I/O代价来提高效率.本文提出一种快速挖掘频繁项目集的算法FDFI(fast discoveryfrequentitemsets).该算法利用深度优先搜索的特点,结合频繁项目集的性质,有效地缩小了搜索空间,并采用独特的支持度计数策略,只需一次数据库扫描,就可计算所有项目集的支持度,大大减少了数据扫描量.最后作者对这一算法的性能进行了理论分析和实验验证.     

基于DDMINER分布式数据库系统中频繁项目集的更新

给出了一种分布式数据挖掘系统的体系结构DDMINER，对分布式数据库系统中频繁项目集的更新问题进行探讨，既考虑了数据库中事务增加的情况，又考虑了事务删除的情况；提出了一种基于DDMINER的局部频繁项目集的更新算法ULF和全局频繁项目集的更新算法UGF．该算法能够产生较少数量的候选频繁项目集，在求解全局频繁项目集过程中，传送候选局部频繁项目集支持数的通信量为O(n)；将文章提出的算法用Java语言加以实现，并对算法性能进行了研究；实验结果表明这些算法是正确、可行的，并且具有较高的效率．     

基于分解事务矩阵的关联规则挖掘算法

Apriori算法是数据挖掘领域挖掘关联规则频繁项目集的经典算法,但该算法存在产生大量的候选项目集及需要多次扫描数据库的缺陷。为此提出一种新的挖掘关联规则频繁项目集算法（ CApriori算法）：利用分解事务矩阵来压缩存放数据库的相关信息,进而对分解事务矩阵进行关联规则挖掘;优化了由频繁k -1项目集生成频繁k项目集的连接过程;提出了一种不需要扫描数据库,利用行集“与运算”快速计算支持数的方法,改进算法挖掘所有的频繁项目集只需扫描数据库两次。实验结果表明,改进算法在最小支持度较小时效率高于Apriori算法。     

一种基于后缀项表的并行闭频繁项集挖掘算法

对现有的基于MapReduce的并行频繁项集挖掘算法进行了研究, 提出一种基于后缀项表的并行闭频繁项集挖掘算法, 通过后缀项表的引入及以闭频繁项集挖掘的形式, 减少组分间的数据传送量, 提高挖掘效率。实验表明, 该算法可以有效缩短平均挖掘时间, 对于高维大数据具有较好的性能。     

频繁项集挖掘的研究进展及主流方法

关联分析作为数据挖掘的主要研究模块之一,主要用于发现隐藏在大型数据集中的强关联特征。而多数关联规则挖掘任务可分为频繁模式(频繁项集、频繁序列、频繁子图)的产生和规则的产生。前者发现数据集中满足最小支持度阈值的项集、序列与子图;后者从上一步发现的频繁模式中提取高置信度的规则。频繁项集挖掘是许多数据挖掘任务中的关键问题,也是关联规则挖掘算法的核心。十几年来,学者们致力于提高频繁项集的生成效率,从不同的角度进行改进以提高算法效率,大量的高效可伸缩性算法被提出。文中对频繁项集挖掘进行深入分析,对完全频繁项集、闭频繁项集、极大频繁项集的典型算法进行介绍和评述,最后对频繁项集挖掘算法的研究方向进行简要分析。     

基于频繁项集挖掘最大频繁项集和频繁闭项集

提出了基于频繁项集的最大频繁项集（BFI-DMFI）和频繁闭项集挖掘算法（BFI-DCFI）。BFI-DMFI算法通过逐个检测频繁项集在其集合中是否存在超集确定该项集是不是最大频繁项集;BFI-DCFI算法则是通过挖掘所有支持度相等的频繁项集中的最大频繁项集组合生成频繁闭项集。该类算法的提出,为关联规则的精简提供了一种新的解决方法。     

在线挖掘数据流闭合频繁项集CMNL-SW算法

提出了一种新的CMNL-SW(Closed map and num list-sliding window)挖掘算法。具体使用数据结构Closedmap存储挖掘到的闭合项集和Num list存储所有不同项的序号,通过对添加新事务和删除旧事务包含的项序号进行简单的并集和该事务与之相关已经挖掘到的闭合项集进行交集运算来更新当前滑动窗口,使之能够根据用户任意指定的支持度阈值在线输出数据流上闭合频繁项集信息。通过理论分析和对真实数据集Mushroom,Retail-chain和人工合成数据集T40I10D100K的挖掘结果表明,提出的算法在时空效率上明显优于同类经典算法Moment和CFI-Stream,并且随着数据流上处理事务数的递增和快速改变表现出良好的稳定性。     

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

针对相关算法在挖掘频繁闭项集时所存在的问题, 提出了一种基于位运算的频繁闭项集挖掘算法。该算法首先将数据集转换成布尔矩阵, 只需扫描数据集一次; 通过位运算计算支持度, 利用矩阵和数组存储辅助信息, 减少时间和空间消耗; 深度优先搜索产生频繁闭项集时利用剪枝策略进一步减少挖掘时间; 利用同生项集性质进行闭合性检测, 无须检查超集或子集。理论分析和实验结果验证了该算法的有效性。     

一种高效的最大频繁项集挖掘算法DFMFI-Miner

分析最大频繁项集和完全频繁项集的关系,提出了一个挖掘最大频繁项集的高效算法DFMFI—Miner（The Miner Basedon Depth—First Searching for Mining Maximal Frequent Itemsets）,采用深度优先方法搜索项集空间,采用垂直位图及一定的压缩方法对表示事务数据库并进行约简,并采用多种有效剪枝策略和优化策略,提高了算法的效率。在多个数据集上进行了实验,实验结果表明该算法特别适于挖掘具有长频繁项集的数据集。