`
wangdei
  • 浏览: 372345 次
社区版块
存档分类
最新评论

(转贴)数学之美 系列九 -- 如何确定网页和查询的相关性

阅读更多

我们已经谈过了如何自动下载网页、如何建立索引、如何衡量网页的质量(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 年在一篇题为关键词特殊性的统计解释和她在文献检索中的应用的论文中提出IDF。遗憾的是,她既没有从理论上解释为什么权重IDF 应该是对数函数 log(D/Dw)(而不是其它的函数,比如平方根),也没有在这个题目上作进一步深入研究,以至于在以后的很多文献中人们提到 TF/IDF 时没有引用她的论文,绝大多数人甚至不知道斯巴克-琼斯的贡献。同年罗宾逊写了个两页纸的解释,解释得很不好。倒是后来康乃尔大学的萨尔顿(Salton)多次写文章、写书讨论 TF/IDF 在信息检索中的用途,加上萨尔顿本人的大名(信息检索的世界大奖就是以萨尔顿的名字命名的)。很多人都引用萨尔顿的书,甚至以为这个信息检索中最重要的概念是他提出的。当然,世界并没有忘记斯巴克-琼斯的贡献,2004年,在纪念文献学学报创刊 60 周年之际,该学报重印了斯巴克-琼斯的大作。罗宾逊在同期期刊上写了篇文章,用香农的信息论解释 IDF,这回的解释是对的,但文章写的并不好、非常冗长(足足十八页),把一个简单问题搞复杂了。其实,信息论的学者们已经发现并指出,其实 IDF 的概念就是一个特定条件下、关键词的概率分布的交叉熵(Kullback-Leibler Divergence)(详见上一系列)。这样,信息检索相关性的度量,又回到了信息论。

现在的搜索引擎对 TF/IDF 进行了不少细微的优化,使得相关性的度量更加准确了。当然,对有兴趣写一个搜索引擎的爱好者来讲,使用 TF/IDF 就足够了。 如果我们结合上网页排名(Page Rank),那么给定一个查询,有关网页综合排名大致由相关性和网页排名乘积决定.
http://googlechinablog.com/2006/06/blog-post_27.html

分享到:
评论

相关推荐

    [转贴]Symbian编程VC开发环境设置 (方便个人学习用,转载自 rocklys的专栏,转贴请搜索原作者) - waferham的专栏 - CSDNBlog.mht

    [转贴]Symbian编程VC开发环境设置 (方便个人学习用,转载自 rocklys的专栏,转贴请搜索原作者) - waferham的专栏

    论坛转贴 v1.0 JS版-源码.zip

    【标题】"论坛转贴 v1.0 JS版-源码.zip" 提供的是一个基于JavaScript的论坛转贴功能的源代码实现。JS版通常指的是使用JavaScript编程语言编写的版本,这表明该软件可能主要用于网页端,利用浏览器的JavaScript引擎...

    Spark 入门实战系列

    Spark 入门实战系列,适合初学者,文档包括十部分内容,质量很好,为了感谢文档作者,也为了帮助更多的人入门,传播作者的心血,特此友情转贴: 1.Spark及其生态圈简介.pdf 2.Spark编译与部署(上)--基础环境搭建....

    行业分类-设备装置-FPC吸附胶纸转贴组件.zip

    合适的胶纸类型和转贴工艺能够有效防止FPC在使用过程中发生松动、脱落,甚至损坏,从而保证设备的稳定运行和信号传输的可靠性。 FPC吸附胶纸转贴组件在各种设备装置中都有应用,例如智能手机、平板电脑、医疗设备、...

    动易系统的论坛转贴工具 -ASP源码.zip

    3. 数据库交互:可能使用ADO(ActiveX Data Objects)来连接和查询数据库,如SQL Server或Access,进行论坛数据的读取和写入。 4. HTML和CSS:尽管主要关注的是服务器端的ASP,但理解和使用HTML和CSS来构建和美化...

    电子政务-导电泡棉转贴装置.zip

    综上所述,"导电泡棉转贴装置"在电子政务中的应用涉及到硬件设计、设备维护、电磁兼容性和法规遵从等多个方面,是保障电子政务系统稳定运行的关键技术之一。通过阅读"行业分类-电子政务-导电泡棉转贴装置.pdf"这份...

    Axis学习笔记(网页转贴)

    **Axis学习笔记(网页转贴)** Axis是一个开源的Java库,主要用于创建和使用Web服务。它是Apache软件基金会的一部分,广泛应用于开发基于SOAP(简单对象访问协议)的Web服务。本学习笔记将深入探讨Axis在Web服务开发...

    电子功用-导电胶配对模切对半转贴加工方法

    本篇将详细探讨“电子功用-导电胶配对模切对半转贴加工方法”,这是一种高效的生产工艺,旨在提高电子产品的性能和可靠性。 导电胶主要由导电填料(如金属颗粒)、树脂基体和添加剂组成。它的特性在于既能保持良好...

    行业文档-设计装置-木器、玻璃用贴花纸生产及转贴方法.zip

    《木器、玻璃用贴花纸生产及转贴方法》是一个深入探讨装饰材料工艺的行业文档,主要聚焦于贴花纸在木器和玻璃制品上的应用。这份文档可能包含了从贴花纸的设计、生产到实际转贴过程中的各种技术细节和实践经验。 1....

    jquery的转贴功能实现

    在网页开发中,jQuery是一个非常流行的JavaScript库,它极大地简化了DOM操作、事件处理和Ajax交互等任务。在本主题中,我们将深入探讨如何利用jQuery实现“转贴”功能,这是一种常见的社交媒体分享功能,允许用户将...

    [转贴]九大BI厂商点将录

    【标题解析】:“九大BI厂商点将录”这个标题揭示了文章的核心内容,它是一个关于商业智能(Business Intelligence,简称BI)领域中的九个主要厂商的综合评价和分析。BI是IT行业的一个重要分支,专注于数据提取、...

    Struts-menu源码分析(转贴).rar

    它简化了构建基于JSP和Servlet的Web应用的过程,通过提供一系列的控制器、标签库和验证框架来帮助开发者组织和管理代码。 2. **MVC模式**: MVC模式是软件工程中的一个设计模式,将业务逻辑(Model)、用户界面...

    行业资料-电子功用-全自动导电布成型转贴穿管设备及工艺的介绍分析.rar

    全自动导电布成型转贴穿管设备广泛应用于电子设备、通信设备、汽车电子、航空航天等领域的电磁屏蔽和防护,例如,用于手机、电脑、服务器的内部线路屏蔽,汽车电线的防电磁干扰,以及飞机内部电子系统的静电防护。...

    动网转贴.zip易语言项目例子源码下载

    《易语言项目实例——动网转贴》 易语言,作为一种中文编程语言,以其独特的语法和易用性,深受广大编程爱好者尤其是初学者的喜爱。...通过深入研究和实践,你将能够更好地理解和运用易语言,开启自己的编程之旅。

    易语言源码动网转贴.rar

    7. **数据库操作**:如果动网转贴还需要记录用户的转发历史,那么就会涉及到数据库操作,如MySQL、SQLite等,用于存储和查询用户转发的信息。 8. **安全防护**:防止恶意用户滥发帖子,可能需要设置转发频率限制,...

    动网转贴.e.rar

    动网论坛的用户可能经常进行帖子的分享和转贴,这些信息可能包括帖子的文本内容、图片、链接和其他附件。.rar文件格式是一种常见的压缩格式,用于将多个文件打包在一起,减少存储空间并方便传输。 【标签】"动网...

    易语言动网转贴.rar

    "动网转贴"可能是基于易语言编写的一个功能模块或者工具,用于在论坛或者网站之间转移帖子数据。由于压缩包文件名为“易语言动网转贴.rar”,我们可以推测这可能是一个软件开发资源,包含了一些源代码、教程或者是...

    BFC UBB转贴器

    由于现在流行的转贴工具都是基于浏览器的,转换速度比较慢,还得打开浏览器才能使用(同时受到浏览器版本限制)。 <br> 而这个小程序则完全不依赖于浏览器,以BFC采集器的UBB转换模块为基础,转换速度超快,...

Global site tag (gtag.js) - Google Analytics