搜索引擎用户访问量模型.pdf

《搜索引擎用户访问量模型.pdf》由会员分享，可在线阅读，更多相关《搜索引擎用户访问量模型.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机工程与应用!#$!%&引言搜索引擎是一种()上的应用软件系统，它以一定的策略在()上搜集和发现信息，对信息进行处理和组织，为用户提供()信息查询服务。*+,*（中国互联网络信息中心）-&.的统计表明，搜索引擎已经成为继电子邮件之后人们用得最多的网上信息服务系统。搜索引擎系统主要维护两类日志：用户查询日志和点击日志-!.。用户的查询日志记录用户向搜索引擎提交查询的相关数据，一般包含查询词、时间、用户信息（,/，浏览器类型等）、查询结果等信息。用户的点击日志是在用户浏览查询结果时点击结果页面中的012时被搜索引擎记录的信息，一般包含点击时间、点击的012、用户,/、点击012的序号（该页面在

2、查询结果中的位置）、该点击对应的查询词等信息，它记录和反映了查询结果中用户感兴趣页面的相关信息。目前针对用户的查询和点击日志的分析已有一些研究成果-!3%.，如：用户平均输入的查询词长度为两个英文单词，多数用户并不基于返回结果修正查询词，重复查询项遵从/45(67分布，查询词序列具有自相似性特征，用户点击不同012的数量遵从8(49:定律等。而针对搜索引擎用户访问量进行建模分析和预测的方法尚未见到。对北大天网用户的查询和点击日志进行统计分析显示用户的查询量、点击量和不同,/用户的访问量具有较好的周期性：主周期!#小时比较明显，但其他周期不易判定。当将用户的访问量看成按时间次序排列的随机变量序列

3、时，就可以利用时间序列分析的方法建立了用户访问量的潜周期模型，由此得到了用户访问的所有主要周期。模型的建立对搜索引擎系统性能测试、系统仿真、把握用户对系统访问的时间规律性具有重要的理论和实际意义。文章内容安排如下：第!节简要介绍了天网搜索引擎的查询与点击日志的数据格式；第;节讨论了基于小波技术的用户异常访问检测问题；第#节给出了建立时间序列潜周期模型的一般方法；第%节分别建立了天网用户的查询量、点击量和不同,/用户访问量的潜周期模型；第&）!（中科院资源环境科学信息中心，兰州;）?A4BC：DEAFG(6$9HI$(JI$KG摘要基于大规模分布式搜索引擎系统北大“天网”的用户日志，该文研究了搜

4、索引擎用户访问量建模分析和预测的一般方法；将用户的访问量看成按时间次序排列的随机变量序列，利用时间序列分析的方法，分别建立了天网用户的查询量、点击量和不同,/用户访问量的潜周期模型；结果显示模型对实际数据拟合效果较好；用户访问的主周期为!#小时，其它周期依次为&!小时、小时、=小时、%小时、&=小时（即一周）；用户的异常访问情况可通过小波技术检测。关键词搜索引擎用户访问量小波潜周期模型文章编号&!=;&（!#）!%L;文献标识码M中图分类号N/;L;!#$%&()*+,&,-./0$10233$00.1 4$+135 6(&$7+(8&9&(:，;&）!（,GP75A46B7G*(G6(5 P

5、75 1(:7I5K(:4GJ?GVB57GA(G6 QKB(GK(，*MQ，24GXS7I;）20,1+3,：NB4GD4GT B:4 C45T(:K4C(:(45KS(GTBG(:U:6(A DSBKS B:G7D A4BG64BGBGT BGJ(Y 7P 4)7I6!%=ABCCB7G:D()94T(:4GJ!ABCCB7G:P69 PBC(:$Q7A(SBJJ(G 9(5B7JBKB6U A7J(C:7P 6S(ZI4G6B6U 7P I:(5:4KK(:P75:(45KS(GTBG(B:(:64)CB:S(J)4:(J 7G 6S(ZI(5U 4GJ KCBKH C7T 7P NB4

6、GD4GT$NS(A4BG BJ(4 B:6S46 6S(ZI4G6B6U 7P I:(5:4KK(:，DSBKSBGKCIJ(:6S(ZI4G6B6U 7P I:(5:ZI(5U，KCBKH 4GJ JB:6BGK6,/I:(5:IGJ(5 4 IGB6 6BA(，B:5(T45J(J 4:4 6BA(:(5B(:$NS(G6S(A7J(C:K4G)(:64)CB:S(J)U 499CUBGT:7A(A(6S7J:BG 6BA(:(5B(:4G4CU:B:$NS(5(:IC6:S7D 6S46 6S(A7J(C:957VBJ(4)(66(5 PB6 67 6S(5(4C J464$MGJ 6

7、S(A4BG 9(5B7J 7P 6S(ZI4G6B6U 7P I:(5:4KK(:B:!#S7I5，6S(76S(5:&!S7I5，S7I5，=S7I5，%S7I5 4GJ&;重点基础发展研究计划项目（编号：&LLL;!）资助作者简介：王继民（&L%），男，博士研究生，研究方向为：网络与分布式系统。L万方数据!#$!%计算机工程与应用字段说明!&%&%(&$&()$!%&$&*%!#*)会话标识+,-./0&：&)!(查询时间111$111$111$111用户23（经过变换，保护用户隐私）4567/是否在4567/中命中火车时间表查询词#页号字段说明!&%!8!$&!$!%!$!#%!&)会

8、话标识+,-./0&：&!(点击时间111$111$111$111用户23（经过变换，保护用户隐私）智能网技术查询词7990：:;$60,?5-BU,）是一种窗口大小不变但形状可变的局部化分析方法。近几年，利用小波技术来分析信号的奇异性及其奇异性的位置和奇异度的大小是比较有效的。基于小波技术的奇异点检测的一般步骤是：对信号进行多尺度分析，在信号出现突变时，其小波变换后的系数具有模量的极大值，因而可以通过对模量的极大值点的检测来确定故障发生的时间点。将搜索引擎系统的查询量、点击量、不同23访问量分别看成是时域中的一个一维信号，由此可以利用小波技术进行奇异点检测和噪声的消除。选取!(年)月至&月的

9、用户查询日志，以小时为单位统计用户访问量，共得到&#个数据。用 V=&小波将这些数据进行(层分解，第一层（V&）和第二层（V!）的高频部分将信号的不连续点显示得相当明显，由图&可知，信号的异常点出现在9W8*（即&月(日时）附近。查看当日用户的查询日志，发现在该日两小时内有来自同一23的用户访问了近!万次，属于异常攻击行为。在建模时应予以清除并补充新的平滑数据。图&用V=&小波分解的高频系数（V=&）#时间序列的潜周期模型时间序列是按时间顺序排列的随机变量序列，任何时间序列经过合理的函数变换后都可以被认为由三部分叠加而成，即趋势项部分、周期项部分和随机噪声项部分F)，&G。实际问题中对具有明显

10、周期性的实值数据可以考虑用潜周期模型来描述，如某地区月平均气温（或降水量）的变化等；它在气象，天文，机械震动，共振研究和调和信号处理方面有着广泛的应用F&G。在信号处理领域中的余弦波信号是一种常见的信号，通常也用潜周期模型（&）来表示：!#$%#&!&%6,B（!%）#，!(X（&）其中，Y!&Y!Y$Y!$。正数&%是相应于第%个角频率!%的振幅。对应于!%的周期)W!$:!%，%!（，!$）是相应于角频率!%的初始相位，Z#是一个有色噪声序列。在模型（&）中，若用%WT5（#）表示噪声项的标准差，则称&%#&%*%为对应于角频率!%的信噪比（信号和噪声的比）。信噪比越大，频率项&%6,B（

11、!%）的作用越大。由于模型（&）是三角函数项的叠加，所以有时又称其为调和模型。对应的复数形式如下：!#+%#&#,%F6,B（%）-.BS-（%）G#，!(X（!）&万方数据计算机工程与应用!#$!%&!(#%)!$!)!$%!#$#*$(%$+*)$(+#,（计算值）!($-*$-%$-#$*(+$-)+$-,（近似值）!#!)%*)*$-+$*$+%.$!#.$#+.!$-/!-$!*(!$*!-$)!)$#!+!$+!#($(若数据为实值序列，则有!0!1#1。在实际的应用中，为对实值模型（）中的参数进行估计，可首先对数据进行零均值化处理，设处理后的数据为：$，$!，$%，引入函数&%（

12、#）%(!$()*+#(（(）由此，（!）式中的复数#可用下式来估计：#0%(!$()*+#(，!,（#）由于1&%（#）1是偶函数，因而只需在2，$3上找出峰群的个数,，并可对相应的角频率进行估计。这里&%的作用是将时域的信号转换到频域，类似于平稳序列的谱密度函数。由此参照文献23，给出建立实值潜周期模型的一般步骤：（）对原始数据进行清理，清除异常点或噪声数据，对空缺的数据用平均值或回归函数的值进行补充。（!）减去趋势项和均值，进行零均值化处理。（(）根据（(）式，构造&%（#），并由1&%（#）1值的大小来估计角频率。（#）由（#）式，计算对应于各角频率的#。（%）计算（）式中的振幅!0!

13、1#1，初相位为#的幅角。这样就可以构建一个数据序列的潜周期模型。为了检测拟合模型是否合理，需要计算残差：%($(*-!456（!(.），(%7（%）和它的样本自协方差函数&-（-，!，$，%）。如果&-有收敛到零的性质，就可以认为模型合适；或者为残差序列式（%）建立/8或/89/模型，如果所建立的/8或/89/模型可以通过模型检测，就应当肯定拟合模型的合理性。%用户访问量模型下面采用上述方法，分别建立用户的查询量、用户的点击量和不同:;用户访问量的潜周期模型。%$查询量模型选取!(年-月日.!*日共计#周的天网查询日志，统计每小时的用户访问量。用/(=表示这#周的数据序列，共)+!个数据。用

14、最小二乘法拟合后发现在这段时间内没有明显的趋势成分，样本均值为0/0!-#!$+，令：/*0/，即对!$%?%），另有(个小的峰值（1&%（#）1+?#）。根据前述方法得到相应角频率、周期、初相位和振幅估计如表(；该表第三行给出了用户查询量的周期：主周期为!#小时，其它周期依次有!小时、)小时、*小时、%小时、)*小时（即一周）。表(用户查询量模型参数由此，在不考虑随机干扰时可以建立模型（)）：/(0/.)!456（!(.），（)）其中0/为样本均值!-#!$+。用该模型对!(年-月!(日和!-日的实际访问量与模型预测量进行比较（如图(），图中实线为用户实际访问量，星点为由模型（)）预测的数据

15、值，其残差图如图#，近似为一个平稳序列，残差序列的自协方差函数也有逐渐减少的趋势，构造其频数直方图发现它呈现均值为，标准差为#)%$#!的正态分布的形状，误差序列的中位数仅为!$(*，可以认为是一个白噪声序列。相对误差在左右，为此笔者认为，该模型合理。图(模型（)）和实际访问量图#模型（)）的残差图%$!不同:;用户访问量模型（下转(页）万方数据!#$!%计算机工程与应用&!(#%)!$!)!$%!#$#*$(%$+*)$(+#,（计算值）!($-*$-%$-#$*(+$-)+$-,（近似值）!#!)%*)*$-)$+$+#.$!#.$#%.!$(/-!%$+(%)$(%$(*$-*+$(*+

16、$&!(#%)!$!)!$%!#$#*$(%$+*)$(+#,（计算值）!($-*$-%$-#$*(+$-)+$-,（近似值）!#!)%*)*$-+$*$+#.$!%.$#+.!$*/(%)$%(*$#()#$!#!$!#%)$*(%!$%（上接页）用户在使用搜索引擎进行查询时，一般并不仅仅查询一次就离开，为此笔者统计各时间段内来自不同01用户的访问情况。与查询量模型建立的过程类似，可以为其建立一个不同01用户访问量模型。日志仍选取!(年-月日.!*日共计#周的天网查询日志，统计每小时来自不同01的用户访问量。在模型构造的过程中，发现其2!（#）2取到极大值点的#值是完全相同的，所不同的只是2

17、!（#）2的具体取值而已。事实上也应该如此，用户的访问量与用户个数呈正相关关系。相应角频率、周期、初相位和振幅估计如表#；它与表(的区别主要是振幅/取值的不同，同时其相位角也略有一点很小的差异。把该模型与实际数据比较，同样取得了不错的拟合效果。模型表示仍为（)）式。表#不同01用户访问模型参数%$(点击量模型对用户点击日志进行统计，可得到用户在每个小时内的点击量；采用前述为用户查询量进行建模的方法，为用户点击量建立潜周期模型。日志选取!(年-月日.!*日的天网点击日志；同样由于用户访问量、不同01的数量、用户点击量之间存在正相关关系，用户点击量序列的角频率与查询量序列相同；计算得到的角频率周期

18、、初相位和振幅估计如表%所示。模型仍为（)）式。表%用户点击量模型参数)结语该文基于北大天网333搜索引擎的用户查询与点击日志数据，分别为用户访问量的(个主要指标：用户的查询量、点击量和不同01用户访问量建立了时间序列的潜周期模型；该模型较好地拟合了真实数据（相对误差4左右）；并得到了用户访问的主周期为!#小时，其它周期依次有!小时、)小时、*小时、%小时、)*小时（即一周）；用户的异常访问情况可采用小波技术加以检测。是否有更好的模型来刻画搜索引擎的用户访问量是笔者下一步研究的工作重点之一，其它的研究工作包括利用该模型对搜索引擎系统的数据作仿真试验，检测系统性能等。模型对节假日（五一、十一、春

19、节）期间的预测有较大偏差，但在各时间段上的分布形式类似，只是用户的访问量要减少，可用一个适当的比例因子（如$+）去乘以预测数量，得到用户访问量；如何较好地估计这一比例因子，以使得整体误差最小是值得进一步研究的问题。（收稿日期：!#年%月）参考文献$56605（中国互联网络信息中心）$7889：:;$=?8$=GHI=J?，KILM NOPIHHIQR=$SR8T=U?IQ=?VW?Q?X I=M08X 0Y9HR=X ZRQ 5I=GA5C$0=：1QR 0DDD 0=ZR=，K 3RHZQIY，B BI=X?=?8 IH$U?IQ=G 87?;?：,7?9WHQ W?Q?XABC$BRWQ=

20、IH RZ 87?/Y?QI=UR?8T ZRQ 0=ZRQYI8R=U?=，1 QIX，1 UYT87$_RM?H=G 87?0=8?Q=?8 I=M 87?3?，9QRIHX887YXA_C$BR7=3H?T，!()$天网搜索引擎$7889：:?$9W$?MW$=X，5 b?=X?H$,Y?U?Q?X/=IHTXX：RQ?=G I=M 5R=8QRHA_C$1Q?=8?c7IHH，0=.7I=M直接视觉伺服研究中，还没有同时进行过上述两方面的工作。仿真结果说明了算法的有效性。目前在国内外直接视觉伺服的研究当中还没有考虑过电机模型，因此进一步的研究工作，将考虑把电机模型直接应用到视觉伺服研究

21、当中。（收稿日期：!#年%月）参考文献$3?XX S D，UI=M?QXR=/5$KT=IY X?=XRQ.IX?M 87 LXWIH Z?MIR=，-*+；(（%）：#E#+!$5RQ?1 0$/8W8RQIH R=LXWIH X?QLR R=，-)；!（%）：)%E)+($57IWY?88?，_IQ7I=M D$/b?MW=MI=L?/99QRIM=G BR=8 SY8X：/99HR=8R dXWIH U?QLR=GABC$0DDD,QI=XR=bRR8R=，!；+（%）：+-E+(#$BI?.U?W=G XWIH X?QLR=G WX=G 9RX8R=I=M I=GH?RZ YIG?Z?

22、I8WQ?XABC$DH?IW$/=?;I99QRIXWIH X?QLR=G=QRR8R=，-!；*（(）：(E(!)$X7R9 D，U9R=G _ 3$/M9I8L?QI8R=I=M R=8QRH RZ!K YR.=RXWIH X?QLR XTX8?YXABC$5R=8QRH D=G=?Q=G 1QIa?M XWIH X?QLR R=8QRH ZRQ 9HI=IQ QRR8XA5C$0=：1QRR=，_=?I9RHX，_6，-)：!)#(E!)#-*$蔡自兴$机器人学A_C$北京：清华大学出版社，!-$U U?$/MLI=?M R=8QRH 8?W?RZ QRR89WHI8RQXA5C$0=：1QRI=R=8QRH R=Z?Q?=HIM?97I，-*：!*%E!-$胡跃明$非线性控制系统理论与应用A_C$北京：国防工业出版社，!(万方数据