?

Log in

No account? Create an account

Пространственно-размерное - Ваши рубидии уже у кобальта во ртути

May. 27th, 2017

11:04 am - Пространственно-размерное

Previous Entry Share Next Entry

Comments:

From:ald1976
Date:May 27th, 2017 11:52 pm (UTC)
(Link)
Раз точек всего несколько десятков, значит попарных расстояний несколько сотен или тысяч, что немного. Поэтому вопрос об эффективности не стоит.

А дальше тупейший алгоритм.

1. Берем первую точку и присваиваем ей координату 0.
2. Берем вторую точку и присваиваем ей координату расст(первой точки до второй точки) = r.
3. Берем третью точку и проверяем, лежит ли она на прямой, проходящей через первые две.
3.1. Не лежит - меняем координаты первой точки на (0,0), второй на (r,0), третьей даем координаты (u,v), определяемые из расстояний, взяв, по произволу, один из двух подходящий вариантов.
3.2. Остаемся на прямой, даем третьей точки одномерную координату.
4. Берем четвертую точку и проверяем, лежит ли она в многообразии из предыдущих точек, переопределяя, при необходимости, координаты.
5. И.т.д., пока не кончатся точки.

В итоге получаем вложение исходного метрического пространства в евклидово пространство минимальной размерности.

Если вкладывать во что-то более хитрое, чем евклидово пространство, размерность может получиться иная. Но, скорее всего, вам это не актуально.

UPD. НО ЕСТЬ ПРОБЛЕМА!!!

Вложение в конкретное линейное нормированное пространство вообще говоря не обязано существовать. Контр-пример есть уже для четырех точек: A,B,C,D, таких, что

AB=BC=1; AC=AD=BD=CD=2. Эти 4 точки невозможно вложить ни в какое евклидово пространство и надо сильно напрячься, чтобы придумать, куда это вложить и как это вложение релевантно исходной задаче.

Edited at 2017-05-28 12:31 am (UTC)
(Reply) (Thread)
[User Picture]
From:spamsink
Date:May 28th, 2017 01:08 am (UTC)
(Link)
Да, евклидова метрика не предполагается. Возможно, удастся найти 4 такие строки A, B, C, D, чтобы editing distances между ними были такие, как в примере; но, с другой стороны, очевидно, что если взять набор строк a, aa, aaa, aaaa, aaaaa, то они лежат в одномерном пространстве.
(Reply) (Parent) (Thread)
From:ald1976
Date:May 28th, 2017 05:31 pm (UTC)
(Link)
Не вижу никаких проблем с тем, чтобы в Левенштейновой, хемминговой или какой-угодно метрике не возникло неразрешимых проблем с вложением.

Плюс проблемы с тем, как ввести на множестве строк линейную структуру.

Так что ваш вопрос в том общем виде, как он задан, смысла не имеет. Надо на данные, с которыми планируется работать, смотреть. Может и повезёт.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:May 28th, 2017 05:55 pm (UTC)
(Link)
Если проблемы возникают, то размерность пространства будет равна количеству элементов в наборе, с метрикой, определенной матрицей расстояний, и вводить линейную структуру не будет необходимости.
(Reply) (Parent) (Thread)
From:ald1976
Date:May 28th, 2017 06:08 pm (UTC)
(Link)
Размерность еще более заюзанное слово, чем поле.

Но все же, обычно, по умолчанию размерность - это размерность линейного пространства.

А все прочие размерности идут с уточнением, о какой "размерности" речь.

Так что лучше уточнить, задачи из какой области вы собрались решать.
(Reply) (Parent) (Thread)