论文部分内容阅读
关联规则最早是挖掘频繁项集,以支持度为度量,挖掘数据库中频繁出现的项集模式。考虑到数据库中每个项目在事务中可以出现多次,并且不同项目可以有不同的权重,频繁项集被扩展到高效用项集挖掘,高效用项集挖掘能使用用户期望的效用度量方式挖掘出更符合用户需求的结果。本文主要围绕关联规则中的频繁项集挖掘算法与高效用项集挖掘算法的时间效率提升展开,具体内容包括以下2个方面:1)基于事务约简和2-项集支持度矩阵快速剪枝的Apriori改进算法。首先自定义了保存频繁1-项集的数据结构,计算候选项集支持度时,依据这个自定义的数据结构决定扫描的事务,之后引入事务约简优化,进一步对数据库中项目和事务进行约简,提出改进的MR-Apriori算法。随后,定义一种2-项集支持度矩阵,对候选项集进行快速剪枝,提出了改进后的MP-Apriori算法。再次,结合MR-Apriori和MP-Apriori算法改进策略,提出了改进的MRP-Apriori算法。最后,在mushroom和T10I4D100K进行实验,结果表明:改进的MRApriori算法和改进的MP-Apriori算法,运行时间都比原Apriori算法减少,而结合这两种改进策略的MRP-Apriori算法运行时间最短,从而最终验证了三种算法改进的时间效率。2)基于数组伪投影和事务合并的频繁高效用项集挖掘算法。在分析了单独考虑支持度或效用值的缺陷后,本文提出一种基于数组伪投影数据结构、递归构造前缀项集的投影数据库挖掘频繁高效用项集的算法。算法将支持度和效用值这两种度量手段同时考虑,挖掘数据库中那些出现次数频繁且效用值高的项目集合。为减小算法的搜索空间,提出了局部效用剪枝和子树效用剪枝两种剪枝方案,基于算法模型和上述剪枝方案提出FUIM-P算法。随后,观察到数据库中有许多可以合并的事务,根据FUIM-P算法的特点,将这种合并被扩展到投影数据库,引入了事务(投影事务)合并技术。同时,提出了一种自定义排序规则,以在线性时间内找到满足可以快速合并的条件的事务,提出最终的FUIM-MP算法。最后在mushroom、chess和accident数据集上进行实验,结果表明:FUIM-P算法的运行时间相比对比的FHIMA-ALL算法缩短,而加入了事务(投影事务)合并技术的FUIM-MP算法则较前两者时间效率有非常大的提升;另外,实验中mushroom、chess和accident数据集中大量可合并事务(投影事务)数目也很好地证明了事务(投影事务)合并提高算法运行时间的有效性。