минимизировать евклидово расстояние от множества точек в n-измерениях

Question

Давайте посмотрим на m точек в n-d-пространстве (решение для 4-х точек в 3-d-пространстве здесь: минимизировать расстояние от наборов точек )

a= (x1, y1, z1, ..)

b= (x2, y2 ,z2, ..)

c= (x3, y3, z3, ..)
.
.

p= (x , y , z, ..)

Find point q = c1* a + c2* b + c3* c + ..

where c1 + c2 + c3 + .. = 1
and  c1, c2, c3, .. >= 0
s.t.
euclidean distance pq is minimized.

Какие алгоритмы можно использовать? Идея или псевдокод достаточно. (Оптимизация производительности является большой проблемой здесь. Метод Монте-Карло со всеми вершинами и изменяющимися коэффициентами также даст решение.)

Answer 1

Мы можем предположить, что p = 0, вычитая p из всех остальных точек. Тогда возникает вопрос минимизации нормы над выпуклой оболочкой конечного множества точек, т. Е. Многогранника.

Есть несколько статей по этой проблеме. Он выглядит как «Рекурсивный алгоритм для нахождения минимальной точки нормы в многограннике и пары ближайших точек в двух многогранниках» Казуюки Секитани и Йошицугу Ямамото - хороший пример с кратким обзором предыдущих решений проблемы. Он находится за платным доступом, но если у вас есть доступ к университетской библиотеке, вы можете загрузить копию.

Алгоритм, который они дают, довольно прост, как только вы пройдете через обозначения. P - конечное множество точек. C (P) - его выпуклая оболочка. Nr (C (P)) - это уникальная точка минимальной нормы, которую вы хотите найти.

Шаг 0: Выберите точку x_0 из выпуклой оболочки C (P) вашего конечного набора точек P. Они рекомендуют выбрать x_0 в качестве точки в P с минимальной нормой. Пусть k = 1.

Теперь цикл:

Шаг 1: Пусть a_k = min {x ^ t_ {k-1} p | р находится в P}. Здесь x ^ t_ {k-1} - это транспонирование x_ {k-1} (поэтому минимизируемая функция является просто точечным произведением, так как p находится в пределах вашего конечного множества P). Если | x_ {k-1} | ^ 2 <= a_k, то ответ x_ {k-1}, остановка. </p>

Шаг 2: P_k = {p | p в P и x ^ t_ {k-1} = a_k}. P_k - это подмножество P, которое минимизирует выражение на шаге 1. Вызовите алгоритм рекурсивно для этого набора P_k, и пусть результат будет y_k = Nr (C (P_k)).

Шаг 3: b_k = min {y ^ t_k p | p в P \ P_k}, минимум точечного произведения y_k с точками в наборе дополнений P \ P_k. Если | y_k | ^ 2 <= b_k, то y_k является ответом, остановитесь. </p>

Шаг 4: s_k = max {s | [(1-s) x_ {k-1} + sy_k] ^ t y_k <= [(1-s) x_ {k-1} + sy_k] ^ t p для каждого p в P \ P_k}. Пусть x_k = (1-s_k) x_ {k-1} + s_k y_k, пусть k = k + 1 и вернемся к шагу 1. </p>

В шаге 4 есть явная формула для s_k:

s_k = min {[x ^ t_ {k-1} (p-y_k)] / [(y_k-x_ {k-1}) ^ t (y_k-p)] | p в P \ P_k и (y_k - x_ {k-1}) ^ t (y_k-p)> 0}

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

Обратите внимание, что вам следует добавить некоторые допуски в свои сравнения, иначе ошибки округления могут привести к сбою алгоритма. Существует много дискуссий о численной стабильности, подробности см. В статье.

Они не дают полного анализа вычислительной сложности алгоритма, но они доказывают, что в двумерном случае это не более O (m ^ 2) (m - число точек в P), и они провели численные эксперименты, которые создают впечатление, что оно является сублинейным во времени как функция m с фиксированной размерностью. Я скептически отношусь к этому требованию. В отсутствие подробного анализа я предлагаю вам попробовать несколько экспериментов с типичными данными, чтобы увидеть, насколько хорошо алгоритм работает для вас.

Answer 2

Проще говоря, у вас есть набор баллов {a} _i , и вы рассматриваете все баллы, которые являются их некоторой средневзвешенной величиной. Этот набор точек является в точности выпуклой оболочкой из этих точек; это многогранник (многоугольник, многогранник и т. д.), который просто выпуклый, где углы являются подмножеством {a} _i точек.

Вы просто спрашиваете, какая точка многогранника (~ эдрон) является ближайшей к точке. (точка вашего запроса p )

Ближайшая точка должна быть на внешней стороне многогранника. Один из алгоритмов - перебор всех N-1 мерных поверхностей. Сделайте это обычным способом, чтобы найти точку, ближайшую к линии или поверхности или N-мерной поверхности, к точке запроса.

(Если точки не все линейно независимы, у вас будет несколько способов (несколько весовых векторов), которые могут дать вам одинаковую средневзвешенную точку q . Вы можете беспокоиться о восстановлении ответа q из базисных векторов после того, как вы найдете его геометрически.)