论文部分内容阅读
计算机和互联网技术的普及与快速发展使得数据的产生、收集、存储日益便捷，因而数据量呈爆炸式增长。但是信息过载，使得人们面对海量的数据往往无从下手。因此频繁模式挖掘被提出用于找出事物间的内在联系，并被广泛地应用于商品推荐、疾病诊断、入侵检测等方面。然而频繁模式仅关注模式在事务数据库中出现的频率，却忽略了构成模式的项本身所具有的权重值。因此高效用模式挖掘算法被提出，它综合考虑了构成模式的项的权重信息与频率间的关系，具有更高的实际意义。 但是，在挖掘高效用模式前需要用户设定最小效用阈值，而最小效用阈值的设定更多地依赖于用户的经验，对于经验不足的用户来说，不合适的阈值设置使挖掘结果千差万别。而且在实际应用中，人们更倾向于关注效用值最高的前k个模式。因此提出了Top-k高效用模式挖掘算法。在Top-k高效用模式挖掘中，仅需设定k值即可挖掘出效用值最高的k个模式，避免了经验在阈值设定中的主导作用，从而降低了高效用模式挖掘在应用中的准入门槛。 然而，目前Top-k高效用模式挖掘算法存在临时效用阈值上升速度慢、时间性能差、算法可扩展性差的问题。针对这些不足，本文提出了基于投影的Top-k高效用模式挖掘算法来解决这些问题，同时针对在海量数据下单机模式挖掘效率低的问题，提出了基于MapReduce的Top-k高效用模式挖掘分布式的解决方案。本文的主要工作如下: 1.提出了基于投影表结构的Top-k高效用模式挖掘算法TKHUP。该算法是一阶段的Top-k效用模式挖掘算法，采用投影表结构能直接读取效用值，并快速提升临时效用阈值，从而有效地挖掘出指定数量的高效用模式。 2.提出了基于MapReduce的分布式Top-k高效用模式挖掘算法TKHUP-MaR。本文通过研究和使用MapReduce并行技术，实现了在大数据场景下挖掘Top-k高效用模式的方法，从并行计算、并行构建存储结构、并行挖掘三个阶段来实现该并行算法。 3.设计了五个策略提高算法的挖掘效率。策略CSD能够极大地合并前缀模式相同的投影结构，从而节省更多的内存空间。策略QPPR通过前缀项数字和能够快速比较前缀模式是否相同，便于加快投影结构的生成。策略DS优先对效用值大的基模式进行挖掘，从而提高临时效用阈值的增长速度。策略DFP采用深度优先挖掘的方式，对正在处理的投影迭代地构建其子投影结构，能够快速提高临时效用阈值。策略DPUP利用事务权重向下闭包特性，排除为低效用模式构建子投影，加快挖掘的速度。 4.通过在稀疏数据集和稠密数据集下的实验对比，从运行时间和内存空间上证明了TKHUP算法性能优异。另外，通过在Hadoop平台下的实验结果验证了TKHUP-MaR算法的可行性和扩展性。