Lucene相似度

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：

image

• norm(t,d)的计算公式为

空间向量模型是一种很优秀的思路，也是Lucene早期版本默认的相似度算法模型，也在很多搜索项目中被用到。

3．基于概率的模型

BM25算法是根据BIM（Binary independentModel，二元独立模型）算法改进而来的，二元独立模型做了两个假设。

• 二元假设，指一个词和文档的关系只有两种：1，相关；2，不相关。不考虑其他因素。

• 词的独立性假设，指文档里词和词之间没有任何关联，任意一个词在文档中的分布概率不依赖于其他单词或者文档。

而BM25算法是在BIM算法的基础上添加了词的权重和两个经验参数，到目前为止是很优秀的排名算法。现在Elasticsearch默认的打分算法已经由原来的向量空间模型变成了BM25。

BM25的计算公式主要分为两大部分：W_i是第i个词的权重；R(q_i,d)是每个词和文档的相关度值，其中q_i代表查询语句中的第i个词，d代表相关的文档。

一个包含n个词的查询语句Q和文档d的BM25算法公式为：

其中W_i的值是一个词的idf值，公式如下，这个公式是由BIM模型推理得出的：

image

其中，N是文档的总数，n(q_i)是包含该词的文档数，0.5是为了避免n(q_i)为0，导致分母为零。

由公式可知n(q_i)越小，分子部分就越大，分母部分就越小，所以IDF值就越大，log用于让IDF的值受n(q_i)的影响更加平滑。该公式虽然与向量空间模型的idf算法不太一样，但同样体现了一个词的重要程度和其出现在文档中的数量成反比这一思想。

image

其中

image

f_i表示第i个词在文档中出现的次数（类似于空间向量模型里的TF），qf_i表示第i个词在查询语句出现的次数。

同向量空间模型中的思路一样，在一个查询语句中很少会有一个词出现多次，所以我们认为qf_i永远为1，这样qf_i（k2+1）/(qf_i+k2)就等于1了。

最终，BM25算法的公式如下：

BM25算法

对其中的参数说明如下：

• IDF(q_i)：词的重要程度和其出现在文档中的数量成反比，包含该词的文档数越多，idf值就越小。
• f_i：f_i表示第i个词在文档中出现的次数，f_i的值越大，得分就越高。
• dl：表示文档的长度，文档越长，得分就越低
• avgdl：表示文档的平均长度，随着索引的增、删、改，这个值是实时变化的。
• k₁：表示调节因子，调节词频对得分的影响，k₁越大，表示词频对得分的影响越大，在k₁=0的极限情况下，词频特征失效。默认值为1.2。
• b：表示调节因子，调节字段长度对得分的影响，b越大，表示对文档长度的惩罚越大，在k=0的极限情况下，忽略文档长度的影响。默认值为0.75。