精华内容
下载资源
问答
  • 信息检索导论

    2021-01-07 11:09:40
    信息检索导论 第一讲 概论 数据、信息、知识、智慧 信息检索系统 信息资源库、 第二讲 自然语言处理基础 文档的基本概念 从内部看,文档具有两部分:数据(提取词项),结构(语法) 从外部看:表现形式 元数据 自然...
  • 信息检索导论答案

    2019-04-17 17:37:43
    信息检索导论原作者提供答案
  • 目录信息检索导论-读书笔记(1)-信息检索导论基础知识0. 本文概述1. 倒排索引和布尔检索1.1 倒排索引的构建1.2. 布尔查询的处理1.3 基本布尔操作的扩展以及有序检索2 词项词典及倒排记录表2.1 词项集合的确定2.2 基于...

    信息检索导论-读书笔记(1)-信息检索导论基础知识

    本文是对国科大2018-2019年春季教授的信息检索课程的复习总结,主要参考《信息检索导论》一书以及老师上课所用课件。根据书中章节的划分,本系列文章为五个部分,本文是第一部分:信息检索的基础知识,其余部分如下:

    0. 本文概述

    本文主要介绍信息检索的基础知识,也是搜索引擎的核心理论。首先介绍倒排索引,包括其构建之前的预处理构建的过程、以及用于布尔查询时如何使用,然后基于上面的过程,针对具体的场景,提出了具体的改进方法:

    1. 如何处理短语查询?
    2. 进行布尔查询时存在查询拼写错误或者不能精确匹配的情况时如何处理?
    3. 如何为大规模文档集构建索引?
    4. 如何对词典和倒排记录表进行压缩以节省空间?

    在对布尔查询及其扩展有了基本的了解之后,我们知道了如何从文档集中检索出匹配的文档,但是并不知道每一篇文档匹配的程度,因此剩下的内容将会介绍如何对文档和查询的匹配程度进行度量,主要包括词项权重的计算以及评分算法。

    有了上面的内容,我们已经对一个简单的搜索引擎的基础组成部分有了大致的了解,最后,将会介绍如何对一个检索系统进行评价。

    1. 倒排索引和布尔检索

    布尔检索也称为布尔逻辑检索,是指利用布尔逻辑运算连接各个检索式,然后由检索系统执行相应逻辑计算,以找出所需信息的犯法。在该模型下,每篇文档只被看成是一些列词的集合。

    为了执行布尔检索式,我们需要提前对文档集建立索引,即词项-文档关联矩阵,词项是索引的单位,我们会在下面的预处理中再次提到它,关联矩阵就是为了记录某一篇文档是否包含词表中的每个词,这里的词表指的是文档集包含的所有词项的集合,所以关联矩阵的大小是mnm*nmm是文档集中的文档数量,nn是文档集包含的所有词项的总数,矩阵中每一个值的取值范围是0或1,分别表示不包含该词项和包含该词项。

    有了词项关联矩阵我们就可以对布尔检索式进行逻辑运算了,比如我们希望查找(AAndB)(A And B)即同时包含A和B的文档,可以取出关联矩阵中词项A的那一列和词项B的那一列,然后统计两列数据中同时取1的那些行,即是我们想要的结果。

    但是词项文档矩阵有一个很严重的问题就是当文档集比较大的时候,实际上不需要很大的时候,矩阵占用的内存会急剧增长,因为这个矩阵是及其稀疏的,所以我们有了信息检索中的第一个核心概念——倒排索引

    倒排索引由词典和倒排记录表组成,词典即上面提到的词项集合,每一个词项对应一个倒排记录表,该表中的每个元素记录的是该词项在某文档中出现的一次信息,如下图:

    1.1 倒排索引的构建

    倒排索引的构建过程如下所示:

    1. 收集需要建立索引的文档;
    2. 将每篇文档转化成一个个词条(token)的列表,这个过程称为词条化(tokenization);
    3. 进行语言学处理,产生归一化的词条来作为词项;
    4. 对所有文档按照其中出现的词项来建立倒排索引。

    产生归一化词项的过程我们可以看做是对建立倒排索引的预处理过程,会在下面进行介绍,这里主要讲第四步,在上面的前3步处理结束后,对每篇文档建立索引时的输入就是一个归一化的词条表,也可以看成二元组(term,documentID)(term, documentID)的一个列表,建立索引的核心步骤就是将这个由所有文档的词条表组成的列表按照词项的字母顺序进行排序,同一词项在同一文档中的多次出现会合并在一起,最后整个结果分成词典和倒排记录表两部分,如下图所示:

    在最终得到的倒排记录表中,往往会将词典放在内存中,而倒排记录表放在磁盘上。

    1.2. 布尔查询的处理

    布尔查询包括两种操作AND 和 OR,基于倒排索引的布尔查询就是取出词项对应的倒排记录表进行合并或者交集操作,这里不做赘述。

    查询优化指的是如何通过组织查询的处理过程来使处理工作量最小,对布尔查询进行优化要考虑的一个主要因素是倒排记录表的访问顺序,一个启发式的想法是按照词项的文档频率(也就是倒排记录表的长度)从小到大依次处理,如果是复合的布尔检索式,我们可以保守的估计出每一个子检索式的结果大小然后按照从小到大的顺序依次处理。

    1.3 基本布尔操作的扩展以及有序检索

    与布尔检索模型相对的是有序检索模型或者叫排序检索模型,后者不是通过具有精确语义的逻辑表达式来构建查询,而是采用一个或者多个词来构成自由文本查询,需要确定哪些文档最能满足用户的需求。

    实际上,严格的布尔检索模型并不能满足用户的要求,实际应用中往往会在系统中加入更多的操作,比如词项近邻等。

    2 词项词典及倒排记录表

    上面我们讲了如何构建倒排记录表,以及在布尔查询中基础使用,接下来讲一下倒排记录表的具体实现问题,包括如何得到词项词典,以及一些扩展的索引结构。

    2.1 词项集合的确定

    词项集合的确定包括词条化去除停用词词项归一化词干还原和词性归并。词条化是将给定的字符序列拆分成一系列子序列的过程,其中每一个子序列称为一个词条;去除停用词的目的是为了去除那些语义内容1余文档主题关系不大的高频词,同时节省存储空间;词项归一化是将看起来不完全一直的词条归纳成一个等价类,以便在他们之间进行匹配;词干还原和词性归并的目的是为了减少词的曲折变化形式,并且有时候会将派生词转化为基本形式。

    2.2 基于跳表的倒排记录表快速合并算法

    考虑两个大小分别为m和n的倒排记录表的合并问题,其时间复杂度是O(m+n)O(m+n),为了优化类似查询,一种方法是采用跳表,用少量的空间去换取时间上的优化。

    跳表是在构建索引的同时在倒排记录表上建立跳表,跳表指针能够提供捷径来跳过那些不可能出现在检索结果中的记录项,如下图所示:

    跳表的使用方式很直观,不再赘述。现在要考虑的问题是如何选择跳跃步长,一个简单的启发式策略是在每个p\sqrt{p}处放置跳表指针。

    2.3 含位置信息的倒排记录表和短语查询

    有时候我们需要对一个完整的短语进行检索,不希望我们的检索系统将其拆分成多个词项,这种情况下,原来的倒排索引就不能满足要求了,这里讨论两种解决该问题的方法。

    二元词索引,为了处理长度为2的短语查询,我们可以扩展我们的索引结构,将文档中每两个连续词都看成一个短语词项,并为其建立倒排记录表,这样我们就有了词典为二元词项的倒排索引。

    如果短语中的词项个数超过两个,可以简单的将其拆分成由AND连接的多个二元查询,比如(A B C)(A\ B\ C)可以拆分成(A B AND B C)(A\ B\ AND\ B\ C),但是这种方法存在的一个问题就是可能会有错误的返回结果。

    二元词索引可以扩展到个更长的词序列,随之而来的问题就是我们的倒排词典可能会变得非常大,实际上当长度为2的时候词典的规模已经比原来大了很多。

    很显然,二元词索引并不能真正解决短语查的问题,实际中更常用的是位置信息索引,顾名思义,就是将此项出现的位置信息存储在此项的倒排记录表中,形式为:文档ID:(位置1,位置2)。为了方便计算此项权重,我们往往也会将此项的频率写进倒排记录表。如下图所示:

    为了处理短语查询,在前面提到的倒排记录表合并算法的基础上,我们不仅仅要考虑词项是否出现,还要考虑其出现的位置。

    采用位置索引会大大增加倒排记录表的存储空间,也会提高倒排记录表合并的复杂度。

    一个混合策略是:对某些查询使用短语索引或者只使用二元词索引,而对其短语查询使用位置索引。短语索引所收录的那些较好的查询可以通过分析日志得到,往往是那些高频常见的查询,或者是处理开销比较大的查询,比如这样一些短语,它们中的每一个词都很常见,但是组合起来却很少见。

    3. 词典及容错式检索

    在介绍正式内容之前,我们先了解一下词汇表的两种存储结构:哈希表和搜索树。哈希表将每一个词项映射成一个整数,为了减少碰撞,需要足够大的目标空间,查询词项稍有变化都会导致哈希结果完全不同,因此哈希表的存储方式不能处理前缀查询。搜索树能够解决上面的大部分问题,它支持前缀搜索,最为出名的就是二叉树,每个内部节点都代表一个二值测试,测试结果用于确定下一步应该搜索的子树,二叉树高效搜索的关键是树的高度,即树的平衡性,因此在对二叉树进行增删的同时要进行平衡化处理。

    在上面的介绍中,我们已经可以处理一般的布尔查询和邻近查询(即短语查询),有的时候我们对需要查询的词项的拼写形式没有绝对的把握,这个时候就需要通配符查询,类似于(ab)(a*b),查询以a开头以b结尾的词项相关的信息。

    除此之外,有的时候我们的查询可能出现拼写错误,导致精确查询没有返回结果,我们的检索系统应该能够对这类错误有一定的鲁棒性。

    最后,我们会在普通的倒排索引的基础上介绍一些扩展之后的倒排索引。

    3.1 通配符查询

    我们首先看一种比较简单的形式,(a)(a*),即通配符出现在尾部,这种查询称为前缀式查询,基于搜索树的词典结构对于处理这种查询来说非常方便。同样的,如果通配符出现在首部,即后缀式查询,我们可以使用反向搜索树来存储词典结构,两者结合起来的话我们就可以对更一般的通配符出现在中间的查询进行处理了,即分别使用正向搜索树和反向搜索树搜索通配符两边的子串,将得到得结果进行取交集。这样我们就可以处理只包含单个*的查询。

    对于更一般的通配符查询,主要思想是将给定的通配符查询qwq_w表示成布尔查询QQ,然后在给定的倒排索引上进行处理。

    轮排索引,轮排索引是倒排索引的一种特殊形式,如下图所示:

    首先在词项的末尾加入一个结束标识符,然后对词项的每一个旋转结果都构造一个指针来指向原始词项,我们称这些旋转之后得到的词项为轮排词汇表,我们可以使用搜索树来存储轮排词汇表。

    有了轮排索引之后,下一步就是讲查询词项转化成以*结尾,然后我们就可以在轮排词汇表中搜索符合相应前缀的词项,然后通过指针在普通倒排索引中查找这些词项,从而检索出需要的文档。这样我们就可以处理单个*的查询了。对于多个*的查询,可以先忽略之间的通配符,只考虑前缀和后缀,然后进行后过滤。

    k-gram索引,轮排索引最大的问题就是导致索引表的存储空间急剧增长,在k-gram索引中,其词典由词汇表中所有词项的所有k-gram形式构成,而每个倒排记录表则由包含该k-gram的词项组成,如下图:

    其实k-gram索引是对轮排索引的一种优化,轮排索引汇中要考虑词项的所有旋转形式,而k-gram索引中只需要考虑词项中任意连续的k个字符组成的k-gram词项,大大节省了存储空间。k-gram所以结构其实也是一种倒排索引结构,我们首先对查询进行解析,构造新的布尔查询,然后在k-gram索引中搜索得到词项,然后在普通倒排索引中利用这些词项去搜索需要的文档。

    3.2 拼写校正

    这里主要介绍拼写校正常用的三种方法:基于编辑距离的拼写校正、基于k-gram重合度的拼写校正、基于上下文敏感的拼写校正。

    基于编辑距离的拼写校正,首先,编辑距离定义为一个字符串转换成另一个字符串的最小编辑操作数。这些操作包括:增加一个字符,删除一个字符,替换一个字符,编辑距离的概念可以进一步推广,比如给每一种操作赋予不同的权重。编辑距离的计算采用动态规划的方法,其时间复杂度是O(s1s2)O(s_1*s_2)

    有了编辑距离,一种简单的做法是通过计算输入词项和词典中所有词项的编辑距离来进行拼写校正,但是这种穷举的做法明显是不可取的。一种启发式的方式是将搜索限制在与查询词具有相同首字母的字符串上,进一步的,我们可以使用轮排索引的思想,考虑查询字符串的每一种旋转形式,通过遍历B树来访问轮排索引,返回以r(查询字符串的一种旋转形式)开头的词项,其实这种方法仅仅考虑了编辑操作中的增删操作,没有考虑替换操作带来的影响,为了解决这个问题,可以对旋转形式做一定的修改,比如忽略其一定长度的后缀,然后再对其进行轮排索引搜索。

    基于k-gram重合度的拼写校正,为了进一步较少计算编辑距离后得到的词汇表大小,我们希望能够预先筛选出一下和查询字符串比较相近的词项,然后对这些词项进行编辑距离计算。我们利用k-gram索引来查找与查询具有很多公共k-gram的词项,在这里我们需要清楚k-gram索引其实也是倒排索引,只不过不是对文档按照词项进行索引建立,而是对所有的词项按照k元字符串进行索引建立,比如使用2-gram索引搜索bord,首先将bord拆分成三个二元字符串:bo、or、rd,然后在2-gram索引中进行检索,但是这里我们并不需要要求结果一定包含所有的二元字符串,我们可以对包含的程度进行一个度量,比如Jaccard系数。所以在检索的过程中,我们对每一个二元字符串对应的词汇表进行扫描,计算词汇t和查询q的Jaccard系数,如果超过预定的阈值,就输出。

    所以现在的拼写校正方法是,首先使用k-gram索引返回可能是查询qwq_w的潜在正确拼写形式的词项集合,然后计算该集合中的每个元素和qwq_w之间的编辑距离并选择具有较小编辑距离的那些词项。

    上下文敏感的拼写校正,我们在进行查询的时候,有的时候每一个词项都没有错误,但是组合在一起却不合理,导致搜索引擎返回的结果很少,面对这类错误,我们仍要对每个单词找到可能正确的拼写,即使它们本身就是正确的,然后尝试对查询中的每个词进行替换。但是上述的穷举过程可能开销非常大,一种启发式的方法是分析日志,找出高频组合词来获得可能正确的拼写组合。

    4. 索引构建

    本节主要介绍索引的构建方法,包括四种:基于块的排序索引构建算法、内存式单遍索引构建算法、分布式索引构建、动态索引构建。

    4.1 基于块的排序索引构建算法(BSBI)

    我们在一开始就介绍了如何构建不包含位置信息的倒排索引,但是其整个过程都是在内存中完成的,对大规模文档集进行索引建立的时候需要引进二级存储介质,这时候我们需要一个更具有扩展性的索引构建算法。

    为使索引构建过程效率更高,我们将此项用其ID来表示,而不是在前面提到的字符串形式,每个此项ID是其唯一标识,我们可以在处理文档之余将词项映射成其ID。因此我们有一个额外的存储结构是词项-词项ID映射。

    基于块的排序索引构建算法的步骤如下:

    1. 将文档集分割成几个大小相等的部分;
    2. 将每个部分的词项ID-文档ID对排序;
    3. 将中间产生的临时排序结果转化成倒排索引格式后存放到磁盘;
    4. 将所有的中间文件合并成最终的索引。

    实际上,上述步骤只是基础倒排索引构建的一个简单扩展,2-3步其实就是普通倒排索引的构建,我们只是将大的文档集进行分而治之。

    4.2. 内存式单遍索引构建算法(SPIMI)

    由于BSBI算法需要将词项映射成其ID,会占用大量存储空间,在SPIMI算法中,我们不在使用词项ID,而是直接使用词项,这样带来的一个直接问题是我们无法知道所有词项的信息,因此这里采用动态添加词典的方法构建倒排记录表,算法步骤如下:

    返回调用上面的算法就可以处理完所有的文档。SPIMI的最后一步和BSBI一样,也是合并多个块,得到最终的倒排索引。

    4.3 分布式索引构建方法

    web搜索引擎通常使用分布式的方法来构建索引,这里介绍基于词项分割的分布式索引构建方法,实际上实际中更常用的是基于文档分割的索引。基于词项分割的索引构建方法实际上是MapReduce的一个应用,其流程如下:

    首先,输入数据被分割成n个数据片,然后每一个数据片会分派给一个分析器执行map阶段,也就SPIMI和BSBI中的分析任务,每个分析器的输出就是排序后的词项ID-文档ID对,分析器会将输出结果存在本地的中间文件,然后在Reduce阶段,每一个倒排器会负责处理所有分区文件中固定范围的键,比如a-f,最后得到最终的倒排记录表。

    实际上分布式索引构建方法的过程是SPIMI、BSBI的结合,首先将文档集分块,并行处理得到排好序的词项ID-文档ID对,然后由倒排器进行分布式的倒排索引构建,不同的是,在SPIMI和BSBI中是串行的对所有分区文件进行合并,这里是并行的同时对所有分区文件的不同部分处理。

    4.4 动态索引构建方法

    当文档集随着文档的增加和删除而变化时,我们需要对倒排索引进行更新,最简单的方法是定时的从头到尾更新索引,但是这样会导致新文档的检索有一定延迟,一个比较好的办法是,同时维护两个索引,一个是主索引,一个是辅助索引,辅助索引负责管理最近的文档增删记录,并且定时的将辅助索引合并到主索引中。

    5. 索引压缩

    当需要建立的文档集规模较大时,其索引也会占用很大的空间,本节讨论如何对索引进行压缩,压缩索引有两个隐含的好处:

    1. 能增加高速缓存技术的利用率,使得告诉缓存中能够存储更多的倒排记录表信息,而不用每次都去内存中加载;
    2. 能够加快数据从磁盘到内存的传输速度,压缩后的数据从硬盘传输到内存然后再解压的时间往往会比未压缩的数据直接从硬盘传输到内存少很多

    本节首先介绍将字典视为长串以及按块存储的词典压缩技术,然后介绍两种倒排记录表的压缩方法:变长字节码和γ\gamma编码。

    5.1 词典压缩

    最简单的存储词典的数据结构是,整个词典采用定长数组来存储并且所有词项按照词典序排列,但是很明显所有词项的长度是不同的,这就导致了大量的空间浪费,一种解决这个缺陷的方法是,将所有的词项看成一个长字符串,并给每个词项添加一个定位指针,可以标识当前词项的开始和上一词项的结束,词项的查找定位可以使用二分法。这种机制可以节省大约60%的存储空间。如下图所示:

    上面的方法给每一个词项都增加了一个4B的定位指针,我们可以通过其他的定位方式来节省这部分空间。首先将长字符串中的词项进行分组变成大小为k的块,k是每一块中词项的数目,然后对每一个块只保留第一个词项的指针,每一个词项用一个额外的字节将其长度存储在每个词项的首部,如下图所示:

    显然的,k越大压缩效率越高,但是同时词项的定位效率也就越低,因此在压缩和词项查找效率之间必须要保持某种平衡。

    至此,我们还没有利用词项之间的冗余信息,实际上,按照词典顺序排序的连续词项之间往往具有公共前缀,因此,我们可以利用它们的公共前缀压缩编码。当我们识别到一个公共前缀之后,后续的词项便可以使用一种特殊字符来表示这段前缀,这种方法称为前端编码。

    5.2 倒排记录表的压缩

    考虑到高频词出现的文档ID序列值相差不大,我们可以考虑用间距间接的表示文档ID,而不是文档ID本身,如下图所示:

    为了对小数字采用比大数字更短的编码方式,这里主要考虑两种方法,按字节压缩和按位压缩。

    可变字节码利用整数个字节来对间距编码,字节的后7为是间距的有效编码区,第1位是延续位,如果该为1,表示本字节是某个间距编码的最后一个字节。下图是一个例子:

    可变字节编码可以将倒排索引压缩50%。

    γ\gamma编码是由一元编码发展而来,由两部分组成,第一部分表示偏移部分的长度,以0为结束标识,第二部分是偏移,因此在解码的时候,先读入第一部分,遇到0结束,然后就知道后面的偏移的长度,读入偏移,然后补上原来去掉的前端1,就得到原来的值。如下图所示:

    6. 文档评分、词项权重计算及向量空间模型

    上面我们介绍了支持布尔查询的索引处理方法,给定一个布尔查询,一个文档要么满足要求,要么不满足,在文档集规模很大的时候,满足布尔查询要求的文档往往会非常多,这时候对满足要求的文档进行排序就显得很重要了。本节首先介绍了参数化索引和域索引的概念,可以使用文档的元数据进行索引,同时还能够对文档进行简单的评分;然后引入了文档中词项权重的概念,介绍了几种计算权重的方法,最后介绍了向量空间模型。

    6.1 参数化索引和域索引

    实际上大多数文档都具有额外的结构信息,上文中我们只是简单的把文档看成一系列词项的序列,我们可以在检索的时候用用上文档的元数据,比如作者、时间、标题等等,可以称之为字段,每个字段都存在一个与之对应的参数化索引,我们将查询解析成分别对每个字段的索引,然后执行参数化索引上的合并操作。

    域索引相当于是对参数化索引的一个细化,我们一般讲取值相对比较固定的元数据称为字段,比如发布时间,而将那些更加自由的任意文本称为域,比如文档的标题和摘要,我们可以对文档的不同域构建独立的倒排索引,下面是一个例子:

    由于需要分别对每个域建立索引,可能需要大量的空间,因此我们可以考虑对域进行编码来减小词典的规模,比如下图:

    将词项在不同域中的出现情况统一编码,同时还支持域加权评分。

    所谓的域加权评分就是给每个域一个权重,所有域的权重之和为1,每个文档的评分计算如下:

    i=1lgisi\sum_{i=1}^lg_is_i

    权重的设置可以有领域专家来设定也可以由用户来指定,但是更好的办法是从人工标注好的数据中学习得到,就是一个权重学习过程,其目标函数就是相关样本的评分尽量高,不相关样本的评分尽量低。

    6.2 词项频率和权重计算

    首先介绍一下词袋模型,即忽略词项的出现顺序,只考虑词项的出现次数。给定一个查询,我们可以简单的将其看成多个词项组成的集合,为了对匹配文档进行评分,一个简单的想法是先基于每个查询词项与文档的匹配情况对文档进行打分,然后对所有查询词项上的得分求和。首先,我们需要对文档中的每一个词项赋予一个权重,最简单的方式是将权重设置为词项在文档中的出现次数,这种权重计算方式成为词项频率,简称tf。位于文档d,使用上述权重计算方法,可以得到一个权重集合,这和布尔检索形成了强烈的对比,布尔检索不考虑词项的出现次数,只考虑是否出现。

    原始的词项频率面临这样一个问题,在进行查询相关度计算时,认为所有词项的重要性是一样的,实际上,很多词在所有文档中的词项频率可能都很高,但是很少有区分能力,因此这种词的重要性应该降低,我们提出了文档频率,简称df,表示出现词项的文档的数量,由于该值可能比较大,一般会取其log值,词项的逆文档频率(idf)定义如下:
    idft=logNdfti d f_{t}=\log \frac{N}{d f_{t}}

    综合tf、idf我们就有了最常用的tf-idf权重计算方式:

    tfidft,d=tft,d×idft\mathrm{tf}-\mathrm{idf}_{t, d}=\mathrm{tf}_{t, d} \times \mathrm{idf}_{t}

    这样就可以把文档看成是一个向量,其中的每个分量都对应词典中的一个词项,因此我们可以引出重合度评分指标
    (q,d)=tqtfidft,d (q, d)=\sum_{t \in q} \mathrm{tf}-\mathrm{i} \mathrm{d} \mathrm{f}_{t, d}

    6.3 向量空间模型

    上一节引出了向量空间模型的概念,但是只是将文档表示成向量,然后基于词项的权重得到基于重合度的评分指标,实际上我们可以把查询也表示成向量,然后通过计算查询向量和文档向量的内积来得到评分。同时,为了对结果进行归一化,我们采用余弦值作为相似度计算的公式,两个文档之间的相似度计算如下:
    sim(d1,d2)=V(d1)V(d2)V(d1)V(d2) si m\left(d_{1}, d_{2}\right)=\frac{\vec{V}\left(d_{1}\right) \cdot \vec{V}\left(d_{2}\right)}{\left|\vec{V}\left(d_{1}\right) \| \vec{V}\left(d_{2}\right)\right|}
    同样的,查询向量和文档向量的相似度计算也可以表示成:
    score(q,d)=V(q)V(d)V(q)V(d) \operatorname{score}(q, d)=\frac{\vec{V}(q) \cdot \vec{V}(d)}{|\vec{V}(q) \| \vec{V}(d)|}

    6.4 其他tf-idf权重计算方法

    除了最原始的tf-idf计算方法之外,还有很多针对具体情况的改进计算方法,针对不同的tf、idf计算方法以及他们之间的组合如下:

    6.5 文档长度的回转归一化

    //TODO

    7. 一个完整搜索系统中的评分计算

    上一节我们介绍了词项权重的计算和向量空间模型,本节将会介绍一些启发式策略,这些策略能够加快评分算法的速度,当然其中的不少策略可能不能精确返回与查询相匹配的前K篇文档。

    7.1 快速评分及计算

    为了精确返回与查询匹配的前K篇文档,我们需要计算查询与文档集中所有文档的相似度然后排序,这是极其耗时的,我们希望能够减少参与计算的文档数目。即找到一个文档集合A,其数目远远小于文档集大小N,同时大于我们要求的K,然后对A中的所有文档进行相似度计算,返回前K篇文档。

    对于一个包含对个查询词项的查询来说,我们可以通过一些启发式的方法来减少需要计算相似度的文档的数量:

    1. 只考虑那些IDF值超过一定阈值的词项,因此IDF越低说明其文档区分性越低,我们希望更多的使用那些文档区分性高的词项来计算文档和查询的相似度,这个过程可以在进行倒排索引遍历的时候实现;
    2. 只考虑包含多个词项的文档,我们对匹配文档做一个最低阈值的限制,比如至少包含两个查询词项,这样可以大大减少最后需要计算得文档数量,这个过程可以在合并倒排记录表的时候实现;
    3. 引入胜者表,对于词典中的每一个词项,计算其倒排记录表中tf-idf值最高的r个文档,r需要实现给定,给定查询q,对查询q中所有词项的胜者表求并集,组成集合A;
    4. 我们可以对胜者表进一步扩展,引入静态得分,实际上文档集中的每一篇文档本身都有一个与查询无关的静态得分g(d)g(d),比如新闻网页的可信度、评论数目等等,这样一篇文档的最终得分就可以由两部分组成,一部分是文档本身的静态得分,一部分是与查询计算得到的相似度得分。然后我们对胜者表进行扩展,同样给定一个r值,每个词项的胜者表中包含g(d)+tfidft,dg(d)+tf-idf_{t,d}最高的r篇文档,其余和上面类似;
    5. 我们可以从另外一个角度考虑上面那种方法,将每个词项的倒排记录表分成两部分,都按照文档ID或者静态得分进行排序,一部分称为高端表,一部分称为低端表,高端表就是g(d)+tfidft,dg(d)+tf-idf_{t,d}最高的r篇文档,低端表就是剩下的所有文档,同样的处理顺序,对查询q中所有词项的胜者表求并集,组成集合A,计算相似度,如果该过程能够得到得分最高的前K篇文档,则结束,如果不能,继续对低端表进行扫描处理;
    6. 簇剪枝方法,我们可以先对文档向量进行聚类来进行预处理操作,然后在查询处理时,我们只考虑利用少数几个簇中的文档进行余弦相似度计算。

    7.2 信息检索的组成

    层次型索引,这个概念我们在前面已经涉及到过,就是在普通倒排索引的基础上再加一层索引,比如在优胜表中,我们可以认为高端表的处理就是第一层索引,而低端表的处理时第二层索引,在第一层索引的结果不能满足要求时我们才启动第二层索引。

    查询分析,一般的搜索界面通常情况下会对用户屏蔽查询操作符,使用查询解析器对用户输入的自由文本进行解析,一般会产生如下的一系列查询:

    • 将用户输入的查询字符串看成一个短语查询;
    • 如果短语查询返回的结果较少,则对短语进行解析,得到对个短语,分别进行查询;
    • 如果上一步返回的结果仍然不够,则将查询解析为多个词项,分别进行查询。

    一个完整的搜索系统的组成如下图所示:

    8. 信息检索的评价

    //TODO

    展开全文
  • 信息检索导论配书论文集
  • 信息检索导论 中科院王斌老师ppt 可结合相关书籍进行学习
  • 现代信息检索导论复习要点
  • Introduction to Information__ Retrieval信息检索导论_引擎学习-课件信息检索 8.1 信息检索系统的评价 .8.2 标准测试集 .8.3 无序检索结果集合的评价 .8.4 有序检索结果的评价方法 .8.5 相关性判断 .8.6 系统质量及...
  • 2017年最新信息检索导论答案完整版,内容清晰,考试复习必备
  • 信息检索导论 干货速览

    检索问题可以分为两类:

    • ad hoc:数据库基本不变,query会发生变化
    • routing:query不怎么变化,数据库和热点在实时更新

    搜索方式的进化:线性扫描(太慢)->词项-文档关联矩阵(太大)->倒排索引

    建立倒排索引的过程:收集文档->确定文档的格式、编码方式、语种进行识别、确立文档单位->tokenization(英语:词干还原(单复数)、词形归并(时态)、大小写转换等/汉语:分词,去掉停止词)->normalization(同义词)->建立倒排表和词典(词典有哈希表方式(小一点的词典)和搜索树方式两种实现方式,为了可以进行通配符查询,需要建立k-gram 索引、轮排索引)

    Query的处理过程:输入的原始query->纠错->tokenization(英语:词干还原(单复数)、词形归并(时态)、大小写转换等/汉语:分词,去掉停止词)->normalization(同义词,拼写校正(基于发音的和书写的),query改写)->查询(由词典找到相应的倒排表,根据逻辑合并倒排表,优化方法是从短的往长的合并,建立跳跃表、n-gram表、短语表)

    文档的摘要:静态摘要,动态摘要(为基于关键词上下文(keyword-in-context,简称 KWIC)的结果片段)

    进行排序的特征:

    • 参数化索引:文档的作者、标题以及出版日期等等
    • tf-idf权重计算:tf*idf(亚线性尺度变换、基于最大值的 tf 归一化、回转归一化)
    • 余弦相似度
    • BM25

    快速评分及排序

    • 索引去除技术(只考虑那些词项的 idf 值超过一定阈值的文档;只考虑包含多个查询词项(一个特例是包含全部查询词项)的文档)【减少要查询的索引数量】
    • 胜者表(对于词典中的每个词项 t,预先计算出 r 个最高权重的文档)【减少要查询的索引数量】
    • 静态得分(每篇文档 d 往往都有 一个与查询无关的静态得分 g(d))【减少要查询的索引数量】
    • 簇剪枝方法(cluster pruning)(先随机取KaTeX parse error: Expected '}', got 'EOF' at end of input: \sqrt{N)个先导者,再对他们聚类每个由若干个追随者,给定查询先计算与先导者的相似度,在计算最近的相似度的先导者的追随者的相似度)【减少要查询的索引长度】

    无序检索结果的评价:正确率,召回率,F 值
    有序检索结果的评价方法:

    • 插值正确率(interpolated precision)(在某个召回率水平r上的插值正确率定义为对于任意不小于r的召回率水平 r′ 所对应的最大正确率 )
    • MAP(mean average precision)
    • 前 k 个结果的正确率(precision at k,可简写成 P@k,缺点是不太稳定)
    • R-precision (对于共有|Rel| 篇相关文档查询,而在前|Rel|个返回结果中有 r 篇相关文档,此时的正确率和召回率都为r/|Rel|,定义R-Precision为r/|Rel|)
    • ROC
    • CG(cumulative gain,累积增益),一个具体的指标为NDCG(normalized discounted cumulative gain,归一化折损累积增益)。

    在线测试:A/B 测试

    RF(relevance feedback,相关反馈)的主要思想是,在信息检索的过程中通过用户交互(点击率等)来提高最终的检索效果 。

    LTR(learning to rank):

    • NB:线性分类器
    • Svm
    • Rocchio:kmean类似,线性分类器
    • kNN:非线性
    • 在基于语言模型(简记为 LM)的检索(关键词生成文章的概率)
    展开全文
  • 现代信息检索导论_王斌译_课后习题答案
  • 信息检索导论要点整理

    千次阅读 2017-07-07 10:23:24
    这是在准备期末考试的时候根据王斌博士翻译的《信息检索导论》(人民邮电出版社出版)和山东大学信息检索实验室的陈竹敏老师的授课课件进行整理的。 、归一化计算笔记繁琐。 前言 1、 IR的两种模式:pull(ad ...

    这是在准备期末考试的时候根据王斌博士翻译的《信息检索导论》(人民邮电出版社出版)和山东大学信息检索实验室的陈竹敏老师的授课课件进行整理的。

    、归一化计算笔记繁琐。

    前言

    1、     IR的两种模式:pull(ad hoc)或者push(filtering)

    Pull:用户是主动的发起请求,在一个相对稳定的数据集合上进行查询。

    push:用户事先定义自己的兴趣,系统在不断到来的流动数据上进行操作,将满足用户兴趣的数据推送给用户,典型就是推荐系统。

    布尔检索

    1、确定文档和IR的相关度是信息检索的核心。

    2、信息检索模型是描述信息检索中的文档、查询和它们之间关系(匹配函数)的数学模型。

    3、 布尔模型:定义

    文档表示:一个文档被表示为关键词的集合。

    查询表示:查询式被表示为关键词的布尔组合,用“与、或、非”连接起来。

    相关度计算:一个文档当且仅当它能够满足布尔查询式时,才能将其检索出来,检索策略是二值匹配。

    4、 布尔模型的优缺点

    优点:

    (1)  由于查询简单,因此容易理解。

    (2)  通过使用复杂的布尔表达式,可方便地控制查询结果。

    (3)  相当有效的实现方法。

    (4)  经过某种训练的用户可以容易地写出布尔查询式。

    (5)  布尔模型可以通过扩展来包含排序的功能。

    缺点:

    (1)  弱。不支持部分匹配,完全匹配会导致结果太多或太少。

    (2)  非常刚性。“与”意味着全部,“或”意味着任何一个。

    (3)  原则上讲,所有被匹配的文档都将被返回。

    (4)  不考虑索引词的权重,所有的文档都以相同的方式和查询相匹配。

    (5)  很难进行自动的相关反馈。

    (6)  如果一篇文档被用户确认为相关或者不相关,怎样相应地修改查询式呢?

    5、查准率:返回的能够满足用户信息需求的文档占总的返回文档的百分比。

    6、召回率:返回的能够满足用户信息需求的文档占总的能满足用户需求的文档的百分比。

    7、索引的一种表示方法:词项文档矩阵。

    8、倒排索引

    对于每一个词项,存储所有包含这个词项的文档的一个列表。一个文档用一个序列号docID来表示。(按照docID排列)

    应当使用可变长度的记录列表。在硬盘上,一串连续的记录是正常的,也是最好的。在内存里可以使用链表,或者可变长度的数组。

    9、建立索引的步骤(23页)

    (1)词条序列Token Sequence((修改过的词条,文档ID)对序列);

    (2)排序(先按照词条排序,再按照docID排序);

    (3)词典和倒排表(同一篇文档中多次出现的词被合并,分割成词典和倒排表,词汇的文档频率也被记录)。

    10、倒排索引的建立过程:词条化模块à语言学模块à索引模块

    11、布尔模型的匹配函数

        用qdnf表示查询q析取范式,qcc表示qdnf的任意合取分量。文献与查询q的相似度为


    如果值为1则表示相关,否则不相关。sim就是该模型的匹配函数。

    12、查询优化

    按照文档频率的顺序进行处理:先处理文档频率小的,再处理大的(这就是为什么我们在前面提到要存储词条的文档频率)。

    更一般的优化:获得所有词项的文档频率;保守地估计出每个OR操作后的结果大小;按照结果从小到大的顺序执行AND。

    词项词典和倒排记录表

    1、 如何建立词项词典?

    文档解析à词条化à停用词à词项归一化à词形归并à词干还原

    2、词条化:将给定的字符序列拆分成一系列子序列的过程,其中每一个子序列称之为一个“词条”(tokens)。/*我们平时说的分词*/这个过程中英文会有不同的问题。

    3、词条化的策略。针对不同的语言,采取不同策略的词条化方法。分词的基本方法:基于词典的最大匹配法(逆向最大匹配、正向最大匹配)、机器学习方法。

    4、消除停用词的问题和可能的方法

    优点:可以减少term的个数。

    缺点:有时消除的停用词对检索是有意义的。

    方法:查表法、基于文档频率。

    5、 词项归一化:将文档和查询中的词条“归一化”成一致的形式(如USA与U.S.A)。

    6、归一化的结果:在IR系统的词项词典中,形成多个近似词项的一个等价类。

    7、词项归一化的策略:建立同义词扩展表。

    8、 词形归并:减少曲折变化的形式,将其转变为基本形式(如am,are,isàbe)。词形归并可以减少词项词典中的词项数量。

    9、 词干还原

    通常指粗略地去除单词两端词缀的启发式过程。词干还原能够提高召回率,但是会降低准确率。

    10、     Porter算法:英文处理中最常用的词干还原算法。

    11、     合并算法回顾(32页)

    通过在两个倒排表之间同时移动指针来实现合并,此时的操作与线性表的总数成线性关系。

    基于跳表的倒排记录表快速合并算法。

    跳表指针能够跳过那些不可能出现在检索结果中的记录项。

    放置跳表指针的一个简单的启发式策略是:如果倒排表的长度是L,那么在每个处均匀放置跳表指针。

    注意:跳表指针只对AND类型的查询有用,对OR类型的查询不起作用。

    12、    短语查询第一种方法:二元词索引

    将文档中每个连续词对看成一个短语。其中的每一个二元词对都将作为词典中的词项。经过上述的处理,此时可以处理两个词构成的短语查询。

    13、    扩展的二元词索引

    名词和名词短语构成的查询具有相当特殊的地位。

    首先对文本进行词条化,然后进行词性标注;

    把每个词项分为名词(N)、虚词(X),冠词和介词和其他词;

    将形式为N*XN非词项序列看成一个扩展的二元词;

    每个这样的扩展的二元词对应一个词项。

    14、    短语查询的第二种方法:位置信息索引

    在这种索引中,对每个词项,采取以下方式存储倒排表记录:

    <词项,词项频率;

    文档1:位置1,位置2……;

    文档2:位置1,位置2……;

    ……>

    对于短语查询,仍然采用合并算法,查找符合的文档不只是简单判断两个词是否出现在同一个文档中,还需要检查它们出现的位置情况。

    索引构建与压缩

    1、构建索引的程序或计算机称倒排器索引器)。

    2、索引构建算法:

    基于块的排序索引构建算法(面向静态文档集、单机)

    内存式单边扫描索引构建算法

    分布式索引构建算法

    动态索引构建算法

    3、 基于块的排序索引算法(BSBI)

    基本思想:对每一个块都生成倒排记录,并排序,写入硬盘;然后将这些块合并成一个长的排好序的倒排记录。

    存在的问题:(假设:能够将词典存入内存中)需要该词典(动态增长)去查找任一词项和词项ID之间的关系。事实上,可以采用<词项,文档ID>对来代替<词项ID,文档ID>对。中间文件会变得非常大,这是一个可扩展的,但效率非常低的索引构建算法。

    4、SPIMI内存式单遍扫描索引算法

    核心思想1:为每一个块单独生成一个词典——不需要维护全局的<词项,词项ID>映射表。

    核心思想2:不进行排序。有新的<词项,文档ID>对时直接在倒排记录表中增加一项。

    根据这两点思想,可以为每一个块生成一个完整的倒排索引。然后将这些单独的索引合并为一个大的索引。

    5、分布式索引构建

    利用集群中的主控节点来指挥索引构建工作(我们认为主控节点是“安全的”);将索引构建过程分解成一组并行的任务;主控计算机从集群中选取一台空闲的机器并将任务分配给它。

    6、 并行任务。首先将输入的文档集分割成n个数据片,每个数据片就是一个文档子集(对应于BSBI/SPIMI中的数据块)

    两种文档集分割方法:基于词项的分割,基于文档的分割。

    7、 分析器Parsers

    主节点将一个数据片分配给一台空闲的分析服务器。分析器依次读取文档并生成<词项,文档>对。分析器将这些<词项,文档>按照词项对分成j个段,每一段是按照词项首字母划分成的一个区间。然后可以进行索引的倒排。

    8、 采用MapReduce的索引构建架构

    Map:输入àlist(k,v) Reduce:(k,list(v))à输出。

    //索引构建中上述架构的实例化

    Map:Web文档集àlist(词项ID,文档ID)

    Reduce:(<词项ID1,list(文档ID)>,<词项ID2,list(文档ID)>,…)à(倒排记录表1,倒排记录表2,…)

    9、动态索引构建方法

    (1)  周期性索引重构

    (2)  维护一个大的主索引,新文档存储在一个小的辅助索引中(位于内存),检索可以同时遍历两个索引并将结果合并,定期地将辅助索引合并到主索引中,文档更新通过先删除后插入的方式实现。

    10、    主索引与辅助索引存在的问题

    (1)  频繁的合并,带来很大的开销;

    (2)  合并过程效率很低

    如果每个词项的倒排记录表都单独成一个文件,那么合并主索引和辅助索引将会很高效。合并将是一个简单的添加操作。但需要非常多的倒排文件,对文件系统来说是低效的。

    11、    对数合并

    维护一系列的索引I0,I1,I2,…,每个都是前一个的两倍大小20*n,21*n,22*n,…。n是辅助索引Z0的大小。

    辅助索引Z0存储在内存中。

    将较大的那些(I0,I1,I2,…)存储在磁盘中。

    当Z0达到上限n时,将它写入磁盘的I0中。

    当Z0下一次达到上限时,它会和I0合并,生成Z1(大小21*n)


    12、总结——索引构建


    13、为什么要压缩(一般来说)?

    (1)  节省磁盘空间

    (2)  提高内存的利用率

    (3)  加快数据从磁盘到内存的传输速度(前提:解压缩算法要很快)。

    14、无损压缩:压缩之后所有的原始信息都被保留(在IR系统中常采用无损压缩)。

    15、有损压缩:丢掉一些信息。

    16、一些预处理步骤可以看成有损压缩:大小写转换、停用词剔除、词干还原、数字去除。


    词汇量的大小M和文档集大小T在对数空间中存在着斜率为0.5的线性关系。

    18、Zipf定律:排名第i多的词性的文档集频率与1/i成正比。

    高频词项很少,低频罕见词项很多。

    19、为什么要压缩词典?

    搜索从词典开始。想要将词典放入内存中。想和其他应用程序共享内存资源。手机或嵌入式设备通常只有很小的内存。既是词典不存入内存中,也希望它能比较小,以便搜索能快速启动。所以压缩词典非常重要。

    20、词典存储——定长方法存储词项浪费空间。

    21、压缩词项列表:将词典看成单一字符串,只想下一词项的指针同时也标识着当前词项的结束。

    22、按块存储:每k个词项分成一块,只保留第一个指针,需要存储词项长度(额外1字节)。

    23、词典搜索的比较次数与平均比较次数(包括压缩的词典和未压缩过的词典)的计算。

    24、前段编码:按照词典顺序排列的连续此项之间往往具有公共前缀…。

    25、倒排记录表的压缩

    26、按照文档ID的递增顺序来存储一个词项的倒排列表。可以存储间距。

    27、    可变长度编码

    如果词项的平均间距为G,我们想使用log2G bit/间距项。

    先用一个字节来存储G,并分配1bit作为延续位c

    如果G≤127,对7位有效码采用二进制编码并设延续位c=1(表示结束)

    若G>127,则先对G低阶的7位编码,然后采取相同的算法用额外的字节对高阶bit位进行编码

    设置最后一个字节的延续位为1(c=1),其他字节的c=0(表示未结束)

    28、    可变字节编码被很多商业/研究系统所使用。实现简单,能够在时间和空间之间达到一个非常好的平衡点。

    web搜索

    1、相似性计算

    2、搭叠Shingles(N元词N-Grams)

    给定正整数k及文档d的一个词项序列,可以定义文档d的k-shingle为d中所有k歌连续词项构成的序列。

    直观上看,如果两个文档的shingle集合几乎一样,那么它们就满足近似重复。

    3、Jaccard系数

    在文档的Single集合上计算  交集大小/并集大小

    /*计算所有文档对之间搭叠的精确交集是非常费时而且难以处理的。使用一种聪明的方式从Shingles中选出一个子集(素描sketch)来近似计算*/

    4、近似重复检测(小结)

    Shingle算法的核心思想是将文件相似性问题转换为集合的相似性问题。

    数量较大时,对shingle集合进行抽样,以降低空间和时间计算复杂性。

    shingle取样主要有三种方法,即Min-Wise,Modm,和Mins。

        Mins技术先将shingle和整数集进行映射,然后从中选择最小s个元素组成取样集合。

        此外,还可以使用shingle的hash值代表shingle进行相似性计算,能够节省一定计算开销。

    5、web采集器(爬虫)

    (1)  从已知的种子URL开始

    (2)  获取页面并进行解析:提取页面中包含的链接,把链接放入URL队列

    (3)  对队列中的URL,转(2)

    6、采集器必须具有的功能:礼貌性、鲁棒性、分布式、可扩展性、性能和效率、新鲜度、功能可扩展性。

    7、web图

    8、锚文本:超链接周围还有一些文本,这些文本通常被嵌在<a>标签(成为锚)的href属性中。

    可以根据锚文本所在的页面的权威性来确定锚文本的权重。

    web上随处可见的一个现象是,很多网页的内容不包含对自身的精确描述,因此web搜索者不一定要使用网页中的词项来对网页进行查询,而使用锚文本。锚文本周围窗口中的文本也可以当成锚文本一样来使用。

    9、PageRank

    对web图中的每一个节点赋一个0-1之间的分值。

    查询词无关的排序。

    10、    随机行走,随机跳转

    11、    Markov链

    Markov链是随机游走在数学上的抽象。

    12、    遍历Markov链。

    满足遍历性的必要条件:

    (1)  不可约,任意两个状态之间都存在非零概率转移序列;

    (2)  对任意的初始状态,经过有限时间T0的跳转后,在T>T0时刻处于其它任意状态的概率都大于0;

    (3)  非周期性,不存在两个状态子集之间的循环往复。

    13、    将web图上的一个随机冲浪过程看成是马尔科夫链,其中马尔科夫链中的每一个状态对应一个网页,而每个转移概率代表一个从网页跳转到另外一个网页的概率。

    14、    web图的邻接矩阵可以这么定义:如果存在网页i到网页j的一条链接,那么Aii=1,否则为0 。

    15、    概率转移矩阵,在邻接矩阵的基础上进行操作。如果A的某一行没有1(即没有出链),则用1/N代替每个元素(随机选择其它任一网页)。其它行的处理如下:

    (1)  用每行中的1的个数去除每个1,因此如果某行有3个1,则每个1用1/3代替(归一化);

    (2)  上面处理后的结果矩阵乘以1−α;

    (3)  对上面得到的矩阵中的每个元素都加上α *1/N。

    16、    稳态概率


    17、计算a的一种方法:幂迭代   60

    18、PageRank小结

    预处理:

    web图à邻接矩阵à概率转移矩阵P

    由P计算a

    元素ai是一个0和1之间的数:即页面i的PageRank

    查询处理:

    检索满足查询要求的页面。按PageRank排序。排序与查询词是无关的。

    19、PageRank对于爬虫的爬取策略还是很有用的。

    20、超链导向的主题搜索(HITS)

    对每个网页给出两个得分:一个得分被称为hub(导航)值,另外一个被称为authority(权威)值。

    针对某一主题的好Hub页会指向很多关于这个主题的Authority页面。关于某一主题的好Authority页面会被很多针对这一主题的好Hub页指向。循环定义Circulardefinition–导致可以迭代求解页面的Hub值和Authority值。

    21、HITS步骤

    确定基本集à精选出Hub页和Authority页à迭代更新。

    向量模型及检索系统

    1、在排序检索模型中,系统根据文档与query的相关性排序返回文档集合中的文档,而不是简单地返回所有满足query描述的文档集合。

    2、Jaccard系数。一种常用的衡量两个集合A,B重叠度的方法。交集除以并集。

    3、用Jaccard系数评分的问题:没有考虑一下两点:

    (1)  词项频率(词项在文档中出现的次数);

    (2)  罕见词比高频词的信息量更大,更加具有区分度。

    4、词项-文档词频关联矩阵:将每一个文档看成是一个词频向量(矩阵中的一列)。

    5、词袋模型:不考虑词在文档中出现的顺序。

    6、词项频率:词项t在文档d中出现的次数,记为tft,d

    7、一种替代原始tf的方法:对数词频



    文档-词项的匹配得分是所有同时出现在q和文档d中的词项的词频的对数之和。

    8、对于罕见词我们希望赋予高权重,对于常见词项我们希望赋予正的低权重。

    9、文档频率:出现词项的文档数目。



    14、二值关联矩阵、词频矩阵

    二值à词频àtf-idf矩阵

    每篇文档表示成一个基于tf-idf权重的实值向量(空间的每一位都对应词项,文档是空间中的点或者向量)。

    将Queries表示成向量

    思路:对于查询做同样的处理,即将查询表示成同一高维空间的向量,在向量空间内根据query与文档向量间的距离来排序。

    欧氏距离不好。可以通过计算文档与query的夹角给文档排序。

    15、文档长度归一化,可以用2范数对文档长度进行归一化,这样文档之间的长度差异就不会影响相关性了。

    16、计算题余弦相似度计算实例46页

    ========================检索系统=====================

    17、词典中保存每个词的idf(逆文档频率)值,词项频率tf存入倒排索引中。

    18、精确top K检索加速方法一:快速计算余弦

    排序只需要相对得分,于是,不需要对查询向量进行归一化。

    (1)  无权重查询

    (2)  堆排序法N中选K

    (3)  提前终止计算

    采用另一种与查询无关的反映结果好坏程度的指标(静态质量)。例如,页面d的PageRank g(d)就是度量有多少好页面指向d的一种指标。69页例子。

    19、精确top K 检索仍然无法避免大量文档参与计算。

    20、 非精确top K检索

    一般思路:找一个文档集合A,K < |A|<< N,利用A中的top K结果代替整个文档集的top K结果。

    策略一:索引去除

    对于一个包含多个词项的查询来说,很显然可以仅仅考虑那些至少包含一个查询词项的文档(可以进一步扩展这种思路:只考虑那些词项的idf值超过一定阈值的文档;只考虑包含多个查询词项的文档)。

    策略二:胜者表//例子78页

        对于词典中的每个词项t,预先计算出r个最高权重的文档。词项t所对应的tf值最高的r篇文档构成t的胜者表,也成优胜表或高分文档。(其中r的值需要在索引建立时给出,因此可能会出现r<K的情况)。

    策略三:静态得分

    希望排序靠前的文档既是相关的有时权威的。(相关性通过余弦相似度得分来判断,权威性是与query无关的文档本身的属性决定的)。

    利用g(d)排序的优点:高分文档更可能在倒排记录表遍历的前期出现,在时间受限的应用中可以提前结束倒排记录表的遍历。

    高端表和低端表:对每个词项,维护两个倒排记录表,分别称为高端表和低端表。遍历倒排记录表时,仅仅先遍历高端表,如果返回的结果数目超过K,那么直接选择前K篇文档返回。否则,继续遍历低端表,从中补足剩下的文档数目。(实际上相当于将整个索引分层)

        策略四:影响度排序

           思路一:提前结束

           思路二:词项按照idf降序排列

        策略五:簇剪枝方法

           先导者,追随者。

    21、层次索引,可以看成是优胜表的一般化形式。

    22、用窗口大小来度量位置关系。

    23、    搜索系统的组成



    检索评价

    1、无序检索结果的评价。

    2、整个文档集的划分

    未检索出的不相关文档(NN),未检索出的相关文档(NR),检索出的不相关文档(RN),检索出的相关文档(RR)。

    3、召回率(Recall): RR/(RR + NR),返回的相关结果数占实际相关结果总数的比率,也称为查全率,R∈[0,1]。正确率(Precision):RR/(RR + RN),返回的结果中真正相关结果的比率,也称为查准率,P∈[0,1]。

    两个极端情况:返回有把握的一篇;全部文档都返回。

    4、召回率难以计算

    解决方法:Pooling方法,或者不考虑召回率。

    不可能准确地计算召回率。

    缓冲池(Pooling)方法:对多个检索系统的top N个结果组成的集合进行人工标注,标注出的相关文档集合作为整个相关文档集合。

    5、一个综合评价准则:F = P和R的融合


    表示召回率的重要程度是正确率的倍。

    6、为什么使用调和平均计算F值。

    (1)  调和平均比较“保守”。调和平均小于算术平均和几何平均。如果采用算术平均计算F值,那么一个返回全部文档的搜索引擎的F值就不会低于50%,这有些过高。

    (2)  不管R还是P,如果有一个偏低,都应该体现出来。最小值可以达到该目的,但是最小值方法不平滑,而且不易加权。基于调和平均计算出的F值可以看成是平滑的最小中函数。

    7、精确率是所有判定中正确的比率(相关à相关,不相关à不相关)。

    8、精确率不适合IR的原因

    由于和查询相关的文档毕竟占文档集的极少数,所以即使什么都不返回也会得到很高的精确率。用户希望找到某些文档并且能够容忍结果中有一定的不相关性,返回一些即使不好的文档也比不返回任何文档强。因此…

    9、有序检索结果的评价

    10、查准率-召回率曲线

    检索结果以排序方式排列,用户不可能马上看到全部文档,因此,在用户观察过程中,正确率和召回率在不断变化。

    位于上面的曲线对应的系统结果更好。

    11、P-R曲线为何出现锯齿形状?

    这是很正常的。如果第k+1篇文档不相关,则查全率和前k篇文档的查全率是一样的,但是准确率降低了,所以曲线会下降。如果第k+1篇文档相关,则查全率和查准率都上升。如此就会出现锯齿状。

    12、需要去掉锯齿,进行平滑。可采用插值查准率,记为pinter

    在查全率为r的位置的插值查准率,定义为查全率不小于r的位置上的查准率的最大值。

    13、P-R的优缺点

    优点:简单直观。既考虑了检索结果的覆盖度,有考虑了检索结果的排序情况。

    缺点:单个查询的P-R曲线虽然直观,但是难以明确表示两个查询的检索结果的优劣。

    14、基于P-R曲线的单一指标

    固定检索等级的查准率

    11点平均正确率

    15、    更多的评价准则:AP

    平均正确率(AP):对不同召回率点上的正确率进行平均。

    16、    不考虑召回率

    Precision@N:在第N个位置上的正确率

    17、    宏平均(Macro Average):对每个查询求出某个指标,然后对这些指标进行算术平均。

    18、    微平均(Micro Average):将所有查询视为一个查询,将各种情况的文档总数求和,然后进行指标的计算。

    19、    宏平均对所有查询一视同仁,微平均受返回文档数目比较大的查询影响。

    20、    在每个相关文档位置上查准率的平均值,被称为平均查准率(AP)

    21、    对所有查询求宏平均,就得到平均查准率均值(MAP)



    Q为信息需求,qjQ所对应的所有相关文档集合为{d1,d2,…,dmj},Rjk是查询qj的返回结果,该结果中包含{d1,d2,…,dk}而不含有dk+1及以后的相关文档

    22、第50页可出计算。

    23、覆盖率:系统找到的用户已知的相关文档比例。

    新率:系统返回的新相关文档(用户之前未知)的比例。

    24、GMAP


    25、NDCG

    26、静态摘要,动态摘要

    相关反馈与查询扩展

    1、交互式相关反馈:在初始检索结果的基础上,通过用户交互指定那些文档相关或不相关,然后改进检索的结果。(最著名的相关反馈方法:Rocchio相关反馈)。

    2、查询扩展:通过在查询中加入同义或者相关的词项来提高检索结果。

    3、两种提高召回率的方法:相关反馈查询扩展

    4、提高召回率的方法:

    局部方法:对用户查询进行局部的即时的分析(主要的局部方法:相关反馈)。

    全局方法:进行一次性的全局分析(比如分析整个文档集)来产生同/近义词词典。

    5、相关反馈的基本思想

    (1)  用户提交一个查询;

    (2)  搜索引擎返回一系列文档;

    (3)  用户将部分返回文档标记为相关的,将部分文档标记为不相关的;

    (4)  搜索引擎根据标记结果计算得到信息需求的一个新查询表示(当然我们希望该表示好于初始的查询表示);

    (5)  搜索引擎对新查询进行处理,返回新结果,新结果有望有更高的召回率。

    6、相关反馈分类

    显式相关反馈(用户相关反馈):用户显示参加交互过程;

    隐式相关反馈:系统根据用户的行为来推测返回文档的相关性,从而进行反馈;

    伪相关反馈(盲相关反馈):没有用户参与,系统直接假设返回文档的前k篇是相关的,然后进行反馈。

    7、相关反馈中的核心概念:质心

    质心是一系列点的中心。

    8、相关反馈基本理论:嘉定我们要找一个最优查询向量q,它与相关文档之间的相似度最大且同时又和不相关文档之间的相似度最小。

    最优的查询向量等于相关文档的质心向量和不相关文档的质心向量的差。

    9、Rocchio算法29页

    10、    Rocchio1971算法40页

    11、    正反馈,负反馈。正反馈价值往往大于负反馈,很多系统甚至只允许正反馈。

    12、    相关反馈中的假设:

    (1)  用户对初始查询有充分的认识,直到使用那些词项来表达;

    (2)  相关文档的原型有一种良好的形式。

    13、    代替相关反馈的方法:用户修改并重新提交查询。

    14、    相关反馈存在的问题

    (1)  相关反馈开销很大(相关反馈生成的新查询往往很长,长查询的处理开销很大)

    (2)  用户不愿意提供显式的相关反馈。

    15、    隐式相关反馈优缺点

    优点:不需要用户显示参与,减轻用户负担。用户行为某种程度上反映用户的兴趣,具有可行性。

    缺点:对行为分析有较高要求;准确率不一定能保证;某些情况下需要增加额外设备。

    16、    伪相关反馈

    伪相关反馈对于真实相关反馈的人工部分进行自动化

    伪相关反馈算法:

        对于用户查询返回有序的检索结果;

        假定前k篇文档是相关的;

        进行相关反馈

    平均效果上不错,但是对于某些查询而言可能结果很差,几次循环之后可能会导致查询漂移。

    17、    伪相关反馈优缺点

    优点:不用考虑用户的因素,处理简单;很多实验页取得了较好效果。

    缺点:没有通过用户判断,所以准确率难以保证;不是所有的查询都会提高效果。

    18、    查询扩张主要使用信息:同义词或近义词。

    通常会提高召回率,可能会显著降低正确率。

    相关词项来源:人工编辑的同义词词典、自动构造的同义词词典、查询日志等。

    概率检索模型

    1、向量空间模型的优缺点

    优点:简洁直观,可以应用到很多其他领域(文本分类、生物信息学);支持部分匹配和近似匹配,结果可以排序;检索效果不错。

    缺点:理论上不够(基于直觉的经验性公式);索引项之间的独立性假设与实际不符(实际上,term的出现之间是有关系的,不是完全独立的)。

    2、概率检索模型

    通过概率的方法将查询和文档联系起来。

    定义3个随机变量R、Q、D:相关度R={0,1},查询Q={q1,q2,…},文档D={d1,d2,…}。过计算条件概率P(R=1|Q=q,D=d)来度量文档和查询的相关度。

    概率模型包括一系列模型,如经典的二值独立概率模型BIM、BM25模型等(还有贝叶斯网络模型)

    3、概率排序原理PRP

    利用概率模型来估计每篇文档和需求的相关概率P(R=1|d,q),然后对结果进行排序。

    最简单的PRP情况:

    检索没有任何代价因子,或者说不会对不同行为或错误采用不同的权重因子。

    在返回一篇不相关文档或者返回一篇相关文档不成功的情况下,将会失去1分(在计算精确率时这种基于二值的情形也往往成为0/1)风险。

    而检索的目标是对于用户任意给定的k值,返回可能性最高的文档前k篇作为结果输出。也就是说,PRP希望可以按照P(R=1|d,q)值的降序来排列所有的文档。

    4、定理:在1/0损失的情况下,PRP对于最小化期望损失(也成为贝叶斯风险)而言是最优的。

    5、基于检索代价的概率排序原理

    C1表示一篇相关文档未返回所发生的代价

    C0表示返回一篇不相关文档发生的代价

    PRP认为,如果对于一篇特定的文档d及所有其他未返回的文档d′ 都满足

    C0· P(R=1|d) –C1· P(R=0|d) ≤ C0· P(R=1|d’) –C1· P(R=0|d′)

    一个是当它不相关时却返回的代价C0· P(R=1|d),另一个是相关时却没有被返回所造成的代价C1· P(R=0|d)。两者相减表示返回文档d 的代价函数,也即此时前者越低越好,后者越高越好。

    那么d就应该是下一篇被返回的文档。

    6、贝叶斯公式

    先验概率反映了各种“原因”,发生的可能性大小(在试验前是知道的,以往的经验得到)。

    后验概率反映了试验后对各种“原因”发生的可能性大小的推断。

    7、二值独立概率模型BIM

    为了对概率函数P(R|q,d)进行估计,引入一些简单假设。

    “二值”等价于布尔值:文档和查询都表示为词项出现与否的布尔向量。也就是说,文档d表示为向量。类似的我们将查询也表示为向量。

    独立性指的是词项在文档中的出现时互相独立的,BIM并不识别词项之间的关联。

    8、RSV检索状态值

    9、这一带课件上有好多内容在整理时并未细看,要注意。

    10、    在减少出现事件的概率估计值的同时提高未出现时间的概率估计值的方法称为平滑

    11、    36页BIM模型小结

    12、    BIM模型的优缺点

    优点:BIM模型建立在数学基础上,理论性较强。

    缺点:需要估计参数;原始的BIM没有考虑TF、文档长度因素;BIM中同样存在词项独立性假设。

    13、BM25:一个非二值的模型

    文本分类及朴素贝叶斯分类器

    1、文本分类的机器学习方法:朴素贝叶斯、Rocchio、kNN、SVM

    2、当学习方法基于统计时,这种方法也成为统计文本分类。

    3、搜索引擎中文本分类的应用:语言识别、垃圾网页的识别、是否包含淫秽内容、领域搜索或垂直搜索、静态查询、情感识别。

    4、朴素贝叶斯分类器

    分类规则


    平滑操作

    23页例题,计算题

    5、朴素贝叶斯方法起作用的原因

    既是在条件独立性假设严重不成立的情况下,朴素贝叶斯方法依然能够高效地工作;

    分类的目标是预测正确的类别,并不是准确地估计概率。

    6、在文本分类中,通常要将文本表示在一个高位空间下,每一维对应一个词项。特征选择是从训练集合出现的词项中选出一部分子集的过程。在文本分类过程中也仅仅使用这个子集作为特征。

    特征选择有两个主要目的:

    (1)  通过减少有效的词汇空间来提高分类器训练和应用效率。

    (2)  特征选择能够去除噪音特征,从而提高分类的精度。

    7、特征选择方法主要基于其所使用的特征效用指标来定义。

    特征效用指标:

    频率法-选择高频词项

    互信息-选择具有最高互信息的那些词项

    卡方

    8、互信息(MI)给出的是词项所包含的有关类别的信息及类别包含的有关词项的信息量。

    基于向量空间模型的文本分类

    1、向量空间模型

    词项-文档矩阵:二值à计数à权重矩阵(tf-idf值)

    相关性=向量距离:欧氏距离à夹角à余弦相似度

    2、利用向量空间模型进行文本分类的思路主要基于邻近假设:

    (1)  同一类的文档会构成一个邻近区域

    (2)  而不同类的邻近区域之间是互不重叠的

    3、核心问题:如何找到分类面决策边界。

    4、Rocchio方法进行向量空间分类的思路

    利用质心来定义分类边界

    一个类别的质心可以通过类中文档向量的平均向量或者质心向量来计算。

    计算每个类的中心向量。

    将每篇测试文档分到离它最近的那个中心向量。

    两个类的边界由那些到两个类质心等距的点集组成(超平面)。

    5、Rocchio分类方法的缺陷

    为了遵循邻近性的要求,Rocchio分类中的每个类别一定要近似球形,并且它们之间具有相似的球半径。。。。

    6、kNN(k近邻)方法

    将每篇测试文档分到训练集中离它最近的k篇文档所属类别中最多的那个类别。

    基本依据:根据邻近假设,一篇测试文档d将和其邻域中的训练文档应该具有相同的类别。

    Voronoi剖分

    kNN思路的改进(概率型版本和基于余弦相似度进行加权)20页

    当训练集非常大的时候,kNN分类的精度很高;如果训练集很小,kNN可能效果很差。

    7、线性分类器。

    支持向量机

    1、对于SVM而言,它定义的准则是寻找一个离数据点最远的决策面。从决策面到最近数据点的距离决定了分类器的间隔(margin)。

    2、离超平面最近的点事支持向量。

    3、SVM基本过程

    基于给定训练数据集,通过二次优化过程寻找最佳分类超平面;

    对于待分类的新数据点,利用分类函数计算该点到超平面的距离;

    距离的正负决定了该数据点类别的归属;

    如果该点在分类器的间隔之内,分类器可以在原来的两个类之外,返回“类别未知”。

    4、软间隔分类

    引入松弛变量允许决策间隔犯错误。

    训练的目标依然是最小化错误,并求最大间隔超平面。

    5、非线性SVM

    将数据映射到一个高维空间并在此空间上使用线性分类器将数据分开。

    通过空间映射将原始空间映射到新空间,为避免显式的映射函数,引入核函数(定义在原始空间下但是结果是新空间下的内积函数)。

    6、核函数

    核函数实际上是一个对应于新特征空间上的内积函数。

    文本聚类

    1、 (文档)聚类是将一系列文档按照相似性聚团成子集或者簇的过程。

    2、 聚类假设:在考虑文档和信息需求之间的相关性时,同一簇中的文档表现互相类似。

    3、 文档聚类用于提高召回率

    可以实现将文档集中的文档进行聚类;

    当文档d和查询匹配时,也返回包含d的簇所包含的其他文档。

    4、扁平聚类算法

    通过一开始将全部或部分文档随机划分为不同的组。通过迭代方式不断修正。(代表算法:k-means)

    5、层次聚类算法

    构建具有层次结构的簇。自底向上的算法成为凝聚式算法。自顶向下的算法成为分裂式算法。

    7、硬聚类:每篇文档仅仅属于一个簇。

    8、软聚类:一篇文档可以属于多个簇。

    9、k-means聚类算法一定会收敛之证明44页

    10、    收敛并不意味着会达到全局最优的聚类结果,这是k-means聚类算法的最大缺点之一。如果开始的种子选得不好,那么最终的聚类结果可能会非常糟糕。

    11、判断聚类结果好坏:内部准则、外部准则

     






    展开全文
  • 现代信息检索导论 2013 王斌 计算所 全部课件
  • 信息检索导论书本第二课PPT(英文的).
  • 信息检索导论书本第一课的PPT(英文版)
  • 中国科学院大学信息检索导论(李波)期末考试试题
  • 信息检索导论王斌译第一章课后习题答案
  • 信息检索导论》第一章 布尔检索信息检索布尔检索模型词项-文档关联矩阵(incidence matrix)倒排索引欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片...

    信息检索

    定义:信息检索是从大规模非结构化数据(通常是文本)的集合(通常保存在计算机上)中找出满足用户信息需求的资料(通常是文档)的过程。

    非结构化数据:没有清晰和明显语义结构的数据。
    半结构化数据:通过显式的标记来体现语言结构的数据(如网页中的结构标签)。
    

    推荐系统是general query search 是一种特殊的IR任务,用户没有显示的给出query

    分类:

    • Web搜索(web search)
      大规模分布式文档的检索
    • 面向企业、机构和特定领域的搜索(domain-specific search)
      对公司内部文档、专利库或生物医学文献等的搜索
    • 个人信息检索(personal information retrieval)
      操作系统或系统应用中融合的信息检索功能

    布尔检索模型

    对于(1)大规模文档集(2)更灵活的匹配方式,如NEAR操作符,’5个词内‘或’同一句中‘ (3)需要对结果进行排序。这些情况下,就不能再采用线性扫描(如unix系统中grep指令)的方式。一种非线性扫描的方式是实现给文档建立索引(index)

    grep is line oriented IR is document oriented

    词项-文档关联矩阵(incidence matrix)

    词项(term):索引的单位,通常用词来表示
    文档(document):检索系统的检索对象,可以是单独一条记录或者是一本书的各章
    文档集/语料库(collection/corpus):所有文档的集合

    在这里插入图片描述
    矩阵从行看,可以得到每个词项对应的文档向量,表示词项在哪些文档出现或不出现
    从列来看,可以得到每个文档对应的词项向量,表示文档中哪些词项出现或不出现。
    1表示出现,0表示不出现。

    词项-文档关联矩阵的布尔查询处理
    对于采用AND、OR及NOT等逻辑操作符连接起来的布尔表达式查询,通过对文档向量间逻辑操作来得到查询结果。

    例:为响应查询 Brutus AND Caesar AND NOT Calpurnia,我们分别取出 Brutus、Caesar 及 Calpumia 对应的行向量,并对 Calpumia 对应的向量求反,然后进行基于位的与操作,得到:
    110100 AND 110111 AND 101111 = 100100
    结果向量中的第 1 和第 4 个元素为 1,这表明该查询对应的剧本是 Antony and Cleopatra 和 Hamlet。

    倒排索引(inverted index)

    对于词项个数和文档规模很大的情况,构造出的关联矩阵是高度稀疏的。只记录原始矩阵中1的位置的表示方法比词项-文档关联矩阵更好,因此引出了倒排索引

    **索引(index)**由一部字典(dictionary)和一个全体倒排记录表(postings)组成。

    建立索引的主要步骤如下:
    1、收集需要建立索引的文档
    2、将每篇文档转换成一个个词条(token)的列表,这个过程称为词条化(tokenization)或者切词。
    3、进行语言学预处理,产生归一化的词条来作为词项(去掉复数标记等 )
    4、对所有文档按照其中出现的词项来建立倒排索引

    在这里插入图片描述
    上图表现了构建倒排索引的过程。
    1、给每篇文章的所有词项加上文档ID
    2、按照字母顺序排序
    3、将同一词项合并,并将词项与文档ID分开存储(词典存储在内存中,记录表存储在磁盘中)

    注:在字典的每个词项中还可以存储其他信息,如文档频率
    每个倒排记录表存储了词项出现的文档列表,还可以存储词项频率(词项在文档中出现的次数)、词项在文档中出现的位置

    基于倒排索引的布尔查询处理
    例:对于Brutus AND Calpurnia这样的布尔查询,首先在字典中分别定位Brutus和Calpurnia,并返回其倒排记录表(posting lists)。对两个倒排记录表求交集(intersect),也称合并。

    在这里插入图片描述

    对于两个有序记录表的合并算法如下
    在这里插入图片描述

    查询优化
    对于更加复杂的查询,可按照词项的文档频率(即倒排记录表的长度)从小到大依次处理,这使得中间结果(多个布尔操作组合起来的query,会产生中间结果)的大小都不会超过最短的倒排记录表。

    布尔查询适合精确查询(法律领域等)

    对基本布尔操作的扩展(beyond term search)

    严格的布尔运算所得到的无序结果集合远远不能使用户满意,故可在系统中加入更多的操作:
    1、邻近操作符(proximity) :用于指定查询中两个词项应该互相靠近
    2、短语查询(phrase search): 可以看成特殊的邻近操作符
    3、尾通配符查询

    例:空格表示逻辑“ 或” 关系,&表示 AND,/s、/p 及/k 分别表示处 于同一句子、段落和 k 个词之内。双引号表示的是短语查询(phrase search,即多个词连续出现, 参见 2.4 节),感叹号(!)表示尾通配符查询(参见 3.2 节)

    查询模型的改进方向

    1、容忍拼写错误及查询和文档中词语表达不一致时的检索方法
    2、对复合词或短语的搜索
    3、通过引入词项频率(词项在文档中出现的次数)等,得到文档相关的可信度,而不是简单的词项存在与不存在。
    4、对返回结果排序

    展开全文
  • 信息检索导论》部分实验python实现汇总实验一:倒排记录表的合并算法实现1. [两个倒排记录表的合并算法。P8](https://blog.csdn.net/qq_36949278/article/details/105647801)2. [输入多个词项与查询时倒排记录表的...
  • 信息检索导论-读书笔记 顺便推荐一下Markdown写作平台 作业部落 再推荐一下wordpress编辑Latex公式的插件 MathJax ,其使用文档在此 转载于:https://www.cnblogs.com/No-body/p/4207214.html...
  • 信息检索导论》 Christopher D.Manning 等著 1. 信息检索:信息检索是从大规模非结构化数据(通常是文本)的集合(通常保存在计算机上)中找出满足用户信息需求的资料(通常是文档)的过程。 2. 检索方式: 1...
  • 【阅读笔记】《信息检索导论》第三章 词典及容错检索词典搜索的数据结构通配符查询一般的通配符查询轮排索引支持通配符查询的k-gram索引拼写校正词项独立(isolated-term)的校正编辑距离拼写校正中的k-gram索引上下文...
  • 除了之前还留了个尾巴的操作系统课程笔记,由于要入职的组是做搜索的,所以打算看一下相关的书籍《信息检索导论》,应该能够从中收获很多知识。 不过这一系列笔记可能跟之前网络和操作系统的课程笔记不太一样,...
  • 信息检索导论学习笔记(一)布尔检索 定义 信息检索是从大规模非结构化数据(通常是文本)的集合(通常保存在计算机上)中找出满足用户信息需求的资料(通常是文档)的过程。 倒排索引 为提高查询效率,建立...
  • 【阅读笔记】《信息检索导论》第四章 索引构建基于块的排序索引方法BSBI算法(blocked sort-based indexing)内存式单遍扫描索引构建方法SPIMI 算法(single-pass in-memory indexing)分布式索引构建方法MapReduce-基于...
  • 【阅读笔记】《信息检索导论》第二十一章 链接分析Web图PageRnak马尔科夫链PageRank的计算面向主题的PageRankHub网页及AuthorityWeb子集的选择 Web图 问题:网页本身携带的词项和用户描述同一网页的词项之间往往存在...
  • 第八章 信息检索的评价 1. 无序检索结果集合的评价 如何度量系统的效果?信息检索中最常用的两个指标是正确率和召回率。 正确率(Precision,简记为P): 返回的结果中相关文档所占的比例 Precision=返回结果...
  • 信息检索导论学习笔记(四) 索引构建 1.基于块的排序索引方法 2.内存是单遍扫描索引构建方法
  • 王斌老师讲课课件,仅供个人保存,请勿下载。。。。。。。。

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 269
精华内容 107
关键字:

信息检索导论