Кластеризация на группы заданного размера

[longstreet]

Существуют ли методы кластеризации, позволяющие разбить группу точек евклидовой плоскости на группы, размер которых задан?

Пример. Для заданного расположения двадцати домов (см. рисунок) нужно расположить две подстанции. Предполагается сначала разбить дома на две группы, внутри которых потом найти оптимальное размещение подстанций. Стандартное разбиение на два кластера даёт группы по $5$ и $15$ элементов. Однако, подстанции имеют ограниченную мощность и более 10 обслуживать не могут. Нужна кластеризация для такой ситуации.


-- 15.07.2012, 14:51 --

Ещё лучше, если бы размер групп задавался бы не точным равенством, а приближённым. И уж совсем хорошо было бы, если бы можно было указывать точное количество требуемых групп. Итак, в идеале такая постановка: разбить заданные $N$ точек на евклидовой плоскости на $K$ групп, по ($P$ плюс-минус $Q$) точек в группе.

[longstreet]

Годится ли последовательное добавление всё менее вероятных точек при вероятностной (нежёсткой) кластеризации? Или это заведомо плохо?

[longstreet]

В википедии написано, что некий метод Уорда (применяется в социологии) в итоге создаёт кластеры приблизительно равных размеров. Кроме этого ничего не нашёл.

[longstreet]

Нашёл любительский алгоритм кластеризации, который разбивает на равные группы. Скачать, чтобы посмотреть как он работает: http://code.google.com/p/ekmeans/downloads/list

Код этого алгоритма на Java: http://code.google.com/p/ekmeans/source ... means.java

Как он работает, не разобрался. К сожалению, не знаю этого языка. Судя по всему, он не поддерживает разбиения на заданные кластеры, а разбивает только на равные. Но и такое разбиение мне интересно. И вдруг потом улучшить можно будет... Буду рад, если кто отпишется $-$ поделится впечатлениями или идеями.

[_hum_]

А может, все-таки, попробовать четко сформулировать задачу оптимизации, наподобие
найти такое расположение двух подстанций максимальных мощностей $P_{I}$, $P_{I\!I}$ и распределение по ним $n$ домов с максимально потребляемыми мощностями $p_i$, $i = 1,\dots,n$, чтобы минимизировать суммарную длину кабелей.

Тогда, в качестве формальной постановки можно рассмотреть, например, следующую. Пусть $\mathbf{x}_{I}, \mathbf{x}_{I\!I}$ - координаты подстанций, $\mathbf{x}_{i}$, $i = 1,\dots, n$ - координаты домов, $b_i$ - идентификатор подстанции, к которой присоединен $i$-ый дом (для удобства считаем $b_i \in \{0,1\}$). Тогда суммарная длина кабелей $L$

$$L(\mathbf{x}_{I}, \mathbf{x}_{I\!I}, b_1,\dots,b_n ) = \sum_{i=1}^{n}b_i d(\mathbf{x}_{I}, \mathbf{x}_{i}) + (1- b_i) d(\mathbf{x}_{I\!I}, \mathbf{x}_{i}).$$

Задача оптимизации:

$$L(\mathbf{x}_{I}, \mathbf{x}_{I\!I}, b_1,\dots,b_n ) \rightarrow \min,$$

$$\sum_{i=1}^{n}b_i p_i \leq P_{I}, \quad \sum_{i=1}^{n}(1 - b_i) p_i \leq P_{I\!I}.$$

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