Два набора точек с высокой размерностью: найдите ближайшего соседа в другом наборе
У меня есть 2 набора: A и B. Оба набора содержат одинаковое количество точек высокой размерности. Как найти ближайшего соседа в наборе A для каждой точки в наборе B?
Я думал об использовании диаграммы Вороного, но кажется (согласно википедии), что она не подходит для измерений выше 2.
Может кто-нибудь предложить мне метод, пожалуйста?
1 ответ
Flann
Если ваши данные действительно лежат в многомерном пространстве, то вы можете использовать FLANN.
Он на самом деле строит несколько повернутых kd-деревьев и выполняет (немного) запросы к каждому отдельному дереву, сохраняя наилучшие найденные результаты. Он также вращает набор данных, чтобы избежать неприятных случаев.
В разделе публикаций вы можете узнать больше о том, как это работает.
В разделе Получение FLANN вы также можете прочитать руководство.
Тем не менее, поскольку вы хотите выполнить поиск ближайших соседей (NNS) в многомерном пространстве, вам необходимо принять компромисс между временем и точностью (больше времени приходит с большей точностью). Вот почему FLANN выполняет приблизительную NNS (подробнее об этом ответе).
LSH
В качестве альтернативы я бы предложил алгоритм LSH. Вот E²LSH, который фактически реализует алгоритм LSH. Руководство можно найти здесь.
Идея алгоритма заключается в том, что мы хотим, чтобы точки, лежащие рядом друг с другом, были расположены (с высокой вероятностью) в одном и том же сегменте. Тем не менее, LSH посвящен решению проблемы R ближайшего соседа.
Под структурой данных R-ближнего соседа автор, вероятно, подразумевает, что, учитывая точку запроса q, мы можем ответить на этот вопрос: "Какие точки набора данных находятся в радиусе R от q?".
Однако в руководстве объясняется, как можно использовать LSH для поиска NN.
Обратите внимание, что этот тип вопросов не для этого сайта. Я ответил вам, потому что вы новый пользователь. В следующий раз убедитесь, что вы не забудете это.:)