论文部分内容阅读
从树结构数据中查找内嵌模式是一个具有许多实际应用的重要研究问题,如电子商务、生物学、用户行为预测等.多年来,有很多算法被提出来解决这一问题.然而,这些算法几乎都集中于在单机上挖掘模式.鉴于数据集规模的激增,这些解决方案就显得效率低下或缺乏可行性.本文根据输入数据类型的不同,从两个方向研究基于MapReduce的分布式环境下频繁无序嵌入树模式的挖掘:事务型数据和单树型数据.本文提出了以事务型数据为输入的分布式频繁无序嵌入树模式挖掘算法TETPM.TETPM算法分为两个阶段:准备阶段找到所有频繁的标记;迭代阶段依次从规模为k的频繁模式中以两两模式连接的方式计算出新的规模为k+1的频繁模式,并在此过程中维护每个模式的实例列表,通过两两模式的实例列表连接计算新模式的支持度.针对TETPM算法我们根据数据粒度分别提出了负载均衡方式不同的两种算法:基于模式划分数据量的TETPM-P和基于模式实例划分的TETPM-E.并在后期的实验部分比较了两者的性能,实验结果表明两者都能处理单机算法不能解决的数据规模,且TETPM-E更适合规模更大的数据集,而TETPM-P更适合于频繁模式的实例数更均衡的数据集.本文提出了以单树型数据为输入的分布式频繁无序嵌入树模式挖掘算法EtpmLtd.EtpmLtd算法以迭代的方式运行,每一个迭代分为三个阶段:枚举候选模式阶段根据已知的规模为k的频繁模式中以两两模式连接的方式枚举出规模为k+1的候选模式;本地挖掘阶段计算出每个候选模式在本数据块的实例,并通过外部子孙阶段扩展策略保证不遗漏实例;全局统计阶段根据所有实例统计出全局的支持度.我们在EtpmLtd算法的基础上提出了两个优化策略以提升运行效率和降低通信消耗.后期的实验结果表明EtpmLtd算法能处理单机算法不能解决的数据规模,且优化策略能带来明显的性能提升.