基于浏览器收藏夹的用户行为研究

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

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

1 引言

网页浏览器是Web服务的客户端浏览程序(以下简称浏览器)。用户通过使用浏览器得以访问各种Web资源，可以说浏览器是用户与万维网的接口。收藏夹是浏览器中一个与用户联系紧密的功能部件。用户使用收藏夹收藏感兴趣的网页，同时通过点击收藏夹中节点实现快速访问。

由于收藏夹的特殊性，如果我们能从用户收藏行为中挖掘出有效信息，将为许多研究提供帮助。根据收藏夹数据的产生方式和存储结构特点，我们认为研究用户收藏行为具有以下重要意义。

首先，收藏夹大部分数据都是用户在Web浏览过程中主动搜集添加的。区别于一般网络资源，收藏夹数据经过用户认证，对用户有特殊意义，或是常用工具，或是对其内容有偏好，需要存储下来备忘。而当前用户行为分析领域中最常用的两种日志，Web访问日志[1-2]和搜索引擎查询日志[3]则主要记录用户点击行为。实际上，由于点击操作只表示用户开始浏览该网页，并不能准确反映出用户浏览完该网页后的反馈情况。与上述两种日志相比，收藏夹数据更能体现用户的兴趣特点，用户收藏的网页应该具有更高的质量。因此，从网页粒度上看，可以将用户收藏行为分析应用到网页质量评估[1-2]、反垃圾[4-5]工作中；将收藏夹中的文本看成是用户对网页的描述，可以像链接文本一样，应用到信息检索领域，帮助提高搜索引擎性能[6]。从用户层面上看，收藏夹信息将为用户个性化研究[7]、广告投放[8]提供另一种数据来源。

其次，收藏夹数据和其他Web日志数据相比，最大的区别是拥有结构信息。传统的网络信息一般是半结构化数据，尽管具有链接结构，但链接结构呈现的是一种自组织的小世界网络形式；对于用户组织信息的过程而言，收藏夹的树状结构无疑更加自然与便利。如果能从中挖掘出高质量的结构信息，将对研究网络资源相互关系的工作提供十分重要的帮助。例如，可以基于结构信息计算出网页之间的相关度，甚至成为大规模网页目录构建[9]的基础。同时，收藏夹的结构特征体现了用户的使用习惯。由于现阶段浏览器用户在使用收藏夹时采用的是浏览查找加点击的方式，从开始查找到完成点击，树状结构中不同位置的节点所需耗费的时间代价是不一样的。一个组织紊乱的收藏夹将影响用户体验。用户是否会根据自己对不同网页的访问频度调整收藏夹的组织结构，什么样的树结构能最大限度地帮助用户提高浏览效率，这都是值得关注的问题。

目前，针对网络用户收藏行为的研究工作不多，本文试图通过对真实数据统计分析，回答以下三个核心问题：

(1) 用户怎样收藏网页；

(2) 用户倾向于收藏哪些网页；

(3) 收藏夹用户有什么兴趣特点。

2 数据格式与预处理

本文实验所使用的浏览器收藏夹数据是由国内一家著名搜索引擎公司通过其浏览器搜集并提供的。为了保护用户隐私，数据是在“用户体验改进计划”的参与者中抽取的，数据收集经过了用户的同意，并删除了用户的IP、用户名等个人信息。数据使用树结构进行存储。具体格式如下。

表1 数据格式

所有用户ID相同的节点构成了一个用户的收藏夹树。收藏夹树包含两种节点： 网页节点和目录节点。其中目录节点URL字段为空。树中所有中间节点均为目录节点，网页节点必定是叶子节点。为叙述方便，我们形式化定义相关概念。

定义1收藏夹树的集合用T表示，即数据全集。树节点集合用V表示，边集用E表示。T=。

定义2树t(usrID)表示用户usrID的收藏夹。其中t∈T。

定义3树节点u(usrID,nodeID)表示用户usrID的收藏夹中标识为nodeID的节点(u∈V)，由二元组表示u=。其中URL和text分别表示为URLu和textu。

在此基础上，我们定义一些本文使用的基本函数。

表2 本文定义的函数

真实的数据中往往存在许多噪声。实验的第一步是进行预处理，过滤掉无用或者有干扰的数据。

首先，我们将只包含目录节点的收藏夹过滤掉。这类用户并没有存储任何网页信息，对研究没有帮助。其次，我们删除在整个数据集T中大量重复出现且深度大于等于2的子树。我们发现有许多桌面软件和网站未经用户许可擅自在浏览器收藏夹中添加信息。这部分数据不是用户主动添加的，不能反映用户真实意图，会对我们的分析造成干扰，因此需要被过滤。为避免误删有用数据，我们判断两棵子树相同，当且仅当两棵子树同构，并且对应节点的URL和text完全相同。

原始数据集包含277 948个用户，23 845 787个节点。经过上述两步过滤，预处理之后剩下273 168个用户，20 009 308个节点。其中，去除掉的噪声用户为1.7%，噪声节点为16%。

3 收藏夹结构分析

3.1 深度和节点数特征

深度和节点数量是衡量一棵树的重要特征。对于收藏夹而言，深度表示用户构建目录的最大层数；节点数量则等于用户收藏网页数量与构建目录数量之和。两者反映了收藏夹的规模。∀t∈T，计算深度height(t)和节点数量|Vt|，分别统计出现比例，得到图1。

图1 深度和节点数

从图1(a)可以看出，深度为2的用户最多，占48%，这部分用户在收藏夹中建立了一层目录。第二多的是深度为1的用户，占36%，这表示用户并没有使用目录，而是直接把网页存在根节点下。除去深度为1的数据，有64%的用户习惯至少建立一层目录，说明从中还是能得到不少结构化信息。如果将深度小于等于2的树看成是“扁平型”，将深度大于等于5以上的树看成是“纵深型”，那么结果表明用户更倾向于“扁平型”的收藏夹，占84%，只有约2%的收藏夹属于“纵深型”。

图1(b)显示，用户收藏的网页数量分布比较分散(从1到1 300)，并没有出现明显的峰值。整体而言，包含网页数量越高，对应的用户越少。有4%的用户只收藏了1个网页， 有80%的收藏夹包含不到100个网页。对比广泛使用的Web访问日志，收藏夹数据规模较小，用户倾向于收藏少量访问过的页面。

3.2 收藏夹浏览点击模型

浏览器用户在使用收藏夹的时候采用顺序浏览查找加点击的方式，如目标网页在较深层目录下，则需将路径上的父辈节点逐一点击展开。不同的树状组织结构将影响收藏夹的使用效率。为了评估收藏夹的使用效率，我们提出了基于收藏夹的浏览点击模型BBCM(Bookmarks Browse Click Model)。

3.2.1 耗时与耗时期望

收藏夹浏览点击模型建立在用户顺序浏览和点击展开两种行为模式上。

定义4ST(Search Time)表示用户在当前节点u下查找一个儿子节点所需的平均时间。不失一般性，我们认为用户顺序浏览节点的间隔时间相同，因此ST与当前节点包含的儿子节点数量成正比，令ST=α×|childSet(u)|，α为常量。

定义5CT(Click Time)表示用户点击一个节点所需时间。不失一般性，我们认为用户执行点击操作耗时相同，因此令CT等于一个常量β，CT=β。

根据BBCM模型，我们定义了两个新指标： 耗时RT(Required Time) 和耗时期望RTE(Required Time Expectation)。

定义6用户访问节点u的耗时RT(u)是指在BBCM模型中用户从根节点开始执行顺序浏览和点击展开操作，直到最终点击访问节点u所耗费的时间。

基于定义4和定义5，我们可以得到计算访问节点u的耗时RT(u)的递推式：

当u非根节点时，

RT(u)= RT(parent(u))+α

×|childSet(parent(u))|+β;

当u是根节点时，

RT(u)=0。

定义7用户访问收藏夹t的耗时期望RTE(t)表示在BBCM模型中用户访问t中一个网页节点的耗时期望。

在没有其他日志数据支持的情况下，我们认为同一个收藏夹中的所有网页节点的访问概率相等，即先验分布是均匀分布。于是，我们可以得到收藏夹(t)的耗时期望：

RTE将随着收藏夹的规模增大而变大。仅从访问效率而言，我们希望在收藏夹包含节点数量一定的情况下，RTE越小越好。

3.2.2 最小耗时期望

在BBCM模型中，给定收藏夹树t包含的网页节点数量|pageSet(t)|，我们能构造出令PRE(t)最小的树状结构。这样的树状结构通常不止一个。我们希望计算出最小耗时期望MRTE(Minimum Required Time Expectation)。

定义8最小耗时期望MRTE(n)是指包含n个网页节点的所有可能形态树状结构的耗时期望的最小值。

MRTE(n)的具体推导如下：

令g(m,n)表示包含n个叶子节点并且根节点有m个儿子节点的树的最小总耗时。分三种情况讨论：

(1) 当m=n时，将n个叶子节点放在根节点下即可。g(n,n)=(α×n+β)×n

(2) 当2≤m

g(m,n)= minm-1≤k

+αk+α(m-1)(n-k)}

(3) 当1=m

g(1,n)=min2≤k

通过g(m,n)，我们可以得到MRTE(n)：

至此，我们完成了最小耗时期望MRTE(n)全部推导过程。

3.2.3 实验与分析

定义9平均耗时期望ARTE(n)表示数据集中包含n个网页节点的收藏夹的平均耗时期望。

根据BBCM模型，我们评估数据集T的整体使用效率。首先，对于数据集中的每个收藏夹t，计算其耗时期望RTE(t)。然后，给定网页节点数量n，计算所有包含n个网页的收藏夹的平均耗时期望ARTE(n)和最小耗时期望MRTE(n)，比较两者的差值。

实验中我们取α=0.1s，β=0.2s。

图2 使用效率分析

从图2可以看出，当网页节点数较小时，ARTE和MRTE还比较接近；当网页节点数增加时，MRTE增长得十分缓慢，基本不变，而ARTE增长则较为迅速，与MRTE差距逐渐拉大。例如，当n=1 时ARTE(1)=0.32，MRTE(1)=0.3；当n=100时ARTE(100)=5.47，MRTE(100)=2；当n=1 000 时ARTE(1 000)=13.4，MRTE(1 000)= 2.99。需要说明的是，网页节点数越大ARTE震荡越厉害是因为此时对应的用户数量在急剧减少(从图1(b)k可以看出)，于是平均值缺乏稳定。

上述实验结果表明，从使用效率上看，许多用户的收藏夹组织方式有很大改进空间。在网页节点访问概率均匀分布的先验假设下，通过计算，我们发现过于“扁平型”和“纵深型”的树状结构使用效率都不高，“平衡型”结构则较好。当然，用户实际存储网页节点时需要考虑到内容上的相关性，往往并不能达到理想的MRTE值。因此，用户可以在内容关联的基础上，尽量将树状结构调整成“平衡型”，减少RTE值。

4 收藏夹网站质量评估

从收藏夹数据的产生方式可知，收藏夹中的网络资源可以看成是用户精心挑选的结果。那么这部分网络资源的质量如何呢？本节试图初步评估收藏夹中包含网站的质量，为后续将收藏夹数据扩展到反垃圾和网页质量评估等工作打下基础。

4.1 PR与CF

PageRank算法[10]是著名搜索引擎Google早期使用的用于评价网页重要性的一种网页级别排序算法。由于Google公司的成功，PageRank算法也被研究界和业界广泛采用。

将用户在Web上的浏览行为看成是一个Markov随机冲浪模型，PR(PageRank)值代表了各个网页极限状态下的被访问概率。具体公式如下：

图3 收藏夹站点质量评估

其中pi表示网页，M(pi)表示pi的入链集合，L(pj)表示pj的出链集合，N是所有页面的数量，q是衰减因子，一般取0.85。根据经典PageRank算法，网页的PR值越高，说明它被访问的概率越大，代表质量较高。

将同一个网站内的所有页面合并成一个点，原图的边对应到合并后的点，这样构成的新图称为站点链接关系图。类似的，在站点链接关系图中执行PageRank算法，我们得到站点级别的PR值。

为了衡量网络资源在收藏夹数据集中的重要程度，我们提出了收藏频度CF(Collection Frequency)指标。网页收藏频度CF(p)是指网页p被不同用户收藏的次数。

为了避免数据稀疏问题，需要使用站点级别的收藏频度。我们认为用户收藏了网页p，则表示用户同时收藏了网页p对应的站点s。网站收藏频度CF(s)是指站点s被不同用户收藏的次数。

4.2 实验与分析

第一步，通过搜索引擎公司获得站点级别的链接关系，使用PageRank算法计算得到了全网的站点级PR值。这部分数据总共涉及148 269 803个网站。

第二步，我们在收藏夹数据集中计算站点收藏频度CF，这部分数据包含个不同905 723个站点。从第一步的结果中，我们还能得到这部分站点对应的PR值。

图3(a)显示了将全网站点PR值从高到低的排列情况。纵轴表示PR值，取值在0到1之间，横轴是排名。曲线基本成线性，大致满足幂律形式。最大值是0.003，最小值是1.03e-10。

图3(b)显示的是PR值的比例分布。横轴是PR值，纵轴是比例，取值在0到1之间。其中，点状符号对象是全网站点，加号符号则只包含了收藏夹数据集T中涉及的站点。根据图3(b)，我们可以看出PR值是离散的，左上角的点状符号表示全网中有62%的站点PR值等于最小值1.03e-10，这也是图3(a)曲线右边出现断层的原因。对比两种符号，两者整体趋势都是斜向下，在PR值小于10-8.5的区间内，点状符号要高于加号符号，而当PR值大于10-8.5时，加号符号则远在点状符号之上。这说明比起全网站点，收藏夹站点明显更多地集中在PR值高端的部分，这也意味着用户倾向于收集PR值较高的站点。

以上我们比较了收藏夹中的站点和全网站点的PR值分布差异，下面我们再来分析被用户收藏的站点集合中收藏频度CF与PR的关系。

图3(c)的横轴是CF值，纵轴是PR均值。函数f表示CF值为x的网站对应的PR均值，定义如下：

可以看出， 整体而言，CF增大，对应的PR均值增大。这个趋势在CF小于100时尤为明显。当CF大于102.1后，图像开始发散。这是因为CF越高，对应的站点数量越少，PR均值也就越不稳定了。

为了更好地看清PR均值随着CF增大而增大这一趋势，我们在图3(c)基础上将横轴分段统计。图3(d)将横轴按对数坐标系分成离散的100个桶，桶区间为[10x,10x+0.06)。函数h表示CF值在区间[10x,10x+0.06)中的网站对应的PR均值，定义如下：

图3(d)结果进一步证明了PR值有随着CF值增长而增长的趋势。结果表明，CF可以作为衡量网站质量的参考之一。

5 收藏夹用户兴趣分析

5.1 开放式分类目录ODP

为了分析用户的兴趣，我们借助了开放式分类目录。 开放式分类目录ODP(Open Directory Project)是目前网络上最大的人工编制站点分类目录。ODP维护了多层的目录结构，支持多语言版本。

本文工作主要分析中文用户，于是我们下载了ODP中文版本。其中包含43 047个标注站点，与收藏夹网站的交集大小为24 973。

5.2 实验与分析

ODP目录第一层包含14个类别： 计算机、商业、地区、艺术、游戏、参考、新闻、社会、休闲 、科学、购物、体育、健康、家庭。我们将这14类看成是兴趣类别，利用标注数据，将网站对应到这14类兴趣中去。

收藏夹网站的兴趣类别分布如图4(a)所示，其中计算机类的网站被用户收藏得最多。图4(b)展示了用户兴趣的多样性。只对一个类别感兴趣的用户最多，占到了20%以上。同时感兴趣的类别越多，用户比例越少，同时对8个类别感兴趣的用户不到5%。

我们使用信息熵指标，考察了用户对兴趣的离散程度。熵的计算公式如下：

图4(c)显示了用户兴趣熵的累积分布情况。熵值从0到3.5变化，兴趣熵为0的用户占到了20%左右，与图4(b)中单兴趣用户对应。曲线往后缓慢上升，显示出大部分用户的兴趣还是比较集中的。

图4 收藏夹用户兴趣分析

6 总结与未来展望

本文通过对大规模真实数据的统计处理，详细分析了网络用户收藏行为的特点，围绕三个核心问题给出了相关结论。

(1) 用户怎样收藏网页

对收藏夹的结构进行分析，发现大部分用户的收藏夹呈“扁平型”，少部分用户属于“纵深型”和“平衡性”。为了衡量不同树状结构的收藏夹的使用效率， 我们提出了收藏夹浏览点击模型BBCM。该模型指出“平衡型”收藏夹能获得较好的使用效率。将真实用户的平均耗时期望与最小耗时期望相比，我们发现大部分用户的收藏夹组织方式有很大改进空间。

(2) 用户倾向于收藏哪些网页

根据经典PageRank算法，我们计算了站点级的PR值。将全网站点PR值与收藏夹站点PR值做比较，实验指出，用户倾向于收藏高质量网站。在收藏夹站点集合内，比较收藏频度CF和PR，发现CF与PR有同样的增长趋势，可以作为衡量网站质量的参考之一。

(3) 收藏夹用户有什么兴趣特点

借助开放式分类目录ODP，我们对收藏夹用户的兴趣进行了分析，发现用户对计算机类的网站最感兴趣，80%左右的用户会对两个以上类别感兴趣。

从兴趣熵的变化来看，大部分用户的兴趣还是比较集中的。

未来我们将进一步分析哪些用户的收藏行为更为可靠，更能为其他用户提供借鉴，同时尝试把本文研究结果应用到反垃圾、网页质量评估、大规模网页目录构建、用户个性化等研究方向上。

[1] Liu Y., Gao B., Liu T., Zhang Y. et al. 2008. BrowseRank: Letting Web Users Vote for Page Importance[C]//Proceedings of the 31st ACM SIGIR Conference. 451-458.

[2] 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).

[3] Silverstein C., Marais H., Henzinger M., Moricz M. 1999. Analysis of a very large web search engine query log[C]//SIGIR Forum 33, 1 (Sep. 1999), 6-12.

[4] Gyongyi Z., Garcia-Molina H. Web spam taxonomy[C]//First International Workshop on Adversarial Information Retrieval on the Web, 2005.

[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.4.

[6] N. Eiron， K.S. McCurley. Analysis of anchor text for Web search[C]//Proceedings of ACM SIGIR ’03, 2003.

[7] B. Mobasher, R. Cooley, J. Srivastava. Automatic personalization based on Web usage mining[J]. Communications of the ACM, (43) 8, August 2000.

[8] J. Feng, H. K. Bhargava, D. M. Pennock. Implementing sponsored search in web search engines: Computational evaluation of alternative mechanisms[J]. INFORMS Journal on Computing, 2005. Forthcoming.

[9] Stamou S., Krikos V., Kokosis P., Ntoulas A. and Christodoulakis D. Web directory construction using lexical chains[C]//Proceedings of the 10th NLDB Conference 2005, 138-149.

[10] Page L., Brin S., Motwani R.， Winograd T. The PageRank citation ranking: Bringing order to the web[R]. Available at http://dbpubs.stanford.edu:8090/pub/1999-66.