K-means: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: accenti |
m Bot: accenti |
||
Riga 29:
==Pregi e difetti==
L'algoritmo ha acquistato notorietà dato che converge molto velocemente. Infatti, si è osservato che generalmente il numero di iterazioni sono minori del numero di punti. Comunque, l'algoritmo puo' essere molto lento nel caso peggiore: D. Arthur e S. Vassilvitskii hanno mostrato che esistono certi insiemi di punti per i quali l'algoritmo impiega un tempo superpolinomiale, <math>2^{\Omega(\sqrt{n})}</math>, a convergere. Più recentemente, A. Vattani ha migliorato questo risultato mostrando che l'algoritmo puo' impiegare tempo esponenziale, <math>2^{\Omega(n)}</math>, a convergere anche per certi insiemi di punti sul piano. D'altra parte, D. Arthur, B. Manthey e H. Roeglin hanno mostrato che la smoothed complexity dell'algoritmo
In termini di qualita' delle soluzioni, l'algoritmo non garantisce il raggiungimento dell'ottimo globale. La qualità della soluzione finale dipende largamente dal set di cluster iniziale e può, in pratica, ottenere una soluzione ben peggiore dell'ottimo globale. Dato che l'algoritmo è di solito estremamente veloce, è possibile applicarlo più volte e fra le soluzioni prodotte scegliere quella più soddisfacente.
|