Afgelopen jaren is het aantal verschillende producten dat webshops aanbieden flink gestegen. Het gevolg hiervan is dat meerdere fabrikanten productdata aan de webshop moeten aanleveren. Als iedereen dit op zijn eigen manier zou doen, zal dit voor veel onduidelijkheid zorgen. Om deze reden is een standaardformaat ingevoerd voor onder andere elektrische en elektronische apparaten: het ETIM-formaat. Veel fabrikanten hebben hun productdata nog niet in dit standaard formaat staan, en vandaar dat Squadra MLC een conversietool aanbiedt. Eén van de taken van deze tool is om de producten in de juiste ETIM-klasse te classificeren. Een product kan bijvoorbeeld ingedeeld worden in de ETIM-klasse ‘stofzuiger’ of ‘wasmachine’.

Probleem en doelstelling

Eerst gebeurde deze productclassificatie met behulp van een multinomiaal, logistisch regressiemodel. De traindata waarop dit model getraind is, bevat echter niet alle mogelijke ETIM-klassen. Hierdoor worden de producten met een ETIM-klasse die niet in de traindata voorkomen over het algemeen niet goed geclassificeerd. Het doel van dit onderzoek was daarom om een classificatiemodel te ontwikkelen dat ook producten kan classificeren met een ETIM-klasse die niet in de traindata voorkomen.

Gebruikte databestanden

Voor dit onderzoek zijn twee databestanden beschikbaar gesteld: de elektronica- en ETIM-dataset. De elektronica-dataset bevat producten die niet in ETIM-formaat staan en dus nog geclassificeerd moeten worden in een ETIM-klasse. In deze dataset staan onder andere de productomschrijvingen en -kenmerken genoteerd. In de ETIM-dataset staan de standaardnamen en codes voor onder andere de ETIM-omschrijvingen en -kenmerken.

Oplossingsmethode

Een oplossing voor het genoemde probleem is schema matching. Schema matching vergelijkt de gegevens van het te classificeren product met de gegevens van de mogelijke ETIM-klassen. De ETIM-klasse met de meeste overeenkomsten is de ETIM-klasse waar het product in geclassificeerd wordt. In figuur 1 staat een voorbeeld waarbij een te classificeren product vergeleken wordt met één mogelijke ETIM-klasse.

Hybride naam-matcher

De schema elementen van het productschema uit figuur 1 worden met de schema elementen van het ETIM-schema uit figuur 1 vergeleken met behulp van een hybride naam-matcher. Deze matcher berekent een waarde tussen de 0 en 1 die de mate van overeenkomstigheid tussen twee strings (bijvoorbeeld ‘luxe koelkast’ en ‘koelkast’) aanduidt; deze waarde wordt de similarity score genoemd. Een similarity score van 0 impliceert geen enkele overeenkomst en een score van 1 impliceert dat de elementen precies hetzelfde zijn. De gebruikte hybride naam-matcher is gebaseerd op twee matchers:

1. De 3-Gram-matcher
   Deze matcher bekijkt het aantal overeenkomende subreeksen van drie achtereenvolgende karakters en kan dus alleen overeenkomsten op basis van teksten vergelijken. De overeenkomst tussen ‘koelkast’ en ‘koelkastje’ kan bijvoorbeeld herkend worden door de 3-Gram-matcher.
2. De cosine similarity matcher met voorgetrainde embeddings
   De voorgetrainde embeddings zijn numerieke vectoren die woorden representeren. De overeenkomstigheid tussen twee strings wordt bepaald door te kijken naar de hoek die deze embeddings met elkaar maken: hoe kleiner de hoek, hoe hoger de similarity score. Een voordeel van deze matcher is dat het ook synoniemen en relaties kan herkennen. De overeenkomst tussen ‘toilet’ en ‘wc’ kan bijvoorbeeld wel herkend worden door de cosine similarity matcher, maar niet door de 3-Gram-matcher.

Similarity flooding algoritme

Het similarity flooding algoritme bepaalt overeenkomsten tussen schema elementen door rekening te houden met zowel de overeenkomsten in elementnamen als de structuur van de schema’s. Het algoritme is gebaseerd op het volgende uitgangspunt: als twee elementen hetzelfde zijn, dan zijn de ouders en kinderen van deze elementen ook enigszins vergelijkbaar.

De globale werking van het similarity flooding algoritme kan het best uitgelegd worden middels een voorbeelddiagram (zie figuur 2). Het voorbeeld betreft een product met twee kenmerken dat geclassificeerd moet worden. In dit voorbeeld kan tussen twee mogelijke ETIM-klassen gekozen worden: ETIM-klasse 1 en ETIM-klasse 2.

Het voorbeelddiagram is op te delen in drie lagen. De eerste laag van het diagram bestaat uit het beginpunt, dat een verzameling is van alle mogelijke ETIM-klassen waarin een product geclassificeerd kan worden. De similarity score van deze laag wordt op 1 gezet, omdat de overeenkomsten onbekend zijn.

In de tweede laag wordt de productomschrijving met de mogelijke ETIM-omschrijvingen vergeleken en in de derde laag worden de productkenmerken met de ETIM-kenmerken vergeleken. De similarity scores in deze twee lagen worden berekend met behulp van de hybride naam-matcher.

Vervolgens worden de similarity scores uit figuur 2 (deels) doorgegeven aan hun buren. Dit heeft te maken met het uitgangspunt dat als twee elementen hetzelfde zijn de ‘ouders’ en ‘kinderen’ (buren) ook enigszins vergelijkbaar zijn. Hierdoor neemt de similarity score van de productomschrijving met de ETIM-omschrijving van klasse 2 toe, omdat de bijbehorende kenmerken goed met elkaar overeenkomen. De gewichten bij de pijlen bepalen hoe goed de similarity score wordt doorgegeven aan zijn buren.

Figuur 3 is het resultaat na het doorgeven van de similarity scores aan hun buren. Om te bepalen in welke ETIM-klasse het product geclassificeerd wordt, wordt gekeken naar de similarity score van de beschrijvingen. Hieruit blijkt dat ETIM-klasse 2 de hoogste similarity score heeft en het product zal dus geclassificeerd worden in ETIM-klasse 2.

Conclusie

Het similarity flooding algoritme heeft voor een significante verbetering van het classificatiemodel gezorgd. Een nadeel van dit algoritme is echter dat de resultaten minder goed worden naar gelang er meer producten zijn met vergelijkbare kenmerken heeft en dat de classificatie lang duurt vanwege de grote hoeveelheid vergelijkingen.

Bronvermelding

• Melnik, S., Garcia-Molina, H., & Rahm, E. (2002). Similarity flooding: a versatile graph matching algorithm and its application to schema matching. Proceedings 18th International Conference on Data Engineering. https://doi.org/10.1109/icde.2002.994702