fuzzy matching dei dati strutturati

Question

Ho un abbastanza piccolo corpus di documenti strutturati che si siedono in un database. Data una piccola frazione delle informazioni contenute in un singolo record, presentata tramite un modulo web (in modo strutturato allo stesso modo come lo schema della tabella), (chiamiamolo così il record di prova) ho bisogno di disegnare rapidamente un elenco di record che sono le partite più probabili per il record di prova, oltre a fornire una stima fiducia di quanto strettamente i termini di ricerca corrispondono a un record. Lo scopo principale di questa ricerca è quello di scoprire se qualcuno sta tentando di inserire un record che è duplicato a uno nel corpus. C'è una ragionevole possibilità che il record di test sarà una vittima, e una ragionevole possibilità il record di prova non sarà una vittima.

I record sono circa 12000 byte di larghezza e il numero totale di record è di circa 150.000. Ci sono 110 colonne nella schema della tabella e il 95% delle ricerche saranno sulla parte superiore del 5% più comunemente cercato colonne.

I dati sono cose come nomi, indirizzi, numeri di telefono e altri numeri specifici del settore. In entrambi corpus e il record di prova viene inserito manualmente e viene semistrutturata all'interno di un singolo campo. Si potrebbe a prima vista dire "il peso delle colonne a mano e partita di parola gettoni al loro interno", ma non è così facile. Lo pensavo anch'io: se ho un numero di telefono ho pensato che possa indicare una corrispondenza perfetta. Il problema è che non v'è un singolo campo nella forma cui frequenza token non variare di ordini di grandezza. Un numero di telefono può apparire 100 volte nel corpus o 1 volta nel corpus. Lo stesso vale per qualsiasi altro campo. Questo rende ponderazione a livello di campo impraticabile. Ho bisogno di un approccio più a grana fine per ottenere corrispondenza decente.

Il mio piano iniziale era quello di creare un hash di hash, di alto livello essendo il fieldname. Allora avrei selezionare tutte le informazioni dal corpus per un dato campo, tentare di ripulire i dati in esso contenuti, e tokenize i dati sterilizzate, hashing i gettoni al secondo livello, con i token come chiavi e frequenza come valore.

Vorrei utilizzare il conteggio delle frequenze come un peso: più alta è la frequenza di un token nel corpus di riferimento, meno peso che attribuisco a quella pedina se si trova nel record di test

.

La mia prima domanda è per gli statistici in sala: come vorrei usare la frequenza come un peso? Esiste un preciso rapporto matematico tra n, il numero di record, f (t), la frequenza con cui un token t è apparso nel corpus, la probabilità o che un record è un originale e non un duplicato, e la probabilità p che il record di prova è davvero un record x dato il test e x contengono la stessa t nello stesso campo? Come circa il rapporto per il gettone più corrispondenze su più campi?

Da quando ho sinceramente dubito che ci sia, c'è qualcosa che mi viene vicino, ma è meglio di un hack del tutto arbitrario pieno di fattori magici?

A parte ciò, qualcuno ha ottenuto un modo per fare questo?

Sono particolarmente appassionato di altri suggerimenti che non comportano il mantenimento di un'altra tabella nel database, come ad esempio una tabella di ricerca di frequenza token.

Answer 1

Probabilmente si potranno ottenere alcune idee da questo diverso ma simile SO domanda: calcolo-context-sensitive-text-correlazione .

Più specifico per il problema in questione, qui ci sono un paio di pensieri e idee:

Prima di tutto, riconoscendo l'utilizzo molto inclinata (solo 6 a 10 attributi coprono il 95% di utilizzo), si può / dovrebbe applicare lo sforzo asimmetrica sugli attributi, cioè investire di più, sia in termini di tempi di programmazione e in termini di run-time assegnazione di CPU, per trattare con questi pochi attributi che per attributi aggiuntivi 100-dispari.

La relativamente piccola quantità di dati forniti come input per la corrispondenza possibili duplicati nel database, il relativamente piccolo insieme di attributi tipicamente usato, e la semantica, apparentemente comuni di queste (numero di telefono, indirizzo, nome ...) suggeriscono una mano soluzione -crafted piuttosto che uno completamente sulla base di apprendimento automatico.

Nota: un sacco di suggerimenti da allora in poi non devono essere applicati a tutti gli attributi (da meno di una dozzina di questi coprono praticamente tutto il loro utilizzo, non v'è alcun punto, almeno in un primo momento di investire molto con gli altri attributi .

• Normalizzare i dati
  Se non è consentito per voi di modificare i valori dei campi originali forse duplicano le colonne corrispondenti ad una coluumn "norm_xxx" dove xxx è il nome originale.
  Cosa, Come normalizzare può variare con ogni attributo; per "testo libero" come dati, assicurarsi che non vi siano spazi iniziali né finali, solo uno spazio tra parole, senza schede e caratteri non stampabili. Utilizzare uno tutto maiuscolo o tutto minuscolo (eventhought il per-visualizzazione del testo / originale può includere un mix, il vostro trattamento sarà andare più veloce da essere in grado di assumere involucro uniforme). In particolare per gli indirizzi e / o nomi di società, è possibile convertire i termini comuni ad un modulo standard (ST per STREET, ST e ST, ecc) (Essere sicuri di mantenere questo elenco per esso verrà applicato ai criteri di ricerca dell'utente come pure ). Parte della normalizzazione può anche essere del tutto a cadere qualche parola di rumore (come dire CO, INC, GMBH alla fine di nomi di società)
• Crea un paio di colonne calcolate
  Ad esempio quelli con il testo, al contrario, per gli attributi che possono essere cercati con un carattere jolly finale
• Considerare l'utilizzo di una conversione Soundex simile per alcuni attributi.
• indice full-text, individualmente, tutte le colonne di testo come
• Crea pianura indici (SQL) su tutti i 6 a 10 colonne molto utilizzati

Tutti i precedenti, sono semplici preparazioni tempo off-line per le partite che effettua. Ora .. l'utente immette il suo / la sua interrogazione ... qui ci sono un paio di idee su come trattare con esso

• normalizzare i criteri che giustificano lo
• Esegui varie ricerche ...
  Questo è un po 'complicato; ci sono diversi, in parte in conflitto, gli obiettivi per l'esecuzione di questi ricerca. Noi vogliamo ridurre, in modo significativo il numero di "potenziali partite": è effettivamente poco pratico per fare un pieno one-to-one a confronto di tutti i 150.000 record con i criteri forniti dall'utente; per esempio alcuni della logica di corrispondenza può implicare calcolare la distanza di montaggio tra un campo di un determinato record del database e un criterio di ricerca. Vogliamo anche assicurare non escludiamo record dalla lista "corrispondenze potenziale" a causa di un errore di battitura nel dire il nome della società ... Infine vogliamo fornire l'elenco di possibili corrispondenze in maniera classificato.
  Il modo per eseguire queste ricerche segue alcune euristiche predefinite (ho trovato il lavoro strategia di design pattern bene per questo, che consente flessibilità nel modo in cui la ricerca vengono eseguiti, a seconda dell'input fornito dall'utente). In poche parole abbiamo cercare le parole più selettivi negli attributi più selettivi / rilevanti, e in base al numero di "hits" sono state trovate ci sia "OR" (unione) o "E" con altri risultati di ricerca, finché abbiamo un paio centinaia di record.
• Calcolare un valore somiglianza tra ogni attributo dei record "potenziali partite" e dei relativi criteri di ricerca. applicare eventualmente un coefficiente a questo valore (che consente di mettere più peso a dire un nome di società [parziale] corrispondere a quello di una partita di Città)
• Tally il valore similarità overal per un record completo (contro i criteri di ricerca completi)

• Mostra i record superiore a una determinata soglia del valore somiglianza con l'utente finale, per la revisione

  Infine, e arriva un processo parzialmente automatizzato, è possibile modificare alcuni parametri basato su un feedback fornito dal finale. (Questo è molto difficile da fare, terrò questo per qualche altro post ;-))