搜索引擎排名改进算法分析

搜索引擎排名改进算法分析

《农业网络信息》2005年第2期

搜索引擎排名改进算法分析

杨沅钊,吴薇,喻晓莉,杨国才

(西南农业大学信息学院,重庆400716)

摘要:近年来WEB上的信息量迅猛增长,信息日益丰富的同时却对有效信息的查询提出了严峻的挑战。面对用户对搜索结果准确性的日益苛求。本文对比分析两种最新的信息检索算法:TSPR算法和Hilltop算法,并就提高信息检索的有效性和准确性提出了新的方案。

关键词:搜索引擎;主题性页面级别算法;Hilltop算法中图分类号:TP3

文献标识码:B

文章编码:1672-6251(2005)02-0041-03

AnalyseofimprovedalgorithmforrankingsearchengineYANGYuan-zhao,WUWei,YUXiao-li,YANGGuo-cai

(Informationcollegeofsouthwestagriculturaluniversity,Chongqing400716,China)

Abstract:TheamountofinformationonWeb,increaseseveralmillionWEBpagesnewlyeverydayinrecentyears,andputforwardtheseverechallengetotheinquiryoftheeffectiveinformation.Inthisessay,ithasanalyzedtwoalgo2rithms:Topic-SensitiveandHilltop.Inaddition,anewschemehasbeputforwardtoimprovetheaccuracyandtheef2ficientofthealgorithmoftheengineinformationsearch.

Keyword:searchengine;Topic-SensitivePageRankAlgorithm;HilltopAlgorithm

1引言

Google曾对排名算法进行了一次业界称之为

2搜索引擎排名算法

研究搜索引擎排名算法,不能不介绍著名的

Google佛罗里达更新,这次更新被认为是搜索引擎历

PageRank算法,它的提出带来了搜索引擎革命性变

史上的一个重要里程碑。那些特意做了大量搜索引擎优化工作的网站管理员突然发现,花费的心思收效甚微甚至完全失效了。这对网站推广的人来说是个非常不利的消息,但对使用Google进行信息搜索的用户却

大大提高了信息搜索的效率。大家都想探究Google到底采用了什么新式"武器",导致了网站排名的重新洗牌,Google没有对此解释,但通过各种迹象表明,它采用的改进算法与以下两种算法紧密相关:HilltopAlgo2

rithm和Topic-SensitivePageRank。本文无意追究Google到底采用哪个算法,而是想通过对两种算法的

革,使人们将目光从注重信息收集的传统搜索引擎转向注重搜索结果准确性上的新一代搜索引擎身上。

PageRank算法描述已经众所周之,在此不在熬述,读

者可以参考相关文献。对于PageRank算法,若互联网上的资源具有同一主题,那么它可说是尽善尽美了。但互联网上的资源涵盖了无数的主题,而用户所寻找的是特定主题的信息,PageRank算法考虑了所有链接,但却忽视了链接页面的主题性。Google已试图将链接的文本内容计入排名算法来克服这一局限性。但精明的搜索引擎营销商却通过在网络上到处建立充盈关键词的链接来欺骗Google的排名算法,通过有偿交换和

交易一些来自较高"页面级别"页的链接,网站能够从毫不相关的站点购买或交易导入链接而使网站排名得到提升,这时PageRank技术已经无法为绝大多数查询条件提供高质量的搜索结果了。

2.1

Topic-SensitivePageRank算法

对比和分析,研究搜索引擎算法的发展动态和趋势。在本文中提出Hilltop和Topic-SensitivePageRank算法的综合型方案,并在试验测试中有优异的表现。目前搜索引擎这一领域仍在不断的发展之中,有着极高的研究价值和实用价值。

在PageRank算法的基础上,斯坦福大学计算机科

收稿日期:2004-11-15

作者简介:杨沅钊(1979-),男,硕士研究生,研究方向:信息技术。

—41—

搜索引擎排名改进算法分析

《农业网络信息》2005年第2期

Si=SUM{keyphrasesp

*

withk-iqueryterns}

学系TaherH.Haveliwala提出了主题敏感页面等级算法

2]

,在此把它译为主题性页面等级算法(TSPR),LevelScore(p)FullnessFactor(p,q)

Ifm<=2,FullnessFactor(p,q)=1

Ifm>2,Fullnessfactor(p,q)=1-(m-2)/plen

(4)(5)

它通过对随机查询用户的随机运动增加一个"偏差"来处理基本的PageRank算法所存在的问题。这个新的随机查询用户具有明确的查询目的,并更感兴趣于跟进那些具有某个特定主题的相关网页上的相关链接。这是一个相对而言较为新颖的思路,它解决了搜索结果的质量性方面的一系列关键性问题。

2.1.1

TSPR算法模型

算法模型描述:q表示查询短语;K表示查询短语中的关键词个数;先用一个三元组形式Si(S0,S1,S2)来计算专家页面的分值,Si表示有k-i个不满足查询短语中的关键词的分值,S0则包含了整个查询短语的情况,LevelScore(p)是定义好了的短语类型得分。

Sqd=

1

P(cj│rankq) ∑

1

j

jd

(2)

FullnessFactor(p,q)是对q中关键词覆盖了p中关键

词的数量的度量,plen为p的长度,m为p中不被q覆盖的关键词个数。因此最终通过如下公式计算出专家文档的分值:

Expert-Score=22.2.2

32

P(c) P(1│c)1

P(cj│aP(cj) ∏P(qi│cj)q)=1P(q)i

(3)

×S0+216×S1+S2(6)

以查询主题重要性得分Sqd为排列搜索结果的依据,rankid为Web上给定某类主题的文档页面集d的向量队列,q表示一个查询请求,我们定义一个q的子集q1;Cj表示ODPCategory;q1对于16个主题的级别都进行相应的计算;用q1i表示;则针对每一个ci,α是TSPR考虑了随机冲浪模型给定了一个相关参数。

2.1.2

TSPR算法存在的问题

TSPR算法仍然有一些亟待解决的问题,一是充

目标页面评分

目标页面T的计算步骤:对于选出来的每一个专家页面E,在他指向的目标页面T之间我们划上一条边edge(E,T),考虑下面关键词和边的限定关系:页面标题限定了所有专家页面链接出来的边;头部元素限制了所有的边,其相应的超链接在页面头部元素以后,在相等或者更重要的下一个标题以前发生的;锚文本限制相应的超链接的边;对于每一个查询关键词W,定义OCC(W,T)来表示E中中不同关键词短语的数目,它包含了W,也限定了edge(E,T),用Edge-Score(E,T)来表示edge(E,T)的分数。计算如下:

*如果对任意一个查询关键词OCC(W,T)是0,

分拓展主题的数量。在试验中选取了16类主题,这是远远不够的。每下一级子类,主题类的增加若干,运算量也呈指数级增长。这个代价是非常巨大的,必须有效的定义好主题类,适当拓展但也要有所顾忌。另外就是如何决定一个查询条件可能对应的主题,我们在对

TSPR算法测试中仍然发现这样的问题,对于关键词

那么Edge-Score(E,T)=0

*否则

Edge-Score(E,T)=Expert-Score(E)

keywordsw}

“Welfarefund”系统提交了很多动物福利基金的内容,对于“Architecture”搜索结果也将计算机体系结构罗列其中,对这些本身具有多主题性的关键词没有做出相应处理,导致了搜索范围的扩大,精确度的降低。

2.2

Hilltop算法

HillTop算法的指导思想和PageRank是一致的,

*Sum{queryOCC(w,T)(7)

去除了相关联或者隶属关系的目标页面,所有这些与该目标文档相链接的Edge-Score(E,T)之和就

是最终目标页面的分值,按这个分值顺序排列在搜索结果页面上。

如果有两个以上相关主题的网站链接到某网站,那么该网站在搜索结果中出现的机会会更大,如果…… 此处隐藏：3692字，全部文档内容请下载后查看。喜欢就下载吧 ……