Почему алгоритм K-средних предпочтительнее алгоритма Крускала для кластеризации

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

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

Алгоритм Крускала находит кластеризацию с максимальным разделением, что означает, что он разбивает узлы так, чтобы расстояния между кластерами были как можно больше. Как в этом случае будет выглядеть кластеризация с максимальным разделением при k=2? Поскольку расстояния увеличиваются по мере того, как мы движемся слева направо, он найдет кластеризацию «всего, кроме самого правого узла» и «самого правого узла».

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

Так что же является «лучшей» кластеризацией? Это зависит от вашего приложения. Я подозреваю, что чаще всего нам нравится эта вторая кластеризация, потому что мы хотим, чтобы узлы в кластере были как можно более похожи друг на друга. Вот почему мы часто видим, что кластеризация k-средних используется чаще, чем алгоритм Крускала, хотя все еще есть случаи, когда Крускал полезен.

Обратите внимание, что эта проблема ортогональна эффективности. Да, алгоритм Крускала очень быстр, но он вычисляет что-то другое, чем то, что вычисляет метод k-средних.

Надеюсь это поможет!