ElasticSearch系列笔记(2)-ElasticSearch 理论基础

本节主要介绍下ElasticSearch 理论基础。知其然知其所以然，如下的理论和算法，就是ElasticSearch的魂！

搜索引擎结果的好坏与否，体现在业界所称的在相关性（Relevance）上。相关性的定义包括狭义和广义两方面，狭义的解释是：检索结果和用户查询的相关程度。而从广义的层面，相关性可以理解为为用户查询的综合满意度。直观的来看，从用户进入搜索框的那一刻起，到需求获得满足为止，这之间经历的过程越顺畅，越便捷，搜索相关性就越好。

为了达到这个目的，各个搜索引擎都在不断的优化搜索质量，即提高搜索相关性。本文主要阐述了ElasticSearch中经典的算法模型。

倒排索引（Inverted index）

概念

倒排索引（Inverted index），也常被称为反向索引、置入档案或反向档案，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：“单词词典”和“倒排文件”。

举个例子

有四个文档（document）

doc1:中国美丽

doc2:中国黄河美丽

doc3:中国长江美丽

doc4:中国北京首都

经过分词，倒排之后，生成的索引（index）文件如表格所示：

词	文档集合	数量
中国	1,2,3,4	4
美丽	1,2,3	3
黄河	2	1
长江	3	1
首都	4	1

这种数据结构下，用户输入一个query词“美丽”，就会很快定位到文档1，2，3。

TF/IDF算法（term frequency–inverse document frequency）

理论依据

tf-idf算法是创建在这样一个假设之上的：对区别文档最有意义的词语应该是那些在文档中出现频率高，而在整个文档集合的其他文档中出现频率少的词语，所以如果特征空间坐标系取 tf 词频作为测度，就可以体现同类文本的特点。另外考虑到单词区别不同类别的能力，tf-idf法认为一个单词出现的文本频数越小，它区别不同类别文本的能力就越大。因此引入了逆文本频度idf的概念，以tf和idf的乘积作为特征空间坐标系的取值测度，并用它完成对权值tf的调整，调整权值的目的在于突出重要单词，抑制次要单词。但是在本质上idf是一种试图抑制噪声的加权，并且单纯地认为文本频率小的单词就越重要，文本频率大的单词就越无用，显然这并不是完全正确的。idf的简单结构并不能有效地反映单词的重要程度和特征词的分布情况，使其无法很好地完成对权值调整的功能，所以tf-idf法的精度并不是很高。此外，在tf-idf算法中并没有体现出单词的位置信息。
虽然TF/IDF存在的问题不少，但是它简单又高效。能够召回高质量的搜索结果。同时Elasticsearch 还有其他模型，如 Okapi-BM25。

数学表达

词频（term frequency，tf）：在一份给定的文件里，词频（term frequency，tf）指的是某一个给定的词语在该文件中出现的频率。这个数字是对词数（term count）的归一化，以防止它偏向长的文件。（同一个词语在长文件里可能会比短文件有更高的词数，而不管该词语重要与否。）对于在某一特定文件里的词语 $ti$ 来说，它的重要性可表示为：
$$tf_i,_j=\frac{n_i,_j}{\sum_{k}n_k,_j}$$

以上式子中$n_i,_j$是该词在文件$d_j$中的出现次数，而分母则是在文件$d_j$中所有字词的出现次数之和。


逆向文档频率（inverse document frequency，idf）：是一个词语普遍重要性的度量。某一特定词语的idf，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取以10为底的对数得到：
$$idf_i=lg\frac{|D|}{|1+j:t_i \in d_j|}$$
       其中

       $|D|$：语料库中的文件总数

       $|1 + j:t_i \in d_j|$：语料库中的文件总数

包含词语 $t_i$ 的文件数目（即 $n_i,_j\neq 0$的文件数目）如果词语不在数据中，就导致分母为零，因此一般情况下使用$|1+j:t_i \in d_j|$

然后
$$tfidf_i,_j = tf_i,_j \times idf_i$$

某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的tf-idf。

举个栗子

假如一篇文件的总词语数是100个，而词语“母牛”出现了3次，那么“母牛”一词在该文件中的词频就是3/100=0.03。而计算文件频率（IDF）的方法是以文件集的文件总数，除以出现“母牛”一词的文件数。所以，如果“母牛”一词在1,000份文件出现过，而文件总数是10,000,000份的话，其逆向文件频率就是lg(10,000,000/1,000)=4。最后的tf-idf的分数为0.03*4=0.12。

布尔模型（Boolean Model）

布尔模型是基于集合论和布尔代数的一种简单检索模型，是早期搜索引擎所使用的检索模型。它的特点是查找那些对于某个查询词返回为“真”的文档。在该模型中，一个查询词就是一个布尔表达式，包括关键词以及逻辑运算符：与（AND）,或（OR）,非（NOT）。

布尔模型的优点是简单且迅速，非常适合召回数据。再对召回的数据作相关性排序之后，返回最终的结果。

举个栗子

基于倒排索引中的4个文档，使用布尔模型，查询包含“中国和首都”的文档，则相当于中国 AND 首都，只会检索出doc4文档。如果查询包含“中国和（长江或黄河）”，相当于中国 AND (长江 OR 黄河)，会查询出doc2，和doc3。

向量空间模型（Vector Space Model，VSM）

向量空间模型是一个把文本文件表示为标识符（比如索引）向量的代数模型。它应用于信息过滤、信息检索、索引以及相关排序。

定义

文档和查询都用向量来表示。

$$d_j=(w_1,_j,w_2,_j,…,w_t,_j)$$
$$q=(w_1,_q,w_2,_q,…,w_t,_q)$$
每一维都对应于一个个别的词组。如果某个词组出现在了文档中，那它在向量中的值就非零。已经发展出了不少的方法来计算这些值，这些值叫做（词组）权重。其中一种最为知名的方式是tf-idf权重。词组的定义按不同应用而定。典型的词组就是一个单一的词、关键词、或者较长的短语。如果将词语选为词组，那么向量的维数就是词汇表中的词语个数（出现在语料库中的不同词语的个数）。通过向量运算，可以对各文档和各查询作比较。

应用

据文档相似度理论的假设，如要在一次关键词查询中计算各文档间的相关排序，只需比较每个文档向量和原先查询向量（跟文档向量的类型是相同的）之间的角度偏差。

实际上，计算向量之间夹角的余弦比直接计算夹角本身要简单。

$$cos\theta = \frac{d_2.q}{\lVert d_2\lVert .\lVert q \lVert}$$

其中 $d_2.q$是文档向量（即右图中的d2）和查询向量（图中的q）的点乘。 $\lVert d_2 \lVert$是向量d2的模，而$\lVert q\lVert$是向量q的模。向量的模通过下面的公式来计算：
$$\lVert v \lVert = \sqrt{\sum_{k=1}^{n}v_i^2}$$
由于这个模型所考虑的所有向量都是每个元素严格非负的，因此如果余弦值为零，则表示查询向量和文档向量是正交的，即不符合（换句话说，就是检索项在文档中没有找到）。如果要了解详细的信息可以查看余弦相似性这条目。

Okapi BM25

能与 TF/IDF 和向量空间模型媲美的就是 Okapi BM25 ，它被认为是当今最先进的排序函数。 BM25 源自概率相关模型（probabilistic relevance model），而不是向量空间模型，但这个算法也和 Lucene 的实用评分函数有很多共通之处。

BM25 is a bag-of-words retrieval function that ranks a set of documents based on the query terms appearing in each document, regardless of the inter-relationship between the query terms within a document (e.g., their relative proximity). It is not a single function, but actually a whole family of scoring functions, with slightly different components and parameters. One of the most prominent instantiations of the function is as follows.

Given a query $Q$, containing keywords $ q_1,…,q_n$, the BM25 score of a document $D$ is:
$$score(D,Q) = \sum_{i=1}^{n}IDF(q_i).\frac{f(q_i,D).(k_1+1)}{f(q_i,D).(1-b+b.\frac{\lvert D \lvert}{avgd1})}$$
where $f(q_i,D)$ is $q_i$’s term frequency in the document $D$, $\lvert D\lvert$ is the length of the document $D$ in words, and avgdl is the average document length in the text collection from which documents are drawn. $k_1$ and $b$ are free parameters, usually chosen, in absence of an advanced optimization, as $k_1 \in[1.2,2.0]$ and $b=0.75$.$IDF(q_i)$is the IDF (inverse document frequency) weight of the query term $q_i$. It is usually computed as:
$$IDF(q_i)=log\frac{N-n(q_i)+0.5}{n(q_i)+0.5}$$
where $N$ is the total number of documents in the collection, and $n(q_i)$ is the number of documents containing $q_i$.

There are several interpretations for IDF and slight variations on its formula. In the original BM25 derivation, the IDF component is derived from the Binary Independence Model.

Please note that the above formula for IDF shows potentially major drawbacks when using it for terms appearing in more than half of the corpus documents. These terms’ IDF is negative, so for any two almost-identical documents, one which contains the term and one which does not contain it, the latter will possibly get a larger score. This means that terms appearing in more than half of the corpus will provide negative contributions to the final document score. This is often an undesirable behavior, so many real-world applications would deal with this IDF formula in a different way:

Each summand can be given a floor of 0, to trim out common terms;
The IDF function can be given a floor of a constant $\epsilon$ , to avoid common terms being ignored at all;
The IDF function can be replaced with a similarly shaped one which is non-negative, or strictly positive to avoid terms being ignored at all.

不像 TF/IDF ，BM25 有一个比较好的特性就是它提供了两个可调参数：

k1

这个参数控制着词频结果在词频饱和度中的上升速度。默认值为 1.2 。值越小饱和度变化越快，值越大饱和度变化越慢。

b

这个参数控制着字段长归一值所起的作用， 0.0 会禁用归一化， 1.0 会启用完全归一化。默认值为 0.75 。
在实践中，调试 BM25 是另外一回事， k1 和 b 的默认值适用于绝大多数文档集合，但最优值还是会因为文档集不同而有所区别，为了找到文档集合的最优值，就必须对参数进行反复修改验证。