搜索引擎的网页 质量排序-PageRank算法 & 相关度排序-TF-IDF算法_搜索引擎网页排序 矩阵

对于大部分用户的查询，今天的搜索引擎，都会返回成千上万条结果，那么应该如何排序,把用户最想看到的结果排在前面呢?这个问题很大程度上决定了搜索引擎的质量。总的来讲，对于一个特定的查询，搜索结果的排名取决于两组信息，关于网页的质量信息( Quality ), 和这个查询与每个网页的相关性(Relevance)。

网页的质量——PageRank算法

真正找到计算网页自身质量的完美的数学模型的是Google的创始人拉里●佩奇和谢尔盖●布林。Google的“PageRank”(网页排名)是怎么回事呢? 其实简单地说就是民主表决。打个比方，假如我们要找李开复博士，有100个人举手说自己是李开复。那么谁是真的呢?也许有好几个真的，但即使如此谁又是大家真正想找的呢?如果大家都说在创新工场的那个是真的，那么他就是真的。

在互联网上，如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。这就是PageRank的核心思想。当然Google的PageRank算法实际上要复杂得多。比如说，对来自不同网页的链接区别对待，因为网页排名高的那些网页的链接更可靠，于是要给这些链接以较大的权重。这就好比在现实生活中股东大会里的表决，是要考虑每个股东的表决权(Voting Power)的，拥有20%表决权的股东和拥有1%表决权的股东，对最后的表决结果的影响力明显不同。PageRank 算法考虑了这个因素，即网页排名高的网站贡献的链接权重大。

现在举一个例子，我们知道一个网页Y的排名应该来自于所有指向这个网页的其他网页$X_1,X_2,...,X_k$的权重之和，如下图中，Y的网页排名pagerank = 0.001 + 0.01 + 0.02 + 0.05 = 0.081。

接下来的问题是X1,X2, X3, X4的权重分别是多少,如何度量。佩奇认为,应该是这些网页本身的网页排名。现在麻烦来了,计算搜索结果的网页排名过程中需要用到网页本身的排名，这不成了“先有鸡还是先有蛋”的问题了吗?

破解这个怪圈的应该是布林。他把这个问题变成了一个二维矩阵相乘的问题，并且用迭代的方法解决了这个问题。他们先假定所有网页的排名是相同的，并且根据这个初始值，算出各个网页的第一次迭代排名， 然后再根据第一次迭代排名算出第二次的排名。他们两人从理论上证明了不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到排名的真实值。值得一提的事，这种算法是完全没有任何人工干预的。理论问题解决了, 又遇到实际问题。因为互联网上网页的数量是巨大的,上面提到的二维矩阵从理论上讲有网页数量的二次方这么多个元素。如果假定有十亿个网页，那么这个矩阵就有一百亿亿个元素。这么大的矩阵相乘，计算量是非常大的。佩奇和布林两人利用稀疏矩阵计算的技巧，大大简化了计算量，并实现了这个网页排名算法。

互联网网页数量的增长使得PageRank的计算量越来越大，必须利用多台服务器才能完成。Google 早期时，PageRank 计算的并行化是半手工、半自动的，这样更新一遍所有网页的PageRank的周期很长。2003年，Google的工程师发明了MapReduce 这个并行计算的工具，PageRank 的并行计算完全自动化了，这就大大缩短了计算时间，使网页排名的更新周期比以前短了许多。

网页的相关性——TF-IDF算法

短语“原子能的应用”可以分成三个关键词: 原子能、的、应用。根据直觉,我们知道，包含这三个词较多的网页应该比包含它们较少的网页相关。当然，这个办法有一个明显的漏洞，那就是内容长的网页比内容短的网页占便宜，因为长的网页总的来讲包含的关键词要多些。因此，需要根据网页的长度，对关键词的次数进行归一化，也就是用关键词的次数除以网页的总字数。我们把这个商称为“关键词的频率”，或者“单文本词频”( Term Frequency)，比如，某个网页上一共有1000词,其中“原子能”、“的”和“应用”分别出现了2次、35次和5次，那么它们的词频就分别是0.002、0.035 和0.005。将这三个数相加，其和0.042就是相应网页和查询“原子能的应用”的“单文本词频”.

因此，度量网页和查询的相关性，有一个简单的方法，就是直接使用各个关键词在网页中出现的总词频。具体地讲,如果一个查询包含N个关键词$W_1,W_2,...W_N$,它们在一个特定网页中的词频分别是: $T{F}_1,...,T{F}_N$。(TF: Term Frequency,是词频一词的英文缩写)。那么，这个查询和该网页的相关性(即相似度)就是:
$$T{F}_1+T{F}_2+...+T{F}_N$$
读者可能已经发现了又一个漏洞。在上面的例子中，“的”这个词占了总词频的80%.上，而它对确定网页的主题几乎没什么用处。我们称这种词叫“停止词”(Stop Word)，也就是说，在度量相关性时不应考虑它们的频率。在汉语中，停止词还有“是”、“和” 、“中”、 “地” 、“得”等几十个。忽略这些停止词后，上述网页和查询的相关性就变成了0.007, 其中“原子能”贡献了0.002，“应用” 贡献了0.005。

细心的读者可能还会发现另一个小漏洞。在汉语中，“应用”是个很通用的词，而“原子能”是个很专业的词，后者在相关性排名中比前者重要。因此，需要对汉语中的每一个词给一个权重，这个权重的设定必须满足下面两个条件:

1. 一个词预测主题的能力越强，权重越大，反之，权重越小。在网页中看到“原子能”这个词，或多或少能了解网页的主题。而看到“应用”一词，则对主题基本.上还是一无所知。因此，“原子能”的权重就应该比应用大。
2. 停止词的权重为零。

很容易发现，如果一个关键词只在很少的网页中出现，通过它就容易锁定搜索目标，它的权重也就应该大。反之,如果一个词在大量网页中出现，看到它仍然不很清楚要找什么内容，因此它的权重就应该小。概括地讲，假定一个关键词w在$D_w$个网页中出现过，那么$D_w$越大, w的权重越小，反之亦然。在信息检索中,使用最多的权重是“逆文本频率指数”(Inverse Document Frequency, 缩写为IDF )，它的公式为$\log \left(\frac{D}{D_w}\right)$.

其中D是全部网页数。比如，假定中文网页数是D= 10亿，停止词“的”在所有的网页中都出现，即$D_w$= 10亿，那么它的IDF =log(10亿/ 10
亿)= log(1)=0。假如专用词“原子能”在200万个网页中出现，即$D_w$= 200万, 则它的权重IDF = log(500) = 8.96。又假定通用词“应用”出现在五亿个网页中，它的权重IDF = log(2)， 则只有1。也就是说，在网页中找到一个“原子能”的命中率( Hits)相当于找到九个“应用”的命中率。利用IDF, 上述相关性计算的公式就由词频的简单求和变成了加权求和，即
$$T{F}_1\cdot ID{F}_1+T{F}_2\cdot ID{F}_2+\cdots +T{F}_N\cdot ID{F}_N$$
在上面的例子中，该网页和“原子能的应用”的相关性为0.0161, 其中“原子能”贡献了0.0126，而“应用”只贡献了0.0035。这个比例和我们的
直觉比较一致了。

来源

[1]吴军. 数学之美 : Beauty of mathematics[M]. 人民邮电出版社, 2014.