AI内参_52_050_经典图算法之HITS

你好，我是洪亮杰。

今天我和你分享的主题是经典的图算法HITS.这周我们分享的内容是如何理解网页和网页之间的关系。

周一呢我们介绍了用图来表达网页与网页之间的关系，并计算网页的重要性，这就是经典算法。

Page rank.今天呢我来介绍一下page rank的姊妹算法。

Hits算法。

我先来简单的说说HITS的历史。

Hits是heyer、 text、 induced topic search算法的简称。

Hits算法是由康奈尔大学计算机科学教授乔克莱恩堡与一九九八年发明的，正好和我们周一讲的布林和佩奇发表的page rank算法是同一年。

这里呢有必要简单来介绍一下乔这个人。

乔呢于一九七一年出生在马萨朱塞州波士顿。

一九九三年，他毕业于康奈尔大学，获得了计算机科学学士学位，并于一九九六年从麻省理工大学获得计算机博士学位。

一九九八年的时候，乔正在位于美国西海岸硅谷地区的IBM埃尔马登研究院做博士后研究。

Hits的工作最早发表于一九九八年在旧金山举办的第九届ACMCM离散算法年会上，乔目前是美国国家工程院和美国自然与人文科学院院士。

顺便提一下，乔德弟弟罗伯特克莱恩堡也在康奈尔大学计算机系任教职。

在介绍HITS算法的基本原理之前，我们首先先来复习一下网页的网络结构。

每一个网页都有一个输出链接的集何输出链接指的是从当前网页出发所指向的其他页面。

比如从页面a有一个链接到页面，b那么b就是a的输出链接。

比据这个定义我们来看，输入节点指的就是指向当前页面的其他页面。

比如页面c指向页面a那么c就是a的输入链接。

要理解HITS算法，我们还需要引入一组概念、权威节点和输纽节点。

这两点节点到底是什么意思呢？ Hits给出了一种循环的定义，好的权威节点是很多枢纽节点的输出链接，好的枢纽节点则指向很多好的权威节点。

这种循环定义，我们在配置rank的定义中已经建树过了，很明显要用数学的方法来表述权威节点和枢纽节点之间的关系，就必须要为每一个页面准备两个值。

因为从直觉上来说，不可能有一个页面完全是权威，也不可能有一个页面完全是枢纽，绝大多数页面都在这两种角色中转换，或者说同时扮演这两类角色。

数学上对于每一个页面i我们用x来表达输入页面的权威值，用y来表达这个页面的枢纽值。

那么一个最直观的定义，对于i的权威值x来说，它是所有i页面的输入链接的枢纽值的总和。

同理，i的枢纽值是所有i页面输出链接的权威值的总和，这就是HITS算法的原始定义。

我们可以看到，如果i页面的输入链接的枢纽值大，说明i页面经常被一些好的枢纽节点链接到，那么i自身的权威性自然也就增加了。

反之，如果i能够经常指向好的权威节点，那i自身的枢纽性质也就显得重要了。

那然和配置rank值一样，x和y在HITS算法里也都是视线不可知的。

因此呢HITS算法的重点就是要求解x y如果把所有页面的x和y都表达成向量的形式，那么HITS算法可以写成x是矩阵l的转置和y的乘积，而y是矩阵l和x的乘积。

这里的矩阵l就是一个邻接矩阵每一行列，表达某两个页面是否相连，进行一下代数变形，我们就可以得到x其实是一个矩阵a乘以x这里的a是l的转置乘以LY,其实是一个矩阵b乘以y这里的b是l乘以l的转置于是惊人的一点出现了，那就是HITS.算法其实是需要求解矩阵a或者矩阵b的主特征向量，也就是特征值最大所对应的特征向量用于求解x或者y这一点和配置rank用矩阵表达的形式不谋而合。

也就是说，尽管配置rank和HITS在思路和概念上完全不同，并且在最初的定义式上南辕北辙。

但是经过一番变形之后，我们能够把两者都划归为某种形式的矩阵。

求解特征向量的问题，实际上把图表达为矩阵，并且通过特征向量对图的一些特性进行分析，是图算法中的一个重要分支。

既然我们已经知道了需要计算最大的特征向量，那么之前计算配置rank所使用的乘幂法在这里也是可以使用的，我们在这里就不展开了。

如何把HITS算法用于搜索中呢？最开始提出HITS的时候是这么使用的。

首先我们根据某个查询关键字构建一个相邻图，这个图包括所有和这个查询关键字相关的页面。

这里我们可以简化为所有包含查询关键字的页面。

这一步在现代搜索引擎中，通过倒排索引就可以很容易的得到。

有了这个相邻图以后，我们根据这个图建立邻接矩阵，然后就可以通过邻接矩阵计算这些节点的权威值和枢纽。

值当计算出这两组值之后，我们就可以根据这两组值给用户展现两种网页。

排序的结果，分别是根据不同的假设。

值得注意的是，配置rank是查询关键字无关的算法，也就是说每个页面的配置rank值并不随着查询关键字的不同而产生不同。

而HITS算法是查询关键字相关的算法，从这点来说，HITS就和配置rank有本质的不同。

Hits算法依靠这种叠键字方法来计算全权维值和枢纽值。

你一定很好奇，这样的计算究竟收敛吗？是不是也需要像配ge rank样进行特别的处处理？答案是，HITS的一定是收敛的，只点比原始的配置，rank情况要好。

然而，HITS在原始的情况下，不一定收敛到唯一一组权威值和枢纽值。

也就是说，解是不唯一的。

因此，我们其实需要对HITS进行一部分类似于配置rank处理，那就是让HITS的邻接句阵里面所有的节点都能够达到其他任何节点，只只是比比较小概率率。

经过这样的修改，HITS就能够收敛到唯一的权威值和枢纽值了。

Hits算法的好处是为用户提供了一种全新的视角。

对于同一个查询关键字，HITS提供的权威排序和枢纽排序，能够帮助用户理解自己的需求。

当然，HITS的弱点也来自于这个依赖于查询关键字的问题。

如果把所有的计算都留在用户输入查询关键字以后，并且需要在响应时间内计算出所有的权威值和枢纽值，然后进行排序，这里面的计算量是很大的。

所以后来有研究者开始使用全局的网页图，提前来计算所有网页的权威值和枢纽值。

然而，这样做就失去了对某一个关键词的相关信息。

今天我为你讲了HITS算法的核心思想，一起来回顾一下要点。

第一，我们讲了HITS的一些简明历史。

第一，我们讲了HITS最原始的定义和算法，并且联系置parank讲了两者的异同之处。

第三，我们分析了HITS的一些特点。

最后呢给你留一个思考题，有没有办法把权威值和枢纽值所对应的两个排序合并成为一个排序呢？欢迎你给我留言，和我一起讨论。