下载此文档

信息检索-链接分析.ppt


文档分类:IT计算机 | 页数:约52页 举报非法文档有奖
1/52
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/52 下载此文档
文档列表 文档介绍
第20讲 链接分析
Link Analysis
2017/10/31
提纲
上一讲回顾
锚文本
引用分析
PageRank
HITS: Hub节点&Authority节点
*
PPT课件
上一讲回顾
锚文本
篇文档都看成一个投票单位,引用可以看成是投票,然后计算一篇文档被投票的票数。当然这种方法不太精确。
在Web上: 引用频率=入链数
入链数目大并不一定意味着高质量...
... 主要原因是因为存在大量***链接…
更好的度量方法: 对不同网页来的引用频率进行加权
一篇文档的投票权重来自于它本身的引用因子
会不会出现循环计算?答案是否定的,实际上可以采用良好的形式化定义
*
PPT课件
*
PageRank的起源: 引用分析(3)
更好的度量方法: 加权的引用频率
这就是PageRank的基本思路
PageRank 最早起源于1960年代Pinsker和Narin提出的引用分析
引用分析不是小事情,在美国,任何教职人员的薪水取决于其发表文章的影响力!
*
PPT课件
上一讲回顾
锚文本
引用分析
PageRank
HITS: Hub节点&Authority节点
提纲
*
PPT课件
原始的PageRank公式
R(u)和R(v)是分别是网页u、v的PageRank值,Bu指的是指向网页u的网页集合、Nv是网页v的出链数目。
一个网页的PageRank等于所有的指向它的网页的PageRank的分量之和(c为归一化参数)。网页的每条出链上每个分量上承载了相同的PageRank分量。
*
PPT课件
PageRank的特点
一个网页如果它的入链越多,那么它也越重要(PageRank越高);
一个网页如果被越重要的网页所指向,那么它也越重要(PageRank越高) 。
类比: (1) 打电话; (2)微博粉丝
*
PPT课件
简单计算的例子(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.4
R(B)=0.2
A
B
C
0.4
0.2
0.2
0.4
0.2
0.4
0.2
*
PPT课件
简单计算的例子(c=1):迭代法求解
A
B
C
0.4
0.4
0.2
迭代次数
R(A)
R(B)
R(C)
0
1/3
1/3
1/3
1
1/3
1/6
1/2
2
1/2
1/6
1/3
3
1/3
1/4
5/12




收敛
2/5
1/5
2/5
R(A)=R(C)
R(B)=0.5R(A)
R(C)=R(B)+0.5R(A)
R(A)+R(B)+R(C)=1
*
PPT课件
转化成矩阵形式
令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)
*
PPT课件
一个稍微复杂的例子
A=
*
PPT课件
计算过程
则归一化后A =
R =
Normalized =
R=cATR,令c=1,解得
*
PPT课件
原始PageRank的一个不足
A loop:
图中存在一个循环通路,每次迭代,该循环通路中的每个节点的PageRank不断增加,但是它们并不指出去,即不将PageRank分配给其他节点!
*
PPT课件
一个例子
*
PPT课件
一个例子
*
PPT课件
一个例子
*
PPT课件
改进的PageRank公式
随机冲浪或随机游走(Random Walk)模型:到达u的概率由两部分组成,一部分是直接随机选中的概率(1-d)或(1-d)/N,另一部分是从指向它的网页顺着链接浏览的概率,则有
上述两个公式中,后一个公式所有网页PageRank的和为1,前一个公式的PageRank和为N(1-d)+d 。
可以证明,PageRank是收敛的。计算时,PageRank很难通过解析方式求解,通常通过迭代方式求解。d通常取0.85

*
PPT课件
PageRank面对的Spamm

内容来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数52
  • 收藏数0 收藏
  • 顶次数0
  • 上传人幻影
  • 文件大小1.27 MB
  • 时间2022-01-25