简介

Vocabulary Tree，配合BoVW使用，提高检索速度。

综合转载以下文章：

构造词汇树

使用大量具有代表性的描述子矢量来进行树的无监督训练，在这里使用K-means聚类方法，不过$K$不是代表最终的聚类中心的数量，而是代表每一层的分类数。首先，对原始的训练数据进行K-means聚类，定义$K$个聚类中心。然后把训练数据按照聚类中心分为$K$个组，每个组的数据都有同样的聚类中心。然后同样的聚类过程应用到每个组中，把每个组再划分为$K$个组，不停地迭代，直到词汇树到达了预设的最大深度$L$。

在线搜索阶段，每个描述子只用按照跟训练相似的步骤逐层地寻找聚类中心，直到叶结点。

定义评分

在进行查询的时候，要计算查询图像和数据库图像的相似程度，这是通过比较查询图像和数据库图像的特征在词汇树中的分布相似程度衡量的。一个图像往往会有很多个特征。

基于熵为词汇树中的每个节点$i$分配权重$w_i$，然后根据分配的权重将查询特征向量$q_i$和数据库词汇向量$d_i$定义为

$q_i=n_iw_i \\ d_i = m_iw_i$

其中$n_i$和$m_i$分别是查询描述符向量和数据库图像的描述符向量中，通过节点$i$的数量。然后，基于查询和数据库向量之间的归一化差异，给数据库图像提供相关性得分$s$

$s(q,d)=||\frac{q}{||q||}-\frac{d}{||d||}||$

作者发现上式中 L1-模的效果会比 L2-模的效果要好。

在最简单的情况下，权重wi被设置为常数，但是通常通过熵权重来改善检索性能

$w_i=ln\frac{N}{N_i}$

其中$N$是数据库中图像的数量，$N_i$是数据库中具有至少一个通过节点$i$的描述符矢量路径的图像数。这导致TF-IDF方案。我们也尝试使用节点$i$的出现频率代替$N_i$，但似乎没有太大的区别。

倒排索引

搜索引擎通常检索的场景是：给定几个关键词，找出包含关键词的文档。怎么快速找到包含某个关键词的文档就成为搜索的关键。这里我们借助单词——文档矩阵模型，通过这个模型我们可以很方便知道某篇文档包含哪些关键词，某个关键词被哪些文档所包含。单词-文档矩阵的具体数据结构可以是倒排索引、签名文件、后缀树等。
倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件(inverted file)。倒排索引一般表示为一个关键词，然后是它的频度（出现的次数），位置（出现在哪一篇文章或网页中，及有关的日期，作者等信息），它相当于为互联网上几千亿页网页做了一个索引，好比一本书的目录、标签一般。读者想看哪一个主题相关的章节，直接根据目录即可找到相关的页面。不必再从书的第一页到最后一页，一页一页的查找。

倒排索引由两个部分组成：倒排文件和单词词典。

倒排文件

所有单词的倒排列表顺序的存储在磁盘的某个文件里，这个文件即被称为倒排文件，倒排文件是存储倒排索引的物理文件。

单词词典

单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。单词词典是倒排索引中非常重要的组成部分，它是用来维护文档集合中所有单词的相关信息，同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时，根据用户的查询词，去单词词典里查询，就能够获得相应的倒排列表。对于一个规模很大的文档集合来说，可能包含了几十万甚至上百万的不同单词，快速定位某个单词直接决定搜索的响应速度，所以我们需要很高效的数据结构对单词词典进行构建和查找。常用的数据结构包含哈希加链表和树形词典结构。

实现评分

知道什么是倒排索引之后，看看评分是怎么实现的。

为了有效地利用大型数据库，使用倒排索引。词汇表树中的每个节点都与一个倒排文件相关联。倒排文件存储特定节点出现的图像的id号，以及每个图像中出现的频率$m_i$。前向文件也可以作为补充，以便查找特定图像中出现的视觉词汇。在我们的实现中只有叶节点有真正的倒排文件，而内部节点的倒排文件只是叶节点的倒排文件的拼接。倒排文件的长度存储在词汇树的每个节点中。这个长度本质上是决定节点熵的文档频次。如上所述，超过一定长度的倒排文件会降低得分。

假设每个节点的熵是固定且已知的，这可以通过对特定数据库进行预计算来实现，也可以通过使用大型代表性数据库来确定熵。然后，可以预先计算表示数据库图像的向量，并将其规范化为单位大小，例如，当图像输入数据库时。同样，查询向量被归一化为单位大小。为了计算$L_p$范数的归一化差，可以使用这种方法

$\begin{align} ||\textbf{q}-\textbf{d}||_p^p &= \sum_i|q_i-d_i|^p \\ &= \sum_{i|d_i=0}|q_i|^p+\sum_{i|q_i=0}|d_i|^p+\sum_{i|q_i \neq 0,d_i \neq 0}|q_i-d_i|^p\\ &=||\textbf{q}||_p^p + ||\textbf{d}||_p^p+\sum_{i|q_i \neq 0,d_i \neq 0}(|q_i-d_i|^p - |q_i|^p - |d_i|^p) \\ &=2+\sum_{i|q_i \neq 0, d_i \neq 0}(|q_i-d_i|^p-|q_i|^p-|d_i|^p) \end{align}$

当上式用的是$L_2$范数时，能够再简化为

$\begin{align} ||\textbf{q}-\textbf{d}||_2^2 &=2+\sum_{i|q_i \neq 0, d_i \neq 0}(|q_i-d_i|^2-|q_i|^2-|d_i|^2) \\ & = 2 + \sum_{i|q_i \neq 0, d_i \neq 0}(|q_i|^2-2q_id_i+|d_i|^2-|q_i|^2-|d_i|^2) \\ & = 2 -2 \sum_{i|q_i \neq 0, d_i \neq 0}q_id_i \end{align}$

RexKing6's Note

词汇树Vocabulary Tree

简介