近年来,随着internet的飞速发展,电子商务网站的增多,积累了大量的web日志数据,如何从这些海量的日志文件里找到用户访问站点的行为习惯和兴趣爱好,已成为了web日志挖掘的研究热点。Web频繁序列模式挖掘是web日志挖掘的一个重要研究分支,它挖掘用户访问web站点的频繁页面和频繁路径,挖掘这些有趣的模式对于网站调整组织结构以适应用户的访问习惯是很重要的。在这个竞争激烈的电子商务环境中,优化网站的组织结构也是吸引和挽留用户的重要手段。挖掘这些有趣模式还可以为用户提供个性化服务,推荐他们可能喜欢的商品。此外,在挖掘的频繁路径上投放广告可以使更多的用户访问到广告。因此,web频繁序列模式挖掘的研究对于电商网站的发展是非常重要的。本文的主要研究内容和成果如下:①在PLWAP算法的基础上,研究提出了一种在空间复杂度方面改善较明显的算法RLDWAP。为避免经典的WAP算法需要递归构建大量条件树这一缺陷,PLWAP算法使用位置码来判断两个节点在树中的位置关系,在树中每个节点的父节点位置码之后附加1作为当前节点的位置码,在最近的左兄弟节点的位置码之后附加上0作为其右兄弟节点的位置码,因此当树的深度或宽度很高时,该位置码会变得很长,存储每个节点的位置码需要消耗更多的空间,读取位置码需要遍历指针。针对该问题,在PLWAP算法的基础上提出了RLDWAP改进算法,该算法采用RLD遍历(右子树-左子树-根的遍历次序)WAP-Tree,并在遍历的同时记录下当前节点的最后一个子孙节点,使用RLD遍历序号和当前节点的最后一个子孙节点的遍历序号就可以判断两个节点在树中的关系,以此减少存储每个节点的空间和判断两个节点位置关系的时间。②为适应不同应用需要,在PLWAP算法的基础上,研究提出了另一种在时间复杂度方面改善较明显的算法BCWAP。分析PLWAP的头表构造过程可以发现,其在每次递归挖掘过程中保持不变,并且头表是将表里的每个项集与其在树中标识相同的所有节点连接为一个队列,每次在后缀树中寻找项集的首节点时,都需要从队列的第一个节点开始遍历,对后缀树以上的节点判断是没有必要的。针对该问题,结合RLD遍历序号标识节点的位置关系,BCWAP改进算法通过在每次递归挖掘过程中重新构造后缀树的头表,并且只将头表中的每个项集与其在树中对应的首节点连接为一个队列,减少了在当前频繁序列的后缀树中寻找首节点的时间。由于需要在每次递归过程中构造头表,BCWAP在空间方面的性能介于PLWAP和WAP之间。③对改进算法进行了性能分析和实验论证。通过将改进算法与PLWAP、WAP和NGCWAP算法进行了实验对比和结果分析,分别从时间复杂度方面和空间复杂度方面,验证了两种改进算法的准确性和有效性。