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

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

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

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

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

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

基于FP-Tree的最大频繁项目集挖掘及更新算法

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题,之前的很多研究都是采用Apriori类的候选项目集生成-检验方法.然而,候选项目集产生的代价是很高的,尤其是在存在大量强模式和/或长模式的时候.提出了一种快速的基于频繁模式树(FP-tree)的最大频繁项目集挖掘DMFIA(discover maximum frequent itemsets algorithm)及其更新算法UMFIA(update maximum frequent itemsets algorithm).算法UMFIA将充分利用以前的挖掘结果来减少在更新的数据库中发现新的最大频繁项目集的费用.     

基于OWSFP-Tree的最大频繁项目集挖掘算法

为了解决FP-Max算法挖掘最大频繁项目集时递归生成条件模式树和超集检验的问题,提出了基于单向有序FP-Tree的NCFP-Max算法.该算法在挖掘过程中采用预剪枝策略减少挖掘结点,利用单向有序FP-Tree避免每次存储当前挖掘出的频繁项目集之前都需要超集检验,利用项目表格避免递归生成条件模式树减少时空资源.实验结果表明,在事务条数多、项的数量大的情况下,NCFP-Max算法的挖掘时间比FP-Max算法缩短了50％左右.     

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

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

基于改进FP-Tree的最大频繁项集高效挖掘算法

基于FP-T ree的FP-M ax算法在挖掘最大频繁集时需多次递归建立条件模式树耗费大量存储空间,这大大降低了算法的挖掘效率。提出了一种基于改进FP-T ree的最大频繁集快速挖掘算法-FP-EM ax算法。该算法无需建立条件模式库大大减少了存储空间开销,采用预剪枝策略减少条件模式树的构造次数及子集检测次数,从而算法的挖掘效率大大提高。最后通过实验证明FP-EM ax算法在支持度较小的情况下较之于FP-M ax及同类算法具有更好的性能。     

快速挖掘频繁项目集算法

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

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

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

基于COFI-Tree的N-最有兴趣项目集挖掘算法

BOMO算法采用递归构造条件子树,在挖掘大数据集时耗时较长,执行效率低,为了解决这一不足,文中给出一种基于COFI-Tree的挖掘N-最有兴趣项目集算法。算法采用COFI-Tree结构,无需递归构造条件子树FP-Tree,在同一时间内只有一个COFI-Tree在内存,并且有效地减少了其运算时间。通过对两种算法进行对比分析,实验结果得出：该算法比BOMO算法程序执行时间明显缩短;在挖掘大数据集时执行效率显著提高,尤其是k〈4时,性能最好。由此可见,改进后的算法是可行有效的。     

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

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

基于频繁闭项集挖掘的增量式维护算法

为了能够随着数据库的增加、删除和修改而快速有效地挖掘出频繁闭项集,根据CHARM算法提出了一种基于频繁闭项集挖掘的增量式维护算法。该算法采取分类处理的策略对变化数据进行挖掘,运用IT对的特性从已挖掘出的结果中快速过滤出仍然有效的信息,实现频繁闭项集的更新。实验结果表明该算法是快速有效的。     

基于标记域FP-Tree快速挖掘最大频繁项集

现有最大频繁项集挖掘算法,大多需要维护大量侯选项集并进行超集检测.当已有最大频繁项集数目较大时,超集检测将成为算法的瓶颈.提出了一种基于FP-Tree的快速挖掘最大频繁项集算法BF_DMFI(based on FP-Tree for discovering maximum frequent itemsets algorithm).该算法为FP-Tree中每个节点增加一个标记域,利用该域对节点进行有效的标记,从而减少了最大侯选频繁项集的数量,节约了超集检测时间,在一定程度上提高了算法的效率.     

基于不确定性数据的频繁闭项集挖掘算法

对于不确定性数据,传统判断项集是否频繁的方法并不能准确表达项集的频繁性,同样对于大型数据,频繁项集显得庞大和冗余。针对上述不足,在水平挖掘算法Apriori的基础上,提出一种基于不确定性数据的频繁闭项集挖掘算法UFCIM。利用置信度概率表达项集频繁的准确性,置信度越高,项集为频繁的准确性也越高,且由于频繁闭项集是频繁项集的一种无损压缩表示,因此利用压缩形式的频繁闭项集替代庞大的频繁项集。实验结果表明,该算法能够快速地挖掘出不确定性数据中的频繁闭项集,在减少项集冗余的同时保证项集的准确性和完整性。     

基于频繁模式树的频繁连通闭图集挖掘算法

随着频繁模式挖掘的深入研究,图模型被广泛地应用于为各种事务建模,因此图挖掘的研究显得越来越重要.文中针对唯一标识的有向连通图模型,基于频繁模式树结构,改进了频繁模式增长算法挖掘频繁连通闭合子图.使用生物代谢路径数据集的实验证明,这种算法能有效地挖掘出唯一标识的有向连通图集中的频繁闭图集,一次运算可以挖掘出多个阈值的最大频繁子图集.这种算法适用于以唯一标识的有向连通图建模的网络或图集,可以应用到基于图简化模型的生物网络的子图挖掘任务中.