基于效用表的快速高平均效用挖掘算法.docVIP

基于效用表的快速高平均效用挖掘算法 　　摘 要：高效用项集挖掘在数据挖掘领域中受到了广泛的关注，但是高效用项集挖掘并没有考虑项集长度对效用值的影响，所以高平均效用项集挖掘被提出；而目前的一些高平均效用项集挖掘算法需要耗费大量的时间才能挖掘出有效的高平均效用项集。针对此问题，给出了一个高平均效用项集挖掘的改进算法――FHAUI。FHAUI算法将效用信息保存到效用列表中，通过效用列表的比较来挖掘出所有的高平均效用值，同时FHAUI算法还采用了一个二维矩阵来有效减少二项效用值的连接比较次数。最后将FHAUI算法在多个经典的数据集上测试。实验结果表明，FHAUI算法在效用列表的连接比较次数上有了极大的降低，同时其时间性能也有非常大提高。 　　关键词：平均效用；高效用；模式挖掘；数据挖掘；频繁模式 　　中图分类号：TP311.13 　　文献标志码：A 　　文章编号：1001-9081（2016）11-3062-05 　　0 引言 　　模式挖掘是数据挖掘中的一个重要领域，其中频繁模式挖掘是在事务数据库中找出出现频率比较高的项集，但频繁模式挖掘方法[1-4]仅考虑项是否在事务中出现，并没有考虑项在事务中出现的频率或者项的权重，而项的频率和项的权重往往在实际的推荐中具有非常重要的作用。 　　为了解决这个问题，大量的高效用项集挖掘算法被提出。这些高效用项集挖掘算法可分为一阶段算法[5-7]和二阶段算法[8-12]。高效用项集挖掘是指挖掘数据库中效用值高于用户指定阈值的项集。因为高效用项集挖掘算法综合地考虑了项在事务中出现的次数和项本身的权重，所以其在实际场景中具有更广泛的应用；然而高效用项集挖掘仅仅关注项集的效用值，而对项集长度影响效用值的情况并未探讨。一般来说项集的长度越长，其效用值就越大，因此用相同的阈值来衡量长度不同的项集不是很合理。 　　为了降低项集长度对效用值的影响，以及挖掘出高平均效用项集，Hong等[13]提出了平均效用项集挖掘方法TPAU（Two-Phase Average-Utility）。该方法通过项集效用值和项集的长度来计算项集的平均效用值，即数据库中某一项集的平均效用值是指其真实的效用值除以该项集所含项的个数。高平均效用项集是指项集的平均效用值高于用户指定阈值的项集。由于TPAU是层次计算需要多次扫描数据库，HAUP-Growth（High Average-Utility Pattern Growth）算法[14]被提出。HAUP-Growth是基于树结构的算法，只需要两次数据库扫描即可挖掘出所有的候选项集，但是HAUP-Growth属于二阶段算法，会产生大量的候选项集，所以一阶段算法PBAU（Projection-Based Average-Utility）[15]、HAUI-tree（High Average-Utility Itemsets tree）[16]、HAUI-Miner（High Average-Utility Itemsets Miner）[17]被提出，其中HAUI-Miner是目前已知最优高平均效用项集挖掘算法，它采用AU-list结构保存项集效用信息，然后通过AU-list连接比较挖掘出所有的高平均效用项集，实验表明其时空性能都是最优的。尽管AU-list非常有效，但是其高平均上界并不够紧凑，因此挖掘过程中需要进行大量的连接比较。 　　为此本文提出了一个改进的效用列表结构IAU-list（Improved Average-Utility list），该结构给出了一个更紧凑的高平均上界，它大幅度减少了效用列表比较和连接的过程；另外，依据快速的高效用项集挖掘（Faster High-Utility Itemset， FHM）提出的EUCS（Estimated Utility Co-occurrence Pruning）结构[9]给出了一个平均效用删减的二维矩阵EAUCS（Estimated Average Utility Co-occurrence Pruning），该矩阵可以有效减少二项集的比较过程。FHAUI也是一个一阶段算法，不需要产生候选项集。 　　算法1的第2）～4）行判断当前项集X的一个扩展项集Y是否为高平均效用项集，如果Y是高平均效用项集则将其添加到高平均效用项集表中。第5）～13）行通过sum（Y.rmu）判断项集Y是否可扩展，如果可扩展，将X扩展项集中排在Y之后的项集Z与Y进行连接生成Y的扩展项集。第12行同样地，处理Y的所有扩展项集。如此遍历下去直到找出所有的高平均效用项集。 　　算法1对项集的效用列表的比较连接是一个深度优先的处理过程。例如，图1中的项集按排序CBDA，因为初始项集为null，则C、B、D、A均为null的扩展。算法先处理C生成所