Вопрос или проблема
Правка: в соответствии с комментарием от @anony-mousse, я изменяю вопрос, чтобы искать общий подход кластеризации, который соответствует этому критерию (минимальный вес на кластер).
Мне нужно использовать метод кластеризации на наборе из $n$ взвешенных точек:
---------------------------------------------
| id | weight | feature_1| feature_2 | ... |
---------------------------------------------
| 1 | 4 | 0.2345 | -0.2345 | ... |
| 2 | 2 | 0.675 | 0.7433 | ... |
| 3 | 15 | -0.45 | 0.123 | ... |
| ... | ... | ... | ... | ... |
---------------------------------------------
У меня есть пользовательский критерий: некоторые алгоритмы обеспечивают наличие минимального числа точек $n_{min}$ на кластер; здесь я хотел бы обеспечить, чтобы каждый кластер имел минимальный вес (сумма весов точек) $\sum w_i > s_{min}$.
Существует ли уже такой метод кластеризации, реализованный в Python?
Это не работает, и это не то, как работает иерархическая кластеризация.
Если вы остановитесь на $n_\min$, ни один кластер не будет больше чем $2n_\min-2$, но будут либо множество плохо кластеризованных точек, либо некластеризованные точки.
Рассмотрите набор данных 0 2 3 5 с nmin=2. Первое объединение (2,3) соответствует критерию остановки. Так что либо вы кластеризуете это как (0), (2,3), (5), либо как (0,5), (2,3), ни один из которых не является убедительным: либо nmin не является минимальным размером, либо кластеры могут быть произвольно плохими (и все еще могут быть меньше минимального размера).
Та же проблема относится к взвешенной версии.
Ответ или решение
Теория: В задачах кластеризации данных, особенно когда данные имеют весовые метки, необходимо учитывать не только расстояния между точками, но и такие ограничения, как минимальный вес кластера. Это предъявляет дополнительные требования к алгоритмам кластеризации. При стандартной кластеризации, например, с использованием K-средних, мы ориентируемся на минимизацию внутрикластерного разброса, но такие методы не учитывают вес точек и требования к минимальному весу кластера.
Пример: Представим, что у нас есть набор данных, где каждая точка имеет вес. Требование состоит в том, чтобы каждая группа имела минимальный суммарный вес, что позволяет избежать формирования слишком маленьких или незначительных с точки зрения веса кластеров, которые могут испортить интерпретацию данных. К примеру, в случае, когда имеем массив клиентов с разной покупательной способностью, минимальный вес кластера мог бы означать минимальный общий объём продаж каждому менеджеру.
Применение: Для решения вашей задачи в Python можно рассмотреть использование алгоритмов, позволяющих настраивать собственные условия для образования кластеров. Один из подходов мог бы заключаться в модификации существующих методов или разработке нового метода с использованием библиотек, таких как SciPy или scikit-learn, добавить ограничение на минимальный вес через эвристики или расширения.
Например, с использованием иерархической кластеризации можно программно проверять суммарный вес на каждой итерации и “отклонять” слияния, которые не соблюдают правило минимального веса, тем самым принудительно объединяя маловесные кластеры с соседними, пока они не достигнут установленного порога.
Также возможно использование эвристического подхода или методов смешанного целочисленного программирования (как в библиотеке PuLP), чтобы формализовать задачу как задачу оптимизации с ограничениями на вес кластеров. Этот способ позволит четко задать условия в оптимизационной модели, что подходит для заданий, где необходимо строгое выполнение ограничений.
При отсутствии готовых решений на данном этапе, возможно рассмотреть открытую разработку кастомного алгоритма, основываясь на уже популярных фреймворках и библиотеках, либо интеграции с решениями, поддерживающими гибкие настройки и пользовательские ограничения в реализации процесса кластеризации.