`
lzj0470
  • 浏览: 1276808 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

一个网页和某个查询的相关性

阅读更多


[我们已经谈过了如何自动下载网页如何建立索引如何衡量网页的质量(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),那么给定一个查询,有关网页综合排名大致由相关性和网页排名乘积决定。

分享到:
评论

相关推荐

    计算文档的主题相关性

    为了能够准确地评估文档的主题相关性,首先需要构建一个包含多个文档的集合,这些文档应与想要分析的主题紧密相关。具体操作包括选择与目标主题相关的初始URL,随后下载这些网页并提取文本内容。 **2. 分词计算频率...

    网络游戏-用社交网络特征提高姓名和其它搜索查询的搜索引擎结果页面的相关性.zip

    2. **用户行为分析**:社交网络上的用户互动,如点赞、分享、评论等,可以反映一个话题的热度和用户对特定内容的兴趣。这些数据可以作为搜索引擎评估搜索结果相关性的依据。 3. **社交网络中的关系网络**:在社交...

    搜索引擎中相关性策略之间耦合度的分析方法及装置.docx

    - 对于每一个相关性策略,需要确定其在搜索引擎处理流程中的具体生效位置。这些位置通常是算法执行的关键节点,比如查询解析、文档筛选、排序等环节。 3. **探针函数与策略标识的插入**: - 在每个相关性策略的...

    Python+PHP实现基于机器学习的搜索引擎系统.zip

    资源包含文件:课程论文报告word+源码及数据库文件 完备的索引、对网页质量的度量、用户偏好、确定一个网页和某个查询的相关性的方法。详细介绍参考:https://blog.csdn.net/newlw/article/details/126942989

    HITS算法.docx

    HITS算法 HITS算法(Hypertext Induced Topic Selection)是一种链接分析算法,旨在...HITS算法是一种effective的链接分析算法,能够帮助搜索引擎找到与用户查询主题相关的高质量网页,提高搜索结果的相关性和准确性。

    新力文章关键词密度查询工具

    搜索引擎,如百度、谷歌等,会根据网页的关键词密度来判断其主题相关性,如果一个关键词在文章中出现过于频繁,可能会被视为关键词堆砌,导致搜索引擎惩罚;而关键词密度过低,则可能使网页无法获得理想的搜索排名。...

    文档和代码-搜索引擎

    相关性评分可能涉及到多种算法,如TF-IDF和PageRank等,这些算法的作用是衡量一个网页与用户查询的相关程度。这些信息在项目文档中可能会有详细描述,包括查询优化技巧和用户查询行为分析等。 最后,搜索引擎的用户...

    分页模糊查询商品

    在IT行业中,分页模糊查询商品是一个常见的需求,特别是在电商网站、搜索引擎等应用中,用户通常需要通过输入关键词进行商品的快速查找,并且为了优化用户体验,通常会采用分页的方式来展示大量的搜索结果。...

    基于分布式学习自动机和用户反馈的网页排序算法研究.pdf

    PageRank是Google创始人拉里·佩奇和谢尔盖·布林开发的一种网页排名算法,其核心思想是通过对网页之间的超链接结构进行分析,从而计算出每个网页的重要性或权威性。这一算法模仿了学术领域中引用次数对论文重要性的...

    Google网页质量评估大解密

    EWOQ是Google内部用于网页质量评估的一个平台。它提供了从登录、查看任务到提交评估结果等一系列功能。通过EWOQ,评估员可以更高效地完成评估工作。 - **登录与界面**:评估员需要通过特定的登录凭证进入EWOQ系统。...

    查询检索

    在实现这些功能时,Web开发者需要考虑查询性能、用户体验和查询结果的准确性。优化查询策略(如使用缓存、分页、延迟加载)可以提高系统的响应速度,而提供智能提示和自动完成功能可以改善用户体验。此外,利用机器...

    Baidu地图自定义模糊查询

    2. **范围搜索**:限制搜索范围,例如只在某个城市或特定区域内进行查询,以提高查询效率和结果的相关性。 3. **分类搜索**:针对不同类型的地点(如餐馆、酒店、公园等)进行定制化搜索,便于用户按需筛选。 4. *...

    八桂大地便民查询工具 v1.0.rar

    在揉合了诸如Title标识和Keywords标识等所有其它因素之后,Google通过PageRank来调整结果,使那些更具“等级/重要性”的网页在搜索结果中令网站排名获得提升,从而提高搜索结果的相关性和质量。) 21、关键词排名...

    《Introduction to Information Retrieval》 链接分析技术课件

    链接分析是搜索引擎优化(SEO)和网页排名中的一个重要概念,它利用网页间的超链接来评估网页的相关性和重要性。 在链接分析中,有两个关键假设。首先,一个网页之间的超链接表明了作者对目标页面的感知相关性,即...

    主题PageRank

    主题敏感PageRank是一种改进的网页排名算法,它将传统PageRank算法中网页的重要性排名细化到特定主题的维度上,从而能够根据用户查询的主题兴趣,提供更加精准和个性化的搜索结果。主题敏感PageRank的计算主要分为两...

    点百度名商格子网.rar

    在SEO中,链接分析是评估网页重要性和相关性的一个关键因素,因为搜索引擎通常会考虑一个网页被其他网页链接的次数和质量。因此,该源码可能包含了复杂的算法来计算链接权重,并为用户提供相关的搜索结果。 至于...

    遗传算法网页搜索大全qs.rar

    本资料“遗传算法网页搜索大全qs.rar”显然是一个包含有关遗传算法网页资源的集合,由作者搜集并整理而成,旨在提供一个全面的学习和参考平台。 遗传算法的核心概念源自生物的自然选择、遗传和突变过程。在优化问题...

    网页设计与制作_在线作业_F.rar

    网页设计与制作是一个涵盖多个领域的综合学科,包括前端开发、用户体验设计、图形设计以及交互设计等。这份"网页设计与制作_在线作业_F.rar"压缩包文件,显然与教育相关,可能包含了某个课程或训练项目的作业内容,...

Global site tag (gtag.js) - Google Analytics