欢迎光临本站!

搜索引擎查询系统-网页信息检索

来源:技术探讨    更新时间:2019-12-12 14:11:46    编辑:老王    浏览:342

  网页信息检索的数据源来自于网页索引库(在前一章中介绍了网页对象被索引入库的全过程)网页信息检索输出是一组文档编号,这些被编号的文档都是索引库中包含查询词的文档。

  早期的检索模型


  早期的检索模型是一种称为“布尔模型”( Boolean models)的检索模型。布尔模型也称为“集合模型”,是一种采用ANDOR及NOT等逻辑运算符将多个查询词连成一个逻辑表达式,继而通过布尔运算进行检索的简单匹配模型。例如查询词为“走进搜索引擎检索模型搜索”,将会被翻译成“走进搜索引擎AND检索模型NoT搜索”这样的逻辑语言。按照自然语言的翻译,这个逻辑语言表示包含“走进搜索引擎”且包含“检索模型却不包含"搜索”的文档集合。对于查询系统来说,这样的查询词表示用户请求检索包含“走进搜索引擎”且包含“检索模型”,却不包含“搜索”的文档集合。

  布尔模型的这种检索易于实现,检索速度快。但是由于没有考虑文档和查询词的相关性问题,没有区分查询词的权重问题。因此在“效率”和“效果”的两难选择上放弃了“效果”,而仅仅考虑了“效率"。

  此外,如果查询词中有一个关键词没有包含,则可能出现漏检。不妨通过一个例子来说明布尔模型的这些主要的缺点。

  假定有如下这样3篇待检索的文档。

  (1)在传统搜索引擎架构中,搜索引擎由4个系统构成分别是下载系统、分析系统、索引系统及查询系统。

  (2)机械行业内一般把小型挖掘机简称为“小挖”,小挖由5个系统构成,分别是……详细地理解这些名词可以使用 Google搜索引擎搜索一下。

  (3)搜索引擎有4个主要功能模块,分别是下载系统,分析系统,索引系统和查询系统。这4个系统是搜索引擎的核心,其中查询系统是搜索引擎惟一直接面对客户的系统。

  如果采用布尔检索模型,在査询“搜索引擎系统构成”这样的查询词时,文档1和文档2均会被检索到,因为文档1和文档2均包含了全部查询词。显而易见,在第1个文档中,“搜索引擎这个关键词出现了两次,"系统构成"出现了1次;在文档2中“搜索引擎”出现了1次,“系统构成”也出现了1次,直觉上看应该是文档1的相关性更好。在布尔模型中很难进行相关性强弱的度量,它只解决“有”还是“没有”的问题,不解决“好“还是“不好”的问题。

  最后,从用户查询意图上看,文档3比文档2更加符合用户的查询意图。文档3中出现了3次“搜索引擎”这个关键词,仅仅因为没有包含“系统构成”这个关键词,而没有被检索出,而文档2只是沾边提到了搜索引擎,却能够被检索出。

  布尔模型归纳起来存在如下两大优点。

  (1)表达简单且易于实现。在关键词检索的过程中,把检索计算转变为集合运算,特别是集合间的求交集运算和集合间的差运算。

  (2)检索速度快。布尔模型的计算主要是集合求交运算这将在下一节中介绍。

  正是由于布尔模型的两个优点造成了布尔模型的如下两大不足。

  (1)如果有一个查询词没有被包含,则检索失败。由于布尔模型表达简单,缺乏灵活性,造成上例文档3中没有包含“系统构成”这一关键词,因而无法被检索出来的情况。

  (2)检索出来的结果很难进行相关性排序。由于布尔模型计算简单,例如前面的例子中检索“搜索引擎系统构成”的过程中,文档1和文档2与查询词的相关性没有被计算,从而无法了解哪个文档更加符合用户的查询意图(通常认为符合用户查询意图的文档在搜索结果中应排名靠前)。

  布尔模型的不足主要由于没有考虑到关键词在查询中的权重问题,这一点不足在向量空间模型( Vector Space Models)中得到部分解决。虽然不够完美,但是已经足够解决上面例子中的检索问题。

  向量空间模型( Vector Space Models)


  和布尔模型不同,向量空间模型主要关心的是“效果”,而非效率”。向量空间模型提出了将查询词和文档按照关键词的维度分别向量化,然后通过计算这两个向量间夹角余弦的方法得到文档与査询词的相似度。从而优先检索那些和查询词相似度大的文档,并且能够对检索出的文档按照与查询词的相似度进行排序。向量空间检索模型的计算方法如图6-1所示。

搜索引擎查询系统-网页信息检索

  在向量空间检索模型中,通过下面3个步骤进行检索。

  (1)把原始查询和文档都看做是文本,使用同样的向量化过程分别得到查询向量和文档向量。

  (2)通过计算向量相似度的方法计算原始查询和文档的相似度。

  3)按照与查询词的相似度从大到小排序文档,返回给用户。

  向量( vector)是一个很抽象的概念,它又称为“矢量"。最初被应用于物理学,很多物理量,如力、速度、位移、电场强度,以及磁感应强度等都是向量。大约在公元前350年,古希腊著名学者亚里士多德就已提出力可以表示成向量,两个力的组合作用可用著名的平行四边形法则来得到。英国大科学家牛顿最先使用

  有向线段表示向量。

  事实上,向量包含了两层含义,即长度和方向。长度用向量的模表示,向量的模(长度)的计算公式为向量的每个分量的平方和开根号。由于向量具有方向,所以方向上的差异(角度)被用来量化向量的相似程度。

  将各种不同的关键词看做是不同的维度,那么每个文档按照关键词进行向量化,得到向量中每一个分量可以理解为向量在各个关键词维度上的投影。这一点不难理解,三维坐标上描述一个点采用的方式为(a,b,c)表示向量在x轴上的投影为a,在Y轴上的投影为b,在Z轴上的投影为c。在这里只是把代表三维空间中3个轴转换为n个关键词的n维空间,这样每一个查询句子和每一个文档都可以用这个n维空间来表示。

  通过下面的一个例子来理解向量化的过程。假定汉语的词汇表只有“走进”、“搜索引擎”和“学习”这3个词(实际上,常用的汉语词汇过万)那么这3个词组成的向量空间就是我们熟悉的三维空间,如图6-2所示。

搜索引擎查询系统-网页信息检索

  在图中,对于“走进搜索引擎,学习搜索引擎”这个句子通过计算每个词汇的出现的次数,得到这样的统计信息。即“搜索引擎”出现两次,“走进”出现1次,"学习”出现1次。将3个词的维度理解为三维空间的XYZ轴,这样“走进搜索引擎,学习搜索引擎”在词汇表构成的向量空间内表示为向量(2,1,1)这个向量的3个分量的意义可以理解为对3个轴的投影分别是2,1,1,物理含义为这些关键词在查询句子中分别出现的次数,同时注意这里向量的方向性用箭头表示。

  现在我们扩展到四维空间上理解假定词汇表中还包括了“检索模型”一词,这样对于“走进搜索引擎,学习搜索引擎”这个句子进行向量化的结果可能是(2,1,1,0),其中四维空间的第四维表示“检索模型”。由于这个句子中没有出现“检索模型”,因此它在这个关键词维度上的投影为0。

  据统计常用汉语词汇大约5000条,如果用这5000维的词向量空间表示这个句子,可能是这样的形式,即(0,0,…,0,2,0,…1,…1,…)其中标“0″的分量表示句子在这个词汇上的投影是0,或者说句子中没有出现这个关键词。由于句子中只出现3个词,因此在向量中只有3个分量为有效的非0值。可见在实际的计算中,向量通常都是十分稀疏的。

  向量化的过程就是对一个文档按照关键词的维度进行向量化,每个向量的分量可以理解为包含这个词的权重( weight)出现次数多的词权重就较大,对向量方向的影响力也较大。为了使不同文档和查询词的相关性具有比较性(相关性排序的需要)保证对大文档和小文档做到公平,还需要对关键词的出现次数做归化的工作,即转化为词频(词数/总词数)作为向量的分量。因此在上面例子中,“走进搜索引擎,学习搜索引擎”中的“走进的词频为1/4,“搜索引擎”的词频为2/4,“学习”的词频为1因此在如上图所示的关键词向量空间下,这个查询词被向量化为(214,14,1/4)。

  事实上,向量中的每个分量同除以相同的数不会改变向量的方向,但是会改变向量的距离。因此在只考虑向量方向,而不考虑向量长度的情况下,没有必要使用词频作为向量的分量,这样反而引入了浮点计算的麻烦。考虑到其他可能需要进行向量距离运算的场合,以及为下一小节中的TFDF的权重量化计算做准备,提前了解词频的有关概念,并使用关键词词频作为向量的分量表示。

  在向量化的工作完成后(下一节将提到实际上采用经典的TF/DF方法进行向量化的工作),就需要解决计算文档和查询词相似度的问题。向量空间模型中一般采用向量之间的夹角余弦值作为向量是否相似的度量依据。

  向量间的夹角余弦的计算公式

图片.png

  其中ab表示向量,·表示向量的点乘,|a|表示向量的模,或者说是向量的长度。

  通过一个具体的例子理解这个计算过程。

  假定在一个7个关键词的向量空间下,一个查询词向量化为a(0,0,2,0,1,0,1),一个文档向量化为b(0,1,3,5,2,4,0),夹角余弦计算方法如下:

图片.png

图片.png

  这样查询词a和文档b的相关性就转化为044这个具体的数值上,使得相似性成为可以量化的概念,因此相似性量化的结果称为“相似度”。

  在实际计算中,如果向量a表示查询向量,向量b表示文档向量,在计算查询向量和一组文档向量的相似度时,查询向量总是不变的,或者说对每个文档向量来说查询向量都是相同的。因此相似度计算中是否除以|a|,对将来进行的相似度排序没有影响,可以作为公共因子消去。计算相似度实际只需要计算|al×cosθ即可,方法如下:

图片.png

  其中每个文档向量的模可以预先计算并保存,而不需要每次查询都执行一次文档向量的模运算。这样,每次求相似度只需要次向量点乘和除法计算即可。

  对于两个高维稀疏向量(由于汉语词汇众多,实际向量化后的向量维数高,非0值少),向量的表示和向量点乘的计算也是需要一定技巧。可以采用哈希表的方法快速找到两个向量相同分量的非0值进行计算,这里不再详细展开。

  为了简化描述,在此前提到的关键词量化过程中采用词频作为向量化中每个向量的分量,而事实上却采用了经典的 TF/IDF方法为每个关键词进行更加合理的量化。下面我们将走进经典的TF/IDF方法,领略信息检索的精髓。

评论区

表情

共0条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~

相关内容

点击排行

随机新闻

评论排行榜