论文部分内容阅读
关联规则作为数据挖掘研究中最活跃的研究问题之一,通过从数据中找到事务间的内在联系,提供给用户符合用户需求和兴趣的挖掘结果。关联规则挖掘可以处理来自各行各业的数据,在商业活动、科学研究、生物医疗等领域都有广泛的应用。在进行传统的关联规则挖掘时,首先需要根据项集出现频次得到频繁项集,然后根据规则置信度产生强关联规则；频繁项集挖掘只考虑项集的出现频次,忽略了各项本身的性质,所以出现频次不高但是具有价值的挖掘结果可能被丢失。为了克服这个缺点,基于效用的关联规则挖掘被提出。效用值用来衡量项的重要性,能够体现出项之间的差异。基于效用值的关联规则挖掘通过综合考虑项的频次和效用值,挖掘出更贴合用户需要的结果。传统的效用值会受到项集长度的影响,即项集长度越长,项集的效用值越大；为了消除这种影响,平均效用值和平均高效用项集挖掘算法被提出。目前存在的平均高效用项集挖掘算法往往需要多次扫描数据库或者产生大量的候选项集,会消耗大量的时间和空间。本文围绕着提高平均高效用项集挖掘的效率和数据流上的平均高效用项集挖掘展开研究,主要内容包括：针对现有的平均高效用项集挖掘算法需要产生候选项集这一问题,提出了新的平均高效用项集挖掘算法HAUI-Mine。该算法只需要扫描两次数据库,并且挖掘过程中不需要产生候选项集。还设计了一种新的数据结构HAUI-Tree,其中压缩存储事务数据库中的信息,通过递归构造条件模式树来挖掘平均高效用项集。实验结果表明,在数据集比较稠密或阈值比较小的情况下,HAUI-Mine算法的运行效率明显优于HAUP-Mine算法。提出了能够适用于数据流上的平均高效用项集挖掘的ITR-Mine算法。区别于传统事务数据库,数据流是无限的、按照一定顺序到达的流动的数据。因为数据流的特性,事务数据库中的挖掘算法不能直接对数据流进行实时、快速的挖掘。将ITR-Mine算法和滑动窗口技术相结合,可以用于挖掘数据流中的平均高效用项集。ITR-Tree算法只需要扫描窗口内数据一次,同时在挖掘过程中能够避免产生候选项集。在ITR-Mine算法中,用ITR-Tree这一新的数据结构存储项集信息；通过递归构造条件模式树的方法,从ITR-Tree上挖掘出当前窗口内数据中的平均高效用项集。窗口滑动时,窗口内数据进行更新,此时只需要部分修改ITR-Tree,比完全重构ITR-Tree更节约时间。