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 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
Bij Gites worden berichten die contactinformatie bevatten, zoals een e-mailadres of telefoonnummer, beschouwd als 'spam'. Het kan ook een vagere boodschap zijn zoals "neem contact met ons op via onze website voor extra korting". Hierdoor verplaatst de communicatie zich naar buiten het platform, wat we willen voorkomen.
Om de berichten te classificeren gebruikten we een bekende en redelijk simpele techniek: de Naïve Bayes classifier. In plaats van een bestaande databibliotheek te gebruiken, besloten we alles zelf te bouwen. Dat gaf ons de mogelijkheid om het algoritme aan te passen aan deze specifieke situatie.
Machine learning is geen gemakkelijk vakgebied. Een bestaande techniek als een soort magische 'black box' toepassen, levert vaak teleurstellende resultaten. Het is moeilijk om de nauwkeurigheid te verbeteren zonder kennis van de context én de mogelijkheid om het algoritme aan te passen.
Hieronder leggen we eerst uit hoe een Naïve Bayes spam classifier werkt. Daarna bespreken we onze aanpassingen die de nauwkeurigheid sterk hebben verbeterd.
Een standaard Naïve Bayes spam classifier
Op basis van gelabelde berichten (bericht + spam/ham-label) berekent de classifier welke woorden goede aanwijzingen zijn om spam te herkennen. Dit doet hij door de kans te berekenen dat een woord voorkomt in een spam- of ham-bericht. Het label 'ham' staat voor een geldig bericht.
Elk woord krijgt twee kansen: de kans dat het in een spam-bericht staat, en de kans dat het in een ham-bericht staat. Deze stap is volledig gebaseerd op de dataset van gelabelde berichten.
Bij het classificeren van een nieuw bericht kijken we naar de woorden en combineren we hun kansen. Het systeem vergelijkt de aanwijzingen die naar spam wijzen met de aanwijzingen die naar ham wijzen. De hoogste score wint.
Stel dat het woord 'website' vaak voorkomt in spam-berichten, maar zelden in ham-berichten. De aanwezigheid van 'website' wijst dan sterk op spam. Deze hint wordt gecombineerd met alle andere woorden in het bericht. Als woorden die een illegale transactie suggereren (zoals call, contact of website) overheersen, zal de spam-score hoger zijn dan de ham-score.
Het model in de praktijk
In de praktijk is het systeem complexer dan hierboven beschreven. Om het goed te laten werken, komt er flink wat techniek bij kijken. Hier zijn de belangrijkste stappen:
Voorbewerking
Een cruciaal aspect van machine learning is de kwaliteit van je data. Die wordt bepaald door de statistische significantie: genoeg berichten (zowel spam als ham) die door een expert zijn geclassificeerd en in het juiste formaat staan.
Onze trainingdataset is een csv-bestand met 2 kolommen: uitkomst en bericht. Om het algoritme niet te verwarren, doen we extra voorbewerking:
- We verwijderen alle onbelangrijke tekens (!, ?, ., ;, &, _, nieuwe regels, etc.)
- We zetten alle tekst om naar kleine letters (anders tellen 'GREAT' en 'great' als twee aparte woorden)
- We verwijderen woorden die te kort zijn (in ons geval 1 karakter)
Een testset maken
Als we onze volledige dataset zouden gebruiken om ons model te trainen, zouden we niet weten hoe goed het model presteert. De oplossing is het maken van een aparte testset. We splitsen onze dataset van gelabelde berichten in tweeën: een groot deel voor training en een klein deel voor het testen van de nauwkeurigheid.
We haalden 100 berichten uit de oorspronkelijke dataset van 11.000 berichten om als testset te gebruiken. Om vertekening te voorkomen, kozen we 50% spam en 50% ham. Deze willekeurige splitsing gebeurt elke keer als we een nieuw model trainen. Hierdoor varieert de nauwkeurigheid licht. Toch vertrouwen we het algoritme meer als het over meerdere runs steeds even goed werkt.
Performance
Gezien de vele berekeningen kan performance een probleem zijn. We hebben de data gestructureerd als een soort in-memory database, versneld met technieken die je voor zo'n database zou gebruiken (vergelijkbaar met indices en hash tables). Onze implementatie heeft nu minder dan 5 seconden nodig om een model te trainen met 11.000 berichten. Het classificeren van één bericht gaat bijna direct.
Evaluatie van de resultaten
We kunnen nu ons model trainen en de nauwkeurigheid berekenen met de testset. De nauwkeurigheid is simpelweg het percentage correct geclassificeerde berichten. De belangrijke vragen zijn:
- Is het model nauwkeurig genoeg?
- Welke fouten maken we (false positives of false negatives)?
- Als we een fout maken, waarom gebeurt dat?
- Hoe kunnen we een hogere nauwkeurigheid bereiken?
Een false negative is een spam-bericht dat verkeerd wordt geclassificeerd als ham. Een false positive is een ham-bericht dat verkeerd wordt geclassificeerd als spam. Wij hebben liever false positives dan false negatives, omdat we zeker willen zijn dat we alle spam-berichten vinden.
Met een kant-en-klare databibliotheek waren we waarschijnlijk vastgelopen bij deze vragen. We zouden moeilijk toegang hebben gekregen tot de interne berekeningen om wijzigingen te maken. Bij machine learning is een 'doe-het-zelf'-aanpak in het begin lastiger, maar uiteindelijk de moeite waard. Omdat we alles zelf hebben gebouwd, hebben we toegang tot elke berekening en kunnen we inspecteren wat er gebeurt.
Onze eerste nauwkeurigheid lag rond de 70%. Bij machine learning kun je niet streven naar 100% nauwkeurigheid, maar voor onze toepassing vonden we dit niet goed genoeg. De volgende stap was het maken van een bestand met informatie over de fouten. Voor elk verkeerd geclassificeerd bericht hebben we het volgende genoteerd:
- Het volledige bericht
- Het type fout: false negative of false positive
- De scores voor 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 aan de scoreberekening, voor zowel ham als spam. Als de waarden dicht bij elkaar liggen, helpt het woord niet veel bij het onderscheid maken.
- Het aantal keren dat het woord voorkomt in de trainingset. Het is riskant om te vertrouwen op statistieken gebaseerd op weinig gegevens.
Kijken we bijvoorbeeld naar het woord 'www' (dat in onze context bijna zeker spam 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 geeft. Het verschil tussen de bijdragen is groot, dus het is een sterke hint naar een van de twee uitkomsten. 'www' is dus een 'interessant' woord.
Wat ging er mis?
Door de informatie uit onze results analyzer te bestuderen, konden we de volgende conclusies trekken:
- Soms werd een false negative veroorzaakt door veel 'neutrale' woorden in een bericht: hun gezamenlijke bijdrage overschaduwde de bijdrage van één interessant woord (zoals 'website' of 'www').
- Veel woorden die wij als neutraal beschouwden, hadden een lage verschijningswaarde en/of een klein verschil tussen de bijdragen.
- Woorden met dezelfde betekenis maar anders geschreven (bijvoorbeeld 'contact', 'contacting' en 'contacted') werden gezien als verschillende woorden. Ook werd dezelfde bijdrage geteld voor elke keer dat een woord in een bericht voorkwam.
Maatregelen om de nauwkeurigheid te verbeteren
Om probleem 3 op te lossen, verwijderden we dubbele woorden uit de berichten: we gebruiken een set van woorden in plaats van een lijst. Daarnaast implementeerden we een stamalgoritme dat afgeleide woorden terugbrengt tot hun basisvorm. Het Porter-algoritme reduceert bijvoorbeeld argue/argued/argues/arguing allemaal tot de stam 'argu'.
Problemen 1 en 2 waren de belangrijkste oorzaken van fouten. We pakten deze aan door creatief te zijn en onze kennis van andere machine learning-algoritmes te combineren met gezond verstand. We creëerden een eigen definitie van een 'interessant' woord door de gegevens uit de results analyzer te bestuderen.
We pasten het algoritme zo aan dat een te classificeren bericht eerst wordt gefilterd door oninteressante woorden te verwijderen. Als een bericht na filtering leeg blijft, geven we het altijd het ham-label. Bevat het bericht geen enkel interessant woord, dan is het oninteressant en krijgt het dus ham als label.
Als het bericht na filtering nog woorden bevat, passen we de gewone Naïve Bayes-berekening toe en vergelijken we de scores voor ham en spam.
Wanneer is een woord interessant? Onze definitie is gebaseerd op twee overwegingen:
- Het aantal verschijningen van een woord in de dataset moet boven een bepaalde grenswaarde liggen (na wat testen werd dit 15).
- 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 dat de onzekerheid/onvoorspelbaarheid aangeeft. Een hogere entropie betekent meer onzekerheid. Een woord dat even vaak in ham- als in spam-berichten voorkomt, heeft maximale entropie (1) en is niet informatief. Een woord dat alleen in één categorie voorkomt heeft entropie 0 en is zeer nuttig.
Conclusie
Zo hebben we een spam classifier gebouwd voor Gites.nl. We kozen voor een bekende en vrij eenvoudige techniek, Naïve Bayes, maar implementeerden het model zelf om volledige controle te houden. Dit bleek een goede beslissing, omdat we het algoritme moesten aanpassen aan onze specifieke situatie.
We combineerden het met een ander machine learning-concept: entropie. Met een stamalgoritme voorkwamen we overfitting – een algoritme dat perfect werkt op de trainingsdata maar volledig faalt bij nieuwe data. We zorgden er ook voor dat onze filters, die 'oninteressante' woorden verwijderen, niet te veel woorden uitsluiten.
Door de tussentijdse berekeningen te bestuderen en de implementatie aan te passen aan onze context, maakten we een enorme sprong van 70% naar gemiddeld 95% nauwkeurigheid!
Het eindresultaat is niet alleen een werkende applicatie die ongeveer 95% van de berichten correct classificeert. We hebben nu ook een eigen implementatie van Naïve Bayes die we gemakkelijk kunnen toepassen in en aanpassen aan andere situaties.
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.
