网络检索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=

11、 0.304/5 = 0.061,HITS算法,如果网页A指向大量的重要网页，那么A的建议就会变得有价值，如果A指向B，则说明B也是一个重要网页。 HITS算法是由康奈尔大学的Kleiberg博士于1998年首次提出， HITs的全称Hyperlink-Induced Topic Search，是基于链接分析的网页排名算法。,HITs算法,HITS算法描述两种类型的网页： 1） 权威型（Authority）网页，对于一个特定的检索，该网页提供最好的相关信息。 2）目录型（Hub）网页，该网页提高很多指向其他高质量权威型网页的超链接 。 由此，我们可以在每个网页上定义 “权威型权值”和 “目录型

12、权值”两个参数。,HITs算法,如果一个网页有大量的链接指向其他网页，则这个网也就可能是一个好的Hub；一个网页如果被大量的链接所指，那么它就可能是一个好的Authority。 HITS算法的基本思想 1）好的Hub型网页指向好的Authority网页 2）好的Authority网页是由好的Hub型网页所指向的网页,HITS算法,1）HITS通过搜索引擎查询主题词，生成初始网页集合，称为根集合。由于根集合中有些网页包含指向权威网页的链接，因此，对根集合进行网页扩展生成基集合，其中包括根集合指向的网页以及链接到根集合中的网页。 2）给基集合中的每个网页赋予一个Hub权值hp和一个权威权值ap，初

13、始值为同一个非负常数，然后对hp和ap进行运算。 ，其中网页q指向网页p ，其中网页q由网页p指向,HITS算法,通过迭代递归计算网页的Hub权值和权威权值 3）HITS输出与给定主题对应的一些具有较大Hub权值的网页和具有较大权威权值的网页，即重要的网页。,PageRank与HITS的比较,共同特点：PageRank和HITS的迭代算法都利用了特征向量作为理论基础和收敛性依据。 区别： 1）权值传播模型 2） 处理对象 3） 具体应用,PageRank与HITS的比较,从两者的权值传播模型来看： PageRank基于随机冲浪模型将网页权值直接从Authority网页传递到Authority网

14、页。 HITS将Authority网页的权值经过hub网页的传递进行传播。,PageRank与HITS的比较,从两者的处理对象来看： 都是针对整个Web上的网页的一个自集进行排序、筛选，没有一个搜索引擎能够将整个Interent上的网页全部搜索下来。但是 PageRank的处理对象是一个搜索引擎当前搜索下来的所有网页，一般在几千万个页面以上。 HITS的处理对象是搜索引擎针对具体查询主题所返回的结果，从几百个页面扩展到几千几万个页面。,PageRank与HITS的比较,从两者的具体应用来看： PageRank应用于搜索引擎服务端，可以直接用于关键字查询并获得较好的结果；若要用于全文查询，需要与

15、其他相似度判定标准（向量模型等）进行复合，以针对具体查询形成最终排名。 HITS一般用于全文搜索引擎客户端，对宽主题的搜索相当有效，可以用于自动编撰Web分类目录，通过找到指向某网页的Hub网页并以此为根集，可以查到该网页的相关网页；对于较窄主题的检索，HITS的能力还较弱，因为根集太小，筛选的效果将不会很好。,PageRank与HITS的比较,总之， PageRank算法和HITS算法是具有代表性的两个网页排序算法，前者更适合于搜索引擎的服务器端，后者更适合于搜索引擎的客户端。 PageRank算法和HITS算法为发现核心网页与网页之间的关系提供了基本的思路和方法。,第三代搜索引擎,目前搜索

16、引擎基本上都采用基于关键词匹配的全文检索技术，使得检索效果未能实现质的飞跃，发展知识化、智能化的搜索引擎成为必然趋势，概念检索是关键技术之一。,第三代搜索引擎,概念是关于具有共同属性的一组对象、事件或符号的知识，是客观事物在头脑中的反映，要通过字、词、词组等概念描述元素表达出来。 同一个概念可以由多个描述元素来表达，这些描述元素在此概念的约束下构成了同义关系。 概念并不是独立存在的，一个概念总是与其他概念之间存在着关系，根据概念之间的相互联系，形成的是语义的关系网。,第三代搜索引擎,同义词扩展：自行车脚踏车单车 语义蕴涵扩展：操作系统计算机软件应用软件 语义相关扩展：微软微软视窗Window

17、NT,第三代搜索引擎,概念检索是通过对文档原文信息进行语义上的自然语言处理，析取出各种概念信息，形成一个知识库，从概念意义层次上来处理用户的检索提问式，不仅能检索出包含提问式中的关键词的结果，还能检索出包含那些与该词同属一类概念的词汇的结果。,第三代搜索引擎,概念检索是能够利用信息的语义知识，“理解”用户的检索需求，通过知识学习，分析理解和推理归纳来实现检索的“智能化”，突破关键词匹配局限于表面形式的缺陷。,第三代搜索引擎,构建概念语义网络 概念语义网络可以看做一个带标识的分类树。节点表示概念，节点之间的连线表示概念之间的关系：其中实线表示概念之间的内涵和外延上的竖向层次关系，虚线表示相关概念

18、之间的横向联系。 A 计算机软件 计算机厂商 应用软件 操作系统 国外厂商 国内厂商 微软视窗 微软 ,第三代搜索引擎,概念检索的具体实现： 概念节点是语义网络的基本元素，属性描述如下：,第三代搜索引擎,struct Concept char number; /概念意义分类代码 char name; /概念意义描述 int fathnum; /父概念个数 int bronum; /兄弟概念个数 int sonnum; /下层概念个数 int relnum; /相关概念个数 char * synonym; /指向该概念的集合的指针 struct Concept *father; /指向父概念的指

19、针 struct Concept *brother; /指向所有兄弟概念的指针 struct Concept *son; /指向所有子概念的指针 struct Concept *relation; /指向所有相关概念的指针 ,第三代搜索引擎,其中概念意义分类代码（number）由数字和层次分隔符组成，即n1.n2.n3。数字对应着该层次的概念，每层之间用“.”隔开，层次顺序从左到右依次为第一、二、 三层。若某层次数字为“0”，表示该层不存在。这样代码可以明确反映出概念在分类体系中的位置，所有代码组成了对分类树的完整描述。,第三代搜索引擎,同义词扩展检索的实现 将文档网页进行分词处理，把所有概念

20、描述元素统一进行概念意义分类标注。然后对标识进行索引，生成倒排索引文件。当用户输入检索提问式时，也同样对其进行概念意义分类标注，将其作为检索入口，查找标识符索引文件，便可以得到检索结果。,第三代搜索引擎,语义蕴涵和外延扩展检索的实现 1）若为最高层节点，对其进行细化操作（find-son）则为蕴涵扩展检索；对其进行平级扩展操作（find-brother）则为外延扩展检索。 2）若为非终端节点，对其进行细化操作（find-son）则为蕴涵扩展检索；对其进行平级扩展操作（find-brother）和泛化操作（find-father）则为外延扩展检索。 3)若为叶节点，对其进行平级操作（find-brother）和泛化操作（find-father）则为外延扩展检索。,第三代搜索引擎,语义相关扩展检索的实现 在概念节点定义中，relation是指向与当前概念语义相关的相关概念集合的指针。对当前概念进行相关扩展操作（find-relationship），便能实现语义相关扩展检索。,Thanks,