| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Вероятностный алгоритм поиска k ближайших соседей |
| Автор: fandorin 12.12.2012, 10:14 |
| Добрый день, есть необходимость найти эффективный вероятностный алгоритм поиска k ближайших соседей. Рассматриваем точки в 3-мерном пространстве, в качестве расстояния берем Евклидову метрику. На данный момент я нашел следующие алгоритмы: random projection kd-trees, GNNS, LSH, randomized kd-tree. Возможно, что кто-то сможет посоветовать другие. Нужно улучшить оценку O(nlogn). Заранее спасибо за ваши ответы. |
| Автор: mrgloom 12.12.2012, 15:24 |
| эффективный то по точности или по времени? на самом деле я ответа не знаю, но мне эта тематика тоже интересна. из готовых библиотек ANN http://www.cs.umd.edu/~mount/ANN/ сейчас её использую для 2D(использую для radius search,) напрягает только старый интерфейс и еще то, что даже если ищешь точно, то выдает неточные результаты, там в мануале вроде бы про это что то даже написано, но я так и не понял с чем это связано. FLANN http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN пробовал ту что встроена в opencv, там не было radius search и я забил. а вообще выглядит более свежо. STANN https://sites.google.com/a/compgeom.com/stann/Home |
| Автор: fandorin 12.12.2012, 15:53 |
| Эффективный по времени. ANN http://www.cs.umd.edu/~mount/ANN/ - я так понимаю здесь не используются вероятностные алгоритмы. Получается оценка поиска соседей для одной частицы по времени порядка O(logn). FLANN http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN - здесь смысл в выборе подходящего алгоритма по входным данным, там упоминается интересный алгоритм Randomized kd-trees (его оценка O(klog(n/k)), где k - количество kd-tree, число которых обычно делают степенью 2) STANN https://sites.google.com/a/compgeom.com/stann/Home - не понял, какой алгоритм используется внутри, вы не знаете? Я думаю, что можно попробовать понизить оценку с помощью модификаций алгоритмов GNNS и LSH, вы с этими алгоритмами не сталкивались? Интересная статья http://yury.name/algoweb/05algoweb.pdf, пытаюсь разобраться в сложности поиска. |
| Автор: fandorin 12.12.2012, 16:15 |
| Согласно статье http://yury.name/algoweb/05algoweb.pdf сложность поиска получается порядка O(n^ro), где ro < 1, но тогда выходит асимптотика даже хуже получается, либо я что-то не так понял. |
| Автор: mrgloom 12.12.2012, 16:21 |
| что такое GNNS вообще не нашел, а LSH помоему не выдает K ближайших, а просто группирует несколько в одну ячейку типа кластеризации. |
| Автор: fandorin 12.12.2012, 16:28 |
| GNNS - http://webdocs.cs.ualberta.ca/~zhang/GNNS.pdf, подход основан на построении k-NN графа. В LSH мы получаем ячейку, они это называют списком кандидатов, а затем бежим по списку и уже точно вычисляем k соседей. |