Come faccio a raggruppare le stringhe in base a una relazione tra due stringhe?

5

Se non conosci WEKA, puoi provare una risposta teorica. Non ho bisogno di codice / esempi letterali ...

Ho un enorme set di dati di stringhe in cui voglio raggruppare le stringhe per trovare quelle più correlate, che potrebbero anche essere viste come duplicate. Ho già una serie di coppie di stringhe per le quali so che sono duplicate tra loro, quindi, ora voglio fare del data mining su questi due set.

Il risultato che sto cercando è un sistema che mi restituisca le possibili coppie di stringhe più rilevanti per le quali non sappiamo ancora che siano duplicati, credo che ho bisogno di un cluster per questo, quale tipo?

Nota che voglio basarmi su confronto occorrenza parola , non su interpretazione o significato.

Ecco un esempio di due stringhe di cui sappiamo che sono duplicate (nella nostra visione su di loro):

  • Il tempo è molto freddo e piove.

  • Piove e fa molto freddo.

Ora esistono anche le seguenti stringhe (la maggior parte meno rilevanti, ignorando le parole di stop):

  • Oggi il clima è davvero freddo?

  • I giorni di pioggia sono orribili.

  • Vedo il sole fuori.

Il software restituirà le seguenti due stringhe come più rilevanti, che non sono noti per essere duplicati:

  • Il tempo è molto freddo e piove.

  • Oggi il clima è davvero freddo?

Quindi, lo contrassegnerei come duplicato o non duplicato e mi presenterebbe con un altro paio.

Come faccio ad implementarlo nel modo più efficiente in cui posso applicare a un set di dati di grandi dimensioni?

    
posta Tom Wijsman 15.08.2011 - 17:07
fonte

3 risposte

4

Questo è ovviamente non banale, ma ci sono algoritmi che almeno tentano di fare cose come questa. Mi affretto ad aggiungere, tuttavia, che sono statici, quindi provare a utilizzare solo due frasi come base sarà estremamente nel migliore dei casi.

L'approccio abituale è simile a questo:

  1. filtra le parole di arresto
  2. usa un thesaurus per sostituire una parola canonica per ogni parola
  3. conta le occorrenze di parole in ogni documento / frase
  4. calcola la distanza del coseno tra i documenti di base e ciascun candidato documento simile
  5. seleziona la N più vicina ai documenti di base

Nota che qui c'è spazio per molte variazioni. Ad esempio, il thesaurus può ottenere risultati considerevolmente migliori se è sensibile al contesto e per mantenere il contesto spesso si desidera mantenere le parole di stop, almeno fino al completamento di tale passaggio. Ad esempio, considera i tuoi documenti di base sul tempo che viene confrontato con: "Ho un raffreddore" e "Fa freddo". Se segui i passaggi precedenti, questi saranno entrambi "freddi" al punto 2, ed entrambi sembreranno ugualmente vicini ai documenti di base.

Con un passo del thesaurus sensibile al contesto (un'ontologia, davvero), useresti le parole in più per disambiguare i due usi del "freddo", quindi quando calcoli le distanze, si farebbe riferimento alla malattia chiamata "il freddo" "e l'altro a" tempo freddo ". I documenti di base si riferiscono entrambi al freddo, quindi il risultato mostrerebbe "È freddo" come simile, ma "Ho un raffreddore" come diverso.

Se stai cercando di mantenere le cose più semplici, tuttavia, potresti saltare completamente il lessico e invece limitare le parole. Questo diventa "piovoso" e "piove" entrambi in "pioggia", quindi quando fai confronti compariranno tutti come sinonimi.

Per quanto riguarda i dettagli, ci sono alcuni elenchi di stop-words facilmente trovato . Almeno nei miei test, la scelta non è particolarmente critica.

Per un thesaurus, ho utilizzato il Moby Thesaurus , con alcune elaborazioni (sostanziali) per in pratica l'inversione - - Ad esempio, anziché trovare più sinonimi per una parola, trova una parola canonica per un dato input.

Non ci sono tanti documenti sul contesto- sinonimo sensibile / ricerca di definizione - ma alcuni sono ancora abbastanza buoni . Un sacco di lavoro sul "web semantico" e sulle ontologie correlate è anch'esso lungo questa linea (anche se è poco probabile che sia di grande aiuto nel tuo caso).

Per lo stemming, il Porter Stemmer è ben noto. C'è una versione più recente, leggermente modificata (Porter2) che dovrebbe essere coperta da qualche parte sulla stessa pagina (s). Un altro algoritmo ben noto è Lancaster Stemmer . C'è anche lo stemmer di Lovins, ma non lo raccomanderei veramente 1 - sebbene sia ancora ampiamente conosciuto perché era il primo (ben noto) algoritmo di derivazione pubblicato. Si noti che la maggior parte (tutti?) Di questi strip hanno solo suffissi, non prefissi.

Alcuni documenti discutono la distanza del coseno. È abbastanza noto che anche la voce di Wikipedia è abbastanza decente.

Molte persone hanno già riunito questi pezzi in modo coerente (almeno in genere cercano di essere coerenti) toolkit, programmi completi, ecc. Alcuni esempi ragionevolmente noti includono WordNet , NLTK , Apache OpenNLP e Freeling .

1 In particolare, Lovins rimuove solo il suffisso one da una parola. Se tu avessi, per esempio, "Loverly" e "amorevolmente", Porter ridurrebbe entrambi a "lov" e si mostrerebbero come sinonimi, ma Lovins li ridurrebbe a "amante" e "amorevole", rispettivamente, e loro apparire come diverso. È possibile ripetere l'algoritmo Lovins fino a quando non rimuove più suffissi, ma il risultato non è molto buono - Porter ha un po 'di sensibilità al contesto quindi (per esempio) rimuove solo un suffisso se ha non rimuovi un altro; più applicazioni di Lovins non ne terrebbero conto.

    
risposta data 18.08.2011 - 06:59
fonte
1

Il documento Il raggruppamento dei dati a coppie per annealing deterministico sembra coprire esattamente ciò di cui hai bisogno: tu avere una misura di similarità a coppie e si desidera formare un certo numero di gruppi in base a questa misura. (Sono riuscito a trovare alcune pre-stampe full-text gratuite di questo articolo qualche tempo fa, quindi potresti non dover pagare per accedervi, purtroppo non ho il tempo di cercarle ancora adesso).

Ho usato questa tecnica in elaborazione del segnale ( vedi p15) , ma non il data mining basato su testo, quindi non sono sicuro di quanto potrò aiutarti con le specifiche.

    
risposta data 18.08.2011 - 07:00
fonte
0

Sembra troppo ambizioso. Questo è quasi equivalente alla comprensione di una frase.

Non riesco nemmeno a pensare a un modo per parametrizzare una frase; probabilmente non vuoi inserire solo due stringhe di caratteri nel tuo classificatore. Avresti bisogno di un modello molto complesso per descrivere il tuo problema e quindi un enorme set di dati. Il tuo modello avrebbe bisogno di imparare quali parole sono sinonimi / contrari ... tra molte molte cose che avrebbe bisogno di imparare.

    
risposta data 15.08.2011 - 17:41
fonte

Leggi altre domande sui tag