nutch 1.3 评分机制 opic 详解

Nutch 1.3 学习笔记 11-1 页面评分机制 OPIC
--------------------------------------
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[i]，原论文中OPIC算法的伪代码如下：
view plain

引用
OPIC:    
    On-line Page Importance Computation    
        
    for each i let C[i] := 1/n ;    
    for each i let H[i] := 0 ;    
    let G:=0 ;    
    do forever    
    begin    
     choose some node i ;    
     %% each node is selected    
     %% infinitely often    
        
     H[i] += C[i];    
     %% single disk access per page    
        
     for each child j of i,    
     do C[j] += C[i]/out[i];    
     %% Distribution of cash    
     %% depends on L    
        
     G += C[i];    
     C[i] := 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方法。源代码如下：
view plain
  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<Text, CrawlDatum> 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