大话主题敏感PageRank

本文节选自《这就是搜索引擎：核心技术详解》第六章

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

6.6.1 主题敏感PageRank与PageRank的差异

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

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

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

6.6.2 主题敏感PageRank计算流程

主题敏感PageRank计算主要由两个步骤构成，第一步是离线的分类主题PageRank数值计算；第二步是在线利用算好的主题PageRank分值，来评估网页和用户查询的相似度，以按照相似度排序提供给用户搜索结果。下面以具体示例来了解主题敏感PageRank的计算流程。

分类主题PageRank计算

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

图6-19 ODP首页

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

主题敏感PageRank对16个类别的主题，依次计算该类别的PageRank分值，图6-20图示了其计算流程和基本思路，为了简化说明，示意图只表现出了三个分类类别。在计算某个类别的PageRank分值时，将所有网页划分为两个集合，一个集合是ODP对应分类主题下所包括的所有网页，即人工精选的高质量网页，可以称之为集合S，剩下的网页放入另外一个集合内，可称之为集合T。在计算PageRank时，由于集合S内的网页能够很好地表征分类主题，所以赋予较大的跳转概率值。通过这种设定，集合S内的网页根据链接关系向集合T中网页传递权值，因为直接有链接指向的往往主题类似，这样就将与该分类主题内容相似的网页赋予较高的PageRank值，而无关的网页则赋予较低权重的PageRank分值，以此方式达到对网页所包含主题的判断。

图6-20 网页的分类主题PageRank计算

回到图6-20，假设有个编号为1号的网页，其被列为ODP目录中的艺术类别中，在对艺术类别进行PageRank计算时，1号网页在集合S内，计算结束后，该网页获得的PageRank分值为0.5。当计算体育和商业类别的主题PageRank分值时，1号网页在集合T中，获得了相应的集合S中网页传递的权值，分别为0.02和0.01。在所有类别计算结束后，1号网页获得了3个不同主题对应的PageRank分值，组成一个主题PageRank向量。通过类似的方式，互联网内任意网页也可以获得相应的主题相关PageRank向量。通过以上过程可以看出，主题相关的PageRank分值向量其实代表了某个网页所讲述内容所属类别的概率。

注意：在上述计算主题PageRank过程中，从集合S和集合T的划分，及其权值传播方式中可以看出，该步骤计算过程也符合“子集传播模型”。但是由于本算法主框架及其出发点都是为了改进PageRank，所以将其归入“随机游走模型”的衍生算法类别中。

在线相似度计算

图6-21给出了主题敏感PageRank在线计算用户查询与网页相似度的示意图。假设用户输入了查询请求“乔丹”，搜索系统首先利用“用户查询分类器”对查询进行分类，计算用户查询隶属于定义好的各个类别的概率分别是多少，在我们给出的例子里，“乔丹”隶属于体育类别的概率为0.6，娱乐类别的概率为0.1,商业类别的概率为0.3。

图6-21 在线相似度计算

在进行上述用户查询分类计算的同时，搜索系统读取索引，找出包含了用户查询“乔丹”的所有网页，并获得上一步骤离线计算好的各个分类主题的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

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

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

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

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