K-ближайший сосед C / C ++ реализация
Где я могу найти последовательную реализацию C / C ++ алгоритма k-ближайшего соседа?
Знаете ли вы о какой-либо библиотеке, которая имеет это?
Я нашел openCV, но реализация уже параллельна.
Я хочу начать с последовательной реализации и распараллелить ее с pthreads openMP и MPI.
Спасибо,
Alex
Решение
Как насчет Энн? http://www.cs.umd.edu/~mount/ANN/. Я когда-то использовал реализацию kdtree, но есть и другие варианты.
Цитата с веб-сайта: «ANN — это библиотека, написанная на C ++, которая поддерживает структуры данных и алгоритмы как для точного, так и для приблизительного поиска ближайшего соседа в произвольно больших измерениях».
Другие решения
Я написал C ++ реализация для KD-дерева с поиском ближайшего соседа. Вы можете легко расширить его для K-ближайших соседей, добавив приоритетную очередь.
Обновить: Я добавил поддержку поиска ближайшего соседа в N измерениях
Самый простой способ реализовать это — перебрать все элементы и сохранить K ближайших. (просто сравнивая). Сложность этого O(n) что не очень хорошо, но никакой предварительной обработки не требуется. Так что теперь действительно зависит от вашего приложения. Вы должны использовать некоторый пространственный индекс для разбиения области, где вы ищете knn. Для некоторых приложений пространственная структура, основанная на сетке, — это просто замечательно (просто разделите ваш мир на фиксированные блоки и ищите только внутри закрытых блоков). Это хорошо, когда ваши сущности распределены равномерно. Лучше всего использовать некую иерархическую структуру, например, kd-tree … Все зависит от того, что вам нужно.
Для получения дополнительной информации, включая псевдокод, смотрите эти презентации: