Упорядочивание n-1 ближайших соседей для каждой из n точек данных

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

Каков наиболее эффективный способ вычислить это для каждой точки в наборе данных, если у нас есть метрическая функция расстояния, такая как L-норма?

Наивный подход, по-видимому, состоит в том, чтобы сортировать список расстояний для каждой точки по очереди, по цене O (n log n) за точку, то есть O (n ^ 2 log n) для всех точек. Использование kd-дерева кажется не лучше, учитывая, что каждый раз необходимо проходить полное дерево.

Есть ли лучший способ, например, воспользоваться преимуществом неравенства треугольника?


sorting algorithm data-structures nearest-neighbor kdtree
person user2282497    schedule 04.10.2018    source источник
comment
Я думаю, вы понимаете это правильно. O (n ^ 2 войти n). Но если я правильно понял, здесь нельзя использовать простой BST?   -  person anubhs    schedule 04.10.2018
comment
Возможно, O (n ^ 2 log n) не слишком дорого для получения последовательностей, содержащих n ^ 2 элемента.   -  person MBo    schedule 04.10.2018

Ответы (1)


arrow_upward
0
arrow_downward

Поскольку ваш вывод равен O (n ^ 2), вы не сможете стать лучше.

Я думаю, это сводится к тому, как быстро вы можете ранжировать все остальные точки по расстоянию до точки q. Если у вас есть индексная структура (например, KD-дерево или R-дерево), вы можете использовать просмотр расстояния для сортировки всех остальных точек по кв.

Основная идея дистанционного просмотра состоит в том, чтобы иметь приоритетную очередь pq, записи которой отсортированы по минимальному расстоянию до q. pq может содержать точки и записи структуры индекса. Вы начинаете с помещения корневой записи структуры индекса в pq. Затем вы начинаете извлекать элементы из pq. Когда вы сталкиваетесь с записью (узлом), вы разрешаете ее и возвращаете дочерние элементы в pq. Когда вы встречаете точку, вы нашли своего следующего ближайшего соседа q.

В целом структура индекса имеет O(n) записей. Удаление элемента из pq равно O(log |pq|). Это делает время выполнения O(n * log |pq|). Вопрос в том, сколько элементов в среднем будет в pq.

У меня нет доказательств этого, но быстрый набросок позволяет мне предположить, что среднее количество элементов в очереди должно быть около O (sqrt (n)) для L_1 и 2D-пространства. Обратите внимание, что размер очереди сильно зависит от метрики расстояния и размера ваших точек.

Собрав все это вместе, вы можете построить структуру индекса (O (n log n)) и затем для каждой точки q ранжировать все остальные точки (O (n * log (sqrt (n))))

В целом это дает вам время выполнения O(n * log(n) + n^2 * log(sqrt(n))).

Однако, повторяя @MBo: это большая проблема для небольшого улучшения по сравнению с O (n ^ 2 * log (n))

person SaiBot    schedule 04.10.2018
comment
n^2 * log(sqrt(n)) не является улучшением по сравнению с n^2 * log(n), особенно с учетом увеличенной константы пропорциональности. Также можете ли вы привести еще какое-то обоснование квадратного корня? Хотя выглядит впечатляюще. - person meowgoesthedog; 04.10.2018
comment
Велп, ты прав. Относительно квадратного корня: Все записи, близкие к текущему радиусу поиска, находятся в файле pq. Все остальные записи либо уже решены, либо охватывают очень большие области и, по моему мнению, ими пренебрегают. Итак, вы смотрите на отношение радиуса поиска (окружности) с некоторой шириной эпсилон ко всему пространству. - person SaiBot; 04.10.2018