信息检索导论第六章--文档评分、词项权重计算及向量空间模型

#信息检索导论第六章–文档评分、词项权重计算及向量空间模型

布尔搜索与排序式检索

迄今为止,我们介绍了支持布尔查询的索引处理办法,给定一个布尔查询,一篇文档要么满足查询的要求要么不满足(布尔查询是一种非黑即白的处理方式)。因此对布尔查询常常会导致过少(=0)或者过多(>1000)的结果。因此要对搜索结果进行排序,那么如何设计排序算法呢?
前提:排序算法真的有效,即相关度大的文档结果会排在相关度小的文档结果之前
实现:对每个查询-文档对赋一个[0, 1]之间的分值,该分值度量了文档和查询的匹配程度。

一、Jaccard系数方法

集合重合度

对查询进行数学建模,采用jaccard系数计算两个集合重合度的,根据jaccard系数对搜索结果进行排序。
$$JACCARD(A,B)=\frac{|A\bigcap B|}{|A\bigcup B|}$$

实例:查询“ides of March”,文档“Caesar died in March”。集合A={ides of March},B={Caesar died in March},JACCARD(A, B) = 1/6

jaccard系数的不足:

  • 不考虑词项频率,即词项在文档中的出现次数。
  • 罕见词比高频词的信息量更大,Jaccard系数没有考虑这个信息。

二、文档评分、词项权重计算及向量空间模型方法

1、参数化索引及域索引

元数据:和文档有关的一些特定形式的数据。(如文档的作者、标题、出版日期等)。

:和字段类似,只是它的内容可以是任意的自有文本。字段的取值可能性比较小,域可以是由任意的、数目无限制的文本构成。通常,我们可以把文档的标题和摘要看成域。可以对文档的不同的域建立独立的倒排索引

目的:

  • 可以通过元数据(如文档的作者、标题、出版日期等)来对文档进行索引和检索。
  • 能够提供一个简单的文档评分方法。

词典方式处理(基本的域索引,每个域采用词典项的某种扩展表示方法)
在词典中,对不同域分别建立一个索引.同通常一样,查询的处理过程需要进行倒排记录表的合并操作(不同域下倒排索引的合并).

倒排记录方式处理(支持域加权评分技术的使用)
显然,对于查询,词典方式下域索引的处理要对多个索引进行合并处理,效率相对会比较低.因此考虑将域信息存储在倒排记录而不是词典中.

1.1、域加权评分

给定一个布尔查询q和一篇文档d,域加权评分方法给每个(q,d)对计算出一个[0,1]之间的得分.该得分由每个域上的得分线性组合而成,而每个域上的得分取布尔值:要么是0,要么是1.更具体地,给定一系列文档,假定每篇文档有L个域,其对应的权重分别是g1,…,gl (- [0, 1],他们满足$\sum_{i=1}^{l}g_{i}=1$

eg:一个文档集,其中每篇文章有三个域–author、title和body,对应的权重系数分别为g1=0.2、g2=0.3和g3=0.5,则如果查询shakespeare出现在某篇文档的title和body域,则文档最后总得分为0.8


1.2、权重学习

1.3、最优权重g的计算

没看太懂,到第15章结合机器学习的内容再回来看


2、词项频率及权重计算

词袋模型:文本被看作是无序的词汇集合,忽略语法甚至是单词的顺序。
词项频率tf:指词项t在文档d中出现的次数

2.1、采用tf来计算文档评分的方法:

第一种方法:采用原始的tf值

某个词项在A文档中出现10次,即tf=10,在B文档中出现1次,tf=1,那么A比B更相关,但是相关度不会相差10倍.相关度不会正比于词项频率

第二种方法:采用对数词频

文档-词项的匹配得分是所有同时出现在q和文档d中的词项的对数词频之和
$w_{t,d}=\begin{cases}1+log_{10}tf_{t,d}
& \text{ if } tf_{t,d} > 0\
0 & \text{ if } otherwise
\end{cases}$
公式中的数字1是为了平滑计算用的,对于tf值为1的情况,采用对数频率加1的方式平滑处理

另一种tf的变体计算公式:基于最大值的tf归一化

$ntf_{t,d}=a+(1-a)\frac{tf_{t,d}}{tf_{max}(d)}$
这种方法被称为增强型规范化tf,其中的a是调节因子,过去经验取值0.5,新的研究表明取值为0.4效果更好。公式中的tf代表这个单词的实际词频数目,而Max(tf)代表了文档中所有单词中出现次数最多的那个单词对应的词频数目。之所以要如此操作,主要对于对长文档的一种抑制,因为如果文档较长,则长文档中所有单词的tf值会普遍比短文档的值高,但是这并不意味这长文档与查询更相关。用单词实际词频除以文档中最高词频,等于将绝对的数值进行了规范化转换,公式的含义就转换为:同一个文档内单词之间的相对重要性。

2.2、逆文档频率

原始的词项频率会面临这样一个严重的问题,即在和查询进行相关度计算时,所有的词项都被认为是同等重要的。
显然罕见词项比常见词项所蕴含的信息更多.因此在对搜索结果排序时,对于罕见词我们希望赋予高权重而对于常见词我们希望赋予低权重。

文档频率df:指的是出现词项t的所有文档的数目

罕见词项比常见词项蕴含的信息更多,因此df是和词项t的信息量成反比的一个值.由于df本身往往较大,所以通常需要将它映射到一个较小的取值范围中去.为此, 假定所有文档的数目为N, 词项t的idf(inverse document frequency, 逆文本频率)的定义如下:
$$idf_{t}=logN/df_{t}$$
逆文档频率idf是反映词项t的信息量的一个重要指标,一个罕见词的idf往往很高,而高频词的idf就可能较低.

idf的计算样例:
N=1,000,000

idf对排序的影响:

  • idf 会影响至少包含2个词项的查询的文档排序结果
  • 对于单词项查询,idf对文档排序基本没有任何影响

    问题:idf的计算不应该是在查询之前完成吗,为什么这里会说查询会改变词项的相对权重?

2.3、td-idf权重计算

td-idf权重计算:词项的tf-idf权重是tf权重和idf权重的乘积
$w_{t,d}=(1+logtf_{t,d})log\frac{N}{df_{t}}$

tf-idf权重

  • 随着词项频率的增大而增大
  • 随着词项罕见度的增加而增大

采用tf-idf来计算文档评分的方法:

  1. 当t只在少数几篇文档中多次出现时,权重取值最大(此时能够对这些文档提供最强的区分能力);
  2. 当t在一篇文档中出现次数很少,或者在很多文档中出现,权重取值次之(此时对最后的相关度计算作用不大) ;
  3. 如果t在所有文档中都出现,那么权重取值最小。

引申:在有了tf-idf权重计算之后,一个自然的数学建模的想法是:tf-idf权重矩阵

3、向量空间模型

向量空间模型:把文档看成是一个向量,其中的每个分量都对应词典中的一个词项,分量值为采用tf-idf计算出的权重值。当某词项在文档中没有出现时,其对应的分量值为0。
于是,我们有一个|V|维实值空间,空间的每一维都对应词项(V为词项数目)。

对于Web搜索引擎,空间可能会上千万维。但对每个向量来说又非常稀疏(稀疏矩阵),大部分都是0。

有了向量空间模型后,那么如何对查询进行评分呢?
关键思想:将查询也看成一篇极短的文档来处理,即将查询表示成同一高维空间的向量。因此,可以通过计算给定的查询向量和每个文档向量的相似度来对所有文档进行排名。
于是评分问题转变为:在向量空间下, 如何对两篇文档的相似度进行计算?

3.1、相似度计算方法

方法1. 差向量法:采用两个文档向量差向量的大小(即欧式距离)进行计算。

但是这种计算方法有一个缺点:两篇内容相似的文档向量的差向量可能很大,这是因为一篇文档可能比另一篇文档要长得多。
假想实验:将文档d 复制一份加在自身末尾得到文档d′,则d′是d的两倍。很显然,从语义上看,d 和d′具有相同的内容,代表它们之间具有最大的相似度,而两者之间的夹角为0,但是,它们的欧氏距离可能会很大。

方法2. 余弦相似度法(cosine similarity)采用两个文档向量夹角的余弦值进行计算

验证夹角大小与余弦大小的等价性
在区间[0◦, 180◦]上,余弦函数cosine是一个单调递减函数

为了弥补文档长度给上述相似度计算所带来的负面效果, 计算两篇文档 d1和 d2相似度的常规方法是计算两文档向量的余弦相似度$sim(d_{1},d_{2})=\frac{\overrightarrow{V}(d_{1})\cdot \overrightarrow{V}(d_{2})}{|\overrightarrow{V}(d_{1})|\cdot |\overrightarrow{V}(d_{2})|}$
公式中除以分母的效果实际上相当于将向量进行长度归一化(称为欧氏归一化),得到单位向量。因此公式可以重写为:$sim(d_{1},d_{2})=\overrightarrow{v}(d_{1})\cdot \overrightarrow{v}(d_{2})$
其中:$\overrightarrow{v}(d_{1})=\frac{\overrightarrow{V}(d_{1})}{|\overrightarrow{V}(d_{1})|}$, $\overrightarrow{v}(d_{2})=\frac{\overrightarrow{V}(d_{2})}{|\overrightarrow{V}(d_{2})|}$

问题:既然归一化后的向量权重都处于同一数量级,那是否解决了差向量法弊端?

3.2、向量空间模型相似度计算

向量相似度计算过程:

  1. 将查询表示成tf‐idf权重向量
  2. 将每篇文档表示成同一空间下的tf‐idf权重向量
  3. 计算两个向量之间的某种相似度(如余弦相似度)
  4. 按照相似度大小将文档排序
  5. 将前K(如K =10)篇文档返回给用户

余弦相似度计算算法:

1
2
3
4
5
6
7
8
9
10
11
CosineScore(q)
float Scores[0]=0
Initialize Length[N]
for each query term t
do calculate w_tq and fetch posting list for t
for each pair(d,tf_td) in postings list
do Scores[d] += wf_td*w_tq
Read the array Length[d]
for each d
do Scores[d] = Scores[d]/Length[d]
return Top K components of Scores[]

基于原始tf值实例计算过程:

  1. 列出tf矩阵
  2. 计算出对数词频
  3. 对数词频进行余弦归一化后的权重矩阵

    sim(SaS,PaP) ≈ 0.789 ∗ 0.832 + 0.515 ∗ 0.555 + 0.335 ∗ 0.0 + 0.0 ∗ 0.0 ≈ 0.94.
    sim(SaS,WH) ≈ 0.79
    sim(PaP,WH) ≈ 0.69
    sim(SaS,PaP) > sim(SAS,WH) > sim(PaP,WH)

余弦相似度的问题
余弦归一化倾向于短文档,即对短文档产生的归一化因子太大,而平均而言对长文档产生的归一化因子太小。特别是对那些包含多个不同主题的文档,而查询词项可能只能和文档的部分内容相匹配。这时文档中词项的相对权重,就会和一篇与查询相匹配的短文档迥然不同。

于是我们要找到一种方法:对短文档的相似度降低,而长文档的相似度增大,去除原来余弦归一化偏向短文档的问题。
Amit Singhal的著名论文Pivoted Document Length Normalization提出了一种回转归一化的处理方法。
论文地址:http://ir.iit.edu/~dagr/cs529/files/handouts/singhal96pivoted.pdf

3.3、文档权重和查询权重计算的三要素

对于查询和文档常常采用不同的权重计算机制,记法: ddd.qqq

例如: lnc.ltn
文档: 对数tf,无idf因子,余弦长度归一化
查询: 对数tf,idf,无归一化