Mario Verstraeten 7 March 2023

 

Inleiding

Bij masterdata komt vaak het probleem voor dat verschillende records verwijzen naar dezelfde entiteit in de echte wereld, zoals bijvoorbeeld wanneer een klant meerdere keren werd geregistreerd of wanneer een product dubbel werd aangemaakt. Alhoewel het ontdekken van duplicaten op het eerste zicht eenvoudig lijkt door alle paren records te overlopen en te controleren of ze al dan niet identiek zijn, blijkt dit in de praktijk veel moeilijker. Duplicate records lijken namelijk vaak op elkaar, maar zijn niet helemaal identiek, waardoor het lastig is om deze gelijkaardige recordparen te identificeren. Deduplicatie-bibliotheken vormen een krachtig hulpmiddel voor het automatisch identificeren en verwijderen van duplicaten in grote datasets, wat zowel tijd en middelen kan besparen alsook de kwaliteit van de gegevens kan verbeteren.

Zingg en Dedupe zijn twee zo’n deduplicatie-bibliotheken. In dit artikel worden de overeenkomsten en verschillen tussen Zingg en Dedupe uiteen gezet om zo de keuze voor een deduplicatie-bibliotheek op een gefundeerde manier te kunnen maken.

Wat is deduplicatie?

Stel u werkt voor een bedrijf dat klantgegevens verzamelt uit verschillende bronnen, zoals websiteregistraties, aankopen in winkels en interacties via sociale media. Na verloop van tijd is uw klantendatabase aanzienlijk gegroeid, maar heeft u gemerkt dat bepaalde klanten meerdere keren in de database voorkomen, met bijvoorbeeld iets andere of verkeerd gespelde namen, e-mailadressen of telefoonnummers. Deze duplicatie van records kan leiden tot problemen bij klantenbinding, marketing en verkoop. U kunt bijvoorbeeld twee keer dezelfde e-mail naar dezelfde klant sturen, of een kans missen om een cross-sell of up-sell te doen aan een klant die al een aankoop heeft gedaan. Om dit probleem op te lossen, kunt u een deduplicatie-bibliotheek gebruiken voor het identificeren en samenvoegen van dubbele records. Door dubbele records te elimineren blijven uw data beter bruikbaar voor al uw doeleinden.

Wat is het verschil tussen deduplicatie en fuzzy matching?

Beide termen duiken regelmatig op wanneer er gesproken wordt over (master) data management. Deduplicatie en fuzzy matching zijn immers allebei technieken die gebruikt worden om data op te schonen, maar ze verschillen in hun aanpak en doelstellingen. Beide technieken worden vaak gebruikt in scenario's waar gegevens naar verwachting zeer gestructureerd en consistent zijn, zoals in een database met klantgegevens of productdata.

‘Fuzzy matching’ is een proces waarbij (vaak op kolomniveau) wordt gekeken naar de waarden van de records uit een dataset om zo gelijkaardige waarden te groeperen (of ‘clusteren’). Fuzzy matching gebruikt algoritmen om deze waarden te vergelijken op basis van bepaalde criteria, zoals de string-overeenkomst of fonetische overeenkomst, en kent een similariteitsscore toe aan deze waarden.

Een situatie waarbij fuzzy matching van pas kan komen, is onder andere bij het matchen van namen van landen in een dataset. Zo kunnen bijvoorbeeld "België", "Belgium" en “Belgique” worden omgezet naar één consistente waarde, bv. “België”. In de meeste tools die over data cleaning functionaliteiten beschikken, is fuzzy matching terug te vinden. Denk maar aan tools zoals OpenRefine, Microsoft PowerBI, Dataprep, etc.

 

Bij het opsporen van duplicaten m.b.v. duplicatie-bibliotheken zoals Zingg en Dedupe wordt er, in tegenstelling tot fuzzy matching, rekening gehouden met de waarden uit niet één, maar uit alle kolommen. In tools zoals Zingg en Dedupe komt er bij duplicatiedetectie dan ook een klein deeltje ‘active learning’ aan te pas. Er wordt namelijk een achterliggend model gecreëerd dat identificeert welk ‘type’ foute records aanwezig zijn in de dataset. In de volgende sectie volgt meer informatie hierover.

In onderstaand voorbeeld is voor mensen duidelijk dat beide records betrekking hebben op dezelfde klant, maar dat de waarden in sommige kolommen:

  • Omgewisseld zijn (zie address1 en address2, alsook firstName en lastName)
  • Varianten zijn van elkaar (zie ‘Dante’ en ‘D’)
  • Ontbreken (zie areacode en streetnumber)

Enkel gebruikmakend van fuzzy matching zouden deze duplicaten niet worden gedetecteerd, terwijl dit bij het gebruik van deduplicatie-bibliotheken wel mogelijk is. Kortom, fuzzy matching en deduplicatie zijn twee verschillende methoden die elkaar aanvullen en nuttig kunnen zijn voor het verbeteren van de kwaliteit en betrouwbaarheid van gegevens.  Voor meer informatie over fuzzy matching en duplicaatdetectie kunt u terecht bij onze vorige blogpost. (http://ai-assisted-mdm.be/node/32 )

Zingg en Dedupe

Hoewel er een aantal deduplicatie-bibliotheken beschikbaar zijn, behoren Zingg en Dedupe tot de populairste opties. Zowel Zingg als Dedupe gebruiken geavanceerde algoritmen en technieken om nauwkeurig dubbele records in een dataset te identificeren. Ze zijn ontworpen om een breed scala aan datatypes te verwerken en matches te identificeren, zelfs wanneer records fouten of inconsistenties bevatten of er bepaalde delen van records ontbreken. Beide maken gebruik van ‘active learning’ om een classificatiemodel op te stellen om zo duplicate records te identificeren.

‘Active learning’ is een machine learning techniek waarbij het algoritme zichzelf aanpast en verbetert door actief input te vragen van de gebruiker. Zo zoekt het algoritme naar de meest waardevolle informatie om het model te verbeteren.

In het geval van duplicaatdetectie zal er dus aan de gebruiker gevraagd worden om een record-paar te markeren als zijnde een duplicaat of niet-duplicaat. Tijdens dit labelingsproces wordt niet alleen gekeken naar record-paren die het sterkst op elkaar lijken, maar ook naar paren waar het algoritme het meeste informatie uit kan halen. Het doel is om zo efficiënt mogelijk te werk te gaan en het aantal te labelen paren zo laag mogelijk te houden. Het kan dus voorkomen dat er record-paren worden voorgesteld die niet direct als duplicaat herkenbaar zijn, maar waar het algoritme denkt veel informatie uit te kunnen halen. Het is aan de gebruiker om dan te beoordelen of het om een duplicaat gaat of niet. Dit maakt het labelingsproces soms uitdagend, maar het zorgt er ook voor dat het latere deduplicatie-proces zo nauwkeurig mogelijk verloopt. Door te bepalen welke records geen duplicaten zijn, kunnen deze bibliotheken ook veel ruis en onnauwkeurigheden uit de dataset filteren.

Hoewel Zingg en Dedupe erg gelijkaardig zijn, zijn er toch enkele verschillen vast te stellen in het gebruik en de resultaten die beide bibliotheken behalen. Deze verschillen worden verduidelijkt a.d.h.v. onderstaande vergelijkende studie.

Vergelijkende studie:

Om van start te gaan met een vergelijkende studie, is het nodig om de vereisten voor het gebruik van beide bibliotheken te installeren. Beide bibliotheken hebben een uitgebreide documentatie waarin hun respectievelijke installatieproces en gebruik staan beschreven.

                Dedupe:  https://docs.dedupe.io/en/latest/

                Zingg: https://docs.zingg.ai/zingg/

Setup

Belangrijk om te vermelden is dat het ten sterkste aangeraden is om Zingg te installeren op een Linux machine. Er kan bijvoorbeeld gebruik gemaakt worden van VirtualBox en Vagrant (https://www.vagrantup.com/) om lokaal een virtuele machine te installeren met een Linux besturingssysteem.

Voor de vergelijkende studie werden beide tools geïnstalleerd op een AlmaLinux 9 Virtual Machine, met twee cores (11de gen Intel i7) en 24 GB aan geheugen. Het is belangrijk om te vermelden dat de resultaten met betrekking tot de uitvoeringstijd van de twee deduplicatiebibliotheken kan verschillen in andere omgevingen. Door beide bibliotheken te installeren op dezelfde machine hopen we dat de relatieve verschillen in tijd zinvol zijn.

Dedupe is een Python-bibliotheek, terwijl Zingg een Java-bibliotheek is. Om het gebruik ervan te demonstreren, hebben de ontwikkelaars van beide bibliotheken een paar ‘voorbeeldrecepten’ voor datasets van verschillende grootte opgesteld die u kunt uitproberen. Beide bibliotheken voorzien voorbeelden om zowel duplicaten te detecteren in één dataset, alsook records te vergelijken tussen twee of meer datasets (wat men in de literatuur ‘Record Linkage’ noemt).

Dedupe

Zoals hierboven reeds werd vermeld, is Dedupe een Python-bibliotheek en kan deze uitgevoerd worden met een Python script. In het script kunnen een aantal parameters door de gebruiker worden ingesteld. Zo wordt er verwacht om per kolom aan te duiden welke soort data er in die specifieke kolom aanwezig is: Tekst ; Datum ; Adres ; Getal; etc.. Dit verbetert de werking van het achterliggende algoritme. Daarnaast kan in het script ook een bepaalde drempelwaarde worden opgegeven die bepaalt vanaf wanneer een record geclassificeerd wordt als een duplicaat. Deze drempelwaarde is een waarde tussen 0 en 1 en staat standaard ingesteld op 0.5.  Het verhogen van deze drempelwaarde kan nuttig zijn in situaties waarin de gegevens een hoog niveau van ruis of variabiliteit bevatten, wat kan leiden tot fout-positieve resultaten in de duplicaatdetectie. Een hogere drempelwaarde zal in deze gevallen de nauwkeurigheid van de duplicaatdetectie verhogen door ervoor te zorgen dat alleen records met een hogere mate van overeenkomst worden beschouwd als duplicaten. Aan de andere kant kan het verhogen van de drempelwaarde leiden tot fout-negatieve resultaten, wat betekent dat sommige echte duplicaten over het hoofd worden gezien en niet als zodanig worden geïdentificeerd. Het is daarom belangrijk om de drempelwaarde zorgvuldig af te stemmen op de specifieke dataset en de vereisten van de toepassing. Over het algemeen geldt dat het verhogen van de drempelwaarde gepaard gaat met een hogere precisie maar lagere recall. Precisie verwijst naar het percentage van de geïdentificeerde duplicaten die  daadwerkelijk duplicaten zijn, terwijl recall het percentage is van alle werkelijke duplicaten die als zodanig worden geïdentificeerd.

In Dedupe is het deduplicatie-proces als volgt te omschrijven:

Preparatie: Tijdens de preparatiefase worden de gegevens aangepast om deze te kunnen gebruiken in het deduplicatie-proces. Dit omvat bijvoorbeeld het normaliseren van de gegevens (zoals het verwijderen van overbodige spaties of het omzetten van hoofdletters naar kleine letters), het tokeniseren van de gegevens (het opsplitsen van de gegevens in afzonderlijke termen) en het berekenen van kenmerken die zullen worden gebruikt om de records te vergelijken.

Labeling: Tijdens de labelingsfase presenteert Dedupe twee records aan de gebruiker en vraagt deze om te bepalen of de records een duplicaat zijn of niet.

Dedupe probeert aan de hand van deze informatie een benadering te maken van welke records duplicaat zijn of niet en bepaalt hierbij tegelijk welke informatie nog ontbreekt om deze benadering zo goed mogelijk te maken. Om deze ontbrekende informatie te verkrijgen kiest Dedupe opnieuw twee records waarvan de gebruiker weer moet aangeven of deze een duplicaat zijn of niet. Dit proces herhaalt zich totdat Dedupe een voldoende accurate benadering heeft kunnen maken om een classificatiemodel op te stellen. De records die worden voorgesteld zijn records waarover Dedupe onzeker is en waarvan de labeling het meest nuttig zou zijn om de nauwkeurigheid van het model te verbeteren.

De ontwikkelaars van Dedupe raden aan om de records te labelen tot er minstens tien recordparen gelabeld zijn als duplicaten en minstens tien recordparen uitdrukkelijk gelabeld zijn als niet-duplicaten. In datasets waarin er weinig tot geen duplicaten aanwezig zijn, en er tijdens de labelingsfase  geen tien duplicate paren aan bod komen, is het ook voldoende om de labelingsfase te beëindigen met slechts vijf positieve voorbeelden van duplicaten.

Dedupe slaat alle labels die aan recordparen worden toegekend op in een JSON-bestand. Dit bestand bevat alle informatie die nodig is om het later het classificatiemodel te trainen. Door deze labels lokaal op te slaan, kan de gebruiker op elk gewenst moment het deduplicatieproces onderbreken en deze op een later tijdstip hervatten zonder verlies van eerdere labelinformatie.

Clustering: Nadat de labelingsfase is afgerond, traint Dedupe een classificatiemodel dat in staat is om onderscheid te maken tussen duplicate en niet-duplicate recordparen. Dit model wordt getraind op basis van de gelabelde recordparen die in de labelingsfase zijn geïdentificeerd. Na het trainen van het classificatiemodel wordt er een extra kolom toegevoegd aan de dataset. Deze kolom geeft aan tot welke 'groep' of 'cluster' een bepaald record behoort. Records die door het model als duplicaten herkend, worden samengevoegd in een eigen cluster. Records die niet als duplicaat zijn gelabeld, zullen elk tot een eigen cluster (van grootte 1) behoren.

 

Na het voltooien van het deduplicatie-proces wordt het eindresultaat weggeschreven in hetzelfde formaat als dat waarin de data werd ingelezen. Dedupe ondersteunt verschillende uitvoerformaten, waaronder CSV en JSON. Als er tijdens het inlezen van de data een connectie met een SQL-databank werd gemaakt, kan het eindresultaat dus ook meteen naar diezelfde databank worden weggeschreven. Het eindresultaat bevat alle records uit de originele dataset, waarbij de records die als duplicaten zijn herkend in dezelfde cluster gegroepeerd zijn. De extra kolom die tijdens het deduplicatie-proces aan de dataset is toegevoegd, geeft aan tot welke cluster een bepaald record behoort. Hierdoor is het voor gebruikers gemakkelijk om duplicaten te beheren en te verwijderen, zonder dat dit ten koste gaat van de integriteit van de dataset.

Hieronder een voorbeeld van de extra kolom die werd toegevoegd. In dit geval werd een cluster van grootte 3 geïdentificeerd.

 

Zingg:

Zoals hierboven reeds vermeld, is Zingg een Java bibliotheek die kan uitgevoerd worden met een Shell-script. Dit script gebruikt een JSON-configuratiebestand om een aantal parameters in te stellen. Het is echter ook mogelijk om de parameters die nodig zijn mee te geven door gebruik te maken van een door Zingg aangeleverd Python script. Naast het instellen van de parameters, roept dit Python-script ook de relevante functies uit de Java bibliotheek aan.

Net zoals bij Dedupe, wordt er verwacht dat de gebruiker per kolom aanduidt welk soort data er in die specifieke kolom aanwezig is: Tekst ; Datum ; Adres ; Getal; etc.. Dit verbetert opnieuw de werking van het achterliggende algoritme. Waar Zingg en Dedupe sterk van elkaar verschillen is hoe zij omgaan met de resources van de computer. Zo biedt Zingg de mogelijkheid om data gedistribueerd te verwerken door gebruik te maken van Apache Spark (https://spark.apache.org/). Een interessante parameter om bij het gebruik van Zingg in te stellen, is het aantal partities (numPartitions). Het aantal partities bepaalt namelijk hoe de data wordt verdeeld over de beschikbare computer resources, zoals de CPU-cores. Door het aantal partities te verhogen, kan de verwerking van de data beter worden verdeeld over de beschikbare cores, waardoor de prestaties verbeteren.

De parameter labelDataSampleSize bepaalt het percentage van de data dat wordt gebruikt om het classificatiemodel te trainen. Hoe groter dit percentage, hoe meer tijd Zingg zal besteden aan het trainen van het model en hoe nauwkeuriger het resultaat (hopelijk) zal zijn. Aan de andere kant kan een te klein percentage leiden tot een slechte nauwkeurigheid van het model en mogelijk gemiste randgevallen. Als er veel data beschikbaar is en er voldoende tijd en resources zijn, kan een hoger percentage worden gebruikt om een nauwkeuriger model te verkrijgen. Als de tijd en resources beperkt zijn, kan een lager percentage worden gebruikt om de uitvoeringstijd te verkorten.

Het verloop van het deduplicatie-proces in Zingg verloopt, net zoals Dedupe, in drie fasen. Er is echter een verschil in wat deze fasen exact inhouden.

Preparatie (findTrainingData):

Net zoals bij Dedupe worden de gegevens voorbereid om deze te kunnen gebruiken in het deduplicatie-proces. Het grote verschil met Dedupe is dat Zingg in de findTrainingData-fase op zoek gaat naar ongeveer 20 recordparen tegelijk en deze verzamelt om door de gebruiker te laten labelen.

Labeling:

De labelingsfase bij Zingg heeft als voordeel dat het de gebruiker in staat stelt om sneller en efficiënter te labelen. Er wordt namelijk verwacht dat de gebruiker eerst alle kandidaten labelt, vooraleer Zingg opnieuw bepaalt welke records het meest interessant zijn. Deze aanpak kan echter leiden tot een toename van het aantal benodigde labels, aangezien er telkens 20 recordparen moeten worden gelabeld. Het terugkoppelen van de gelabelde recordparen stuurt Zingg immers in de ‘juiste’ richting om de ‘meest interessante’ recordparen te labelen die dan kunnen worden gebruikt om een classificatiemodel mee te trainen.

Clustering (trainMatch):

Wanneer de labelingsfase is voltooid wordt er gecontroleerd of er voldoende record-paren gelabeld zijn als duplicaten en niet-duplicaten. Wanneer dit niet het geval is, dan zal Zingg de gebruiker vragen om opnieuw de findTrainingData fase te doorlopen. Ditmaal zal er echter ook rekening gehouden worden met de labels die gegeven werd in de vorige iteratie(s). Dit iteratief proces wordt herhaald tot Zingg van oordeel is dat er voldoende paren in elke categorie werden gelabeld. Enkel dan start Zingg met het trainen van een classificiatiemodel.

Zingg heeft als aanbeveling om minstens 10 à 20 recordparen als duplicaten en minstens 10 à 20 recordparen als niet-duplicaten aan te duiden. Afhankelijk van de dataset kan het dus zijn dat er binnen het deduplicatie-proces,  tussen de één à vijf iteraties van de findTrainingData- en labelingfase moeten worden doorlopen.

Wanneer een classificatiemodel succesvol werd getraind, worden er aan de originele data drie extra kolommen toegevoegd. De eerste extra kolom (ClusterID) heeft dezelfde functie als de extra kolom die wordt toegevoegd bij Dedupe en geeft aan tot welke cluster van duplicate records een bepaald record behoort. De andere twee kolommen geven een indicatie van hun ‘gelijkaardigheidsscore’ met respectievelijk het ‘minst’ lijkende record in de gesuggereerde cluster en het ‘meest’ lijkende (andere) record in de cluster. Op deze manier is het mogelijk om na de clusterings-fase, nog te filteren op deze scores om betere resultaten te verkrijgen, zoals wordt geïllustreerd in de sectie ‘Resultaten’ hieronder.

 

Hieronder zie je een voorbeeld van 4 records die door Zingg als duplicaten worden bestempeld. Ze hebben alle vier dezelfde ClusterID (nl. 136).  Bemerk ook de kolommen Min_Score en Max_Score die door Zingg werden toegevoegd.

Zingg kan lezen en schrijven naar Snowflake, Cassandra, S3, Azure, Elastic, meerdere  RDBMS en alle door Spark ondersteunde gegevensbronnen. Zingg werkt ook met alle belangrijke bestandsformaten zoals Parquet, Avro, JSON, XLSX, CSV, TSV, enz.

Methode:

In deze sectie zullen de resultaten van de verschillende de-duplicatie bibliotheken vergeleken worden, door deze op drie datasets te testen. Voor elke dataset is een 'golden standard' beschikbaar. Dit betekent dat er een apart bestand is waarin wordt bijgehouden welke records duplicaten zijn van andere records, zodat de nauwkeurigheid van de resultaten van de verschillende bibliotheken kan worden gemeten.

Daarnaast is het ook belangrijk om te vermelden dat verschillende uitvoeringen van het deduplicatie-proces tot verschillende resultaten kunnen leiden. De reden hiervoor is dat de bepaling van de meest  "interessante" record-paren, niet-deterministisch van aard is.  Hierdoor kunnen bij verschillende uitvoeringen verschillende record-paren worden voorgesteld. Om een zo nauwkeurig mogelijk beeld te krijgen van de effectiviteit van de twee bibliotheken is het dan ook essentieel om het gehele proces meerdere keren uit te voeren en de resultaten te vergelijken. (In de praktijk hoef je dat natuurlijk niet te doen.)

Om te valideren of de resultaten consistent zijn, is het gehele deduplicatie-proces voor elke dataset drie keer uitgevoerd. Hieronder is het verloop omschreven van het laatst uitgevoerde proces. Aangezien de verschillen met de twee voorgaande uitvoeringen zeer beperkt zijn, laten we deze in de blogpost achterwege.

In de omschrijvingen van de verschillende datasets, wordt er telkens vermeld hoeveel records er in de dataset aanwezig zijn, alsook hoeveel duplicate record-paren er aanwezig zijn. Om misopvattingen te vermijden lichten we dit graag even toe a.d.h.v. twee concrete voorbeelden.

Voorbeeld 1: In de dataset zijn er twee records aanwezig die duplicaten zijn van elkaar. Er is dan 1 duplicaat recordpaar.

Voorbeeld 2: In de dataset zijn er vier records aanwezig die duplicaten zijn. Dit wil zeggen dat record A een duplicaat is van record B,  C en D (drie record-paren), dat B een duplicaat is van records C en D en dat C een duplicaat is van record D. In totaal zijn er bij deze vier records dus zes duplicate record-paren aanwezig.

Hoe groter de groepen van duplicate records zijn, hoe meer duplicate record-paren er dus aanwezig zijn. Het is daarom perfect mogelijk dat een dataset met slechts 1.000 records meer dan 100.000 duplicate record-paren bevat, indien er zeer ‘grote’ clusters van duplicaten aanwezig zijn.

 

DATASET 1: FEBRL120k dataset:

Voorbeeld van de data:

Grootte van de dataset: +- 11MB

Aantal kolommen: 10

firstName, lastName, streetnumber, street, address1, address2, areacode, stateCode, dateOfbirth, ssn, id

Aantal rijen: 120.000 rijen

Aantal duplicate record-paren: 36.786 paren

Aard van de duplicaten:

In de dataset zijn duplicate records terug te vinden die door één (of een combinatie) van onderstaande transformaties zijn ontstaan:

  • De aanpassing van een bestaand karakter in de waarde van een kolom.
  • De toevoeging van één of meer extra karakters in de waarde van een kolom.
  • Het verwijderen van de waarde van één of meerdere kolommen.
  • Het omwisselen van de waarde uit een bepaalde kolom met de waarde uit een andere kolom (in dezelfde rij).

Het is belangrijk om hierbij te vermelden dat niet elk origineel record precies één van deze transformaties heeft ondergaan. Het kan ook zijn dat er uit één record, meerdere duplicate records zijn ontstaan door meerdere transformaties uit te voeren.

Vorm van de aanwezige clusters:

De grootte van de clusters in de dataset varieert tussen één en zes records.

 

Uitvoering met Dedupe:

Maximale inbeslagname RAM-geheugen tijdens het proces: +- 20 GB

Doorlooptijd van het deduplicatieproces (zonder labeling): 35 min in totaal.

Aantal Labels: 6/107 duplicaten ; 101/107 niet-duplicaten

 

Uitvoering met Zingg:

Maximale inbeslagname RAM-geheugen tijdens het proces: +- 1 GB

Doorlooptijd van het deduplicatieproces (zonder labeling): 3 min per Preparatie-fase + 7 min voor de Clusterings-fase

Aantal Labels: 7/62 duplicaten ; 55/62 niet-duplicaten

Alhoewel Zingg na het labelen van 62 records een classificatiemodel succesvol had getraind, werd er verder gelabeld en werden de resultaten opgeslagen in verschillende uitvoerbestanden om te kijken of de ‘precision’ en ‘recall’ van het model verbeterde. Meer hierover in de sectie ‘Resultaten’.

Uitvoer 1: 7/62 duplicaten ; 55/62 niet-duplicaten

Uitvoer 2: 26/82 duplicaten ; 56/82 niet-duplicaten

Uitvoer 3: 27/102 duplicaten ; 75/102 niet-duplicaten

Uitvoer 4: 41/122 duplicaten ; 81/122 niet-duplicaten

Uitvoer 5: 50/142 duplicaten ; 92/142 niet-duplicaten

Uitvoer 6: 64/162 duplicaten ; 98/162 niet-duplicaten

 

Dataset 2: RESTO dataset

Voorbeeld van de data:

Grootte van de dataset: +-66KB  

Aantal kolommen: 6

Id, name, addr, city, phone, type

Aantal rijen: 864 rijen

Aantal duplicate record-paren: 224 paren

Aard van de duplicaten:

De dataset is ontstaan uit een samenvoeging van twee kleinere datasets, waarvan enkele records overlappen maar niet op dezelfde schrijfwijze worden bijgehouden, bvb. ‘5th Avenue’ en ‘fifth av.’ . In bepaalde kolommen worden eveneens verschillende kernwoorden gebruikt, bv. ‘bistro’ en ‘french’ in de kolom “type”.

Vorm van de aanwezige clusters:

De grootte van de clusters in de dataset varieert tussen één en twee records. Elk record behoort m.a.w. tot hoogstens één duplicaat recordpaar.

 

Uitvoering met Dedupe:

Maximale inbeslagname RAM-geheugen tijdens het proces: < 1GB

Doorlooptijd van het deduplicatieproces (zonder labeling): <30sec.

Aantal Labels: 12/22 duplicaten ; 10/22 niet-duplicaten

 

Uitvoering met Zingg:

Maximale inbeslagname RAM-geheugen tijdens het proces: <1 GB

Doorlooptijd van het deduplicatieproces (zonder labeling): <10sec Preparatie-fase + <10sec voor de Clusterings-fase

Aantal Labels: 15/44 duplicaten ; 29/44 niet-duplicaten

 

Dataset 3: CDDB dataset

Voorbeeld van de data:

Grootte van de dataset: +-1.5MB

Belangrijke opmerking: De oorspronkelijke dataset heeft een grootte van 4.2MB. Op de machine die gebruikt werd voor de vergelijkende studie was het echter niet mogelijk voor Dedupe om deze hoeveelheid gegevens te verwerken. Dedupe had in essentie meer dan 24 GB aan geheugen nodig om de volledige dataset in te laden en het classificatiemodel te trainen. Om de grootte van de dataset te beperken werden de kolommen Track05 – Track 99 uit de dataset verwijderd.

Aantal kolommen: 11

id, artist, title, category, genre, cdextra, year, track01, track02, track03, track04

Aantal rijen: 9759 rijen

Aantal duplicate record-paren: 298 paren

Aard van de duplicaten:

In deze dataset werden geen artificiële duplicaten geïntroduceerd. De dataset is (voor zover wij weten) ook niet samengesteld uit verschillende bronnen. Dit zorgt ervoor dat de duplicaten op een “natuurlijke” wijze werden gevormd.

Vorm van de aanwezige clusters:

De grootte van de clusters in de dataset varieert tussen één en zes records.

Uitvoering met Dedupe:

Maximale inbeslagname RAM-geheugen tijdens het proces: +- 21GB

Doorlooptijd van het deduplicatieproces (zonder labeling): 45 min.

Aantal Labels: 33/43 duplicaten ; 10/43 niet-duplicaten

 

Uitvoering met Zingg:

Maximale inbeslagname RAM-geheugen tijdens het proces: +-1.5 GB

Doorlooptijd van het deduplicatieproces (zonder labeling): 2 min per Preparatie-fase + 6 min voor de Clusterings-fase

Aantal Labels: 13/53 duplicaten ; 40/53 niet-duplicaten

Alhoewel Zingg na het labelen van 53 records een classificatiemodel succesvol had getraind, werd er verder gelabeld en werden de resultaten opgeslagen in verschillende uitvoerbestanden om te kijken of de ‘precision’ en ‘recall’ van het model verbeterde. In de sectie ‘Resultaten’ vind je meer details.

Uitvoer 1: 13/53 duplicaten ; 40/53 niet-duplicaten

Uitvoer 2: 13/73 duplicaten ; 60/82 niet-duplicaten

Uitvoer 3: 17/93 duplicaten ; 76/93 niet-duplicaten

Uitvoer 4: 22/113 duplicaten ; 91/113 niet-duplicaten

 

Opmerkingen bij de uitvoering:

Zingg:

Afbeelding met tekst Automatisch gegenereerde beschrijving

Zoals is te zien op bovenstaande afbeelding, wordt er (behalve in de eerste iteratie) tijdens de labelingsfase een ‘gelijkaardigheidsscore’ getoond aan de gebruiker, alsook een voorspelling of het recordpaar een duplicaat is of niet. Deze is, zoals is te zien op bovenstaande afbeelding, niet altijd correct. Hoe minder recordparen er al gelabeled zijn, hoe groter de kans dat de ‘gelijkaardigheidsscores’ tussen de 0.45 en 0.55 liggen. Wanneer er reeds een 50-tal recordparen zijn gelabeled, kan het voorkomen dat er recordparen worden voorgesteld met gelijkaardigheidsscores van 0.26 (niet-duplicaat) of 0.71 (duplicaat).

 

Resultaten:

In deze sectie worden er een aantal termen en afkortingen gebruikt die mogelijks een verdere toelichting vereisen.

True Positive (TP): Dit is het geval waarin het achterliggende classificatiemodel correct voorspelt dat twee records overeenkomen met elkaar. Met andere woorden, de records zijn duplicaten en het model voorspelt correct dat ze duplicaten zijn.

False Positive (FP): Dit is het geval waarin het achterliggende classificatiemodel ten onrechte voorspelt dat twee records duplicaten zijn. Met andere woorden, de records zijn geen duplicaten, maar het model voorspelt dat ze dat wel zijn.

True Negative (TN): Dit is het geval waarin het achterliggende classificatiemodel correct voorspelt dat twee records geen duplicaten zijn. Met andere woorden, de records zijn geen duplicaten en het model voorspelt correct dat ze geen duplicaten zijn.

False Negative (FN): Dit is het geval waarin het achterliggende classificatiemodel ten onrechte voorspelt dat twee records geen duplicaten zijn. Met andere woorden, de records zijn duplicaten, maar het model voorspelt dat ze dat niet zijn.

De ‘precision’, ‘recall’ en de ‘F1-score’ zijn metrieken die worden gebruikt om de prestaties van het classificatie-model te evalueren.  Deze metrieken worden berekend m.b.v. de voorafgaande termen.

Precision: Precision meet de nauwkeurigheid van het classificatiemodel bij het voorspellen van duplicaten. Precisie is de verhouding van het aantal echte positieven (TP) ten opzichte van het totale aantal voorspelde positieven (TP + FP). Met andere woorden, precision geeft aan welk percentage van de positieve voorspellingen van het classificatiemodel daadwerkelijk correct zijn.

Recall: Recall meet de mate waarin het classificatiemodel alle positieve resultaten heeft kunnen vinden. Het wordt berekend als de verhouding van het aantal echte positieven (TP) ten opzichte van het totale aantal positieve resultaten (TP + FN). Met andere woorden, recall geeft aan welk percentage van de werkelijke duplicaten door het classificatiemodel zijn opgepikt.

F1-score: De F1-score is het harmonisch gemiddelde van precision en recall en geeft een overkoepelend beeld van de prestaties van het model. De F1-score wordt berekend als
2 * (precision * recall) / (precision + recall).
De F1-score geeft de balans weer tussen precision en recall, omdat deze rekening houdt met zowel de fouten van false positives als false negatives. De F1-score ligt steeds tussen 0 en 1 waarbij een F1-score van 1 betekent dat het model een precisie en recall van 100% heeft.

Over het algemeen, als het classificatiemodel een hoge precision heeft, betekent dit dat het zeer nauwkeurig is bij het voorspellen van positieve gevallen, terwijl als het model een hoge recall heeft, het alle positieve gevallen kan vinden, zelfs als het ten koste gaat van meer fouten (vals positieven in dit geval). Een hoge F1-score duidt op een goede balans tussen precision en recall, wat aangeeft dat het model zowel nauwkeurig als volledig is bij het voorspellen van positieve gevallen.

Resultaten FEBRL120k:

 

TP

FP

Precision

Recall

F1-Score

Dedupe

29706

251

0.9916

0.8075

0.8901

Zingg 1

21331

174

0.9919

0.5798

0.7318

Zingg 2

21480

303

0.9860

0.5839

0.7334

Zingg 3

21220

183

0.9914

0.5768

0.7293

Zingg 4

21148

187

0.9912

0.5748

0.7277

Zingg 5

21030

209

0.9901

0.5716

0.7248

Zingg 6

20629

166

0.9920

0.5607

0.7165

 

Resultaten Restos:

 

TP

FP

Precision

Recall

F1-Score

Dedupe

95

0

1

0.8482

0.9178

Zingg 1

112

0

1

1

1

Zingg 2

112

0

1

1

1

Opmerking: Ook bij andere uitvoeringen van Dedupe werd nooit 100% recall bereikt.

 

Resultaten CDDB:

 

TP

FP

Precision

Recall

F1-Score

Dedupe

126

0

1

0.4228

0.5943

Zingg 1

213

2473

0.079

0.7147

0.1427

Zingg 2

208

1029

0.168

0.6979

0.2710

Zingg 3

206

1372

0.1305

0.6912

0.2196

Zingg 4

188

1026

0.1548

0.6308

0.2486

Op het eerste zicht lijkt het alsof Dedupe voor sommige datasets betere resultaten geeft dan Zingg, terwijl voor andere datasets Zingg de betere resultaten geeft. Bij Zingg  is er echter nog extra informatie beschikbaar die na de clusteringsfase gebruikt kan worden om de resultaten te verbeteren. Zoals eerder vermeld, worden bij elk record, naast een ‘cluster id’, ook de minimale en maximale ‘gelijkaardigheidsscore’ bijgehouden.

Uit onze experimenten blijkt dat Zingg graag ‘te veel’ records samen groepeert als duplicaten. Als we nauwkeuriger kijken merken we op dat er soms records in clusters aanwezig zijn, die daar eigenlijk niet thuishoren. De maximale ‘gelijkheidsscore’ van deze records is over het algemeen lager dan de score van de andere records in diezelfde cluster. Wanneer hierop een filter wordt toegepast kunnen deze records verwijderd worden. Op die manier daalt het aantal vals positieven waardoor de precisie  en F1-score stijgen.

 

Wanneer we zo’n filtering toepassen op de resultaten van de FEBRL120k dataset krijgen we het volgende:

 

TP

FP

Precision

Recall

F1-Score

Zingg 2

21480

303

0.9860

0.5839

0.7334

>0.55

21480

237

0.9890

0.5839

0.7336

>0.60

21480

222

0.9897

0.5839

0.7337

>0.65

21474

212

0.9902

0.5837

0.7340

>0.70

21472

207

0.9904

0.5836

0.7341

>0.75

21472

202

0.9906

0.5836

0.7342

>0.80

21472

197

0.9909

0.5836

0.7344

>0.85

21471

187

0.9913

0.5836

0.7345

>0.90

21468

174

0.9919

0.5835

0.7346

>0.95

21467

162

0.9925

0.5835

0.7349

>0.99

21411

153

0.9929

0.5833

0.7348

De keuze werd gemaakt om deze filtering toe te passen op ‘Zingg output 2’, aangezien deze over de meeste true positives beschikt, en de filtering enkel een daling kan teweegbrengen in TPs en FPs. Anders verwoord: door de resultaten te filteren, verliezen we een aantal TPs, maar verlagen we ook (sterker) het aantal FPs. Een lager aantal FP, is ook belangrijk om meer vertrouwen te creëren bij de eindgebruiker in het achterliggend model.

Daarnaast blijkt uit onze experimenten dat Zingg de neiging heeft om records die voornamelijk bestaan uit lege (of ontbrekende) waarden samen te voegen tot één grote cluster. Dit zorgt ervoor dat het aantal FPs hoog is.  We hebben dit fenomeen voornamelijk opgemerkt bij de CDDB dataset.

 

Bij de CDDB dataset:

Het toepassen van een NaN-threshold wil zeggen dat als er een bepaald percentage van de velden van een record uit NaN, 0, een lege string of enkel uit niet-alfabetische waarden bestaat, en dat record tot een cluster behoort met grootte minstens 2, dan wordt dat record uit die cluster verwijderd (en vormt het een cluster enkel met zichzelf).

Deze NaN-filtering werd toegepast op ‘Zingg output 2’ van de CDDB dataset, aangezien deze over de meeste TPs beschikt en de filtering enkel een daling kan teweegbrengen van het aantal TPs en FPs.

Voor een NAN threshold van 0.2. krijgen we de volgende resultaten. We laten m.a.w. enkel records toe in clusters met minstens twee records, wanneer minstens 80% van de kolommen een waarde heeft.

 

TP

FP

F1-Score

Zingg 2

213

2473

0.1427

NaN filter

191

43

0.7180

Na deze filtering zien we dat het aantal FPs drastisch is gedaald, en dat de F1-score zelfs beter is dan de F1-score van Dedupe op dezelfde dataset (nl. 0.5943).

Conclusie

  • Het aantal vals positieven bij Dedupe is over het algemeen lager dan bij Zingg. Op die manier kan dedupe echter een aantal TPs missen.
  • Dedupe is niet schaalbaar voor grotere datasets (het gebruikt te veel tijd en geheugen) in die mate dat het bijna onbruikbaar wordt. Zingg gaat veel beter om met de beschikbare resources en gebruikt over het algemeen veel minder RAM-geheugen.
  • Bij Zinng kan je de similariteitsscores gebruiken om de gebruikerservaring te optimaliseren (door bv. eerst enkel die records met een hoge similariteitsscore te presenteren aan de gebruiker). Dedupe maakt ook gebruik van een threshold, maar om die threshold te variëren moet je telkens het algoritme volledig opnieuw laten lopen wat dit uiteraard veel minder bruikbaar maakt. Dit is niet het geval bij Zingg.

Voor “real-world” datasets met de volgende kenmerken:

  • Grote datasets (met veel kolommen),
  • Slechts enkele duplicate records, en clusters met hoogstens 5 records

is het ons advies om gebruik te maken van Zingg. Dit is ook de bibliotheek die gebruikt wordt in de tool van het project waaraan deze blogpost is gekoppeld.

Wil je meer weten over deduplicatie? Contacteer ons op info@ai-assisted-mdm.be

Referenties

 

Labels