Вычислительная сложность k-средних

Question

Я проходил через k-means wiki page. На основе алгоритма, я думаю, что сложность O(n*k*i) (n = общие элементы, k = число кластеров итерации)

Так может кто-нибудь объяснить мне это заявление из Википедии и как это NP трудно?

Если k и d (размерность) фиксированы, то проблема может быть решена точно вовремя O(ndk+1 log n), где n является число объектов, которые будут сгруппированы.

Answer 1

Это зависит от того, что вы называете k -средства. Проблема нахождения глобального оптимума в K -средних целевая функция

является NP-трудной. Тем не менее, работаешь фиксированное число я итераций standard algorithm принимает только O (iknd) для п точек в д размеров, и это то, что делают практические реализации (часто со случайными перезапусками между итерациями). Стандартный алгоритм только аппроксимирует локальный оптимум вышеуказанной функции, поэтому все k - алгоритмы, которые я видел.

Answer 2

Вышеуказанный ответ правильный, но i не является тем, что используется в формуле. i - количество итераций, необходимых для конвергенции. Это потому, что для каждой точки вы должны рассчитать расстояние со средним значением для каждого кластера и порядка d (количество функций).