网络检索ppt课件.ppt
《网络检索ppt课件.ppt》由会员分享,可在线阅读,更多相关《网络检索ppt课件.ppt(46页珍藏版)》请在三一文库上搜索。
1、网络检索,李 柯 2010-12,搜索引擎的发展,第一代搜索引擎基于关键词的检索 第二代搜索引擎基于超链接的检索 第三代搜索引擎基于概念的检索,第一代搜索引擎,基于关键词的检索是利用关键词索引来获取文档,即整个文档的内容通过这些关键词进行表示,同样,用户的检索提问式也用一组关键词来表示。然后利用关键词将文档与提问式进行匹配,计算文档与提问式的相关程度。 布尔模型 向量空间模型 概率模型,第二代搜索引擎,基于超链接的检索也称链接分析,是搜索引擎面对网络这一动态环境,所采用的一种新的检索排序方法。 基本思想 PageRank算法 HITs算法,超链接分析的基本思想,主要是来自传统的文献计量学中的文
2、献引文分析。传统的文献引文分析认为,一篇学术论文的价值很大程度上体现在它被其他学术论文作为参考文献饮用的次数,即被其他学术论文引用得越多,这篇论文的价值就越高。 超链接分析充分利用了网络自身的超链接结构,提出了一个假设,即网页的重要性可用其他网页对其超链接的数量来衡量。,超链接分析的基本思想,一般地,我们把一个由网页A指向网页B的超链接理解为网页A中包含对网页B的引用,则超链接分析最简单直接的应用是:指向一个网页的超链接数目越多,则这个网页的重要性就越高。 也可以这样理解: 网页A指向网页B的链接 由网页A对网页B投了一票。,PageRank概念,PageRank(网页级别),2001年9月被
3、授予美国专利,专利人是Google创始人之一拉里佩奇(Larry Page)。 它是Google排名运算法则(排名公式)的一部分,是Google用于用来标识网页的等级/重要性的一种方法,是Google用来衡量一个网站的好坏的唯一标准。,PageRank概念,Google的PageRank根据网站的外部链接和内部链接的数量和质量来衡量网站的价值。PageRank背后的概念是,每个到页面的链接都是对该页面的一次投票,被链接的越多,就意味着被其他网站投票越多。这个就是所谓的“链接流行度”衡量多少人愿意将他们的网站和你的网站挂钩。 PageRank分值从0到10,PR值越高说明该网页越受欢迎。,Pag
4、eRank定义,基本思想:如果网页T存在一个指向网页A的连接,则表明T的所有者认为A比较重要,从而把T的一部分重要性得分赋予A。这个重要性得分值为: PR(T)/C(T)。 其中PR(T)为T的PageRank值,C(T)为T的出链数,则A的PageRank值为一系列类似于T的页面重要性得分值的累加。,PageRank定义,L.Page等人对PageRank的定义:,PR(A):表示网页A的PageRank值; C:为规范化因子,是保证所有网页的PR值总和为一常量; T1,T2,Tn :链接到网页A的其他网页; PR(Ti):网页Ti的PageRank值; C(Ti):网页Ti指向其他网页的超
5、链接数目。,PageRank定义,假设前提:即认为所有的网页形成一个牢固的链接图,每个网页都能从其他网页通过超链接到达。定义中给出的PR值都可以根据所有链接到它的网页的PR值除以各自向外的超链接数的商再进行求和。 假如一个人对网页上的超链接的点击是随机的,在牢固链接图的假设前提下,可以到达任一网页,只是到大的可能性大小不同。 显然,网页链入的超链接数越多,到达的可能性就越大,相应的PR值就越高。对于PR值高的网页链接到的网页,到达的可能性也就越大,其PR值也相应越高。,PageRank计算(一),利用PageRank的公式定义可以计算网页集合中所有网页的PR值。假设S为整个网页的总和,由于所有
6、网页的PR值开始都是未知的,我们进行平均分配,给每个网页的PR值都赋予1/S,再根据公式定义进行计算,然后对得到的值再次利用公式定义,这样循环反复,直到计算所得的PR值收敛于一个相对固定的值。 算法如下:,PageRank计算(一),任意 While for each ; ; ; for each ; ; ,PageRank计算(一),算法中PR(P)i表示进行i次循环计算后的PR值,C的计算是保证总PR值为1 L.Page等人通过实验,认为循环次数和链接数目是对数增长的。,PageRank计算(二),作为最基本的考虑方法,就是用行列式的形式来表达链接关系。从页面 i 链接到另一张页面 j 的
7、时,将其成分定义为1,反之则定义为 0 。即,行列阵 A 的成分 aij 可以用 aij 1 (从页面 i 向页面 j 有 链接的情况) 0 (从页面 i 向页面 j 没有链接的情况) 来表示。,PageRank计算(二),文件数用 N 来表示的话,这个行列阵就成为 NN 的方阵。这个相当于在图论中的“邻接矩阵”。也就是说,Web 的链接关系可以看做是采用了邻接关系有向图 S。总而言之,只要建立了链接,就应该有邻接关系。,PageRank计算(二),PageRank 的行列阵是把这个邻接行列倒置后(行和列互换),为了将各列(column)矢量的总和变成 1 (全概率), 把各个列矢量除以各自的
8、链接数(非零要素数)。这样作成的行列被称为推移概率行列,含有 N 个概率变量,各个行矢量表示状态之间的推移概率。倒置的理由是,PageRank 并非重视链接到多少地方而是重视被多少地方链接。,PageRank计算(二),一个典型化的例子,PageRank计算(二),归一化(全概率) A= 转置矩阵 A= AT=,PageRank计算(二),计算过程,PageRank计算(二),将 PageRank 的评价按顺序排列 名次 PageRank 文件ID 发出链接ID 被链接ID 1 0.304 1 2,3,4,5,7 2,3,5,6 2 0.179 5 1,3,4,6 1,4,6,7 3 0.16
9、6 2 1 1,3,4 4 0.141 3 1,2 1,4,5 5 0.105 4 2,3,5 1,5 6 0.061 7 5 1 7 0.045 6 1,5 5,PageRank计算(二),PageRank计算(二),ID=1的流入量(ID=2发出的Rank)+(ID=3发出的Rank)+(ID=5发出的Rank)+(ID=6发出的Rank) = 0.166+0.141/2+0.179/4+0.045/2 = 0.304 ID=2的流入量(ID=1发出的Rank)+(ID=3发出的Rank)+(ID=4发出的Rank= 0.304/5+0.141/2+0.105/3= 0.167 ID=3的
10、流入量(ID=1发出的Rank)+(ID=4发出的Rank)+(ID=5发出的Rank)= 0.304/5+0.105/3+0.179/4 = 0.141 ID=4的流入量(ID=1发出的Rank)+(ID=5发出的Rank= 0.304/5+0.179/4 = 0.106 ID=5的流入量(ID=1发出的Rank)+(ID=4发出的Rank)+(ID=6发出的Rank)+(ID=7发出的Rank) = 0.304/5+0.105/3+0.045/2+0.061 = 0.180 ID=6的流入量(ID=5发出的Rank= 0.179/4= 0.045 ID=7的流入量(ID=1发出的Rank=
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 网络 检索 ppt 课件
链接地址:https://www.31doc.com/p-3224227.html