Quelle est la complexité temporelle des k-means?

Je passais par le k-means page Wikipedia. Basé sur l'algorithme, je pense que la complexité est O(n*k*i) (n = total des éléments, k = nombre de cluster itération)

Si quelqu'un peut m'expliquer cette déclaration de Wikipédia et comment est-ce NP-difficile?

Si k et d (la dimension) sont fixes, le problème peut être exactement résolu dans le temps O(ndk+1 log n), où n est le nombre d'entités à être regroupés.

OriginalL'auteur parallel | 2013-09-05

  1. 17

    Cela dépend de ce que vous appelez k-moyens.

    Le problème de trouver l'optimum global de la k-means de la fonction objectif

    Quelle est la complexité temporelle des k-means?

    est NP-dur, où Si est le cluster i (et il y a k clusters), xj est le ddimensions de point dans le groupe Si et μi est le centre de gravité (moyenne des points) de cluster Si.

    Toutefois, l'exécution d'un nombre fixe t d'itérations de la algorithme standard ne prend que O(t*k*n*d), pour n (ddimensions) points, où kest le nombre de centroïdes (ou clusters). Cette pratique, implémentations de faire (souvent avec de l'aléatoire redémarre entre les itérations).

    L'algorithme n'est qu'une approximation d'un optimum local de la fonction ci-dessus, et ainsi de faire tous les k-moyens algorithmes que j'ai vu.

    OriginalL'auteur Fred Foo

  2. 1

    Le problème est NP-Dur, car il y a une autre bien connue NP-difficile problème qui peut être réduit à (planaire) k-means problème. Avoir un regard sur le papier Le Planaire k-means Problème est NP-dur (Mahajan et coll.) pour plus d'info.

    OriginalL'auteur Dheeraj M Pai

  3. 1

    Dans cette réponse, notez que i utilisé dans les k-means l'objectif de la formule et i utilisés dans l'analyse de la complexité du temps des k-means (qui est, le nombre d'itérations nécessaires jusqu'à ce que la convergence) sont différentes.

    OriginalL'auteur masec