Придумать вложение

[vlad_light]

У меня есть пространство $\mathcal X = \{(a, s) \in \mathbb R \times \mathbb R _+\} $ с метрикой:

$$d(\mathbf x, \hat{\mathbf x}) = \frac {s}{\hat s} + \frac {\hat s}{s} + \frac {(a - \hat a)^2}{s\hat s} +C $$

Можно ли придумать такое вложение $\phi \colon \mathcal X \to \mathbb R$ такое, что

$$\forall \mathbf x, \hat{\mathbf x} \in \mathcal X : d(\mathbf x, \hat{\mathbf x}) = (\phi (\mathbf x) - \phi (\hat{\mathbf x}))^2$$

[alcoholist]

$C=-2$?

[vlad_light]

Да, т.е. сумма разности квадратов делить на произведение.

[alcoholist]

и, наверное, корень там надо взять

-- Пн авг 29, 2016 17:37:00 --

хорошую функцию $\phi$ не придумать, так как она должна быть инъективна

[vlad_light]

Тогда расскажу чуть более подробнее: у меня есть набор прямоугольников со сторонами параллельными осям (которые я параметризирую координатами центра и сторонами), которые я хочу кластеризировать. Вот, придумал такую метрику (это для "одномерных" прямоугольников), но беда в том, что все алгоритмы с неэвклидовой метрикой считают матрицу расстояний, а у меня около 500,000 наблюдений. Можно ли как-то жадно их кластеризовать с ограничением на максимальное расстояние внутри кластера?

Кстати, мне подойдет для $\mathcal X = [0,1]^2$

[DeBill]

vlad_light
1. Видимо, Вы хотите устроить кластеризацию (факторизацию?) так: засунуть в один кластер те точки, на которых ф-я $\varphi$ принимает одно и то же значение, а расстояние между кластерами считать как обычное расстояние на прямой - между значениями этой функции на кластерах. Мне кажется, Вы желаете слишком многого. Можно попробовать меньшего: искать пару $\psi, \rho$ ($\rho$ метрика на прямой), такие, что $d(A,B) = \rho(\varphi(A),\varphi(B))$ для всех $A,B$. Однако, и это кажется весьма сомнительным, ибо
2. Ваша "метрика" $d$ метрикой не является: не выполняется неравенство треугольника. Пример: $x=(n,1), z=(3n,1), y=(2n,100) $. При больших $n$ будет $d(x,z) > d(x,y) + d(y,z)$...

[alcoholist]

DeBill в сообщении #1147734 писал(а):

Ваша "метрика" $d$ метрикой не является

а если

alcoholist в сообщении #1147389 писал(а):

и, наверное, корень там надо взять

?

[vlad_light]

Спасибо большое за ответ.
На самом деле вложение мне не нужно -- это я так хотел перейти к эвклидовой метрике. На всякий случай напишу, что я хотел бы получить:
Пусть есть метрическое пространство прямоугольников (с любой "хорошей" метрикой). Я хочу научиться разделять заданное конечное множество прямоугольников на непересекающиеся подмножества так, чтоб максимальное расстояние в каждом такои подмножестве между любыми двумя его элементами было меньше некоторого фиксированного параметра. Причем, меня устроит даже приближенное решение.

(Оффтоп)

Если, вдруг, интересно -- могу рассказать зачем все это нужно :)

[DeBill]

alcoholist
А, ну так я с корнем и смотрел...Без него - совсем погано...
vlad_light
А чем Вам не нравится стандартная метрика Хаусдорфа?
(Расстояние между множествами $A$ и $B$ есть минимальное $\varepsilon$, такое, что $\varepsilon$-окрестность $A$ содержит $B$, а $\varepsilon$-окрестность $B$ содержит $A$. Если расстояние на $\mathbb{R}^2$ мерить в норме $\left\lVert\right\rVert_{\infty}$, а прямоугольники задавать честно: $Z=[a,b]\times[c,d]$, то будет $d(Z,Z_1) =\max \{\left\lvert a-a_1\right\rvert, \left\lvert b-b_1\right\rvert, \left\lvert c-c_1\right\rvert, \left\lvert d-d_1 \right\rvert\}$ )

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

[DeBill]

А впрочем, можно, видимо, так.
Вначале рассмотрим одномерную задачу: точки на прямой, с обычным расстоянием. Надо: разбить на группы, чтобы в каждой - попарные расстояния были меньше 1.
Решение: в $k$-ю группу - те, у кого целая часть равна $k$.
Теперь - для прям-ков (используем мою "хаусдорфову метрику"): делаем - как выше - для первой к-ты. Затем в каждой группе делим также по второй к-те, и т.д. (К-ты прям-ка - четверка $a,b,c,d$)
Сложность такого алгоритма - порядка "максимум из числа прям-ков и $N^4$, где все прям-ки - на $[0,N]^2$" (что - иногда - намного лучше общего случая - когда надо считать все попарные расстояния).