数学之美 系列九 — 如何确定网页和查询的相关性

发表者:吴军,Google 研究员

[我们已经谈过了如何自动下载网页、如何建立索引、如何衡量网页的质量(Page Rank)。我们今天谈谈如何确定一个网页和某个查询的相关性。了解了这四个方面,一个有一定编程基础的读者应该可以写一个简单的搜索引擎了,比如为您所在的学校或院系建立一个小的搜索引擎。]

我们还是看上回的例子,查找关于“原子能的应用”的网页。我们第一步是在索引中找到包含这三个词的网页(详见关于布尔运算的系列)。现在任何一个搜索引擎都包含几十万甚至是上百万个多少有点关系的网页。那么哪个应该排在前面呢?显然我们应该根据网页和查询“原子能的应用”的相关性对这些网页进行排序。因此,这里的关键问题是如何度量网页和查询的相关性。

我们知道,短语“原子能的应用”可以分成三个关键词:原子能、的、应用。根据我们的直觉,我们知道,包含这三个词多的网页应该比包含它们少的网页相关。当然,这个办法有一个明显的漏洞,就是长的网页比短的网页占便宜,因为长的网页总的来讲包含的关键词要多些。因此我们需要根据网页的长度,对关键词的次数进行归一化,也就是用关键词的次数除以网页的总字数。我们把这个商称为“关键词的频率”,或者“单文本词汇频率”(Term Frequency),比如,在某个一共有一千词的网页中“原子能”、“的”和“应用”分别出现了 2 次、35 次 和 5 次,那么它们的词频就分别是 0.002、0.035 和 0.005。 我们将这三个数相加,其和 0.042 就是相应网页和查询“原子能的应用”相关性的一个简单的度量。概括地讲,如果一个查询包含关键词 w1,w2,…,wN, 它们在一篇特定网页中的词频分别是: TF1, TF2, …, TFN。 (TF: term frequency)。 那么,这个查询和该网页的相关性就是:TF1 + TF2 + … + TFN。

读者可能已经发现了又一个漏洞。在上面的例子中,词“的”站了总词频的 80% 以上,而它对确定网页的主题几乎没有用。我们称这种词叫“应删除词”(Stopwords),也就是说在度量相关性是不应考虑它们的频率。在汉语中,应删除词还有“是”、“和”、“中”、“地”、“得”等等几十个。忽略这些应删除词后,上述网页的相似度就变成了0.007,其中“原子能”贡献了0.002,“应用”贡献了 0.005。

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

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

2. 应删除词的权重应该是零。

我们很容易发现,如果一个关键词只在很少的网页中出现,我们通过它就容易锁定搜索目标,它的权重也就应该大。反之如果一个词在大量网页中出现,我们看到它仍然不很清楚要找什么内容,因此它应该小。概括地讲,假定一个关键词 w 在 Dw 个网页中出现过,那么 Dw 越大,w 的权重越小,反之亦然。在信息检索中,使用最多的权重是“逆文本频率指数” (Inverse […]

Category

Archives