Web日志频繁序列模式挖掘算法研究

摘要

Web日志频繁序列模式的挖掘是Web日志挖掘的重要组成部分，主要用来发掘站点和用户交互的频繁路径。利用这些频繁序列模式,可以简单的分析出用户的访问序列模式规律、进行建模以及对Web站点进行优化调整，以更好地满足用户访问需求来提升用户体验，进而增加访问用户数量，因而对形成智能化Web站点和个性化推荐有其特殊的意义。
　　针对Web日志频繁序列模式挖掘这一研究领域，目前已经提出一系列算法，比如GSP、Apriori、PSP、G序列、图形遍历、FreeSpan、PrefixSpan、Disc-all、MEMISP、MFS、LAPIN-SPAM、WAP-tree、PLWAP-tree和最近的NGCWAP-tree等。本文针对PLWAP-tree算法存在：1）当树的深度或者宽度超过计算机字长时，判断节点间的位置关系时需要多次移动指针，导致搜索空间挖掘过慢；2）重复遍历头表节点，因此消耗了更多的时间；3）需要更多内存空间来存储PLWAP-tree等缺陷，探索新的改进算法，主要研究内容及取得成果如下：
　　首先，在现有PLWAP-tree算法基础上，提出了一种存储空间更节省、时间效率也略有提升的改进算法PREWAP-tree。PREWAP-tree算法使用树状结构来存储Web访问序列，通过具有相同前子序列的序列共用路径节点来构建PREWAP树，基于前缀序列进行逐步挖掘，得到所有的频繁项集。在先序遍历PREWAP树构建头表的同时，记录当前节点的先序遍历序号和指向其最大先序遍历序号的后代节点的指针，结合节点的先序遍历次序和指向最大先序遍历次序的后代节点指针，来判断节点间的位置关系，遍历头表队列挖掘PREWAP-tree。
　　进而，在上述改进算法 PREWAP-tree基础上，提出了另一种改进算法BFWAP-tree。BFWAP-tree算法首先构建BFWAP树，使相同前缀子序列每重复出现一次时路径上的所有节点权值依次递加一。之后，在先序遍历BFWAP-tree建立头表的同时，记录每个节点所在的子分支序号，在挖掘过程中借助于节点所在分支序号判断其是否为首节点。该算法避免了使用位置码标识节点位置关系，在数据量规模较大的情况下，时间效率和空间节省方面都有更好改进。
　　最后，将本文提出的两种改进算法PREWAP-tree和BFWAP-tree与现有PLWAP-tree、WAP-tree和 NGCWAP-tree算法进行了对比实验和结果分析。分别在一定支持度和不同数据量下以及一定数据量和不同支持度下，对各个算法的时间消耗和内存消耗进行对比和分析，验证了本文提出算法的有效性，准确性以及两种算法在时间和空间上的改进效果。