论文部分内容阅读
关联规则作为数据挖掘的重要研究领域之一,主要解决的是数据之间的关联和许多其他有趣的模式。最大频繁项集挖掘算法作为关联规则算法中的一类经典算法,包含了所有的频繁项集的信息,而且某些数据挖掘应用仅需挖掘最大频繁项集。因此挖掘最大频繁项集具有十分重要的意义。但是经典的最大频繁项集挖掘算法存在一些问题：递归地产生大量条件频繁模式树；每次存储当前挖掘出的频繁项集之前都需要超集检验；更新数据库后需要重新运行挖掘算法。本文在广泛查阅国内外关联规则挖掘算法基础上,针对算法的空间效率和时间效率,提出了三方面的改进,并通过实验验证。本文的主要研究内容如下：(1)提出了单向有序的FP-Tree (OWSFP-Tree)。主要研究了OWSFP-Tree的性质、构建流程以及构造实例。另外,通过和传统的FP-Tree比较,我们可以发现该树具有以下优点：a)节约了空间资源；b)减少了算法递归的次数；c)为避免每次存储当前挖掘出的频繁项集之前都需要超集检验提供基础。(2)提出了基于OWSFP-Tree和项目表格的最大频繁项集挖掘算法(NCFP-Max算法)。主要研究了NCFP-Max算法的性质、策略、算法流程以及算法实例。通过实验验证在相同的环境下NCFP-Max算法的挖掘时间比FP-Max算法减少了50%左右。(3)提出了基于降维的最大频繁项集增量式更新算法。主要针对的是偶然问向事务数据库中增加新的数据集时,如何利用已经生成的最大频繁项集和OWSFP-Tree产生新的最大频繁项集。提出了基于降维的最大频繁项集的增量式更新算法的性质、算法过程以及算法实例,通过实验证明当事务数据库增加新的数据集时(新增加的数据集小于原事务数据集),基于降维的最大频繁项集增量式更新算法的挖掘时间要优于FP-Max和NCFP-Max算法。最后,论文对所做工作进行了总结,并提出了未来的研究方向。