Quanto è utile/interessante questa discussione:
| Autore |
Discussione |
|
|
drop_
Nuovo Arrivato
18 Messaggi |
 Inserito il - 16 maggio 2012 : 12:04:48
|
Ciao a tutti...
sto studiando l'algoritmo K means e vorrei chiedervi alcune delucidazioni in merito...
Soprattutto vorrei avere la certezza di aver capito le formule...
Innanzitutto quest'algoritmo è un Partitional Clustering dove il numero di cluster in cui raggruppare i dati è scelto a priori,e per assegnare i dati ad ogni cluster si fa riferimento alla distanza da un punto rappresentativo di ogni cluster ossia il centroide.
facendo ora riferimento alle formule del file che ho allegato direi:
Abbiamo n oggetti(da x1 ad xn) da raggruppare in K cluster dove K è dcelto a priori...
Innanzitutto dobbiamo introdurre una variabile indicatore che può assumere solo valori 0 o 1,sarà uguale ad uno quando xn appartiene al cluster K,altrimenti sarò zero se appartiene ad un gruppo diverso da k...
Poi introduciamo la funzione distorsione J in cui la sommatoria che va da 1 ad n è il numero di dati,e la sommatoria che va da 1 a K è il numero di cluster...è così?e poi funzione di distorsione però che vuol dire? e compare anche nella formula la distanza euclidea al quadrato,distanza in cui la distanza tra 2 oggetti è uguale alla lunghezza del segmento che li unisce...quindi si usa una metrica euclidea...
Ora il nostro obiettivo è trovare le minime distanze degli oggetti dai centri di ogni cluster,per cui si deve minimizzare la funzione J e lo si fa attraverso vari passi:
Passo 0: si inizializza l'algoritmo e quindi si scelgono CASUALMENTE i punti medi
Passo 1: Si minimizza J rispetto a rnK mantenendo fissi i centri,per cui rnk è uguale ad 1 se xn è il più vicino al centro del cluster k...vuol dire questo la formula tra parentesi graffe?
Quindi praticamente per fare un esempio direi che nel passo 1,una volta scelti i centri,si vede quale oggetto è più vicino al cenro 1 e si assegna al cluster 1,quale è più vicino al centro 2 e si assegna al cluster 2 ecc..
Passo 2 : si minimizza j rispetto a muK tenendo fissi rnk..per cui essendo J una funzione quadratica si fa la derivata prima e si pone uguale a zero è la soluzione è l'ultima formula che compare nell'allegato.
Ciò vuol dire che in quest'ultimo passo si effettuta il ricalcolo dei centri...il tutto si ripete varie volte fin quando non si possno fare più assegnamenti diversi,si arriva quindi a convergenza.
Allegato:  Formule algoritmo K means.doc
107,26 KB
|
|
|
|
|
drop_
Nuovo Arrivato
18 Messaggi |
 Inserito il - 21 maggio 2012 : 16:03:11
|
Ragazzi so che è qualcosa di abbastanza specifico,ma non c'è nessuno che mi può confermare o meno quanto scritto?
Grazie! |
 |
|
|
chick80
Moderatore
Città: Edinburgh
11491 Messaggi |
Inserito il - 21 maggio 2012 : 16:39:50
|
Uh, questa me la ero persa!
Direi che il tuo ragionamento fila.
Per dirlo in parole povere:
1) scegli a caso k centroidi (k deciso a priori)
2) assegni ogni osservazione ad uno di questi centroidi (quello con distanza minore)
3) Hai ora ottenuto k clusters. Ricalcoli i centroidi usando questa volta i valori delle tue osservazioni
4) ripeti dal punto 2 fino a convergenza
Una simpatica applet
http://siebn.de/other/yakmeans/
PS: nota che anche se in generale si usa una metrica euclidea mi è capitato di vedere usare altre metriche (es. Manhattan) |
Sei un nuovo arrivato?
Leggi il regolamento del forum e presentati qui
My photo portfolio (now on G+!) |
|
|
|
drop_
Nuovo Arrivato
18 Messaggi |
Inserito il - 21 maggio 2012 : 19:09:16
|
| Perfetto!Grazieee |
|
|
| |
Discussione |
|
|
|
Quanto è utile/interessante questa discussione:
| MolecularLab.it |
© 2003-18 MolecularLab.it |
|
|
|
Spiegazione formule k means
Guide tools online
