Een nauwkeurigheid van 95%

Onze klant Gites.nl is een online marktplaats voor de verhuur en verkoop van vakantiehuizen in Frankrijk. Soms proberen aanbieders een transactie illegaal – buiten het platform om – af te ronden. Met machine learning bouwden we een spam classifier om deze berichten te onderscheppen. We leggen je graag uit hoe we de Naïve Bayes classifier hebben ingezet om een model te bouwen dat deze berichten met een nauwkeurigheid van 95% beoordeelt.

 

We begonnen from scratch

In de context van Gites worden berichten die expliciete contactinformatie bevatten, zoals een e-mailadres of telefoonnummer, beschouwd als ‘spam’. Het kan ook een wat vagere boodschap zijn, zoals “neem contact met ons op via onze website voor extra korting”. Hierdoor wordt de communicatie tussen de adverteerder en de gebruiker verplaatst naar buiten het platform, wat we juist willen voorkomen. Om de berichten te classificeren gebruikten we een welbekende en redelijk simpel toe te passen techniek, namelijk de Naïve Bayes classifier. In plaats van een beroep te doen op een bestaande databibliotheek, besloten we zelf alles from scratch te implementeren. Dat gaf ons de mogelijkheid om het algoritme zó aan te passen, dat het optimaal werkt voor deze specifieke case.

Maar machine learning is geen gemakkelijk vakgebied. En het toepassen van een bestaande techniek als een soort magische ‘black box’, geeft vaak teleurstellende resultaten. Het is vrijwel onmogelijk om de nauwkeurigheid van een model te verbeteren zonder grondige kennis van de context én de mogelijkheid om de details van het algoritme zo te tweaken dat het beter toepasbaar is op de huidige context. We leggen je eerst uit hoe een Naïve Bayes spam classifier werkt. Daarna bespreken we de aanpassingen die we aan het algoritme hebben gedaan om de nauwkeurigheid sterk te verbeteren.

 

Een standaard Naïve Bayes spam classifier

Op basis van een set gelabelde berichten (bericht + spam/ham-label), probeert de Naïve Bayes classifier te begrijpen welke woorden goede ‘hints’ vormen om te bepalen of een bericht spam is of niet. De classifier doet dat door de kans te berekenen dat het woord voorkomt in een spam- of ham-bericht. Het label ‘ham’ wordt algemeen gebruikt voor het tegenovergestelde van spam, en dus een ‘geldig’ bericht. Elk woord wordt dus geassocieerd met twee kansen: de kans dat het woord in een spam-bericht voorkomt, en de kans dat het woord in een ham-bericht voorkomt. Deze stap is volledig gebaseerd op de dataset van gelabelde berichten.

Bij het classificeren van een nieuw ongelabeld bericht, kijken we naar de woorden die het bericht vormen en combineren we de kansen die ieder woord geeft. Het systeem classificeert door het ‘gewicht’ van de hints die naar spam wijzen, te vergelijken met de hints die naar ham wijzen. Degene met de hoogste score wint. Stel dat de kans dat het woord ‘website’ voorkomt in een spam-bericht zeer groot is, en de kans dat hetzelfde woord voorkomt in een ham-bericht zeer laag. De aanwezigheid van het woord ‘website’ in een te classificeren bericht is dan een sterke aanwijzing dat het om een spam-bericht gaat. Deze hint moet wel worden gecombineerd met de hints die door alle andere woorden in het bericht worden gegeven. Een bericht zal altijd woorden bevatten die in beide richtingen wijzen. Maar als de woorden overheersen die een illegale transactie suggereren (zoals call, contact of website), dan zal de spam-score veel groter zijn dan de ham-score.

 

Het model in de praktijk

Natuurlijk is de realiteit wat rommeliger dan het hierboven beschreven systeem voor een dergelijk algoritme. Om het in de praktijk te laten werken, komt er eerst flink wat engineering aan te pas. Er zijn een paar belangrijke stappen om tot een goed werkende implementatie te komen:

Voorbewerking

Een ongelooflijk belangrijk aspect van machine learning is de kwaliteit van je data. Die wordt bepaald door de statistische significantie: als er genoeg berichten zijn (zowel spam als ham!) die zijn geclassificeerd door een expert, maar ook in het juiste formaat. Onze trainingdataset wordt opgeslagen als een csv-bestand met slechts 2 kolommen: uitkomst en bericht. Om te voorkomen dat het algoritme in de war raakt door onbelangrijke zaken, doen we nog meer voorbewerking. Zo verwijderen we alle oninteressante karakters (!, ?, ., ;, &, _, nieuwe regels, etc.), passen we alle tekst aan naar kleine letters (anders zouden ‘GREAT’ en ‘great’ als twee aparte woorden tellen!) en verwijderen we woorden die te kort zijn om interessant te zijn. In ons geval zijn dat woorden van 1 karakter, maar in een andere context kunnen het ook 2 of 3 karakters zijn.

Een testset maken

Als we onze volledige dataset zouden gebruiken om ons model te trainen, dan zouden we geen idee hebben hoe goed het model presteert. Een oplossing hiervoor, op basis van supervised learning, is het creëren van een testset die los staat van de trainingset. We splitsen dus onze dataset van gelabelde berichten in tweeën. Het grootste deel vormt de trainingset, en een kleine subset bewaren we voor later om de nauwkeurigheid van ons model te testen. Dit doen we door de classificatie die het model heeft gemaakt te vergelijken met de ‘echte’ classificatie. We haalden 100 berichten uit de originele dataset van 11.000 berichten, om te gebruiken als testset. Om vertekening te voorkomen, zorgden we ervoor dat de helft van de berichten spam was, en de andere helft ham. Deze willekeurige splitsing tussen training- en testberichten gebeurt elke keer als we een nieuw model trainen, dus de nauwkeurigheid van het getrainde model is dan steeds iets anders. Toch zijn we er zeker van dat we het algoritme meer kunnen vertrouwen als het over meerdere runs steeds even goed werkt, dan met een vaste training- en testset.

Performance

Gezien de hoeveelheid berekeningen die het algoritme maakt, is het voor de hand liggend dat performance een issue is. Een suggestie is daarom om de data te structureren in een soort in-memory database, en deze te versnellen op manieren die je voor zo’n database zou kunnen gebruiken (in grote lijnen hetzelfde principe dat indices en hash tables snel maakt). Onze implementatie doet er nu minder dan 5 seconden over om een model te trainen met een dataset van 11.000 berichten. Met een getraind model gebeurt het classificeren van één bericht bijna onmiddellijk.

 

Evaluatie van de resultaten

We zijn nu in staat om ons model te trainen en de nauwkeurigheid ervan te berekenen met de testset. De nauwkeurigheid is simpelweg het percentage correct geclassificeerde berichten uit de testset. De vragen die we kunnen stellen zijn:

  • Is het model nauwkeurig genoeg?
  • Welke fouten maken we (false positives of false negatives)?

Een false negative is een spam-bericht dat ten onrechte wordt geclassificeerd als ham. Een false positive is het tegenovergestelde: een ham-bericht dat ten onrechte wordt geclassificeerd als spam. Welke fout is erger? Wij hebben liever false positives dan false negatives, omdat we zeker willen zijn dat we alle spam-berichten te pakken krijgen.

  • Als we een fout maken, waarom gebeurt dat?
  • En als we de antwoorden op deze vragen weten, wat kunnen we dan doen om een hogere nauwkeurigheid te realiseren?

Hadden we een bestaande databibliotheek gebruikt, dan waren we waarschijnlijk vastgelopen op deze vragen. We hadden dan moeilijk toegang kunnen krijgen tot de interne berekeningen van het algoritme om wijzigingen aan te brengen. Bij machine learning is een ‘doe-het-zelf’-benadering in het begin absoluut lastiger, maar uiteindelijk zeker de moeite waard. Omdat wij alles from scratch hebben geïmplementeerd, hebben we nu toegang tot elke afzonderlijke berekening en tussenliggende nummers, zodat we kunnen inspecteren wat er gebeurt en aanpassen waar nodig.

Onze eerste nauwkeurigheid lag rond de 70%. Met machine learning kun je niet streven naar een nauwkeurigheid van 100% en moet je fouten accepteren. Toch vonden we dit voor onze applicatie niet goed genoeg. We vonden het de moeite waard om het verder te onderzoeken en verbeteren. De volgende stap was dus om een bestand te maken met allerlei informatie over de fouten die het algoritme maakt. In het bijzonder hebben we voor elk bericht dat verkeerd geclassificeerd werd, het volgende afgedrukt:

  • Het volledige bericht
  • Het type fout: false negative of false positive?
  • De scores die verbonden zijn aan beide uitkomsten (ham/spam)

Als de scores dicht bij elkaar liggen is de classifier onzeker, waarschijnlijk omdat het bericht moeilijk te classificeren is.

En voor ieder woord in het bericht:

De bijdrage (een numerieke waarde) die het woord heeft geleverd aan de scoreberekening, voor beide uitkomsten (ham/spam). Als de waarden dicht bij elkaar liggen, dan helpt het woord ons dus niet veel bij het maken van het onderscheid tussen ham en spam.

Het aantal keren dat het woord voorkomt in de trainingset; omdat het altijd erg risicovol is om te vertrouwen op statistieken die zijn gebaseerd op te weinig gegevens. Als we een woord maar 1 keer zijn tegengekomen, en alleen in een spam-bericht, dan is het geen goede indicator voor spam omdat het zomaar willekeurig kan zijn geweest.

Kijken we bijvoorbeeld naar het woord ‘www’ (dat in onze context bijna zeker een spam-bericht betekent), dan heeft dat woord de volgende waarden:

  • Bijdrage spam: -4.630538878
  • Bijdrage ham: -8.793873874
  • Absoluut verschil: 4.163334996
  • Aantal verschijningen: 412


Omdat het aantal verschijningen hoog is, kunnen we vertrouwen op de informatie die dit woord oplevert. Het absolute verschil tussen de bijdragen is bovendien vrij groot, en dus is het een sterke hint naar een van de twee uitkomsten. ‘www’ is dus met recht een ‘interessant’ woord.

 

Wat ging er mis?

Als we goed kijken naar de informatie die door onze results analyzer is afgedrukt, kunnen we de volgende conclusies trekken:

  1. Soms werd een false negative fout gemaakt door de aanwezigheid van veel ‘neutrale’ woorden in een bericht: de som van hun bijdragen overschaduwde in dat geval de enkele bijdrage van één interessant woord (zoals ‘website’ of ‘www’).
  2. Veel woorden, die naar ons idee neutraal waren, lieten een hele lage verschijningswaarde en/of een heel laag absoluut verschil tussen de bijdragen zien.
  3. Woorden die iets anders geschreven zijn maar hetzelfde betekenen (bijvoorbeeld ‘contact’, ‘contacting’ en ‘contacted’), worden door het systeem gezien als verschillende woorden en leveren dus een afzonderlijke bijdrage aan de berekening. Bovendien, als hetzelfde woord meerdere keren in een bericht verscheen, werd de bijdrage ervan geteld voor elk van de verschijningen.

Maatregelen om de nauwkeurigheid te verbeteren

Om conclusie 3 op te lossen, besloten we om de dubbele woorden uit de berichten te verwijderen: we gebruiken dan een set van woorden in plaats van een lijst. Daarnaast hebben we een stamalgoritme geïmplementeerd dat afgeleide woorden reduceert tot hun basisvorm (of de stam). De overgebleven stam hoeft geen bestaand woord te zijn. Het Porter-algoritme reduceert bijvoorbeeld argue/argued/argues/arguing en argus allen tot de stam ‘argu’.

Conclusies 1 en 2 zijn de meest cruciale bron van de fouten. Deze hebben we aangepakt door creatief te werk te gaan en onze kennis van andere machine learning-algoritmes te combineren met een vleugje gezond verstand. We creëerden onze eigen definitie van een ‘interessant’ woord door de nummers die door de results analyzer werden afgedrukt te bestuderen. Daarnaast pasten we het algoritme zo aan dat een te classificeren bericht eerst wordt gefilterd door het te ontdoen van woorden die wij als oninteressant bestempelen. Het is dan natuurlijk mogelijk dat een bericht na het filteren leeg achterblijft. In dat geval besloten we zo’n bericht altijd de classificatie ham te geven. Staat er geen enkel interessant woord in het bericht, dan is ook het bericht oninteressant en krijgt het dus het ham-label.

Als het bericht na filtering nog wel enkele woorden bevat, dan passen we de gebruikelijke Naïve Bayes-berekening toe en vergelijken we de scores van de twee uitkomsten (ham/spam). 

Maar wanneer vinden wij een woord dan interessant? Onze definitie van interessant is gebaseerd op twee overwegingen:

  1. Het aantal verschijningen van een woord in de dataset moet boven een bepaalde grenswaarde liggen (na enige afstemming werd dit 15).
  2. De entropie van een woord moet onder een bepaalde grenswaarde liggen (we begonnen met 0,6 en eindigden met 0,4). Entropie is een bekend begrip in machine learning; zo wordt het gebruikt in het kernalgoritme om bijvoorbeeld beslisbomen op te bouwen. Het geeft een idee van de onzekerheid/onvoorspelbaarheid: een hogere waarde van entropie komt overeen met meer onzekerheid/onvoorspelbaarheid. Een woord dat de helft van de tijd in ham-berichten en de helft van de tijd in spam-berichten voorkomt, zou de maximale entropie hebben (1) en voor ons helemaal niet informatief zijn. In plaats daarvan zou een woord dat slechts in één categorie berichten voorkomt (spam bijvoorbeeld) een entropie van 0 hebben en voor ons hele nuttige informatie bevatten.

 

Conclusie

Zo ziet het bouwen van een spam classifier voor berichten van Gites.nl eruit. We besloten om een bekende en vrij eenvoudige techniek te gebruiken, namelijk Naïve Bayes. We hebben het model zelf geïmplementeerd, om volledige controle te houden over het hele classificatieproces. Dat bleek een goede beslissing, aangezien we het algoritme op maat moesten maken om het te laten passen in onze context. Zo combineerden we een ander bekend concept op het gebied van machine learning: entropie. Met het implementeren van een stamalgoritme waakten we voor overfitting. Dat wil zeggen:  een dergelijk algoritme creëren dat perfect werkt op de dataset, maar volledig in de war raakt als het onbekende data ontvangt. Ook zorgden we ervoor dat onze eigen filters, die ‘oninteressante’ woorden verwijderen, niet té veel woorden uitsluiten van ons vocabulaire. We verdiepten ons in de tussentijdse berekeningen van het algoritme en pasten de implementatie aan onze specifieke context aan. Daarmee maakten we een enorme sprong van 70% nauwkeurigheid naar een gemiddelde van 95%!

Het eindresultaat is niet alleen een werkende applicatie die ongeveer 95% van de berichten van Gites.nl correct classificeert. We hebben nu ook een custom implementatie van Naïve Bayes die we gemakkelijk kunnen toepassen in en aanpassen aan een andere context.

Benieuwd wat wij met deze machine learning-technieken kunnen betekenen voor jouw organisatie? Neem contact op met Giuseppe!

Lees het volledige artikel over deze case hier.

Over de auteur

Guiseppe Maggiore is Digital Entrepreneur & CTO bij Hoppinger.

Mis niets

Schrijf je in voor onze nieuwsbrief en laat ons jouw gids zijn in een complexe digitale wereld.