族谱录LOGO

姓氏:

拼音:DIAO  

03-09

883604次

2人

33个

3630个

5041人

246部


[主楼] 四代搜索引擎前沿综述/刁轶夫

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

族谱录纪念网
 
发表回复:
标题:
 
内容:
粗体 斜体 下划线 插入超链接 插入图片
  您目前尚未登录,立即 登录 | 免费注册
 
 
验证码:   
 

注意:严禁发表任何含有侵害他人隐私、侵犯他人版权、辱骂、非法、有害、胁迫、攻击、骚扰、侵害、中伤、粗俗、猥亵、诽谤、淫秽、灌水、种族歧视、政治反动、影响和谐等内容的一切不良信息。经发现后将无条件删除,因此引起的一切后果由该内容发表者承担。请慎重发表!网站稳定来之不易,大家一起努力,共建和谐社区!