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

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

快速更新频繁闭合项目集算法

频繁闭合项目集集可惟一确定频繁项目集完全集且数量小得多,然而有关频繁闭合项目集的更新还不多见。为此,提出快速更新频繁闭合项目集算法—FUAFCI(Fast Updating Algorithm of Frequent Closed Itemsets),该算法主要考虑最小支持度发生变化时频繁闭合项目集的更新情况。FUAFCI在最坏的情况下仅须扫描各局部数据库一遍,且利用CLOSET+的项目集合并、子项目集修剪以及子集检验等优化策略及已挖掘的结果,可确保对频繁闭合项目集进行高效的更新。验结果表明,FUAFCI算法是有效可行的。     

一种改进的最大频繁项目集挖掘算法

本文提出了一种基于布尔矩阵FP-array的最大频繁项目集挖掘的并行算法。该算法利用基于前缀的划分方法将事务数据集划分为较小的子空间,并将具有完全包含关系的项目集分配到同一处理机,然后各处理机站点Si分别进行局部最大频繁项目集的挖掘,再将挖掘结果传送到主站点S,最后得到全局最大频繁项目集。     

快速挖掘频繁项目集算法

频繁项目集挖掘是数据挖掘领域最重要的基本问题之一,在分析已有算法的基础上,提出了一种能够快速挖掘频繁项目集的算法,对频繁项目集挖掘的搜索空间以及数据表示进行了优化,缩小搜索空间和数据表示的规模,减少计算项目集支持数的时间,提高算法的执行效率,实验结果表明,该算法在性能上优于FP-Growth算法.     

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

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

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

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

最小支持度变化时分布式数据库中频繁项目集更新

讨论分布式数据库系统中最小支持度变化时频繁项目集如何高效更新问题，提出了一种基于最小支持度变化的局部频繁项目集的更新算法ULFS和全局频繁项目集的更新算法UGFS．该算法能够充分利用已挖掘的结果．并且产生较少数量的候选频繁项目集，在求解全局频繁项目集过程中．候选局部频繁项目集支持数的通信量为O(n)．将文章提出的算法用Java加以实现．并时算法性能进行了研究．实验结果表明这些算法是可行、有效的．并且具有较快的速度．     

基于FP-tree的最大频繁项目集挖掘算法

最大频繁项目集挖掘是数据挖掘领域最重要的基本问题之一,在分析已有算法的基础上提出了FP-MMFI算法,它是对FP-growth算法在最大频繁项目集挖掘上的扩展.提出了频繁路径的概念,用它可以有效地对FP-tree进行压缩和缩小搜索空间,同时使用投影的方法对超集检测进行了优化,减少了项目匹配的次数.最后实验结果表明,该算法在性能上优于已有的同类算法.     

一种基于F-矩阵的最大频繁项目集快速挖掘算法

最大频繁项目集挖掘是多种数据挖掘应用研究的一个重要方面,最大频繁项目集的快速挖掘算法研究是当前研究的热点。传统的最大频繁项目集挖掘算法要多遍扫描数据库并产生大量的候选项目集。为此,该文提出了基于F-矩阵的最大频繁项目集快速挖掘算法FMMFIBFM,FMMFIBFM采用FP-tree的存储结构,仅须扫描数据库两遍且不产生候选频繁项目集,有效地提高了频繁项目集的挖掘效率。实验结果表明,FMMFIBFM算法是有效可行的。     

最大频繁项目集的快速更新

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题．为克服基于Apriori的最大频繁项目集挖掘算法存在的不足,DMFIA采用FP-tree存储结构及自顶向下的搜索策略,有效地提高了最大频繁项目集的挖掘效率．但对于频繁项目多而最大频繁项目集维数相对较小的情况,DMFIA要经过多层搜索且在每一层产生大量的候选项目集,因而影响算法的执行效率．为此,该文提出了DMFIA的改进算法IDMFIA(the Improved algorithm of DMFIA)．IDMFIA采用自顶向下和自底向上双向搜索策略,可尽早修剪掉较短最大频繁项目集的超集和较长最大频繁项目集的子集．另外,该文还提出最大频繁项目集更新算法FUMFIA(Fast Updating Maximum Frequent Itemsets Algorithm),该算法充分利用已建立的FP-tree和已挖掘的最大频繁项目集,可对已挖掘的最大频繁项目集进行高效维护．实验结果表明,IDMFIA和FUMFIA可有效提高最大频繁项目集的挖掘和更新效率．     

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

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

DBV-Miner: A Dynamic Bit-Vector approach for fast mining frequent closed itemsets

Frequent closed itemsets (FCI) play an important role in pruning redundant rules fast. Therefore, a lot of algorithms for mining FCI have been developed. Algorithms based on vertical data formats have some advantages in that they require scan databases once and compute the support of itemsets fast. Recent years, BitTable (Dong & Han, 2007) and IndexBitTable (Song, Yang, & Xu, 2008) approaches have been applied for mining frequent itemsets and results are significant. However, they always use a fixed size of Bit-Vector for each item (equal to number of transactions in a database). It leads to consume more memory for storage Bit-Vectors and the time for computing the intersection among Bit-Vectors. Besides, they only apply for mining frequent itemsets, algorithm for mining FCI based on BitTable is not proposed. This paper introduces a new method for mining FCI from transaction databases. Firstly, Dynamic Bit-Vector (DBV) approach will be presented and algorithms for fast computing the intersection between two DBVs are also proposed. Lookup table is used for fast computing the support (number of bits 1 in a DBV) of itemsets. Next, subsumption concept for memory and computing time saving will be discussed. Finally, an algorithm based on DBV and subsumption concept for mining frequent closed itemsets fast is proposed. We compare our method with CHARM, and recognize that the proposed algorithm is more efficient than CHARM in both the mining time and the memory usage.     

挖掘事务间频繁闭项集的高效率算法

事务间频繁项集将传统的单维事务内关联规则扩展到多维跨事务关联规则,但事务问频繁项集的数量随滑 动时同间窗口的增大而迅速增加.利用频繁闭项集的特点.提出事务间频繁闭项集的概念及其挖掘算法(FCITA).该算法采用分割和条件数据库技术,避免生成庞大的扩展数据库;利用扩展二进制形武压缩事务,从而提高支持度的计算效事.此外,动态排序和哈希表极大地减少了频繁闭项集的测试次数.仿真比较表明,FCITA算法具有较高的挖掘效率.     

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

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

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

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

频繁项集挖掘的研究与进展

挖掘频繁项集是许多数据挖掘任务中的关键问题,也是关联规则挖掘算法的核心,所以提高频繁项集的生成效率一直是近几年数据挖掘领域研究的热点之一,研究人员从不同的角度对算法进行改进以提高算法的效率。该文从频繁项集生成过程中解空间的类型、搜索方法和剪枝策略、数据库的表示方法、数据压缩技术等几个方面对频繁项集挖掘的基本策略进行了研究,对完全频繁项集挖掘、频繁闭项集挖掘和最大频繁项集挖掘的典型算法特别是最新算法进行了介绍和评述,并分析了各种算法的性能特点,指出其适于哪种类型的数据集。最后,对频繁项集挖掘算法的发展方向进行了初步的探讨。     

高维稀疏数据频繁项集挖掘算法的研究

传统挖掘算法不适用于挖掘高维稀疏数据集.提出了一种针对高维稀疏数据的频繁项集挖掘算法FIHS.FIHS引入了一种新的数据结构用来存储频繁项集,该结构不但可以减少存储空间,而且可以降低计数代价.该算法只需扫描一次数据集,通过优化连接剪枝操作避免产生非频繁的候选项集,基于K-频繁项集使用"与"、"或"操作产生K+1-频繁项...     

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

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