?

Log in

No account? Create an account

Пространственно-размерное - Общество дровосеков Бердичева по изучению Мишны

May. 27th, 2017

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

Previous Entry Share Next Entry

Вопрос к математикам и к примкнувшим к ним.

Допустим, у нас есть некоторый набор абстрактных точек, и нам известны попарные расстояния между этими точками, приведенные с точностью N значащих цифр.

Как определить минимальную размерность пространства, в котором эти точки могут быть расположены, если этих точек не так уж много (скажем, всего несколько десятков), и они могут быть сильно неслучайные, поэтому корреляционную размерность особо не посчитаешь?

This entry was originally posted at http://spamsink.dreamwidth.org/1051076.html. Please comment there using OpenID.

Comments:

[User Picture]
From:dims12
Date:May 27th, 2017 08:37 pm (UTC)
(Link)
Допустим, мы взяли 2 точки. Если расстояние между ими =0, то они совпадают, а если > 0, то лежат на одной прямой.

Допустим, мы взяли N_2 точек, лежащих на одной прямой, причём N_2>2 и хотим рассмотреть точку за номером N_2+1, лежит ли она тоже на одной прямой с предыдущими. Она лежит в том случае, если, если все расстояния разделяются ею точно две части. Смутно.

Теперь допустим, что у нас уже есть точки на плоскости. Как узнать, попадает ли следующая на ту же плоскость или выходит в третье измерение?

То есть, для каждого множества точек M и его размерности K нужно выработать критерий проверки, попадает ли новая точка в ту же размерность,

Что же это за критерий?

(Reply) (Thread)
[User Picture]
From:spamsink
Date:May 28th, 2017 01:11 am (UTC)
(Link)
Грубо, если все расстояния заданы как целые числа, то новая точка попадает в ту же размерность, если вычисленное расстояние между ней и пространством, определяемым множеством М, меньше 0.5.
(Reply) (Parent) (Thread)
[User Picture]
From:dims12
Date:May 27th, 2017 08:47 pm (UTC)
(Link)
А, или может быть взять первую точку за начало координат. Вторую точку, если случай не вырожденный, за первый орт, третью -- за второй орт и так далее. Расстояние до любой новой точки должно быть представимо в виду ax + by + cz + ..., где a, b, c, ,,, произвольные константы, а x, y, z -- длины ортов, то есть, расстояния от нулевой точки до 1-й, 2-й, 3-й и т.д. Если среди чисел попадается 0 (<epsilon), то эта новая точка укладывается в меньшую размерность.... Хм...
(Reply) (Thread)
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)
[User Picture]
From:zlyuk
Date:May 28th, 2017 06:36 am (UTC)
(Link)
если я правильно понял задачу, то можно посмотреть алгоритмы типа LLE (local linear embedding) или Laplacian egienmaps. Это всё вокруг kernel methods. В частности, в Laplacian egienmaps есть способы оценить настоящую размерность (примерно как скорость падения ошибки при увеличении базиса)

Вроде вот есть в википедии статья Nonlinear dimensionality reduction, но я её не изучал.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:May 28th, 2017 07:21 am (UTC)
(Link)
Вот оно, что мне надо: Methods based on proximity matrices

Спасибо, буду смотреть.

Edited at 2017-05-28 07:22 am (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:zlyuk
Date:May 28th, 2017 10:53 am (UTC)
(Link)
да, я именно mds имел в виду. LLE и Isomap, насколько знаю наиболее популярны, поскольку понятны и просты.
если я правильно помню, главная концепция - искать низкоразмерное представление, у которого какое-нибудь корреляционное ядро (например, разброс при случайном гулянии по линейному пространству) наиболее близко к заданной матрице расстояний. причём расстояния, например не обязательно симметричны
(Reply) (Parent) (Thread)