Il concetto di distanza

Nella vita siamo abituati a osservare il mondo e a cercare continuamente, a seconda della nostra attitudine mentale, similitudini o differenze. I temi della ricerca della distanza e della integrazione sono trattati oltre che dalla informatica, dalle scienze sociali, dalle scienze cognitive e dalla stessa filosofia. Il concetto di integrazione è spesso visto come un valore positivo (o osteggiato) nel grande problema dei migranti; in altri campi, nelle persone, nelle opere d’arte, negli stili letterari, noi continuamente cerchiamo similitudini o differenze (guarda come quel ragazzo assomiglia al padre…secondo me assomiglia più alla madre….).

In Figura 13 noi vediamo due casi in cui ci interessa trattare il problema di ciò che abbiamo chiamato distanza; nel caso 1 abbiamo tre testi che hanno parti del discorso simili: ma “quanto” simili?. Il caso 2 è quello che stiamo indagando. Le metriche che da più tempo sono utilizzate per esprimere il concetto di distanza sono quelle relative a dati espressi da stringhe di caratteri. Nel caso 2 di Figura 13 i record delle due tabelle hanno due campi in comune i cui valori corrispondono a stringhe di caratteri, i campi Nome e Cognome. Possiamo confrontare le stringhe di caratteri corrispondenti a Nome, a Cognome, e all’insieme Nome + Cognome, avendo la avvertenza di invertire le stringhe nella seconda tabella. In tutti i casi precedenti possiamo utilizzare per la distanza la edit distance, già introdotta informalmente nel Capitolo 5, Sezione 2. La edit distance (ED), corrisponde al numero di caratteri che dobbiamo cancellare, aggiungere, sostituire per trasformare la prima stringa nella seconda. Cosi’ ad esempio

ED <Carlo, Crlo> = 1 ED <Ratti, Reti> = 2.

164

Caso 1 – Tre testi

Caso 2 – I record di due tabelle

Figura 13 – Cosa è la distanza? Cosa è la somiglianza?

Figura 14 – Inserimento dei caratteri che suggerisce una modifica della formula dell’edit distance Si noti che esistono situazioni in cui possiamo modificare la formula della edit distance per tener conto di particolari tipi di errori. Ad esempio nel caso di Figura 14 può accadere che chi digita le lettere tenda a commettere continuamente l’errore di selezionare il tasto A al posto del tasto S; in questo caso possiamo modificare la formula dando un peso maggiore alla sostituzione S  A rispetto alle altre. La Edit distance, come in fondo dimostra l’ultimo caso visto in precedenza, è troppo generale per essere in grado di trattare una vasta casistica. In particolare la edit distance mostra i suoi limiti quando vogliamo confrontare insiemi di parole, come accade nel caso di Figura 15.

Nel mezzo del cammin di nostra vita Nel mezzo del camino della nostra casa Nel mezzo del cammino della nostra vita

Nome Cognome Città Nascita Regione N.

Crlo Batini Pscara Abruzzo

Gino Retti Roma Lazio

CF Cognome Nome Data Nascita

BTNCRL Batini Carlo 3-6-2000

165

Figura 15 – Un caso in cui la edit distance non va bene

Osservando le due tabelle, Intuitivamente noi facciamo corrispondere ad AT&T Corporation la stringa AT&T, e non IBM Corporation. Invece se calcoliamo la edit distance otteniamo:

ED <AT&T, AT&T Corporation> = 12

ED <IBM Corporation, AT&T Corporation> = 4

Considerati come stringhe di caratteri, sono dunque molto più simili IBM Corporation e AT&T Corporation rispetto a AT&T e AT&T Corporation. Quale è la ragione di questo risultato così contro intuitivo? La ragione risiede nel fatto che quando noi confrontiamo le due stringhe di caratteri non le vediamo come stringhe ma come sequenze di parole, e, viste come sequenze di parole, riconosciamo AT&T come abbreviazione di AT&T Corporation. Per cogliere questo aspetto, possiamo utilizzare la distanza di Jaccard, che calcola la distanza in due passi:

1. Prima si trasformano le stringhe in insiemi di parole: AT&T Corporation  <AT&T, Corporation> (insieme P1) IBM Corporation  <IBM, Corporation> (insieme P2)

2. A questo punto la metrica di distanza di Jaccard e’ DistJaccard = 1 - numero parole (P1  P2)/numero parole (P1  P2)

dove P1  P2 è l’insieme di parole comuni a P1 e P2 e P1  P2 è l’insieme delle parole di P1 a cui si aggiungono le parole di P2.

E’ facile vedere che:

Dist Jaccard <AT&T, AT&T Corporation> = 1 - ½ = 0,5

Dist Jaccard <IBM Corporation, AT&T Corporation> = 1 - 1/3 = 0,66

Si noti che la distanza di Jaccard funziona molto bene anche nel caso delle inversioni, come ad esempio Distanza <Carlo Batini; Batini Carlo>. Anche in questo caso la Edit Disance assume valore molto alto, mentre invece Dist Jaccard <Carlo Batini; Batini Carlo> = 1 – 1 = 0, le due stringhe di caratteri, viste come insiemi di parole, coincidono, perché nel concetto di insieme non c’è una relazione di ordine tra elementi dell’insieme.

Il concetto di distanza cambia a seconda del modello con cui sono rappresentati I dati. Similmente, nella nostra esperienza quotidiana, il confronto tra oggetti e artefatti si modifica se li consideriamo in

... ... ... AT&T ... ... IBM Corporation ... ... ... ... ... ... AT&T Corporation ... ... IBM Corporation Nomi di aziende 2 Nomi di aziende 1

166

isolamento, o nel contesto in cui essi operano o sono collocati. Consideriamo la struttura dati di Figura 16. I dati rappresentano persone che vivono in Africa (prima tabella), le regioni degli stati in cui risiedono (seconda tabella) e infine nella terza tabella gli stati in cui sono collocate le regioni. Le regioni nella seconda tabella e gli stati nella terza sono logicamente legati alle tabelle precedenti per mezzo di valori. In questo caso siamo interessati alla deduplicazione nella terza tabella, quella degli stati.

Figura 16 – Quando cambia la struttura dati, cambia il concetto di distanza

Figura 17 – Dalla distanza tra record alla distanza tra co-occorrenze di record

Se osserviamo la tabella degli stati di Figura 16 e applichiamo la metrica della edit distance, chiaramente sono molto più simili SOA e SWA, e poco simili KE e Kenia. In effetti basta ragionare un attimo sulla

Idp Nome Cognome IdReg

1 Patrick Mezisi 1 2 Amanda Rosci 2 3 George Oado 3 4 John Mumasia 4 5 Vusi Oymo 7 6 Luyo Msgula 5 7 Frial Keyse 8 8 Wania Nagu 6 9 Paul Kohe 7

IdP Regione IdPaese

1 MM 1 2 MM 2 3 Masai Mara 1 4 Eastern Cape 3 5 Free State 3 6 FS 4 7 HHohho 5 8 Lumombo 6 IdPaese Paese 1 KE 2 Kenia 3 SOA 4 South Africa 5 SWA 6 Swaziland Prima tabella Seconda tabella Terza tabella

Idp Nome Cognome IdReg 1 Patrick Mezisi 1 2 Amanda Rosci 2 3 George Oado 3 4 John Mumasia 4 5 Vusi Oymo 7 6 Luyo Msgula 5 7 Frial Keyse 8 8 Wania Nagu 6 9 Paul Kohe 7

IdP Regione IdPaese

1 MM 1 2 MM 2 3 Masai Mara 1 4 Eastern Cape 3 5 Free State 3 6 FS 4 7 HHohho 5 8 Lumombo 6

IdPa ese Pa ese

1 KE 2 Keni a 3 SOA 4 South Afri ca 5 SWA 6 Swa ziland

Idp Nome Cognome IdReg

1 Patrick Mezisi 1 2 Amanda Rosci 2 3 George Oado 3 4 John Mumasia 4 5 Vusi Oymo 7 6 Luyo Msgula 5 7 Frial Keyse 8 8 Wania Nagu 6 9 Paul Kohe 7

IdP Regione IdPaese

1 MM 1 2 MM 2 3 Masai Mara 1 4 Eastern Cape 3 5 Free State 3 6 FS 4 7 HHohho 5 8 Lumombo 6 IdPaese Paese 1 KE 2 Kenia 3 SOA 4 South Africa 5 SWA 6 Swaziland

167

forma delle stringhe per arrivare alla conclusione che in alcuni casi le stringhe sono nomi di stati, in altri appaiono come acronimi o abbreviazioni. Questa osservazione è ben sostanziata dalla seguente idea: invece che considerare i nomi degli stati in isolamento, perché non li consideriamo nel contesto delle regioni che in essi sono collocate? Seguendo questo approccio, vediamo (Figura 17) che gli stati con nomi KE e Kenia hanno regioni in comune (vedi la parte superiore della Figura 17), mentre gli stati con nome SOA e SWA fanno riferimento a regioni diverse (parte inferiore della Figura 17).

Considerare il contesto è fondamentale nella comunicazione tra esseri umani come nella scoperta di similitudini e differenze, diverse tecniche semantiche che che verranno discusse nel Capitolo 8 applicano proprio questa filosofia). Come abbiamo anticipato nel Capitolo 1, se in due documenti compare un nome “Roma”, per capire se si fa riferimento alla capitale d’Italia o a un quartiere di Buenos Aires, potremo considerare le parole che contornano i due termini Roma, che chiamiamo parole di contesto, associarli alla loro posizione in lessici o in Wikipedia sul Web, e poi decidere sulla base dell’insieme delle distanze tra i due insiemi di parole di contesto.

Rientra nei metodi che estendono le distanze lessicografiche con regole semantiche anche il seguente esempio di deduplicazione. Stiamo considerando una tabella, vedi Figura 17, che riporta informazioni sui pensionati americani, sul loro reddito e sugli Stati in cui risiedono per una parte dell’anno. Negli USA è frequente che pensionati con alto reddito risiedano per una parte dell’anno, ad esempio d’estate, in stati del Nord, e l’altra parte dell’anno in stati del Sud, vedi Figura 18.

Figura 18 – Esempio dei pensionati americani

Numero Nome Cognome Stato Età Reddito in $

1 Ann Albright Arizona 65 70.000

2 An Olbrgth Washington 65 70.000

3 Ann Allbrit Florida 85 15.000

4 Ann Alson Louisiana 72 70.000

5 Annie Albight Vermont 85 15.000

6 Annie Allson Florida 72 70.000

7 Georg Allison Vermont 71 66.000

168

Figura 19 – Conoscenza aggiuntiva sui pensionati USA che può essere sfruttata nel record linkage (da www.commons.wikimedia.com)

Ci troviamo quindi di fronte a conoscenza aggiuntiva sui record della tabella, che possiamo sfruttare nella formula che esprime la distanza. Se non consideriamo tale conoscenza aggiuntiva, prendiamo in considerazione Nome e Cognome, e consideriamo la distanza = 3 come soglia della edit distance per decidere se accoppiare i record, allora risultano accoppiati (vedi in Figura 20 i diversi livelli di grigio) i record <1,2,5> , <4,6> e <7,8>.

Figura 20 – Corrispondenze nel caso di applicazione della edit distance

Figura 21 – Corrispondenze tenendo conto nella distanza della conoscenza aggiuntiva

Record # First Name Last Name Country Age Income

1 Ann Albright Arizona 65 70.000

2 An Olbrgth Washington 65 70.000

3 Ann Allbrit Florida 85 15.000

4 Ann Alson Louisiana 72 70.000

5 Annie Albight Vermont 85 15.000

6 Annie Allson Florida 72 70.000

7 Georg Allison Vermont 71 66.000

8 George Alsn Florida 71 66.000

Record # First Name Last Name Country Age Reddito

1 Ann Albright Arizona 65 70.000

2 An Olbrgth Washington 65 70.000

3 Ann Allbrit Florida 25 15.000

4 Ann Alson Louisiana 72 70.000

5 Annie Albight Vermont 25 15.000

6 Annie Allson Florida 72 70.000

7 Georg Allison Vermont 71 66.000

169

Se invece prendiamo in considerazione gli Stati citati nei record, secondo la formula Nord/Sud, e accettiamo una maggiore distanza di edit pari a 5, allora gli accoppiamenti diventano <1,2>, <3,5> e <7,8>, vedi Figura 21.