基于Web日志挖掘的路径补充算法改进

邵天会

【摘要】 由于进行数据挖掘的Web日志来源不同，进行数据预处理时比较复杂，为了提高数据处理效率，结合网络拓扑结构对用户访问路径进行二叉树的转换，提出PFS（Path For Session）算法---消息路径优化。研究表明该算法解决了Web日志用户访问路径的补充问题，提高了数据预处理效率。

【关键词】 访问路径 PFS 消息路径优化

Web日志挖掘主要是针对用户浏览信息进行分析，因此用户会话的提取是首要任务。所谓的用户会话就是某个用户在某个时间段内请求页面的集合[1]。在识别用户会话过程中存在的一个问题是确定访问日志中是否有重要的请求没有被记录。路径补充保证了用户访问日志的完整性，从而保证Web日子挖掘的现实意义。

一、 路径补充原理

路径补充就是将由于本地或代理服务器缓存的影响而没有产生日志记录的请求页增加到用户会话中[2]。

得到用户会话之后，要根据用户会话得到访问路径。路径补充涉及定义如下：

定义：用户会话的路径集合 PS=…> ，其中，1≦k≦n，Resident 表示用户在该页面的停留时间[3]。算法输入为 RS，RS 中的记录是按 Rid 值分组按时间顺序排列的，输出为 PS，得到路径 PS 后，根据引用信息进行路径补充，如果一条记录的ReferUrl 不是上一条记录的 Url，则认为该用户是点击“后退”按钮访问了缓存中的页面，需要进行路径补充。

PS 中的记录是按 Rid 值分组顺序排列的；输出为：PS。

二、消息路径优化算法

2.1 消息路径优化算法原理

结合本文的研究目的和Web日志数据源针对路径补充的问题提出利用网络拓扑结构从用户访问序列获得用户访问事务数据的算法PFS（Path For Session）算法---消息路径优化，PFS算法是首先把网站的树形拓扑结构转换为二叉树的结构，然后在二叉树结构上根据用户的会话序列得到用户访问事务序列，PFS算法认为当前用户的访问序列中出现不连续的节点时，则用户可能点击了浏览器上的Back按钮或重复点击一个链接，当出现这种情况时，表明用户在点击Back按钮或重复点击链接时就结束了上次会话，重新开始了新一轮的会话。

2.2 消息路径优化算法的实现

当前会话页面分别为：A，C，D，I，对应的请求页面分别为F，H，C，J。

这次会话的序列是：A--F--C--H--D--C--I--J使用路径补充技术：A--B--F--B--A--C--H--C--A--D--A--I--D--J再利用最大向前引用路径算法得出用户的访问事务为A--B--F，A--C--H，A--D--I--J，三个事务。在此过程中，必须对用户的访问序列进行补充得到完整的路径后再应用最大向前应用路径才能得到访问事务。利用PFS算法转换为二叉树。

由此，不再需要对访问序列补充路径便可由用户访问序列直接获得用户的访问事务A--B--F，A--C--H，A--D--I--J。

三、算法改进对比

用户访问会话使用路径补充和PFS算法得到用户访问事务的时间进行对比，此对比是假设网站的结点链接已经由图结构转换为树形结构，且树形结构的拥有25个叶结点，树的深度为分别为3，4，5，6时进行的。

实验证明该算法在相同的路径深度前提下，减少了Web日志数据预处理的时间，提高了效率。

四、结论

PFS算法改进了数据预处理阶段的路径补充步骤，从整体上提高了数据挖掘效率，但是算法基于网络拓扑结构，随着网站的页面大量增加，网络拓扑结构也随之复杂，算法的复杂度同时增大，所以PFS算法对网络拓扑结构复杂的网站需要更多的研究，以适应复杂的网络拓扑结构。

参 考 文 献

[1] 何坤鹏，郭海波.Web 日志挖掘技术及其应用研究[J]，中国科技信息，2007-08-15：236-237.

[2] 刘明吉，王秀峰，黄亚楼.数据挖掘中的数据预处理[J]计算机科学，2000-04-15：3-9.

[3] E.F.Codd，S.B.Codd and C.T.Salley.Providing OLAP to User-Analysts：An IT Mandate.IBM Research Lab，Techni cal Report，1993.

[4] J.Qay，S.Chaudhuri，A.Bosworth，A.Layman，D.Reichart，M.Venkatrao，E Pellow，and H.Pirahesh.Data cube：A relational aggregation operatorgeneralizing group-by，cross-tab and sub-totals.Data Mining and Knowledge Discovery，1：29-54，1997.