Per prima cosa, sto cercando di capire comeapplica questo algoritmo per risolvere un progetto di compiti a casa. Quindi, non sto cercando la soluzione per i compiti a casa, solo aiuto a completare il mio algoritmo che risolve il problema.
Sto cercando di usare K-means clustering to clusterun grande set (2 ^ 6) di array. Questi array sono permutazioni uniche della sequenza [0,1,2 ... 31]. Tuttavia, invece di usare la distanza euclidea, ho bisogno di usare la distanza di inversione.
Il mio primo passo in k-means è scegliere k = 10 randompunti dal set di dati. Calcolo quindi la distanza di inversione di ciascun valore nel set di dati su ciascuno dei punti k casuali. Questo dà il cluster iniziale.
Ora, non riesco a capire come convertire il prossimopasso dalla distanza euclidea alla distanza di inversione. Come posso trovare il centro di ciascuno di questi cluster (in termini di distanza di inversione) in modo da poter ripetere il passo del clustering?
Come domanda complementare, la distanza euclidea è una buona approssimazione per (o equivalente) distanza di inversione? Non credo che lo sia, ma non sono sicuro di come provarlo.
Grazie a tutti in anticipo.
risposte:
1 per risposta № 1In generale, tu non può usa k-means con distanze non euclidee. Puoi provare a eseguire l'algoritmo con loro, ma si può dire pochissimo sul significato della convergenza quando l'algoritmo termina.
Come puoi vedere in la voce di Wikipedia, la distanza euclidea è inerente all'algoritmo. Funziona alternando i tipi di passi E e M (come in l'algoritmo EM), e per la distanza euclidea, si può dimostrare che entrambe le fasi riducono al minimo la stessa funzione obiettivo. Per altre distanze, nonostante il codice abbia lo stesso aspetto, non regge, in generale.
Guarda anche questa domanda in Cross Validated.
Se hai una distanza diversa, dovresti usare qualcos'altro, ad es. clustering gerarchico o k-medoids.