Kmeans Flashcards
(6 cards)
A cosa mira il clustering?
Che misura di similarità?
A dividere gli elementi in k gruppi che presentano caratteristiche simili.
La similarità può essere calcolata per esempio con la distanza euclidea.
Come misurare la similarità?
Somma delle distanze tra ogni punto e il suo centroide assegnato.
Qual’é la complessità degli algoritmi in grado di trovare la soluzione ottimale del problema del clustering?
Il problema di che tipo è?
Quindi cosa si prova a cercare e con che complessità?
> polinomiale, intrattabile.
Algoritmi euristici cercano una soluzione approssimata con complessità al massimo polinomiale.
Passaggi del Kmeans
-fisso il numero di k cluster
- scelgo i k centroidi
- assegno gli elementi
- se la somma delle similarità differisce di almeno un certo valore soglia dalla precedente iterazione allora si ricalcolano le posizione dei centroidi e si ripete.
Complessità algoritmo k means ?
O(t * n* k* d):
- t numero di iterazioni effettuate
- n numero di elementi del dataset
- k numero di cluster da formare
- d dimensioni dei punti
Metodo del gomito
Al variare del numero di k eseguo l’algoritmo e vedo come varia l’errore.
