Как эффективно найти k-ближайших соседей в многомерных данных?
Итак, у меня есть около 16 000 75-мерных точек данных, и для каждой точки я хочу найти ее k ближайших соседей (используя евклидово расстояние, в настоящее время k=2, если это облегчает его)
Моей первой мыслью было использовать для этого kd-дерево, но, как оказалось, с ростом числа измерений они становятся довольно неэффективными. В моем примере реализации это только немного быстрее, чем полный поиск.
Моей следующей идеей было бы использовать PCA (анализ основных компонентов) для уменьшения количества измерений, но мне было интересно: есть ли какой-нибудь умный алгоритм или структура данных, чтобы решить это точно в разумные сроки?
6 ответов
Статья Wikipedia для kd-деревьев имеет ссылку на библиотеку ANN:
ANN - это библиотека, написанная на C++, которая поддерживает структуры данных и алгоритмы для точного и приблизительного поиска ближайшего соседа в произвольно больших измерениях.
Основываясь на нашем собственном опыте, ANN довольно эффективно работает для наборов точек размером от тысяч до сотен тысяч и размерами до 20. (Для приложений в значительно более высоких измерениях результаты довольно сомнительны, но вы можете попробовать это в любом случае.)
Что касается алгоритма / структуры данных:
Библиотека реализует ряд различных структур данных, основанных на kd-деревьях и деревьях декомпозиции блоков, и использует несколько различных стратегий поиска.
Сначала я попробовал бы это напрямую, и если это не даст удовлетворительных результатов, я бы использовал его с набором данных после применения PCA/ICA (поскольку весьма маловероятно, что у вас будет достаточно нескольких измерений для дерева kd, чтобы справиться).
использовать kd-дерево
К сожалению, в больших измерениях эта структура данных сильно страдает от проклятия размерности, что делает его время поиска сопоставимым с поиском методом грубой силы.
уменьшить количество измерений
Уменьшение размерности - это хороший подход, который предлагает справедливый компромисс между точностью и скоростью. Вы теряете некоторую информацию, когда уменьшаете свои размеры, но получаете некоторую скорость.
Под точностью я имею в виду нахождение точного ближайшего соседа (NN).
Анализ основных компонентов ( PCA) - это хорошая идея, если вы хотите уменьшить размерное пространство, в котором хранятся ваши данные.
Есть какой-нибудь умный алгоритм или структура данных, чтобы решить это точно в разумные сроки?
Приближенный поиск ближайшего соседа ( ANNS), где вы удовлетворены поиском точки, которая может быть не точным ближайшим соседом, а скорее хорошим приближением к нему (это четвертое, например, NN для вашего запроса, в то время как вы ищете 1-й NN).
Такой подход стоит вам точности, но значительно повышает производительность. Более того, вероятность нахождения хорошего NN (достаточно близкого к запросу) относительно высока.
Вы можете прочитать больше об ANNS во введении к нашей статье kd-GeRaF.
Хорошая идея - объединить ANNS с уменьшением размерности.
Хеширование с учетом локальных особенностей ( LSH) - современный подход к решению проблемы ближайшего соседа в больших размерах. Основная идея заключается в том, что точки, расположенные близко друг к другу, хэшируются в одно и то же ведро. Поэтому, когда запрос поступает, он будет хэширован в сегмент, где этот сегмент (и обычно его соседние) содержит хорошие NN-кандидаты).
FALCONN - это хорошая реализация C++, которая фокусируется на сходстве косинусов. Другой хорошей реализацией является наш DOLPHINN, который является более общей библиотекой.
Можно предположить использование кодов Мортона, но с 75 измерениями они будут огромными. И если все, что у вас есть, - это 16 000 точек данных, исчерпывающий поиск не должен занимать слишком много времени.
BK-Tree не такая плохая мысль. Взгляните на блог Ника по автоматам Левенштейна. В то время как он фокусируется на струнах, он должен дать вам трамплин для других подходов. Другая вещь, о которой я могу думать, это R-деревья, однако я не знаю, были ли они обобщены для больших измерений. Я не могу сказать больше, потому что я не использовал их напрямую и не реализовывал сам.
Нет причин полагать, что это NP-полная. Вы ничего не оптимизируете, и мне будет сложно понять, как преобразовать это в другую NP-полную проблему (у меня на полке есть Гэри и Джонсон, и я не могу найти ничего подобного). На самом деле, я бы просто использовал более эффективные методы поиска и сортировки. Если у вас есть n наблюдений, вы должны рассчитать nxn расстояний прямо перед собой. Затем для каждого наблюдения нужно выбрать из топ k ближайших соседей. Это n в квадрате для расчета расстояния, n log (n) для сортировки, но вы должны выполнить сортировку n раз (разные для КАЖДОГО значения n). Грязное, но все же полиномиальное время, чтобы получить ваши ответы.
Одна из наиболее распространенных реализаций - сортировка массива ближайших соседей, который вы вычислили для каждой точки данных. Поскольку сортировка всего массива может быть очень дорогой, вы можете использовать такие методы, как косвенная сортировка, например, Numpy.argpartition в библиотеке Python Numpy, чтобы сортировать только самые близкие значения K, которые вас интересуют. Не нужно сортировать весь массив.
Ответ @ Грембо выше должен быть значительно уменьшен. так как вам нужно только K ближайших значений. и нет необходимости сортировать все расстояния от каждой точки.
Если вам просто нужно K соседей, этот метод будет работать очень хорошо, уменьшая ваши вычислительные затраты и сложность времени.
если вам нужно отсортировать K соседей, снова отсортируйте вывод
увидеть