荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: bakey (猪朋狗友), 信区: Program
标  题: Web 超链分析算法纵览 zz
发信站: 荔园晨风BBS站 (Sat Jun 24 13:54:32 2006), 站内

http://www.knowlesys.com/research/paper/Web_PageRank.htm

WEB超链分析算法纵览


来源:搜索引擎排名研究

朱炜 王超 李俊 潘金贵

Abstract: The World Wide Web serves as a huge, widely distributed, global

information service center, and expanding in a rapid speed. It is import

to find the information the user need precisely and rapidly. In recent

years, researchers discovery that

rich and import information is contained among hyperlinks, and develop a

lot of algorithm using hyperlink to improve the quantity and relevance of

the results which search engine returned. This paper presents a review and

a comparison of such

algorithms existing now. Problems of these algorithms and directions to

further research will be discussed.

Keyword: PageRank,Authority,Hub,HITS,SALSA,Anchor


1.引言

   万维网WWW(World Wide

Web)是一个巨大的,分布全球的信息服务中心,正在以飞快的速度扩展。1998年WW

W上拥有约3.5亿个文档[14],每天增加约1百万的文档[6],不到9个月的时间文档总

数就会翻一番[14]。WEB上的文档和传统的文档比较,有很多新的特点,它们是分布的

,异构的,无结构或者半结构的,这

就对传统信息检索技术提出了新的挑战。


传统的WEB搜索引擎大多数是基于关键字匹配的,返回的结果是包含查询项的文档,

也有基于目录分类的搜索引擎。这些搜索引擎的结果并不令人满意。有些站点有意提

高关键字出现的频率来提高自身在搜索引擎中的重要性,破坏搜索引擎结果的客观性

和准确性。另外,有些重要的网页并

不包含查询项。搜索引擎的分类目录也不可能把所有的分类考虑全面,并且目录大

多靠人工维护,主观性强,费用高,更新速度慢[2]。

   最近几年,许多研究者发现,WWW上超链结构是个非常丰富和重要的资源,如果

能够充分利用的话,可以极大的提高检索结果的质量。基于这种超链分析的思想,Ser

gey Brin和Lawrence Page在1998年提出了PageRank算法[1] ,同年J.

Kleinberg提出了HITS算法[5],其它一些学者也相继提出了另外的链接分析算法,

如SALSA,PHITS,Bayesian等算法。这些算法有的已经在实际的系统中实现和使用,

并且取得了良好的效果。

   文章的第2部分按照时间顺序详细剖析了各种链接分析算法,对不同的算法进行

了比较。第3部分对这些算法做了评价和总结,指出了存在的问题和改进方向。


2.WEB超链分析算法


2.1 Google和PageRank算法

   搜索引擎Google最初是斯坦福大学的博士研究生Sergey Brin和Lawrence

Page实现的一个原型系统[2],现在已经发展成为WWW上最好的搜索引擎之一。Googl

e的体系结构类似于传统的搜索引擎,它与传统的搜索引擎最大的不同处在于对网页

进行了基于权威值的排序处理,使最重要的网页出现在结果的最前面。Google通过Pag

eRank元算法计算出网页的PageRank值

,从而决定网页在结果集中的出现位置,PageRank值越高的网页,在结果中出现的

位置越前。

2.1.1 PageRank算法

    PageRank算法基于下面2个前提:

   前提1:一个网页被多次引用,则它可能是很重要的;一个网页虽然没有被多次

引用,但是被重要的网页引用,则它也可能是很重要的;一个网页的重要性被平均的

传递到它所引用的网页。这种重要的网页称为权威(Authoritive)网页。

   前提2:假定用户一开始随机的访问网页集合中的一个网页,以后跟随网页的向

外链接向前浏览网页,不回退浏览,浏览下一个网页的概率就是被浏览网页的PageRan

k值。

   简单PageRank算法描述如下:u是一个网页,是u指向的网页集合,是指向u的网

页集合,是u指向外的链接数,显然=| | ,c是一个用于规范化的因子(Google通常取

0.85),(这种表示法也适用于以后介绍的算法)则u的Rank值计算如下:


进行了基于权威值的排序处理,使最重要的网页出现在结果的最前面。Google通过Pag

eRank元算法计算出网页的PageRank值

,从而决定网页在结果集中的出现位置,PageRank值越高的网页,在结果中出现的

位置越前。

2.1.1 PageRank算法

    PageRank算法基于下面2个前提:

   前提1:一个网页被多次引用,则它可能是很重要的;一个网页虽然没有被多次

引用,但是被重要的网页引用,则它也可能是很重要的;一个网页的重要性被平均的

传递到它所引用的网页。这种重要的网页称为权威(Authoritive)网页。

   前提2:假定用户一开始随机的访问网页集合中的一个网页,以后跟随网页的向

外链接向前浏览网页,不回退浏览,浏览下一个网页的概率就是被浏览网页的PageRan

k值。

   简单PageRank算法描述如下:u是一个网页,是u指向的网页集合,是指向u的网

页集合,是u指向外的链接数,显然=| | ,c是一个用于规范化的因子(Google通常取

0.85),(这种表示法也适用于以后介绍的算法)则u的Rank值计算如下:


2.1.2 算法的一些问题

   Google是结合文本的方法来实现PageRank算法的[2],所以只返回包含查询项的

网页,然后根据网页的rank值对搜索到的结果进行排序,把rank值最高的网页放置到

最前面,但是如果最重要的网页不在结果网页集中,PageRank算法就无能为力了,比

如在 Google中查询search

engines,像Google,Yahoo,Altivisa等都是很重要的,但是Google返回的结果中

这些网页并没有出现。 同样的查询例子也可以说明另外一个问题,Google,Yahoo是W

WW上最受欢迎的网页,如果出现在查询项car的结果集中,一定会有很多网页指向它

们,就会得到较高的rank值,

事实上他们与car不太相关。

    在PageRank算法的基础上,其它的研究者提出了改进的PageRank算法。华盛顿

大学计算机科学与工程系的Matthew Richardson和Pedro

Dominggos提出了结合链接和内容信息的PageRank算法,去除了PageRank算法需要的

前提2,增加考虑了用户从一个网页直接跳转到非直接相邻的但是内容相关的另外一

个网页的情况[3]。斯坦福大学计算机科学系Taher

Haveliwala提出了主题敏感(Topic-sensitive)PageRank算法[4]。斯坦福大学计

算机科学系Arvind Arasu等经过试验表明,PageRank算法计算效率还可以得到很大的

提高[22]。


2.2 HITS算法及其变种

   PageRank算法中对于向外链接的权值贡献是平均的,也就是不考虑不同链接的重

要性。而WEB的链接具有以下特征:

   1.有些链接具有注释性,也有些链接是起导航或广告作用。有注释性的链接才用

于权威判断。

   2.基于商业或竞争因素考虑,很少有WEB网页指向其竞争领域的权威网页。

   3.权威网页很少具有显式的描述,比如Google主页不会明确给出WEB搜索引擎之

类的描述信息。

   可见平均的分布权值不符合链接的实际情况[17]。J.

Kleinberg[5]提出的HITS算法中引入了另外一种网页,称为Hub网页,Hub网页是提

供指向权威网页链接集合的WEB网页,它本身可能并不重要,或者说没有几个网页指向

它,但是Hub网页确提供了指向就某个主题而言最为重要的站点的链接集合,比一个

课程主页上的推荐参考文献列表。一般

来说,好的Hub网页指向许多好的权威网页;好的权威网页是有许多好的Hub网页指

向的WEB网页。这种Hub与Authoritive网页之间的相互加强关系,可用于权威网页的发

现和 WEB结构和资源的自动发现,这就是Hub/Authority方法的基本思想。

2.2.1 HITS算法

2.2 HITS算法及其变种

   PageRank算法中对于向外链接的权值贡献是平均的,也就是不考虑不同链接的重

要性。而WEB的链接具有以下特征:

   1.有些链接具有注释性,也有些链接是起导航或广告作用。有注释性的链接才用

于权威判断。

   2.基于商业或竞争因素考虑,很少有WEB网页指向其竞争领域的权威网页。

   3.权威网页很少具有显式的描述,比如Google主页不会明确给出WEB搜索引擎之

类的描述信息。

   可见平均的分布权值不符合链接的实际情况[17]。J.

Kleinberg[5]提出的HITS算法中引入了另外一种网页,称为Hub网页,Hub网页是提

供指向权威网页链接集合的WEB网页,它本身可能并不重要,或者说没有几个网页指向

它,但是Hub网页确提供了指向就某个主题而言最为重要的站点的链接集合,比一个

课程主页上的推荐参考文献列表。一般

来说,好的Hub网页指向许多好的权威网页;好的权威网页是有许多好的Hub网页指

向的WEB网页。这种Hub与Authoritive网页之间的相互加强关系,可用于权威网页的发

现和 WEB结构和资源的自动发现,这就是Hub/Authority方法的基本思想。

2.2.1 HITS算法

   HITS (Hyperlink-Induced Topic Search)算法是利用Hub/Authority方法的

搜索方法,算法如下:将查询q提交给传统的基于关键字匹配的搜索引擎.搜索引擎返

回很多网页,从中取前n个网页作为根集(root set),用S表示。S满足如下3个条件:

   1.S中网页数量相对较小

   2.S中网页大多数是与查询q相关的网页

   3.S中网页包含较多的权威网页。

   通过向S中加入被S引用的网页和引用S的网页将S扩展成一个更大的集合T.

   以T中的Hub网页为顶点集Vl,以权威网页为顶点集V2,Vl中的网页到V2中的网页

的超链接为边集E,形成一个二分有向图SG=(V1,V2,E)。对V1中的任一个顶点v,

用h(v)表示网页v的Hub值,对V2中的顶点u,用a(u)表示网页的Authority值。开始时h

(v)=a(u)=

1,对u执行I操作修改它的a(u),对v执行O操作修改它的h(v),然后规范化a(u),

h(v),如此不断的重复计算下面的操作I,O,直到a (u),h(v)收敛。(证明

此算法收敛可见)

I 操作: (1) O操作: (2)

   每次迭代后需要对a(u),h(v)进行规范化处理:

   式(1)反映了若一个网页由很多好的Hub指向,则其权威值会相应增加(即权威值

增加为所有指向它的网页的现有Hub值之和)。式(2)反映了若一个网页指向许多好的权

威页,则Hub值也会相应增加(即Hub值增加为该网页链接的所有网页的权威值之和)。

   和PageRank算法一样,可以用矩阵形式来描述算法,这里省略不写。

   HITS算法输出一组具有较大Hub值的网页和具有较大权威值的网页。

2.2.2 HITS的问题

   HITS算法有以下几个问题:

   1.实际应用中,由S生成T的时间开销是很昂贵的,需要下载和分析S中每个网页

包含的所有链接,并且排除重复的链接。一般T比S大很多,由T生成有向图也很耗时

。需要分别计算网页的A/H值,计算量比PageRank算法大。

   2.有些时候,一主机A上的很多文档可能指向另外一台主机B上的某个文档,这

就增加了A上文档的Hub值和B上文档的Authority,相反的情况也如此。 HITS是假定某

一文档的权威值是由不同的单个组织或者个人决定的,上述情况影响了A和B上文档的

Hub和Authority值[7]。


3.网页中一些无关的链接影响A,H值的计算。在制作网页的时候,有些开发工具会

自动的在网页上加入一些链接,这些链接大多是与查询主题无关的。同一个站点内的

链接目的是为用户提供导航帮助,也与查询主题不甚无关,还有一些商业广告,赞助

商和用于友情交换的链接,也会降低H

ITS算法的精度[8]。

   4.HITS算法只计算主特征向量,也就是只能发现T集合中的主社区(Community

),忽略了其它重要的社区[12]。事实上,其它社区可能也非常重要。

   5.HITS算法最大的弱点是处理不好主题漂移问题(topic drift)[7,8],也就

是紧密链接TKC(Tightly-Knit Community

Effect)现象[8]。如果在集合T中有少数与查询主题无关的网页,但是他们是紧密

链接的,HITS算法的结果可能就是这些网页,因为HITS只能发现主社区,从而偏离了

原来的查询主题。下面讨论的SALSA算法中解决了TKC问题。

   6.用HITS进行窄主题查询时,可能产生主题泛化问题[5,9],即扩展以后引入了

比原来主题更重要的新的主题,新的主题可能与原始查询无关。泛化的原因是因为网

页中包含不同主题的向外链接,而且新主题的链接具有更加的重要性。

2.2.3 HITS的变种

   HITS算法遇到的问题,大多是因为HITS是纯粹的基于链接分析的算法,没有考虑

文本内容,继J. Kleinberg提出HITS算法以后,很多研究者对HITS进行了改进,提出

了许多HITS的变种算法,主要有:

2.2.3.1 Monika R. Henzinger和Krishna Bharat对HITS的改进

   对于上述提到的HITS遇到的第2个问题,Monika R. Henzinger和Krishna Bharat

在[7]中进行了改进。假定主机A上有k个网页指向主机B上的某个文档d,则A上的k个

文档对B的Authority贡献值总共为1,每个文档贡献1/k,而不是

HITS中的每个文档贡献1,总共贡献k。类似的,对于Hub值,假定主机A上某个文档t

指向主机B上的m个文档,则B上m个文档对t的Hub值总共贡献 1,每个文档贡献1/m。I

,O操作改为如下

I 操作: O操作:

   调整后的算法有效的解决了问题2,称之为imp算法。

    在这基础上,Monika R. Henzinger和Krishna Bharat还引入了传统信息检索的

内容分析技术来解决4和5,实际上也同时解决了问题3。具体方法如下,提取根集S中

的每个文档的前1000个词语,串连起来作为查询主题Q,文档Dj和主题Q的相似度按如

下公式计算:

,,=项i在查询Q中的出现次数,

=项i在文档Dj中的出现次数,IDFi是WWW上包含项i的文档数目的估计值。


在S扩展到T后,计算每个文档的主题相似度,根据不同的阈值(threshold)进行刷

选,可以选择所有文档相似度的中值,根集文档相似度的中值,最大文档相似度的分

数,如1/10,作为阈值。根据不同阈值进行处理,删除不满足条件的文档,再运行im

p算法计算文档的A/H值,这些算法分

别称为med, startmed,maxby10。

   在此改进的算法中,计算文档的相似度时间开销会很大。

2.2.3.2 ARC算法

   IBM Almaden研究中心的Clever工程组提出了ARC(Automatic Resource

Compilation)算法,对原始的HITS做了改进,赋予网页集对应的连结矩阵初值时结合了




的锚(anchor)文本,适应了不同的链接具有不同的权值的情况。

   ARC算法与HITS的不同主要有以下3点:

    1.由根集S扩展为T时,HITS只扩展与根集中网页链接路径长度为1的网页,也

就是只扩展直接与S相邻的网页,而ARC中把扩展的链接长度增加到2,扩展后的网页

集称为增集(Augment Set)。

    2. HITS算法中,每个链接对应的矩阵值设为1,实际上每个链接的重要性是

不同的,ARC算法考虑了链接周围的文本来确定链接的重要性。考虑链接p- >q,p中

有若干链接标记,文本1<a

href=”q”>锚文本</a>文本2,设查询项t在文本1,锚文本,文本2,出现的次数为

n(t),则w(p,q)=1+n (t)。文本1和文本2的长度经过试验设为50字节[10]。

构造矩阵W,如果有网页i->j

,Wi,j=w(i,j),否则Wi,j=0,H值设为1,Z为W的转置矩阵,迭代执行下面3个

的操作:

    (1)A=WH (2)H=ZA (3)规范化A,H

    3.ARC算法的目标是找到前15个最重要的网页,只需要A/H的前15个值相对大

小保持稳定即可,不需要A/H整个收敛,这样2中迭代次数很小就能满足,[10]中指出

迭代5次就可以,所以ARC算法有很高的计算效率,开销主要是在扩展根集上。

2.2.3.3 Hub平均( Hub-Averaging-Kleinberg)算法

   Allan Borodin等在[11]指出了一种现象,设有M+1个Hub网页,M+1个权威网页

,前M个Hub指向第一个权威网页,第M+1个Hub网页指向了所有M+1个权威网页。显

然根据

HITS算法,第一个权威网页最重要,有最高的Authority值,这是我们希望的。但是

,根据HITS,第M+1个Hub网页有最高的Hub值,事实上,第M+1个Hub网页既指向了

权威值很高的第一个权威网页,同时也指向了其它权威值不高的网页,它的Hub值不应

该比前M个网页的Hub值高。因此,

Allan Borodin修改了HITS的O操作:

O操作: ,n是(v,u)的个数

   调整以后,仅指向权威值高的网页的Hub值比既指向权威值高又指向权威值低的

网页的Hub值高,此算法称为Hub平均(Hub-Averaging-Kleinberg)算法。

2.2.3.4 阈值(Threshhold—Kleinberg)算法

   Allan Borodin等在[11]中同时提出了3种阈值控制的算法,分别是Hub阈值算法

,Authority阈值算法,以及结合2者的全阈值算法。

   计算网页p的Authority时候,不考虑指向它的所有网页Hub值对它的贡献,只考

虑Hub值超过平均值的网页的贡献,这就是Hub阈值方法。

   Authority阈值算法和Hub阈值方法类似,不考虑所有p指向的网页的Authority对

p的Hub值贡献,只计算前K个权威网页对它Hub值的贡献,这是基于算法的目标是查找

最重要的K个权威网页的前提。

   同时使用Authority阈值算法和Hub阈值方法的算法,就是全阈值算法。


2.3 SALSA算法

   PageRank算法是基于用户随机的向前浏览网页的直觉知识,HITS算法考虑的是Au

thoritive网页和Hub网页之间的加强关系。实际应用中,用户大多数情况下是向前浏

览网页,但是很多时候也会回退浏览网页。基于上述直觉知识,R. Lempel和S.

Moran提出了SALSA(Stochastic

Approach for Link-Structure Analysis)算法[8],考虑了用户回退浏览网页的情

况,保留了PageRank的随机漫游和HITS中把网页分为Authoritive和Hub的思想,取消

了Authoritive和Hub之间的相互加强关系。

   具体算法如下:

    1.和HITS算法的第一步一样,得到根集并且扩展为网页集合T,并除去孤立节

点。

    2.从集合T构造无向图G’=(Vh,Va,E)

    Vh = { sh |   s∈C and out-degree(s) > 0 } ( G’的Hub边).

2.3.1 BFS(Backword Forward Step)算法


SALSA算法计算网页的Authority值时,只考虑网页在直接相邻网页集中的受欢迎程

度,忽略其它网页对它的影响。HITS算法考虑的是整个图的结构,特别的,经过n步以

后,网页i的Authority的权重是,为离开网页i的的路径的数目,也就是说网页j<>i

,对i的权值贡献等于从i到j的路径的

数量。如果从i到j包含有一个回路,那么j对i的贡献将会呈指数级增加,这并不是

算法所希望的,因为回路可能不是与查询相关的。

   因此,Allan Borodin等[11]提出了BFS(Backward Forward

Step)算法,既是SALSA的扩展情况,也是HITS的限制情况。基本思想是,SALSA只

考虑直接相邻网页的影响,BFS扩展到考虑路径长度为n的相邻网页的影响。在BFS中,

被指定表示能通过路径到达i的结点的集合,这样j对i的贡献依赖就与j到i的距离。B

FS采用指数级降低权值的方式,结点i

的权值计算公式如下:

=|B(i)|+ |BF(i)| +|BFB(i)|+……+||

   算法从结点i开始,第一步向后访问,然后继续向前或者向后访问邻居,每一步

遇到新的结点加入权值计算,结点只有在第一次被访问时加入进去计算。


2.4 PHITS

   D. Cohn and H. Chang提出了计算Hub和Authority的统计算法PHITS(Probabi

listic analogue of the

HITS)[12]。他们提出了一个概率模型,在这个模型里面一个潜在的因子或者主题z

影响了文档d到文档c的一个链接,他们进一步假定,给定因子z,文档c的条件分布P(

c|z)存在,并且给定文档d,因子z的条件分布P(z|d)也存在。

   P(d) P(z|d) P(c|z) ,其中

   根据这些条件分布,提出了一个可能性函数(likelihood function)L,

,M是对应的连结矩阵

   然后,PHITS算法使用Dempster等提出的EM算法[20]分配未知的条件概率使得L最

大化,也就是最好的解释了网页之间的链接关系。算法要求因子z的数目事先给定。A

llan Borodin指出,PHITS中使用的EM算法可能会收敛于局部的最大化,而不是真正

的全局最大化[11]。D. Cohn和T.

Hofmann还提出了结合文档内容和超链接的概率模型[13]。


2.5 贝叶斯算法

   Allan

Borodin等提出了完全的贝叶斯统计方法来确定Hub和Authoritive网页[11]。假定有

M个Hub网页和N个Authority网页,可以是相同的集合。每个Hub网页有一个未知的实

数参数,表示拥有超链的一般趋势,一个未知的非负参数,表示拥有指向Authority网

页的链接的趋势。每个Authoritive网

页j,有一个未知的非负参数,表示j的Authority的级别。

   统计模型如下,Hub网页i到Authority网页j的链接的先验概率如下给定:

    P(i,j)=Exp(+)/(1+Exp(+))

   Hub网页i到Authority网页j没有链接时,P(i,j)=1/(1+Exp(+))

   从以上公式可以看出,如果很大(表示Hub网页i有很高的趋势指向任何一个网页

),或者和都很大(表示i是个高质量Hub,j是个高质量的Authority网页),那么i

->j的链接的概率就比较大。

   为了符合贝叶斯统计模型的规范,要给2M+N个未知参数(,,)指定先验分布

,这些分布应该是一般化的,不提供信息的,不依赖于被观察数据的,对结果只能产

生很小影响的。Allan

Borodin等在中指定满足正太分布N(μ,),均值μ=0,标准方差δ=10,指定和

满足Exp(1)分布,即x>=0,P(>=x)=P(>=x)=Exp(-x)。

   接下来就是标准的贝叶斯方法处理和HITS中求矩阵特征根的运算。

2.5.1 简化的贝叶斯算法

   Allan Borodin同时提出了简化的上述贝叶斯算法,完全除去了参数,也就不再

需要正太分布的参数μ,δ了。计算公式变为:P(i,j)=/(1+),Hub网页到Aut

hority网页j没有链接时,P(i,j)=1/(1+)。

   Allan Borodin 指出简化的贝叶斯产生的效果与SALSA算法的结果非常类似。


2.6 Reputation

   上面的所有算法,都是从查询项或者主题出发,经过算法处理,得到结果网页。

多伦多大学计算机系Alberto Mendelzon, Davood

Rafiei提出了一种反向的算法,输入为某个网页的URL地址,输出为一组主题,网页

在这些主题上有声望(repution)[16]。比如输入,www.gamelan.com,可能的输出

结果是“java”,具体的系统可以访问htpp://www.cs.toronto.edu/db/topic。

   给定一个网页p,计算在主题t上的声望,首先定义2个参数,渗透率和聚焦率,

简单起见,网页p包含主题项t,就认为p在主题t上。


是指向p而且包含t的网页数目,是指向p的网页数目,是包含t的网页数目。结合非

条件概率,引入,,是WEB上网页的数目。P在t上的声望计算如下:

   指定是既指向p有包含t的概率,即,显然有

   我们可以从搜索引擎(如Altavista)的结果得到,, ,WEB上网页的总数估计值

某些组织会经常公布,在计算中是个常量不影响RM的排序,RM最后如此计算:

    给定网页p和主题t,RM可以如上计算,但是多数的情况的只给定网页p,需要提

取主题后计算。算法的目标是找到一组t,使得RM(p,t)有较大的值。

TOPIC系统中是抽取指向p的网页中的锚文本的单词作为主题(上面已经讨论过锚文

本能很好描述目标网页,精度很高),避免了下载所有指向p的网页,而且 RM(p,t

)的计算很简单,算法的效率较高。主题抽取时,还忽略了用于导航、重复的链接的

文本,同时也过滤了停止字(stop

word),如“a”,“the”,“for”,“in”等。

   Reputation算法也是基于随机漫游模型的(random walk),可以说是PageRank

和SALSA算法的结合体。


3.链接算法的分类及其评价

   链接分析算法可以用来提高搜索引擎的查询效果,可以发现WWW上的重要的社区

,可以分析某个网站的拓扑结构,声望,分类等,可以用来实现文档的自动分类等。

归根结底,能够帮助用户在WWW海量的信息里面准确找到需要的信息。这是一个正在迅

速发展的研究领域。


上面我们从历史的角度总结了链接分析算法的发展历程,较为详细的介绍了算法的

基本思想和具体实现,对算法的存在的问题也做了讨论。这些算法有的处于研究阶段

,有的已经在具体的系统实现了。这些算法大体可以分为3类,基于随机漫游模型的,

比如PageRank,Repution算法,基于H

ub和

Authority相互加强模型的,如HITS及其变种,基于概率模型的,如SALSA,PHITS,

基于贝叶斯模型的,如贝叶斯算法及其简化版本。所有的算法在实际应用中都结合传

统的内容分析技术进行了优化。一些实际的系统实现了某些算法,并且获得了很好的

效果,Google实现了PageRank算法,I

BM Almaden Research Center 的Clever Project实现了ARC算法,多伦多大学计算

和SALSA算法的结合体。


3.链接算法的分类及其评价

   链接分析算法可以用来提高搜索引擎的查询效果,可以发现WWW上的重要的社区

,可以分析某个网站的拓扑结构,声望,分类等,可以用来实现文档的自动分类等。

归根结底,能够帮助用户在WWW海量的信息里面准确找到需要的信息。这是一个正在迅

速发展的研究领域。


上面我们从历史的角度总结了链接分析算法的发展历程,较为详细的介绍了算法的

基本思想和具体实现,对算法的存在的问题也做了讨论。这些算法有的处于研究阶段

,有的已经在具体的系统实现了。这些算法大体可以分为3类,基于随机漫游模型的,

比如PageRank,Repution算法,基于H

ub和

Authority相互加强模型的,如HITS及其变种,基于概率模型的,如SALSA,PHITS,

基于贝叶斯模型的,如贝叶斯算法及其简化版本。所有的算法在实际应用中都结合传

统的内容分析技术进行了优化。一些实际的系统实现了某些算法,并且获得了很好的

效果,Google实现了PageRank算法,I

BM Almaden Research Center 的Clever Project实现了ARC算法,多伦多大学计算

机系实现了一个原型系统TOPIC,来计算指定网页有声望的主题。

   AT&T香农实验室的Brian Amento在指出,用权威性来评价网页的质量和人类专家

评价的结果是一致的,并且各种链接分析算法的结果在大多数的情况下差别很小[15]

。但是,Allan

Borodin也指出没有一种算法是完美的,在某些查询下,结果可能很好,在另外的查

询下,结果可能很差[11]。所以应该根据不同查询的情况,选择不同的合适的算法。

   基于链接分析的算法,提供了一种衡量网页质量的客观方法,独立于语言,独立

于内容,不需人工干预就能自动发现WEB上重要的资源,挖掘出WEB上重要的社区,自

动实现文档分类。但是也有一些共同的问题影响着算法的精度。

    1.根集的质量。根集质量应该是很高的,否则,扩展后的网页集会增加很多

无关的网页,产生主题漂移,主题泛化等一系列的问题,计算量也增加很多。算法再

好,也无法在低质量网页集找出很多高质量的网页。

    2.噪音链接。WEB上不是每个链接都包含了有用的信息,比如广告,站点导航

,赞助商,用于友情交换的链接,对于链接分析不仅没有帮助,而且还影响结果。如

何有效的去除这些无关链接,也是算法的一个关键点。

    3.锚文本的利用。锚文本有很高的精度,对链接和目标网页的描述比较精确

。上述算法在具体的实现中利用了锚文本来优化算法。如何准确充分的利用锚文本,

对算法的精度影响很大。

    4.查询的分类。每种算法都有自身的适用情况,对于不同的查询,应该采用

不同的算法,以求获得最好的结果。因此,对于查询的分类也显得非常重要。


当然,这些问题带有很大的主观性,比如,质量不能精确的定义,链接是否包含重

要的信息也没有有效的方法能准确的判定,分析锚文本又涉及到语义问题,查询的分

类也没有明确界限。如果算法要取得更好的效果,在这几个方面需要继续做深入的研

究,相信在不久的将来会有更多的有趣

和有用的成果出现。


4.参考文献

1.L.Page , S.Brin , R.Motwani,and T.Winograd , ”The pageRank Citation

Ranking : Bringing Order to the WEB ” , January 1998.

and July 2001 at http://www.db.stanford.edu/~backub/PageRanksub.ps

2.Sergey Brin and Larry Page.The anatomy of a large-scale hypertextual

WEB search engine.In Proceedings of the Seventh International World Wide WEB


Conference, 1998

3.Matthew Richardson ,Pedro Domingos.The Intelligent Surfer: Probabilis

tic Combination of Link and Content Information in PageRank, volume 14.MIT

Press, Cambridge, MA, 2002.

4.Taher H. Haveliwala. Topic-Sensitive PageRank, in Proceedings of the

Eleventh International World Wide WEB Conference, 2002

5.J. Kleinberg. Authoritative sources in a hyperlinked environment. Proc

. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. Extended version in

Journal of the ACM 46(1999). Also appears as IBM Research Report RJ 10076

, May 1997

6.S. Chakrabarti, B. Dom, D. Gibson, J. Kleinberg, S.R. Kumar, P.

Raghavan, S. Rajagopalan, A. Tomkins, Hypersearching the WEB. Scientific

American, June 1999

7.Monika R. Henzinger and Krishna Bharat. Improved algorithms for topic

distillation in a hyperlinked environment. Proceedings of the 21'st

International ACM SIGIR Conference on Research and Development in IR, August
 199

13.D. Cohn, T. Hofmann, The Missing Link-A Probabilistic Model of

Document Content and Hypertext Connectivity. Advances in Neural Information

Processing Systems (NIPS)13, 2000

14.R.Baeza-Yates and B.Ribeiro-Neto,Moderm Information Retrieval,Addis

on Wesley,New York,NY,USA,1999

15.Brian Amento, Loren Terveen, and Will Hill. Does "Authority" Mean

Quality? Predicting Expert Quality Ratings of WEB Documents. 23rd Annual

International ACM SIGIR Conference on Research and Development in Informatio
n

Retrieval, 2000.

16.Alberto Mendelzon, Davood Rafiei, What do the Neighbours Think?

Computing WEB Page Reputations IEEE Data Engineering Bulletin, 23(3): 9-16,

September 2000

17.韩家炜,孟小峰,王静,李盛思,WEB挖掘研究,计算机研究与发展,Vol

38,No4,2001年4月

18.Google Inc. Google search engine. http://www.Google.com

19.Topic system,htpp://www.cs.toronto.edu/db/topic

20.A.Dempster,N.Laird,and D.Rubin, Maximun likelihood from incomplete

data via the EM algotithm,Journal of the Royal Statistical Society ,Series

B,39:1-38,1977

21.IBM Almaden Research Center Clever Project

http://www.almaden.ibm.com/cs/k53/clever.html

22.Arvind Arasu, Jasmine Novak, Andrew Tomkins, John Tomlin ,PageRank

Computation and the Structure of the WEB: Experiments and Algorithms, 11th

International World Wide WEB Conference, 2002.

(南京大学计算机软件新技术国家重点实验室,南京大学多媒体技术研究所)

--

我的个人主页: http://student.zsu.edu.cn/~is03kyh

开发日记: http://student.zsu.edu.cn/~is03kyh/publish/DevLog.html

RSS 订阅: http://student.zsu.edu.cn/~is03kyh/publish/rss/DevLog.xml

我的 Blog, 更新更快: http://192.168.48.19:8080/bbsblog?board=pudding

于是又有一个 DoNews 的: http://blog.donews.com/kyhpudding/

19.Topic system,htpp://www.cs.toronto.edu/db/topic

20.A.Dempster,N.Laird,and D.Rubin, Maximun likelihood from incomplete

data via the EM algotithm,Journal of the Royal Statistical Society ,Series

B,39:1-38,1977

21.IBM Almaden Research Center Clever Project

http://www.almaden.ibm.com/cs/k53/clever.html

22.Arvind Arasu, Jasmine Novak, Andrew Tomkins, John Tomlin ,PageRank

Computation and the Structure of the WEB: Experiments and Algorithms, 11th

International World Wide WEB Conference, 2002.

(南京大学计算机软件新技术国家重点实验室,南京大学多媒体技术研究所)


--
     心码合一,心中有代码,码中存我心;维码无心,心动即码动,代码表我心;
     维心无码,视万物皆空,知万千变化;无码无心,行如若无规,动全依所意


※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.149]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店