Поиск n ближайших соседей для многомерного вектора в Евклидовой метрике

Новый комментарий
 
Доброго времени суток! Появилась задача на конечном множестве векторов {X1, X2, ..., Xm} найти n ближайших к фиксированному ветору X', расстояние определяю, как ||X' - Xk||, норма Евклидова. Прошу подсказать, если кому известно хорошее решение данной задачи. Заранее спасибо!
 

Пока что на ум приходит только n раз обойти массив векторов и находить и записывать ближайшие или центрировать относительно нужного вектора и отсортировать, взяв первые n - не очень удобно, когда их 10^5 + 10-мерные...

 
Pavel Krivoshein #:

Пока что на ум приходит только n раз обойти массив векторов и находить и записывать ближайшие или центрировать относительно нужного вектора и отсортировать, взяв первые n - не очень удобно, когда их 10^5 + 10-мерные...

мне на ум приходит https://www.cgal.org :-)

 

Универсальное решение - R + пакет class, в котором есть функция knn() и mt-R для связки R с mql5.

Частное решение - зависит от конкретики: один раз нужно найти расстояние или много раз, меняется ли обучающая выборка и тд.

 
Pavel Krivoshein:
Доброго времени суток! Появилась задача на конечном множестве векторов {X1, X2, ..., Xm} найти n ближайших к фиксированному ветору X', расстояние определяю, как ||X' - Xk||, норма Евклидова. Прошу подсказать, если кому известно хорошее решение данной задачи. Заранее спасибо!
Зачем Вы точки в пространстве конечной размерности называете векторами? Если это не точки, то задача просто не поставлена. Если точки, то решение простое и Вам самому ясное, не нужны никакие библиотеки.
 
Vladimir #:
Зачем Вы точки в пространстве конечной размерности называете векторами? Если это не точки, то задача просто не поставлена. Если точки, то решение простое и Вам самому ясное, не нужны никакие библиотеки.

Я думаю, что вы поняли смысл. А что касается билиотек - я не просил билиотек, скорее искал интересный алгоритм, который не повесит машину, когда количество точек будет порядка 10^8, а размерность, к примеру - 10

 
Pavel Krivoshein #:

Я думаю, что вы поняли смысл. А что касается билиотек - я не просил билиотек, скорее искал интересный алгоритм, который не повесит машину, когда количество точек будет порядка 10^8, а размерность, к примеру - 10

m=100 млн, а n? Задача так и не поставлена. Будем исходить из того, что n << m, раз уж это выборка.

Если не получается выделить память сплошным куском для 100 млн точек по 80 байт на точку, то есть 8 Гб - тогда это вопрос о том, как разместить исходные данные. Можно и на диске, обрабатывать последовательно, частями.

Множество превращаем в массив, нумеруя его точки. Задача превращается в поиск списка номеров точек, ближайших к заданной. Поскольку высока цена прохода по m точкам - будем делать за один проход.

Создаем начальный вариант искомого решения Res из первых n точек. Его будем постепенно менять. В рабочий массив Wor помещаем n расстояний этих точек от заданной. Упорядочиваем Res и Wor по возрастанию расстояний в Wor.

На последнем месте в Wor оказывается наибольшее из расстояний rMax. Дальше берем поочередно из исходного множества-массива точки, начиная с n+1 и до m. Для каждой новой точки:

1. Вычисляем r - расстояние от заданной фиксированной.

2. Если r >= rMax, точку пропускаем, она не изменит массив - претендент. Переходим к следующей точке.

3. r < rMax. Ищем в Wor от начала первый элемент, у которого расстояние >= r. Если n велико, то методом деления пополам или золотого сечения. Он найдется, пусть его номер k.

4. Двигаем элементы Wor с k-го по n-1 включительно вправо на один; также и с элементами Res. На место номер k вставляем номер в исходном массиве (в Res) и расстояние (в Wor). rMax = Wor [n] уменьшается, набор Res становится ближе к заданной точке.

5. Переходим к следующей точке.

   О "повесит машину". Это о времени работы алгоритма? Или о чем?

 
Владимир, не сомневаюсь, что вы - отличный математик, правда люди, которые ответили до вас, смогли додумать суть задания, да и реализацию я уже организовал без сортировки: в итоге выходит m+n! операций чтения из массива и сравнения, где n-нужное количество соседей. Можно и меньше операций наверное, но расписывать т.з. я вам не хочу, ещё денег попросите потом за идею=)
Новый комментарий