Расчет расстояния до k-го ближайшего соседа для всех точек в наборе

9

Для применения машинного обучения моя группа должна рассчитать евклидово расстояние до kближайший сосед в наборе X для каждого x(XY)Rd (за d от 5 до 100, и |X||Y|от нескольких сотен до нескольких миллионов). В настоящее время мы используем либо грубую силуO(d|X||XY|) подход или очевидный с KD-дерева на Xкоторый когда d высокий и |X|относительно низок, никогда не побеждает. (Все в памяти.)

Похоже, что должен быть лучший способ, чем грубая сила - по крайней мере, тот, который использует неравенство треугольника, или, возможно, с помощью хэшей, чувствительных к локальности. Достаточно узкое приближение также потенциально хорошо.

Исследование, которое я смог найти, похоже, сосредоточено на проблеме поиска единственного ближайшего соседа (или того, который приблизительно является ближайшим). Идет ли проблема, которую я ищу, под каким-то другим именем, или есть связь с проблемой, о которой я не думал?

Дугал
источник
2
КД-деревья ДОЛЖНЫ использовать неравенство треугольника. Вы пробовали использовать другие деревья разделения пространственных данных? Еще одна вещь, которую вы можете посмотреть (я ничего не знаю о вашем алгоритме машинного обучения), имеют ли определенные точки структуру, которая может помочь вам быстро найти гиперплоскости и использовать их в дереве, подобном kd, вместо обычного медианного разделение координат, которое плохо работает в больших размерах.
Росс Снайдер
@RossSnider спасибо за предложения. И конечно, деревья KD используют неравенство треугольника, но я думал о чем-то, что будет быстрее, чем грубая сила. :) Какие еще виды деревьев пространственного разделения данных вы бы порекомендовали? Из списка Википедии, возможно, только vp-деревья кажутся применимыми, и они не кажутся лучше, чем kd-деревья на евклидовом расстоянии. И я подумаю, есть ли лучший способ определения разделяющих гиперплоскостей для конкретных проблем, но он не приходит в голову.
Дугал
Я думаю, я надеялся, что тот факт, что мы знаем, что мы оцениваем это для всех X(а также другие пункты) позволили бы получить некоторую помощь в алгоритме. Я не уверен, что это так, хотя.
Дугал
что такое kкак правило в ваших приложениях?
Суреш Венкат
1
@SureshVenkat Мы обычно используем kоколо 3, иногда немного больше.
Дугал

Ответы:

10

Вот простой трюк, который может быть полезен. Рассмотрим случайную выборку, которая выбирает каждую точку с вероятностью 1 / k. Легко проверить, что с большой вероятностью именно один из ваших k ближайших соседей будет в выборке. Вычислить ближайшего соседа в образце. Повторите это O (k log n) раз. С большой вероятностью k ближайших точек вO(klogn)Вычисленные точки - это k ближайших соседей к вашему запросу. Таким образом, нахождение k ближайшего соседа эквивалентноO(klogn) запросы ближайшего соседа.

Короче говоря, дайте мне быструю структуру данных для ответа на запросы ближайшего соседа, и я был бы рад предоставить вам быструю структуру данных k-ближайшего соседа.

Сариэль Хар-Пелед
источник
Хороший трюк. Также должно быть хорошо повторно использовать образцы для разных точек запроса, верно? Таким образом, чтобы рассчитатьkближайший сосед для каждой точки в наборе, мне нужно только построить структуру данных O(klogn)раз.
Дугал
1
Повторное использование образцов сложно, потому что тогда вы требуете, чтобы фиксированный образец работал для ЛЮБОГО запроса (квантификация перевернута) и поэтому вероятности изменились бы. Общая идея заключается в том, чтобы создать набор выборок большего размера (это зависит от #queries) и использовать их, если это проблема.
Суреш Венкат
@SureshVenkat А, конечно. Я сяду и выясню реальные вероятности. Спасибо всем!
Дугал
Если вы делаете O(klog(1/δ)) выборки, то каждый запрос выполняется с вероятностью 1δ, Обратите внимание, что этот трюк немного лучше, чем кажется на первый взгляд - у вас естьO(klogn) образцы, каждый из них размером O(n/k) (с высокой вероятностью, если kне слишком большой). Что означает лучшее время запроса для каждого из образцов.
Сариэль Хар-Пелед
3

Дешевое приблизительное решение, использующее «хеш-код с учетом локальности», состоит в преобразовании каждой точки в форму с чередованием битов:

[xxx, yyy, zzz] -> xyzxyzxyz

затем радикальная сортировка для предварительной обработки.

Выберите свою точку для запроса и вперед k указывает в обоих направлениях, чтобы получить размер 2kнабор; затем возьмитеkthближайший к вашей точке. Также посмотрите эту статью Коннора и Кумара.

Также посмотрите эту статью Каллахана и Косараджу.

Чад Brewbaker
источник