ANN算法

ANN搜索：approximate nearest neighbor, 本质上是在很多稠密向量中，迅速找到目标点的临近点，并认为这认为是相似的节点，主要用于图像检索、高维检索。几乎所有的方法都是对空间进行切分，可以迅速找到子空间，并与子空间的数据进行计算。方法主要有基于树的方法、哈希方法、矢量量化、基于图的方法。

1. 基于树的方法

主要就是利用树的数据结构来表达对空间的划分，KD树是最经典的例子

1.1 KD树

KD树构建的过程就是迭代二分空间的过程

经典算法：选择方差最大的维度,计算中位数点，作为划分点，分为左右子树，迭代上述过程, 直到空间上的点小于阈值

选择方差最大的维度，便于切分空间，使得整个树的深度最小

随机KD树算法：区别与经典算法，主要是随机选择一个维度来切分，最终构造m个树(横看成岭侧成峰,不同角度来看空间点的树分布)

1.2 annoy

不断的用选取的两个质心的法平面对空间切分，最终将子空间的数据点控制在K以内，对于待插入样本X，从根节点ROOT使用法向量与X做内积运算判断在左子树还是右子树。构建多个树提高查询召回率

2. 哈希方法（局部敏感性哈希）

局部敏感：相近的样本点比相远的点更容易碰撞

加速查找：查找目标分在哪个桶中，只需要在桶中遍历比较

多表哈希：当哈希函数数目K取得太大，查询样本与其对应的最近邻分配到同一个桶的概率很小，建立多个表，增加召回率

LSH主要涉及到三个参数

K：每一个哈希表的哈希函数数目（空间划分)

L：哈希表的数目

T：近邻哈希桶的数目

3. 矢量量化方法

将一个向量空间中的点用其中的一个有限子集来编码的过程

4. 基于图的方法

4.1 NSW

可导航小世界(Nagigable Small World)

对于每个待插入新元素，我们从结构中找到其最近的邻居集合（近似的Delaunay图），该集合连接到元素，反复迭代此过程连通所有节点构成图，最开始连接的边因为随机性大概率是长距离边而不是短距离边，形成可导航的小世界

贪婪搜索算法如下：

1.计算从查询q到当前顶点的朋友列表的距离，然后选择具有最小距离的定点

2.如果查询q与所选顶点距离小于查询与当前元素之间的距离，则算法移动到所选顶点，并更新为当前顶点

3.算法迭代直到局部最小点停止: 一个顶点，其朋友列表不包含比顶点更接近于q的节点存在

NSW K-NN搜索算法如下：

K-NNSearch(object q, integer:m, k)

TreeSet [object] tempRes, candidates, visitedSet, result

//m次循环，避免随机性

for (i=0; i

put random entry point in candidates //随机选择搜索进入点

tempRes <- null

repeated:

//利用贪婪搜索算法找到距离q最近的点c

get element c closest from candidates to q

remove c from candidates

//最近的c距离比结果result里面的任何点距离目标点都要远,跳出循环

if c is further than k-th element from result then

break repeat

for every element e from friends of c; do:

if e is not in visitedSet then

add e to visitedSet, candidates, tempRes

end repeat

//一次循环结果, 把从本次随机选择的进入点选择到的最近临时节点加入到result中

add objects from tempRes to result

return best k elements from result

4.2 HNSW

分层的可导航小世界(Hierarchical Navigable Small World), NSW基础上引入跳表概念，加快搜索跳转速度

选边策略1: 节点q最近的N个邻居,按照距离选出M个作为邻居进行连接即可

选边策略2: 节点q最近的N个邻居，选出最近的节点，加入邻居队列，然后剩余的节点选出a进行判断，如果q到到a的距离大于所有的邻居节点到a的距离，则将q->a进行连接，因为q不能通过邻居节点更接近a,所以直接将q和a连接,建立一条高速公路

ANN算法的度量空间局限

需要对两者向量进行度量计算，一般就是cosine计算或者L2距离，计算函数较为单一，在搜索上和推荐上，不能完全适用，需要二者向量空间一致，反映到计算过程上，就是需要两个平行空间的映射关系，将不同空间的点映射到一起（见图a）

先表征计算，然后在做简单的向量匹配可能无法表达部分复杂的非线性计算，如一些深度模型的，实际例子中，譬如一个用户，可能喜欢两部类型差异完全不同的影片，那么不同差异很大的item很难映射到一起，而图b则是会对向量过神经网络复杂计算表征一些非线性很复杂的关系。图b这种向量匹配形式就很难在上述的KD-TREE, LSH方法中取得良好的效果，而基于图的方法经过改良是可以去完成的，甚至能计算表征维度不同向量的关系远近。

Previous

Gflag和glog在centos下的安装总结