KNN和ANN
...大约 2 分钟
本文包含的内容：
- KNN问题，ANN问题，相关算法的分类
- 沃罗诺伊图 (Voronoi Diagram) 和德劳内图 (Delaunay Graph) 的基础知识，以及相关定理的证明
- MSNET (Monotonic Search Network) 的基础知识，以及相关定理的证明
- RNG (Relative Neighborhood Graph) 的基础知识
- MRNG (Monotonic Relative Neighborhood Graph) 的基础知识，以及相关定理的证明
- NSG (Navigating Spreading-out Graph) 的基础知识，以及相关定理的证明
本文不包含的内容：
- 如何使用代码实现一个KNN或者ANN算法
KNN问题
KNN (K Nearest Neighbor) 问题，也叫作K最近邻问题，是要在欧式空间中找到离给定点最近的K个点，在空间中每个点都以向量表示。之所以要说欧式空间，是为了简化后续的讨论，毕竟“近”这个词就意味着距离，而普通的向量空间是没有距离的概念的；另外，欧式空间并不意味着向量只能是三维，实际上可以是任意高维的。
解决KNN问题，最容易想到的方案就是暴力搜索，只需要计算给定点到其他每个点的距离，然后进行Top K排序就可以了。这种方案的优点是精准，找到的一定是最近的K个点；但缺点也是显而易见的，即耗时严重，尤其是在点的数量非常多，向量维数很高的时候，往往无法在实际生产环境中使用。
一般来说，精准找到K个最近邻往往代价很大，所以在实际应用中，KNN问题常常被弱化成ANN (Approximate Nearest Neighbor) 问题，即近似最近邻问题。相应的各种ANN算法，都是通过牺牲一定的精度来换取时间和空间上的优势。
在业界，ANN算法常常被分为四个大类：
- 基于树结构的
- 基于Hash的
- 基于量化 (Quantization) 的
- 基于图 (Graph) 的
目前一个普遍的看法是，基于图的算法一般要优于其它三种类型的算法，表现在查询的速度和召回率上面。
在基于图的ANN算法中，如何构造图的结构至关重要，更准确一些来说的话，是边的构造至关重要。在后面的章节中，本文会针对一些图算法和结构，例如Delaunay Graph，Monotonic Search Network，Relative Neighborhood Graphs等进行深入的探讨。
参考资料
理解近似最近邻 (ANN) 问题中的图算法：Voronoi Diagram，Delaunay Graph，MSNET，RNG，MRNG和NSG