Может ли k-средних попасть в бесконечный цикл? - PullRequest
6 голосов
/ 05 ноября 2010

Я изучил алгоритм k-средних и знаю, как он работает.

Просто любопытно, есть ли ситуации, когда этот алгоритм войдет в бесконечный цикл, скажем, если у нас есть какие-то плохие варианты для начальных точек центроида? Я мог только представить себе, что k-means достигнет локального минимума с неправильными начальными вариантами.

1 Ответ

9 голосов
/ 05 ноября 2010

Нет. k-means имеет верхнюю границу O (n kd ) в d -мерном пространстве.

...