26
Sto provando a vedere se le prestazioni di entrambi possono essere confrontate in base alle funzioni obiettivo su cui lavorano?qual è la differenza tra "k significa" e "fuzzy c significa" funzioni obiettive?
A
risposta
22
BTW, l'algoritmo di clustering Fuzzy-C-Means (FCM) è anche noto come Soft K-Means.
Le funzioni obiettivo sono praticamente identiche, l'unica differenza è l'introduzione di un vettore che esprime la percentuale di appartenenza di un dato punto a ciascuno dei cluster. Questo vettore è sottoposto ad un esponente di "rigidità" volto a dare più importanza alle connessioni più forti (e viceversa a minimizzare il peso di quelle più deboli); incidentalmente, quando il fattore di rigidezza tende all'infinito, il vettore risultante diventa una matrice binaria, rendendo quindi il modello FCM identico a quello dei K-Means.
Penso che ad eccezione di alcuni possibili problemi con i cluster a cui non è stato assegnato alcun punto, è possibile emulare l'algoritmo K-Means con quello di FCM, simulando un fattore di rigidità infinito (= introducendo una funzione che cambia il valore più grande nel vettore in 1 e zera gli altri valori, al posto dell'esponenziazione del vettore). Questo è ovviamente un modo molto inefficiente di eseguire un K-Means, perché l'algoritmo deve quindi eseguire tante operazioni come con un vero FCM (se solo con valori 1 e 0, cosa che semplifica l'aritmetica, ma non la complessità)
per quanto riguarda le prestazioni, FCM deve quindi effettuare k (cioè il numero di cluster) moltiplicazioni per ciascun punto, per ogni dimensione (non contando anche l'elevamento a prendere in considerazione rigidità). Questo, oltre al sovraccarico necessario per l'elaborazione e la gestione del vettore di prossimità, spiega perché l'FCM è molto più lento dei normali K-Means.
Ma FCM/Soft-K-Means è meno "stupido" di Hard-K-Means quando si tratta ad esempio di cluster allungati (quando punti altrimenti coerenti in altre dimensioni tendono a disperdersi lungo una particolare o due dimensioni), ed è per questo che è ancora in circolazione ;-)
Inoltre, ho solo pensato a questo, ma non ci ho pensato "matematicamente", l'FCM può convergere più velocemente dei K-Means duri, un po 'sfalsando il più grande requisito computazionale di FCM.
+0
Perché FCM dovrebbe convergere più velocemente? In realtà non converge affatto, devi fermarti a una certa soglia, quando i relativi compiti non cambiano più "abbastanza"; proprio come il clustering GMM-EM. –
+0
@ Anony-Mousse: sia FCM che K-Means _converge_, in senso matematico, è molto quello che si descrive con 'quando le assegnazioni relative non cambiano più" abbastanza "." In altre parole la soluzione di clustering fornita dalle successive le iterazioni di questi algoritmi cambiano molto, inizialmente, da una iterazione alla successiva, ma alla fine le modifiche diventano sempre più piccole man mano che la funzione si avvicina al limite. È sicuro interrompere la iterazione dopo aver raggiunto una soglia di modifica pratica perché la funzione è convergente: l'iterazione di più non produrrà un risultato significativamente diverso ... – mjv
+0
... Ciò che sto ancora cercando di studiare è se FCM converge effettivamente più veloce di K-Mezzi duri. In altre parole se impiega un minor numero di iterazioni con FCM (rispetto a K-Means) per raggiungere la soluzione "stabile" desiderata. – mjv
16
K-Means clustering e Fuzzy-C Means Clustering sono molto simili negli approcci. La differenza principale è che, nel cluster di Fuzzy-C Means, ogni punto ha una ponderazione associata a un particolare cluster, quindi un punto non si siede "in un cluster" tanto quanto ha un'associazione debole o forte al cluster, che è determinato dalla distanza inversa rispetto al centro del cluster.
I mezzi Fuzzy-C tenderanno a funzionare più lentamente di K significa, poiché in realtà sta facendo più lavoro. Ogni punto viene valutato con ciascun cluster e più operazioni sono coinvolte in ogni valutazione. K-Medie ha solo bisogno di fare un calcolo della distanza, mentre fuzzy c significa che deve fare una pesatura inversa a distanza completa.
1
le persone hanno scritto tecnicamente e ogni risposta è ben scritta. Ma quello che voglio dire è lo stesso in parole povere. K indica cluster di cluster l'intero set di dati in K numero di cluster in cui un dato deve appartenere a un solo cluster. Fuzzy c-significa creare k numeri di cluster e quindi assegnare ogni dato a ciascun cluster, ma il loro sarà un fattore che definirà quanto fortemente i dati appartengono a quel cluster.
Vieni! Non chiudere ... il clustering è correlato alla programmazione, allo stesso livello che dice algoritmi di ordinamento o domande sulla grammatica formale! – mjv