Hvem er i nabolaget?

Vidar Moe
Vidar Moe
Feb 18 · 5 min read
Won’t You Be My Neighbor follows the making, reception, and critique of the beloved children’s show “Misters Rodger’s Neighborhood” (1968–2001).

En stor del av arbeidet når en jobber med maskinlæring, er å forstå dataene en jobber med. En måte å bli bedre kjent med dataene på, er å undersøke om dataene inneholder grupper, eller clustre, av data som ligner på hverandre.

For å gjøre dette kan vi bruke en familie av algoritmer som kalles clusteringalgoritmer. Disse algoritmene gjør jobben uten treningsdata, men de trenger som mange andre maskinlæringsalgoritmer en numerisk, vektorisert representasjon av dataene en ønsker å undersøke.

Vi har jobbet med klassifisering av e-poster til og fra kundesenter for bedriftskunder i SpareBank 1. For å finne forslag til kategorier for klassifiseringen, ga vi problemet til en clusteringalgoritme.

Felles for mange clusteringalgoritmer er at de bruker avstanden mellom datapunktene til å finne de aktuelle clustrene.

https://no.wikipedia.org/wiki/M%C3%A5leb%C3%A5nd#/media/File:Tape_measure_colored.jpeg

Avstanden mellom numeriske vektorer kan beregnes på flere måter. De vanligste er Manhattan Distance og Eucledian Distance. For tekst er det ofte best å bruke Cosine, evt. Jaccard.

Før man kjører selve clustringen må dataene vaskes og vektoriseres. I vasken av e-postene forsøkte vi å ta bort all tekst som ikke var med i hovedbudskapet, f.eks. standard hilsninger, disclaimers o.l. Dette gjorde vi for å unngå at det dannes grupper basert på likhetstrekk i disse, i stedet for det innholdet vi egentlig er interessert i.

http://renholdsnytt.no

Vektorisering av korpuset (dvs. alle e-postene) gjør om enkle ord og ordkombinasjoner til en vektor, eller lettere sagt en ordbok. Viktigheten og frekvensen av ordene blir så vektet vha. TFIDF (Term Frequency — Inverse Document Frequency). Vi brukte stort sett enkle og doble ord, noe som betyr at vi i ordboken får alle unike ord fra korpuset pluss alle kombinasjoner av to ord som står ved siden av hverandre. Man sier da at vi har brukt bag-of-words med TFIDF-vekting på uni- og bigram.

For å kunne trekke ut det aller viktigste i tekstene har vi benyttet Oslo-Bergen-taggeren. Denne analyserer teksten og finner ut hvilket ord som er substantiv, verb, adjektiv osv. Vi endte opp med å fjerne alle andre ord enn substantiv. Videre valgte vi å ta base-ordet til substantivet for å kunne finne likheter mellom e-postene. F.eks.: Baseordet av konti er konto, forsikringer er forsikring osv.

https://en.oxforddictionaries.com/grammar/types-of-noun

Når substantiv-uttrekket var ferdig, kunne vi endelig kjøre selve clustringen.

Den vanligste clusteringalgoritmen er K-means. Denne algoritmen må vite antall clustre vi ønsker på forhånd og blir derfor ofte omtalt som en partisjoneringsalgoritme. Basert på dette, velger den senterpunkter innenfor datamengden, og finner de punktene som er nærmest de aktuelle senterpunktene. Deretter beregnes gjennomsnittet av punktene i hvert cluster. Dette blir så de nye senterpunktene, og slik fortsetter det til den konvergerer. Eksempel:

https://hdbscan.readthedocs.io

K-means fungerer best for sfæriske clustre, noe vi ser tydelig i figuren ovenfor. Den trenger som nevnt også antallet cluster på forhånd. Man kan finne antallet ved hjelp av albue-metoden som går ut på å finne optimalt antall clustre basert på kompromisset færrest mulig clustre og likest mulig tekst. I figuren under vises beregning av e-postenes inertia (likhet) som funksjon av antall clustre. Som vi ser, ligger det optimale antall clustre på 100 +-20.

Inertia som funksjon av k-verdi (antall clustre). Lavere inertia er bedre.

Vi prøvde oss frem med forskjellige verdier, men det var vanskelig å komme frem til riktig antall. Derfor valgte vi å prøve Density Based Spatial Clustering of Applications with Noise (DBSCAN) algoritmen i stedet. DBSCAN ser på tettheten til datapunktene, altså likheten mellom e-postene, og gir oss et antall clustre. Eksempel på et DBSCAN-resultat:

https://hdbscan.readthedocs.io

Parametre man i hovedsak skal sette er epsilon, som er minimum tetthet på clustrene, samt minimum antall medlemmer som kreves for å opprette et cluster. Det viktige her er at man ikke velger for lav eller for høy epsilon. For høy tetthet (lav epsilon) kan føre til at e-poster som skulle ha ligget i et cluster faller utenfor som støy eller plasseres i feil cluster. For lav tetthet kan føre til at e-poster som er ulike havner i samme cluster. Ved å analysere avstand til nærmeste naboer for alle datapunkter kan man finne egnede nivåer av epsilon. Man kjører da DBSCAN med disse epsilon-verdiene og trekker ut clustrene man får i hver kjøring. Denne metoden er beskrevet i ymse papers som Variable Density Based Clustering, Multi Density DBSCAN o.l.

En annen utvidelse av DBSCAN er HDBSCAN (Hierarkisk DBSCAN). Fordelen med den algoritmen er at den ikke trenger epsilon (clustertetthet). Den finner selv ut hvordan custrene skal deles opp ut fra lokal tetthet. Eksempel på et HDBSCAN-resultat:

https://hdbscan.readthedocs.io

Selv om HDBSCAN i teorien skal fungere bedre enn DBSCAN, ble ikke kvaliteten på clusterne så bra som med ren DBSCAN. Det kan hende at HDBSCAN kan gjøre det bedre enn DBSCAN i vårt tilfelle, f.eks. ved justering av hyperparametrene eller rense datasettet slik at kvaliteten blir akseptabel. I vårt første forsøk endte vi likevel opp med å bruke ordinær DBSCAN.

Figuren viser de ulike clusterner algoritmen fant og størrelsen på dem

For å summere opp noen av erfaringene vi har gjort oss så langt:

  • Vasking og preparering av datasett tar tid
  • Visualisering av dataene og resultatene er nyttig for bedre forståelse
  • Oslo-Bergen-taggeren kan være nyttig i tekstanalyse

Prøving og feiling er en del av å jobbe med maskinlæring. Få erfaring — prøv “alt mulig rart”. Plutselig dukker det opp noe spennende!

Stein Rune Henriksen, Vidar Moe

SpareBank 1 Utvikling

Vi jobber med digitale løsninger hos SpareBank 1. Vi liker å skrive om det vi brenner for

Vidar Moe

Written by

Vidar Moe

Loves creating great, simple software solutions using continous learning and respect for people.

SpareBank 1 Utvikling

Vi jobber med digitale løsninger hos SpareBank 1. Vi liker å skrive om det vi brenner for

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade