|
越来越发现自己学习太不深入了，什么都只懂点皮毛，对于别人的思想没有理解透彻，看来学习还是要深入的，别人的东西要完全理解才能变成自己的。最近开始研究机器学习的算法，今天心血来潮看了下PageRank,思想还是比较简单的，可是要把思想完全理解并用算法实现，对于我这个菜鸟还是花了点时间的。
1.PageRank思想简介
互联网中的页面是以页面的PageRank来判断其重要性的，值越大越体现其重要性。而页面之间是相互联系的，一个页面可能被多个页面链接，一个页面也可能指向多个页面，从而形成了一个有向图，页面表示有向图的顶点，有向边表示链接，w(i,j)=1表示页面i存在指向页面j的超链接，否则w(i,j)=0。如果页面A存在指向其他页面的超链接，就将A的PageRank的份额平均地分给其所指向的所有页面，一次类推。虽然PageRank会一直传递，但总的来说PageRank的计算是收敛的，下面给出其迭代公式（1-1）：
PRn(A)=(1-d)+d*（∑PRn-1(Ti)/C(Ti)）（1-1）（页面的初始PageRank均设为1）
%PRn(A)
表示页面A的n次迭代后的PageRank,PRn-1(Ti) 表示页面Ti的n-1的PageRank。
%C(Ti)
表示页面Ti的链接数。
%d
表示阻尼系数（0
算法思想来源 http://wenku.baidu.com/view/e226710e52ea551810a6873d.html
2.PageRank算法描述
实际应用中可以采用幂法来计算PageRank，假如总共有m个页面，计算如（1-2）所示：
r=A*x（1-2）其中A=d*P+（1-d)*(e*e'/m)
%r表示当前迭代后的PageRank，它是一个m行的列向量,x是所有页面的PageRank初始值。
%P由有向图的邻接矩阵变化而来，P'为邻接矩阵的每个元素除以每行元素之和得到。
%e是m行的元素都为1的列向量。tyuuyuyfuu
幂法计算过程如下：
x<--任意m行列向量;
r=A*x;
if(||r-x||
return r；%r为最终的PageRank
else
x=r;goto 2；
3.PageRank算法的maltab实现代码
%pagerank
P1=[0 1 1
0;0 0 0 1; 1 0 0 0;1 1 1 0];%链接的有向图的邻接矩阵表示
P=[];
[n,n]=size(P1);%n表示页面数
for
i=1:n
P=[P;P1(i,:)/sum(P1(i,:))];%将M1的数据除以每行数据之和
end
d=0.5;%阻尼系数
sigma=0.0001;%收敛阈值
e=ones(n,1);
A=d*P'+(1-d)*((e*e')/n);
%x=ones(n,1);
x=rand(n,1)
%页面的pagerank初始值
r=A*x;%pagerank的计算公式
while(norm(r-x)>=sigma);%判断是否收敛
x=r;
r=A*x;
end
r
%收敛之后得到最后的pagerank，并输出
输出结果：
x =
0.7431
0.3922
0.6555
0.1712
r =
0.5568
0.4640
0.4640
0.4773
另一组结果如下：
x =
0.7060
0.0318
0.2769
0.0462
r =
0.3011
0.2509
0.2509
0.2581
通过结果发现页面的重要性与PageRank的初始值无关，虽然当x不同时，得到的r的值也不同，但是页面的重要性排序保持不变。
4.总结
在理解PageRank算法时，对于其中的数学公式我进行了分析，明白了r=A*x的意义，也明白了为什么A的取值是那样的。下面的将自己的理解介绍如下：
r=A*x=d*P*x+(1-d)*(e*e'/m)*x (1)
PRn(A)=(1-d)+d*（∑PRn-1(Ti)/C(Ti)）
(2)
P1表示有向图的邻接矩阵，P1的第i行中的非零元素表示页面i中链接页面，第j列中的非零元素表示指向页面j的页面，将P1的每个元素除以每行元素之和转置得到P，P的第i行元素表示的就是指向页面i其他页面给页面i的PageRank份额1/C(Ti)。用矩阵表示就是d*P*x，结果也就是（2）的后部分值。而（1）中的后部分表示的是每个页面分出d份额的PageRank之后的PageRank，为了表示成矩阵形式才有了(e*e')/m的表达，这一部分的矩阵表示也就是（2）中的1-d。
还有一个论文(http://www.cnblogs.com/FengYan/archive/2011/11/12/2246461.html)介绍PageRank,主要思想都差不多，上面的思想用到了阻尼系数d,就相当于这个论文中的C，而论文中的逃脱因子E（E(i)表示第i个网页的逃脱因子）是为了解决Rank
sink，我觉得类似与上面的（1-d)*(e*e'/m)*x，对于这一点比较我不是很确定。
总的来说，对于PageRank还算进行了比较深入的了解。对于海量页面数的相关处理是实际问题的难点，由于我对于分布式处理几乎是0基础，所以还有待好好学习。
|
