Clustering efficace di una matrice di similarità

Question

il mio argomento è la similarità e il clustering di (un gruppo di) testo/i. In breve: voglio raggruppare i testi raccolti insieme e dovrebbero apparire in gruppi significativi alla fine. Per fare questo, il mio approccio fino ad ora è il seguente, il mio problema è nel clustering. Il software attuale è scritto in PHP.

1) Somiglianza: Tratto ogni documento come "sacchetto di parole" e converto parole in vettori. Uso

• filtraggio (soltanto in termini "reali")
• tokenization (frasi diviso in parole)
• derivanti (ridurre parole alla loro forma di base; Stemmer Porter)
• potatura (taglio di parole con troppo alta & bassa frequenza)

come metodi per la riduzione della dimensionalità. . Dopo di che, sto usando coseno di similitudine (come suggerito/descritto a vari siti sul web and here

Il risultato è quindi una matrice di similarità come questo:

 A B C D E 
    A 0 30 51 75 80 
    B X 0 21 55 70 
    C X X 0 25 10 
    D X X X 0 15 
    E X X X X 0 

A ... E sono i miei testi e il numero è la somiglianza in percentuale, più alto è il più simile sono i testi, poiché sim (A, B) == sim (B, A) è riempito solo a metà della matrice. Quindi la somiglianza del testo A al testo D è 71%

Voglio generare un numero sconosciuto di cluster (priori) fuori da questa matrice ora. I cluster dovrebbero rappresentare gli elementi simili (fino ad una certa fermata criterio p) insieme.

Ho provato un implementazione di base io stesso, che era fondamentalmente come questo (il 60% come soglia di somiglianza fissa)

foreach article 
     get similar entries where sim > 60 
       foreach similar entry 
       check if one of the entries already has a cluster number 
       if no: assign new cluster number to all similar entries 
       if yes: use that number 

ha funzionato (in qualche modo), ma non era affatto buono ei risultati sono stati spesso mostro-cluster. Quindi, voglio ripetere questo e ho già dato un'occhiata a tutti i tipi di algoritmi di clustering, ma non sono ancora sicuro di quale funzionerà meglio. Penso che dovrebbe essere un algoritmo agglomerato, perché ogni coppia di testi può essere vista come un cluster all'inizio. Ma ancora le domande sono quali sono i criteri di arresto e se l'algoritmo dovrebbe dividere e/o unire insieme i cluster esistenti.

Scusate se alcune delle cose sembrano fondamentali, ma sono relativamente nuovo in questo campo. Grazie per l'aiuto.

Answer 1

Basta provarne. Ci sono così tanti algoritmi di clustering là fuori, nessuno li conoscerà tutti. Inoltre, dipende anche molto dal set di dati e dalla struttura di cluster che si trova lì. Alla fine, potrebbe esserci anche questo cluster di mostri rispetto alla distanza del coseno e alle funzioni di BofW.

Answer 2

Dato che siete entrambi nuovi sul campo, avete un numero sconosciuto di cluster e utilizzate già la distanza coseno, raccomanderei l'algoritmo di clustering FLAME.

È intuitivo, facile da implementare e ha implementazioni in un gran numero di lingue (non PHP, soprattutto perché pochissime persone usano PHP per la scienza dei dati).

Per non parlare, in realtà è abbastanza buono da essere utilizzato nella ricerca da un gran numero di persone.Se non altro, puoi avere un'idea di quali sono esattamente le carenze in questo algoritmo di clustering che vuoi indirizzare nel passaggio a un altro.

Answer 3

Forse è possibile trasformare la matrice di similarità in una matrice di dissomiglianza come trasformare x in 1/x, quindi il problema è raggruppare una matrice di dissomiglianza. Penso che il cluster gerarchico possa funzionare. Questi possono aiutarti: hierarchical clustering e Clustering a dissimilarity matrix