Наиболее эффективная реализация для получения ближайших k элементов

Question

В алгоритме K-Nearest-Neighbor мы находим верхние k соседей, ближайших к новой точке из N наблюдений, и используем этих соседей для классификации точки.Исходя из своих знаний о структурах данных, я могу думать о двух реализациях этого процесса:

Подход 1

1. Рассчитать расстояния до новой точки из каждого из N наблюдений
2. Отсортируйте расстояния с помощью быстрой сортировки и возьмите верхние k точек

Что займет время O (N + NlogN) = O (NlogN).

Подход 2

1. Создать максимальную кучу размера k
2. Рассчитать расстояние от новой точки для первых k точек
3. Для каждого следующего наблюдения, если расстояние меньше максимальногов куче извлеките эту точку из кучи и замените ее текущим наблюдением
4. Повторная куча (операции logk для N точек)
5. Продолжайте до тех пор, пока в этой точке больше не будет наблюдений.должен иметь только 5 самых близких расстояний в куче.

Этот подход предполагает выполнение операций O (N + NlogK) = O (NlogK).

Правильны ли мои анализы?Как оптимизировать этот процесс в стандартном пакете, таком как sklearn?Спасибо!

Answer 1

Вот хороший обзор часто используемых методов: https://en.wikipedia.org/wiki/Nearest_neighbor_search

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

Если вы немного больше знаете о своих данных, вы можете получить более высокую производительность.Если данные имеют низкую размерность (2D, 3D) и равномерно распределены (это не означает идеально, просто не в очень плотных и очень плотных кластерах), тогда разделение пространства работает отлично, потому что оно быстро сокращает точки, которые находятся слишком далеков любом случае (сложность O (logN)).Они также работают для большей размерности или, если есть некоторые кластеры, но производительность немного снижается (все же лучше в целом, чем линейный поиск).

Обычно для общих наборов данных достаточно разделения пространства или хеширования с учетом локальности.

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