Нахождение самого маленького угла между векторами в логарифмическое время
Я имею n=10000 10-мерные векторы. Для каждого вектора v1 Я хочу знать вектор v2 это минимизирует угол между v1 и v2.
Есть ли способ решить эту проблему быстрее, чем O(n^2)?
4 ответа
Вы можете нормализовать все векторы за время O (n) и найти их параметризацию на результирующую 9-мерную гиперсферу. Затем вы можете использовать структуру пространственного поиска в n-1-мерном пространстве, такую как Kd-дерево, для ускорения запроса ближайшего соседа. Для этого есть хорошо известные методы ( ИНС ).
То, что у вас есть, по сути, является проблемой ближайших точек на сфере (поскольку угол между векторами - это примерно расстояние между точками на сфере, на которых лежат их единичные векторы), поэтому вы, вероятно, могли бы сделать какую-то двоичную (может быть, тройную было бы проще избежать слишком большого количества проблем с границами) разбиение на разделы.
Но это было бы неприятно кодировать и, вероятно, не намного быстрее, чем наивный метод всего для 10 000 точек (в частности, вы начинаете с разделения точек на 3 ^ 10 = 59049 блоков, хотя большинство из них будут быть пустым). Сто миллионов скалярных произведений из десяти элементов должны быть меньше одной секунды.
Как насчет вычисления углов для каждого вектора ( O(n)), затем сортировки массива на основе углов ( O(nlogn)) и затем просто пройтись по массиву ( O(n) )ближайший вектор либо i+1, либо i-1.
Edit:. Как указано в комментариях, это работает только в 2 измерениях.
Вау. Десятимерные векторы? Что вы с ними делаете?
Думаю, я бы начал с уменьшения каждого вектора до единичной длины, то есть до точек на гиперсфере, а затем использовал некоторый алгоритм «поиска ближайшего соседа» (NNS), такой как дерево kD ( k-мерное двоичное дерево), R-tree, Best Bin First и т. д.
Вероятно, невозможно решить эту проблему быстрее, чем O (n log n), потому что если бы вы могли решить эту проблему быстрее, чем это, вы могли бы решить более простая «проблема ближайшей пары точек» быстрее, чем текущая нижняя граница O (n log n).
Как заметил Том Вомак, алгоритм грубой силы O (n ^ 2) потребует меньше реального времени настенных часов, чем эти более сложные алгоритмы для «небольших» объемов данных, и это выглядит как «n = 10000» относительно невелик для 10 измерений.