基于MFP方法的Web用户访问模式的模式发现

摘要：针对Web用户访问模式问题，采用最大频繁访问路径（MFP）方法可以挖掘出更有普遍意义的模式。给出一种新的用户访问模式树WUAPtree结构，并采用EOEM模型，综合考虑了页面拓扑结构及用户浏览路径等多个数据源，进一步提出了一种Web访问模式挖掘算法WUAPmine。该算法不用产生候选集和递归，只对事务数据库进行一次扫描，对WUAPtree结构进行深度优先遍历一次，就可从WUAPtree结构上直接查询出Web用户频繁访问模式。最后，从理论和实践上推导和验证了它的有效性和高效性。

关键词：Web用户访问模式；最大频繁访问路径方法；点击流

中图分类号：TP311.13

文献标识码：A

0引言

数据挖掘技术应用在点击流数据上可以挖掘出不同的路径游历模式。一个游历模式是事务中用户访问页面的集合。通过对网络使用记录的挖掘可以挖掘出不同类型的模式[1]，不同之处在于如何定义模式。不同类型的模式之间的差别主要体现在是否具有如下三个主要特点：

1) 是否允许重复网页引用（回退游历和刷新）；

2) 模式是仅由相邻的网页引用组成还是允许由非相邻的网页引用组成；

3) 模式是否是最大频繁模式。

例1网络管理员发现用户频繁地访问下列网页。也就是说，用户先访问页面A，其次访问页面B，然后，回退到页面A，最后访问页面C。基于上述的观察，网络管理员可以确定在页面B和C之间需要添加一条超级链接。

从例1可以看出，我们对网页引用的序列（即点击流）感兴趣，包括那些回退或刷新的游历（重复性）。回退或刷新的游历是指那些已经访问过的网页引用。同时，我们不仅仅是对访问过的网页集感兴趣，对相邻的网页引用也感兴趣（连续性）。

1不同类型游历模式的分析与比较

1.1不同类型游历模式的分析

1.1.1最大向前引用（Maximal Forward References）

文献[2,3]用最大向前引用切割事务，并提出两种算法Fullscan和Selectivescan来挖掘频繁出现的访问序列。

问题1首先，这将会丢失一些有用的信息。例如，例1中事务，向前引用的结果是和。这样就无法弄清楚是否应在B、C间增加一条超级链接；其次，随着网络拓扑结构的复杂，它的效率明显下降。因为向前引用越来越多，而内容引用就越来越少成为最大向前引用[4]，丢失的信息就越来越多。

问题2在候选集的产生过程中，没有考虑图结构，以至于产生的候选项与图游历不对应，产生大量多余无用的序列。虽然，hash技术可以剪掉很多候选项目，但它由于没有考虑到图结构，在候选集中没有去掉那些候选序列与图中的路径path不符的序列。例如，如果节点A和节点B之间没有弧连接，那么候选序列就应该被剪枝掉。

问题3这两种算法都不可避免地同所有的Apriori及其变体算法一样，承受两种沉重的代价：一个是产生大量的候选集，另一个是多次频繁扫描事务数据库和通过模式匹配来频繁检查一个很大的候选集合[5]。

1.1.2关联规则

关联规则可以发现哪些商品被顾客同时购买，分析顾客

的购买习惯，了解市场动态[6]，也可以用于网络日志的挖掘[7]。由于关联规则不考虑页面的重复和页面彼此之间的

顺序，势必丢失一部分有用的信息。例如，事务 应简单地看成{A, B, C}；其次，不支持网页的连续性，不便于预取和缓存；再次，找出频繁大项集后，还需根据频繁大项集和置信度找出规则。文献[5]中的FPgrowth算法不用产生候选集的方法挖掘关联规则问题，有效地解决了问题3，但却无法解决其他两个问题。

1.1.3序列模式

序列模式[8]也可以用于网络使用挖掘[9,10]。由于一个用户可能有很多的事务，因此序列模式可能是跨事务的，并且所访问的页面之间不需要彼此相邻。

文献[11]提出EOEM模型和相似路径的概念。路径相似度的概念主要是用于网页的聚类[12]。由于作者将路径相似度概念的用于挖掘用户访问模式问题，导致搜索空间增大，每条路径都要与其他路径进行相似度比较，算法运行时间随路径相似度近似线性增长，使得算法的可用性不好。同时它也无法避免问题3的困境。

文献[13]通过一个给定的简单不包括环的无权重的直接图办法，采用两种算法levelwise和nonlevelwise（类似AprioriAll）算法来挖掘访问模式。由于访问模式是从图游历的过程中来挖掘的，因此，模式本身也应和图游历相一致，有效地解决了问题2的影响。文献[13]提出了WAPtree结构和WAPmine算法来挖掘用户访问模式，有效地解决了问题3的影响。

序列模式是从用户的覆盖面角度出发来考虑频繁序列，在用户访问模式问题上具有片面性。因为它忽略了个人的贡献，不能有效地排除多用户单访问的影响；其次，这种方法不支持网页的连续性，不便于预取和缓存。

1.1.4频繁的Episodes（事件）

Episodes[14]也可以用于网络日志的挖掘[15]。该方法将网页与事件相对应，所有的网页以它们访问的时间戳排序，并且不需要进行用户标定。Episodes被定义成一个网页的偏序集[14]，在该集合上满足自反性、反对称性和传递性。这种方法不支持用户的标定，所以我们无法分析出哪些页面序列是多数用户频繁访问的。其次，它也同样将丢失一部分有用的信息，以及无法达到预取和缓存的目的。

1.1.5 最大频繁序列（Maximal Frequent Sequent，MFS）

文献[15]提出MFS概念，然后使用后缀树和OAT算法。这种方法是从个人的贡献的角度（点击率）出发来考虑频繁的序列，在用户访问模式问题上具有片面性，因为它忽略了用户的覆盖面，不能有效地排除单用户多访问的影响。

1.2不同类型的游历模式的比较

从表1的比较和分析看，在路径游历问题的研究上需要解决以下问题：

1）如何定义模式才能不丢失有用的信息？

2）采用何种类型游历模式才能挖掘出更具有普遍意义的模式，提高算法的精度，增加算法的可用性？

3）采用何种切割事务方法才能不丢失有用的信息？

4）采用何种数据结构以减少对事务数据库和所用的数据结构的扫描次数，同时又不增加时间和空间的开销，提高算法的效率？

5）如何构造一种便于查询的结构，不通过递归就可通过遍历该结构查找出频繁访问序列，提高算法的效率？

2最大频繁访问路径方法

2.1路径游历模式的构成

在模式发现方面，可根据挖掘目的，使用游历模式的三种特点的并集。因为正像例1所示：

1） 重复性。重复页面引用的出现本身有着重要的意义，可以在频繁的网页间建立链接。

2） 连续性。频繁的相邻网页引用预示着今后潜在的网页引用，故可用于预取和缓存。

3） 最大性。 最大频繁模式的最大特点主要是用于减少频繁模式的数目。

针对问题1挖掘的模式是三种特点的并集。

找出的模式应具有重复、连续和最大三个特点。这里并不是说那些不允许重复页面引用或非相邻的网页引用的模式不重要，而是通过使用这些特点，可以比那些不使用这些特点发现的模式具有更多的有用信息。

2.2MFP方法

基于长度和基于用户数这两种支持度约束下，挖掘频繁访问的最大序列的方法称为最大频繁访问路径方法（Maximal Frequent Path，MFP）[1]。

针对问题2采用MFP方法挖掘路径游历模式。

MFS方法以点击率作为兴趣度的度量标准，将支持度定义为supL＝freq(X)/ #clicks，即supL＝freq(X)/ #len(D)。这说明作者从个人贡献的角度出发，不考虑用户覆盖面。也就是说，不论是谁，只要点击就对网站有贡献。显然，这种方法不能有效地避免单用户多访问的影响。例如，某广告公司在某网站上广告，1次点击广告公司将付给站点1元钱。据调查共有20000次点击，其中，有10000次是站点内部工作人员所为，而另10B000次点击才是有用的价值。

序列模式以用户的百分比作为网页吸引力的度量标准，将支持度定义：supC＝freq(X)/ #customers，这说明它考虑用户的覆盖面，忽略了个人贡献。也就是说，不管你访问多少次，只计数1次。显然，这种方法不能有效地避免多用户单访问的影响。例如，情况1，若有10个用户对某一页面分别访问1次；情况2，有5个用户对某一页面分别访问2次。两种情况中显然情况2对站点的贡献大，才是有用的价值，因为有可能情况1的10个用户以后不会再访问该网站的这个页面。

所以本文采用MFP方法，设置两种支持度约束，有效地解决了上述问题。找出的频繁模式集为二者的交集，是更具有普遍意义的模式，从而可以提高挖掘算法的精度、增加算法的可用性。

2.3事务的标定

从原始的网络日志中可以提取出事务构建事务数据库， 从事务数据库中可以挖掘出用户频繁访问的游历模式。选取研究工作需要的事务标定方法十分关键。采用何种事务标定的方法才能适合工作需要？即挖掘出的模式应具有重复、连续和最大的特点。

针对问题3采用引用长度方法；采用其他两种方法都会丢失有用的信息[4]。

时间窗口方法不支持对内容网页和辅助网页的划分，故不能分别创建两个事务集（内容引用事务集和辅助材谌菀用事务集），也就不能对二者分别挖掘，无法在内容网页之间添加超级链接，也就无法为用户找到尽快到达访问频率较高的页面的最近路径。采用最大向前引用方法，它的效率随着站点网络拓扑结构的复杂呈下降趋势。因为向前引用越来越多，内容引用所占比例就越来越小[4]。它将内容引用分成若干事务成为若干个最大向前引用，内容引用所占的比例相对就减少了。其次，这种方法还将丢失一些有用的信息。

引用长度的办法可以挖掘出所有用户频繁访问的内容网页序列，这是一项极其有意义的工作。因为内容网页本身与其他类型网页相比更具意义，用内容网页构成事务集，在挖掘出的频繁访问的内容网页之间建立超级链接意义更为巨大。

2.4WUAPtree结构

2.4.1基本数据结构――后缀树

trie结构[13]、FPtree结构[10]和WAPtree结构[15]，需要对事务数据库扫描两次并对递归构建所用结构，同时它的时间和空间的开销很大，因为它的节点需要记录大量的关键码，而不是关键码的指针。

采用何种数据结构才能满足工作需要（找到的游历模式具有三种特点），同时又不增加时间和空间的开销，提高算法的效率呢？采用上述文献的结构显然不行，首先，模式不具有三种特点；其次，时间和空间的开销很大。

针对问题4采用后缀树结构来减少对事务数据库和后缀树扫描次数，同时又不增加时间和空间的开销，提高算法的效率。

后缀树是在节点中存储指针，而不再像相关文献的模式树那样存储关键码，而是存储指向关键码起始位置和长度的指针。只有采用后缀树结构才能满足工作需要，才能减少时间和空间的开销，挖掘出的模式才具有重复、连续和最大三个特点。

2.4.2WUAPtree结构的构造

文献[15]提出OAT模式挖掘算法，利用后缀树结构挖掘最大频繁序列。但文献采用递归方法，需对事务数据库扫描两次，对后缀树深度优先遍历两次。如何构造一种便于查询的结构，不通过递归方法就可在该结构上深度优先遍历直接查找出频繁访问序列，提高算法的效率？

针对问题5本文对基本数据结构加以改进，提出一种新的数据结构WUAPtree (Web User Access Patterntree)结构，该结构是一种“具有用户标识数目和共享前缀序列计数”的后缀树。

其中：用户标识数目指的是浏览到该页面为止，用户访问该条路径的用户数目，即有多少用户访问了该条路径。共享前缀序列计数是指浏览到该页面为止该条路径被访问的数目，即该条路径被点击的数量为多少。

这种改进后的数据结构便于查询，因为它具有用户的标识数目和共享前缀计数，所以它不需要通过递归方法，可深度优先遍历该结构后根据用户数目与共享前缀序列数目直接查找出最大频繁访问序列，这样就进一步减少对事务数据库和所用数据结构的扫描次数（只需要对事务数据库进行一次扫描，对WUAPtree进行深度优先遍历一次），从而提高了算法的效率。

1）构造WUAPtree结构的前期工作

首先，根据原始日志文件对EOEM模型进行游历，并对原始日志数据进行预处理，并加载所需的信息。其次，将预处理后的事务放入事务数据库。

2）构造WUAPtree结构

每一个WUAPtree树节点记录了四种信息：起始位置、长度、共享前缀计数和访问的用户数目。分别是begin（label）域、length域、count域和User_num域，记作begin(label): length: count: User_num。其中：

begin域值表示的是节点的开始位置（即网页组成的字符串的开始位置）；在非压缩折叠的WUAPtree树结构中也可表示成label(即网页的标识)。

length域表示的是节点的长度；在非压缩折叠的WUAPtree树结构中其值为1，因为节点仅由一个网页组成，其长度为1。

count域表示的是该字符串被访问的次数（不区分同一用户的不同次访问）；

User_num域表示的是该节点被不同用户访问的次数（同一用户不同次访问这里只计数1次）。

3）构造WUAPtree结构

（1） 首先创建树的根节点，用“null”标记，树的根节点是一个空的虚节点，它的label(begin)域值、length域值、count域值和User_num域值记为0。

（2） 对D中的第一个事务（序列串）构建后缀树。

（3） 其次从D中选取第二个事务，将其添加到后缀树中。其中：

count域的计数原则共享前缀序列的节点计数加1，对于非共享的后缀创建新的分支，构成一个新的后缀树。这种共享可以带来很多优点：首先它可以节省一部分访问序列的存储空间；其次它便于计数任何含有前缀P的子序列的支持度sup。

User_num域的计数原则对于当前节点来说，若用户信息列表中没有，即为新用户，其用户计数加1；若用户信息列表中有，即旧用户，则用户计数不变。

（4） 依此类推，直至D中的所有事务添加完毕。

2.4.3WUAPmine算法

因为WUAPtree结构记录了四种信息：起始位置、长度、共享前缀计数、用户数目。根据给定的两个约束，最小支持度supL和supC，对WUAPtree结构进行深度优先遍历就可查找出最大频繁访问序列，而不必采用递归方法。

对WUAPtree作深度优先遍历一次就可以获得下面三组数据。

1） 仅考虑个人贡献而不考虑用户覆盖面的情况。这组数据实际上就是优化改进的OAT算法。

2） 仅考虑用户覆盖面而不考虑个人贡献的情况。这组数据实际上就是优化改进的考虑了重复性和连续性的特殊的WAPmine算法。

3） 既考虑个人贡献，又考虑用户覆盖面的情况。这组数据实际上就是MFP方法[1]。

从根节点开始遍历找到所有大于最小支持度约束的最大频繁访问路径，这样保证了挖掘出的路径都是频繁的路径。

2.4.4算法描述

算法1模式提取算法

3用户访问模式挖掘实验

为了对该方法的性能做出评估，本文采用了校园网真实的网络日志文件，在Pentium 450/256M RAM/Windows 2000环境下，采用MS SQL Server 2000作为后台数据库管理系统，TOMCAT, JSP（Java Application）作为前端开发工具，分别采用WAP―mine算法、OAT算法以及采用两种支持度约束的MFP方法进行实验。数据集的属性描述如下：事务的平均长度为10，用户数为10，supminL=0.001， supminC=0.4。数据集

的大小为0.1M～10M。

4结语

本文采用了最大频繁路径的方法，使挖掘出的模式更具有意义；采用具有用户标识数目和共享前缀计数的后缀树使挖掘出的模式具有重复、连续和最大三个特点；利用引用长度事务标定法来切割事务使其不丢失有用的信息；构造WUAPtree的查询结构，不产生候选集、无需递归操作，减少了对事务数据库和频繁模式树的扫描次数，只需对该结构进行一次深度优先遍历即可查找出用户频繁访问模式且不产生遗失和多余的最大频繁路径。WUAPmine算法继承了OAT算法的优点，支持在线自适应查询。也就是说，当对一年的日志文件事务数据库技能型挖掘的过程中，若想查询第一季度的挖掘的结果，就可以使其暂停，观看第一季度的查询结果，然后继续进行。采用后缀树结构的优势在于固定的索引集和层次索引，适用于在大的文本中进行快速地查询，使得挖掘算法具有较好的性能。