Какой-то критерий для объединения множеств

[zgemm]

Здравствуйте!

У меня есть два набора точек в 3-х мерном пространстве $x_i \in R^3, i=1,...,N_x$ и $y_i \in R^3, i=1,...,N_y$, для которых я могу посчитать среднее и среднеквадратичное, и мне надо придумать какой-то критерий, по которому я разрешал бы объединять этот набор точек в один общий набор, например, если объединенный набор бы вписывался в шар не на много больший, чем любой исходный набор.

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

Скажите, пожалуйста, какие критерии такого объединения обычно используются?

[ozheredov]

Погуглите что-нибудь про кластеризацию.

[zgemm]

Спасибо, ozheredov да, гуглил, все критерии кластеризации требуют обхода всех точек, а я это хочу избежать. То есть есть наивный критерий - посчитать среднее обоих распределений, посчтать среднеквадратичное отклонение в суммарном распределении и в исходных, но ведь у объединенного множества всегда получаемый шар будет не меньше. Все остальное, когда можно отбросить выпадающие точки, или среднемедианные - требуют знания всех точек.

[ozheredov]

zgemm
Когда Вы считаете среднее или скв-отклонение, Вы все точки не обходите?

[zgemm]

ozheredov в сообщении #1587997 писал(а):

zgemm
Когда Вы считаете среднее или скв-отклонение, Вы все точки не обходите?

Конечно обхожу, но это делается один раз на исходный набор точек. Таких наборов у меня очень много. Далее я хочу некоторые наборы объединить, если в них оказались точки, которые находятся "близко". И вот во время объединения я не хочу обходить эти точки снова и снова. По хорошему, у меня, скажем, $10^5$ наборов точек, и мне надо провести очень много, в худшем случае $5\times10^9$ сравнений, а я ожидаю, что после всех таких сравнений и объединений у меня останется порядка $10^3$ наборов. Так как в каждом наборе всреднем около ста точек до начала сравнений и около десяти тысяч к концу сравнений, использовать для сравнения все точки не хотелось бы.

[Geen]

zgemm в сообщении #1588014 писал(а):

И вот во время объединения я не хочу обходить эти точки снова и снова.

а как Вы рассчитаете среднее и дисперсию для объединения?

[zgemm]

Geen в сообщении #1588033 писал(а):

а как Вы рассчитаете среднее и дисперсию для объединения?

Так вроде просто же?

Пусть

$s_1 = \sum_{i=1}^{N_x} x_i \in R^3, s_2 = \sum_{i=1}^{N_x} ||x_i||_2^2 \in R$, и я запоминаю для каждого исходного набора эти самые $s_1$, $s_2$, и, конечно же $N_x$.

В силу аддитивности, для объединения двух наборов я смогу получить значения $s_1$, $s_2$ простым суммированием и из него получить и среднее и дисперсию.

Очевидно можно запоминать и не только такие простые вещи, но и что-то типа

$\sum_{i=1}^{N_x} x_i x_i^T \in R^{3 \times 3}$

но поможет ли мне знание эллипса распределения дисперсии - пока для меня не очевидно.