Algoritmo di clustering

Question

Algoritmo di clustering

#1 da (1 voti)
#2 da (0 voti)

5

Ho un insieme di n elementi (1,000 < = n < = 100,000) e posso calcolare il grado di somiglianza tra ogni coppia, cioè un valore da 0 (molto simile) a 1 (molto diverso). Vorrei raggruppare gli elementi in base al loro grado di somiglianza.

Ho pensato di rappresentarli come un grafico, gli elementi sono i vertici ei bordi ponderati sono la somiglianza tra loro. Ho letto l'algoritmo MCL ma penso che non sia l'approccio migliore dal momento che il mio grafico è completo.

D'altra parte, poiché ci sono molti elementi, forse calcolare la somiglianza tra ogni coppia non è la migliore pratica (voglio un algoritmo veloce). Leggo anche qualcosa sugli algoritmi di clustering leader, ma, ancora una volta, non sono sicuro che sia l'approccio migliore perché, per quanto ne so, è abbastanza incline a fallire a causa della sua golosità (vorrei qualcosa di più robusto). / p>

Modifica: ho dimenticato di menzionare che conosco una soglia per la quale quando il confronto tra due elementi è più alto di quello, allora so che appartengono a diversi cluster.

artificial-intelligence

posta ibci 19.03.2015 - 14:44

fonte

2 risposte

Leggi altre domande sui tag artificial-intelligence

Design pattern per la struttura dati che contiene al massimo un articolo di ciascun tipo Design pattern per la mappatura dei campi di dati

score 1 · Answer 1

Non penso che un raggruppamento significativo sia possibile se similarity(a,b) e similarity(b,c) non sono% con limite superioresimilarity(a,c). Per dimostrare, consideriamo il seguente esempio semplice (ed estremo) con solo 3 elementi:

similarity(a,b) == 0
similarity(b,c) == 0
similarity(a,c) == 1

a dovrebbe quindi essere nello stesso cluster di b e b nello stesso cluster di c . Ma a e c dovrebbero essere in diversi cluster, che contraddice le aspettative precedenti.

score 0 · Answer 2

Questo è un problema di cluster spettrale che è stato studiato nell'area di ricerca per molto tempo. In generale, un algoritmo di clustering spettrale utilizza l'autovalore (aka spectrum) per dividere i dati in due o più cluster alla volta. Ognuna di queste suddivisioni è in qualche modo ottimizzata a livello globale, il che porta a buoni risultati complessivi nel clustering finale.

La voce di Wikipedia può fornire ulteriori dettagli.

PS: comunemente un elemento di una matrice di similarità, che è una misura di somiglianza per due oggetti, ha un valore minore per oggetti dissimili e un valore più grande per quelli simili.