文档章节

从赌钱游戏看PageRank算法

fourinone
 fourinone
发布于 2013/03/27 13:45
字数 2960
阅读 4236
收藏 160

谈到并行计算应用,会有人想到PageRank算法,我们有成千上万的网页分析链接关系确定排名先后,借助并行计算完成是一个很好的场景。长期以来,google的创始发明PageRank算法吸引了很多人学习研究,据说当年google创始者兴奋的找到yahoo公司,说他们找到一种更好的搜索引擎算法,但是被yahoo公司技术人员泼了冷水,说他们关心的不是更好的技术,而是搜索的盈利。后来google包装成了“更先进技术的新一代搜索引擎”的身份,逐渐取代了市场,并实现了盈利。

由于PageRank算法有非常高的知名度和普及度,我们接下来以PageRank算法为例讲述“并行计算+数据算法”的经典搭配,并且这种“海量数据并行处理、迭代多轮后收敛”的分析过程也跟其他的数据挖掘或者机器学习算法应用类似,能起到很好的参考作用。

下面是PageRank算法的公式:



我们其实可以直接阐述该公式本身,并介绍如何使用并行计算套用上面公式得到各网页的PageRank值,这样虽然通过并行计算方式完成了PageRank计算,但是大家仍然不明白上面的PageRank公式是怎么来的。

我们把这个PageRank算法公式先放在一边,看看一个赌钱的游戏:
有甲、乙、丙三个人赌钱,他们的输赢关系如下:
甲的钱输给乙和丙
乙的钱输给丙
丙的钱输给甲
例如,甲、乙、丙各有本钱100元,按照以上输赢关系,玩一把下来:
甲输给乙50元、输给丙50元
乙输给丙100元
丙输给甲100元

如果仅是玩一把的话很容易算出谁输谁赢
但如果他们几个维持这样的输赢关系,赢的钱又投进去继续赌,这样一轮一轮赌下去的话,最后会是什么样子呢?

我们可以写个单机程序看看,为了方便计算,初始本钱都设为1块钱,用x1,x2,x3代表甲、乙、丙:
double x1=1.0,x2=1.0,x3=1.0;
用x1_income,x2_income,x3_income代表每赌一把后各人赢的钱,根据输赢关系:
double x2_ income =x1/2.0;
double x3_ income =x1/2.0+x2;
double x1_ income =x3;
最后再把各人赢的钱覆盖掉本钱,继续往下算。完整程序如下:

// Gamble单机程序

public class Gamble
{
 public static double x1=1.0,x2=1.0,x3=1.0;
 
 public static void playgame(){
  double x2_income=x1/2.0;
  double x3_income=x1/2.0+x2;
  double x1_income=x3;
  x1=x1_income;
  x2=x2_income;
  x3=x3_income;
  System.out.println("x1:"+x1+", x2:"+x2+", x3:"+x3);
 }
 
 public static void main(String[] args){
  for(int i=0;i<500;i++){
   System.out.print("第"+i+"轮 ");
   playgame();
  }
 }
}

我们运行500轮后,看到结果如下:



我们发现,从107轮后,各人的输赢结果就一直是
x1:1.2000000000000002, x2:0.6000000000000001, x3:1.2000000000000002
…...
可能你都没想到会有这么个规律,这样一直赌下去,虽然各人每轮有输有赢,但是多轮后的输赢结果居然保持平衡,维持不变了。用技术术语来说就是多轮迭代后产生了收敛,用俗话来讲,就是玩下去甲和丙是不亏的,乙不服输再继续赌下去,也不会有扳本的机会的。

我们再把输赢关系稍微改一下:丙的钱输给甲和乙
double x2_income=x1/2.0+x3/2.0;
double x3_income=x1/2.0+x2;
double x1_income=x3/2.0;

运行10000轮后,发现又收敛了:
x1:0.6666666666666667, x2:1.0, x3:1.3333333333333333

不过这次就变成了“甲是输的,乙保本,丙是赢的”,我们发现收敛的结果可用于排名,如果给他们做一个赌王排名的话,很显然:“丙排第一,乙第二、甲第三”

那么这样的收敛是在所有情况下都会发生吗,什么情况不会收敛呢?
我们回过头观察上面的输赢关系,甲、乙、丙三人互相各有输赢,导致钱没有流走,所以他们三人才一直可以赌下去,如果把输赢关系改一下,让甲只输钱,不赢钱,如下:
double x2_income=x1/2.0+x3/2.0;
double x3_income=x1/2.0+x2;
double x1_income=0;

那么运行下来会是什么结果呢?


我们发现很多轮后,全部为0了。我们分析一下过程,第一轮后,甲的钱就输光了,没有赢得一分钱。但是乙和丙各有输赢,他们一直赌到2000多轮时,乙的钱全部输光了,甲乙都没钱投进来赌了,导致丙再也赢不到钱了,最后所有人结果都变为0了。

我们再分析一下输赢关系,甲的钱全部输给丙和乙后,丙跟乙赌,赢的多输的少,于是所有的钱慢慢都被丙赢走了,导致最后无法维持一个平衡的输赢结果。因此,如果我们要维持平衡和收敛,必须保证赢了钱的人不准走,必须又输给别人才行,让钱一直在三人圈里转不流失。换句话说,如果存在某人只输不赢,那么这个游戏就玩不下去。

赌钱游戏讲完了,我们再看看PageRank算法的公式:



上面的L(B)代表页面B指向其他页面的连接数,我们举个例子:

假设有A、B、C三张网页,他们的链接关系如下:
A包含B和C的链接
B包含C的链接
C包含A的链接

根据上面的公式,得到各网页PR值如下:
PR(B)=PR(A)/2;
PR(C)=PR(A)/2+PR(B);
PR(A)=PR(C);

可以回过头对照一下,把A、B、C改成甲、乙、丙就是上面举的赌钱游戏例子。

那么q是干吗的?公式里的q叫做逃脱因子,名字很抽象,目的就是用于解决上面赌钱游戏中“只输不赢”不收敛的问题,1-q会保证其中一个PR值为0时计算下来不会全部为0,那么加了这么一个(…)*q+1-q的关系后,整体的PR值会变化吗?

当每个页面的初始PR值为1时,0<=q<=1(计算时通常取值0.8),我们把所有页面的PR值相加看看,假设有n张网页:

PR(x1)+ PR(x2)+ …+PR(xn) 
=( (PR(x2)/ L(x2)+ … )*q+1-q) + … + ( (PR(x1)/ L(x1)+ … )*q+1-q)
=(PR(x1)* L(x1)/L(x1) + PR(x2)* L(x2)/L(x2) + … + PR(xn)* L(xn)/L(xn))q + n(1-q)
=( PR(x1) + PR(x2) + … + PR(xn))*q + n - n*q
=n*q + n – n*q
= n

由于初始PR值为1,所以最后所有页面的PR值相加结果还是为n,保持不变,但是加上(…)*q+1-q的关系后,就避免了PR值为0可以寻求收敛进行排序。

当然实际应用中,这个公式还可以设计的更复杂,并可以通过高等代数矩阵旋转求解,我们这里只是为了理解原理,并不是为了做搜索算法,所以就不再深入下去了。

总结:世界的很多东西都是零和游戏,就像炒股,股民赚的钱也就是机构亏的钱,机构赚的钱也就是股民亏的钱,也许股民们应该研究一下PageRank算法,看看股市起起落落的背后是不是收敛了,收敛了说明炒下去永远别想解套,而且机构永远不会亏。

如何使用并行计算方式求PR值:
我们这里通过fourinone提供的各种并行计算模式去设计,思路方法可以有很多种。
第一次使用可以参考分布式计算上手demo指南,开发包下载地址:http://code.google.com/p/fourinone/ 

思路一:可以采取工人互相合并的机制(工人互相合并及receive使用可参见sayhello demo),每个工人分析当前网页链接,对每个链接进行一次PR值投票,通过receive直接投票到该链接对于网页所在的工人机器上,这样经过一轮工人的互相投票,然后再统计一下本机器各网页所得的投票数得到新的PR值。但是这种方式,对于每个链接投票,都要调用一次receive到其他工人机器,比较耗用带宽,网页数量庞大链接众多时要调用很多次receive,导致性能不高。

思路二:由于求PR值的特点是输入数据大,输出数据小,也就是网页成千上万占空间多,但是算出来的PR值占空间小,我们姑且用内存可以装下。因此我们优先考虑每个工人统计各自机器上的网页,计算各链接对应网页的所得投票,然后返回工头统一合并得到各网页的PR值。可以采用最基本的“总—分—总”并行计算模式实现(请参考分布式计算上手demo指南)。
并行计算的拆分和合并设计如下:

可以看到:
工人负责统计各自机器上网页的各个链接的PR得票。
工头负责合并累加得到各链接对应网页的新PR值,并迭代计算。

程序实现:
PageRankWorker:是一个PageRank工人实现,为了方便演示,它通过一个字符串数组代表包括的链接(实际上应该从本地网页文件里获取)
links = new String[]{"B","C"};
然后对链接集合中的每个链接进行PR投票
for(String p:links)
 outhouse.setObj(p, pr/links.length);

PageRankCtor:是一个PageRank包工头实现,它将A、B、C三个网页的PageRank初始值设置为1.00,然后通过doTaskBatch进行阶段计算,doTaskBatch提供一个栅栏机制,等待每个工人计算完成才返回,工头将各工人返回的链接投票结果合并累加:
pagepr = pagepr+(Double)prwh.getObj(page);
得到各网页新的PR值(这里取q值为1进行计算),然后连续迭代500轮计算。

运行步骤:
1、 启动ParkServerDemo(它的IP端口已经在配置文件指定)
java -cp fourinone.jar; ParkServerDemo
 

2、运行A、B、C三个PageRankWorker,传入不同的IP和端口号
java  -cp fourinone.jar; PageRankWorker localhost 2008 A
java  -cp fourinone.jar; PageRankWorker localhost 2009 B
java  -cp fourinone.jar; PageRankWorker localhost 2010 C

3、运行PageRankCtor
java -cp fourinone.jar; PageRankCtor

我们可以看到跟开始的单机程序的结果是一样的,同时各工人窗口依次输出了各自的PR值:

完整demo源码如下:
// ParkServerDemo

import com.fourinone.BeanContext;
public class ParkServerDemo
{
 public static void main(String[] args)
 {
  BeanContext.startPark();
 }
}

// PageRankWorker

import com.fourinone.MigrantWorker;
import com.fourinone.WareHouse;
import com.fourinone.Workman;

public class PageRankWorker extends MigrantWorker
{
 public String page = null;
 public String[] links = null;
 
 public PageRankWorker(String page, String[] links){
  this.page = page;
  this.links = links;
 }

 public WareHouse doTask(WareHouse inhouse)
 {
  Double pr = (Double)inhouse.getObj(page);
  System.out.println(pr);
  
  WareHouse outhouse = new WareHouse();
  for(String p:links)
   outhouse.setObj(p, pr/links.length);//对包括的链接PR投票

  return outhouse;
 }
 
 public static void main(String[] args)
 {
  String[] links = null;
  if(args[2].equals("A"))
   links = new String[]{"B","C"};//A页面包括的链接
  else if(args[2].equals("B"))
   links = new String[]{"C"};
  else if(args[2].equals("C"))
   links = new String[]{"A"};
  
  PageRankWorker mw = new PageRankWorker(args[2],links);
  mw.waitWorking(args[0],Integer.parseInt(args[1]),"pagerankworker");
 }
}

// PageRankCtor
import com.fourinone.Contractor;
import com.fourinone.WareHouse;
import com.fourinone.WorkerLocal;
import java.util.Iterator;

public class PageRankCtor extends Contractor
{
 public WareHouse giveTask(WareHouse inhouse)
 {
  WorkerLocal[] wks = getWaitingWorkers("pagerankworker");
  System.out.println("wks.length:"+wks.length);
  
  for(int i=0;i<500;i++){//500轮
   WareHouse[] hmarr = doTaskBatch(wks, inhouse);
   WareHouse prwh = new WareHouse();
   for(WareHouse result:hmarr){
    for(Iterator iter=result.keySet().iterator();iter.hasNext();){
     String page = (String)iter.next();
     Double pagepr = (Double)result.getObj(page);
     if(prwh.containsKey(page))
      pagepr = pagepr+(Double)prwh.getObj(page);
     prwh.setObj(page,pagepr);
    }
   }
   inhouse = prwh;//迭代
   System.out.println("No."+i+":"+inhouse);
  }
  return inhouse;
 }
 
 public static void main(String[] args)
 {
  PageRankCtor a = new PageRankCtor();
  WareHouse inhouse = new WareHouse();
  inhouse.setObj("A",1.00d);//A的pr初始值
  inhouse.setObj("B",1.00d);//B的pr初始值
  inhouse.setObj("C",1.00d);//C的pr初始值
  a.giveTask(inhouse);
  a.exit();
 }
}

 

© 著作权归作者所有

共有 人打赏支持
fourinone

fourinone

粉丝 273
博文 43
码字总数 49961
作品 1
杭州
私信 提问
加载中

评论(19)

邪云子
邪云子
我要说不明觉厉吗
浩浩好好
浩浩好好
不懂你们在说什么,但是看起来好厉害的样子
酒逍遥
酒逍遥
pagerank 的数学理论基础 好像就是来自 马可夫链...
老外的东西 都是 真正的 理论 结合 实际啊
开源中国首席吹牛大师
开源中国首席吹牛大师

引用来自“巢鹏”的评论

把马可夫链说这么复杂不是坑爹吗。。。

我是来看评论的,好专业看不懂。
红科
红科
一个字 :晕
奥特曼FFF

引用来自“呆阿呆”的评论

很简单的东西说这么复杂,忽悠小白。

( (PR(x2)/ L(x2)+ … )*q+1-q) + … + ( (PR(x1)/ L(x1)+ … )*q+1-q)
=(PR(x1)* L(x1)/L(x1) + PR(x2)* L(x2)/L(x2) + … + PR(xn)* L(xn)/L(xn))q + n(1-q)
这步是怎么计算的
老腊肉
老腊肉
很简单的东西说这么复杂,忽悠小白。
美丽蜗牛
美丽蜗牛
我去,这个看的懵了,原本挺好理解的公式怎么那么复杂了
奥特曼FFF

引用来自“fourinone”的评论

引用来自“zqhxuyuan”的评论

根据上面的公式,得到各网页PR值如下:
PR(B)=PR(A)/2;
PR(B)=PR(A)/2+PR(C);
PR(A)=PR(C);
第二行有错:PR(C)=PR(A)/2 + PR(B)

谢谢提醒, 复制手误,已经修正.

明白了,数学太差- -!
奥特曼FFF

引用来自“fourinone”的评论

引用来自“奥特曼FFF”的评论

( (PR(x2)/ L(x2)+ … )*q+1-q) + … + ( (PR(x1)/ L(x1)+ … )*q+1-q)
=(PR(x1)* L(x1)/L(x1) + PR(x2)* L(x2)/L(x2) + … + PR(xn)* L(xn)/L(xn))q + n(1-q)
这步是怎么计算的

把q提出来

这个我知道,提出来之后呢
PageRank原理、举例、实现及使用networkX库简单调用

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/quiet_girl/article/details/81227904 PageRank是google搜素算法用到的算法思想。关于PageRank的背景网上有很...

nana-li
2018/07/27
0
0
深入探讨PageRank(一):PageRank算法原理入门

深入探讨PageRank(一):PageRank算法原理入门 一、PageRank简介 大名鼎鼎的PageRank算法是Google排名运算法则(排名公式)的一个非常重要的组成部分,其用于衡量一个网站好坏的标准。在揉合...

monkey_d_meng
2011/06/19
0
0
网络爬虫的抓取策略:深度抓取策略、广度优先遍历策略、Partial PageRank策略、OCIP策略、大站优先策略

前言 遍历策略是爬虫的核心问题,在爬虫系统中,待抓取URL队列是很重要的一部分。待抓取URL队列中的URL以什么样的顺序排列也是一个很重要的问题,因为这涉及到先抓取那个页面,后抓取哪个页面...

扶七
2018/05/10
0
0
pagerank 算法 快速入门

背景 pageRank 是Google CEO 拉里佩奇提出的一种算法,来计算互联网里的网站的重要性,以对搜索进行排名。 此处为啥算法叫pagerank,因为是以Google公司创办人拉里·佩奇(Larry Page)之姓来...

yuejiewc
2018/05/23
0
0
PageRank算法原理与实现

1 PageRank 1.1 简介 PageRank,又称网页排名、谷歌左侧排名,是一种由搜索引擎根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)...

致Great
2018/07/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

linux shell使用代理

export http_proxy=http://proxyAddress:port export http_proxy=http://proxyAddress:port

萌萌哒的小萝卜
刚刚
0
0
Krpano 插入视频-video

hotspot-video <hotspot name="videospot" url="%SWFPATH%/plugins/videoplayer.swf" alturl="%SWFPATH%/plugins/videoplayer.js" videourl="%SWFPATH%/image/video.flv|%......

华山猛男
3分钟前
0
0
el-select使用方法及遇到数据回显的坑

<el-select v-model="temp.lang" class="filter-item" placeholder="Please select"> <el-option v-for="item in langs" :key="item.value" :label="item.label" :value="item.value"/> </el......

BraveLN
5分钟前
0
0
百度贴吧自动签到

实现百度贴吧自动签到功能 1.编写签到Python脚本 2.服务器配置定时任务执行签到脚本

MrPei
10分钟前
0
0
windows nginx

之前一直是在linux上使用nginx,今天百度了一下,发现原来nginx在windows也有软件。 最近在研究jeecg-boot,现在越来越多的框架开始采用前后分离的模式了,看来也是时候跟进了。 nginx: dow...

miaojiangmin
15分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部