Матрица расстояний -> координаты на плоскости

Здравствуйте.

Имея координаты на плоскости мы с легкостью можем построить матрицу расстояний между всеми координатами.

Но как сделать обратное(с матрицы расстояний получить координаты на плоскости)? Что-то ничего в голову не приходит.

0

Я полагаю что вы уже посмотрели в вики что такое многомерное шкалирование.
Итак имеем несколько точек допустим 5 в 6-мерном пространстве(n-мерного пространства).
Между каждыми парами точек можно найти расстояние. Находим расстояние и записываем в матрицу расстояний.
Далее создадим случайно 5 точек в двумерном пространстве(каждая из этих точек будет представлять те точки из 6-мерного пространства). Находи для них матрицу расстояний.

Итак имеем две матрицы. Одна показывающая реальное положение вещей, а другая случайная.
Наша цель добиться того чтобы расстояния между точками во второй матрице были такие же или приблизительно такие же как в первой. Если мы этого добьемся и нанесем точки из второй матрицы на плоскость то увидим отношение расстояний между точками 6-мерного пространства.

Теперь нужно найти способ найти то насколько вторая матрицы отличается от первой(размер ошибки).
В самом простом случае можно взять разность соответствующих ячеек(расстояний) возвести в квадрат, тоже самое сделать с остальными ячейками и затем сложить(первая формула так называемая абсолютная ошибка). Чем меньше это число тем меньше разница.

Первая формула так называемая абсолютная ошибка
Вторая относительная ошибка
Третья что то среднее между абсолютной и относительной (формула Сэммона)

Итак теперь нужно минимизировать эту ошибку, для этого используется метод градиентного спуска.
Проблема только в том что он не гарантирует лучшее решение так как может застрять в локальном минимуме.


В Вашем случае первой матрицей будет Ваша матрица расстояний, а дальше как описано.

Миниатюры

 

1

Можно поинтересоватся для каких целий нужно было решать эту задачу?

0

boberjajtsegolo, спасибо за описание. Этот метод, как я понял, является приближённым. Моя склонность всегда была к точным методам, мой метод как раз таки является аналитическим.

Сообщение от boberjajtsegolo Проблема только в том что он не гарантирует лучшее решение так как может застрять в локальном минимуме

Плавали, знаем))

Сообщение от boberjajtsegolo Можно поинтересоватся для каких целий нужно было решать эту задачу?

Я решал чисто из спортивного интереса. А вот для чего это нужно было ТС, мы, скорее всего, никогда не узнаем:

nicolaus2 ..... Дополнительная информация Последняя активность: 21.03.2013 17:28

0

Скорее всего это для решения задачи коммивояжера.

0