K-最近邻 C/C++ 实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13488497/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
K-nearest neighbour C/C++ implementation
提问by alexsardan
Where can I find an serial C/C++ implementation of the k-nearest neighbour algorithm?
Do you know of any library that has this?
I have found openCV but the implementation is already parallel.
I want to start from a serial implementation and parallelize it with pthreads openMP and MPI.
在哪里可以找到 k 最近邻算法的串行 C/C++ 实现？
你知道任何图书馆有这个吗？
我找到了 openCV，但实现已经是并行的。
我想从串行实现开始，并使用 pthreads openMP 和 MPI 对其进行并行化。
Thanks,
Alex
谢谢，
亚历克斯
采纳答案by incrediblehulk
How about ANN? http://www.cs.umd.edu/~mount/ANN/. I have once used the kdtree implementation, but there are other options.
安呢？http://www.cs.umd.edu/~mount/ANN/。我曾经使用过 kdtree 实现，但还有其他选择。
Quoting from the website: "ANN is a library written in C++, which supports data structures and algorithms for both exact and approximate nearest neighbor searching in arbitrarily high dimensions."
引自网站：“ANN 是一个用 C++ 编写的库，它支持在任意高维度上进行精确和近似最近邻搜索的数据结构和算法。”
回答by gvd
I wrote a C++ implementation for a KD-treewith nearest neighbor search. You can easily extend it for K-nearest neighbors by adding a priority queue.
我为具有最近邻搜索的 KD 树编写了一个C++ 实现。您可以通过添加优先级队列轻松地将其扩展为 K-最近邻居。
Update:I added support for k-nearest neighbor search in N dimensions
更新：我添加了对 N 维 k-最近邻搜索的支持
回答by relaxxx
The simplest way to implement this is to loop through all elements and store K nearest. (just comparing). Complexity of this is O(n)which is not so good but no preprocessing is needed. So now really depends on your application. You should use some spatial index to partition area where you search for knn. For some application grid based spatial structure is just fine (just divide your world into fixed block and search only within closes blocks first). This is good when your entities are evenly distributed. Better approach is to use some hierarchical structure like kd-tree... It really all depends on what you need
实现这一点的最简单方法是循环遍历所有元素并最近存储 K。（只是比较）。这样做的复杂性O(n)不是很好，但不需要预处理。所以现在真的取决于你的应用程序。您应该使用一些空间索引来划分您搜索 knn 的区域。对于某些基于网格的应用程序空间结构就好了（只需将您的世界划分为固定块，然后仅在关闭的块内搜索）。当您的实体均匀分布时，这很好。更好的方法是使用一些像 kd-tree 这样的层次结构......这完全取决于你需要什么
for more information including pseudocode look in these presentations:
有关包括伪代码在内的更多信息，请查看这些演示文稿：
http://www.ulozto.net/xCTidts/dpg06-pdf
http://www.ulozto.net/xCTidts/dpg06-pdf
