Duplicaatdetectie

Een vaak voorkomend probleem bij masterdata is dat verschillende records verwijzen naar dezelfde entiteit in de echte wereld. Dit kan bv. voorkomen wanneer een klant dubbel werd geregistreerd (één keer bij het eerste contact met het bedrijf en een tweede keer wanneer er effectief een bestelling werd geplaatst.), of wanneer een product dubbel werd aangemaakt.

Op het eerste zicht lijkt het ontdekken van duplicaten eenvoudig op te lossen: overloop alle recordparen en verifieer of ze gelijk zijn of niet. In de praktijk is dit echter heel wat moeilijker omdat duplicate records vaak wel gelijkaardig zijn maar niet helemaal gelijk. De vraag is dan om deze gelijkaardige recordparen te identificeren.

Eén kolom vergelijken

Vooraleer men start met het vergelijken van volledige records ligt het voor de hand om te kijken hoe men de waarden in één enkele kolom met elkaar kan vergelijken. Hierbij veronderstellen we dat de waarden in een kolom van het type "string" zijn. Wat men dan typisch wenst is een similariteitsmaat die kan aangeven hoe gelijkaardig twee strings zijn. Zo'n similariteitsmaat neemt als invoer twee strings en heeft als uitvoer een getal dat aangeeft hoe gelijkaardig de twee strings zijn, waarbij de waarde 1 meestal staat voor "perfect gelijk" en de waarde 0 voor "helemaal niet gelijk". Soms gebruikt men ook afstandsmaten: bij een afstandsmaat is de betekenis precies omgedraaid: een afstand gelijk aan nul betekent dat de strings gelijk zijn, en hoe groter de (waarde van de) afstand hoe meer verschillend de strings zijn.

De verschillende manieren waarop de similariteit van (of afstand tussen) twee strings kan worden bepaald kunnen onderverdeeld worden in een aantal categorieën:

• Karaktergebaseerde methoden
• Tokengebaseerde methoden
• Methoden gebaseerd op de uitspraak van de woorden/strings
• Methoden gebaseerd op woord-semantiek

 

Karaktergebaseerde methoden

Zoals de naam suggereert werken karaktergebaseerde methoden op het niveau van individuele karakters. Deze methoden geven goede resultaten wanneer men verwacht dat de oorzaak van de fouten kleine tikfouten zijn, waardoor bv. twee letters van plaats worden gewisseld of er per ongeluk een klein aantal karakters worden toegevoegd. Binnen deze categorie herkennen we de volgende afstandsmaten:

• Edit afstand: deze afstandsfunctie is goed in het herkennen van kleine typografische fouten.
• "Affine gap" afstand: deze afstandsfunctie houdt rekening met het feit dat eens men een extra karakter heeft ingevoegd men waarschijnlijk nog bijkomende extra karakters zal invoegen.
• Afstand gebaseerd op n-grammen. Hierbij wordt er gekeken hoeveel n-grammen twee strings gemeenschappelijk hebben, waarbij de intuïtie is dat gelijkaardige strings veel n-grammen gemeenschappelijk hebben maar strings die veel van elkaar verschillen niet.

Hieronder geven we nog een korte uitleg over elk van deze 3 afstandsmaten, samen met eventuele verwijzingen naar andere pagina's waar je alles in meer detail kan nalezen.

 

Edit afstand

De edit of Levenshtein afstand bekijkt in essentie hoeveel veranderingen, tussenvoegingen en verwijderingen er minimaal nodig zijn om de twee strings in elkaar om te zetten. Zo is bv. de Levenshtein afstand tussen "boekenkast" en "boeekekzst" gelijk aan drie.

 

boeekekzst (verwijdering) => boekekzst (verandering) => boekekast (toevoeging) => boekenkast

"Affine gap" afstand

Wanneer strings werden afgebroken of verkort, dan geeft de edit afstand soms een grote waarde aan, terwijl het wel degelijk over dezelfde entiteit gaat. Een voorbeeld hiervan zijn de strings "John R. Smith" en "Jonathan Richard Smith". Bij de "affine gap" afstand past men de Levenshtein afstand aan door het introduceren van twee additionele bewerkingen, nl. het "openen" van een gat en het "uitbreiden" van een gat, waarbij typisch het openen van een gat een grotere kost heeft (i.e. aanleiding zal geven tot een grotere afstand) dan het uitbreiden van een gat. De redenering is dat eens men een extra eerste karakter heeft getypt men wellicht nog meerdere extra karakters zal typen.

Bij wijze van voorbeeld berekenen we de affine gap afstand tussen de woorden "Boulevard" en "Blvd".

Boulevard (1 verwijdering) => Bulevard
Bulevard (0.5 opeenvolgende verwijdering) => "Blevard"
Blevard (1 verwijdering) => Blvard
Blvard (1 verwijdering) => Blvrd
Blvrd (0.5 opeenvolgende verwijdering) => Blvd

De totale afstand tussen "Boulevard" en "Blvd" is m.a.w. gelijk aan 4, terwijl die met de gewone edit-afstand gelijk zou zijn aan 5.

Afstand gebaseerd op n-grammen

Een n-gram van een string is niets anders dan een opeenvolging van n karakters van die string. Bv. alle 2-grammen van "boeken" zijn "bo", "oe", "ek", "ke" en "en". De 2-grammen van "beeken" zijn "be", "ee", "ek", "ke" en "en". Om de afstand, gebaseerd op 2-grammen, te berekenen tussen deze twee woorden bekijkt men alle 2-grammen die in minstens één van de twee woorden voorkomen en men bekijkt de absolute waarde van het verschil tussen het aantal voorkomens in beide woorden. Voor het gegeven voorbeeld zijn alle 2-grammen:

2-gram	boeken	beeken	verschil
bo	1	0	1
oe	1	0	1
ek	1	1	0
ke	1	1	0
en	1	1	0
be	0	1	1
ee	0	1	1

De afstand tussen "boeken" en "beeken" gebaseerd op 2-grammen is m.a.w. gelijk aan 4.

Tokengebaseerde methoden

Wanneer woorden van plaats werden verwisseld in twee strings, dan zullen karaktergebaseerde methoden hier typisch een grote afstand (of een lage similariteit) aan toeschrijven. Methodes gebaseerd op "tokens" trachten hiervoor een oplossing te bieden.

We sommen hieronder een aantal tokengebaseerde methoden op:

• Methode gebaseerd op "atomic strings"
• Deze methode zal typisch goed werken wanneer bepaalde woorden soms worden afgekort.
• Een methode waarbij n-grammen worden gecombineerd met "tf.idf"

 

"Atomic strings" methode

Met een "atomic string" wordt in deze context een sequentie van alfanumerieke karakters bedoeld die begrensd wordt door andere karakters. We zeggen dat twee "atomic strings" een overeenkomst opleveren wanneer ze gelijk zijn of wanneer één van de twee een prefix is van de andere. Bv. "Univ" en "University" komen overeen want de eerste is een prefix van de tweede.

De similariteit tussen twee strings A en B wordt bij deze methode gedefinieerd als het aantal atomic strings van A die een match opleveren met een atomic string van B gedeeld door het gemiddeld aantal atomic strings in de strings A en B.

Bij wijze van voorbeeld: veronderstel dat

• string A gelijk is aan "Comput. Sci. & Eng. Dept., University of California, San Diego"
• en dat string B gelijk is aan "Department of Computer Science, Univ. Calif., San Diego"

De atomic strings zijn dan

• Voor string A: "Comput", "Sci", "Eng", "Dept", "University", "of", "California", "San", "Diego"
• Voor sting B: "Department", "of", "Computer", "Science", "Univ", "Calif", "San", "Diego"

De volgende atomic strings van A geven een match met een atomic string van B:

• "Comput" match met "Computer"
• "Sci" match met "Science"
• "University" match met "Univ"
• "of" match met "of"
• "California" match met "Calif"
• "San" match met "San"
• "Diego" match met "Diego"

 

Het aantal atomic strings van A die matchen met een atomic string van B is bijgevolg gelijk aan 7. Gemiddeld hebben string A en B (9 + 8)/2 = 8.5 atomic strings. De similariteit, gebaseerd op deze methode van atomic strings, tussen A en B is bijgevolg: 7/8.5 = 0.82.

Als men het stopwoord "of" zou weglaten dan wordt de similariteit op basis van deze methode 6/7.5 = 0.8.

n-grammen gecombineerd met tf.idf

tf.idf, wat de afkorting is voor "term frequency, inverse document frequency" is een getal dat aangeeft hoe belangrijk een woord is voor de inhoud van een document t.o.v. een collectie van documenten. Termen die vaak voorkomen in een document hebben een hoge "term frequency". Wanneer een term evenwel in veel documenten voorkomt dan heeft deze ook een grote "document frequency". Om de tf.idf van een woord in een document te bepalen wordt de "term frequency" gedeeld door de "document frequency". Men krijgt dus enkel een hoge "tf.idf" voor een bepaald woord in een document als dit woord vaak voorkomt in dit document en in niet veel andere documenten voorkomt.

Als volgende stap kan men alle termen die voorkomen in alle documenten in een bepaalde volgorde plaatsen (bv. alfabetisch). Eén enkel document kan dan als het ware samengevat worden door een (zeer lange) lijst van getallen, waarbij elk getal de tf.idf is van een bepaalde term.

Het vergelijken van lange lijsten van getalle (i.e. van "vectoren") is een probleem dat reeds diepgaand werd bestudeerd. Eén van de typische manieren om zo'n lijsten van getallen met elkaar te vergelijken is de zogenoemde cosine similarity. Wanneer twee lijsten van getallen precies gelijk zijn dan geeft deze een waarde gelijk aan +1, wanneer ze precies tegengesteld zijn is de waarde gelijk aan -1. Als men gelijkaardige documenten wil identificeren dan zoekt men dus naar documenten waarvoor de cosine similarity van hun tf.idf lijsten "groot" is.

Binnen de context van tabellen in databanken zijn er maar weinig velden die genoeg verschillende woorden bevatten om de tf.idf op een zinvolle manier te kunnen berekenen. De techniek bestaat er nu in om de bovenvermelde procedure toe te passen op n-grammen van de velden. Dit is m.a.w. de eerste techniek die om twee strings met elkaar te vergelijken ook de inhoud van alle (andere) strings in dezelfde kolom nodig heeft.

Fonetische methoden

Deze methoden zijn typisch zeer specifiek en taalafhankelijk. Hierbij worden woorden vergeleken op basis van hun uitspraak. Woorden met een gelijkaardige uitspraak krijgen een hogere similariteit toegekend.

Methoden gebaseerd op woord semantiek

Maar wat als we woorden vergelijken die syntactisch helemaal niet op elkaar lijken, maar die wel hetzelfde betekenen? De woorden 'Auto' en 'Wagen' zijn bijvoorbeeld synoniemen van elkaar, maar zouden met de voorgaande besproken methoden weinig tot geen similariteit kennen. We kunnen de similariteit van woorden bepalen door hun woordvectoren, ofwel “word embeddings” te vergelijken. Woordvectoren kunnen worden gegenereerd met een algoritme als word2vec: Zoals de naam al aangeeft, vertegenwoordigt word2vec elk afzonderlijk woord met een bepaalde lijst van getallen, een vector genaamd. De vectoren worden zorgvuldig gekozen zodat een eenvoudige wiskundige functie (de cosinusgelijkheid tussen de vectoren) de mate van semantische overeenkomst aangeeft tussen de woorden die door die vectoren worden vertegenwoordigd. In essentie wordt een woord omgevormd tot een sequentie van een 300-tal getallen en zullen deze sequenties van getallen sterk op elkaar lijken waneer men woorden vergelijkt die dezelfde betekenis hebben.

Deze methoden zullen goed werken wanneer de woorden in een kolom algemeen bestaande woorden zijn; wanneer het gaat over een specifiek jargon dan zullen de woorden misschien niet herkend worden of zullen de vectoren waarop ze worden afgebeeld niet noodzakelijk het juiste gedrag vertonen qua similariteit.

Vergelijken van records

Door het toepassen van de voorgaande éénkolomsmethoden op paren van records, krijgen we een (groot aantal) records waarvan de velden getallen zijn. We noemen zo'n record een vergelijkingsrecord. Ieder veld in zo'n vergelijkingsrecord geeft aan hoe gelijkaardig of verschillend de originele waarden in de overeenkomstige kolommen zijn.

Eigenlijk willen nu voor elk dergelijk vergelijkingsrecord aangeven of het een mogelijk duplicaat is of niet, i.e. of de originele records duplicaten zijn of niet. Dit probleem kunnen we op verschillende manieren aanpakken.

Enerzijds zijn er gesuperviseerde methoden waarbij we een binair classificatiealgoritme trainen om de duplicaten te detecteren. Het probleem hierbij is dat zo'n algoritme typisch een grote hoeveelheid gelabelde data nodig heeft. Dat is niet zo interessant omdat het aanmaken van zo'n gelabelde dataset een grote inspanning vergt.

Interessanter is om de duplicaten te herkennen op basis van een ongesuperviseerde methode, i.e. een methode die kan werken zonder gelabelde data. De onderliggende gedachte is dat de vergelijkingsrecords er "anders" zullen uitzien voor duplicaten in vergelijking met "niet-duplicaten". Intuïtief kunnen we voor duplicaten verwachten dat ze veel hoge similariteiten vertonen, terwijl dat voor niet-duplicaten wellicht niet het geval is.

Een eerste ongesuperviseerde methode die men kan proberen is een (harde) clusteringsmethode zoals het k-gemiddelden algoritme . In dit geval zouden we typisch werken met 2 klassen. Nadat het algoritme werd uitgevoerd zullen de vergelijkingsrecords onderverdeeld zijn in twee klassen. We kunnen aannemen dat de kleinste klasse de klasse is die de duplicaten bevat (omdat we er van uitgaan dat er veel minder duplicaten zijn dan niet-duplicaten). Deze kunnen dan gepresenteerd worden aan de gebruiker ter controle.

Het grootste nadeel van harde clusteringsmethodes is dat deze een ja/nee antwoord geven en dat ze niet kunnen aangeven hoe "zeker" ze zijn over hun antwoord. Daarvoor zijn er andere methodes nodig die de (on)zekerheid in hun antwoord kunnen aangeven.

Een Gaussian mixture model kan gezien worden als een "zachte" versie van het (harde) k-means clusteringsalgoritme. Na het uitvoeren van dit algoritme heeft elk record een zekere "kans" om tot een bepaalde cluster te behoren. De wiskundige details zijn relatief ingewikkeld maar opnieuw kunnen we veronderstellen dat de "kleinste" cluster diegene is die de duplicaten voorstelt. In dit geval kunnen we enkel de meest "duidelijke" (kandidaat) duplicaten aan de gebruiker tonen ter verificatie.

Gesuperviseerd leren heeft het probleem dat een grote hoeveelheid gelabelde data nodig is; bij ongesuperviseerd leren is dit niet het geval maar hier is het ook niet altijd duidelijk of een record(paar) een duplicaat is of niet. Bij active learning gaat het algoritme zelf op zoek naar recordparen die (voor het algoritme) het meest informatief zijn; dit zullen typisch recordparen zijn die tamelijk "ambigu" zijn. Deze records worden dan getoond aan de gebruiker met de vraag om deze te labelen.

Beperken van het aantal te vergelijken records

Wanneer men algoritmen uitvoert dan is het belangrijk dat deze binnen een redelijke tijd eindigen. Hier kan een addertje onder het gras zitten bij duplicaatdetectie. Wanneer men bv. 1000 records heeft dan is het aantal paren ongeveer 500.000! (Het precieze aantal is 1000 * 999 / 2 = 499.500 maar 500.000 rekent duidelijk gemakkelijker.) Voor een datasets met 10.000 records is het aantal paren al ongeveer 50.000.000! Zelfs voor snelle en krachtige computers kan dit al snel een probleem vormen. Als men dit technisch wil uitdrukken zegt men dat het aantal paren van de orde n² is, waarbij n het aantal records voorstelt.

In bepaalde gevallen heeft men echter domeinkennis waardoor men weet dat records die verschillen in een bepaalde kolom (of in de beginletters van een kolomwaarde) hoogstwaarschijnlijk geen duplicaten zijn. Dit kan men dan gebruiken om het aantal te vergelijken records sterk te beperken.

Bij wijze van voorbeeld: stel dat men een klantenlijst heeft en dat men geslacht van de klant heeft genoteerd. Om het voorbeeld eenvoudig te houden veronderstellen we dat er slechts twee mogelijke waarden zijn, nl. 'M' en 'V'. Hoewel het mogelijk is dat het geslacht verkeerd werd genoteerd en er dus dubbels voorkomen tussen 'M' en 'V' lijkt dit onwaarschijnlijk. Als we nu veronderstellen dat er 1000 klanten zijn waarvan er 500 'M' en 500 'V' zijn, en we vergelijken enkel binnen de 'M' en 'V' dan is het aantal te vergelijken records ongeveer 125.000 (voor 'M') en 125.000 (voor 'V'). Samen is dit 250.000, en dus ongeveer de helft van wat het aantal te vergelijken records zonder deze opdeling.

Als we nog meer kunnen opdelen, dan wordt de winst nog groter. Stel dat er een bepaalde kolom is met 10 verschillende waarden die elk 100 keer voorkomen (i.e. er zijn nog steeds 1000 records) en dat het zeer onwaarschijnlijk is dat er twee records een duplicaat zijn wanneer ze een verschillende waarde hebben voor deze kolom. Als we zoals reeds gezegd aannemen dat elke waarde 100 keer voorkomt dan is het aantal te vergelijken records ongeveer gelijk aan 10 keer 5000 wat gelijk is aan 50.000. Vergelijk dit met de 500.000 records die we vinden zonder deze opdeling.

De technische naam voor deze opdeling is blocking, en is cruciaal om duplicaatdetectie schaalbaar te maken.

Python-bibliotheken voor duplicaatdetectie

Het is ondertussen wellicht duidelijk geworden dat het volledig zelf implementeren van een algoritme voor duplicaatdetectie redelijk wat werk zal vragen. Gelukkig zijn er reeds implementaties beschikbaar van deze verschillende methoden in gemakkelijk te gebruiken Python-bibliotheken. Enkele voorbeelden hiervan zijn:

• Dedupe.io Volgens hun website zal dedupe je helpen om:
  • duplicaten te verwijderen uit een spreadsheet van namen en adressen
  • een lijst met klanteninformatie te linken aan bestelling, zelfs al is er geen uniek klantenID aanwezig.
  Deze tool heeft ook een commercieel alternatief, nl. dedupe.io.
• deduplipy Een Python-bibliotheek die gebruikmaakt van active learning om duplicaten te ontdekken en die volgens de website "out-of-the-box" kan gebruikt worden maar tegelijkertijd ook geavanceerde gebruikers de mogelijkheid geeft om het algoritme af te stellen naar hun eigen wensen.
• zeroER is de implementatie die hoort bij een onderzoeksartikel ZeroER: Entity Resolution using Zero Labeled Examples wat zoals de titel aangeeft geen enkel gelabeld voorbeeld nodig heeft om aan "entity resolution" (wat een andere naam is voor duplicaatdetectie) te doen. Deze code bevindt zich nog meer in de onderzoeksfase en wordt niet ondersteund door een (mooie) website of een afgewerkt product.
• Python Record Linkage Toolkit De Python Record Linkage Toolkit is een bibliotheek om records te koppelen in of tussen gegevensbronnen. Volgens de informatie op hun website biedt de toolkit de meeste tools aan die nodig zijn voor record linkage en deduplicatie. Het pakket bevat indexeringsmethoden, functies om records te vergelijken en classifiers. Het pakket is ontwikkeld voor onderzoek en het koppelen van kleine of middelgrote bestanden.

  Opnieuw volgens de informatie geleverd door deze bibliotheek zijn de belangrijkste kenmerken ervan:

  • Paren van records maken met slimme indexeringsmethoden zoals blocking en sorted neighbourhood indexing
  • De toolkit bevat verschillende classificatie-algoritmen, zowel gesuperviseerde als ongesuperviseerde algoritmen.

   

Interessant? Advies nodig?

Heb je zelf behoefte aan duplicaatdetectie voor één of meerdere van jouw datasets, dan helpen we je graag, contacteer ons hier.

We plannen een volgende blogpost waarin we onze concrete ervaring met de verschillende tools en bibliotheken beschrijven.