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之间的夹角描述了它们之间的相似度,夹角越小就越相似,如果qd完全相同,则其夹角为0。

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

图2 多维VSM

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

其中,

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

其中,分母中的|Vq|表示向量q的模长,|Vd|表示向量d的模长;分子部分的Vq•Vd表示向量q和向量d的点积。

如果有两个向量AB,其中向量A = (A1,A2,...,An),B = (B1,B2,...,Bn),则向量的模长就是把向量中的各个元素的平方相加再开根号,即

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


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

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

  • 查询向量:Vq = < W (t1, q),W (t2, q), ……, W (tn,q)>。
  • 文档向量:Vd = < W (t1, d),W (t2, d), ……, W (tn,d)>。

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

由向量乘积的公式可以得出:
Vq * Vd = W(t1,qW(t1, d) + …… +W(tn,qW(tn, d)

由于W=tf * * idf,所以可得出:
Vq * Vd=
tf(t1, qidf(t1,qtf(t1, didf(t1,d) + …… + tf(tn* ,qidf(tn,qtf(tn, d) ×idf(tn, d)

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

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

因为有tf(ti, q)=1和idf(ti,d)= idf(ti, q)=idf(ti),所以
Vq * Vd=tf(t1, qidf(t1,qtf(t1, didf(t1,d) + …… + tf(tn ,qidf(tn,qtf(tn,*** didf(tn,d*)

可以简化为:
Vq * Vd= tf(t1, didf(t1idf(t1)+ …… + tf(tn, didf(tnidf(tn)

公式


可以变为:


下面进行|V q|的推理。因为tf(ti,q)=1,所以推理如下:

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

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

所以向量d的模长公式|Vd|可以简化为:

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

基于空间向量模型

在相似度打分公式中在加入boost后,公式变成:

image

其中,

  • coord(q,d) =hitTermNum/queryTermNumhitTermNum是文档d中包含查询词的个数。queryTermNum是查询语句中包含的Term的个数。比如在文档“elastic is a good project”中检索“lucene elastic”,因为匹配了elastic,没有匹配lucene,所以hitTermNum=1,queryTermNum=2,coord(q,d)=1/2。

  • queryNorm是在|Vq|的基础上添加了query Boostterm boost

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

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

3.基于概率的模型

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

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

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

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

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

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

其中Wi的值是一个词的idf值,公式如下,这个公式是由BIM模型推理得出的:

image

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

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

image

其中

image

fi表示第i个词在文档中出现的次数(类似于空间向量模型里的TF),qfi表示第i个词在查询语句出现的次数。

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

最终,BM25算法的公式如下:


BM25算法

对其中的参数说明如下:

  • IDF(qi):词的重要程度和其出现在文档中的数量成反比,包含该词的文档数越多,idf值就越小。
  • fifi表示第i个词在文档中出现的次数,fi的值越大,得分就越高。
  • dl:表示文档的长度,文档越长,得分就越低
  • avgdl:表示文档的平均长度,随着索引的增、删、改,这个值是实时变化的。
  • k1:表示调节因子,调节词频对得分的影响,k1越大,表示词频对得分的影响越大,在k1=0的极限情况下,词频特征失效。默认值为1.2。
  • b:表示调节因子,调节字段长度对得分的影响,b越大,表示对文档长度的惩罚越大,在k=0的极限情况下,忽略文档长度的影响。默认值为0.75。
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 217,826评论 6 506
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,968评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 164,234评论 0 354
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,562评论 1 293
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,611评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,482评论 1 302
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,271评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,166评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,608评论 1 314
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,814评论 3 336
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,926评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,644评论 5 346
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,249评论 3 329
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,866评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,991评论 1 269
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,063评论 3 370
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,871评论 2 354

推荐阅读更多精彩内容