Как найти ближайшие 2 точки в 100-мерном пространстве с 500000 точек?
У меня есть база данных с 500000 точек в 100-мерном пространстве, и я хочу найти ближайшие 2 точки. Как мне это сделать?
Обновление: Пространство евклидово, извините. И спасибо за все ответы. Кстати, это не домашнее задание.
5 ответов
Вы можете попробовать библиотеку ANN, но это дает надежные результаты только до 20 измерений.
Во введении к алгоритмам есть глава, посвященная поиску двух ближайших точек в двумерном пространстве за O(n*logn) времени. Вы можете проверить это на книгах Google. На самом деле, я предлагаю это всем, так как метод решения проблемы "разделяй и властвуй" очень прост, элегантен и впечатляет.
Хотя это не может быть расширено непосредственно к вашей проблеме (как постоянная 7 будет заменен на 2^101 - 1), это должно быть хорошо для большинства наборов данных. Итак, если у вас есть достаточно случайный ввод, он даст вам O(n*logn*m) сложность где n это количество очков и m это число измерений.
редактировать
Это все, если у вас есть евклидово пространство. Т.е. длина вектора v является sqrt(v0^2 + v1^2 + v2^2 + ...), Если вы можете выбрать метрику, однако, могут быть другие варианты для оптимизации алгоритма.
Используйте дерево кд. Вы смотрите на проблему ближайшего соседа, и есть высоко оптимизированные структуры данных для обработки именно этого класса проблем.
http://en.wikipedia.org/wiki/Kd-tree
PS Забавная проблема!
Запустите PCA для ваших данных, чтобы преобразовать векторы из 100 измерений в 20 измерений. Затем создайте дерево K-ближайших соседей (KD-Tree) и получите 2 ближайших соседей на основе евклидова расстояния.
Вообще если нет. измерений очень велики, то вы должны либо использовать метод грубой силы (параллельный + распределенный / картографический) или кластерный подход.
Используйте структуру данных, известную как KD-TREE. Вам нужно будет выделить много памяти, но вы можете обнаружить одну или две оптимизации на основе ваших данных.
http://en.wikipedia.org/wiki/Kd-tree.
Мой друг работал над диссертацией несколько лет назад, когда столкнулся с подобной проблемой. Его работа была порядка 1М баллов по 10 измерениям. Мы создали библиотеку kd-tree для ее решения. Мы можем выкопать код, если вы хотите связаться с нами в автономном режиме.
Вот его опубликованная статья: http://www.elec.qmul.ac.uk/people/josh/documents/ReissSelbieSandler-WIAMIS2003.pdf