论文部分内容阅读
通过Web日志分析挖掘用户的行为模式和访问意图,广泛应用于网站的页面推荐和链接结构优化。随着日志数据规模的增长,日志分析的可扩展性技术研究成为日志分析的研究方向。频繁模式挖掘是日志分析的基础应用,本文侧重研究集合频繁模式和序列频繁模式挖掘的可扩展性技术方法,分别通过基于磁盘的MapReduce平台和基于内存的Spark平台实现海量日志频繁模式的并行挖据,解决日志数据的分割和并行挖掘的负载均衡,以及分布式环境下大规模候选数据的支持度计数等问题,具体研究内容包括:(1)针对Web日志数据预处理的关键阶段—事务识别,提出一种基于候选路径的事务识别算法,主要思想是用空间换时间,与基于用户访问树的算法相比,将对日志数据的两次遍历降为一次,节省了遍历用户访问树的时间开销。(2)研究基于压缩结构FP-Tree的日志集合频繁模式并行挖掘,提出一种近似负载均衡的并行FP-Growth算法,利用item的最大前缀路径长度的上界来衡量挖掘item的条件模式树的工作量,工作量的近似值用于负载分组,所有计算节点根据分组结果并行地进行数据库的划分。与完全负载均衡的并行FP-Growth算法相比,无需构建全局FP-Tree,消除了数据划分过程中的单点局限,兼顾了负载的计算分配和整个计算过程的负载均衡。(3)研究日志序列频繁模式的并行挖掘,提出一种基于Spark的并行AprioriAll算法。首先,迭代过程中的数据扫描可以直接在内存中的RDD上进行,不用去扫描硬盘。其次,计算过程中的中间结果也可以直接持久化到RDD,下一步的计算可以直接从内存中读取数据。最后,对于分布式环境下大规模候选数据的支持度计数问题,提出了基于reduce端join的数据划分方案。与基于MapReduce的并行AprioriAll算法相比,整个计算过程节省了大量的磁盘IO和数据Shuffle。(4)最后,通过实验验证,基于候选的事务识别方法可以有效应对大规模日志的事务识别,近似负载均衡的并行FP-Growth算法拥有比较好的性能优势,且稳定性更好,基于Spark的并行AprioriAll算法拥有更好的性能和扩展性。