怎样求得 PageRank(2)

PageRank 的计算，就是求属于这个推移概率行列最大特性值的固有矢量(优固有矢量)。

这是因为，当线性变换系 t→∞ 渐近时，我们能够根据变换行列的"绝对价值最大的特性值"和"属于它的固有矢量"将其从根本上记述下来。换句话说，用推移概率行列表示的概率过程，是反复对这个行列进行乘法运算的一个过程，并且能够计算出前方状态的概率。

再者，虽然听起来很难,但是求特性值和固有矢量的值是能够严密分析的一种基础的数学手段。我们能够自由地给矢量的初始值赋值，但是因为不断地将行列相乘，得到的矢量却会集中在一些特定数值的组合中。我们把那些稳定的数值的组合称为固有矢量，把固有矢量中特征性的标量(scalar)称为特性值，把这样的计算方法总称为分解特性值，把解特性值的问题称为特性值问题。

(*注) 对 N 次的正方行列 A 把满足 Ax =λx 的数 λ 称为 A 的特性值，称 x 为属于 λ 的固有矢量。如果你怎么也不能适应行列的概念的话，你也可以考虑 N×N 的二元排列就可以了。同时，也可以把矢量考虑成为长度为 N 的普通的(一元)排列就可以了。

简单的例子
让我们用简单的例子来试着逐次计算 PageRank 。首先考虑一下有像下图表示那样的链接关系的7个HTML文件。并且，这些HTML文件间的链接关系只是闭合于这1-7的文件中。也就是说，除了这些文档以外没有其他任何链接的出入。另外请注意，所有的页面都有正向和反向链接(即没有终点)，这也是后面将提出的一个重要假定,在此暂且不深入探讨。
表示页面间互相链接关系的推移图

首先，把这张推移图图表构造的邻接列表表示为排列式，就有以下式子。即，根据各个链接源ID列举链接目标的ID。

链接源I D 链接目标 ID
1 2,3 ,4,5, 7
2 1
3 1,2
4 2,3,5
5 1,3,4,6
6 1,5
7 5
以这个邻接列表中所表示的链接关系的邻接行列 A 是以下这样的 7×7 的正方行列。一个仅有要素 0 和 1 位图行列(bitmap matrix)。横向查看第 i 行表示从文件 i 正向链接的文件ID。

A = [
0, 1, 1, 1, 1, 0, 1;
1, 0, 0, 0, 0, 0, 0;
1, 1, 0, 0, 0, 0, 0;
0, 1, 1, 0, 1, 0, 0;
1, 0, 1, 1, 0, 1, 0;
1, 0, 0, 0, 1, 0, 0;
0, 0, 0, 0, 1, 0, 0;
]
PageRank 式的推移概率行列 M ，是将 A 倒置后将各个数值除以各自的非零要素后得到的。即以下这个 7×7 的正方行列。横向查看第 i 行非零要素表示有指向文件 i 链接的文件ID(文件 i 的反向链接源)。请注意，各纵列的值相加的和为 1(全概率)。

M = [
0, 1, 1/2, 0, 1/4, 1/2, 0;
1/5, 0, 1/2, 1/3, 0, 0, 0;
1/5, 0, 0, 1/3, 1/4, 0, 0;
1/5, 0, 0, 0, 1/4, 0, 0;
1/5, 0, 0, 1/3, 0, 1/2, 1;
0, 0, 0, 0, 1/4, 0, 0;
1/5, 0, 0, 0, 0, 0, 0;
]
表示 PageRank 的矢量 R (各个的页面的等级数的队列)，存在着 R = cMR 的关系(c 为定量)。在这种情况下，R 相当于线形代数中的固有矢量，c 相当于对应特性值的倒数。为了求得 R ，只要对这个正方行列 M 作特性值分解就可以了。

在分解特性值时有相应的各种各样的数值分析法,但是本文将不在这里对各种方法详细说明，请读者自己去阅读一本恰当的教科书(在你的暑假里一定有这么一本被埋没的教科书)。在此，我们就暂且使用决 GNU Octave 这个计算程序实际计算一下特性值和固有矢量。

(*注) GNU Octave ，是支持数值计算，类似于描述性出色的 MATLAB 的编程语言。扩展后的处理语言更适合于行列演算,但基本上和C语言的语风相像，因此可读性很高。当然，除了Octave以外 MATLAB 和 Scilab 也是非常不错的语言，但是根据 GPL, Octave 是最容易得到的。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有