Почему алгоритм k-средних может давать локальные минимумы?

Алгоритм k-средних может давать локальные минимумы, потому что его результат зависит от выбора начальных (случайных) кластеров. 1 Разные начальные центры могут привести к разным кластерам. 3

Если центры кластеров выбираются слишком близко друг к другу, то алгоритм может «разделить» то, что должно быть единым кластером, и «объединить» два разных. 5 В таком случае алгоритм минимизирует ошибку, но лишь в пределах того, что ему позволил изначальный выбор положения центроидов. 5

Чтобы преодолеть проблему локальных минимумов, часто используют метод k-means++, который предлагает более интеллектуальную стратегию инициализации центроидов. 2 Она основана на вероятностном распределении, пропорциональном квадрату расстояния от уже выбранных центроидов. 2