姓氏：刁

2010年5月

此文是我大四的时候一篇课程论文，现在看来，自己做的事情还真跟这篇文章里写的关系很大。过段时间我想写写社交搜索与传统搜索在实现方法上的对比，所以把此文翻出来贴上。这里粘贴图片不方便，看有图片的版本，请下载：第四代搜索引擎前沿综述.pdf

最早发布于：http://www.newsmth.net/bbstcon.php?board=SearchEngineTech&gid=23434

1．介绍

随着因特网的普及，网上信息的发展呈现两个基本的趋势：规模的爆炸性增长，覆盖领域的不断扩大。如何在海量，非结构化信息中，提取对用户有用的信息是信息时代的核心课题。搜索引擎正是通过对信息的自动搜集，索引，在用户发出请求时经过实时排序，为用户呈现其最有价值的信息。

由搜索引擎衍生而来的关键词广告产生了巨大的商业价值，并造就了谷歌、百度等互联网巨头。但同时，谷歌以pagerank为核心的第三代搜索引擎已经不能满足日益增长的需求，数据量的增长和数据覆盖范围的增加迫切呼唤第四代搜索引擎。

我认为，第四代搜索将把个性化信息及人际推荐关系叠加到链接分析上，大大改善搜索结果排序效果；同时，跨媒体搜索将实现诸如用图片搜索图片等功能，打通文字，图片，视频，声音的界限，颠覆现在全部基于关键字的搜索方法，为用户带来更加直观的搜索体验。

2．搜索引擎发展历史及趋势

2.1 搜索引擎发展历史

从Lycos和Yahoo的时代到现在，搜索引擎的发展已经经过了三代。Andrei[1]的文章中对前三代搜索引擎的特征做了描述：

第一代：页面分析 仅使用页面内信息，文本信息，TF/IDF等
第二代：使用链接信息 链接分析，对搜索结果点击数据，链接文字
第三代：语义分析 拼写建议，关键词建议，关键词优化
第四代：正在发展 结合个性化数据，人际关系数据，跨媒体搜索

其中，第一代搜索引擎以早期Yahoo为代表，第二代以Google的创立为标志，之后Google经过改进Pagerank和一系列技术，演化至第三代，而第四代搜索引擎有大量公司如Cuil,Quora探索，但还未形成成熟的产品。

下图援引自Google创始人论文[2]，说明第二代，第三代搜索引擎的主要原理：



首先搜索引擎通过爬虫技术（Crawler），根据网页链接爬取互联网内容；然后建立倒排索引(Inverted Index)；同时通过Pagerank技术，基于random walk的思想计算出每个网页的Pagerank。前面几步都是独立于用户查询进行的。当用户提交查询关键词后，搜索引擎将首先对查询此进行分析（拼写建议，搜索建议，中文及日文等还需要分词），然后查询倒排索引，根据两项因素对网页文档排序：1，查询词语文档的匹配程度，主要通过TF-IDF反映；2，网页的质量，通过预先算好的Pagerank反映。其中，TF-IDF是第一代搜索引擎已经发展出来的技术。


2.2 现代搜索引擎的核心：PageRank

Google推出后即风靡全球，其对搜索质量的提升，主要就在于Pagerank基于链接分析的排序技术，大大提高了搜索结果质量。Pagerank自1998年提出至今10年时间，一直是第三代搜索引擎的核心，也经过了一定的改进。在孟涛[3]的文章中，对于近年来Pagerank的改进算法进行了较全面的综述。

Pagerank的算法的基本思想是通过网页间的互相引用（以链接形式表现），来区分出网页质量高低，类似论文的引用。

如果网页Q被共m个Pi网页所链接，则其权值PR(Q)为



其中（1-λ）称为缓冲因子，为从一个网页随机跳转到另一个网页的几率。odpi为网页Pi链向其他网页的链接数量。

若将所有的网页权值看作一个矢量，则Pagerank的矩阵表示为：



Pagerank技术很好的利用了链接信息，并且能够较快收敛，因此取得了很好的的效果。在之后，出现了pagerank技术的各种改进：

Weighted Pagerank算法：Web中存在不同的块结构: Domain, Host, Directory，等等（Host最好）块内和块外的链接应该给不同的系数。改进后公式：


Two-Layer PageRank算法: 经典PageRank算法认为网页之间均等，随机跳转在网页之间; 实际上存在网站和网页两极结构，应该修正马尔科夫模型到两级
�0�1 Block-Level PageRank算法: 网页可以细分到Block，各个块分量不一网页与Block之间互有链接。改进之后的计算公式
网页到块系数�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2 块之间的权值矩阵



网页间的权值矩阵(Z：块到网页的矩阵)





2.3 第三代搜索引擎的缺陷

基于链接分析的第三代搜索引擎呈现出以下几点局限性：

1，一个关键字查询词对所有用户呈现的搜索结果均相同。但是实际上，比如一个计算机用户搜索“树”可能指数据结构，与其他用户有很大区别。

2，Pagerank基于链接反映网页质量的方法，只反映了网页制作者对于网页质量的评价，并没有反映网页浏览着对于网页的评价。对于一些不善于进行链接优化的网站，虽然内容可能很优质，但是Pagerank可能并不高。同时，一些新网站很难在短期内提高Pagerank，而一些擅长优化技术的网站会用大量垃圾链接作弊。

3，基于关键词的搜索方法是建立在用户对于搜索有明确目的，并能清晰表述这种目的的假设上。但是实际上，用户的搜索引擎使用水平参差不齐；并且由于存在同义词等现象，同一个搜索请求有不同的表示方法，搜索结果也大为不同。

4，现在的图像搜索，视频搜索，音乐搜索也都是基于关键字，如图像Tag，音乐电影介绍等，而文字对于这些信息的表现能力是很有限的，也不直观。

5，并不是所有有价值的信息都能被搜索引擎爬取到，比如学校论坛，公司内网资料等有价值的资料就无法被搜索引擎检索，这叫做Hidden Web现象；同时一些信息需要经过人脑的加工，这方面问答平台更能胜任。这部分不能被爬取的信息实际上占了人类所有信息的大部分。


2.4 下一代搜索的趋势

此处的下一代搜索即指第四代搜索引擎，一个主要的变化是从信息检索(Information Retrieval)到信息推送（Information Supply）的转变，信息推送将主要通过个性化搜索和社交搜索实现。

第四代搜索将呈现出以下几个主要趋势：

1，个性化的搜索。基于个人的网页浏览历史，搜索关键词历史，个人档案信息，使得即使是同一个搜索关键词，也能为不同用户呈现不同的搜索结果。个性化搜索将基本解决2.3节提到的第一点局限。

2，社交搜索大大提高网页排序质量，其影响主要在两方面：a,网页浏览者（普通用户）对于网页的评价（收藏行为，评分，举报等）将可以作为排序的依据b,通过用户的社交圈推测用户兴趣，通过用户间的不同程度信任关系为其提供不同权重的网页排序推荐。社交搜索也包括问答系统，用优质的设置提高信息的质量。社交搜索将基本解决2.3节中提到的2，3，5中Pagerank和关键字搜索的局限。

3，跨媒体搜索将打通文字，图像，声音，视频间的界限，使得用图像搜图像，用声音搜声音，用图像搜视频等都成为可能。

本文的以下3，4，5节就将分别从个性化搜索，社交搜索，跨媒体搜索三个主要趋势进行探讨，并且尝试探讨基因搜索，移动搜索，情绪搜索。

3．个性化搜索（Personalized Search）

个性化搜索是搜索引擎根据用户搜索的历史记录，包括用户所搜索的关键词，在搜索结果中的点击情况，在各个网站的访问情况，书签情况等，然后对这些信息进行分析，在用户搜索新的关键词时，能返回更有针对性的搜索结果，从而提高用户体验

个性化搜索主要存在两个难点：a,搜索引擎怎样才能准确猜测用户在特定时间的搜索目的？人的需求是不断变更的，依据历史记录完全可能得出相差十万八千里的猜测。b,如何在利用用户信息为其提供个性化服务的同时，保护用户的隐私？

对于第二个问题，Yabo Xu[4]等人的文章中进行了有益的探讨。

首先，他们观察到两个有趣的现象：

a,如果能够提供个性化的服务，用户愿意牺牲一些隐私。

b,不一定需要用户隐私的细节来猜测用户兴趣，实际用更普遍的信息也可推测用户兴趣。

基于这两个观察，作者首先为用户建立了层次化的个人信息档案：

第一分割后的用户兴趣档案：�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2 第二次分割后的用户兴趣档案：

经过隐私划分的用户档案：

通过这样的划分，用户可以通过调整上图中的minDetail参数来控制他可以暴露哪些隐私，从而使个性化搜索引擎可以根据这些隐私优化搜索结果。上图中的expRation则反映了在minDetail水平下的隐私暴露程度。

4．社交搜索 (Social Search)

随着Facebook为代表的社交网站兴起，互联网用户通过网络进行社交的时间大大增加，并且在网络上留下了真实社交关系的数字表达，这使得利用社交关系改善搜索质量成为了可能。如第2节所说，社交关系将从三个方面大大改善搜索质量。


4.1用户对网页评价改善搜索结果排序质量

用户对网页的评价包括主动评价和行为暗示。主动评价包括通过delicious收藏夹的评分，评论等，行为暗示则包括用户对网页的收藏等。Shenghua Bao[5]通过delicious收藏夹的数据，进行了这方面的研究。

他们引入了两个评价指标及相应算法：SSR(SocialSimRank)评价搜索关键词和用户对收藏夹评价的关联性，SPR(SocialPageRank)揭示了网页在浏览者中的热度。



上面这个图揭示了通过SSR和SPR建立的搜索引擎的基本结构。

SSR算法：�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2�0�2 SPR算法：



他们的结果显示，通过SSR和SPR建立的搜索引擎，更容易发现优质但是外链较少的网页。比如这个网页http://37signals.com/papers/introtopatterns//index虽然内容很少，但是Pagerank为0，而SPR为10，这样有效的发掘出了内容优质但是不善于搜索引擎优化的网页，并且新网站也更容易得到推广。

但是Shenghua Bao等人的这篇论文也存在一定的局限性，首先数据集delicious仅有用户对网页的文字评论而没有评分，因此无法对网页质量进行较大区分。其次没有考虑不同的社交圈子对于网站的不同评价。另外可以做的提升就是对用户的评价进行opinion mining。



4.2 根据用户社交圈推测用户兴趣

一个社交圈子通常有相似的喜好，在社交关系的基础上，可以通过用户的社交圈子来推测其兴趣，从而有产生更准确的搜索结果。同时，用户之间可以建立信任关系，也可改善搜索效果。信任关系的应用比如如下情景：A是搜索引擎专家，B是一个本科生，B通过twitter与A建立了信任关系,同时A又通过delicious对很多搜索引擎研究网站进行了评价和打分；因此，B可以声称在搜索引擎领域对A十分信任，从而在B搜索此领域关键词时A推荐的网页将有更高的排序权重。

David [6]等人正是在此领域做了有益的探索：



4.3 高效的问答系统

问答系统是另一个高效的获取信息的渠道，我们熟知的问答系统包括百度知道，AskJeeves等，但是他们主要存在两个关键问题：1，问答者水平参差不齐，十分缺少领域专家的参与；2，通过积分奖励的办法并不能吸引有价值的回答，经常看到的回答都是互联网上的复制粘贴，而缺乏思考。

现在我发现的最好的问答系统是美国Quora.com:



Quora的优势主要体现在：1，新用户需要通过原有用户的邀请才能加入，并且通过Facebook Connect登录，自然地在问答系统内形成了社交关系；同时由于初始用户都是硅谷的IT人士，因此从一开始就聚集了大量领域专家，保持了问答的水平。2，由于社交关系的引入，即使系统并没有设置积分奖励，用户仍然十分活跃，他们的参与完全是因为对知识的渴望和分享的欲望，进一步保证了信息质量。3，良好的信息组织形式，包括类似wiki的用户自主建立，编辑Topic,每个Topic下有一系列问题，问题之间又通过Related Question联系起来。4，在现有Quora的信息架构上，未来还可以利用机器学习推测用户的话题喜好等。

5．跨媒体搜索 (Cross Media Search)

传统的文本、图像、音频和视频分析与检索技术都是相互独立的，缺乏面向多种媒体的跨媒体搜索技术。这些多媒体信息应用的发展，要求信息搜索“必须是跨媒体的，也就是说用户通过统一的界面和单一的提问，就能够获得以各种媒体形式存在的语义相似的结果。”为了提供支持多种检索方式和多模态用户信息需求的跨媒体检索，跨媒体搜索技术研究涉及海量多媒体数据的智能处理、多通道信息的融合和集成、快速准确的跨媒体索引等关键问题研究和应用。最终，跨媒体将打通图像，文字，声音，视频的界限，使得用图像搜图像，用声音搜声音，用图像搜视频等都成为可能。

Ritendra[7]等的文章探讨了图像搜索的发展，他们的主要目的是是的图片搜索更加直观，其中涉及的主要课题是图像特征的提取和图片相似度的计算。



6．其他趋势

Jeonghee Yi[8]等人发现在移动用户的搜索关键词通常在2.35个词，短于通过PC提交的关键词。另外移动用户的搜索集中在娱乐领域（44%）及旅游（7%）。移动互联网将是新的科技周期，如何根据移动设备的特点优化搜索将是重要的课题。同时基于地理位置的广告和聚会建议也大有可为。

生物信息的发展方兴未艾，测定大众基因序列有可能在近10年普及。当基因信息也可用时，个性化搜索将更有可为，比如根据基因的药物建议，餐饮建议等。

NLP的发展有助于更准确理解用户搜索意图。

7．总结

这篇文章回顾了搜索引擎的发展历史，提出第三代搜索引擎主要存在的弱点，主要是集中在搜索关键词表达性的局限，pagerank算法未考虑浏览着评价的局限，搜索呈现的单一。通过第四代搜索引擎技术的个性化搜索，社交搜索及跨媒体搜索，将有效解决这些问题，使搜索引擎交互方式更加友好，信息来源更加符合用户要求，信息质量更高。总之，第四代搜索引擎是一个激动人心的课题，并且有巨大的商业前景。

作者：222.184.28.*   回复：0   发表时间：2011-10-26 20:49:29