Web日志挖掘预处理中会话识别算法的优化

摘要:会话识别是Web日志数据预处理中的重要步骤,直接影响着Web日志挖掘的效率和准确性。在给出会话识别定义的基础上,对传统的预先设定时间间隔方法进行了优化,并具体描述了数据结构及其算法。实验结果证明会话质量得到了提高。

关键词:会话识别;Web日志挖掘;数据预处理

An Optimization of the Session Identification Algorithm in Preprocessingthe Web Log Mining

LI Rui, ZHU He-xiang

(School of Software,Dalian Jiaotong University,Dalian116028,China)

Abstract: Session identification is the important process of data preprocessing in web log mining, which directly affects the impact and accuracy of web log mining. The definition of session identification is given, the traditional method of preestablished time interval is optimized and the algorithm is described concretely based on the data structure. The empirical analysis prove that the quality of session is improved.

Key words: session identification;Web log mining; data preprocessing

随着Internet的迅速发展和不断普及,Web日志资源越来越多,如何分析和利用这些海量数据是当前突出的问题。Web日志挖掘是将数据挖掘技术用于Web服务器日志以获取有规律性的知识和用户的访问行为模式,从而改善Web站点的组织结构,提高站点的访问质量,改进网站的性能。Web日志挖掘的主要步骤有数据预处理、模式识别和模式分析这3个阶段,其中数据预处理是关键和首要任务。Web日志挖掘的数据预处理包括数据清洗、用户识别、会话识别和路径补充等步骤,其结果直接影响着Web日志挖掘的效率和准确性。目前会话识别的方法有很多种。文献[6]提出了基于时间的启发式会话识别方法。文献[2]提出了一种利用最大向前引用将会话切分成事务的方法。文献[1]提出了一种事务识别会话的方法,称为序列长度法。文献[7]是基于时间间隔的会话切分方法,统计每一个用户的频率矢量,在正态分布的假设下,为每一个用户设定一个合理的切分阈值。本文提出了一种改进的基于时间间隔阈值的会话识别算法,对传统的预先设定时间间隔阈值的方法进行改进,实验证明该算法能更加准确地识别出真实的会话。

1 Web日志挖掘数据预处理

1.1 数据清理

数据清理是指删除Web日志中与挖掘算法无关的数据,这些数据主要有三类:1) 图片、框架等非用户请求逻辑单位;2) Web Robot的浏览日志记录;3) 噪音和错误信息。

1.2 用户识别

由于本地缓存、服务器和防火墙的存在使得用户识别变得很复杂。通常的用户识别通过IP地址、cookie 、注册用户等方法来提高识别的精确度.通常利用如下的启发式规则来识别用户:

规则1:不同的IP地址代表着不同的用户。

规则2:当IP地址相同时,可以默认不同的操作系统或浏览器代表不同的用户。

规则3:在IP地址相同,用户使用的操作系统和浏览器也相同的情况下,则可以根据网站的拓扑结构图对用户进行识别:如果用户请求的某个页面不能从已访问的任何页面到达,则判断这是又一个新的用户。

1.3 用户会话识别

用户会话直观的表述为用户在一次访问网站期间从进入网站到离开网站所进行的一系列活动,也就是一个从用户进入站点时刻起至他离开时刻止所请求的一系列链接的集合。会话识别就是在用户识别之后、将一个用户的访问日志记录分为单个的会话。可以认为一次会话是用户的一次浏览行为, 由一系列页面组成, 由访问时间决定页面次序。

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

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

通过用户识别后,能得到关于用户访问Web页面的序列。从该序列中识别出用户会话,通常采用设定时间阈值的方法来实现。时间阈值的设定有两种方法,一是设定整个用户会话的时间,则(1)式中的用户会话必定满足下面的条件(T为预先设定好的时间阈值):

另一种方法是设定相邻页面间的请求时间间隔,如果两页面请求时间间隔超过一定的界限值就认为用户开始了一个新的会话,则(1)式中的用户会话必定满足下面的条件(T为预先设定好的时间间隔阈值):

本文对第二种用户会话识别算法进行改进研究。

2 用户会话识别算法的优化

传统的使用预先设定时间间隔阈值的方法,没有考虑到页面重要程度和网站结构对阈值(T)的影响,优化后的算法中结合页面重要程度和网站结构对每个页面设置时间阈值,进而再进行会话识别。

2.1页面的重要程度与站点结构

页面重要程度通常用页面的链入、链出数来衡量。一般情况下,一个页面的链入要比链出重要,需要对它们进行加权调整,本文以黄金分割来假设链入与链出的权值之比。

定义2 页面链接权值比RLCR计算公式为:

其中Li为链入数,Lo为链出数。

为了将RLCR值用于对阈值T 的调整,需要将RLCR值映射到(0 ,1) 之间。选择如下的映射

方式, 记为RLCR值对T的影响因子为β。

定义3 β为页面RLCR对页面访问时间阈值T的影响因子,其计算公式为:

页面访问时间t可以从扩展日志的time-take字段中得到,考虑到用户在理解力,阅读速度等方面的个性差异,需给该值进行平滑处理,实验时选择从1.1～1.6作为平滑系数,本文选择平滑系数α为1.2。

综上所得,可以得出时间阈值δ的计算公式为:

2.2 会话识别算法描述

为了获得每个页面较为真实的访问时间阈值δ,首先要获取日志文件中的time-take字段值,然后根据(4)和(5)式计算出β影响因子,最利用(6)计算出每个页面的时间阈值δ。将相邻页面的时间间隔值T与δ进行比较,如果T小于δ则该页面属于前一会话,否则表示新的会话开始。

2.2.1 数据结构

算法中定义的数据结构如下:

1)页面链接结点(URL NODE)。包含三个成员:用户所访问的URL、访问时间和指向下一个URL结点的指针。

2)用户结点(USER NODE)。包含如下成员:用户名或者用户IP地址、起始时间(当前会话中用户首次访问记录的时间)、当前时间(当前会话中用户最后一次访问记录的时间)、指向页面链接结点的指针(指向当前用户当前会话中的页面结点)、计数器(用来统计当前用户访问过的所有页面个数)、指向头一个用户结点指针和指向下一个用户结点指针。

3)头结点(HEAD NODE)。包含两个成员:指向起始用户结点的指针和计数器(统计当前处理过的所有访问记录个数)。

2.2.2 优化算法描述

下面给出基于页面时间间隔阈值会话识别的优化算法pgSessionizer,对用户的会话进行优化,描述如下。

Algorithm pgSessionizer:

输入: 输入 web日志文件

输出: 输出用户会话文件

参数说明如下:

r:日志文件的某个记录

t(r):用户访问该记录的起始时间

α > 0: 会话时间间隔界限值

γ > 0: 用户数目界限值

β > 0:页面访问时间阈值影响因子

begin

1. open infile and outfile/*打开输入输出文件*/

2. createHeadNode(S); S.head = null; S.counter=0 /*创建用户链表头结点并初始化*/

3. while (infile is not empty)

4.readRecord(infile, r) /*读取日志文件中的记录 */

5. if (isRecordRelevant(r)) /*判断该记录是否有效*/

β=effRecord(r) /*计算出页面访问时间阈值影响因子*/

α=calRecord(r, β,t) /*计算出会话时间间隔界限值*/

6.n = findRecord(S, r) /*识别出访问该记录的用户*/

7.if (n is null)

8. addRecord(S, r) /*将新用户结点插入用户链表中*/

9. else if (t(r) - n.currentTime ≤ α)/*判断相邻页面时间间隔值是否满足所属条件*/

10.n.currentTime = t(r)/*保存当前记录的访问时间*/

11. addURL(n.urlListPtr, r)/*将新的URL结点插入到用户所属的URL链表中*/

12.else

13.writeSessionAndReset(outfile, n, r)/*输出当前用户会话并重置用户URL链表*/

14.S.counter = S.counter + 1/*计算器累加*/

15.if (S.counter > γ)

16. purgeNodes(outfile, S, t(r)); S.counter=1 /输出当前所有用户会话,并初始化计数器/

17. cleanList(outfile,S); /*清空用户链表*/

18. close infile and outfile

end

3 实验分析

实验数据来源于大连交通大学软件学院Web服务器,日志文件记录的是2008年6月份对该学院网站的访问信息。由于要人工识别真实会话,数据量和工作量都很大,所以只选取一天的记录进行分析。根据分析判断,6月22日的日志比较接近整个月份的平均访问水平线,具有典型性,所以对该天的日志进行分析判断。

按照真实会话的定义,经过人工识别,2008年6月22日这一天内所产生的真实会话有1079个。实验首先用传统的使用预先设定时间间隔阈值的方法识别会话,时间阈值T设定为30分钟。然后用改进后的优化算法识别会话。发现会话的结果在表1中给出。

表1中,A表示发现的会话数目,B表示发现的真实会话数目,Z表示总共发现的真实会话数目。

从上表的实验数据可以看出,传统的预先设定时间间隔阈值方法发现的总会话数目有840个,其中真实会话数目为752个,占实际真实会话数目的比例是69.694%。将过本文算法pgSessionizer优化识别,各个参数值都有了明显的提高,算法pgSessionizer可以有效地提高会话识别的质量。

4 结论

本文提出的Web日志会话识别优化算法,考虑了页面重要程度和网站结构对会话识别的影响,并给出了算法的具体描述,经过实验验证,会话的质量得到了明显的提高,使得发现的会话更加接近真实会话。

由于Web用户的多样性和随意性,缓存技术及服务器的广泛应用,使得会话识别的概念有待进一步标准化和精确化,以利于提高会话识别算法的效率和质量。

参考文献 :

[1] Robert Cooley, Bamshad Mobasher, and Jaidep Srivastava. Data preparation for mining world wide web browsing patterns[J]. Journal of Knowledge and Information Systems, 1:1, 1999.

[2] Chen M.S,Park J.S ,Yu P.S.Efficient data mining for path traversal patterns[J/OL].IEEE Transactions on Knowledge and Data Engineering, 10:2:209-221, 1998.

[3] Osmar Zaiane, Man Xin, Jiawei Han. Discovering web access patterns and trends by applying olap and data mining technology on web logs[Z/OL]. Advances in Digital Libraries, 1998:19-29.

[4] B. Berendt and M. Spiliopoulou. Analysis of navigation behavior in web sites integrating multiple information systems[J]. The VLDB Journal, 9:56-75, 2000.

[5] Yang Qiang , Zhang Haining , Li Tianyi. Mining Web logs for prediction models in WWW caching and prefecting[C] ∥The Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining KDD’01. San Francisco: ACM SIGKDD , 2001.

[6] Berendt B, Mobasher B, Nakagawa M,etal. The impact of site structure and user environment on session reconstruction in Web usage analysis[C]∥Proceedings of the 4th WebKDD 2002 Workshop at the ACM2SIGKDD Conference on Knowledge Discovery in Database.Edmonton,Alberta: ACM SIGKDD ,2002.

[7] 庄力可,寇忠宝,张长水. 网络日志挖掘中基于时间间隔的会话切分[J].清华大学学报,2005,45(1):115-118.

[8] 陈子军,王鑫昱,李伟.一种Web日志会话识别的优化方法[J].计算机工程,2007,33(1):95-97.

[9] 殷贤亮,张为.Web使用挖掘中的一种改进的会话识别方法[J].华中科技大学学报:自然科学版,2006,(7):33-35.

[10] 朱晋华,陈俊杰.Web日志预处理中会话识别的优化[J].太原理工大学学报,2008,39(2):111-114.