第四代搜索引擎前沿综述刁轶夫3061401080 2010年5月1．介绍随着因特网的普及，网上信息的发展呈现两个基本的趋势：规模的爆炸性增长，覆盖领域的不断扩大。

如何在海量，非结构化信息中，提取对用户有用的信息是信息时代的核心课题。

搜索引擎正是通过对信息的自动搜集，索引，在用户发出请求时经过实时排序，为用户呈现其最有价值的信息。

由搜索引擎衍生而来的关键词广告产生了巨大的商业价值，并造就了谷歌、百度等互联网巨头。

但同时，谷歌以pagerank为核心的第三代搜索引擎已经不能满足日益增长的需求，数据量的增长和数据覆盖范围的增加迫切呼唤第四代搜索引擎。

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

2．搜索引擎发展历史及趋势2.1 搜索引擎发展历史从Lycos和Yahoo的时代到现在，搜索引擎的发展已经经过了三代。

Andrei[1]的文章中对前三代搜索引擎的特征做了描述：Google经过改进Pagerank和一系列技术，演化至第三代，而第四代搜索引擎有大量公司如Cuil,Quora探索，但还未形成成熟的产品。

下图援引自Google创始人论文[2]，说明第二代，第三代搜索引擎的主要原理：首先搜索引擎通过爬虫技术（Crawler），根据网页链接爬取互联网内容；然后建立倒排索引(Inverted Index)；同时通过Pagerank技术，基于random walk的思想计算出每个网页的Pagerank。

前面几步都是独立于用户查询进行的。

当用户提交查询关键词后，搜索引擎将首先对查询此进行分析（拼写建议，搜索建议，中文及日文等还需要分词），然后查询倒排索引，根据两项因素对网页文档排序：1，查询词语文档的匹配程度，主要通过TF-IDF 反映；2，网页的质量，通过预先算好的Pagerank反映。

其中，TF-IDF是第一代搜索引擎已经发展出来的技术。

2.2 现代搜索引擎的核心：PageRankGoogle推出后即风靡全球，其对搜索质量的提升，主要就在于Pagerank基于链接分析的排序技术，大大提高了搜索结果质量。

Pagerank自1998年提出至今10年时间，一直是第三代搜索引擎的核心，也经过了一定的改进。

在孟涛[3]的文章中，对于近年来Pagerank 的改进算法进行了较全面的综述。

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

如果网页Q被共m个Pi网页所链接，则其权值PR(Q)为其中（1-λ）称为缓冲因子，为从一个网页随机跳转到另一个网页的几率。

od pi为网页P i链向其他网页的链接数量。

若将所有的网页权值看作一个矢量，则Pagerank的矩阵表示为：Pagerank技术很好的利用了链接信息，并且能够较快收敛，因此取得了很好的的效果。

在之后，出现了pagerank技术的各种改进：Weighted Pagerank算法：Web中存在不同的块结构: Domain, Host, Directory，等等（Host最好）块内和块外的链接应该给不同的系数。

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

改进之后的计算公式网页到块系数块之间的权值矩阵网页间的权值矩阵(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,不一定需要用户隐私的细节来猜测用户兴趣，实际用更普遍的信息也可推测用户兴趣。

基于这两个观察，作者首先为用户建立了层次化的个人信息档案：第一分割后的用户兴趣档案：第二次分割后的用户兴趣档案：经过隐私划分的用户档案：通过这样的划分，用户可以通过调整上图中的minDetail参数来控制他可以暴露哪些隐私，从而使个性化搜索引擎可以根据这些隐私优化搜索结果。

上图中的expRation则反映了在minDetail水平下的隐私暴露程度。

4．社交搜索(Social Search)随着Facebook为代表的社交网站兴起，互联网用户通过网络进行社交的时间大大增加，并且在网络上留下了真实社交关系的数字表达，这使得利用社交关系改善搜索质量成为了可能。

如第2节所说，社交关系将从三个方面大大改善搜索质量。

4.1用户对网页评价改善搜索结果排序质量用户对网页的评价包括主动评价和行为暗示。

主动评价包括通过delicious收藏夹的评分，评论等，行为暗示则包括用户对网页的收藏等。

Shenghua Bao[5]通过delicious收藏夹的数据，进行了这方面的研究。

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

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

SSR算法：SPR算法：他们的结果显示，通过SSR和SPR建立的搜索引擎，更容易发现优质但是外链较少的网页。

比如这个网页/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的优势主要体现在：1，新用户需要通过原有用户的邀请才能加入，并且通过Facebook Connect登录，自然地在问答系统内形成了社交关系；同时由于初始用户都是硅谷的IT人士，因此从一开始就聚集了大量领域专家，保持了问答的水平。

2，由于社交关系的引入，即使系统并没有设置积分奖励，用户仍然十分活跃，他们的参与完全是因为对知识的渴望和分享的欲望，进一步保证了信息质量。