Google核心技术之——PageRank算法scala实现

PageRank算法简述

常言道，看一个人怎样，看他有什么朋友就知道了。也就是说，一个人有着越多牛X朋友的人，他是牛X的概率就越大。将这个知识迁移到网页上就是“被越多优质的网页所指的网页，它是优质的概率就越大”。PageRank是Google创始人提出来的，算法的发展也经历了很多次优化。至于原理这边就不累赘了，同学们可以自行谷歌~~

工程化实现

1.输入数据

2,1 2,4 3,2 3,5 4,1 5,3 6,7

数据说明：链出页面，链入页面

2.每步的迭代公式

S(Vi)是网页i的中重要性（权重）。d是阻尼系数，一般设置为0.85。In(Vi)是存在指向网页i的链接的网页集合。Out(Vj)是网页j中的链接存在的链接指向的网页的集合。|Out(Vj)|是集合中网页的个数。

3.数据清洗

所有集合

[1,2,3,4,5,6,7]

初始评分 （可以自定义，这边设置为1）

[(1,1),(2,1),(3,1),(4,1),(5,1)...]

清洗结果

[(2,<1,4>),(3,<2,5>),(4,<1>),(5,<3>)...] （1）

迭代过程

def main(args: Array[String]): Unit = {
    val sc = new SparkContext(new SparkConf().setMaster("local[1]").setAppName("pageRank"))
    val file = sc.textFile("D:/HDFS/Input/pageRank.txt").persist(StorageLevel.MEMORY_ONLY_SER)
    val initFile = file.flatMap { _.split(",").toList }
    //<2, 1> <2, 4> <3, 2>.... (1)
    val rankFile = file.map { line =>
      val token = line.split(",")
      (token(0), token(1))
    }.distinct()
    file.unpersist(true);
    //<2, 1f> <3, 1f>  <4, 1f>...
    var init = initFile.distinct().map { (_, 1f) }
    var map = sc.broadcast(init.collectAsMap())
    //循环遍历 迭代次数
    val num = 1
    for (i <- 1 to num) {
      init = rankFile.aggregateByKey(List[String]())(_ :+ _, _ ++ _).flatMap(calculate(_, map.value)).reduceByKey(_ + _)
             .rightOuterJoin(init).map(x => (x._1, if (x._2._1.isDefined == true) x._2._1.get else 0f))
      if (i != num) {
        map = sc.broadcast(init.collectAsMap())
      }
    }
    init.collect().foreach(println)
  }


  def calculate(a: (String, List[String]), b: scala.collection.Map[String, Float]): ArrayBuffer[(String, Float)] = {
    val array = ArrayBuffer[(String, Float)]()
      for (i <- 0 to (a._2.size - 1)) {
        array += ((a._2(i), b.get(a._2(i)).get / a._2.size))
      }
    array
  }

核心步骤

1. (1) ===> <2, [1, 4]>

2. <2, [1, 4]> ===> <1, 上次迭代1的分数 / [1, 4].size>

3. reduceByKey

4. rightOuterJoin(init) 保证无出链的不丢失

迭代结果

num = 1 (4,0.5) (7,1.0) (5,0.5) (6,0.0) (2,0.5) (3,1.0) (1,1.5)

注意：公式中阻尼系数d在算法初始阶段是没有的，上述公式中d设置为1此处会发现6的权重为0，就出现了孤立页面，这时候便引进了阻尼系数d，d一般设值为0.85

修改之后公式(0.15f + x._2._1.get * 0.85f)，其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率。 1- q= 0.15就是用户停止点击，随机跳到新URL的概率）的算法被用到了所有页面上，估算页面可能被上网者放入书签的概率。迭代一次结果为

(4,0.57500005) (7,1.0) (5,0.57500005) (6,0.15) (2,0.57500005) (3,1.0) (1,1.4250001)

迭代十次

(4,0.2610117) (7,1.0) (5,0.2610117) (6,0.15) (2,0.2610117) (3,1.0) (1,16.99974)

随着每一轮的计算进行，网页当前的PageRank值会不断得到更新。设置一个阈值，通过比较迭代前后的平方差是否接近阈值来判断迭代是否停止。

总结

已经完成了pageRank算法的scala代码实现工程，对pageRank算法的认知也更加深刻。算法么，都存在自身的优缺点，pageRank算法的它与查询无关，也就是说无论是谁在百度或者谷歌无搜索关键词返回结果应该是一样的，但是有了搜索词，会在整个排序中取出部分结果重新排序展示给用户，这些就是搜索引擎所做的事情了。pageRank算法设计思想类似于itembase协同过滤算法中M/N的设计，大多数人认为对的通常都是对的。搜索推荐真是一家人！！！

来源：http://blog.csdn.net/pztyz314151/