论文部分内容阅读
频繁序列模式的挖掘长久以来就被广泛地应用到各种实际场景中为商家或企业提供各种生产销售方面的决策支持。而随着科学技术的发展,数据获取和存储能力的不断加强,各种实际场景中需要进行频繁序列模式挖掘的数据也经历了爆炸式的增长并最终达到了海量。海量的数据能得到更多频繁序列信息,但传统频繁序列挖掘算法在对海量数据进行挖掘时,其效率已经远远不能满足实际场景中的效率需求。不仅如此,实际场景中的数据集中的各元素通常并不是扁平化的,其自身通常拥有若干的类别信息,所有元素的类别信息能够组合为层级树。传统的频繁序列挖掘算法只能针对数据集中存在的元素挖掘出只包含这些元素的频繁序列模式。借助层级树来进行频繁序列的挖掘,我们能够得到传统算法不能挖掘到的更具一般性的频繁序列。已有的基于层级树在海量数据下进行频繁序列挖掘的算法还有很大的挖掘效率提升空间。同时,在基于层级树进行频繁序列挖掘时,其挖掘结果存在冗余的问题,已有部分研究提到该问题,但它们都没有对冗余结果做精确的定义,也并没有给出解决方法。此外,在挖掘频繁序列模式的时候,特别是在基于层级树对海量数据进行挖掘时,其挖掘到的结果序列会极其多,而用户感兴趣的可能只是其中的一部分符合特定模式的序列。因此我们需要在挖掘时对结果序列给出若干形式的约束,如最大间隔约束、最大序列长度约束、正则表达式约束等。正则表达式约束能够使算法只挖掘出涉及特定内容的结果序列。但目前还没有将正则表达式约束结合到海量数据下基于层级树的分布式频繁序列挖掘算法中的研究。本文提出了框架RUMMAGE来解决上述问题。RUMMAGE分为预处理、Map、Reduce、Cleanup四个阶段。本文在Map阶段基于LASH的投影算法提出更高效的投影算法PUT;在Reduce阶段,首先基于PSM算法提出不含冗余操作的算法MINE,接着定义了适用于层级树的正则表达式RE-Hierarchy,并提出算法REC-MINE以接受正则表达式约束在海量数据下基于层级树进行频繁序列挖掘;最后,在Cleanup阶段提出了算法REI以高效解决挖掘结果冗余的问题,极大地减少了结果序列的数量。