PageRank计算方法及java实现

时间:2021-04-26 18:08:01

倒排索引解决的是如何有效的搜索包含某一关键字的网页,PageRank就是如何计算这些网页的价值。PageRank的计算是根据网页的链接计算的。若有1,2,3,4号网页之间的链接关系如下:

PageRank计算方法及java实现

PageRank计算方法及java实现

这里假设每个网页的权重相等,都为1,这个S矩阵是这样得出来的,第1列是1号网页,它指向了2,3,4号网页,它的权重为1,所以2,3,4每个获得的为1/3,这样依次类推。

求解G的特征向量可以通过q(next)=G*q(cur)这样不断迭代获得,已经证明,q(next)与q(cur)最终会收敛。刚开始q可以去一个随机的向量

这里,通过编程求解pagerank,取alpha=0.85,通过不断的迭代,当q(next)和q(cur)之间的距离小于0.0000001时,认为已经收敛。pagerank就是特征值为1的特征向量,1,2,3,4号网页的价值分别为特征向量中对应维的值。

为了便于观察结果,这里q取值为

2.14335103032906, 0.4690253246490811, 0.152093449701467, 2.751926907462932

用List泛型作为向量和矩阵的容器,顺便熟悉一下容器类的使用。java代码如下:

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class PageRank {
	private static final double ALPHA = 0.85;
	private static final double DISTANCE = 0.0000001;

	public static void main(String[] args) {
		// List<Double> q1=getInitQ(4);
		System.out.println("alpha的值为: " + ALPHA);
		List<Double> q1 = new ArrayList<Double>();
		q1.add(new Double(2.14335103032906));
		q1.add(new Double(0.4690253246490811));
		q1.add(new Double(0.152093449701467));
		q1.add(new Double(2.751926907462932));
		System.out.println("初始的向量q为:");
		printVec(q1);
		System.out.println("初始的矩阵G为:");
		printMatrix(getG(ALPHA));
		List<Double> pageRank = calPageRank(q1, ALPHA);
		System.out.println("PageRank为:");
		printVec(pageRank);
		System.out.println();
	}

	/**
	 * 打印输出一个矩阵
	 * 
	 * @param m
	 */
	public static void printMatrix(List<List<Double>> m) {
		for (int i = 0; i < m.size(); i++) {
			for (int j = 0; j < m.get(i).size(); j++) {
				System.out.print(m.get(i).get(j) + ", ");
			}
			System.out.println();
		}
	}

	/**
	 * 打印输出一个向量
	 * 
	 * @param v
	 */
	public static void printVec(List<Double> v) {
		for (int i = 0; i < v.size(); i++) {
			System.out.print(v.get(i) + ", ");
		}
		System.out.println();
	}

	/**
	 * 获得一个初始的随机向量q
	 * 
	 * @param n
	 *            向量q的维数
	 * @return 一个随机的向量q,每一维是0-5之间的随机数
	 */
	public static List<Double> getInitQ(int n) {
		Random random = new Random();
		List<Double> q = new ArrayList<Double>();
		for (int i = 0; i < n; i++) {
			q.add(new Double(5 * random.nextDouble()));
		}
		return q;
	}

	/**
	 * 计算两个向量的距离
	 * 
	 * @param q1
	 *            第一个向量
	 * @param q2
	 *            第二个向量
	 * @return 它们的距离
	 */
	public static double calDistance(List<Double> q1, List<Double> q2) {
		double sum = 0;

		if (q1.size() != q2.size()) {
			return -1;
		}

		for (int i = 0; i < q1.size(); i++) {
			sum += Math.pow(q1.get(i).doubleValue() - q2.get(i).doubleValue(),
					2);
		}
		return Math.sqrt(sum);
	}

	/**
	 * 计算pagerank
	 * 
	 * @param q1
	 *            初始向量
	 * @param a
	 *            alpha的值
	 * @return pagerank的结果
	 */
	public static List<Double> calPageRank(List<Double> q1, double a) {

		List<List<Double>> g = getG(a);
		List<Double> q = null;
		while (true) {
			q = vectorMulMatrix(g, q1);
			double dis = calDistance(q, q1);
			System.out.println(dis);
			if (dis <= DISTANCE) {
				System.out.println("q1:");
				printVec(q1);
				System.out.println("q:");
				printVec(q);
				break;
			}
			q1 = q;
		}
		return q;
	}

	/**
	 * 计算获得初始的G矩阵
	 * 
	 * @param a
	 *            为alpha的值,0.85
	 * @return 初始矩阵G
	 */
	public static List<List<Double>> getG(double a) {

		int n = getS().size();
		List<List<Double>> aS = numberMulMatrix(getS(), a);
		List<List<Double>> nU = numberMulMatrix(getU(), (1 - a) / n);
		List<List<Double>> g = addMatrix(aS, nU);
		return g;
	}

	/**
	 * 计算一个矩阵乘以一个向量
	 * 
	 * @param m
	 *            一个矩阵
	 * @param v
	 *            一个向量
	 * @return 返回一个新的向量
	 */
	public static List<Double> vectorMulMatrix(List<List<Double>> m,
			List<Double> v) {
		if (m == null || v == null || m.size() <= 0
				|| m.get(0).size() != v.size()) {
			return null;
		}

		List<Double> list = new ArrayList<Double>();
		for (int i = 0; i < m.size(); i++) {
			double sum = 0;
			for (int j = 0; j < m.get(i).size(); j++) {
				double temp = m.get(i).get(j).doubleValue()
						* v.get(j).doubleValue();
				sum += temp;
			}
			list.add(sum);
		}

		return list;
	}

	/**
	 * 计算两个矩阵的和
	 * 
	 * @param list1
	 *            第一个矩阵
	 * @param list2
	 *            第二个矩阵
	 * @return 两个矩阵的和
	 */
	public static List<List<Double>> addMatrix(List<List<Double>> list1,
			List<List<Double>> list2) {
		List<List<Double>> list = new ArrayList<List<Double>>();
		if (list1.size() != list2.size() || list1.size() <= 0
				|| list2.size() <= 0) {
			return null;
		}
		for (int i = 0; i < list1.size(); i++) {
			list.add(new ArrayList<Double>());
			for (int j = 0; j < list1.get(i).size(); j++) {
				double temp = list1.get(i).get(j).doubleValue()
						+ list2.get(i).get(j).doubleValue();
				list.get(i).add(new Double(temp));
			}
		}
		return list;
	}

	/**
	 * 计算一个数乘以矩阵
	 * 
	 * @param s
	 *            矩阵s
	 * @param a
	 *            double类型的数
	 * @return 一个新的矩阵
	 */
	public static List<List<Double>> numberMulMatrix(List<List<Double>> s,
			double a) {
		List<List<Double>> list = new ArrayList<List<Double>>();

		for (int i = 0; i < s.size(); i++) {
			list.add(new ArrayList<Double>());
			for (int j = 0; j < s.get(i).size(); j++) {
				double temp = a * s.get(i).get(j).doubleValue();
				list.get(i).add(new Double(temp));
			}
		}
		return list;
	}

	/**
	 * 初始化S矩阵
	 * 
	 * @return S
	 */
	public static List<List<Double>> getS() {
		List<Double> row1 = new ArrayList<Double>();
		row1.add(new Double(0));
		row1.add(new Double(0));
		row1.add(new Double(0));
		row1.add(new Double(0));
		List<Double> row2 = new ArrayList<Double>();
		row2.add(new Double(1 / 3.0));
		row2.add(new Double(0));
		row2.add(new Double(0));
		row2.add(new Double(1));
		List<Double> row3 = new ArrayList<Double>();
		row3.add(new Double(1 / 3.0));
		row3.add(new Double(1 / 2.0));
		row3.add(new Double(0));
		row3.add(new Double(0));
		List<Double> row4 = new ArrayList<Double>();
		row4.add(new Double(1 / 3.0));
		row4.add(new Double(1 / 2.0));
		row4.add(new Double(1));
		row4.add(new Double(0));

		List<List<Double>> s = new ArrayList<List<Double>>();
		s.add(row1);
		s.add(row2);
		s.add(row3);
		s.add(row4);

		return s;
	}

	/**
	 * 初始化U矩阵,全1
	 * 
	 * @return U
	 */
	public static List<List<Double>> getU() {
		List<Double> row1 = new ArrayList<Double>();
		row1.add(new Double(1));
		row1.add(new Double(1));
		row1.add(new Double(1));
		row1.add(new Double(1));
		List<Double> row2 = new ArrayList<Double>();
		row2.add(new Double(1));
		row2.add(new Double(1));
		row2.add(new Double(1));
		row2.add(new Double(1));
		List<Double> row3 = new ArrayList<Double>();
		row3.add(new Double(1));
		row3.add(new Double(1));
		row3.add(new Double(1));
		row3.add(new Double(1));
		List<Double> row4 = new ArrayList<Double>();
		row4.add(new Double(1));
		row4.add(new Double(1));
		row4.add(new Double(1));
		row4.add(new Double(1));

		List<List<Double>> s = new ArrayList<List<Double>>();
		s.add(row1);
		s.add(row2);
		s.add(row3);
		s.add(row4);

		return s;
	}
}

运行的结果如下:

alpha的值为: 0.85
初始的向量q为:
2.14335103032906, 0.4690253246490811, 0.152093449701467, 2.751926907462932, 
初始的矩阵G为:
0.037500000000000006, 0.037500000000000006, 0.037500000000000006, 0.037500000000000006, 
0.3208333333333333, 0.037500000000000006, 0.037500000000000006, 0.8875, 
0.3208333333333333, 0.4625, 0.037500000000000006, 0.037500000000000006, 
0.3208333333333333, 0.4625, 0.8875, 0.037500000000000006, 
3.779766282051368 //每次迭代q(next)与q(cur)之间的距离
2.4035965167590136
1.4238587872383457
0.5870223621104362
0.36369176025574346
0.31367310105660856
0.18581579651395874
0.07660733547785258
0.04746234298175015
0.040934829802108524
0.024249251782254677
0.009997376978821962
0.006193909919029721
0.005342059249847388
0.0031645652470405
0.0013046733166379352
8.083149224182183E-4
6.971470790734495E-4
4.12980709372539E-4
1.7026190637372944E-4
1.0548636036817723E-4
9.097878311218115E-5
5.389462785614166E-5
2.2219444816460543E-5
1.3766134850747929E-5
1.18728733506049E-5
7.033333145760403E-6
2.899672266338346E-6
1.796502107519953E-6
1.5494285237433766E-6
9.178609651241069E-7
3.784117613752634E-7
2.3444633197666482E-7
2.0220284343471307E-7
1.197822903479996E-7
4.9383326013693536E-8
q1:
0.2068648767053453, 2.0589818452675903, 1.1405438357642066, 2.110006154405399,   //收敛时q(cur)的值
q:
0.2068648767053453, 2.058981823016449, 1.1405438760105855, 2.110006136410161,    //收敛时q(next)的值
PageRank为:
0.2068648767053453, 2.058981823016449, 1.1405438760105855, 2.110006136410161,    //最终PageRank的值

从这个结果可以看出,网页的价值排序是4>2>3>1