论文部分内容阅读
数据挖掘是指从大量数据中提取或“挖掘”知识。关联规则是数据挖掘当前研究的主要模式之一,用于确定数据集中不同域或属性之间的联系,找出有价值的多个域之间的依赖关系。发现频繁项集是关联规则挖掘中最基本、最重要的问题,自从Agrawal的开创性工作以来,有关研究从未停止过。当支持度阈值较低或数据集中存在长模式时,频繁项集挖掘可能产生大量频繁模式集,这将给人们的理解和从中发现有趣的模式造成一定的困难。为压缩庞大的频繁模式集,压缩的频繁项集挖掘是最近研究的一个热点问题,其中包括最大频繁项集挖掘和频繁闭项集挖掘。现有最大频繁项集挖掘算法,大多需要维护大量侯选项集并进行超集检测。当已有最大频繁项集数目较大时,超集检测将成为算法的瓶颈。本文首先提出了一种基于标记域FP-Tree的快速挖掘最大频繁项集算法BF-DMFI,该算法为FP-Tree中每个节点增加一个标记域,利用该域对节点进行有效的标记,从而减少了最大侯选频繁项集的数量,节约了超集检测时间,在一定程度上提高了算法的性能。按照搜索空间树的遍历策略,最大频繁项集挖掘算法分为宽度优先算法和深度优先算法。宽度优先算法大多需要维护大量候选项集并多次重复扫描数据库或搜索FP-Tree;而深度优先算法则需要递归构造频繁项的条件模式树并进行相应挖掘,这将加大算法的执行时间和所占用的内存空间。提出了一种基于FP-Tree的非递归深度优先挖掘算法DF-DMFI。该算法通过构造每个频繁节点的频繁子孙集和频繁前缀,连接生成最大频繁项集,利用MFI-Tree进行超集检测,并对FP-Tree进行有效的剪枝,从而保证了算法的执行效率。现有最大频繁项集和频繁闭项集挖掘算法,大多从事务数据库中直接挖掘,具有较高的时间和空间复杂度。提出了基于频繁项集的最大频繁项集(BFI-DMFI)和频繁闭项集挖掘算法(BFI-DCFI)。在BFI-DMFI算法中,通过逐个检测频繁项集在其集合中是否存在超集来判断该项集是不是最大频繁项集;在BFI-DCFI算法中,通过挖掘所有支持度相等的频繁项集中的最大频繁项集,组合生成频繁闭项集。利用此方法挖掘最大频繁项集和频繁闭项集在一定程度上降低了算法的时间和空间复杂度。在上述研究的基础上,本文最后设计并实现了一个关联规则挖掘工具原型。该原型可以挖掘出基于频繁项集、频繁闭项集和最大频繁项集的关联规则,并可根据用户自定义的规则进行约束挖掘,以进一步精简关联规则结果集。