论文部分内容阅读
关联规则挖掘是一种在事务数据库中发现项目之间的特定关联关系的方法。它的目的是利用一些有趣性度量来识别事务数据库中发现的强规则,以便为决策者提供感兴趣的消息。关联规则挖掘在商业决策与推荐、科学研究、生物医疗等领域有广泛的应用。但是,传统的关联规则挖掘主要考虑挖掘基于“支持度-置信度”的频繁项集(FIM),过多强调了项集出现的频率,忽略了项之间的差异,因而很可能丢失了效用较高、但支持度较低的规则。引入了效用度量的关联规则挖掘——高效用项集挖掘则很好的克服了这个缺点。高效用项集挖掘用效用值来度量项集的有趣性,充分考虑项之间的差异性与频率,挖掘出更符合实际需求的结果。然而,在实际的应用中发现,长度较长的项集通常具有更大的效用,并且长项集通常是由个别效用较大的项贡献了大部分的效用。为了更客观地评价项集,均值高效用项集挖掘被提出。但是,现有的均值高效用项集挖掘算法要求用户拥有足够的背景知识与经验,来设置必要的最小效用阀值参数。本文主要研究Top-k均值高效用项集挖掘算法,以更加直观的项集数量参数代替最小效用阀值参数,解决了最小效用阀值难以设置的问题。文中还针对数据流系统逐渐增多的情况,提出了两种在数据流中挖掘均值高效用项集的高效算法。本文的主要研究有:(1)提出了一种高效的Top-k均值高效用项集挖掘算法TKAU。TKAU基于效用列表结构,将事务数据转换为列表结构,通过列表之间的递归交叉得到更长的项集的列表。该算法可以直接从列表获取效用,避免了多次扫描数据库。我们提出了两种剪枝策略,EMUP和EA,极大程度地减小搜索空间,减少了列表的交叉操作。并且根据Top-k项集挖掘问题的特点,设计了三种最小效用阀值提升策略RIU、CAD和EPBF,快速提升了最小效用阀值,避免了无效的搜索操作。(2)提出了两种能够在数据流环境下挖掘均值高效用项集的算法HAUIS-list和HAUIS-pd。HAUIS-list是将TKAU和滑动窗口模型相结合,加入了列表快速更新操作。而HAUIS-pd基于映射数据库的方式,利用事务映射与合并技术,不断减少所需扫描的事务数据库的大小,快速统计项集的均值效用。HAUIS-pd结合高效的剪枝策略,在时间和空间效率上表现优秀。