参数化索引及域索引
迄今为止,我们都将文档看成一系列词项的序列.实际上,大多数文档都具有额外的结构信息.数字文档通常会把与之相关的元数据(metadata)以机读的方式一起编码.所谓元数据,指的是和文档相关的一些特定形式的数据,比如文档的作者,标题以及出版日期等等.
问题:考虑查询"寻找由William Shakespeare 于 1961年撰写,其中包含短语alas poor Yorick的文档".和通常一样,查询的处理过程需要进行倒排记录表的合并操作.但是不同的是,这里在处理查询时还会涉及参数化索引上的合并操作.
对上述查询,如何设计索引结构?通常有两种方式:
词典方式处理
在词典中,对不同域分别建立一个索引.同通常一样,查询的处理过程需要进行倒排记录表的合并操作(不同域下倒排索引的合并).
倒排记录方式处理
显然,对于查询,词典方式下域索引的处理要对多个索引进行合并处理,效率相对会比较低.因此考虑将域信息存储在倒排记录而不是词典中.
采用这种编码的另外一个重要的原因是它能支持域加权评分(weighted zone scoring)技术的使用
域
域和字段很相似,只是它的内容可以是任意的自由文本.字段通常的取值可能性相对较小,而域可以由任意的,数目无限制的文本构成.比如,通常可以把文档的标题和摘要看作域.我们可以对文档的不同域构建独立的倒排索引.
域加权评分
给定一个布尔查询q和一篇文档d,域加权评分方法给每个(q,d)对计算出一个[0,1]之间的得分.该得分由每个域上的得分线性组合而成,而每个域上的得分取布尔值:要么是0,要么是1.更具体地,给定一系列文档,假定每篇文档有L个域,其对应的权重分别是g1,...,gl (- [0, 1],他们满足
令si为查询和文档的第i个域匹配得分(1和0分别表示匹配上和没匹配上).例如,在AND查询下,如果所有查询词项都出现在某个域中,则这个域的对应得分为1,否则为0.
词项频率及权重计算
到目前为止,我们只考虑了词项在文档域中出现与否这两种情况.现在开始考虑词项频率,按常理如果文档或者域中词项出现的频率越高,那么该文档或者域的得分也越高
词项频率:词项t的词项频率是指词项t在文档d中出现的次数,记为:
,其中两个下标分别对应词项和文档
那么如何评价得分呢? 最简单的方式是直接根据term在文档中的出现次数(即原始词频tf),来对文档进行评分
然而,原始tf不太合适:某个词项在A文档中出现10次,即tf=10,在B文档中出现1次,tf=1,那么A比B更相关,但是相关度不会相差10倍.相关度不会正比于词项频率
一种替代原始tf的方法:对数词频
公式中的数字1是为了平滑计算用的,对于tf值为1的情况,采用对数频率加1的方式平滑处理
另一种tf的变体计算公式:基于最大值的tf归一化
这种方法被称为增强型规范化tf, 其中的a是调节因子,过去经验值为0.5,新的研究表明取值为0.4效果更好.公式中的tf代表这个单词的实际词频数目,而MAX(tf)代表了文档中所有单词中出现次数最多的那个单词对应的词频数目.之所以要如此操作,主要对于长文档的一种抑制,因为如果文档较长,则长文档中所有单词的tf值会普遍比段文档的值高,但是这并不意味着长文档与查询更相关.用单词的实际词频除以文档中最高词频,等于将绝对的数值进行了规范化转换,公式的含义就转换为:同一个文档内单词之间的相对重要性.
逆文档频率
原始的词项频率会面临这样一个严重的问题,即在和查询进行相关度计算时,所有的词项都被认为是同等重要的.
显然罕见词项比常见词项所蕴含的信息更多.因此在对搜索结果排序时,对于罕见词我们希望赋予高权重而对于常见词我们希望赋予低权重
引入因子文档频率(document frequency)df,它表示的是出现t的所有文档的数目
罕见词项比常见词项蕴含的信息更多,因此df是和词项t的信息量成反比的一个值.由于df本身往往较大,所以通常需要将它映射到一个较小的取值范围中去.为此, 假定所有文档的数目为N, 词项t的idf(inverse document frequency, 逆文本频率)的定义如下:
idf是反映词项t的信息量的一个重要指标,一个罕见词的idf往往很高,而高频词的idf就可能较低.
idf对排序的影响:
- idf会影响至少包含2个词项的查询的文档排序结果.例如,在查询"arachnocentric line"中,idf权重计算方法会增加arachnocentric的相对权重,同时降低line的相对权重
- 对于单词项查询,idf对文档排序基本没有任何影响
tf-idf权重计算
对于每篇文档中的每个词项,可以将其tf和idf组合在一起形成最终的权重.tf-idf权重机制对文档d中的词项t赋予的权重如下:
换句话说,tf-idf按照如下的方式对文档d中词项t赋予权重:
- 当t只在少数几篇文档中出现多次时,权重取值最大(此时能够对这些文档提供最强的区分能力)
- 当t在一篇文档中出现次数很少,或者在很多文档中出现,权重取值次之(此时对最后的相关度计算作用不大)
- 如果t在所有的文档中都出现,那么权重取值最小
BM25算法浅析
了解了上述概念后,我们可以来看一下BM25算法.BM25算法,通常用来作搜索相关性评分.一句话概括其主要思想:对Query进行语素解析,生成语素qi.然后,对于每个搜索结果D,计算每个qi与D的相关性得分,最后,对qi相对与D的相关性的分进行加权求和,从而得到Query与D的相关性得分.
语素(科普):语速是最小的语音,语义结体,是最小的有意义的基本单位
BM25算法的一般性公式如下:
其中:
- Q表示query
- qi表示Q解析之后的一个语速(对于中文而言,我们可以把对Query的分词作为语素分析,每个词看成语速qi)
- d表示一个搜索结果文档
- W表示语速qi的权重
- R(qi, d)表示语素qi与文档d的相关性得分
权重Wi
判断一个词与一个文档的相关性权重,方法有很多种,较常用的是idf,这里公式如下:
其中,N为索引中全部文档的数目,n(qi)为包含语素qi的文档数目
根据idf的定义可以看出,对于给定的文档集合,包含qi的文档数目越多,则qi的权重越低.也就是说,当很多文档都包含了qi时,qi的区分度就不高,因此使用qi来判断相关性时的重要度就较低.(举例:的这个词出现频率很高,但是所含的信息量很低)
相关性得分R(qi,d)
BM25中相关性得分的一般形式为:
其中:
其中:
- k1, k2, b为调节因子,通常根据经验设置,一般k1 = 2, b = 0.75
- fi为qi在d中出现频率,也就是词项频率,qfi为qi在Query中出现频率
- dl为文档d的长度,avgdl为所有文档的平均长度.由于绝大部分情况下,qi在Query中只会出现一次,因此qfi为1
综上所述,公式可以化简为:
从K的定义中可以看出,参数b的作用是调整文档长度对相关性影响的大小.b越大,文档长度对相关性得分的影响越大,反之越小.这可以理解为:当文档较长时,包含qi的机会越大.因此,同等fi情况下,长文档与qi的相关性应该比短文档与qi的相关性弱
参考链接
分享到:
相关推荐
中国科学院大学信息检索导论(李波)期末考试试题
基于向量空间模型的概念检索基于向量空间模型的概念检索基于向量空间模型的概念检索
含有2020年信息检索导论期末考试试题,2017信息检索导论作业及答案2016春国科大现代信息检索何苯期末试题(1),信息检索荷苯2015,信息检索荷苯2016,信息检索王斌2012 一、 选择题(单选, 每题 2 分,共 20 分) 1....
文档内容清晰,排版整齐,包含题目与答案,适用于正在学习信息检索导论这门课程的学生,用于掌握重点与查漏补缺,当然,每个老师的重点势必会不一样,所以该内容仅供参考,具体重点还是以自己老师为准。 此外,文中...
向量空间模型的构建 C++实现 VS2013上做的,绝对的好用
UCAS 信息检索导论大作业--新闻检索系统 目标:定向采集不少于4个中文社会新闻网站或频道,实现这些网站新闻信息的自动爬取、抽取、索引和检索。 具体要求: : 新闻网页数目不少于5万页,新闻信息能在一天之内...
基于N层向量空间模型的网络信息检索平台 基于N层向量空间模型的网络信息检索平台
基于倒排索引和向量空间模型的信息检索系统 倒排索引机制 倒排索引(Inversed index)的特点是不通过文档来寻找关键词,而是通过关键词来定位文档及它在文档中出现的具体位置, 它的工作原理就是通过建立索引和位置表...
基于结构化向量空间模型的中文信息检索系统研究与实现
现代信息检索导论_王斌译_课后习题答案
信息检索导论 2.pdf
以python语言为基础,利用向量空间模型,构建了倒排索引,并建立了邮件信息检索系统 以python语言为基础,利用向量空间模型,构建了倒排索引,并建立了邮件信息检索系统。选取的数据集来自安然公司150位用户50多万...
向量空间模型(VSM)的JAVA实现,从文档表示到相似度计算,使用两种相似度计算方式:cos和tf-idf算法
图 灵 计 算 机 科 学 丛 书信息检索导论人 民 邮 电 出 版 社北 京王 斌 译Christopher D. Manning[美][德]版 权 声 明I
第一章布尔检索习题 1-2考虑如下几篇文档:文档 1breakthrough drug for schizophrenia文档 2new schizophren
信息检索导论 中科院王斌老师ppt 可结合相关书籍进行学习
简单向量空间模型可用于文档相似度的计算,也可以用于检索信息,配有详细的注释
利用倒排索引和向量空间模型实现的信息检索系统. ## 完成工作: - 带位置信息的倒排索引 - 向量空间模型 - TOP K查询 - BOOL查询 - 短语查询 - 拼写矫正 - 同义词查询 - 拼写矫正(短语) # 运行 环境要求:python...
Introduction to Information__ Retrieval信息检索导论_引擎学习-课件信息检索 8.1 信息检索系统的评价 .8.2 标准测试集 .8.3 无序检索结果集合的评价 .8.4 有序检索结果的评价方法 .8.5 相关性判断 .8.6 系统质量及...
信息检索系统原理,空间向量模型,带域查询 实现空间向量模型,自定义域(诗名、作者、诗句)的查询