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

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

挖掘最大频繁模式的新方法

由于其内在的计算复杂性，挖掘密集型数据集的频繁模式完全集非常困难，解决方案之一是挖掘最大频繁模式集．该文在频繁模式完全集挖掘算法Opportune Project基础上，提出了挖掘最大频繁模式的新算法MOP．它采用宽度与深度优先相结合的混合搜索策略，能恰当地选择不同的支持集表示和投影方法，将闭合性剪裁和一般性剪裁相结合，并适时前窥，实现搜索与剪裁效率最优化．实验表明，MOP效率是MaxMiner的2～8倍，比MAFIA高2个数量级以上．     

在FP-树中挖掘频繁模式而不生成条件FP-树

FP-growth算法是目前已发表的最有效的频繁模式挖掘算法之一．然而，由于在挖掘频繁模式时需要递归地生成大量的条件FP-树，其时空效率仍然不够高．改进了FP-树结构，提出了一种基于被约束子树挖掘频繁项集的有效算法．改进的FP-树是单向的，每个结点只保留指向父结点的指针，这大约节省了三分之一的树空间．通过引入被约束子树(可以用3个很小的数组表示)，算法在挖掘频繁模式时不生成条件FP-树，从而大大提高了频繁模式挖掘的时空效率．实验表明，与FP-growth算法相比，算法的挖掘速度提高了1倍以上，而所需的存储空间减少了一半．此外，随着数据库规模的增大，算法具有很好的可伸缩性．对于稠密数据集，算法也具有良好的性能．     

个性化书目推荐系统中的一个改进算法-FP_MAXMN算法

用挖掘最大频繁模式集代替挖掘频繁模式集是近年提出的一个新策略。本文主要是通过对基于FP_Tree的最大频繁模式挖掘问题的研究。根据频繁模式树的共享特性和最大频繁模式的特性给出了基于自底向上分治策略,先挖掘候选最大频繁模式再判断子集的算法--FP_MAXMN算法。     

一种分布式全局频繁项集挖掘方法

提出一种基于频繁模式树与最大频繁项集的分布式全局频繁项集挖掘算法BFM-MGFIS,该算法引入子集枚举树以实现有序挖掘与全局剪枝策略,有效地减小了候选数据集且提高了并行性,实验表明本文提出的算法是有效可行的。     

基于B-list的最大频繁项集挖掘算法

针对现有的最大频繁项集挖掘算法挖掘时间过长、内存消耗较大的问题,提出了一种基于构造链表B-list的最大频繁项集挖掘算法BMFI,该算法利用B-list数据结构来挖掘频繁项集并采用全序搜索树作为搜索空间,然后采用父等价剪枝技术来缩小搜索空间,最后再结合基于MFI-tree的投影策略实现超集检测来提高算法的效率。实验结果表明,BMFI算法在时间效率与空间效率方面均优于FPMAX算法与MFIN算法。该算法在稠密数据集与稀疏数据集中进行最大频繁项集挖掘时均有良好的效果。     

基于B-list的快速频繁模式挖掘算法

针对现有的频繁模式挖掘算法存在建树复杂、挖掘效率低等问题,提出一种基于构造链表（B-list）的频繁模式挖掘（BLFPM）算法。BLFPM使用一种新的数据结构B-list表示频繁项集,通过连接两个k-1-频繁项集的B-list可以快速得到k-项集的支持度,避免了多次扫描数据库;针对连接两个B-list时间复杂度高的问题,给出了一种线性时间复杂度的连接方法,提高了BLFPM的时间效率;同时,BLFPM采用集合枚举树代表搜索空间,并使用子集非频繁剪枝策略,减小了频繁模式挖掘的搜索空间,提高了算法的执行速度。实验结果表明,与NSFI算法和prepost算法相比,BLFPM的时间效率提高约12%到29%,空间效率提高约10%到24%,对稀疏数据库或稠密数据库进行频繁模式挖掘均可以得到良好的效果。     

利用编码的频繁导出式子树挖掘算法

针对频繁导出式子树的特点,给出一种基于编码的频繁导出式子树挖掘算法。该算法通过宽度优先编码来表示原始数据库,使单个投影的规模最小;通过对每个投影编码降低了整个投影库的规模,从而有效地提高了频繁导出式子树的挖掘效率。实验结果验证了该算法具有较高的挖掘效率。     

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

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

最大频集的挖掘方法

在对树生成的策略、模式支持集表示与投影、闭合性剪裁方法研究的基础上，提出了挖掘最大频繁集的两个新算法cap-max和op-max。cap-max是基于闭合频集的二阶段挖掘算法，先挖掘闭合频集，再从中求得最大频集；op-max是直接剪裁完全频集的算法，在频集生成过程中，通过前窥和包含关系检查及时剪裁搜索空间。实验表明，cap—max的时间效率比maxminer高1．5～4倍，op-cap的时间效率比maxminer高2～lO倍。     

基于FP-Tree有效挖掘最大频繁项集

最大频繁项集的挖掘过程中,在最小支持度较小的情况下,超集检测是算法的主要耗时操作.提出了最大频繁项集挖掘算法FPMFI(frequent pattern tree for maximal frequent item set)使用基于投影进行超集检测的机制,有效地缩减了超集检测的时间.另外,算法FPMFI通过删除FP子树(conditional frequent pattern tree)的冗余信息,有效地压缩了FP子树的规模,减少了遍历的开销.分析表明,算法FPMFI具有优越性.实验比较说明,在最小支持度较小时,算法FPMFI的性能优于同类算法1倍以上.     

频繁模式挖掘的约束算法

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

快速统一挖掘超团模式和极大超团模式

超团模式是一种新型的关联模式,这种模式所包含的项目相互间具有很高的亲密度.超团模式中某个项目在事务中的出现很强地暗示了模式中其他项目也会相应地出现.极大超团模式是一组超团模式更加紧凑的表示,可被用于多种应用.挖掘这两种模式的标准算法是完全不同的.提出一种基于FP-tree(frequent pattern tree)的快速挖掘算法——混合超团模式增长(hybrid hyperclique pattern growth,简称HHCP-growth),统一了两种模式的挖掘.算法采用递归挖掘方法,并应用多种有效的剪枝策略.提出并证明几个相关命题来说明剪枝策略的有效性和算法的正确性.实验结果表明,HHCP-growth算法相对于标准的超团模式挖掘算法和极大超团模式挖掘算法都具有更高的效率,尤其对于大数据集或在低支持度条件下更为显著.     

一种改进的基于FP-树的最大目标频繁项集挖掘算法

目前,基于FP-树的最大频繁项集挖掘算法存在的一个问题是FP-树的规模过大,遍历树需耗费大量的运行时间,并且挖掘出来的很多频繁项集是用户不感兴趣的,过多的无用频繁 模式影响了挖掘的效率。本文提出一种排序紧缩非冗余的STFP-树,以及基于STFP-树的最大目标频繁项集挖掘算法STFP-MAX。该算法在满足用户需求的基础上有效地缩小了FP--树的规模,又加快了搜索的速度,从而提高了挖掘的效率。     

连续时间区间内的频繁词序列挖掘算法

查询文本中频繁出现的短语可快速掌握文本内容,然而传统频繁词序列挖掘算法面向挖掘任务时的时间复杂度较高,无法满足频繁更换查询条件及快速获得反馈的查询需求。利用基于频率树的快速频繁词序列挖掘算法（TS_Mining）,在保持后缀树线性构造时间的情况下实现文本集合中频繁词序列的查询,并采用树型索引结构避免多次扫描文本集合,降低算法时间复杂度。针对连续时间区间内的频繁词序列查询问题,提出改进的剪枝挖掘算法（TS_Pruning）,通过减少频率树的扫描范围进一步提高挖掘效率。实验结果表明,TS_Mining与TS_Pruning算法的运行时间相比经典Apriori挖掘算法约减少了2个数量级,具有更高的频繁词序列挖掘效率。     

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

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

基于事务映射区间求交的高效频繁模式挖掘算法

关联规则挖掘是数据挖掘重要研究课题,大数据处理对关联规则挖掘算法效率提出了更高要求,而关联规则挖掘的最耗时的步骤是频繁模式挖掘。针对当前频繁模式挖掘算法效率不高的问题,结合Apriori算法和FP-growth算法,提出一种基于事务映射区间求交的频繁模式挖掘算法IITM（interval interaction and transaction mapping）,只需扫描数据集两次来生成FP树,然后扫描FP树将每个项的ID映射到区间中,通过区间求交来进行模式增长。该算法解决了Apriori算法需要多次扫描数据集,FP-growth算法需要迭代地生成条件FP树来进行模式增长而带来的效率下降的问题。在真实数据集上的实验显示,在不同的支持度下IITM算法都要要优于Apriori、FP-growth以及PIETM算法。     

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

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