信息检索20-链接分析.ppt

《信息检索20-链接分析.ppt》由会员分享，可在线阅读，更多相关《信息检索20-链接分析.ppt（52页珍藏版）》请在三一办公上搜索。

1、第20讲 链接分析Link Analysis,2017/10/31,提纲,上一讲回顾 锚文本 引用分析 PageRank HITS:Hub节点&Authority节点,上一讲回顾 锚文本 引用分析 PageRank HITS:Hub节点&Authority节点,提纲,4,4,基本的采集过程,初始化采集URL种子队列；重复如下过程：从队列中取出URL下载并分析网页从网页中抽取更多的URL将这些URL放到队列中这里有个“Web的连通性很好”的基本假设,5,5,基本的采集架构,6,6,分布式采集器,7,7,Mercator采集器(待采集URL缓冲池),8,本讲内容,锚文本:Web上的链接相关信息为什

2、么对IR有用?,HITS:另一个著名的基于链接分析的排序算法(IBM),PageRank:一个著名的基于链接分析的排序算法(Google),引用分析(Citation analysis):PageRank及其他基于链接排序方法的数学基础,上一讲回顾 锚文本 引用分析 PageRank HITS:Hub节点&Authority节点,提纲,10,Web可以看成一个有向图,假设1:超链接代表了某种质量认可信号超链 d1 d2 表示 d1的作者认可 d2 的质量和相关性 假设 2:锚文本描述了文档 d2 的内容 这里的锚文本定义比较宽泛，包括链接周围的文本例子：“You can find cheap

3、cars a href=http:/here/a.”锚文本:“You can find cheap here”,11,d2中文本 vs.d2中文本+锚文本 d2,后者往往效果好于前者例子:查询 IBMIBM 的版权页匹配上很多作弊网页匹配上IBM的wikipedia页面可能与IBM 的主页并不匹配!也许 IBM 的主页上大部分都是图而按照 锚文本 d2 来搜索效果会比较好这种表示下，出现IBM最多的是其主页,12,指向的很多锚文本中包含IBM,13,对锚文本构建索引,因此，锚文本往往比网页本身更能揭示网页的内容在计算过程中，锚文本应该被赋予比文档中文本更高的权重,14,课堂练习：PageRan

4、k背后的假设,假设1:Web上的链接是网页质量的标志链出网页的作者认为链向的网页具有很高的质量假设2：锚文本能够描述链向网页的内容通常情况下假设1是否成立？通常情况下假设2是否成立？,15,Google炸弹(Google bomb),Google炸弹是指由于人为恶意构造锚文本而导致的结果很差的搜索2007年1月Google引入了一个新的权重计算公式来修正了很多Google炸弹的结果。但是还有不少没有解决:dangerous cult on Google,Bing,Yahoo一些厌恶 Church of Scientology的任何联合构建链接已解决的Google炸弹:dumb motherf,

5、who is a failure?,evil empire,上一讲回顾 锚文本 引用分析 PageRank HITS:Hub节点&Authority节点,提纲,17,PageRank的起源:引用分析(1),引用分析：科技文献中的引用分析一个引用的例子:“Miller(2001)has shown that physical activity alters the metabolism of estrogens.”可以把“Miller(2001)”看成是两篇学术文献之间的超链接在科技文献领域使用这些“超链接”的一个应用:根据他人引用的重合率来度量两篇文献的相似度，这称为共引相似度在Web上也存在

6、共引相似度：Google中提供的“find pages like this”或者“Similar”功能,18,PageRank起源:引用分析(2),另一个应用:引用频率可以用度量一篇文档的影响度最简单的度量指标：每篇文档都看成一个投票单位，引用可以看成是投票，然后计算一篇文档被投票的票数。当然这种方法不太精确。在Web上：引用频率=入链数入链数目大并不一定意味着高质量.主要原因是因为存在大量作弊链接更好的度量方法：对不同网页来的引用频率进行加权一篇文档的投票权重来自于它本身的引用因子会不会出现循环计算？答案是否定的，实际上可以采用良好的形式化定义,19,PageRank的起源:引用分析(3),

7、更好的度量方法:加权的引用频率这就是PageRank的基本思路PageRank 最早起源于1960年代Pinsker和Narin提出的引用分析引用分析不是小事情，在美国，任何教职人员的薪水取决于其发表文章的影响力！,上一讲回顾 锚文本 引用分析 PageRank HITS:Hub节点&Authority节点,提纲,21,原始的PageRank公式,R(u)和R(v)是分别是网页u、v的PageRank值，Bu指的是指向网页u的网页集合、Nv是网页v的出链数目。一个网页的PageRank等于所有的指向它的网页的PageRank的分量之和(c为归一化参数)。网页的每条出链上每个分量上承载了相同的P

8、ageRank分量。,22,PageRank的特点,一个网页如果它的入链越多，那么它也越重要(PageRank越高)；一个网页如果被越重要的网页所指向，那么它也越重要(PageRank越高)。类比:(1)打电话；(2)微博粉丝,23,简单计算的例子(c=1),R(A)=R(C)R(B)=0.5R(A)R(C)=R(B)+0.5R(A)R(A)+R(B)+R(C)=1解上述方程得：R(A)=R(C)=0.4R(B)=0.2,A,B,C,0.4,0.2,0.2,0.4,0.2,0.4,0.2,24,简单计算的例子(c=1)：迭代法求解,A,B,C,0.4,0.4,0.2,R(A)=R(C)R(B)

9、=0.5R(A)R(C)=R(B)+0.5R(A)R(A)+R(B)+R(C)=1,25,转化成矩阵形式,令R表示所有N个网页的PageRank组成的列向量，令网页间的连接矩阵L=lij，Pi有链接指向Pj时，lij=1，否则lij=0。对L的每行进行归一化，即用Pi的出度Ni去除得到矩阵A=aij，aij=lij/Ni，则有(AT表示A的转置矩阵)：R=cATR c-1R=ATR 根据线性代数中有关特征向量和特征值的理论，R是矩阵AT的c-1特征值对应的特征向量,R(A)=R(C)R(B)=0.5R(A)R(C)=R(B)+0.5R(A),26,一个稍微复杂的例子,A=,27,计算过程,则归

10、一化后A=,R=,Normalized=,RcATR，令c=1，解得,原始PageRank的一个不足,A loop:,图中存在一个循环通路，每次迭代，该循环通路中的每个节点的PageRank不断增加，但是它们并不指出去，即不将PageRank分配给其他节点！,一个例子,一个例子,一个例子,32,改进的PageRank公式,随机冲浪或随机游走(Random Walk)模型：到达u的概率由两部分组成，一部分是直接随机选中的概率(1-d)或(1-d)/N，另一部分是从指向它的网页顺着链接浏览的概率，则有,上述两个公式中，后一个公式所有网页PageRank的和为1，前一个公式的PageRank和为N(

11、1-d)+d。可以证明，PageRank是收敛的。计算时，PageRank很难通过解析方式求解，通常通过迭代方式求解。d通常取0.85,或,33,PageRank面对的Spamming问题,SEO(Search Engine Optimization)：通过正当或者作弊等手段提高网站的检索排名(包括PageRank)排名。因此，实际中的PageRank实现必须应对这种作弊，实际实现复杂得多。实际中往往有多个因子(比如内容相似度)的融合。,上一讲回顾 锚文本 引用分析 PageRank HITS:Hub节点&Authority节点,提纲,35,IBM的HITS算法,HITS(Hyperlink-

12、Induced Topic Search)每个网页计算两个值Hub：作为目录型或导航型网页的权重Authority：作为权威型网页的权重,36,Hub&Authority,Authority,Authority,Hub,37,例子,38,查询Chicago Bulls的权威网页,(Ben Shaul et al,WWW8),39,Chicago Bulls的权威网页,40,查询Chicago Bulls的导航型网页,(Ben Shaul et al,WWW8),41,Chicago Bulls导航型网页的例子,42,计算方法,一个网页被越重要的导航型网页指向越多，那么它的Authority越大

13、；一个网页指向的高重要度权威型网页越多，那么它的Hub越大。HITS算法也是收敛的，也可以通过迭代的方式计算。,A,H,43,HITS算法的实际计算过程,首先进行Web搜索；搜索的结果称为根集(root set)；(注：从搜索结果中选择一部分排名靠前的网页作为根集，也叫做种子集合)将所有链向种子集合和种子集合链出的网页加入到种子集合；新的更大的集合称为基本集(base set)；最后，在基本集上计算每个网页的hub值和authority值(该基本集可以看成一个小的Web图)。,根集和基本集(1),根集,根集和基本集(2),根集中节点链向的网页节点,根集,根集和基本集(3),指向根集节点的那些节

14、点,根集,根集和基本集(4),基本集,根集,基本集,48,根集和基本集(5),根集（注：种子集合）往往包含200-1000个节点基本集可以达到5000个节点,49,PageRank vs.HITS,网页的PageRank与查询主题无关，可以事先算好，因此适合于大型搜索引擎的应用。HITS算法的计算与查询主题相关，检索之后再进行计算，因此，不适合于大型搜索引擎。,50,本讲内容,锚文本:Web上的链接相关信息为什么对IR有用?,HITS:另一个著名的基于链接分析的排序算法(IBM),PageRank:一个著名的基于链接分析的排序算法(Google),引用分析(Citation analysis)

15、:PageRank及其他基于链接排序方法的数学基础,51,参考资料,信息检索导论第21章http:/ifnlp.org/irAmerican Mathematical Society article on PageRank(popular science style)Jon Kleinbergs home page(main person behind HITS)A Google bomb and its defusingGoogles official description of PageRank:PageRank reflects our view of the importance of web pages by considering more than 500 million variables and 2 billion terms.Pages that believe are important pages receive a higher PageRank and are more likely to appear at the top of the search results.,52,课后习题,