annoy 源码阅读 (近似最近邻搜索 ANN)_KIDGIN7439的专栏-CSDN博客_annoy

最近工作中使用了一下annoy，于是抽时间看了下代码，记录下。。

annoy支持三种距离度量方式，cos距离，欧式距离和曼哈顿距离。下面主要通过最简单的欧氏距离来看。

首先看下节点node的结构

n_descendants记录了该节点下子节点的个数，children[2]记录了左右子树，v和a之后会详细说，先知道v[1]代表该节点对应的向量，a代表偏移就好。

然后看下AnnoyIndex类

_n_items记录了我们一共有多少个向量需要构建索引，_n_nodes记录了一共有多少个节点，_s是node占有的空间大小，_f是向量的维度，_nodes所有节点，_roots是所有树的根节点。

annoy建树的时候当该区域内的节点数小于k的时候就不会再继续递归建树，之前疑惑怎么调整k这个参数，看完代码才发现没法调整，_K是一个定值，如果一个区域内的节点数小于_K的时候，这个节点就不再记录向量v，v的空间也用来记录节点的id。

另外还有一个比较奇怪的事情就是annoy为node开辟空间的方式。。比如我有三个item，建索引的时候id分别为3,6,10，那么annoy会开辟11个node空间，从0-10。。看下面这段代码就能明白

再接下来就是到了建树。annoy建树如下图，每次选择空间中的两个质心作为分割点，相当于kmeans过程，以使得两棵子树分割的尽量均匀以保证logn的检索复杂度。以垂直于过两点的直线的超平面来分割整个空间，然后在两个子空间内递归分割直到子空间最多只有k个点。如下图

然后看下创建分割面的过程，入参为当前空间的所有点nodes，维度f，随机函数random，分割节点n

best_iv和best_jv就是选出来的那两个点，n->v存储的就是这两个点连线对应的向量，即分隔面的法向量，计算方式就是两点对应向量相减。n->a存储的就是分割超平面对应的偏移，以三维空间举例，三维空间中的平面表示方法为Ax + By + Cz + D = 0，n->a存储的就是这个D，计算方法如下，因为平面的法向量已经确定，又因为该平面过best_iv和best_jv连线中点，将中点坐标代入，连线中心点定义为m=((best_iv[0] + best_jv[0])/2, (best_iv[1] + best_jv[1])/2, (best_iv[2] +best_jv[2])/2)，则A m[0] + B m[1] + C m[2] + D =0  => D= -(A m[0] +B m[1] + C m[2])。

接下来看一下是如何选择两个点的，即two_means

为了保证nlogn的检索复杂度，需要使得每次分割得到的两棵子树尽量平衡，所以要找空间中的两个质心，过程很像kmeans，初始随机选取两个点，每次迭代过程中随机选择一个点计算该点属于哪个子树，并更新对应的质心坐标。

建树完成之后就是检索，对于给定的点去树中找topk近邻，最基本的想法就是从根开始，根据该点的向量信息和每个树节点的分割超平面比较决定去哪个子树遍历。如图所示

但是这样还是存在一些问题，就是最近邻不一定会和查询点在同一个叶结点上

解决方法是这样的，一是建立多棵树，二是在查询点遍历树的时候不一定只选择一条路径，这两个方法对应两个参数treenum和searchnum，如图所示

遍历过程中用优先队列维护候选集合，将所有树的结果去重维护到优先队列中，最后对这些候选集合计算距离并返回topk

首先看两个小函数，这是在树上遍历的时候计算点到超平面的距离并确定在哪棵子树的函数，点到平面的距离函数为

因为每个树节点中的超平面向量已经被归一化到1了，所以只需计算分子即可。

然后看下检索函数，

nns是候选集合，search_k即前面提到的search_num

首先是将所有树的根节点压入优先队列中，每次取出优先队列的头结点进行遍历，如果头结点为叶结点，则将该树节点对应的所有点加入到nns中，如果是非叶结点，则将两棵子树都加入到优先队列中，以此循环遍历直到nns中节点超过searchnum，最后对nns中的id去重后计算距离返回。

最后说下遇到的另一个问题，我们度量距离的方式为向量内积，内积并不能使用lsh方法来计算最近邻，为了解决这个问题，我们将内积距离转换为了cos距离，具体做法为在建立索引时，将所有向量的每一维除以c，c设置为所有向量中最大的模长，并将所有向量增加一维，设置为1减去其他维的平方的和再开根。这样就可以把cos距离中的分母消去了索引向量模长，而检索向量的模长并不会影响排序。

参考：

http://blog.csdn.net/hero_fantao/article/details/70245387

annoy作者的ppt

原网址: 访问
创建于: 2021-10-20 10:40:52
目录: default
标签: 无

未标明原创文章均为采集，版权归作者所有，转载无需和我联系，请注明原出处，南摩阿彌陀佛，知识，不只知道，要得到

请先后发表评论
  • 最新评论
  • 总共0条评论