HITS算法--从原理到实现-白红宇

HITS算法--从原理到实现

阅读量：4034 次

发布时间：2019-05-24

本文共 16375 字，大约阅读时间需要 54 分钟。

1. 算法来源

1999年，Jon Kleinberg 提出了HITS算法。作为几乎是与PageRank同一时期被提出的算法，HITS同样以更精确的搜索为目的，并到今天仍然是一个优秀的算法。

HITS算法的全称是Hyperlink-Induced Topic Search。在HITS算法中，每个页面被赋予两个属性：hub属性和authority属性。同时，网页被分为两种：hub页面和authority页面。hub，中心的意思，所以hub页面指那些包含了很多指向authority页面的链接的网页，比如国内的一些门户网站；authority页面则指那些包含有实质性内容的网页。HITS算法的目的是：当用户查询时，返回给用户高质量的authority页面。

2. 算法原理

很多算法都是建立在一些假设之上的，HITS算法也不例外。HITS算法基于下面两个假设：

一个高质量的authority页面会被很多高质量的hub页面所指向。

一个高质量的hub页面会指向很多高质量的authority页面。

什么叫“高质量”，这由每个页面的hub值和authority值确定。其确定方法为：

页面hub值等于所有它指向的页面的authority值之和。

页面authority值等于所有指向它的页面的hub值之和。

为了让大家快速理解HITS算法，先举一个简单的例子。

图中共有3个网页，它们构成了一个有向图。我们设每个网页的初始hub值和authority值都为1。记 h(p) 为页面 p 的hub值， a(p) 为页面 p 的authority值。则有 h(1)=h(2)=h(3)=1 ， a(1)=a(2)=a(3)=1 。

HITS算法的计算过程也是一个迭代的过程。在第一次迭代中，有：

a (1) = 0, a (2) = 0, a (3) = h (1) + h (2) = 2 （ 没 有 页 面 指 向 网 页 1 和 网 页 2 ） h (1) = a (3) = 2, h (2) = a (3) = 2, h (3) = 0 （ 网 页 3 没 有 指 向 任 何 页 面 ）

这里就已经可以看出网页3是一个相对好的authority页面，而网页1和网页2是相对好的hub页面。其实到这里迭代也可以结束了，因为再迭代下去无非是 a(3) ， h(1) 与 h(2) 的值不断增大，而哪个是hub页面，哪个是authority页面并不会改变。

上面的简单例子只是为了帮助理解，省略掉了很多步骤和细节。下面将详细地介绍HITS算法:。

与PageRank算法不同，HITS算法是在用户搜索后运行的，所以HITS算法的处理对象集合肯定得小很多。

首先，我们需要确定这个集合。整个互联网中的网页之间的关系可以抽象为一个有向图 G=(V,E) ，当有一个搜索请求产生时（不妨设关键字为 σ ）,我们可以取所有包含关键字 σ 的网页组成的集合 Qσ 为初始集合，并在这个集合上运行我们的HITS算法。然而，这个集合却有着明显的缺陷：这个集合可能非常之大，大到包含了数百万个网页，而这显然不是理想的集合大小。于是，我们进而想找到一个更小的集合 Sσ ，满足以下条件：

Sσ 确实足够小。

Sσ 包含很多与查询相关的页面。

Sσ 包含很多高质量的authority页面。

如何找到这个 Sσ 集合？我们假设用户输入关键字搜索，使用一个基于文本的引擎进行搜索。然后我们取排名（按照相关度排名）最靠前的t（t一般取200左右）个网页作为初始集合，记为根集合 Rσ 。这个集合满足我们上面提到的前两个条件，但是还远远不能满足第三个条件。

于是，我们需要扩展 Rσ 。一般认为，一个与关键字相关的高质量的网页即使不在 Rσ 中，那也很可能在 Rσ 中有某些网页指向它。基于此，我们扩展 Rσ 的过程如下（摘自Jon Kleinberg 的论文）：

Subgraph( σ , ψ , t, d)
　　 σ : a query string.
　　 ψ : a text-based search engine.
　　t, d: natural numbers.

　　Let Rσ denote the top t results of ψ on σ .
　　Set Sσ := Rσ

　　For each page p ∈ Rσ
　　　　Let Γ+(p) denote the set of all pages p points to.
　　　　Let Γ−(p) denote the set of all pages pointing to p.
　　　　Add all pages in Γ+(p) to Sσ .
　　　　If |Γ−(p)|≤d , then
　　　　　　Add all pages in Γ−(p) to Sσ .
　　　　Else
　　　　　　Add an arbitrary set of d pages from Γ−(p) to Sσ .
　　End
　　Return Sσ

一开始我们令 Sσ = Rσ 。然后通过上面的方法，我们将所有被 Rσ 中网页所指向的网页加入到 Sσ 中，再把一定数量的指向 Rσ 集合中网页的那些网页（每个 Rσ 中网页最多能添加d个指向它的网页）加入到 Sσ 中。为了保证 Sσ 集合的合适的大小，d不能太大，一般设置为50左右。通常情况下，扩展之后集合的大小为1000~5000个网页，满足上面的三个条件。

在计算hub值和authority值之前，我们还需要对 Sσ 进行一下处理。我们把同一个“域名”（域名指一个网站）下的网页之间的链接全部删除，因为通常这些链接只是为了让人能在这个网站下的不同网页之间进行切换，例如网站内的导航链接。在HITS算法中，这些链接与不同网站之间的链接相比，肯定是后者更能体现hub值和authority值的传递关系。所以我们在 Sσ 集合中删除这些链接，形成新集合 Gσ 。

现在，就可以开始计算hub值和authority值了。我们用 h(p) 表示页面 p 的hub值， a(p) 表示页面 p 的authority值。首先令每个页面的初始hub值 h(p) 为1，初始authority值 a(p) 也为1。然后就开始迭代计算的过程（n为 Gσ 中总的网页数）：

\forall p, a (p) = \sum i = 1 n h (i), \forall p, h (p) = \sum i = 1 n a (i)

每一轮迭代结束，都需要进行标准化，使 ∑ni=1h(i)2=∑ni=1a(i)2=1 。标准化的必要性将在算法证明部分解释。

什么时候迭代结束呢？我们可以设置一个迭代次数上限k来控制，或者设定一个阈值，当变化小于阈值的时候迭代结束。然后只要返回给用户authority值靠前的十几个网页就行了。

好了，HITS算法的原理其实就这么点，十分通俗易懂。

3. 算法证明

上面说到如何控制迭代的终止，而这又有个前提条件，那就是经过不断的迭代，每个网页的hub值和authority值最终会收敛。下面我们就来证明HITS算法的收敛性。

为了证明的方便，我们用矩阵的方式来表示HITS算法。

对于初始集合 Gσ ，用一个矩阵 M 表示 Gσ 中网页之间的关系： mij=1 表示网页 i 指向网页 j ，否则为0。用向量 H 表示所有页面的hub值，其中第i个分量表示网页i的hub值；用向量 A 表示所有页面的authority值，其中第i个分量表示网页i的authority值。所有页面的hub值和authority值初始都为1。例如上面算法原理的例子中的图就可以表示为：

M = ⎛ ⎝ ⎜ 000000110 ⎞ ⎠ ⎟

然后可以计算：

A = M T H = ⎛ ⎝ ⎜ 001001000 ⎞ ⎠ ⎟ ⎛ ⎝ ⎜ 111 ⎞ ⎠ ⎟ = ⎛ ⎝ ⎜ 002 ⎞ ⎠ ⎟, H = M A = ⎛ ⎝ ⎜ 000000110 ⎞ ⎠ ⎟ ⎛ ⎝ ⎜ 002 ⎞ ⎠ ⎟ = ⎛ ⎝ ⎜ 220 ⎞ ⎠ ⎟

一般的，我们有：

A k = M T H k - 1, H k = M A k (每 一 轮 先 计 算 A k ， 然 后 根 据 A k 计 算 H k)

更进一步，有：

A k = (M T M) k - 1 M T Z, H k = (M M T) k Z (其 中 Z 的 所 有 分 量 都 为 1)

在这里我们引用一些线性代数的知识：

定理1

一个矩阵与该矩阵的转置的乘积是对称矩阵。

定理2

实对称矩阵的特征值都是实数，且若矩阵大小为n * n，则其必有n个实特征值（包含重根）。

定理3

含有n个特征值的n阶矩阵，其主对角线元素之和等于其特征值之和。

定义1

对于实数矩阵，绝对值最大的特征值称为主特征值，对应的特征向量称为主特征向量。

定理4

如果一个实对称矩阵是非负矩阵，则其主特征向量也是非负的，并且是非0向量。

定理5

令 W 为一个n*n实对称矩阵， v 是一个n维向量且与 W 的主特征向量 ωw 非正交，则一个n维单位向量将沿着 Wkv 的方向收敛至 ωw 。

由定理1可知上面的 MTM 和 MMT 都是对称矩阵，且由定理2可知都有n个实特征值。

在 Hk=(MMT)kZ 中， Z 与 MTM 的主特征向量非正交，所以 H 向量最终将收敛至 MTM 的主特征向量。定理5中的单位向量指的就是 H 向量，为了保证其每轮迭代时都是一个单位向量，我们在每次迭代之后都对其进行标准化。

在 Ak=(MTM)k−1MTZ 中， MTZ 与 MTM 的主特征向量非正交。证明如下（这部分证明在 Jon Kleinberg 的原论文中省略了，自行证明，仅供参考）：

假 设 M T Z 与 M T M 的 主 特 征 向 量 ω w 正 交 ， 则 有 : (M T Z) T ω w = 0 \Rightarrow (Z T M) ω w = 0 \Rightarrow Z T (M ω w) = 0 ∵ M 是 非 负 矩 阵 ， ω w 也 是 非 负 矩 阵 ∴ M ω w 是 非 负 矩 阵

我们只要再证 Mωw 不是 0 矩阵，就可以推翻我们的假设了。因为 ZT 的所有分量都为1，所以 ZT 与非负且非0矩阵的内积一定不为0。在进一步证明之前，我们先证 MTM的主特征值λw≠0 ：

令 m i j 为 矩 阵 M 第 i 行 第 j 列 的 元 素 即 M = ⎛ ⎝ ⎜ ⎜ m 11 ⋮ m n 1 \dots m i j \dots m 1 n ⋮ m n n ⎞ ⎠ ⎟ ⎟, M T = ⎛ ⎝ ⎜ ⎜ m 11 ⋮ m 1 n \dots m j i \dots m n 1 ⋮ m n n ⎞ ⎠ ⎟ ⎟ 则 M T M 的 主 对 角 线 元 素 w i i = \sum j = 1 n m 2 j i ∵ M 不 是 0 矩 阵 ∴ w i i 不 全 为 0 ∴ M T M 主 对 角 线 元 素 之 和 必 不 为 0 又 ∵ 由 定 理 2 和 定 理 3 可 知 对 称 矩 阵 的 主 对 角 线 元 素 之 和 为 特 征 值 之 和 ∴ M T M 的 特 征 值 之 和 必 不 为 0 ∴ M T M 的 主 特 征 值 λ w \neq 0

下面证明 Mωw 不是 0 矩阵：

∵ ω w 是 M T M 的 主 特 征 向 量 ∴ 有 M T M ω w = λ w ω w ， 其 中 λ w 为 主 特 征 值 假 设 M ω w 是 0 矩 阵 ， 则 ： M T M ω w = 0 \Rightarrow λ w ω w = 0 但 这 显 然 不 成 立 ∵ λ w \neq 0 且 ω w 是 非 负 矩 阵 ∴ λ w ω w \neq 0 ∴ 假 设 不 成 立 ∴ M ω w 不 是 0 矩 阵

再结合上面的结论： Mωw是非负矩阵，即可得出： Mωw 是非负矩阵且不是 0 矩阵。

所以上面的假设：假设MTZ与MTM的主特征向量ωw正交不成立。所以 MTZ 与 MTM 的主特征向量非正交。也即 A 向量最终将收敛至 MTM 的主特征向量。同样的，为了保证其每轮迭代时都是一个单位向量，我们在每次迭代之后都对其进行标准化。

至此，我们便证明了HITS算法的收敛性。

4. 算法实现

下面的代码原理与我的另一篇博客相似。

4.1 基于迭代法的简单实现

用实现，需要先安装-graph-core。

class HITSIterator:    __doc__ = '''计算一张图中的hub,authority值'''    def __init__(self, dg):        self.max_iterations = 100  # 最大迭代次数        self.min_delta = 0.0001  # 确定迭代是否结束的参数        self.graph = dg        self.hub = {}        self.authority = {}        for node in self.graph.nodes():            self.hub[node] = 1            self.authority[node] = 1    def hits(self):        """        计算每个页面的hub,authority值        :return:        """        if not self.graph:            return        flag = False        for i in range(self.max_iterations):            change = 0.0  # 记录每轮的变化值            norm = 0  # 标准化系数            tmp = {}            # 计算每个页面的authority值            tmp = self.authority.copy()            for node in self.graph.nodes():                self.authority[node] = 0                for incident_page in self.graph.incidents(node):  # 遍历所有“入射”的页面                    self.authority[node] += self.hub[incident_page]                norm += pow(self.authority[node], 2)            # 标准化            norm = sqrt(norm)            for node in self.graph.nodes():                self.authority[node] /= norm                change += abs(tmp[node] - self.authority[node])            # 计算每个页面的hub值            norm = 0            tmp = self.hub.copy()            for node in self.graph.nodes():                self.hub[node] = 0                for neighbor_page in self.graph.neighbors(node):  # 遍历所有“出射”的页面                    self.hub[node] += self.authority[neighbor_page]                norm += pow(self.hub[node], 2)            # 标准化            norm = sqrt(norm)            for node in self.graph.nodes():                self.hub[node] /= norm                change += abs(tmp[node] - self.hub[node])            print("This is NO.%s iteration" % (i + 1))            print("authority", self.authority)            print("hub", self.hub)            if change < self.min_delta:                flag = True                break        if flag:            print("finished in %s iterations!" % (i + 1))        else:            print("finished out of 100 iterations!")        print("The best authority page: ", max(self.authority.items(), key=lambda x: x[1]))        print("The best hub page: ", max(self.hub.items(), key=lambda x: x[1]))if __name__ == '__main__':    dg = digraph()    dg.add_nodes(["A", "B", "C", "D", "E"])    dg.add_edge(("A", "C"))    dg.add_edge(("A", "D"))    dg.add_edge(("B", "D"))    dg.add_edge(("C", "E"))    dg.add_edge(("D", "E"))    dg.add_edge(("B", "E"))    dg.add_edge(("E", "A"))    hits = HITSIterator(dg)    hits.hits()

程序中给出的网页之间的关系如下：

运行结果如下：

This is NO.9 iterationauthority {
  'E': 0.7886751345855355, 'C': 0.2113248654398108, 'B': 0.0, 'A': 7.119870133749228e-06, 'D': 0.5773502691457247}hub {
  'E': 3.6855159786102477e-06, 'C': 0.40824829046663563, 'B': 0.7071067811721405, 'A': 0.40824829046663563, 'D': 0.40824829046663563}finished in 9 iterations!The best authority page:  ('E', 0.7886751345855355)The best hub page:  ('B', 0.7071067811721405)

4.2 MapReduce实现

class HITSMapReduce:    __doc__ = '''计算一张图中的hub,authority值'''    def __init__(self, dg):        self.max_iterations = 100  # 最大迭代次数        self.min_delta = 0.0001  # 确定迭代是否结束的参数        # graph表示整个网络图。是字典类型。        # graph[i][authority][0] 存放第i网页的authority值        # graph[i][authority][1] 存放第i网页的入链网页，是一个列表        # graph[i][hub][0] 存放第i网页的hub值        # graph[i][hub][1] 存放第i网页的出链网页，是一个列表        self.graph = {}        for node in dg.nodes():            self.graph[node] = {"authority": [1, dg.incidents(node)], "hub": [1, dg.neighbors(node)]}    @staticmethod    def normalize(ah_list):        """        标准化        :param ah_list: 一个列表，其元素为(网页名，数值)        :return: 返回一个标准化的列表，其元素为(网页名，标准化的数值)        """        norm = 0        for ah in ah_list:            norm += pow(ah[1], 2)        norm = sqrt(norm)        return [(ah[0], ah[1] / norm) for ah in ah_list]    def hits_authority_mapper(self, input_key, input_value):        """        用于计算每个页面能获得的hub值，这个hub值将传递给页面的authority值        :param input_key: 网页名，如 A        :param input_value: self.graph[input_key]，即这个网页的相关信息，包含两个字典，{a...}和{h...}        :return: [(网页名, 0.0), (出链网页1, A的hub值), (出链网页2, A的hub值)...]        """        return [(input_key, 0.0)] + \               [(out_link, input_value["hub"][0]) for out_link in input_value["hub"][1]]    def hits_hub_mapper(self, input_key, input_value):        """        用于计算每个页面能获得的authority值，这个authority值将传递给页面的hub值        :param input_key: 网页名，如 A        :param input_value: self.graph[input_key]，即这个网页的相关信息，包含两个字典，{a...}和{h...}        :return: [(网页名, 0.0), (入链网页1, A的authority值), (入链网页2, A的authority值)...]        """        return [(input_key, 0.0)] + \               [(in_link, input_value["authority"][0]) for in_link in input_value["authority"][1]]    def hits_reducer(self, intermediate_key, intermediate_value_list):        """        统计每个网页获得的authority或hub值        :param intermediate_key: 网页名，如 A        :param intermediate_value_list: A所有获得的authority值或hub值的列表:[0.0,获得的值,获得的值...]        :return: (网页名，计算所得的authority值或hub值)        """        return intermediate_key, sum(intermediate_value_list)    def hits(self):        """        计算authority值与hub值，各需要调用一次mapreduce模块        :return: self.graph，其中的 authority值与hub值 已经计算好        """        iteration = 1  # 迭代次数        change = 1  # 记录每轮迭代后的PR值变化情况，初始值为1保证至少有一次迭代        while change > self.min_delta:            print("Iteration: " + str(iteration))            # 计算每个页面的authority值并标准化            # new_authority为一个列表，元素为:(网页名，此轮迭代所得的authority值)            new_authority = HITSMapReduce.normalize(                MapReduce.map_reduce(self.graph, self.hits_authority_mapper, self.hits_reducer))            # 计算每个页面的hub值并标准化            # new_hub为一个列表，元素为:(网页名，此轮迭代所得的hub值)            new_hub = HITSMapReduce.normalize(                MapReduce.map_reduce(self.graph, self.hits_hub_mapper, self.hits_reducer))            # 计算此轮 authority值+hub值 的变化情况            change = sum(                [abs(new_authority[i][1] - self.graph[new_authority[i][0]]["authority"][0]) for i in range(len(self.graph))])            change += sum(                [abs(new_hub[i][1] - self.graph[new_hub[i][0]]["hub"][0]) for i in range(len(self.graph))])            print("Change: " + str(change))            # 更新authority值与hub值            for i in range(len(self.graph)):                self.graph[new_authority[i][0]]["authority"][0] = new_authority[i][1]                self.graph[new_hub[i][0]]["hub"][0] = new_hub[i][1]            iteration += 1        return self.graph

class HITSMapReduce:    __doc__ = '''计算一张图中的hub,authority值'''    def __init__(self, dg):        self.max_iterations = 100  # 最大迭代次数        self.min_delta = 0.0001  # 确定迭代是否结束的参数        # graph表示整个网络图。是字典类型。        # graph[i][authority][0] 存放第i网页的authority值        # graph[i][authority][1] 存放第i网页的入链网页，是一个列表        # graph[i][hub][0] 存放第i网页的hub值        # graph[i][hub][1] 存放第i网页的出链网页，是一个列表        self.graph = {}        for node in dg.nodes():            self.graph[node] = {
  "authority": [1, dg.incidents(node)], "hub": [1, dg.neighbors(node)]}    @staticmethod    def normalize(ah_list):        """        标准化        :param ah_list: 一个列表，其元素为(网页名，数值)        :return: 返回一个标准化的列表，其元素为(网页名，标准化的数值)        """        norm = 0        for ah in ah_list:            norm += pow(ah[1], 2)        norm = sqrt(norm)        return [(ah[0], ah[1] / norm) for ah in ah_list]    def hits_authority_mapper(self, input_key, input_value):        """        用于计算每个页面能获得的hub值，这个hub值将传递给页面的authority值        :param input_key: 网页名，如 A        :param input_value: self.graph[input_key]，即这个网页的相关信息，包含两个字典，{a...}和{h...}        :return: [(网页名, 0.0), (出链网页1, A的hub值), (出链网页2, A的hub值)...]        """        return [(input_key, 0.0)] + \               [(out_link, input_value["hub"][0]) for out_link in input_value["hub"][1]]    def hits_hub_mapper(self, input_key, input_value):        """        用于计算每个页面能获得的authority值，这个authority值将传递给页面的hub值        :param input_key: 网页名，如 A        :param input_value: self.graph[input_key]，即这个网页的相关信息，包含两个字典，{a...}和{h...}        :return: [(网页名, 0.0), (入链网页1, A的authority值), (入链网页2, A的authority值)...]        """        return [(input_key, 0.0)] + \               [(in_link, input_value["authority"][0]) for in_link in input_value["authority"][1]]    def hits_reducer(self, intermediate_key, intermediate_value_list):        """        统计每个网页获得的authority或hub值        :param intermediate_key: 网页名，如 A        :param intermediate_value_list: A所有获得的authority值或hub值的列表:[0.0,获得的值,获得的值...]        :return: (网页名，计算所得的authority值或hub值)        """        return intermediate_key, sum(intermediate_value_list)    def hits(self):        """        计算authority值与hub值，各需要调用一次mapreduce模块        :return: self.graph，其中的 authority值与hub值 已经计算好        """        iteration = 1  # 迭代次数        change = 1  # 记录每轮迭代后的PR值变化情况，初始值为1保证至少有一次迭代        while change > self.min_delta:            print("Iteration: " + str(iteration))            # 计算每个页面的authority值并标准化            # new_authority为一个列表，元素为:(网页名，此轮迭代所得的authority值)            new_authority = HITSMapReduce.normalize(                MapReduce.map_reduce(self.graph, self.hits_authority_mapper, self.hits_reducer))            # 计算每个页面的hub值并标准化            # new_hub为一个列表，元素为:(网页名，此轮迭代所得的hub值)            new_hub = HITSMapReduce.normalize(                MapReduce.map_reduce(self.graph, self.hits_hub_mapper, self.hits_reducer))            # 计算此轮 authority值+hub值 的变化情况            change = sum(                [abs(new_authority[i][1] - self.graph[new_authority[i][0]]["authority"][0]) for i in range(len(self.graph))])            change += sum(                [abs(new_hub[i][1] - self.graph[new_hub[i][0]]["hub"][0]) for i in range(len(self.graph))])            print("Change: " + str(change))            # 更新authority值与hub值            for i in range(len(self.graph)):                self.graph[new_authority[i][0]]["authority"][0] = new_authority[i][1]                self.graph[new_hub[i][0]]["hub"][0] = new_hub[i][1]            iteration += 1        return self.graph

if __name__ == '__main__':    dg = digraph()    dg.add_nodes(["A", "B", "C", "D", "E"])    dg.add_edge(("A", "C"))    dg.add_edge(("A", "D"))    dg.add_edge(("B", "D"))    dg.add_edge(("C", "E"))    dg.add_edge(("D", "E"))    dg.add_edge(("B", "E"))    dg.add_edge(("E", "A"))    h = HITSMapReduce(dg)    hits_result = h.hits()    print("The final iteration result is")    for key, value in hits_result.items():        print(key + " authority: ", value["authority"][0], " hub: ", value["hub"][0])    max_authority_page = max(hits_result.items(), key=lambda x: x[1]["authority"][0])    max_hub_page = max(hits_result.items(), key=lambda x: x[1]["hub"][0])    print("The best authority page: ", (max_authority_page[0], max_authority_page[1]["authority"][0]))    print("The best hub page: ", (max_hub_page[0], max_hub_page[1]["hub"][0]))

运行结果为：

The final iteration result isE authority:  0.7886751345948128  hub:  8.64738646858812e-10A authority:  7.060561487452559e-10  hub:  0.408267180858587C authority:  0.2113248654051872  hub:  0.40823884510260666B authority:  0.0  hub:  0.7071067809972986D authority:  0.5773502691896258  hub:  0.40823884510260666The best authority page:  ('E', 0.7886751345948128)The best hub page:  ('B', 0.7071067809972986)

以上便是HITS算法的MapReduce实现。