Алгоритмы нахождения ближайшего вектора

Question

У меня есть набор векторов. Для вектора в этом наборе мне нравится находить подмножество, наиболее близкое к этому вектору. Какой алгоритм может это сделать.

Answer 1

Этот класс алгоритмов называется Ближайший сосед или K Ближайший сосед .

Косинусное сходство , как говорит excpeiont, будет работать, если важно направление вектора. Если вектор представляет позицию в пространстве, то будет работать любая метрика для представления расстояния в пространстве.

Например, Евклидово расстояние : взять квадратный корень из суммы разностей квадратов в каждом измерении. Это даст вам расстояние для каждого вектора, а затем отсортирует ваш набор векторов по возрастанию на этом расстоянии.

Этот процесс будет O (N) во времени. Если это слишком медленно для вас, вы можете посмотреть на некоторые распространенные алгоритмы K Nearest Neighbor .

Answer 2

используйте косинусное сходство (http://en.wikipedia.org/wiki/Cosine_similarity) среди векторов, а затем отсортируйте их.

Answer 3

Если ваша проблема связана с большим количеством данных:

Я опубликовал соответствующий алгоритм на ddj.com, который находит ближайшую линию к данной точке :

Ускоренный поиск ближайшей линии

Вы должны будете изменить этот алгоритм, т. Е. Преобразовав данный вектор во множество точек. Это значительно сократит число возможных совпадений . Точное совпадение должно быть проверено для каждого возможного совпадения с помощью

• Найти точку среза обоих векторов или
• Получите расстояние от начальной и конечной точки вектора до возможного совпадения, как описано в статье