Метрическая группировка/группировка на основе плотности

Question

У меня есть конечное число точек (облако) с метрикой, определенной на них. Я хотел бы найти максимальное количество кластеров в этом облаке таким образом, что:

1) максимальное расстояние между любыми двумя точками в одном кластере меньше заданного эпсилон (сопзЬ)

2) каждый кластер имеет точно k (const) указывает на это

Я смотрел на все виды различных методов кластеризации, и кластеризация с ограничением на внутреннем максимальном расстоянии не является проблемой (основанной на плотности). 2) ограничение и требование найти «максимальное количество кластеров s.t.» Кажется, это проблематично. Любые предложения по эффективному решению?

Спасибо, A ~

Answer 1

Учитывая ваши ограничения, не может быть никакого решения. И на самом деле это может случиться довольно часто ...

Самый очевидный случай, когда у вас нет кратного k баллов.

Но также, если epsilon установлен слишком низко, могут быть точки, которые больше не могут быть помещены в кластеры.

Я думаю, вам нужно переосмыслить свои требования и проблемы, вместо того, чтобы искать алгоритм для решения неоправданно жесткого требования, которое может быть неудовлетворительным.

Также подумайте, действительно ли вам нужно найти гарантированный максимум или просто хорошее решение.

Есть довольно очевидные подходы, которые, по крайней мере, быстро найдут хорошее приближение.

Answer 2

У меня такое впечатление, что @ Anony-Mousse, на самом деле: вы еще не поняли свои проблемы и требования.

Если вы хотите, чтобы размеры вашего кластера были k, нет вопросов о том, сколько кластеров вы получите: это, очевидно, n /k. Таким образом, вы можете попробовать использовать k-мерный вариант, который создает кластеры того же размера, что, например, описанных в этом уроке: Tutorial on same-size k-means и установите необходимое количество кластеров в n/k.

Обратите внимание, что это не особый разумный или хороший алгоритм кластеризации. Он делает что-то, чтобы удовлетворить ограничения, но кластеры не имеет смысла с точки зрения кластерного анализа. Это ограничение ограничений, но не кластерный анализ.

Для того чтобы удовлетворить ваши требования к epsilon, вы можете начать с этого первоначального решения (что, вероятно, является тем, что @ Anony-Mousse называют «очевидными подходами») и попытаться выполнить такую ​​же оптимизацию - -спутниковые элементы, чтобы удовлетворить условию эпсилона.

Возможно, вам потребуется несколько перезапусков, так как не может быть никакого решения.

Смотрите также:

Group n points in k clusters of equal size

K-means algorithm variation with equal cluster size

по существу избыточных вопросов.