Raggruppamento di stringhe sulla base di sottostringhe comuni

Question

Raggruppamento di stringhe sulla base di sottostringhe comuni

#1 da (1 voti)
#2 da (-1 voti)

6

Ho circa 10000+ stringhe e devo identificare e raggruppare tutte le stringhe che sembrano simili (baso la somiglianza sul numero di parole comuni tra due stringhe). Più numero di parole comuni, più simili sarebbero le stringhe. Ad esempio:

Come creare un altro livello da un livello esistente
Impossibile modificare i dati sull'unità di rete
Livelli esistenti nel desktop
Assistenza con l'unità di rete

In questo caso, le stringhe 1 e 3 sono simili con le parole comuni Esistente, Strato e 2 e 4 sono simili con parole comuni Network Drive (eliminando la parola di arresto)

I passaggi che seguo sono:

Fai scorrere il set di dati
Esegui un confronto riga per riga
Trova le parole comuni tra le stringhe
Forma un cluster in cui il numero di parole comuni è maggiore o uguale a 2 (eliminando le parole di arresto)
Se numero di parole comuni < 2, inserisci la stringa in un nuovo cluster.
Assegna le righe ai cluster esistenti o ne crea una nuova a seconda delle parole comuni
Continua fino a quando tutte le stringhe vengono elaborate

Sto implementando il progetto in C # e ho completato il passaggio 3. Tuttavia, non sono sicuro di come procedere con il clustering. Ho studiato molto sul clustering di stringhe, ma non ho trovato nessuna soluzione adatta al mio problema. I tuoi contributi sarebbero molto apprezzati.

c# sql strings cluster data-mining

posta pk188 26.06.2013 - 23:20

fonte

2 risposte

Leggi altre domande sui tag c# sql strings cluster data-mining

Autenticazione di Facebook con un server autorevole per un gioco Flash Quanti dettagli tecnici sono eccessivi quando si parla di manager non tecnici?

score 1 · Answer 1

Una tecnica che può essere utilizzata per eseguire il clustering su dati numerici multidimensionali è la mappa delle funzionalità auto-organizzanti di Kohonen. È un po 'troppo complicato da descrivere qui, ma dovrebbe essere incluso nel testo di ogni principiante sull'apprendimento automatico.

Questo lascia solo il problema di come convertire i dati in forma numerica. Per fare questo, prima eseguivo un'analisi per trovare un numero ragionevole (ad esempio 100) di parole che appaiono in molte stringhe, ma non troppe. Stai cercando le parole nel mezzo della distribuzione di frequenza, poiché queste contengono le informazioni più utili. Puoi quindi utilizzare la presenza o l'assenza di queste parole come input per la tua mappa delle caratteristiche.

score -1 · Answer 2

Simile a questa domanda / risposta e ho usato l'algoritmo c # pubblicato lì in passato e funziona come un fascino ecco l'algoritmo della risposta collegata:

public class SimilarityTool
{
    public double CompareStrings(string str1, string str2)
    {
        List<string> pairs1 = WordLetterPairs(str1.ToUpper());
        List<string> pairs2 = WordLetterPairs(str2.ToUpper());

        int intersection = 0;
        int union = pairs1.Count + pairs2.Count;

        for (int i = 0; i < pairs1.Count; i++)
        {
            for (int j = 0; j < pairs2.Count; j++)
            {
                if (pairs1[i] == pairs2[j])
                {
                    intersection++;
                    pairs2.RemoveAt(j);//Must remove the match to prevent "GGGG" from appearing to match "GG" with 100% success

                    break;
                }
            }
        }

        return (2.0 * intersection) / union;
    }