Lucene相似度

2019-05-05 本文已影响0人 KhaosYang

Lucene的查询过程是：首先在词典中查找每个Term，根据Term获得每个Term所存在的文档链表；然后根据查询条件对链表做交、并、差等操作，链表合并后的结果集就是我们要查找的数据，查询出来的数据和我们的查询条件的关系是什么，其文本相似度是多少呢？因此本文介绍Lucene最经典的两个文本相似度算法：

基于向量空间模型的算法
基于概率的算法（BM25）

好处

避免对关系型数据库进行全表扫描，可以大大提升查询效率。

1．文本相似度的主要影响因子

文本相似度的主要影响因子如下：

词频 tf（term frequency）：指某个词在文档中出现的次数，其值越大，就可认为这篇文章描述的内容与该词越相近，相似度得分就越高。
在Lucene中的计算公式为：

TF（ t表示Term，d表示文档）

逆文本频率 df（inverse document frequency）：这是一个逆向的指标，表示在整个文档集合中包含某个词的文档数量越少，这个词便越重要。
公式为：

idf(t) = 1+Log（ docCount/（docFreq+1））

其中，docCount表示索引中的文档总数，docFreq表示包含Term t的文档数，分母中docFreq+1是为了防止分母为0。

Length：这也是一个逆向的指标，表示在同等条件下，搜索词所在文档的长度越长，搜索词和文档的相似度就越低；文档的长度越短，相似度就越高。例如“lucene”出现在一篇包含10个字的文档中和一篇包含10000个字的文档中，那么我们可以认为10个字的那篇文章与“lucene”更相关。

Lucene为了更好地调节相似度得分，增加了以下几种boost值。

term boost：查询在语句中每个词的权重，可以在查询中设定某些词更重要。
document boost：文档的权重，在创建索引时设置某些文档比其他文档更重要。比如我国某大型搜索引擎网站可以将其域名下网站的boost值设置得比其他网站的大一些，当有查询过来时，其域名下的网站就会有更好的排名。
field boost：域的权重，就是字段的权重，表明某些字段比其他字段更重要。比如，在有标题和正文的网站中，命中标题要比命中正文重要得多。
query boost：查询条件的权重，在复合查询时使用，这种用法不常见。

2．基于向量空间模型

向量空间模型（Vector SpaceModel，VSM）的主要思路是把文本信息映射到空间向量中，形成文本信息和向量数据的映射关系，然后通过计算几个或者多个不同的向量的差异，来计算文本的相似度。

如图1所示有两个文本query和document，在query中包含两个Term 1和1个Term 2，在document中包含1个Term 1和4个Term 2。

图1 二维VSM

根据每个Term在每个文本中出现的次数，我们可以把文本信息映射到空间向量中，形成文本信息和向量数据的映射关系，也就是根据两个文档query和document生成query（以下简称q）和document（以下简称d）这两个向量，而向量q和向量d之间的夹角描述了它们之间的相似度，夹角越小就越相似，如果q和d完全相同，则其夹角为0。

图1 所示的是只有两个Term时的情形，但是一篇文档通常由很多Term组成，所以我们把二维的情形推广到N维也是可行的，两个向量之间的夹角依然可以表示两个文档的相似度，夹角越小就越相似，如图2所示。

图2 多维VSM

我们根据两个向量之间的夹角求两个文本的相似度，文本越相似，它们之间的夹角就越小，因为余弦的性质是夹角越小，余弦值越大。所以，我们可以把求两个文本相似度的问题转换为求两个向量余弦值的问题。余弦值的问题又可以通过点积的形式表示，根据向量余弦的公式可以得到如下公式：

其中，

score(q,d)表示向量q和d的相似度。
表示两个向量的夹角θ的余弦值。
所以向量q和向量d的夹角余弦的具体计算为：

其中，分母中的|V_q|表示向量q的模长，|V_d|表示向量d的模长；分子部分的V_q•V_d表示向量q和向量d的点积。

如果有两个向量A和B，其中向量A = (A₁,A₂,...,A_n)，B = (B₁,B₂,...,B_n)，则向量的模长就是把向量中的各个元素的平方相加再开根号，即

向量的点积就是将两个向量中的各个元素相乘再相加，即

文档是由词（Term）组成的，但是在一篇文章中各个词对这篇文章的贡献是不一样的，所以我们在做点积计算前先了解一下词权重。词权重用于描述一个词在一篇文章中的价值，常用的计算方法是tf * idf，它是一种非常优秀的思想，经常出现在文本处理的各个领域中。

因为无论是查询语句还是具体的文档，都是由多个Term组成的，所以查询向量和文档向量可以写成如下形式。

查询向量：V_q = < W (t₁, q),W (t₂, q), ……, W (t_n,q)>。
文档向量：V_d = < W (t₁, d),W (t₂, d), ……, W (t_n,d)>。

其中，W(t_i,q)表示t_i在query里的权重，W(t_i,d)表示t_i在doucument里的权重，W代表词的权重，公式为tf ×idf。

由向量乘积的公式可以得出：
V_q * V_d = W(t₁,q)×W(t₁, d) + …… +W(t_n,q)×W(t_n, d)

由于W=tf * * idf，所以可得出：
Vq * V_d=tf(t₁, q)×idf(t₁,q)×tf(t₁, d)×idf(t₁,d) + …… + tf(t_n* ,q)×idf(t_n,q)×tf(t_n, d) ×idf(t_n, d)

但是在查询时，我们很少会输入多个同样的查找词，所以这里可以假设tf(t_i, q)永远都等于1。

我们由idf的定义可知，idf表示的是一个全局的变量，所以一个Term无论是出现在query中，还是出现在document中，值是一样的，所以idf(t_i,d)= idf(t_i,q)=idf(t_i)。idf(t_i)表示t_i的idf值，它与具体出现在查询中还是文档中没有关系，它是索引文件中的一个全局数据。

因为有tf(t_i, q)=1和idf(t_i,d)= idf(t_i, q)=idf(t_i)，所以
V_q * V_d=tf(t₁, q)×idf(t₁,q)×tf(t₁, d)×idf(t₁,d) + …… + tf(t_n ,q)×idf(t_n,q)×tf(t_n,*** d)×idf(t_n,d*)

可以简化为：
V_q * V_d= tf(t₁, d)×idf(t₁)×idf(t₁)+ …… + tf(t_n, d)×idf(t_n)×idf(t_n)

公式

可以变为：

下面进行|V _q|的推理。因为tf(t_i,q)=1，所以推理如下：

接着进行|V_d|的推理。由向量模长的公式可得：

在Lucene的空间向量模型的实现类DefaultSimilarity中，认为在计算文档的向量模长时，每个Term的权重就不需要在考虑了，即w(t_i,d)=1，只考虑Term在文档的几个Field中出现。

所以向量d的模长公式|V_d|可以简化为：

基于空间向量模型的最终公式就是：

基于空间向量模型

在相似度打分公式中在加入boost后，公式变成：

image

其中，

coord(q,d) =hitTermNum/queryTermNum。hitTermNum是文档d中包含查询词的个数。queryTermNum是查询语句中包含的Term的个数。比如在文档“elastic is a good project”中检索“lucene elastic”，因为匹配了elastic，没有匹配lucene，所以hitTermNum=1，queryTermNum=2，coord(q,d)=1/2。
queryNorm是在|V_q|的基础上添加了query Boost和term boost：