不同意图类别查询的搜索引擎稳定性分析，本文主要内容关键词为：意图论文,稳定性论文,类别论文,搜索引擎论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
修回日期：2015-04-02 中图分类号G353.4 文献标识码A 文章编号1002-1965(2015)06-0183-08 DOI 10.3969/j.issn.1002-1965.2015.06.033 0 引言 自Broder[1]将查询意图(即查询中包含的潜在用户信息需求)划分为信息类、导航类、事务类三大类别后，学界对其进行了广泛探讨，研究的重点是如何选取有效分类特征，实现三大查询意图类别之间的自动区分[2-4]。因搜索引擎识别用户意图的真正目的是针对不同的用户意图提供不同的信息，获取和分类用户意图仅仅是手段，当前的相关研究也大多停留在对查询意图进行自动分类，而如何对识别出的查询意图进行分析并以此为搜索引擎性能优化提供依据的相关研究甚少。 搜索引擎作为用户获取网络资源的重要途径，在人们日常生活中发挥着越来越重要的作用。当前，网络呈现出动态发展状态，如：网络文档总经历着消失、更新、添加等变化。搜索引擎也尝试各种方法去捕捉其动态性，并将其融合到其检索排序中，随时更新其查询结果，以便为用户提供最新的信息。但Selbert等[5]指出，搜索引擎具有不稳定性特征，查询结果排序的变化幅度有时大大超出了网络本身的变化程度，即在当前时间段返回的相关文档，在下一时间段内，不一定能在同一搜索引擎中被同一查询检索到(即使这些文档与原查询相关)。因Teevan等[6]研究表明，用户每天提交的查询中约40%的查询是想获得先前与该查询相关的文档，针对这部分查询，搜索引擎不稳定性特征在一定程度上给用户和搜索引擎供应商带来了困扰：对于用户来说，难以找到以前点击过的文档；对于搜索引擎供应商来说，因需随时监督搜索引擎的搜索质量，查询结果的不稳定性常常使得搜索引擎难以对其搜索性能做出准确的评价。因此，排序结果稳定性也是搜索引擎需具备的一重要性能。 考虑到在一般情况下，搜索引擎针对不同类别查询的稳定性程度可能不一样，本文尝试以查询意图类别体系为依据，分析搜索引擎针对不同意图类别查询的稳定性情况，以期能为搜索引擎稳定性的性能优化提供相关指导，且能有助于搜索引擎提高其返回结果的用户满意度。鉴于此，本文尝试以两个月为期，每隔四天分别向百度、搜狗、Yahoo三个搜索引擎提交不同用户意图类别的查询，通过采用不同衡量搜索引擎稳定性的指标来分析搜索引擎针对不同意图类别查询的结果稳定性情况。本文的结构如下：第二节介绍了相关研究现状，第三节介绍了衡量搜索引擎稳定性的相关方法，第四节介绍了实验数据集的获取，并在第五节做了相关实验和分析，第六节做了总结分析。 1 相关研究 1.1 查询意图的相关研究 2002年，Broder等[1]通过用户调研与对AltaVista查询日志分析将用户查询意图分为信息类、导航类和事务类。信息类是指用户以一种静态方式去查询被认为能在网络上获取到的信息，除阅读之外无其他交互信息，查找内容可以是数据、文档或多媒体，信息需求既可以是精确的也可以是模糊的；导航类是指用户查找某个特定网站(网页)，该网站(网页)可以是个人网站(网页)也可以是组织网站(网页)等，即用户在执行检索时已在头脑中形成了查找意向，知道或者认为存在网址可以满足自己的信息需求；事务类是指用户通过查找获取一些资源或网络服务，比如购买、下载等。另在Broder的基础上，虽多位学者[7-13]在查询意图类目划分方面做了相关研究，且每个划分都有其依据和支撑，但总体而言，Broder的类目体系最受推崇，且已有大量查询意图自动分类研究都是基于此分类体系来展开的。 1.2 搜索引擎稳定性相关研究 从经典Cranfield实验到已经兴起的TREC(Text Retrieval Conference)评测会议[14]，学者们已经构建了一些评价检索系统性能的指标，如查询率、查准率、覆盖率、响应时间等。这些指标主要针对静态的检索系统数据集(即一旦某数据添加到某检索系统中，一般都不会改变或者移除)提出的。针对网络动态性特点，Bar-Ilan[15]指出需定义一些能衡量搜索引擎随时间变化的性能指标。基于此，早期一些研究者[15-16]主要通过衡量搜索引擎所返回的查询结果数变化情况来衡量其稳定性，但因此类方法不能从细致层面衡量搜索引擎结果变化情况，使得此类指标未得到广泛应用。也有一些学者利用搜索引擎之间的重复性衡量其稳定性：如Bharat等[17]探讨了HotBot、Alta Vista、Excite与InfoSeek四个搜索引擎之间索引网页之间的重复性，其实验结果表明四搜索引擎之间重复率不超过1.4%；Gordon等[18]分别根据查询返回前20、50、100的网页来衡量搜索引擎之间的重复性，其实验结果表明，约93%的网页只被其中一个搜索引擎返回；Bar-Ilan等[19]在5个月时间内，每个月向6个不同搜索引擎提交同一查询“informetrics OR informetric”，以此来观察搜索引擎的稳定性。其实验结果表明，搜索引擎当前时间内返回的URLs，在后一时间段该搜索引擎将不再返回，即使其他搜索引擎能否返回这些网页且这些网页的内容仍与查询相关；Bar-Ilan等[20]通过案例分析搜索引擎Google和Allthe Web排名前10随时间的变化情况及其特征，实验结果表明，Google的稳定性高于AlltheWeb。Bar-Ilan等[21]定义了以下评测搜索引擎在动态环境中的性能指标：技术相关性、技术准确性、相对覆盖率、新URLs数以及持续URL数。 除以上查询结果数与搜索引擎之间结果重复性两指标外，另一些学者也提出了通过衡量查询结果排序变化情况来衡量搜索引擎稳定性，如Bar-Ilan等[22]利用Spearman相关系数对比不同搜索引擎之间的排序结果情况，其实验结果表明，一些大型公共搜索引擎采用了不同的排序算法；Fagin等[23]针对此类指标的缺陷，提出了Faigin's方法，并对此方进行了扩展，得到了G指标；Bar-Ilan等[24]针对已有衡量查询结果排序随时间变化情况指标(Overlap、Spearman's footrule[25]、Fagin's G measure[23])的缺陷，提出了新指标M指标，并在对文本和图片查询的实验中发现，文本搜索的结果排序相对图片搜索结果排序要稳定。在已有研究工作的基础上，Vaughan等[26]提出了评价搜索引擎稳定性的3个指标：检索结果数的稳定性、检索结果返回URL的稳定性以及检索结果排序的稳定性，并通过实验利用这些指标对搜索引擎性能进行评测。 2 衡量搜索引擎稳定性的方法 自搜索引擎稳定性概念被提出后，一些学者尝试提出相关方法对其进行衡量。综合相关研究，其方法主要分为以下四类：基于重叠的方法、Spearman's footrule方法、Fagin's方法、G指标与M指标。 2.1 基于重叠的方法 基于重叠方法是衡量搜索引擎稳定性最简单的方法，即计算两不同搜索引擎针对相同查询分别返回的前k个查询结果之间的相同度。其中，
与
两指标[27]是该类方法中的重要指标，分别衡量某URL的持续性(n个不同查询结果列表中，若某一URL均出现在这些查询结果列表中，认为该URL是持续的)与查询结果列表中包含不同的URL数。
表示某查询在n个观察期内具有持续性的URL个数，其计算方法如公式(1)所示，其中，
表示查询结果列表i中的查询结果集合。
用于衡量不同查询结果列表中的不同URL个数，其计算方法如公式(2)所示。其中，
表示查询结果列表i(即第i个观察期返回的结果列表)中的查询结果集合。
2.2 Spearman's footrule方法 Spearman's footrule[28-29]用于衡量两相同查询结果集合之间存在的排序差异性。使用该指标计算搜索引擎稳定性的前提条件是：若查询结果集合中元素个数为N，所有元素的排序必须是从1到N。因两不同搜索引擎针对同一查询返回的排名前10个查询结果不一定相同，或者是同一搜索引擎在不同时间针对同一查询返回的排名前10个查询结果也不一定相同，当计算Spearman's footrule系数时，两结果列表需要转换。第一，需剔除并非两结果列表中都包含的查询结果；第二，在对每个结果列表中的每个URL进行重排序时，使得每个结果列表中的查询结果集合都是从1到|S|(表示两个结果列表中重叠的URL数)的排序，在此基础上，利用公式(3)计算两结果列表之间差异度值
值。该公式中
分别表示两个结果列表，而
分别表示元素i在两结果列表中的排序。
其中，
取值在0～1之间，当两结果列表排序一样时，该值为0；当两结果列表排序相反时，该值为1，该值越大，表明两查询结果之间的排序差异性越大，搜索引擎的稳定性也越低。 2.3 Fagin's方法 针对Spearman' footrule方法所存在的缺陷，Fagin等[23]对该方法进行了扩展，使其能够适用于当两结果列表中的元素不相同的情况。在Fagin's方法中，将未同时出现在两个结果列表中的元素的排序均赋值为“k+1”，其计算方法如公式(5)所示：
其中，Z表示两结果集A与B之间的交集，S表示属于A但不属于B的查询结果集合，T表示属于B但不属于A的查询结果集合。
表示某结果在A中的排序，
表示结果在集合B中的排序。该方法适合于两对比结果列表中包含较多相同元素时。F值表示一距离值，该值越大，表明两结果列表的排序越小，搜索引擎的排序结果也就越不稳定。 2.4 G指标 在一般情况下，两搜索引擎针对同一查询返回的前10个查询结果之间相同元素很少。于是，Fagin方法存在着如下缺陷，当两结果列表中相同元素较少时，不同的文档集合将会对该指标起着重要作用。基于此，Fagin等对以上方法进行了归一化，使得该指标取值在0～1之间。如公式(6)中
，即当k=10时，其标准化因子为110。该指标也被称为G指标。其中，G值越大，表明两查询结果列表中差异越小，搜索引擎排序结果越稳定。
2.5 M指标 针对以上所述方法存在的缺陷，Bar-Ilan等[24]利用公式(7)尝试将相同排序或者近似相同排序赋予较高权重。该方法的主要思想是，两查询结果集合中排序越靠前文档之间的相似性相对排序靠后文档之间相似性的价值更大。
其中，Z表示两结果列表中重叠元素集合，
表示在第一个结果集合中文档i的排序，
(i)表示该文档在第二个结果集中的排序。S表示出现在第一个文档结果列表而不出现在第二个结果列表中的文档集合，T表示出现在第二个结果列表而不出现在第一个结果列表中的文档集合。总体来说，M值越大，两查询结果列表之间的相似性越大，排序结果的稳定性越好。 3 搜索引擎选取与实验数据获取 本文中数据集获取的基本思路为：选择合适的搜索引擎作为研究对象，在一定时间范围内，不断向所选取的搜索引擎提交相同查询组，以此来获得所需实验数据。 3.1 搜索引擎选取 由于时间和精力有限，本实验无法对所有搜索引擎的稳定性进行分析，则需从中选取具有代表性的搜索引擎来进行研究。因本文所选取的是中文查询，中文搜索引擎将是本文的首选对象，依照知名度为主要标准，Baidu(百度，http://www.baidu.com)和Sogou(搜狗，http://www.sogou.com/)代表了当前中文搜索引擎技术的发展方向和特点，且这两搜索引擎的查询结果网页也支持网络爬虫程序的数据采集，则这两搜索引擎将作为本文研究对象。除了以上两国内搜索引擎外，本文也选取了国外另一知名搜索引擎—Yahoo(雅虎，http://www.yahoo.com)作为本实验的研究对象，该搜索引擎支持中文检索，且检索结果也支持网络爬虫程序的数据采集。 3.2 实验数据获取 为了探讨搜索引擎针对不同用户意图类别查询的稳定性情况，笔者从Sogou日志随机选取了信息类查询、导航类查询与事务类查询各10个，其中，所选取的不同意图类别查询如表1所示。为获得本文数据，在2013年10月18日至2013年12月18日这两个月期间，笔者每隔四天分别向搜狗、百度与雅虎提交这30个查询，再利用爬虫程序自动采集每个搜索引擎针对每个查询返回的排名前50位的结果。其中，采集的信息包括每条查询结果的URL地址以及在结果列表中的排序。笔者将每次的数据采集时间点视为对搜索引擎查询结果的观察期。其中，从2013年10月18日到2013年12月18日之间，笔者共采集了16次数据，即本文对各搜索引擎排序结果进行进行了16次观察。笔者在2013年10月18日这天首次进行数据采集，且在2013年12月18日这天进行了最后一次数据采集，最终获得了(30×3×50×16)72000条记录。 4 实验结果分析 Bar-Ilan在文献[22]中提出搜索引擎稳定性研究内容应该包括以下两方面内容：a.在同一搜索引擎中，不仅考虑查询返回结果的URL变化，也考虑URL在返回结果中的排序变化；b.不仅考虑同一搜索引擎针对同一查询的稳定性，也考虑不同搜索引擎之间针对同一查询的结果稳定性，即与查询相关的URL在同一时间能被不同的搜索引擎检索到，说明不同搜索引擎之间针对该查询具有稳定性。因此，本实验也将从这两方面分析搜索引擎针对不同意图类别查询的稳定性情况。
4.1 查询意图的同一搜索引擎稳定性分析 本小节首先采用
与
来衡量查询结果中的URL变化情况，再采用M指标来衡量查询结果中URL排序结果变化情况。 4.1.1 基于
与
指标的稳定性分析 首先利用
与
两指标来衡量同一搜索引擎针对不同查询意图的稳定性，并在此基础上，利用MWU验证了三查询意图之间是否存在着显著性差异。表2表示Yahoo(Y)、Baidu(B)与Sogou(S)三搜索引擎针对不同查询意图的平均
值。表2中“List”列表示以时间先后顺序罗列的16个观察期。该表格中的
值表示在某观察时间内，针对某搜索引擎，某类查询意图(一般包括10个查询)的
平均值，如该表中第三行中的第一个元素值“50”表示，在第一个观察期间，10个导航类查询在Yahoo搜索引擎中返回结果的平均
值为50。从该表中数据可知，三意图类别查询在某一搜索引擎中返回结果的平均
值随着时间均呈现下降趋势，也就表明随时间变化，搜索引擎在不同观察期间返回结果集合之间相同URL越来越少。 同理，表3是三不同意图类别查询在Yahoo(Y)、Baidu(B)与Sogou(S)三搜索引擎中返回结果的平均
值。从该表中数据可知，三类意图类别查询在特定搜索引擎中的平均
值随着时间的增加而增加，也就表明随着时间，搜索引擎在不同观察期返回的结果集合之间不同元素越来越多。
基于表2与表3中的数据，笔者利用图1来更好地描述不同查询意图随时间的
与
值变化情况。其中，该图中X轴中“List”表示不同观察期(即不同的数据采集点)，Y轴分别表示对应的
或
值，需指明的是，此处的
(或
)值表示某类查询在某观察点针对三搜索引擎的平均
(或
)值。从该图中可以看出，信息类查询的
值整体高于导航类和事务类查询的
，而信息类的
值整体低于导航类与事务类查询的
值。由此可知，信息类查询了的结果稳定性低于其他两类查询的结果稳定性。另从该图中也可知，在不同时间点，导航类查询的
值与
值分别低于与高于其他两类查询的
值与
值，说明了导航类查询的稳定性高于其他两意图类别查询。同理可以得出，事务类查询的稳定性介于另两类查询之间。 4.1.2 三类查询意图之间的显著性差异 本实验利用Mann-Whitney(曼惠特尼，简称为MWU)[30]方法中样本容量不大于10的假设检验方法来验证三意图类别之间是否存在着显著性差异，主要计算过程为：针对每个搜索引擎，首先分别计算每个意图类别(信息类、导航类、事务类)下10个查询在16个观察期内的
值(或
值)，从而可为每个查询意图构建相关的值列表，以Yahoo为例，所构建的三查询意图列表
分别表示10个信息类查询、10个导航类查询和10个事务类查询的
值集合(或者
值集合)。当采用MWU验证三查询意图在Yahoo搜索引擎中是否存在着显著性差异时，需利用该搜索引擎中两不同查询意图列表之间的组合(如
)，即首先将两不同查询意图列表中的数值合并，并从小到大进行排序，再在此基础上计算曼惠特尼U值。
图1 不同意图类别查询在不同时间段内的
与
值 对于每一对查询意图列表A和B来说，其零假设
：此对查询意图列表之间在观察期间的
值(或
值)之间不存在着显著性差异(比如：
：A=B)；
：两查询意图列表之间存在显著性差异(如，
：A≠B)。本文设定的显性水平为α=0.05，因本实验中每个样本容量为10，因此处为双侧检验，从而查表得当样本值落入到[23，77]时，接受原假设
，否则拒绝原假设。
表4、表5与表6分别表示针对Yahoo、Baidu与Sogou不同搜索引擎，通过计算T[，url]与P[，url]值而得到的曼惠特尼U值，从这三表中数据可以看出，在Yahoo、Baidu与Sogou搜索引擎中，信息类与其他两类查询(即事务类、导航类)之间均存在着显著性差异。另外，在Yahoo搜索引擎中，事务类和导航类存在着显著性差异，而在Baidu与Sogou两搜索引擎中，事务类与导航类之间无显著性差异。
4.1.3 基于M指标的稳定性分析 以上
与
两指标主要用于衡量两结果列表中的查询结果元素变化情况。为了衡量查询结果列表中URL排序的变化情况，本文采用了M值来计算其他观察期结果列表与第一观察期结果列表之间的差异性。 表7中数据表示各个观察期的查询结果列表与List 1(即第一个观察期)查询结果列表之间的平均M距离值(即分别为(
的值)。其中，List 1是指第一个时间点(即2013年10月18日)采集到的查询结果列表。该表格中每个元素表示针对每一类别查询中10个查询的平均值。比如说，列表2中的第一个值0.531表示：对于Yahoo搜索引擎来说，10个导航类查询在List 2(第二个观察点)的查询结果列表与List 1(第一个观察点)的查询结果列表之间的平均M距离值为0.531。从该表中数据可知，信息类查询的平均M值相对其他类查询的平均M值要低，说明了相对其他两类查询来说，信息类查询在其他时间点的查询结果列表与第一时间点的查询结果列表的差距较大，也表明了信息类查询的搜索引擎稳定性相对要低。
图2 不同搜索引擎针对不同查询意图的M值 图2表示针对不同意图类别查询，不同搜索引擎在不同观察期返回结果列表与List 1结果列表的平均M值。从图2中可以看出，Sogou搜索引擎相对Yahoo、Baidu两搜索引擎的M值都要低，说明了Sogou搜索引擎的稳定性相对这两搜索引擎的稳定性要低，相反，Yahoo的稳定性相对较高。从该图中还可看出，随着时间的增加，三搜索引擎针对信息类查询的M值差距越来越小，说明三搜索引擎分别针对此类查询的稳定性越来越相似，而三搜索引擎针对导航类、事务类查询的M值差距越来越大，说明三搜索引擎分别针对这两类查询的稳定性差异越来越大。以上现象说明了，随时间变化，三搜索引擎之间排序算法存在的差异性会越来越明显。 4.2 查询意图的不同搜索引擎之间稳定性分析 本文除探讨不用意图类别查询针对同一搜索引擎对时间的稳定性外，也尝试探讨不同搜索引擎之间针对不同意图类别查询随时间的稳定性情况。表8表示针对不同意图类别查询，三搜索引擎两两之间的返回结果的差异性。该表中采用了三指标对比两搜索引擎之间结果差异的指标，其中，“S”表示Spearman's footrule方法，“F”表示Fagin's方法，“G”表示G指标，“M”表示M指标。
在利用以上指标来衡量不同搜索引擎之间的稳定性时，主要是通过就计算不同搜索引擎之间针对同一查询在同一观察时间内所返回结果列表之间的差异度。其中，该表格中数值表示不同搜索引擎之间，针对同一用户意图类别查询而计算得到的平均值。从该表数据中可以看出，Yahoo搜索引擎分别与Baidu、Sogou搜索引擎之间的检索结果差异性较大，而Baidu与Sogou之间的查询结果之间差异性相对较小，说明了Yahoo所采用的排序原理与其他两搜索引擎所采用的排序原理差异较大，而Baidu与Sogou两搜索引擎所采用的排序规则相似度较大。从该表中还可以看出，针对导航类查询来说，各搜索引擎之间表现出的排序结果差异性低于其他两类查询。而对信息类查询来说，其各搜索引擎之间表现出来的排序结果差异性高于其他两类查询。 另外，图3表示不同搜索引擎之间对不同查询意图的M值，其中，X轴表示观察时间点，Y轴表示在同一观察点，不同搜索引擎之间对同类意图查询的平均M值，从该图中可以看出，不同搜索引擎之间针对不同意图类别查询的稳定性随时间均呈现下降趋势，且针对不同意图类别查询，Yahoo与另外两搜索引擎之间的稳定性程度随时间变化倾向于相同。以上现象说明了，随时间变化，不同搜索引擎之间的稳定性越来越低，且Yahoo与其他年搜索引擎之间的稳定性越来越相同。
图3 不同搜索引擎之间针对不同查询意图的M值 综合4.1节与4.2节实验分析可知，同一搜索引擎或不同搜索引擎之间对信息类查询的稳定性低于其他两类查询，其主要原因在于：相对导航类和事务类查询来说，信息类查询所包含更多的子主题[30]，随着时间变化，同一搜索引擎会融合不同结果网页以此来满足大众用户在特定时间对特定子主题的需求。因此，查询结果的稳定性就低于其他两类查询；而不同搜索引擎之间所关注信息类查询的主题不一样，因此，会采取不同排序算法为其不同子主题进行排序，不同搜索引擎之间针对此类查询的排序结果存在着差异性，其排序稳定性也相对较低。 5 总结与展望 本文以百度、雅虎和搜狗三搜索引擎为研究对象，以两个月为观察期，分析了搜索引擎针对不同意图类别查询的稳定性情况。首先，利用T[，url]和P[，url]两指标来衡量搜索引擎返回结果随时间的URL变化，在此基础上，笔者利用MWU(秩和检验)来验证不同意图类别查询之间的差异性。其次，利用M指标来验证搜索引擎返回结果的排序变化情况。最后，利用Spearman's footrule指标、Fagin's指标、G指标和M指标来衡量不同搜索之间的稳定性。其最终实验结果表明，相对导航类和事务类查询来说，同一搜索引擎或者不同搜索引擎之间对信息类查询的稳定性相对要低。另外，在三搜索引擎返回结果中，信息类与其他两类查询之间均存在着显著性差异。尽管如此，本文还存在着一些不足之处，以下三点将是今后要深入探讨的地方：一是笔者所选取的观察期为两个月，在将来工作中将会从更长的观察期来探讨此问题；二是笔者只探讨了搜索引擎针对信息类、导航类和事务类三类查询的稳定性，今后将会探讨搜索引擎针对更细致意图类别查询的稳定性情况；三是针对本文实验结果，笔者在后续工作中会将实验分析结果融合到检索排序算法中，以此对检索排序进行优化。
标签：搜索引擎论文; 搜狗论文; 搜索引擎原理论文; 相关性分析论文; 用户研究论文; 国外搜索引擎论文; 差异分析论文; 排序算法论文; 用户分析论文; 时间计算论文;
