Алгоритм Ллойда

Question

Можно ли запустить алгоритм Ллойда для нахождения k-средних в одномерном за полиномиальное время?

Я знаю, что проблема k-средних является NP-трудной для чего-либо болееразмеры.Любое, если у вас есть фиксированное измерение, алгоритм Ллойда будет работать за полиномиальное время, верно?

Answer 1

Истинный алгоритм k-средних сложен в NP и всегда дает оптимальный результат. Алгоритм Ллойда - это эвристический алгоритм k-средних, который «скорее всего» дает оптимум, но часто предпочтительнее, поскольку его можно запустить за многократное время.

Answer 2

Я бы не слишком беспокоился о времени работы k средних на практике.Вы можете построить распределения, которые заставят его работать экспоненциально, но если эти входы будут немного шумными, время выполнения будет полиномиальным.http://theory.stanford.edu/~sergei/papers/kMeans-socg.pdf