全球旧事资料 分类
稳向量(statio
aryvector)。
让我们来看一个例子。下图所示为一个网页集合(8个),箭头表示链接。
f其相应的矩阵为
这说明网页8的受欢迎程度最高。下图是阴影化的图,其中网页排序值越高的网页阴影越浅。
f计算平稳向量I
有很多方法可以找到一个方阵的特征向量。然而,我们面对的是一个特殊的挑战,因为矩阵H是一个这样的方阵,它的每一列都对应谷歌检索到的一个网页。也就是说,H大约有
250亿行和列。不过其中大多数的元都是0;事实上,研究表明每个网页平均约有10个链接,换言之,平均而言,每一列中除了10个元外全是0。我们将选择被称为幂法(powermethod)的方法来找到矩阵H的平稳向量I。
幂法如何实现呢?首先选择I的备选向量I0,进而按下式产生向量序列Ik
Ik1HIk
k012
这个方法是建立在如下的一般原理上:
一般原理:序列Ik将收敛到平稳向量I。
f我们首先用个例子验证上面的结论。
I0I1
100000000050500000
I2
0025005025000
I3
0016670025016670250083300833
I4
002780083300166701111018060097203333

I60
006006750030067500975020250180295
I61
006006750030067500975020250180295
一个自然的问题是,这些数字有什么含义。当然,关于一个网页的重要性,可能没有绝对的度量,而仅有比较两个网页的重要性的比例度量,如“网页A的重要性是网页B的两倍。”基于这一原因,我们可以用一个固定量去同乘以所有的重要性排序值,这并不会影响我们能获得的信息。这样,我们总是假定所有受欢迎程度值(popularity)的和为1,原因稍后解释。
三个重要的问题
自然而然产生的三个问题是:

序列Ik总是收敛吗?(即运算多次后,Ik和Ik1几乎是一样的)收敛后的平稳向量是否和初始向量I0的选取没有关系?重要性排序值是否包含了我们想要的信息?
f对目前的方法而言,上述三个的答案都是否定的!下面,我们将看看如何改进我们的方法,使得改进后的算法满足上述三个要求。
先看个非常简单的例子。考虑如下包含两个网页的小网络,其中一个链接到另一个:
下例展示了算法的运行过程:
I0
10
I1
01
I2
00
I3I
00
在这个例子中,两个网页的重要性排序值均为0,这样我们无法获知两个网页之间的相对重要性信息。问题在于r
好听全球资料 返回顶部