数学应用-如何确定网页和查询的相关性

发表者:吴军,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 document frequency 缩写为IDF),它的公式为log(D/Dw)其中D是全部网页 数。比如,我们假定中文网页数是D=10亿,应删除词“的”在所有的网页中 都出现,即Dw =10亿,那么它的IDF=log(10 亿/10 亿)= log (1) = 0。 假如专用词“原子能”在两百万个网页中出现,即Dw=200万,则它的权重 IDF=log(500) =6.2。又假定通用词“应用”,出现在五亿个网页中,它的 权重IDF = log(2)

则只有 0.7。也就只说,在网页中找到一个“原子能”的比配相当于找到九个 “应用”的匹配。利用 IDF,上述相关性计算个公式就由词频的简单求和变成了 加权求和,即 TF1*IDF1 + TF2*IDF2 +… + TFN*IDFN。在上面的例子中,该 网页和“原子能的应用”的相关性为 0.0161,其中“原子能”贡献了 0.0126, 而“应用”只贡献了 0.0035。这个比例和我们的直觉比较一致了。

TF/IDF(term frequency/inverse document frequency) 的概念被公认 为信息检索中最重要的发明。在搜索、文献分类和其他相关领域有广泛的应用。 讲起 TF/IDF 的历史蛮有意思。IDF 的概念最早是剑桥大学的斯巴克-琼斯[注: 她有两个姓] (Karen Sparck Jones)提出来的。斯巴克-琼斯 1972 年在 一篇题为关键词特殊性的统计解释和她在文献检索中的应用的论文中提出ID F。遗憾的是,她既没有从理论上解释为什么权重IDF 应该是对数函数 lo g(D/Dw)(而不是其它的函数,比如平方根),也没有在这个题目上作进 一步深入研究,以至于在以后的很多文献中人们提到 TF/IDF 时没有引用 她的论文,绝大多数人甚至不知道斯巴克-琼斯的贡献。同年罗宾逊写了个两页 纸的解释,解释得很不好。倒是后来康乃尔大学的萨尔顿 (Salton)多次写文章、 写书讨论 TF/IDF 在信息检索中的用途,加上萨尔顿本人的大名(信息检索的世 界大奖就是以萨尔顿的名字命名的)。很多人都引用萨尔顿的书,甚至以为这个 信息检索中最重要的概 念是他提出的。当然,世界并没有忘记斯巴克-琼斯的 贡献,2004 年,在纪念文献学学报创刊 60 周年之际,该学报重印了斯巴克-琼 斯的大作。罗宾逊在同期期刊上写了篇文章,用香农的信息论解释 IDF,这回的 解释是对的,但文章写的并不好、非常冗长(足足十八页),把一个简单搞 复杂了。其实,信息论的学者们已经发现并指出,其实 IDF 的概念就是一个特 定条件下、关键词的概率分布的交叉熵(Kullback-Leibler Divergence)(详见 上一系列 )。这样,信息检索相关性的度量,又回到了信息论。

现 在的搜索引擎对 TF/IDF 进行了不少细微的优化,使得相关性的度量更加准 确了。当然,对有兴趣写一个搜索引擎的爱好者来讲,使用 TF/IDF 就足够了。

如果我们结合上网页排名(Page Rank),那么给定一个查询,有关网页综合排名 大致由相关性和网页排名乘积决定。

声明: 除非转自他站(如有侵权,请联系处理)外,本文采用 BY-NC-SA 协议进行授权 | 智乐兔
转载请注明:转自《数学应用-如何确定网页和查询的相关性
本文地址:https://www.zhiletu.com/archives-2802.html
关注公众号:智乐兔

赞赏

wechat pay微信赞赏alipay pay支付宝赞赏

上一篇
下一篇

相关文章

在线留言

你必须 登录后 才能留言!

在线客服
在线客服 X

售前: 点击这里给我发消息
售后: 点击这里给我发消息

智乐兔官微