поиск ближайших соседей

[AndreyL]

Возникла такая задача:
В $n$-мерном пространстве имеется $m$ точек, причем $m>n$. Эти точки имеют координаты $x_i_j\geq0$, $i=1..m$, $j=1..n$, при этом $\sum _{j=1}^n x_i_j=1$ для всех $i=1..m$. Попросту говоря, все координаты всех точек неотрицательные и для каждой точки сумма координат равна единице. Фактически все точки гарантировано лежат на одной гиперплоскости. Точки могут лежать на пересечении нескольких гиперплоскостей, в общем случае количество этих гиперплоскостей $1\leq k \leq n-2$.

В этом же $n$-мерном пространстве задана точка $Y$ с координатами $y_j\geq0$, и $\sum _{j=1}^n y_j=1$, т.е. условия на координаты также сохраняются. Точка $Y$ принадлежит тем же $k$ плоскостям, что и точки предыдущего множества.

требуется:
для точки $Y$ найти набор $L$ ближайших точек из первого множества, так чтобы $y_j=\sum _{i\in L} z_i x_i_j$, где $z_i$ – вес $i$-ой точки первого множества в точке $Y$. При этом опять же $z_i\geq0$, и $\sum _{i\in L} z_i=1$. Т.е. точку $Y$ нужно представить как сумму ближайших точек первого множества, типа средневзвешенного, веса неотрицательные и сумма весов равна единице. Есть подозрение, что для этого понадобится не более $n-k+1$ точек.

Такая задача иногда возникает в химии, когда появляется необходимость описать свойства раствора. Раствор представляется как смесь некоторых других растворов с известными свойствами. Чтобы такое описание было близким к истине, растворы этой смеси нужно выбрать как можно ближе к составу изучаемого раствора.
Не мог бы кто нибудь подсказать идею решения такой задачи.

[Alexey1]

Вам необходимо представить вектор $Y$, как линейную комбинацию векторов $X_i, i=1,...,L$, с ограничением на значения $z$, которые тоже необходимо найти, то есть $z$ не фиксированы, так? Вообще, такая задача не всегда имеет решение. Например, возьмите 3 вектора $X_1=(0,4;0,6), X_2=(0,5;0,5), X_3=(0,1;0,9)$ и попытайтесь решить задачу для $Y=(0,7;0,3)$.
По последней части Вашего сообщения вроде как следует, что линейная комбинация векторов $X_i$ просто должна быть наиближайшей из всех возможных к вектору $Y$, то есть равенство не принципиально, это так?
Также задача похожа на задачу математического программирования о наполнении рюкзака. Можете посмотреть здесь.

[AndreyL]

Ваш пример не совсем для моей задачи. Точка Y лежит внутри выпуклого многоугольника, образованного опорными точками X - извиняюсь, что сразу этого не написал. А вот случай, когда опорные точки лежат на прямой, действительно вполне реален. За ссылку спасибо.

[AndreyL]

Посмотрел задачу о ранце - не совсем так. У меня количество опорных точек, из которых нужно собрать точку $Y$ известно, хотя может быть и меньше (если искомая точка легла между опорными). Идея набирать ближайшие точки богатая. Предположим, выбрали $n-k+1$ ближайших точек, собрали искомую, некоторые опорные получились с отрицательным весом - тогда, наверное, надо убрать из тех, которые с отрицательным весом одну, которая дальше, и добавить еще точку. Если из этих точек нельзя собрать искомую, то добавляем еще одну точку. Похоже на правду?

[Alexey1]

AndreyL в сообщении #312937 писал(а):

Предположим, выбрали $n-k+1$ ближайших точек, собрали искомую, некоторые опорные получились с отрицательным весом - тогда, наверное, надо убрать из тех, которые с отрицательным весом одну, которая дальше, и добавить еще точку. Если из этих точек нельзя собрать искомую, то добавляем еще одну точку. Похоже на правду?

Сходимость этого алгоритма не очевидна. Так можно и простым перебором. Ограничения в задаче понятны, это
$\sum_{i=1}^{m} a_i \bar x_i=\bar y$
$\sum_{i=1}^{m} a_i = 1$
$a_i \geq 0, \forall i$
Теперь хорошо было бы составить целевую функцию, которая выбирала бы минимальное количество точек $\bar x_i$. Например, $\min \sum_{i=1}^{m} a_i |\bar x_i-\bar y|$, то есть минимизируется взвешенное расстояние. Эту задачу легко преобразовать в задачу линейного программирования.

[AndreyL]

тем более, что $|\bar x_i-\bar y|$ для всех $i=1..m$ можно посчитать заранее. Попробую, спасибо!

-- Сб апр 24, 2010 10:44 pm --

Не, не понял, как свести к линейному программированию - как задать целевую функцию? Если ее расписать, то получится $ \sum_{j=1}^{n} (\sum_{i=1}^{m} a_i x_i_j- y_j)^2$, это если евклидово расстояние

[AndreyL]

Все, понял! Свел к нелинейной оптимизации с ограничениями. Спасибо огромное!

[Alexey1]

Если так определите расстояния то, это уже нелинейная оптимизация. Можно проще. За расстояние возьмите сумму абсолютных значений разности координат, то есть вместо квадрата берёте абсолютное значение. То есть задача
$\min \sum_{i=1}^{n} c_i|x_i|$
$Ax \geq b$
имеет тоже оптимальное решение, что и задача линейного программирования
$\min \sum_{i=1}^{n} c_iz_i$
$Ax \geq b$
$x_i \leq z_i, i=1,...,n$
$-x_i \leq z_i, i=1,...,n$.

[AndreyL]

Еще проще! Ровно по Вашей схеме
целевая функция $\min \sum_{i=1}^{m} a_i |\bar x_i-\bar y|$, при этом все $|\bar x_i-\bar y|=\sqrt{\sum_{j=1}^{n} (x_i_j-y_j)^2}$ можно посчитать заранее - векторы то известны.
И два типа ограничений:
равенства
$\sum_{i=1}^{m} a_i \bar x_i=\bar y$
$\sum_{i=1}^{m} a_i = 1$

и неравенства
$0\leq a_i \leq 1$

По-моему это должно находить правильный ответ.

[Alexey1]

AndreyL в сообщении #313045 писал(а):

и неравенства
$0\leq a_i \leq 1$

Достаточно просто указать $a_i \geq 0$. Да там действительно способ расчёта расстояний не влияет на линейность (нелинейность), так как точки фиксированы. И имейте ввиду, что эта задача минимизирует взвешенное расстояние.

[AndreyL]

Да, Вы правы - сумма то 1.
Вот еще вопрос такой. Известно, что при размерности пространства, предположим $n=8$, все $m=40$ опорных точек лежат в трех гиперплоскостях (одна понятна - $\sum_{j=1}^{n} x_i_j = 1$, но есть еще две). Точка $Y$ лежит только в одной из этих гиперплоскостей, а именно $\sum_{j=1}^{n} y_j = 1$, и не лежит в двух других. Можно ли представить точку $Y$ линейной комбинацией опорных точек? По-моему, нельзя - уж если все опорные точки находятся в одной гиперплоскости, то из них можно собрать только точку, также находящуюся в этой гиперплоскости.

[Alexey1]

Что Вы имеете ввиду под опорной точкой? И откуда взялись три гиперплоскости? Все Ваши точки в $R^n$ (включая $Y$) будут лежать на одной гиперплоскости заданной уравнением $\sum_{i=1}^{n} x_i = 1$. В частности, если $n=2$, то все точки лежат на линии проходящей через $(1;0), (0,1)$.

[AndreyL]

Опорными точками я называю точки $X$, из которых надо собрать точку $Y$ - надо же как-то их называть. Дело в том, что набор опорных точек таков, что они запросто могут оказаться в этом пространстве в нескольких гиперплоскостях. Но это поправимо, просто пока выбираю набор так, чтобы не было побочных гиперплоскостей.

сейчас следующий вопрос - когда опорных точек 50, то проблем нет, есть из чего выбирать. Но хотелось бы сократить их количество. Дело в том, что таких точек $Y$ не одна. Следующий этап - подобрать такой минимальный набор опорных точек (точек $X$, из которых все собираем), чтобы из них можно было собрать все имеющиеся точки $Y$, причем так, чтобы не было нулевых весов. Анализ пока дал, что набор опорных точек несколько меняется для конкретных имеющихся $Y$. Если использовать наиболее часто встречающийся набор, то некоторые точки не отвечают условиям (похоже выпадают из выпуклого многоугольника). Не подскажете идею?

[Alexey1]

Сначала для одной точки $Y$. Если необходимо выбрать из точек $X$ минимальное их количество, такое чтобы давало точку $Y$, то решается задача.
$\min \sum_{i=1}^{m} z_i$
$a_i \leq z_i, i=1,...,m$
$\sum_{i=1}^{m} a_ix_i=y$
$\sum_{i=1}^{m} a_i=1$
$a_i \geq 0, i=1,...,m$
$z_i=\{0,1\}, i=1,...,m$.
То есть здесь уже минимизируется количество выбранных точек.
Для нескольких точек $Y^k, k=1,...,L$ добавляются ограничения $\sum_{i=1}^{m} a_i^kx_i=y^k$, $\sum_{i=1}^{m} a_i^k=1$, $a_i \geq 0, i=1,...,m$ и затем на все веса добавляете $a_i^k \leq z_i, i=1,...,m$.

[AndreyL]

Извиняюсь, что долго не отвечал - почему-то сервер форума был недоступен.
Маленький вопрос - удастся ли задачу в такой постановке свести к задаче линейного программирования? По идее все $z_i$ принимают значения или 0, или 1, а непрерывными неизвестными являются $a_i^k$, которых нет в целевой функции.