搜索引擎在查找时主要考虑两方面因素：网页和查询的相关性、网页的重要性
链接分析解决网页重要性的问题
网页中最重要的三个要素，出链（Out Link），入链（In Links），锚文字
链接分析算法
1、随机游走模型：对直接跳转和远程跳转两种用户浏览行为进行抽象的概念模型，用户从当前网页到达某网页的概率
2、子集传播模型：把网页划分为若干子集，给予子集内网页初始权值，根据链接关系，按照一定方式将权值传递到其他网页
不同子集传播模型在如下方面存在差异：
1）如何定义特殊子集合
2）在确定了特殊子集合所具有的性质后，如果对子集内的网页赋初始值
3）从特殊子集合将其分值传播到其他网页时，采取何种传播方式
PageRank算法
除了考虑到入链数量的影响，还参考了网页质量因素
数量假设：在Web图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要
质量假设：质量高的页面会通过链接向其他页面传递更多的权重
算法开始赋予每个网页相同的重要性得分，通过迭代递归计算来更新每个页面节点的PageRank得分，直到稳定为止
远程跳转：解决链接陷阱的通用方式，在网页向外传递分值时，不限于向出链所指网页传递，也可以以一定的概率向任意其他网页跳转（虚拟边，权值通过虚拟边向外传递）
HITS(Hypertext Induced Topic Selection)算法
Authority页面：某个领域或者某个话题相关的高质量网页
Hub页面：指向很多Authority页面
基本假设1：一个好的Authority页面会被很多好的Hub页面指向
基本假设2：一个好的Hub页面会向向很好的Authority页面
算法步骤：
1、将查询提交给某个现有的搜索引擎，或检索系统，提取排名靠前的结果（根集）
2、在根集的基础上，对其扩充（凡是与根集内网页有直接链接指向关系的网页都被扩充进来）
3、在根集+扩充网页，寻找好的Hub页面与好的Authority页面
4、初始情况下，在没有更多可利用信息前，把所有页面两个权值都设置为1
5、以相互增强的关系等原则进行多轮迭代计算，每轮迭代计算更新每个页面的两个权值，直到权值稳定为止
HITS算法不仅在搜索引擎领域应用，在自然语言处理，社交分析也有较好的效果
HITS算法的不足：计算效率较低、主题漂移，易被作弊者操纵结果，结果不稳定（添加删除个别网页或者改变少数链接关系，对排名影响会很大）
HITS算法与PageRank算法比较
1、HITS与用户输入查询相关，PageRank与查询无关
2、HITS计算效率低，PageRank离线计算，在线直接使用计算结果，计算效率高
3、HITS为局部计算，适合在客户端，PageRank为全局计算，适合步骤在服务器端
4、HITS适合处理具体用户查询，PageRank处理适合处理宽泛的用户查询
5、HITS算法在计算时，为每个页面计算两个分值，PageRank只需计算一个分值，在搜索引擎领域，更重要Authority权值，其他应用领域Hub分值也很重要
6、从反作弊角度说，PageRank从机制上优于HITS
7、PageRank比HITS计算过程更稳定，原因是PageRank计算时的远程跳转
SALSA算法
很多实验数据表明，SALSA是目前最好的链接分析算法之一
计算流程分两个阶段：
1、确定计算对象集合，与HITS类似
1）扩展网页集合，在收到用户查询后，利用现有搜索引擎或检索系统获取根集，并扩展
2）转换为无向二分图，一个子集合Hub集合，Authority集合
2、链接关系传播过程，在这一阶段采纳了随机游走模型
在权值传播过程中，权值是被所有链接平均分配的
HITS模型关注的是Hub和Authority之间的节点相互增强关系
SALSA实际上关注的是Hub-Hub及Authority-Authority之间的节点关系
Authority集合内从某个节点i转移到另一个节点j的概率，i与j之间概率是不同的，非对称
在二分图中，对于Authority集合内的某个节点来说，一定可以通过Hub子集合的节点中转后再次返回本身
建立好Authority节点关系图后，即可利用随机游走模型来计算每个节点的Authority权值
SALSA将搜索结合排序问题进一步转换为求Authority节点矩阵的主秩问题，无需迭代，计算速度快
决定Authority权值的4个因子：
1）Authority子集合中包含的节点总数
2）网页i所在连通图中的节点个数
3）网页i所在连通图中包含的入链总数
4）网页i的入链个数
SALSA算法的特点：
1、SALSA算法无需像HITS算法一样迭代计算，计算速度快
2、解决了HITS主题漂移的问题，搜索质量优于HITS
主题敏感PageRank
该算法被Google使用在个性化搜索服务中，非常适合作为个性化搜索的技术方案
用户会对某些领域感兴趣，同时当浏览某个页面时，这个页面也是与某个主题相关，跳转时，更倾向于点击和当前页面主题类似的链接
主题敏感PageRank是将用户兴趣，页面主题及链接所指向网页与当前网页主题的相似程度综合考虑而建立模型
该算法引入16种主题类型，对于某个网页来说，对应某个主题类型都有相应的PageRank分值
主题敏感的PageRank与主题相关，在接收到用户查询后，主题敏感PageRank还需要利用分类器，计算该查询隶属于事先定义好的16个主题的相似度，并在排序时利用此相似度信息
计算流程：
1、离线的分类主题PageRank数值计算，计算网页对于16个分类的相似度
将网页划分为两个集合，一个ODP对应分类主题对应的所有网页S，剩下的网页为另一个集合T
通过链接关系，从S向T传递权重，即计算网页所属类别的概率
2、在线利用算好的PageRank分值，来评估网页和用户查询的相似度
通过计算查询词所属类别的概率*网页所属类别的概率，得出两者相关性的分值，进行排序
HillTop算法
1、从海量的互联网网页中通过一定的规则选出专家页面子集合，并单独为其建立索引
2、接收用户发出的查询请求时，根据用户查询的主题，从专家页面子集合中找出部分相关性最强的专家页面，对每个专家页面计算相关性得分
3、根据目标页面（从索引系统中中取到的页面）和这些专家页面的链接关系 对目标页面进行排序
4、整合相关专家页面和得分较高的目标页面作为搜索结果，返回给用户
从属组织页面：主机IP地址的前3个网段相同，网站域名中的主域名相同
专家页面
1、与某个主题相关的高质量页面
2、这些页面的链接所指向的页面相互之间是非从属组织页面
3、这些被指向的页面大多数是与专家页面主题相近
HillTop可以与某个排序算法相结合，不适合作为一个独立的网页排序算法来使用，因为当无法得到一个足够大的专家页面时，会返回空结果。
步骤1：专家页面搜索
从1亿4千万网页中，筛选出250万作为专家页面，专家页面特征:
1、页面中至少包含K个出链，K可以人为指定
2、K个出链指向的所有页面相互之间的关系，都符合非从属组织页面
对专家页面单独建索引，且只对关键字段(Key Phrase)进行索引，关键字段包含3类信息：网页标题，H1标签内文字和URL锚文字
关键字段有影响范围（可以支配Qualify的链接），依次为，标题->H1标签->URL锚文字
在计算网页排序时，对查询字段在不同的关键字段中，会使用不同的权值
系统接收到用户查询Q，将对专家页面进行打分，主要考虑以下3类信息：
1、关键字段包含了多少词
2、关键片段本身的类型，即关键字段的类型
3、用户查询和关键词的失配率，即关键字段中不属于查询的单词个数占关键片段总单词个数的比率
步骤2：目标页面排序
Hilltop算法包含的基本假设：一个目标页面如果是满足用户查询的高质量搜索结果，其充分必要条件是该目标页面有高质量专家页面链接指向
为保证上述假设的成立，Hilltop算法在这个阶段需要对专家页面的出链仔细进行甄别，以保证查询时，选出那些和查询密切相关的目标页面。
在进行传递分值之前，首先需要对链接关系进行整理，能够获得专家页面分值的目标页面需要满足以下两点要求：
条件1、至少需要两个专家页面有链接指向目标页面，且两个专家页面不能是从属组织页面
能够获得传递分值的目标页面一定有多个专家页面链接指向，目标页面所获得的总传播分值是每个有链接指向的专家页面所传递的分值之和
条件2、专家页面和所指向的目标页面不能是从属组织页面
目标页面权值计算步骤：
1、找到专家页面中那些能够支配页面的关键片段集合S
2、统计S中包含用户查询词的关键片段个数T，T越大权值越大
3、专家页面给目标页面传递分值：E*T,E为专家页面本身在第一阶段计算得到的相关得分，T为b步骤计算分值
对于包含多个查询词的用户请求，则每个查询词单独计算，将多个查询词的传递分值累加
Hilltop算法存在与HITS算法类似的计算效率问题，随着专家页面集合的增大
其他改进算法
1、智能游走模型(Intelligent Surfer Model)
判断网页包含的链接所指向的网页内容和用户查询的相关性，以此来改善链接分析效果
2、偏置游走模型(Biased Sufer Model)
智能游走模型考虑的是网页内容和用户查询的相关性，而偏游走模型考虑的是链接指向的网页内容和当前浏览网页内容之间的相似性
3、PHITS算法(Probability Analogy of HITS)
PHITS是对HITS算法的直接改进。PHITS算法认为不同链接其传递权值的能力应该是不同的，PHITS需要计算两个页面S和T之间链接的连接强度
链接的强度依据页面S和T之间相似度确定
4、BFS算法(Backward Forward Step)
对SALSA算法的扩展，对HITS算法的限制
解除了SALSA算法只允许直接相邻网页才能有影响的限制，只要网页S和T可通达，即可对网页T施加影响，如果网页S距离网页T距离越远，那么网页S的影响就随着距离增大而呈现衰减
posted on 2013-11-12 14:06
胡满超 阅读(594)
评论(0) 编辑 收藏 引用 所属分类:
搜索引擎