主题敏感PageRank (Topic-Sensitive PageRank)

标签: pagerank topic sensitive | 发表时间:2012-09-23 13:11 | 作者:hguisu
出处:http://blog.csdn.net

        前面的讨论提到。PageRank忽略了主题相关性,导致结果的 相关性和主题性降低,对于不同的用户,甚至有很大的差别。例如,当搜索“苹果”时,一个数码爱好者可能是想要看 iphone 的信息,一个果农可能是想看苹果的价格走势和种植技巧,而一个小朋友可能在找苹果的简笔画。理想情况下,应该为每个用户维护一套专用向量,但面对海量用户这种方法显然不可行。所以搜索引擎一般会选择一种称为 Topic-Sensitive 的折中方案。Topic-Sensitive PageRank 的做法是预定义几个话题类别,例如体育、娱乐、科技等等,为每个话题单独维护一个向量,然后想办法关联用户的话题倾向,根据用户的话题倾向排序结果。

      主题敏感PageRank是PageRank算法的改进版本,该算法已被Google使用在个性化搜索服务中。

1. 基本思想

基本思想:

       通过离线计算出一个与某一主题相关的PageRank向量集合,即计算某个页面关于不同主题的得分。主要分为两个阶段:主题相关的PageRank向量集合的计算和在线查询时主题的确定(即在线相似度的计算)。 

2. 主题敏感PageRank计算流程

1、确定话题分类

           主题敏感PageRank参考ODP网站( www.dmoz.org),定义了16个大的主题类别,包括体育、商业、科技等。ODP(Open Directory Project)是人工整理的多层级网页分类导航站点(参见 图1),在顶级的16个大分类下还有更细致的小

                  

     

                                                                    图1  ODP首页

粒度分类结构,在最底层目录下,人工收集了符合该目录主题的精选高质量网页地址,以供互联网用户导航寻址。主题敏感PageRank采用了ODP最高级别的16个分类类别作为事先定义的主题类型。 

2、网页topic 归属

       这一步需要将每个页面归入最合适的分类,具体归类有很多算法,例如可以使用 TF-IDF 基于词素归类,也可以聚类后人工归类。这一步最终的结果是每个网页被归到其中一个 topic。

3、分topic 向量计算

      在PageRank的向量迭代公式:

        

        

     即 R = q  × P * R + ( 1 一 q) * e/N  (e单位向量)

     而在主题敏感PageRank中,向量迭代公式为:

      

          首先是单位向量e变为了s。

          而s是这样一个向量:对于某 topic 的s,如果网页k在此 topic 中,则s中第k个元素为1,否则为0。注意对于每一个 topic 都有一个不同的s。而|s |表示s中 1 的数量。

        假设有页面A,B,C, D,假设页面A归为 Arts,B归为 Computers,C归为 Computers,D归为 Sports。那么对于 Computers 这个 topic,s就是:

           

     假设我们设置阻尼系数q=0.8, 而|s|=2, 因此,迭代公式为:

      

       最后算出的向量就是 Computers 这个 topic 的 rank。如果实际计算一下,会发现B、C页在这个 topic 下的权重相比上面非 Topic-Sensitive 的 rank 会升高,这说明如果用户是一个倾向于 Computers topic 的人(例如程序员),那么在给他呈现的结果中B、C会更重要,因此可能排名更靠前。

4. 在线相似度计算

        最后一步就是在用户提交搜索时,确定用户的 topic 倾向,以选择合适的 rank 向量。主要方法有两种:

       一种是列出所有 topic 让用户自己选择感兴趣的项目,这种方法在一些社交问答网站注册时经常使用;

       另外一种方法利用“用户查询分类器”对查询进行分类,即搜索引擎会通过某种手段(如 cookie 跟踪)跟踪用户的行为,进行数据分析判断用户的倾向。

       如 图2,假设用户输入了查询请求“乔丹”,查询词“乔丹”隶属于体育类别的概率为0.6,娱乐类别的概率为0.1,商业类别的概率为0.3。                                              


                                            2 在线相似度计算

       在进行上述用户查询分类计算的同时,搜索系统读取索引,找出包含了用户查询“乔丹”的所有网页,并获得已计算好的各个分类主题的PageRank值,在图6-21的例子里,假设某个网页A的各个主题PageRank值分别为体育0.2,娱乐0.3以及商业0.1。

      得到用户查询的类别向量和某个网页的主题PageRank向量后,即可计算这个网页和查询的相似度。通过计算两个向量的乘积就可以得出两者之间的相关性。在图6-21的例子里,网页A和用户查询“乔丹”的相似度为:

Sim(“乔丹”,A)= 0.6*0.2+0.1*0.3+0.3*0.1=0.18

      对包含“乔丹”这个关键词的网页,都根据以上方法计算,得出其与用户查询的相似度后,就可以按照相似度由高到低排序输出,作为本次搜索的搜索结果返回给用户。

3. 利用主题敏感PageRank构造个性化搜索    

       以上内容介绍的是主题敏感PageRank的基本思想和计算流程,从其内在机制来说,这个算法非常适合作为个性化搜索的技术方案。

    在图2所示例子里,计算相似度使用的只有用户当前输入的查询词“乔丹”,如果能够对此进行扩展,即不仅仅使用当前查询词,也考虑利用用户过去的搜索记录等个性化信息。比如用户之前搜索过“耐克”,则可以推断用户输入“乔丹”是想购买运动服饰,而如果之前搜索过“姚明”,则很可能用户希望获得体育方面的信息。通过这种方式,可以将用户的个性化信息和当前查询相融合来构造搜索系统,以此达到个性化搜索的目的,更精准的提供搜索服务。

4. 主题敏感PageRank与PageRank的差异 

      PageRank算法基本遵循前面章节提到的“随机游走模型”,即用户在浏览某个网页时,如果希望跳转到其它页面,则随机选择本网页包含的某个链接,进入另外一个页面。主题敏感PageRank则对该概念模型做出改进,引入了更符合现实的假设。一般来说用户会对某些领域感兴趣,同时,当浏览某个页面时,这个页面也是与某个主题相关的(比如体育报道或者娱乐新闻),所以,当用户看完当前页面,希望跳转时,更倾向于点击和当前页面主题类似的链接,即主题敏感PageRank是将用户兴趣、页面主题以及链接所指向网页与当前网页主题的相似程度综合考虑而建立的模型。很明显,这更符合真实用户的浏览过程。

     PageRank是全局性的网页重要性衡量标准,每个网页会根据链接情况,被赋予一个唯一的PageRank分值。主题敏感PageRank在此点有所不同,该算法引入16种主题类型,对于某个网页来说,对应某个主题类型都有相应的PageRank分值,即每个网页会被赋予16个主题相关PageRank分值。

     在接受到用户查询后,两个算法在处理方式上也有较大差异。PageRank算法与查询无关,只能作为相似度计算的一个计算因子体现作用,无法独立使用。而主题敏感PageRank是查询相关的,可单独作为相似度计算公式使用。而且,在接收到用户查询后,主题敏感PageRank还需要利用分类器,计算该查询隶属于事先定义好的16个主题的隶属度,并在相似度计算时的排序公式中利用此信息。

作者:hguisu 发表于2012-9-23 13:11:59 原文链接
阅读:15 评论:0 查看评论

相关 [pagerank topic sensitive] 推荐:

主题敏感PageRank (Topic-Sensitive PageRank)

- - CSDN博客推荐文章
        前面的讨论提到. PageRank忽略了主题相关性,导致结果的. 相关性和主题性降低,对于不同的用户,甚至有很大的差别. 例如,当搜索“苹果”时,一个数码爱好者可能是想要看 iphone 的信息,一个果农可能是想看苹果的价格走势和种植技巧,而一个小朋友可能在找苹果的简笔画. 理想情况下,应该为每个用户维护一套专用向量,但面对海量用户这种方法显然不可行.

pagerank 与 相关度

- - 张沈鹏
我总是能搜索到我以前整理的文章. 我一直很困惑 pagerank 和 相关度怎么做整合. 晚上开始蒸腾搜索 研究了一下 摘录一点. 虽然每个搜索引擎都严格保密各自的明确的搜索算法,但是搜索引擎分析人士相信搜索引擎结果(排名列表)是“Page Relevance”与“PageRank”. 如果在Google上进行广泛搜索,看起来好象有几千个结果,但实际显示最多前1,000项结果.

Fast Near-Duplicate Image Search using Locality Sensitive Hashing

- -
使用LSH快速搜索相似图片,使用LSH的ANN查询按如下方式执行:1)查找查询项的“桶”(哈希值)2)与桶中的每个其他项进行比较. Locality Sensitive Hashing(LSH)是一种有用的工具,即使对于非常大的数据集也可以很好地扩展执行近似最近邻居查询. 深度学习的时代为我们复活了在向量上相似的图像,文本和音频(简单的欧几里得距离)在原始语义内容上也相似(图像的VGG特征向量,文本的Word2Vec).

[转]排名算法(一)--PageRank

- - 工作笔记
转自: https://blog.csdn.net/isuccess88/article/details/70339759. PageRank是Google研发的主要应用于评估网站可靠度和重要性的一种算法,是进行网页排名的考量指标之一. 本文将对PageRank的原理进行讲解,并以此为出发点介绍如何利用Transwarp Data Hub的Graphene在实际中满足相关分析需求.

网页重要性与PageRank的理解

- - CSDN博客互联网推荐文章
首先不要混淆网页重要性和网页相关性. 相关性:搜索关键字和某一网页之间相关的程度,主要是tf-idf值(最简单:tf*idf)来衡量. 重要性:网页之间重要程度的比较,或者说是网页质量的衡量,主要用pagerank算法计算. of course,搜索关键字搜索引擎给出的应该是重要性和相关性的结合结果.

ActiveMQ的queue以及topic两种消息处理机制分析

- - Java - 编程语言 - ITeye博客
        上一期介绍了我们项目要用到activeMQ来作为jms总线,并且给大家介绍了activeMQ的集群和高可用部署方案,本期给大家再介绍下,如何根据自己的项目需求,更好地使用activeMQ的两种消息处理模式. 1    queue与topic的技术特点对比. Publish Subscribe messaging 发布订阅消息.

MQTT--topic(主题通配符)设计 - CSDN博客

- -
 主题的设计是非常重要的,首先需要了解的就是MQTT主题过滤规则.  定阅与发布必须要有主题,只有当定阅了某个主题后,才能收到相应主题的payload,才能进行通信.  主题层级分隔符使得主题名结构化. 如果存在分隔符,它将主题名分割为多个主题层级. 斜杠(‘/’ U+002F)用于分割主题的每个层级,为主题名提供一个分层结构.

Kafka日志及Topic数据清理 - moonandstar08 - 博客园

- -
  由于项目原因,最近经常碰到Kafka消息队列拥堵的情况. 碰到这种情况为了不影响在线系统的正常使用,需要大家手动的清理Kafka Log. 但是清理Kafka Log又不能单纯的去删除中间环节产生的日志,中间关联的很多东西需要手动同时去清理,否则可能会导致删除后客户端无法消费的情况.   在介绍手动删除操作之前,先简单的介绍一下Kafka消费Offset原理.

局部敏感哈希开源项目和论文 Locality-Sensitive Hashing (LSH) · Jian Zhou

- -
Although no single definition of a similarity measure exists, usually such measures are in some sense the inverse of distance metrics.. JorenSix/TarsosLSHA Java library implementing Locality-sensitive Hashing (LSH), a practical nearest neighbour search algorithm for multidimensional vectors that operates in sublinear time..

PageRank 在 40 天里连续更新三次

- Jason - 谷奥——探寻谷歌的奥秘
感谢读者 英文SEO 和 安卓吧 的爆料. PageRank今天再次更新,这也是40天内的第三次更新,前两次是6月27日和7月18日,而7月18日那次号称是6月27日那次的修复更新,修复了之前PageRank更新后的数值错误(包括错误的将Google.com的PageRank从10降级到9). 英文SEO还发现现此次更新的多为无PR的新站.