注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Koala++'s blog

计算广告学 RTB

 
 
 

日志

 
 

相关推荐之Hitting Time  

2011-06-27 18:27:49|  分类: 搜索引擎 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

         相关搜索是我在公司做过比较早的一个项目,可惜我的代码总是不能发挥它应有的作用,最近想起来也颇感遗憾,且最近也较为空闲,就用C++重新实现,希望能对在做这一方面的人有所帮助。

在我以前的博客里写过一些Query Suggestion Using Hitting Time的内容,我的实现也基本按它给出的算法写的。

这次我使用的数据集是搜狗数据集,http://www.sogou.com/labs/dl/q.html。它的数据格式是:访问时间\t用户ID\t[查询词]\tURL在返回结果中的排名\t用户点击的顺序号\t用户点击的URL。对于这个算法有用的查询词和URL

6596513318966846         [谢婷婷]  3 1    ent.163.com/edit/011016/011016_104204.html

062050989872388496     [好男儿]  1 1    ent.sina.com.cn/f/v/myhero/index.shtml

11807085795661931       [最新私服登陆器]  3 1    blog.donews.com/zxcqsfdlq/

7206792245725311         [理发视频]       4 1    ent.sina.com.cn/m/c/2006-04-23/10581061697.html

3279773841588313         [明星]       1 1    club.yule.sohu.com/r-bagua-285533-0-52-0.html

4590153353788459         [徐静蕾]  1 1    club.chinaren.com/73000610.html

46810510882737205       [赤峰市花卉种子]  8 1    www.oyaseed.com/new.asp?catid=47

算法第一步是要得到通过某查询词访问某url的次数,对于这个数据集,它只有1.9G,这数据量以今天的眼光来看,不但不是海量,连大量都似乎不够资格,所以直接用HashMap<pair<string,string>,int>在内存里做就足够了,pair<string,string>是指查询词和url对,intpair的出现次数。我实现的时候不知道脑子在想什么,没有用map在内存里做,而是用了我自己写的一个合并类,它的好处是可以处理几百G的数据,是我是没有权限碰Hadoop集群时写出来的工具类。

合并完一共有438406对查询词和url,下面是一段结果。

[翡翠]  www.fengya.org/ 2

[翡翠]  www.huabao88.com/   1

[翡翠]  www.jade158.com/    3

[翡翠]  www.jixiangfc.com.cn/   2

[翡翠]  www.laoyujiang.com/ 1

         即通过翡翠访问www.fengya.org/的次数为两次。通过翡翠访问www.huabao88.com/的次数为一次。

         有了这个结果,就可以构造二分图了,这里的二分图,与数据结构中的二分图中的用途已经没有太大关系,所以不用参考二分图的结构。我的实现中将queryurl编号,以节约内存,数据结构中我最痴迷Map,所以我的Bipartite是用几个map实现的。

         不管怎么实现二分图吧,反正与这个算法没太大的关系,充其量只能影响一下效率。

/*

 * 算法第二步,计算transition probability,参数ij是两个不同的query

 * */

double HittingTime::transitionProb( const std::string &i, const std::string &j )

{

    set<string> iurls;

    /* 我将二分图左边称为U集合,右边称为V集合

     * U是查询词集合,VURL集合

     * getUConnectors是得到与query相连的所有urls */

    m_Graph.getUConnectors( i, iurls );

    set<string> jurls;

    m_Graph.getUConnectors( j, jurls );

 

    /* 得到两个query共同访问的queries交集 */

    set<string> intersect;

    set_intersection( iurls.begin(), iurls.end(),

                jurls.begin(), jurls.end(),

                insert_iterator<set<string> >( intersect,

intersect.begin() ) );

 

    // 算出di

    int di = 0;

    set<string>::iterator iurlsIter = iurls.begin();

    for( ; iurlsIter != iurls.end(); iurlsIter++ )

    {

       /* getWeight是得到查询词i*iurlIter的访问次数 */

       di += m_Graph.getWeight( i, *iurlsIter );

    }

 

    double weight = 0;

    set<string>::iterator iter = intersect.begin();

    for( ; iter != intersect.end(); iter++ )

    {

       /* 公式中的w(i,k) */

       int pik = m_Graph.getWeight( i, *iter );

       /* 公式中的w(j,k) */

       int pkj = m_Graph.getWeight( j, *iter );

 

       set<string> queries;

       m_Graph.getVConnectors( *iter, queries );

       int dk = 0;

       // 计算dk

       set<string>::iterator qiter = queries.begin();

       for( ; qiter != queries.end(); qiter++ )

       {

           dk += m_Graph.getWeight( *qiter, *iter );

       }

 

       weight += ((double)pik / di) * ((double)pkj / dk);

    }

 

    return weight;

}

         原论文中的第一步,我在实现的时候,感觉没什么用,不知道我理解是否有误。

相关推荐之Hitting Time - quweiprotoss - Koala++s blog

 

  1 distributed computing   http://hadoop.apache.org/   10000

  2 distributed computing   http://mahout.apache.org/   10000

  3 distributed computing   http://nutch.apache.org/    10000

  4 search engine   http://lucene.apache.org/   5000

  5 search engine   http://www.lemurproject.org/    5000

  6 info retrieval  http://lucene.apache.org/   4000

  7 info retrieval  http://www.lemurproject.org/    3000

  8 data mining http://mahout.apache.org/   2000

  9 data mining http://www.cs.waikato.ac.nz/ml/weka/    2000

 10 lucene  http://lucene.apache.org/   10000

 11 hadoop  http://hadoop.apache.org/   200000

 12 nutch   http://nutch.apache.org/    5000

 13 mahout  http://mahout.apache.org/   4000

 14 lemur   http://www.lemurproject.org/    4000   

 15 weka    http://www.cs.waikato.ac.nz/ml/weka/    4000

我按它的算法实现了之后,发现结果和我的理解有一些偏差,我就自己实现了一个类似的算法。先看上图中墨绿色的线。如果我要计算search engineB)和info retrievalC)的transition probability,即isearch engineB),jinfo retrievalC),k有两个取值,http://lucene.apache.org/3)和http://www.lemurproject.org/4),令k的一个取值为k1,另一个取值为k2w(i,k1)=w(B,3)=5000w(I,k2)=w(B,4)=5000dB=w(B,3) + w(B,4)= 5000 + 5000 = 10000. w(k1,C) = w(3,C)=4000w(k2,C)=w(4,C)=3000d3=w(3,B)+w(3,C)+w(3,E) = 3000 + 4000 + 10000 = 17000d4=w(4,B)+w(4,C)+w(4,I) = 3000 + 4000 + 10000 = 17000。懒得写了。

如果算法只是如此,那简直就是笑话,就算只为了荣誉也要搞复杂点呀。我认为有必要提醒一下的是pij不一定等于pji,现在看蓝色的线, NutchG)和DistributedA),它们都访问了http://nutch.apache.org/5),在递归的时候,Distriubeted会发现它与HadoopF)都访问了http://hadoop.apache.org/,即紫色的线。在我的计算方法中,对于这种曲折的相关关系,我会得到P(G,A)的转换概率再乘以P(A,F)的转换概率,作为G->F的权重。

         但上述的计算方法,还不足够完美,参考下图:

相关推荐之Hitting Time - quweiprotoss - Koala++s blog

 

查询词BC可以通过它们都访问的URL 3来计算,即蓝色折线,但还有一条较为曲折的相关关系,BA通过URL 1具有相关关系,即紫色折线,而AC通过URL 2有相关关系,即是红色的折线,我个人认为最两者的最大值比较合理,因为用户搜索时,他想找的一般只是一个概念,而不是一堆概念之和,所以要做的应该是估计它与哪个概念更为相近。

void HittingTime::computeWeight( const string &query, set<WeightedQuery> &nodes )

{

    int iterate = 0;

    queue<string> succQueries;

    /* 广度优先遍历 */

    succQueries.push( query );

    while( !succQueries.empty() && m_iMaxIterate > iterate )

    {

       string curQuery = succQueries.front();

       succQueries.pop();  

       set<WeightedQuery>::iterator iter;

       iter = nodes.find( WeightedQuery( curQuery ) );

       /* 得到当前查询词的权重 */

       double curWeight = iter->weight;

 

       set<string> urls;

       /*得到与这个query相连的urls*/

       m_Graph.getUConnectors( curQuery, urls );

       set<string>::iterator uiter = urls.begin();

       for( ; uiter != urls.end(); uiter++ )

       {

           set<string> queries;

           m_Graph.getVConnectors( *uiter, queries );

           set<string>::iterator qiter = queries.begin();

           /* 广度优先遍历,先将queries加入集合*/

           for( ; qiter != queries.end(); qiter++ )

           {

              /* 如果query等于自己,按理是不会发生 */

              if( curQuery == *qiter )

                  continue;

 

              set<WeightedQuery>::iterator iter;

              iter = nodes.find( WeightedQuery( *qiter ) );

              /* 得到当前查询词的权重 */

              double maxWeight =  0;

              if( iter != nodes.end() )

                  maxWeight = iter->weight;

 

              double weight = 0;

              if( curQuery == *qiter )

                  weight = 0;

              else

                  /* 权重等于转换概率乘以当前权重,初始化时将它设置为1 */

                  weight = transitionProb( curQuery, *qiter ) *

curWeight;

              if( weight > maxWeight && iter != nodes.end() )

                  nodes.erase( iter );

              if( weight > maxWeight )

              {

                  WeightedQuery wq;

                  wq.query = *qiter;

                  wq.weight = weight;

                  nodes.insert( wq );

              }

 

              succQueries.push( *qiter );

           }

       }

       iterate++;

    }

 

    /* 取前K个得分最高的queries返回 */

    topK( nodes );

}                                                          

         算法大致就是这样了,下面看一下我计算出来的结果吧,原论文中是相关度是权重最大它的相关性越小。而我这种算出来刚好相反。

         我将一部分结果列出来:

[智联]

[chinahr] : 0.00124548 | [www.51job.com] : 0.00450919 | [前程无忧] : 0.0105214 | [招聘] : 0.209677 | [招聘网] : 0.0806452 | [智联招聘] : 0.33871 | [智联招聘网] : 0.129032 | [中华英才] : 0.00633172 | [中华英才网] : 0.0297104 |

--------------------

[智联招聘]

[chinahr] : 0.00100597 | [www.51job.com] : 0.00364204 | [前程无忧] : 0.00849809 | [招聘] : 0.169355 | [招聘网] : 0.0651365 | [智联] : 0.195409 | [智联招聘网] : 0.104218 | [中华英才] : 0.00511408 | [中华英才网] : 0.0239969 |

--------------------

[智联招聘网]

[chinahr] : 0.00124548 | [www.51job.com] : 0.00450919 | [前程无忧] : 0.0105214 | [招聘] : 0.209677 | [招聘网] : 0.0806452 | [智联] : 0.241935 | [智联招聘] : 0.33871 | [中华英才] : 0.00633172 | [中华英才网] : 0.0297104 |

--------------------

[萱萱休闲吧]

[网络游戏] : 6.21615e-05 | [小游戏] : 0.396226 | [小游戏大全] : 0.00201634 | [小游戏下载] : 0.00172829 | [休闲小游戏] : 0.00702078 | [休闲游戏] : 0.00115677 | [游戏] : 0.00485841 | [在线小游戏] : 0.0224169 | [在线游戏] : 0.0050879 |

--------------------

[潇湘书院]

[萧湘书院] : 0.0490798 | [小说] : 0.306748 | [小说网] : 0.00544889 | [小说阅读网] : 0.0132646 | [虚拟军事小说] : 0.00205569 | [玄幻小说] : 0.453988 | [异侠] : 0.00965317 | [中华小说网] : 0.0042969 | [榕树下] : 0.00140964 |

--------------------

[榕树下]

[萧湘书院] : 0.000469879 | [小说] : 0.0626126 | [小说网] : 0.00412458 | [小说阅读网] : 0.00270754 | [虚拟军事小说] : 0.000130735 | [玄幻小说] : 0.0288721 | [异侠] : 0.000613908 | [中华小说网] : 0.000509326 | [潇湘书院] : 0.00152711 |

 

 

 

 

  评论这张
 
阅读(2254)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017