基于群体智慧的Web访问日志会话主题识别研究

方 奇，刘奕群，张 敏，茹立云，马少平

(智能技术与系统国家重点实验室 清华信息科学与技术国家实验室(筹)，清华大学 计算机系，北京 100084)

1 引言

随着互联网技术的迅猛发展，Web上存储的信息量日新月异。如今万维网已经成为人们获取信息的重要来源。据最新CNNIC统计报告显示[1]，截止2009年底，中国网民规模已达3.84亿人，网站数量达到323万个，继续平稳增长。与此同时，主流搜索引擎公司如谷歌(http://toolbar.google.com/)、雅虎(http://toolbar.yahoo.com/)、百度(http://bar.baidu.com/)、微软(http://toolbar.live.com/)等都通过浏览器工具栏基于匿名策略收集用户的Web访问行为数据，以便为工具栏用户提供更多个性化的增值服务。近来，Web访问日志的使用挖掘成为了研究界和产业界关注的热点，基于Web访问日志的用户行为分析被广泛应用于搜索引擎算法改进[2-3]，竞价广告投放[4]，作弊页面识别[5]等方面的工作中。

Web访问日志中包含了大量的点击信息，将其划分成能体现用户意图的合适的处理单元是进行后续挖掘分析工作的基础。所谓用户意图，是指用户在访问Web资源之前或过程中产生并伴随着整个访问过程的意识动机。用户意图指导用户的操作行为，同时也会在访问过程中进行转变。作为一种被广泛应用的处理单元形式，传统的会话(session)在体现用户意图上往往粒度太粗： 要么只考虑了用户和时间的因素，完全没有考虑用户意图的限制，要么虽然考虑了用户意图的限制，但是作为由连续操作构成的序列，无法处理意图交叉的情况。其中，意图交叉是指用户在一段时间内根据两个或两个以上的意图进行访问，意图对应的操作记录交叉出现的情况。基于上述原因，我们有必要在会话的基础上做进一步的细化，识别出与用户意图有关的更合适的处理单元。

本文基于Web访问日志完善了一套与用户意图相关的概念体系，认为会话(session)是与用户、时间相关的操作序列，将主题(topic)定义成会话中与用户意图相关的处理单元，即会话中具有相同用户意图的子序列。在对会话(session)、主题(topic)、划分等概念做形式化定义的基础上，为区别前人识别主题边界的工作，我们将会话主题识别任务转化为求session的最大划分问题。进一步地，为了解决该问题，本文仅使用 Web访问日志信息，设计出基于用户群体智慧的会话主题识别算法，取得了不错的实验效果。

2 相关研究工作概述

会话 (session)的概念并没有一个十分标准的定义，在不同的工作中会被赋予不同的涵义。在有些工作中，session的定义只考虑了时间跨度和用户的因素。例如，在文献[6]中，session被定义成用户在一次访问网站期间从进入网站到离开网站所进行的一系列活动；文献[7]在研究搜索引擎日志的工作中，将一个用户与搜索引擎的所有交互行为定义为一个session，在session内部进行与用户意图相关的主题(topic)边界识别。在另一部分工作中，session的定义加入了用户意图的限制。例如，文献[8]认为session是用户为了同一个意图进行的一系列访问活动；文献[9]在数据库查询记录上也有类似的定义。

时间是识别session最为常用的特征。文献[10]推导出用户一次访问的持续时间大约是25.5分钟，据此得到按时间跨度识别session的方法。按前后两次访问的时间间隔作为session边界的识别是另一种被普遍使用的方法。文献[8]在Excite和Reuters的访问日志上使用时间间隔属性进行实验，结果表明时间间隔取值在10～15分钟之间时，session包含的访问记录数量趋于稳定。除了单个session内部的信息，有的工作还基于统计使用了群体信息。文献[9]在数据库访问日志中使用语言模型进行session识别。

从目标上看，尽管关于session的定义不全一致，但大部分相关工作都希望将日志信息划分成具有相同用户意图的处理单元。对于划分结果单元，有的称之为session，有的称之为topic。从划分方法和结果上看，上述相关工作都存在一个缺陷，即将算法输出的相同用户意图处理单元表示成连续的操作记录，完成的只是一个边界识别工作，无法解决意图交叉的问题。

3 会话主题识别问题的形式化定义

Web访问日志包含了用户在访问互联网资源时的操作记录，主要由大量的用户点击数据构成。经过清理，用户点击数据一般都能转化成至少包含用户ID、点击发生时刻、请求目标网页URL这三项的记录格式。由此引出以下定义。

定义1点击记录c： 用户访问网页时的点击操作记录。用三元组表示。c=。其中，cuserID表示该点击记录的userID，ctime表示该点击记录的点击发生时刻，cURL表示该点击记录的请求目标网页URL。

定义2Web访问日志C： 所有点击记录的集合。

定义3session(s)： 在满足一定时间条件限制下，某个用户的所有点击按发生先后顺序构成的序列。所有session的集合用S表示。s的形式化定义如下:

su=(c1,c2,c3…cn) ∀1≤i≤n,

由上面定义可知，session只考虑了时间属性，没有考虑用户访问时的意图。

为了定义session的划分和划分之后的结果，我们引入与序列有关的两个概念。

易知，连续子序列是子序列的一种特殊情况。

为了表述方便，定义函数L(s)，L(s)表示序列s中所有元素构成的集合。例如，当s表示某个session序列时，L(s)表示s中所有点击构成的集合。

定义4topic(t)： 点击序列t称为session(s)的一个topic，当且仅当t满足以下两个条件：

1)t是s的子序列；

2)t中的所有点击都具有相同的用户意图。

定义5连续topic(tsuc)： 点击序列tsuc称为session(s)的一个连续topic，当且仅当tsuc满足以下两个条件：

1)tsuc是s的一个topic；

2)tsuc是s 的连续子序列。

由上述两个定义可知，连续topic是topic的一种特殊情况。

定义6session的划分D： topic集合D{t1,t2,t3…tn}称为session(s)的一个划分，当且仅当L(t1)∪L(t2)∪L(t3)…∪L(tn)=L(s)，且∀1≤i

需要说明的是，定义6使用了如下假设：

假设1session中的每个点击行为，具有唯一的用户意图。

对划分D加入不同的限制条件，我们可以得到两种特殊的划分。

定义7session的连续划分Dsuc： topic集合Dsuc{t1,t2,t3…tn}称为session(s)的连续划分，当且仅当Dsuc满足以下两个条件：

1)Dsuc是s的一个划分；

2) ∀t∈Dsuc，t是连续topic。

定义8session的最大划分Dmax： topic集合Dmax{t1,t2,t3…tn}称为session(s)的最大划分，当且仅当满足以下两个条件：

1)Dmax是s的一个划分；

2) ∀ci∈L(t),cj∈L(t′),t∈Dmax,t′∈Dmax′t≠t′，有ciintent/cj。其中ciintentcj表示ci和cj用户意图相同，ciintent/cj表示ci和cj用户意图不同。

对比定义7和定义8，我们可以发现，最大划分Dmax中的topic是具有同一个用户意图的所有点击的集合，这是人们最终需要的结果。而连续划分Dsuc则不能保证满足这一点，往往会将最大划分中的topic进一步切分成一系列零碎的点击片段。例如，已知sessions=(c1,c2,c3,c4,c5,c6) ，其中点击c1,c2,c5,c6具有一个用户意图，c3,c4具有另一个用户意图。对于这种意图交叉的情况，Dmax={(c1,c2,c5,c6),(c3,c4)}，Dsuc={(c1,c2),(c3,c4),(c5,c6)}。可以看到Dsuc将具有相同用户意图的topic(c1,c2,c5,c6)分成了两个： (c1,c2)和(c5,c6)。

在以往的相关工作中，人们更多的是使用本文的定义5，直接将Web访问日志中具有相同用户意图的处理单元定义成连续topic，完成的是连续topic边界识别任务，得到的是连续划分Dsuc，无法处理意图交叉的情况。为了得到更好的划分结果，我们基于上述定义，将会话主题识别问题描述为： 已知session(s)，求出s的最大划分Dmax。

4 基于群体智慧的会话主题识别算法

4.1 Session划分求解算法

根据假设1，可以得到如下推论。

推论1若点击ci和cj满足ciintentcj，点击cj和ck满足cjintentck，则有ciintentck。

设图Gc=，其中点集Vc={c|c∈L(s)}，边集Ec={(ci,cj)|ci∈L(s),cj∈L(s),ciintentcj}。

推论2若已知session(s)和s中部分具有相同用户意图的点击对集合EI，即EI⊆Ec。构造图GI=，则GI中同一个连通分量中的所有点击都具有相同的用户意图，每一个连通分量都对应session中的一个topic。

证明： 若点击ci和cj处在图GI的一个连通分量中，必存在路径使ci和cj可达。设路径为ci→ca1→ca2…→cak→cj,则有ciintentca1,ca1intentca2…cak-1intentcak,cakintentcj。根据推论1，可以得到ciintentcj，即Gc中同一个连通分量中的任意两个点击具有相同的用户意图。再根据假设1，可以推出GI中同一个连通分量中的所有点击都具有相同的用户意图, 每一个连通分量都对应session中的一个topic。证毕。

推论2提供了计算session划分的思路。给定点击对集合EI，由此构建出的图GI中连通分量对应的topic的集合就是session的一个划分。当构建GI所依赖的初始集合EI中包含的点击对足够多时，该算法得到的划分就是session的最大划分。我们希望EI逼近Ec，于是session的最大划分求解问题转化成初始点击对集合EI的求解问题。

基于群体智慧的会话主题识别算法的主要思想就是利用用户群体信息，尽量多地发现具有相同用户意图的点击对，然后根据推论2，求出session的最大划分。

4.2 EI的求解

Web访问日志中包含了大量不同用户的操作记录，群体的智慧蕴含在这海量数据集中。使用统计方法对大规模数据进行分析，有利于我们发现其中潜藏的规律。在求解session划分问题中，我们尝试比较两个点击对应的网页(page)在Web访问日志中的出现情况，判断两者是否具有相同的用户意图。

图1 二分图和邻接矩阵的构建

4.2.1 用session表示page

构造二分图GSP=表示Web访问日志中所有会话(session)和网页(page)的关系。图GSP节点集VSP由session集合S和page集合P两部分构成，page用对应的URL表示。VSP={v|v∈S或v∈P}。图GSP边集ESP={(s,p)|s∈S或p∈P，且∃c∈L(s)，使CURL=p}。即二分图GSP中session结点s和page节点p之间存在一条无向边，当且仅当p是s中某次点击的目标URL对应的page。

如图1所示，给定四个session，先构建出二分图GSP，然后导出邻接矩阵A。注意到由于二分图GSP是一个无权无向图，所以矩阵A是对称的01矩阵。根据矩阵A，我们可以用行向量表示page。例如，p1=(1,1,0,0)，p2=(1,1,1,0)。

4.2.2 Page相关度计算

向量之间的相关度计算公式有很多。本算法中主要使用了贾卡德相似度(Jaccard Similarity)和余弦距离(Cosine Similarity)两种。

贾卡德相似度(Jaccard Similarity)：

(1)

用邻接矩阵A表示，有

(2)

余弦距离(Cosine Similarity)：

(3)

用邻接矩阵A表示，有

(4)

通过用session表示page，并选取合适的相关度计算公式，我们可以得到page之间的相关度σ(x,y)。相关度σ(x,y)是0到1之间的实数。

为了判断同一个session中的两个点击是否具有相同的用户意图，我们认为：

intentcj

(5)

根据本文4.1的理论推导，我们可以令EI=Eσ，算法执行的结果就是session的一个划分。通过上述转化，我们运用用户群体智慧，将具有相同意图的点击对判断近似成了page的相关度计算。

4.3 算法实施流程

如图2所示，算法分为离线和在线两个部分。

图2 基于群体智慧的会话主题识别算法流程

离线部分

步骤1： 使用Web访问日志构建包含session和page的二分图；

步骤2： 由二分图导出邻接矩阵A。

在线部分：

步骤2： 根据 EI构建点击意图关系图GI，使用图搜索算法计算出它的所有连通分量；

步骤3： 将图GI的每个连通分量转化为s 的topic，得到s 的划分。

5 评价方案与实验结果

5.1 会话主题识别的评价标准

我们采用人工标注的方法对真实Web 访问日志中的session进行划分，识别出一系列会话主题。设人工标注的结果为最大划分Dmax，评价会话主题识别算法的优劣，就是比较算法求出的划分D与最大划分Dmax的差异。文献[6]在评价session重构性能的工作中引入了IR领域常用的准确率(precision)和召回率(recall)。类似地，我们同样使用了这两个指标，并增加了两者的综合指标F1。

(6)

(7)

(8)

其中，|D|表示算法结果划分D中topic数量，|Dmax|表示人工标注结果最大划分Dmax中topic数量，|D∩Dmax|表示算法完全识别正确的topic数量。

上述三个指标可以看成是在topic层面上的评价。除此之外，我们从点击层面提出了相应的指标。定义二元准确率PP(pairwiseprecision)如下：

PP(pairwiseprecision)=

(9)

其中|s|表示session中包含点击的数量。event_topic(D,ci,cj)表示事件——点击ci和cj在划分D上属于同一个topic。I(event)是示性函数。

5.2 实验结果分析

本次实验使用的 Web访问日志是由国内一家著名的搜索引擎公司通过浏览器工具栏搜集并提供的。我们抽取了2010年3月28日一整天的数据进行分析。日志数据面向万维网，包含34 918 182条点击记录。将拥有相同用户ID的点击记录合并，按发生时刻从小到大排序，我们得到1 393 046个session，并从中随机挑选出500个作为测试集合。专业人员对测试集合中的每一个session进行手动划分，标注出一系列会话主题。在此基础上，我们实现并评价了基于群体智慧的识别算法(求最大划分)和基于空闲时间间隔的识别算法。其中，基于群体智慧的识别算法分别使用了贾卡德相似度和余弦距离，阈值θ分别取0.1和0.05。基于空闲时间间隔的识别算法取空闲时间间隔为30分钟。

表1 会话主题识别算法评价结果

从表1可以看出，在各个指标上基于群体智慧的识别算法都明显优于基于空闲时间间隔的识别算法。其中，使用余弦距离作为page相关度时，基于群体智慧的识别算法达到最好结果，TP、TR、F1、PP分别为0.572 4、0.564 4、0.568 3、0.858 1，比基于空闲时间间隔的识别算法分别提高了83.52%、85.96%、84.75%、16.61%。

5 结论与分析

本文形式化定义了 Web访问日志中会话(session)、主题(topic)和划分的相关概念。特别地，为了区别于前人识别topic边界的工作，本文还形式化地提出了连续topic的概念。针对 topic和连续topic，本文尝试性地给出了session的最大划分和连续划分的形式化定义。同时，本文通过对大规模真实Web访问日志的分析研究，提出并实现了基于群体智慧的会话主题识别算法，解决了用户意图交叉问题。该算法只使用了Web访问日志中最基本的请求目标网页URL信息，在完全没有使用页面之间的链接关系和页面内容文本信息的情况下，与常用的基于空闲时间间隔的识别算法相比，取得了不错的识别效果。在评价准则方面，我们扩展了前人在线性空间上针对连续topic边界识别的评价方法，定义了二维的准确度指标，并运用到了评价最大划分的任务上。在今后的工作中，我们将针对同一session中的点击行为具有唯一用户意图这一假设做进一步深入研究，提高会话主题识别的性能。

[1] CNNIC (China Internet Network Information Center). The 25st report in development of Internet in China[EB/OL]. http://www.cnnic.net.cn/uploadfiles/pdf/2010/1/15/101600.pdf, 2010.

[2] Liu, Y., Gao, B., Liu, T., Zhang, Y., Ma, Z., He, S., and Li, H. BrowseRank: letting web users vote for page importance[C]//Proceedings of the 31st ACM SIGIR Conference. 2008： 451-458.

[3] Liu, Y., Zhang, M., Ma, S., Ru, L., User Browsing Graph: Structure, Evolution and Application[C]//The 2nd ACM International Conference on Web Search and Data Mining (WSDM 2009).

[4] 陈磊,刘奕群,茹立云,等.基于用户日志挖掘的搜索引擎广告效果分析[J]. 中文信息学报，2008,22(6): 92-97.

[5] Yiqun Liu, Rongwei Cen, Min Zhang, Shaoping Ma, Liyun Ru. Identifying Web Spam with User Behavior Analysis[C]//The Fourth International Workshop on Adversarial Information Retrieval on the Web. 2008.

[6] M Spiliopoulou, B Mobasher, B Berendt, Miki Nakagawa. A framework for the evaluation of session reconstruction heuristics in web-usage analysis[J]. INFORMS journal of Computing, 2003，15(2)：171-190.

[7] Seda Ozmutlu, H. Cenk Ozmutlu, Amanda Spink. Automatic New Topic Identification in Search Engine Transaction Logs using Multiple Linear Regression[C]//Proceedings of the 41st Hawaii International Conference on System Sciences. 2008.

[8] Daqing He, Ayse Goker. Detecting session boundaries from Web user logs[C]//Proceedings of the 22nd annual colloquium on information, 2000.

[9] Qingsong Yao, Xiangji Huang and Aijun An. Applying Language Modeling to Session Identification from Database Trace Logs[J]. Knowledge and Information Systems, 2006，10(4)：473-504.

[10] Catledge, L, J Pitkow. Characterizing Browsing Behaviors on the World Wide Web[J]. Computer Networks and ISDN System 1995，27(6)：1065-1073.