浅析PageRank(公式篇2)

飞烟步尘

浏览: 23812 次
性别:

最近访客更多访客>>

Teasue

Captainwsj

x影千绝

liushiyan2000

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

云计算

上公式~~~PageRank最开始一个版本的公式：

最基本的概念这里不再赘述，对公示稍加解释：页面A的PR是由页面B、C、D一起贡献的，每个页面贡献给A的大小由各自链出数目决定，如果B有五个链出，PR(B)=10，那么就有2的值给A。q是阻尼因子，指代浏览者沿着当前链接继续阅读的可能性，每个页面都有一个最小值1-q，PR中q=0.85。

接下来，用实例说明：(为了使计算简单明了，实例中的页面无外部的链入和链出，实际PR算法的设计也是依据将互联网看做一个整体，只有内部成员间的连接，无外部链接)

自己随意画了一个关系图，箭头代表A、B、C页面间的联系(为使矩阵运算简单可观，这里只列出三个页面)。

由图可以看出，它们之间的关联以及构造的矩阵如下(不懂怎么构造矩阵的去看公式篇1，不再解释~~)：

(赤果果的word图，好难看啊~)然后我们沿着之前说过的思路，将矩阵进行转置和概率化，结果如下：

对如图概率化后的矩阵求解特征值和相对应的特征向量，解得最大特征值所对应特征向量中的原素即为各页面的PR值。这里我们从数学思想与PR公式两个角度进行计算，以验证结果的有效性。

1、数学实现

通过公式Ax=kx(详细求解过程与思路1中都已经介绍，这里给出大体思路和结果)，其中k为特征值，x为特征向量。求解特征值时，根据(A-kE)x=0，E为与A同型的单位矩阵，即求|A-kE|=0，经计算可得 -k³+1/4k=0，因为数学中的前提是 k≠0，所以k=1/2，解得特征向量为p=(1,1,2)^T，可以得所有的mp( m≠0)均为特征值1/2的特征向量。

2、公式

由公式PR(A)=(PR(B)/L(B)+PR(C)/L(C))*0.85+0.15，假设A、B、C的初始PR均为1，那么通过代入公式，进行第一次求值可得PR(A)=0.575，PR(B)=0.394375，PR(C)=0.7119844(注：在这里计算的时候取的精度为float，与以下代码中使用的相同，也就是精确到小数点后7位)。再将第一次得出的值代入公式进行第二次计算，可得PR(A)=0.31760937，PR(B)=0.284984，PR(C)=0.5561022，重复代入的步骤进行计算，这里不列出全值，但是通过观察结果可以看出，一直到第11次开始，A、B、C三者的PR值保持了一致，不再随计算的重复性变动，当然这里的精确度达到了小数点后的7位，如果对精确度的要求更低，运算的次数会大大减少，比如对精度的要求是小数点后2位，那么计算到第4次便达到了要求。最终的稳定结果是PR(A)=0.26086956，PR(B)=0.26086956，PR(C)=0.5217391。

将公式计算的结果与数学方法所求的值相比可以看出，数学实现的结果中存在的关联关系PR(A)=PR(B)=1/2*PR(C)与通过公式计算的结果PR(A)=0.26086956，PR(B)=0.26086956，PR(C)=0.5217391有着高度的一致性,因此，这两种方法在思路上是统一的。

由这个例子，我们可以再回过头来分析阻尼因子q的作用。Sample中出现了一个比较特殊的情况，C页面只有链入没有链出，也就是说迭代时A，B的值不断传入C，C却不为PR的传播做任何贡献，这必然会导致有限次计算后全网的PR趋于0。加入阻尼因子后，我们看到，计算的结果并未受这一情况的影响，网页间实际PR的计算依然与模型一致，这就是概念篇中提到过的消除值沉淀问题。

这里还有一个很重要的问题要说明：Brin与Page的设计中，证明无论如何取初值，计算结果都会收敛到一个固定的值，之前的计算中取得初值全为1，此时我们验证一下这个说法的正确性。令PR(A)=1，PR(B)=2，PR(C)=3，运算后在第12次、float精度下趋于稳定；令PR(A)=60，PR(B)=70，PR(C)=80，运算在第14次、float精度下趋于稳定；令PR(A)=100，PR(B)=500，PR(C)=1000，运算在第15次、float精度下趋于稳定…………从例子中可以看出，不论初值如何取，最终的计算结果都会趋于一个稳定值，当然这些稳定值也是相等的，区别则是当选取了一个合理的初始值，会使得计算的次数减少，这里只是一个三维矩阵的计算，差距可能不够明显，实际操作中面对几十亿的网页数量这种操作的时间差是不可忽视的。从这些计算值中，可以看出运算次数在随着初始值的增加而增加，个人猜测这或许也是Google将网页排名定为0~10的一个原因，如果将几十的初始值放入十亿单位的网页操作，计算量应该相当的惊人。

本来想进行一下随着维度增加，运算时间变化的分析，但实现过程中发现这个运算时间的影响因素太多，比如电脑运算的即时性、录入矩阵的复杂度等，使得运算之变化幅度很大，维度之间差距也不够明显，尤其是矩阵内部链接复杂度对运算影响非常大，一个简单的四维矩阵可以比上文例举的三维矩阵算短一半时间，复杂的四维花费又变成了一倍，因此这里不列出数据进行对比，感兴趣的话可以自行研究~但是可以确定的是，这个时间量的增加并不是线性的，当维度增加n，行的遍历增加n，列的遍历也增加了n,额外增加的数据其实是n²个，三位矩阵的耗时为28毫秒(取大致的平均值),那么可以假设同等复杂度的维度是1亿的矩阵为28/9*10¹⁶毫秒，这还不考虑多耗费的用于创建临时变量以及数组的时间。同时我们可以估算出来，此时初始值有10⁸个，400MB的数据是可以接受的，但矩阵里面的数据有10^8*10⁸个元素，每个float型占4Byte，也就是需要4*10^8*10⁸B，等同于40000TB……这需要多么庞大的存储空间啊……

讨论过了理论，我用java的方法模拟一下PR值的计算过程,具体的描述代码中都写出来了，使用的思路和上述Sample一样，只不过代码中是直接从选定的文件中读入初始PR值以及矩阵元素(文件中的书写顺序是：第一行为各个初始的PR值，接下来是矩阵，每行的元素之间通过,分隔，行与行之间无分隔符)，然后进行转置、概率化、公式重复求解（这份新代码修改了一个计算上的失误，也增加了随机生成一个矩阵的方法，节省了手工录入矩阵的时间。其中矩阵维度就是矩阵的大小，初始值为初始的PR值，复杂度指代连接中有百分之多少多少为1，当然，这里的复杂度只是取最简单情况，实际中计算复杂程度取决于更为详细的链接情况，比如全部都是50%的复杂度，全单向链接和存在双向链接的计算时间与收敛次数必然不会相同）

package cn.wx.PageRank;

import java.awt.FlowLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

import javax.swing.JButton;
import javax.swing.JFileChooser;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;
import javax.swing.JTextField;

/**
 * 求取PageRank值的代码
 * @author 艾儿
 */
public class newPageRank {
	
	static JTextField jtf;//显示文件路径的框
	static JTextArea jta;//显示计算结果的框
	static JFrame jf;//显示的窗体
	static JFrame jf1;//显示输入矩阵的窗体
	static float[] data;//存数输入数据的数组
	static int time=20;//指定的运行次数
	
	public static void main(String [] args){
		newPageRank mine = new newPageRank();
		mine.showUI();
	}
	
	/**
	 * 展示计算结果的界面
	 */
	public void showUI(){
		//初始化界面以及按钮、输入框等
		jf = new JFrame();
		jf.setTitle("PR值计算~~");
		jf.setSize(500, 500);
		jf.setDefaultCloseOperation(3);
		jf.setResizable(false);
		jf.setLayout(null);
		jf.setLocationRelativeTo(null);
		
		JButton btn = new JButton("打开");
		btn.setActionCommand("Open");
		btn.setBounds(20, 20, 80, 30);
		
		JButton btn1 = new JButton("随机");
		btn1.setActionCommand("Input");
		btn1.setBounds(110, 20, 80, 30);
		
		jtf = new JTextField();
		jtf.setBounds(200, 20, 260, 30);
		jtf.setEditable(true);
		jtf.setActionCommand("Over");
		
		jta = new JTextArea();
		jta.setEditable(false);
		jta.setLineWrap(true);
		jta.setAutoscrolls(true);
		
		JScrollPane jsp = new JScrollPane(jta);//创建滚动条
		jsp.setBounds(20, 70, 460, 380);
		
		
		//添加监听器
		ActionListener al = new ActionListener(){
			public void actionPerformed(ActionEvent e) {
				if(e.getActionCommand().equals("Open")){
					//弹出选择框
					jta.setText("");//每次重新选择之前清空输入框
					JFileChooser fc = new JFileChooser();
					int value = fc.showOpenDialog(null);
					fc.setFileSelectionMode(JFileChooser.FILES_ONLY);
					if(value == JFileChooser.CANCEL_OPTION){
						return;
					}
					File file = fc.getSelectedFile();
					jtf.setText(file.getAbsolutePath());
					readFile(file);
				}
				if(e.getActionCommand().equals("Input")){
					init();//初始化窗体，获取值
				}
				if(e.getActionCommand().equals("Over")){
					jta.setText("");
					//输入路径结束，执行以下操作
					File file = new File(jtf.getText());
					readFile(file);
				}
			}
			
		};
		
		jf.add(btn);
		jf.add(btn1);
		jf.add(jtf);
		jf.add(jsp);
		btn.addActionListener(al);
		btn1.addActionListener(al);
		jtf.addActionListener(al);
		
		jf.setVisible(true);
	}
	
	/**
	 * 读取相应路径文件的方法
	 * 定义文件中第一行是节点对应的初始化PR值，接下来是N*N的矩阵
	 * 同行数据之间均通过，分隔，不同行无需分隔符
	 * @param file：文件
	 */
	public static void readFile(File file){
		try {
			//创建读文件的流
			FileReader fr = new FileReader(file);
			BufferedReader br = new BufferedReader(fr);
			
			String PR = br.readLine();
			String[] sPR = PR.split(",");//将第一行PR值存入对应数组
			//将读取的PR值从String转为float
			float[] initPR = new float[sPR.length];
			for(int i=0;i<sPR.length;i++){
				initPR[i] = Float.parseFloat(sPR[i]);
			}
			jta.append("各页面的初始PR值………………………………………………………………"+"\n");
			for(int i=0;i<initPR.length;i++){
				jta.append(initPR[i]+"\t");//打印出PR值
			}
			jta.append("\n");
			
			//读取并创建N*N矩阵，在这里使用float，精度为小数点后7位
			float[][] array = new float[initPR.length][initPR.length];
			int count = 0;//用计数器控制行的变化
			//当行数小于指定数N时进行读取
			while(count<initPR.length){
				String value = br.readLine();//读取一行的值
				String[] rowV = value.split(",");
				//对第count行第i列赋值
				for(int i=0;i<initPR.length;i++){
					array[count][i] = Float.parseFloat(rowV[i]);
				}
				count++;
			}
			jta.append("原始矩阵为………………………………………………………"+"\n");
			print(array);//打印出矩阵
			//读取完成后，调用计算的函数对矩阵进行计算
			long start = System.currentTimeMillis();
			calculate(initPR,array);
			long end = System.currentTimeMillis();
			jta.append("total time is:"+(end-start));
		} catch (FileNotFoundException e) {
			javax.swing.JOptionPane.showMessageDialog(jf,"文件未找到，请重试！");
		} catch (IOException e) {
			javax.swing.JOptionPane.showMessageDialog(jf,"文件读取有误，请重试！");
		}
	}
	
	/**
	 * 打印矩阵的方法
	 * @param s
	 */
	static void print(float[][] f){
		for(int i=0;i<f.length;i++){
			for(int j=0;j<f.length;j++){
				jta.append(f[i][j]+"\t");
			}
			jta.append("\n");
		}
	}

	/**
	 * 计算矩阵特征值以及特征向量的方法
	 * @param initPR：存储初始的PR值的float数组
	 * @param array：存储初始矩阵的float二维数组
	 */
	static void calculate(float[] initPR,float[][] array){
		array = changeRC(array);//倒置矩阵
		jta.append("转置后的矩阵…………………………………………………………");
		jta.append("\n");
		print(array);
		array = randomization(array);//概率化矩阵
		jta.append("\n");
		jta.append("概率化后的矩阵………………………………………………………………");
		jta.append("\n");
		print(array);
		for(int i=1;i<=time;i++){
			initPR = formular(initPR,array);
			jta.append("\n");
			jta.append("经过"+i+"次计算，PR值为………………………………………………");
			jta.append("\n");
			for(int j=0;j<initPR.length;j++){
				jta.append("PR["+j+"]的值为："+initPR[j]);
				jta.append("\n");
			}
		}
		jta.repaint();
	}
	
	/**
	 * 转置矩阵的方法
	 * @param array：需要转置的矩阵
	 * @return：将转置后的矩阵返回
	 */
	static float[][] changeRC(float[][] array){
		float temp = 0;//临时变量，用于交换
		for(int i=0;i<array.length;i++){
			for(int j=0;j<array.length;j++){
				//对矩阵的每一行、列遍历，如果下标i<j就倒换
				if(i<j){
					temp = array[i][j];
					array[i][j] = array[j][i];
					array[j][i] = temp;
				}
			}
		}
		return array;
	}
	
	/**
	 * 概率化矩阵的方法
	 * @param array：需要概率化的矩阵
	 * @return：返回已经概率化的矩阵
	 */
	static float[][] randomization(float[][] array){
		int count = 0;//控制列变化的计数器
		int size = 0;//计量列中连接为1的元素数量的计数器
		while(count<array.length){
			size = 0;//每次计数之前要清零
			for(int i=0;i<array.length;i++){
				if(array[i][count]==1){
					size++;//先统计出数量为多少
				}
			}
			jta.append("the size of "+count+" is:"+size+"    ");
			for(int i=0;i<array.length;i++){
				if(array[i][count]==1){
					array[i][count]=(float)1/size;
				}
			}
			count++;
		}
		return array;
	}
	
	/**
	 * 通过公式计算PR值
	 * @param initPR：初始PR值
	 * @param array：经处理的矩阵
	 * @return：返回计算后的PR值
	 */
	static float[] formular(float[] initPR,float[][] array){
		for(int i=0;i<initPR.length;i++){
			initPR[i] = 0;//重算一个PR之前，将其清零
			int count =0;//计量每一行0元素个数
			for(int j=0;j<initPR.length;j++){
				if(i!=j && array[i][j]!=0){
					initPR[i] = (float) (initPR[i]+((initPR[j]*array[i][j])*0.85+0.15));
				}else
					count++;
			}
			if(count==initPR.length){
				initPR[i] = (float) 0.15;
			}
		}
		return initPR;
	} 
	
	
	static void input(float[] data){
		float size = data[0];
		float complex = data[1];
		float[] initPR = new float[data.length-2];
		for(int i=0;i<initPR.length;i++){
			initPR[i] = data[i+2];
		}
		float[][] array = new float[(int) size][(int) size];//创建输入大小的矩阵
		//初始化矩阵元素为0
		for(int i=0;i<array.length;i++){
			for(int j=0;j<array.length;j++){
				array[i][j]=0;
			}
		}
		int num = (int) (complex/100*array.length*array.length);//需要被赋为1的元素个数
		//为矩阵按照复杂程度赋值
		while(num>0){
			int row = (int) (Math.random()*(array.length));
			int column = (int) (Math.random()*(array.length));//随机生成行列数
			if(row!=column && array[row][column]!=1){
				array[row][column]=1;
				num--;
			}
		}
		//打印随机生成的PR和矩阵
		jta.append("各页面的初始PR值………………………………………………………………"+"\n");
		for(int i=0;i<initPR.length;i++){
			jta.append(initPR[i]+"\t");//打印出PR值
		}
		jta.append("\n");
		jta.append("生成的矩阵…………………………………………………………………………"+"\n");
		print(array);
		//将计算好的初始PR数组和矩阵传入计算
		long start = System.currentTimeMillis();
		calculate(initPR,array);
		long end = System.currentTimeMillis();
		jta.append("total time is:"+(end-start));
	}
	
	/**
	 * 初始化一个输入值的窗体
	 */
	static void init(){
		jf1 = new JFrame("生成随机矩阵");
		jf1.setSize(300, 160);
		jf1.setResizable(false);
		jf1.setDefaultCloseOperation(2);
		jf1.setLocationRelativeTo(null);
		jf1.setLayout(new FlowLayout());
		
		JLabel lb = new JLabel("矩阵维度：");
		final JTextField jtf = new JTextField(15);
		JLabel lb1 = new JLabel("初始PR值：");
		final JTextField jtf1 = new JTextField(15);
		JLabel lb2 = new JLabel("    复杂度：  ");
		final JTextField jtf2 = new JTextField(15);
		jtf2.setActionCommand("sure");
		JLabel lb3 = new JLabel("% ");
		JButton btn = new JButton("确认");
		btn.setActionCommand("sure");
		JButton btn1 = new JButton("取消");
		btn1.setActionCommand("cancle");
		
		ActionListener al = new ActionListener(){
			public void actionPerformed(ActionEvent e) {
				if(e.getActionCommand().equals("sure")){
					//点击确认后，存储输入值
					float size = Integer.parseInt(jtf.getText());//取值
					String[] s = jtf1.getText().split(",");
					float complex = Integer.parseInt(jtf2.getText());
					
					//初始化数组，将输入框中的值存入数组
					data = new float[s.length+2];
					//先存入矩阵维度，再放入复杂度，最后存入各个初始值
					data[0] = size;
					data[1] = complex;
					for(int i=0;i<s.length;i++){
						data[2+i] = Float.parseFloat(s[i]);
					}
					jf1.dispose();
					input(data);
				}
				if(e.getActionCommand().equals("cancle")){
					jf1.dispose();
				}
			}
			
		};
		
		jf1.add(lb);
		jf1.add(jtf);
		jf1.add(lb1);
		jf1.add(jtf1);
		jf1.add(lb2);
		jf1.add(jtf2);
		jf1.add(lb3);
		jf1.add(btn);
		jf1.add(btn1);
		
		jtf2.addActionListener(al);
		btn.addActionListener(al);
		btn1.addActionListener(al);
		
		jf1.setVisible(true);
	}
	
}

关于公式再提一下，Google后来调整时使用了1-q/N,公式的其他部分未作任何变动，这里的N是互联网中全部的网页数量，网上的参考资料说这样做使得网页级别变为了被随机访问的期望值(不理解)……做一下比较，对于0.15/N这个公式，从逻辑上看也可以认为是加速了值收敛，通过代码计算验证发现，对于同样维度为10的矩阵，初始值全为1，复杂度为50%，原公式经过20次运算后，有9个PR值收敛到了小数点后2位，一个收敛到了小数点后1位，而改进后的公式，有8个PR值收敛到了小数点后3位，2个收敛到小数点后2位。可以看出，仅仅是10维矩阵就几乎存在一位的精度差，如果应用到上亿的网页运算中，计算时间一定会大大的缩减~但是这种情况下的计算比较复杂，而且两种计算的原理近似，这里不再额外讨论。