论文部分内容阅读
高效用项集挖掘(High Utility Itemsets Mining,HUIM)是近年来数据挖掘领域中研究的热点问题之一,它解决了传统的频繁项集挖掘(Frequent Itemsets Mining,FIM)中只考虑项集的出现频率,而不考虑项的数量和单位效用的问题。但是,大多数高效用项集挖掘算法都采用单一效用阈值约束,而没有考虑项之间的差异,这在现实生活中是不适当的和不公平的。因此,采用多最小效用阈值挖掘高效用项集应运而生,本文主要针对多最小效用阈值挖掘算法中存在的不足做出改进。另外,众所周知,高效用项集挖掘和频繁项集挖掘在数据挖掘领域都有着非常重要的意义。但是现有的大多数研究算法要么使用支持度约束来挖掘频繁项集,要么使用效用约束来挖掘高效用项集。然而单独考虑这两种约束都有各自的局限性,比如支持度很高的项集其效用不一定高,同样效用很高的项集其支持度也不一定高。本文针对以上两个方面存在的问题主要做了以下工作:(1)对频繁项集挖掘和高效用项集挖掘的研究现状进行描述,分析已有的频繁项集挖掘算法和高效用项集挖掘算法,并对其优点和不足进行总结。(2)分析现有的多最小效用阈值挖掘算法,针对多最小效用阈值高效用项集挖掘算法(MHUI算法)中出现的重复计算、挖掘的结果项集不是频繁项集的问题,提出两个新的快速挖掘算法FMHUI算法和SFMHUI算法。其中,FMHUI算法在计算项集的最小效用阈值时利用前一次计算结果,避免了项之间的重复比较;另外定义了项的扩展项的最小效用阈值表EMMU-table快速计算出扩展项的最小效用阈值,提高了运行效率。SFMHUI算法在FMHUI算法的基础上增加了支持度约束,使挖掘的项集既是高效用的也是频繁的。这两个算法结合4个剪枝性质来剪枝搜索空间,提高挖掘效率。最后通过仿真实验验证了FMHUI算法比最新的多最小效用阈值挖掘算法MHUI算法具有更高的挖掘效率,并验证了SFMHU算法的有效性和可行性。(3)现实生活中,很多物品都是需要进行分类处理的,而现有的高效用项集挖掘算法对从这类数据库中挖掘高效用项集都不太合适。采用单一效用阈值的挖掘算法,没有考虑项之间的差异,这在实际生活中是不适当和不公平的。而采用多最小效用阈值挖掘算法,对每个项都赋一个最小效用阈值,当数据库中的项非常多但项的种类又很少时,这时如果再对每一个项都进行赋值,显然是不合适的。针对这一问题,本文提出基于同类项的多最小效用阈值挖掘算法CMFHUI。CMFHUI算法通过对每一类赋一个最小效用阈值来挖掘高效用项集,并在此基础加上支持度约束,进一步使挖掘的高效用项集又是频繁项集。然后又提出一个改进算法CMFHUI+来进一步提高挖掘效率。最后通过在公共数据库中进行仿真实验,验证了这两个算法的有效性和可行性。总体来说,本文结合了频繁项集挖掘、多最小效用阈值的高效用项集挖掘等理论,提出了改进的算法,并通过仿真实验得到了验证。