Apache Nutch 1.3 学习笔记十一（页面评分机制 OPIC）

fox111

　　
1. Nutch 1.3 的页面评分机制
　　   Nutch1.3目前默认还是使用OPIC作为其网页分数算法，但其之后，已经引入了PageRank-like算法，以弥补OPIC算法的不足，目前OPIC算法还是作为Nutch中ScoreFilter扩展点的一个扩展来实现的，而新的LinkRank算法有一个叫做org.apache.nutch.scoring.webgraph的包来对网页进行分数计算，它可以解决OPIC解决不了的问题，一个是重复地抓取页面，会引起那些被抓取的页面重要性增加；另一个是同时新添加的页面必须进行抓取，这样会使整个网络的总cash流通量增加，这样会造成那些没有重复抓取的页面重要性降低。

2. 什么是OPIC算法及其特点
　　下面内容来自[http://www.endless-loops.com/2011/03/nutch%E6%BA%90%E7%A0%81%E4%B8%AD%E7%9A%84%E9%93%BE%E6%8E%A5%E5%88%86%E6%9E%90%E7%AE%97%E6%B3%95-497.html]
OPIC算法是针对静态图的。OPIC算法的基本思想是：每个页面都有一个初始的cash，在抓取某页面时，该页面的cash会平均地分配到其所接向的页面，总的整个网络图中总的cash量是个定值，在抓取网页的过程这些一定量的cash在页面之间流通，很直观地，OPIC算法中页面的重要性就定义为流通过程中流过该页面的cash的总量在总流通量中占的比重。
对于每个网面(图中的结点)，OPIC算法维护两个值cash与history，cash是网页当前的cash值，history表示的则是该网页从OPIC算法开始到最后一次被抓取，获得的cash的总和。cash的初始值一般为1/n (n为网页总数)，history初始值为0。
OPIC算法使用两个向量C[1,…,n] 和H[1,…,n]分别表示各个网页的cash值和history值，为了优化算法，还引入一个变量G，使每一次抓取网页时都有G=|H|=∑i H，原论文中OPIC算法的伪代码如下：
　　

• 
  OPIC:   
  
• 
      On-line Page Importance Computation   
  
• 
  
• 
      for each i let C := 1/n ;   
  
• 
      for each i let H := 0 ;   
  
• 
      let G:=0 ;   
  
• 
      do forever   
  
• 
      begin   
  
• 
       choose some node i ;   
  
• 
       %% each node is selected   
  
• 
       %% infinitely often   
  
• 
  
• 
       H += C;   
  
• 
       %% single disk access per page   
  
• 
  
• 
       for each child j of i,   
  
• 
       do C[j] += C/out;   
  
• 
       %% Distribution of cash   
  
• 
       %% depends on L   
  
• 
  
• 
       G += C;   
  
• 
       C := 0 ;   
  
• 
      end   
  

　　
　　OPIC算法的几个问题：
1.无外向链接的sink页面处理：
OPIC算法中有个虚拟网页 (virtual page)的概念，虚拟网页与所有网页之间都有双向链接。
2.收敛性：
OPIC算法将网页重要性的计算集成到了网页抓取的过程中，OPIC算法依赖于反复的抓取，一个重要的问题就是（*）式的值在页面反复抓取过程中是收敛的，只有确保这一点算法才是正确有意义的，关于收敛性的证明，原论文里有严密的证明，这里只提示一下。
3.抓取策略
上面提到OPIC算法依赖于反复抓取，那么抓取策略就是个重要问题了，抓取策略直接影响网面重要性（*）式的收敛速度，事实上，理论与实验都证明贪心法中是最好的策略，即优先抓取那些cash值高的页面。
为了解决OPIC算法的收敛性问题，后来有人提出了Adaptive OPIC算法,它主要引一个时间窗(time window)的概念，它的点主要在于将网页重要性的计算集成到网页抓取的过程中了，简化了模型，简化了网页重要性值的求解。
3. OPIC在NUTCH中的应用
　　   在Nutch1.3的源码org.apache.nutch.scoring.opic包OPICScoringFilter类的注释里提到Nutch实现的链接分析算法是基于《Adaptive On-Line Page Importance Computaion》。Nutch把它做为一个ScoringFilter插件来对付，也就是说用户可以扩展自已的分数算法，
   其中ParseOutputFormat是用来为计算分数做准备，而FetchOutputFormat中的RecordWriter集成了ParseOutputFormat,抓取解析后的网页都会通过ParseOutputFormat生成的RecordWriter写出去，而这个计算OPIC的方法就是在这个RecordWriter中调用的。

4. Nutch OPIC源代码分析
　　下面是OPICScoringFIlter的distributeScoreToOutlinks方法。源代码如下：
　　

• 
    float score = scoreInjected; //得到插入的分数，不过好像没用  
  
• 
  // 得到解析后初始化的分数，这个分数在FetchThread在对网页解析之前进行了设置  
  
• 
  // scfilters.passScoreBeforeParsing(key, datum, content);  
  
• 
      String scoreString = parseData.getContentMeta().get(Nutch.SCORE_KEY);  
  
• 
      if (scoreString != null) {  
  
• 
        try {  
  
• 
          score = Float.parseFloat(scoreString);  
  
• 
        } catch (Exception e) {  
  
• 
          e.printStackTrace(LogUtil.getWarnStream(LOG));  
  
• 
        }  
  
• 
      }  
  
• 
      // 得到有效的网页个数  
  
• 
      int validCount = targets.size();  
  
• 
      if (countFiltered) {  
  
• 
        score /= allCount;  
  
• 
      } else {  
  
• 
        if (validCount == 0) {  
  
• 
          // no outlinks to distribute score, so just return adjust  
  
• 
          return adjust;  
  
• 
        }  
  
• 
        score /= validCount;  
  
• 
      }  
  
• 
      // internal and external score factor  
  
• 
      float internalScore = score * internalScoreFactor; // 设置内链接的分数值，乘以一个内链接的权重因子，默认为1.0f  
  
• 
      float externalScore = score * externalScoreFactor; // 设置外链接的分数值，乘以一个外链接的权重因子，默认为1.0f  
  
• 
      for (Entry target : targets) {  
  
• 
        try {  
  
• 
          String toHost = new URL(target.getKey().toString()).getHost();  
  
• 
          String fromHost = new URL(fromUrl.toString()).getHost();  
  
• 
          if(toHost.equalsIgnoreCase(fromHost)){  
  
• 
            target.getValue().setScore(internalScore);    // 设置内链接的贡献值  
  
• 
          } else {  
  
• 
            target.getValue().setScore(externalScore);    // 设置外链接的贡献值  
  
• 
          }  
  
• 
        } catch (MalformedURLException e) {  
  
• 
          e.printStackTrace(LogUtil.getWarnStream(LOG));  
  
• 
          target.getValue().setScore(externalScore);  
  
• 
        }  
  
• 
      }  
  
• 
      // XXX (ab) no adjustment? I think this is contrary to the algorithm descr.  
  
• 
      // XXX in the paper, where page "loses" its score if it's distributed to  
  
• 
      // XXX linked pages...  
  
• 
      return adjust;  
  
• 
    }  
  

　　
5. 总结
　　   在网页抓取中，排序算法的好坏直接影响到搜索引擎出现的更新结果，特点是在聚焦爬虫中更是这样。可能在Nutch 2.0以后就不会用OPIC，而是使用新的评分功能，在org.apache.nutch.scoring.webgraph中可以发现。
6. 参考
　　[1] Fixing the OPIC algorithm in Nutch  http://wiki.apache.org/nutch/FixingOpicScoring
[2] Abiteboul et al., 2003  http://www2003.org/cdrom/papers/refereed/p007/p7-abiteboul.html
[3] http://www.endless-loops.com/2011/03/nutch%E6%BA%90%E7%A0%81%E4%B8%AD%E7%9A%84%E9%93%BE%E6%8E%A5%E5%88%86%E6%9E%90%E7%AE%97%E6%B3%95-497.html
[4] http://wiki.apache.org/nutch/FixingOpicScoring
　　
　　作者：http://blog.iyunv.com/amuseme_lu
　　
　　
　　
　　
　　
　　
　　
　　相关文章阅读及免费下载：
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记目录》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记一》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记二》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记三（Inject）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记三（Inject CrawlDB Reader）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记四（Generate）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记四（SegmentReader分析）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记五（FetchThread）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记五（Fetcher流程）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记六（ParseSegment）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记七（CrawlDb - updatedb）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记八（LinkDb）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记九（SolrIndexer）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记十（Ntuch 插件机制简单介绍）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记十（插件扩展）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记十（插件机制分析）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记十一（页面评分机制 OPIC）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记十一（页面评分机制 LinkRank 介绍）》
　　
　　
　　
　　《Apache Nutch 1.3 学习笔记十二（Nutch 2.0 的主要变化）》
　　
　　
　　
　　更多《Apache Nutch文档》，尽在开卷有益360 http://www.docin.com/book_360