Hilltop算法

Hilltop算法介绍及实现

Posted by ZhY on March 12, 2017

hilltop是什么

上一篇博文介绍了google的PageRank算法,而这篇博文将会介绍一个超链接相关的分析算法————hilltop算法。HillTop是一种查询相关性链接分析算法,克服了的PageRank的查询无关性的缺点。简单的说HillTop算法是针对热门查询关键词来对搜索结果重新排序的一种算法。即通过HillTop算法,我们可以得出与查询的关键词关联度最高的搜索结果,让我们可以更准确的获取查询结果。

前提思想

hilltop有两个基础的思想:

一、子集传播模型

子集传播模型有一个核心思想:主题相关网页之间的链接关系对权重所占的贡献值大于主题不相关网页之间的链接关系。即HTML页面中的超链接标签——a标签中的内容所指向的网页与该标签的关联度越大,则他们所占的权重越大。 如图所示,这两个标签都指向了另外的H1标签,显然第一个例子中两个标签的关联度大于第二个例子中两个标签的关联度(第一个例子中二者都包含了关键词”计算机”,而第二个例子中二者并没有明显的联系)。

二、通过页面入链的数量和质量决定排序权重

页面入链的质量越高、数量越多,则该页面所获得的权重更大,就更有机会排在前面。 如果我的网站同时被百度、网易、腾讯等收录,那它就有很大几率排在最前的位置了。

定义与概念

一、非从属组织页面

什么是从属组织页面呢?从属组织页面就是两个页面可能具有很强的从属关系,如果两个网站具有很强的从属关系,可能会影响对于其他网站权重的计算。举个例子,比如我的母亲喜欢吃西瓜,即使我本身对于西瓜不是很感冒,但是在与我母亲在一起时,我也会表现出喜欢吃西瓜。因此只有当两个页面从属度不高时,才能保证他们确实是代表的自己的观点。

从属组织页面有以下两个特征,满足任意一个则会被认定为是从属组织页面:

特征1:主机IP地址的前三个网段相同,如:118.218.75.19 和 118.218.75.140

特征2:网络域名中的主域名相同,如:www.baidu.com 和 www.baidu.com.cn

而若两个页面不包含这两个特征,则该两页面是非从属组织页面。

二、专家页面

专家页面即所有页面中最具有权威的一部分页面,他们的影响力远大于普通页面。而专家页面需要符合以下全部的两个特征:

特征1:这些页面链接所指向的页面相互之间是非从属组织页面

特征2:被该页面所指向的页面与该页面的主题相近

三、目标页面集合

在该算法中,整个互联网中的所有页面被划分为两个子集: 专家页面集合 和 其他页面集合。

算法核心步骤

算法流程如图所示

1.构建专家页面集合

专家页面的条件:页面至少包含K个出链、K个出链指向的页面都符合非从属组织页面

2.建立索引

根据相关片断(HTML中的网页标题、H1标签、a标签)建立索引,其中:

页面标题:支配页面内所有链接

H1标签:支配H1标签内的链接

a标签:支配自己

3.对专家页面打分——即对专家页面匹配度排序

打分考虑如下三点:

1)包含查询词的多少

2)网页标题权值最高,H1其次,a标签最低

3)失配率 P=N/T(N:不属于查询词的单词个数;T:该片段的总单词数)越小越好

4.传递得分——将专家页面的得分传递给目标页面

目标页面的要求:

1)至少有两个专家页面指向该目标页面

2)专家页面和目标页面是非从属组织

传递得分为所有专家页面传递分值之和

传递分值计算:

1)找到“专家页面” 中那些能够支配目标页面的“关键片段”集合S

2)统计S中包含用户查询词的“关键片段”个数T,T越大传递的权值越大

3)“专家页面”传递给“目标页面”的分值为:E*T,E为专家页面本身在第一阶段计算得到的相关得分,T为b步骤计算的分值

例如:

整个页面的关键片段集合:{title,h1,h1中计算机,h1中操作系统,操作系统}
用户查询“计算机”,若此时页面已算出分值S。
该页面包含“计算机”的集合为:{title,h1,h1中计算机}
由于这三项全部可以支配www.computer.com页面,所以传递给www.computer.com页面的值为S*3
由于只有title和h1可以支配www.os.com页面,因此传递给www.os.com的值为S*2

不足

1.Hilltop算法在得到的相关专家页面集合数量过少时返回null,即没有查询结果。这意味着Hilltop算法无法作为单独的页面排序算法。可以配合其他的排序算法一起使用。

2.Hilltop算法过于依赖专家页面,忽视了非专家页面的影响。

3.由于算法在从专家页面中挑选相关专家页面集合时需要在线运行,因此时间复杂度较高。