中篇 基于Web用户查询日志的实证研究

本篇介绍我们针对不同类型Web查询系统的用户日志所开展的实证研究，主要包括：北大天网大规模Web搜索引擎系统的用户日志、国内某大型期刊数据库的用户日志、移动搜索的用户日志，这三种日志涵盖搜索引擎使用情况、学术网站使用情况和移动搜索的使用情况，代表性较强。对这些日志数据集，我们开展了多维度、多方法的综合性试验研究。

本篇共包含七章内容，具体如下。

(1) 用户对Web检索系统访问的规律性极强。本篇第5章将用户的访问量看成按时间次序排列的随机变量序列，利用时间序列分析的方法，分别建立了北大天网搜索引擎用户的查询量、点击量和不同IP用户访问量的潜周期模型。

(2) 本篇第6章研究了中文Web搜索引擎用户检索行为的一般行为特征与规律，包括用户所使用的词项特征、会话特征、查看网页快照情况等。

(3) 用户在使用Web搜索引擎进行信息查询时，可能包含单个或多个主题(多任务)，如：用户开始时查找“计算机”类的信息，随后查找“娱乐”类的信息，这属于两种不同主题的信息查询。本篇第7章研究了多任务中文Web查询的特征。

(4) 本篇第8章重点研究了用户的点击行为特征，得到了一些极具价值的研究结果，如用户点击URL与页面大小相关，点击URL具有时间局部性，其顺序具有自相似性特征等。

(5) 对5年的北大天网搜索引擎的用户日志进行抽样分析，发现了中文Web用户查询行为的演化趋势，如：用户输入的查询串中所包含词项数量有明显增多的趋势；用户会话的长度逐年下降；查看的时间间隔逐渐缩短；查询串中所包含的汉字个数基本稳定，其中包含2～4个汉字的查询串居多；Web用户查询的主题变化较快等。这是本篇第9章的研究内容。

(6) 基于国内某大型期刊数据库的用户查询日志，第10章研究了高校用户使用学术期刊数据库的基本行为特征，分析了不同类型高校用户的检索策略，提出了高校用户检索策略的影响因素模型。

(7) 限于数据获取的困难，目前国内外关于传统PC搜索的用户行为分析的研究成果较多，而针对移动搜索日志挖掘的研究相对较少。本篇第11章基于国内某网站一批包含300余万条有效记录的日志数据，研究了我国移动搜索用户行为的基本特征，丰富了中文移动搜索领域的研究成果。

第5章 搜索引擎用户访问量模型

基于北大天网这一大规模分布式Web搜索引擎系统的用户日志，本章研究了搜索引擎用户访问量建模分析和预测的一般方法；将用户的访问量看成按时间次序排列的随机变量序列，利用时间序列分析的方法，分别建立了天网用户的查询量、点击量和不同IP用户访问量的潜周期模型；结果显示模型对实际数据拟合效果较好；用户访问的主周期为24小时，其他周期依次为12小时、6小时、8小时、5小时、168小时 (即一周)；用户的异常访问情况可通过小波技术检测。

5.1 引言

WWW搜索引擎是一种Web上的应用软件系统，它以一定的策略在Web上搜集和发现信息，对信息进行处理和组织，为用户提供Web信息查询服务。中国互联网络信息中心 (CNNIC)[1]的统计表明，搜索引擎已经成为继电子邮件之后人们用得最多的网上信息服务系统。

搜索引擎系统主要维护两类日志：用户查询日志和点击日志[2]。用户的查询日志记录用户向搜索引擎提交查询的相关数据，一般包含查询词，时间，用户信息 (IP、浏览器类型等)，查询结果等信息。用户的点击日志是在用户浏览查询结果时点击结果页面中的URL时被搜索引擎记录的信息，一般包含点击时间、点击的URL、用户IP、点击URL的序号 (该页面在查询结果中的位置)、该点击对应的查询词等信息，它记录和反映了查询结果中用户感兴趣页面的相关信息。

目前针对用户的查询和点击日志的分析已有一些研究成果[2-5]，如：用户平均输入的查询词长度为两个英文单词，多数用户并不基于返回结果修正查询词，重复查询项遵从Pareto分布，查询词序列具有自相似性特征，用户点击不同URL的数量遵从Heaps定律等。而针对搜索引擎用户访问量进行建模分析和预测的方法尚未见到。

对天网搜索引擎系统用户的查询和点击日志进行统计分析显示用户的查询量、点击量和不同IP用户的访问量具有较好的周期性：主周期24小时比较明显，但其他周期不易判定。当我们将用户的访问量看成按时间次序排列的随机变量序列时，就可以利用时间序列分析的方法建立用户访问量的潜周期模型，由此得到了用户访问的所有主要周期。模型的建立对搜索引擎系统性能测试、系统仿真、把握用户对系统访问的时间规律性具有重要的理论和实际意义。

本章内容安排如下：5.2节简要介绍了天网搜索引擎的查询与点击日志的数据格式；5.3节讨论了基于小波技术的用户异常访问检测问题；5.4节给出了建立时间序列潜周期模型的一般方法；5.5节分别建立了天网用户的查询量、点击量和不同IP用户访问量的潜周期模型；5.6节是本章的结论和进一步的工作。

5.2 用户查询与点击日志

天网搜索引擎[6]于1997年10月正式在CERNET上为广大用户提供Web信息导航服务，系统的体系结构从早期的集中式发展到了现在的并行分布式，无论搜集的网页质量还是提供的服务质量都已发生了很大的变化。到2004年年初天网搜集系统已搜集到国内静态网页2.58亿个 (不包括通过提交查询词动态生成的网页)，每天用户访问量20余万，用户点击记录10余万条。天网的用户查询与点击日志的一个完整的记录分别如表5-1和表5-2所示。

目前搜索引擎的更新周期越来越短，天网大约两个月左右更新一次新的数据。为此，本章的研究中，我们抽取了天网系统2003年9月1日到10月31日共两个月的用户查询与点击日志进行分析，在燕穹提供的数据产品中的编号为：YQ-QUERYLOG.0309-10和YQ-CLICKLOG.0309-10。用户会话为提交一次查询以及后续的翻页、在结果页面中点击的全部过程。天网未使用Cookie技术标识用户查询的会话，以用户IP来区分用户。本章统计分析对象包括单位时间 (本章以小时为单位) 内用户的访问量、点击量、不同IP用户的访问量，这些数据对象先经过整数编码，赋予全局唯一的连续整数标识，以便于后续统计、处理和分析。

5.3 基于小波的异常访问检测

时间序列中的异常数据直接影响着模型的拟合精度，如不加以清除和替换，将可能导致一些虚假信息的产生。我们在对天网搜索引擎系统的查询日志进行分析处理时，也的确发现了一些异常访问数据 (尽管不多)，如2002年12月系统在40分钟内，记录了来自同一IP的查询次数达到2万多次，这显然属于使用程序的恶意攻击行为。

如何发现异常数据，已有一些现成的处理方法，如使用数据的分箱处理技术，聚类技术等都可以进行异常数据探测。基于小波的异常数据发现与消噪是近几年出现的一种比较有效的方法[7,8]。

传统的傅立叶变换缺乏空间局部性，它只能确定一个函数奇异性的整体性质，而难于确定奇异点在空间的位置和分布情况。小波变换 (wavelet transform)是一种窗口大小不变但形状可变的局部化分析方法。近几年，利用小波技术来分析信号的奇异性及其奇异性的位置和奇异度的大小是比较有效的。

基于小波技术的奇异点检测的一般步骤是：对信号进行多尺度分析，在信号出现突变时，其小波变换后的系数具有模量的极大值，因而可以通过对模量的极大值点的检测来确定故障发生的时间点。

我们将搜索引擎系统的查询量、点击量、不同IP访问量分别看成是时域中的一个一维信号，由此可以利用小波技术进行奇异点检测和噪声的消除。

选取2003年9月至10月的用户查询日志，以小时为单位统计用户访问量，共得到1440个数据。我们用“db1”小波将这些数据进行3层分解，第一层(d1) 和第二层 (d2) 的高频部分将信号的不连续点显示得相当明显，由图5-1可知，信号的异常点出现在t=768 (即10月3日0时) 附近。查看当日用户的查询日志，发现在该日两小时内有来自同一IP的用户访问了近2万次，属于异常攻击行为。在建模时应予以清除并补充新的平滑数据。

5.4 时间序列的潜周期模型

时间序列是按时间顺序排列的随机变量序列，任何时间序列经过合理的函数变换后都可以被认为由三部分叠加而成，即趋势项部分、周期项部分和随机噪声项部分[9,10]。

实际问题中对具有明显周期性的实值数据可以考虑用潜周期模型来描述，如某地区月平均气温 (或降水量) 的变化等。它在气象、天文、机械震动、共振研究和调和信号处理方面有着广泛的应用[10]。

在信号处理领域中的余弦波信号是一种常见的信号，通常也用潜周期模型(5-1) 来表示：

其中，0<ω1<ω2<…<ωk≤π。正数Aj是相应于第j个角频率ωj的振幅。对应于ωj的周期T =2π/ωj, φj∈[0, 2π) 是相应于角频率ωj的初始相位，{ ξt}是一个有色噪声序列。

在模型 (5-1) 中，若用表示噪声项的标准差，则称ηj=Aj/σ为对应于角频率ωj的信噪比 (信号和噪声的比)。信噪比越大，频率项Ajcos(ωjt+φj) 的作用越大。

由于模型 (5-1) 是三角函数项的叠加，所以有时又称其为调和模型。对应的复数形式如下：

若数据为实值序列，则有Aj=2| aj|。

在实际的应用中，为对实值模型 (5-1) 中的参数进行估计，可首先对数据进行零均值化处理，设处理后的数据为：x1, x2, … xN，引入函数

由此，式 (5-2) 中的复数aj可用下式来估计：

由于|| 是偶函数，因而只需在[0, π]上找出峰群的个数q，并可对相应的角频率进行估计。这里SN的作用是将时域的信号转换到频域，类似于平稳序列的谱密度函数。

由此我们参照文献[10]，给出建立实值潜周期模型的一般步骤。

(1) 对原始数据进行清理，清除异常点或噪声数据，对空缺的数据用平均值或回归函数的值进行补充。

(2) 减去趋势项和均值，进行零均值化处理。

(3) 根据式 (5-3)，构造SN(λ)，并由| SN(λ) | 值的大小来估计角频率。

(4) 由式 (5-4)，计算对应于各角频率的aj。

(5) 计算式 (5-1) 中的振幅Aj=2| aj|，初相位φj为aj的幅角。

这样就可以构建一个数据序列的潜周期模型。为了检测拟合模型是否合理，需要计算残差：

和它的样本自协方差函数γk(k =1, 2, …, )。如果γk有收敛到零的性质，就可以认为模型合适。或者为残差序列 (5-5) 建立AR或ARMA模型，如果所建立的AR或ARMA模型可以通过模型检测，就应当可以肯定拟合模型的合理性。

5.5 用户访问量模型

如下我们采用上述方法，分别建立用户的查询量、用户的点击量和不同IP用户访问量的潜周期模型。

5.5.1 查询量模型

选取2003年9月1日～28日共计4周的天网查询日志，统计每小时的用户访问量。我们用{zt}表示这4周的数据序列，共672个数据。用最小二乘法拟合后发现在这段时间内没有明显的趋势成分，样本均值为mz=2942.7，令：z=z -mz，即对{zt} 进行零均值化处理。构造函数SN(λ)，并以λ为横坐标，区间为[0, π]，以| SN(λ) | 的值为纵坐标，得到图5-2。

该图的峰值表现较明显的有3个 ( | SN(λ) | > 2.5 × 105)，另有3个小的峰值 ( | SN(λ) | > 7 × 104)。根据前述方法得到相应角频率、周期、初相位和振幅估计，见表5-3。该表第三行给出了用户查询量的周期：主周期为24小时，其他周期依次有12小时、6小时、8小时、5小时、168小时 (即一周)。

由此，在不考虑随机干扰时可以建立模型 (5-6)：

其中，mz为样本均值2942.7。

我们用该模型对2003年9月23日和29日的实际访问量与模型预测量作比较 (图5-3)，图中实线为用户实际访问量，星点为由模型 (5-6) 预测的数据值，其残差图如图5-4所示，近似为一个平稳序列，残差序列的自协方差函数也有逐渐减少的趋势，构造其频数直方图发现它呈现均值为0，标准差为465.42的正态分布的形状，误差序列的中位数仅为12.38，可以认为是一个白噪声序列。相对误差在10%左右，为此我们认为，该模型合理。

5.5.2 不同IP用户访问量模型

用户在使用搜索引擎进行查询时，一般并不仅仅查询一次就离开，为此我们统计各时间段内来自不同IP用户的访问情况。与查询量模型建立的过程类似，我们可以为其建立一个不同IP用户访问量模型。

日志仍选取2003年9月1日～28日共计4周的天网查询日志，统计每小时来自不同IP的用户访问量。在模型构造的过程中，我们发现其| SN(λ) | 取到极大值点的λ值是完全相同的，所不同的只是| SN(λ) | 的具体取值而已。事实上也应该如此，用户的访问量与用户个数呈正相关关系。

相应角频率、周期、初相位和振幅估计如表5-4所示。它与表5-3的区别主要在振幅A取值的不同，同时其相位角也略有一点很小的差异。对该模型与实际数据比较，同样取得了不错的拟合效果。模型表示仍为式 (5-6)。

5.5.3 点击量模型

对用户点击日志进行统计，可得到用户在每个小时内的点击量。采用前述为用户查询量进行建模的方法，为用户点击量建立潜周期模型。日志选取2003年9月1日～28日的天网点击日志。同样由于用户访问量、不同IP的数量、用户点击量之间存在正相关关系，用户点击量序列的角频率与查询量序列相同。计算得到的角频率周期、初相位和振幅估计如表5-5，模型仍为式 (5-6)。

5.6 小结

本章基于天网Web搜索引擎的用户查询与点击日志数据，分别为用户访问量的三个主要指标：用户的查询量、点击量和不同IP用户访问量建立了时间序列的潜周期模型。该模型较好地拟合了真实数据 (相对误差10%左右)，并得到了用户访问的主周期为24小时，其他周期依次有12小时、6小时、8小时、5小时、168小时 (即一周)。用户的异常访问情况可采用小波技术加以检测。

寻求更好的模型来刻画搜索引擎的用户访问量是一个值得研究的问题，相关的研究工作还包括利用该模型对搜索引擎系统的数据作仿真试验，检测系统性能等。

模型对节假日 (五一、十一、春节) 期间的预测有较大偏差，但在各时间段上的分布形式类似，只是用户的访问量要减少，可用一个适当的比例因子 (如0.7) 去乘以预测数量，得到用户访问量。如何较好地估计这一比例因子，以使得整体误差最小是值得进一步研究的问题。

参考文献

[1]CNNIC (中国互联网络信息中心). http://www.cnnic.net.cn/.

[2]王建勇，李晓明，单松巍，等．海量Web搜索引擎系统中用户行为的分布特征及其启示[J]．中国科学 (E), 2001, Vol.31 (4):372-384.

[3]Xie Y, O' Hallaron D. Locality in search engine queries and its implications for caching[C]. // Proc IEEE Infocom 2002.

[4]Spink A, Wolfram D, Jansen B J, et al. Searching the web: the public and their queries[J]. Journal of the American Society for Information Science, 2001, 53 (2): 226-234.

[5]Baldi P, Frasconi P, Smyth P. Modeling the Internet and the Web, Probabilistic Methods and Algorithms[M]. John Wiley, 2003.

[6]天网搜索引擎．http://e.pku.edu.cn.

[7]胡昌化，张军波，等．基于Matlab的系统分析与设计——小波分析[M]．西安：西安电子科技大学出版社，1999.

[8]王鹏，单保慈，曾振柄，等．多尺度网络时序数据挖掘[M]//李晓明，李星．搜索引擎与Web挖掘进展．北京：高等教育出版社，2003: 178-185.

[9]Box G E P, Jenkins G M, Reinsel G C. Time Series Analysis: Forecasting and Control[M], Prentice hall, Inc.1994.

[10]何书元．应用时间序列分析[M]．北京：北京大学出版社，2003.