Web日志挖掘中的数据预处理研究

摘要：Web日志信息的预处理是Web日志挖掘任务中的重要阶段，是整个Web日志挖掘过程的基础和实施有效挖掘算法的前提，在Web日志挖掘中起着重要的作用，也是工作量较大的一部分。数据预处理的基本技术，包括数据清理、数据集成和转换、数据归约等。本文介绍了数据预处理中涉及到的数据清理、用户识别、会话识别、路径补充、事务识别等过程，并提出了一种路径补充算法。

关键词：Web日志；数据预处理；用户会话；路径补充；事务识别

中图分类号：TP311文献标志码：A 文章编号：1009-3044(2008)14-20789-03

1 引言

存在不完整、含噪声的和不一致的数据是大型的、现实世界数据库或者数据仓库的共同特点。不完整的数据的出现可能有多种原因，如收集不全，或者感兴趣的数据很难得到等。数据含有噪声（具有不正确的属性值）可能由于收集数据的设备出现故障，或者是数据传输中出现错误。在含有噪声的数据上进行数据挖掘可能得到错误的结果。因而在进行数据挖掘之前我们必须对数据进行预处理，以消除数据的不完整性、噪声和不一致性。数据预处理的过程见图1。

2 数据预处理步骤

2.1 数据清理

数据清理过程中试图填充空缺的值，识别孤立点、清除噪声，并纠正数据中的不一致性。由于Web服务器纪录了很多用户不关心的信息。数据清理阶段就是要删除Web日志中与挖掘目的不相关的数据和记录，为后面的用户会话识别和事务识别做好准备工作。

由于Web日志挖掘主要是对Web用户使用行为的研究，所以只有利用准确描述用户浏览行为的数据进行挖掘，才能发现正确的规则和模式。因为用户在发出html的请求时，会发出对包含在页面中的图片及音乐等次要元素的请求，而Web服务器都会为此做记录，所以数据清理阶段通过检查URL的后缀删除不相关的数据，把后缀名为GIF、JPEG、JPG、JPEG、JPG、SWF、CSS、JS和MAP的请求项删除。值得注意的是，当服务器对用户发出的请求响应失败时，Web日志同样会记录这种情况，但这对Web日志挖掘没有意义，可以采取在数据清理过程中通过检测日志中的状态码来删除服务器对请求失败的记录。

2.2 用户识别

用户识别的目的是要分辨出每个访问网站的用户，但由于本地缓存、防火墙还有服务器的存在使得过程变得复杂。解决的办法可以通过对用户行为进行跟踪，一般最常使用的技术是基于日志/站点的方法，并辅助一些启发式规则来识别用户，概括起来就是：若没有证据表明是不同的用户，就认为是同一用户。最常用的一个规则是：若访问用户的IP地址相同，但是相应的日志中如果显示访问用户的操作系统不同或者是浏览器类型不同，则认为他们来自不同的用户。另一个规则是：将用户的访问日志、引用日志和站点的拓扑结构结合起来，构建出用户的浏览路径，如果当前的请求页面同用户已浏览的页面之间没有超链接关系，那么就认为存在相同IP地址的不同用户。

2.3 会话识别

一个会话是指用户对服务器进行访问时一串顺序的页面请求，即用户连续访问的具有一定目的性的页面序列。用户会话识别就是将用户的多条访问日志记录分为单个的会话。

目前用户会话的表示方法主要有两种方法：一种是将会话简单地表示成访问页面的集合[1,2]，其优点是算法思想简单、直观。另一种方法在集合表示的基础上，加上了用户访问的时间信息，将用户会话看成是访问页面所形成的一个页面序列[3,4]。

定义1 用户会话S是一个二元组，其中userid是用户标识，RS是用户在一段时间内请求的Web页面的集合。

RS包含了用户请求的页面的标识符Pid和请求的时间t，用户会话S可以表示为如下的元组。

S= (1)

其中tk表示页面Pidk的访问时间。通过用户识别，可以得到关于用户的访问web页面的一个序列，然后可以通过设定超时的方法识别用户会话。这里有两种方法[5]，一种方法是设定整个用户会话时间间隔T，使得tk－t1≤T。另一种方法就是缩小范围，设定相邻请求之间的超时时间，如果两个页面请求时间的差值超过设定的界限值就认为用户开始了一个新的会话。(1)式中的用户会话要满足下面的条件（其中T为设定的超时界限值）：

ti－ti-1≤T,1

现在常采用第二种方法来进行超时设定。基于以上的思想，可以用如下伪代码算法过程来识别用户会话：

输入：经过数据清理后的日志集合Cleaned_Data，会话的超时设定值T。

输出：经过识别得到的会话集合Recognized_Session，在算法开始时将Session集合初始化为空。

算法如下：

RecognizeProgress (DataQueue)

{Createlist(); //初始化一个新队列用来存放会话识别后的页面序列

If (DataQueue.Isempty) return; //如果日志记录队列为空，则退出

else {Session.add(DataQueue.Front); DataQueue.Dequeue;}

//取得队列中的第一个元素加入到识别后的集合中，并从队列清除之

//寻找DataQueue队列中剩下的元素

If userid与新队列的当前指针所指结点的userid相同且Time与该结点的Time相差小于T

{session.Add (Data);

DataQueue.Dequeue;

} //将符合条件的页面结点加入集合中，并删除该节点更新队列。

//比较完DataQueue中所有的元素后，按照页面的访问时间进行排序

session.sortByVisitOrder ();

If DataQueue.Isempty return;/ /如果队列为空，则退出

else //否则递归访问DataQueue队列

RecognizeProgress(DataQueue)；

以上算法基于递归的思想，将经过清理后的日志记录数据集合中符合同一用户会话条件的页面序列取出来放入一个新的集合中，并按照访问页面的时间进行排序。该算法简单，实现起来相对容易。

2.4 路径补充

路径补充(path completion)是对识别出的用户会话进行优化的步骤，使得其更适合描述用户的浏览请求。由于本地缓存和服务器的存在，使得服务器的日志会遗漏一些重要的页面请求。路径补充就是将这些一路的请求补充到用户会话中去。解决的方法往往依赖于网站的拓扑结构图。

根据网站的拓扑结构分析，网站可以用树形结构来表示。网站有一个主页，用户可以通过主页到达任何一个一级栏目首页、二级栏目首页以及最终内容页面。考虑到每个页面所拥有的子链接数目不同，页面可以采用非结构化的存储方式。

定义每个页面节点的结构表示为：node=。

node=，如果是网站首页，则node的父节点集合为空。如果是网站的尾页即叶节点，则node的子节点集合为空。

基于站点的拓扑结构，这里提出一种路径搜索算法，其基本思想是若当前页与下一页有链接关系时，说明用户可能是通过当前页的链接到达下一页。若无链接，则返回当前页的引用页。若存在两个或两个以上的引用页，可根据请求时间最接近于当前页的那个链接作为考虑对象，并判断引用页与下一页有无链接关系。循环执行，最后能得到用户的访问路径。

此处定义一个字符串数组path[m]存储每个用户的访问路径。首先初始化path[m]为空。算法描述：

输入：经过数据清洗、用户识别、会话识别后的web日志集合，网站的拓扑结构。

输出：用户完整的访问路径。

算法伪码如下：

for(i=1;i

{{If T>2 //如果会话集合页面数大于2页则执行下面操作

{node1=FirstPage(); //取得用户路径中的第一页

node2=SecondPage(); //取得用户路径中的第二页

s=0

While (S

// S为页面计数变量，Total为一次会话中用户浏览的总页面数

If (node1和node2之间有链接) //查找网络拓扑物理结构存储

{Path[i].Add(node1); //将Node1加入路径数组中

node1=node2; node2=NextPage();//取下一页

S++

}

else //node1和node2之间没有链接

{//向前搜索获得node1的父节点

node1=node1.parent; //取node1的父节点作为回退页

//如果碰到多个父节点，取请求时间最接近node1的节点

path[i].Add(node1); //将node1的父节点加入路径}

}}}

算法分析：其时间复杂度为O(m×t) , 空间复杂度为O(m)。由于算法中采用了数组来存储路径补充后的页面序列，而路径补充后的页面序列的长度不能预先得到，所以也可以用队列来实现上述算法。在用户会话识别的基础上应用上述路径补充算法能够有效的完成对用户访问路径的补充。

2.5 事务识别

用户事务识别主要是根据Web日志挖掘中的模式发现的知识挖掘特性来确定与知识相对应的事务定义，因此不同的会话分析可以确定不同的事务。

事务识别最常用的是最大向前参考模型，方法如下：假设用户访问过程中只在改变访问主题时才会访问前面访问过的页面以跳转到另外的页面。那么，确定用户访问事务是指用户一直前向访问，直到向后返回访问才算是开始一个新的访问事务。所谓前向，指的是某页面不在目前的访问事务页面集里。后向，指的是某页面在目前的访问事务页面集里。最大向前路径(MFP)是在用户会话中第一页到回退的前一页组成的路径。例如：一个用户会话中请求的页面顺序是A－B－C－A－D－E ，对应的MFP为A－B－C和A－D－E。这种方法的基本模型是MFP中的最后一页是内容页，而在此之前的页面都是导航页。

3 结束语

Web日志数据准确性是Web日志挖掘中重要的前提和基础。只有准确的数据才能正确地反映用户的意图，才能保证分析沿着正确的方向进行。高质量的Web日志挖掘必须依赖高质量的数据。有效的利用web日志可以挖掘出潜在的信息，有助于网站经营者为用户提供个性化服务。目前，如何提高与改进Web日志挖掘预处理技术，确保输入Web日志挖掘的数据正确高效已成为一项重要课题和研究方向。

本文作者创新点：在路径补充阶段提出了一种算法，此算法在一定程度上提高了数据预处理阶段的工作效率，节省了系统开销，为web日志挖掘的下一阶段工作模式发现和模式分析做了充分的准备。

参考文献：

[1] Pei, J., Han, J., et al.. Mining access patterns efficiently from Web logs[C].PAKDD’00, Kyoto, Japan2000, Liping Sun, Xiuzhen Zhang. Efficient Frequent Pattern Mining on Web Logs[C]. APWeb 2004. pp. 533C542.

[2] Liping Sun, Xiuzhen Zhang. Efficient Frequent Pattern Mining on Web Logs[C].APWeb 2004. pp. 533C542.

[3] Ezeife，Yi Lu. Mining Web Log Sequential Patterns with Position Coded Pre-Order Linked WAP-Tree [J]. Data Mining and Knowledge Discovery. 2005, 10, 5-38.

[4] Maged El-Sayed, Carolina Ruiz, Elke A. Rundensteiner: FS-Miner: efficient and incremental mining of frequent sequence patterns in web logs. WIDM 2004:128-135.

[5] Robert Cooley, Bamshad Mobasher, Jaideep Srivastava: Data Preparation for Mining World Wide Web Browsing Patterns [J]. Knowledge and Information System. 1(1): 5-32 (1999).

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文