Nearest neighbor: patroonherkenning via de naaste buur

Wat is nearest neighbor?

Nearest neighbor is een techniek die de eigenschappen van een onbekend element schat door met een afstandsfunctie het dichtstbijzijnde element met bekende eigenschappen te zoeken en diens indeling over te nemen.

Onze buren zijn heel vaak ons soort mensen. Ze hebben een soortgelijk huis en daarom vaak een soortgelijk inkomen en een soortgelijke auto, en de overeenkomsten kunnen verder gaan: de sportverenigingen van de kinderen, de scholen en de liefhebberijen. Toch is er geen gelijkvormigheid: de buren van mijn buren verschillen waarschijnlijk meer van mij, en de bewoners aan het eind van de straat nog meer. Zolang de huizen qua grootte vergelijkbaar zijn, worden de overeenkomsten kleiner naarmate de afstand toeneemt.

Omgekeerd zijn de eigenschappen van de bewoners van een willekeurig huis te schatten door eerst te bepalen in welk deel van de wijk het ligt en ze vervolgens gelijk te stellen aan die van het dichtstbijzijnde huis waarvan de eigenschappen bekend zijn: de naaste buur. De techniek is een van de methoden van predictive analytics en wordt vooral toegepast bij patroon- en beeldherkenning. Ze bestaat feitelijk uit een combinatie van clusteren met elementen uit lineaire regressie.

Het probleem van de naaste buur

Gezond verstand leert dat alle eigenschappen nauwkeurig bepalen onmogelijk is, maar dat het moet lukken bewoners in groepen in te delen. Dat betekent feitelijk het clusteren van de bewoners op een aantal bepalende eigenschappen, met de gegevens van een beperkt aantal bewoners, soms zelfs uit andere wijken. Vervolgens moet je van elk huis de naaste buur bepalen: welk al ingedeeld huis ligt er zo dicht mogelijk bij? Hoe bepaal je die afstand, en welke factoren spelen mee? Is alleen de meetkundige afstand van belang, of telt een andere straat ook? Het begrip afstand is niet per definitie gelijk aan de meetkundige afstand. Zo nodig pas je de berekende afstand aan op grond van aanvullende factoren.

Een schematisch voorbeeld

Neem aan dat van vijf punten de eigenschappen bekend zijn. Op grond daarvan valt elk punt in een groep: de punten 1 en 2 zijn grijs, punt 3 is wit, de punten 4 en 5 zijn zwart. Drie nieuwe punten A, B en C moeten in een van de drie groepen worden ingedeeld. Gemeten met de meetkundige afstand ligt punt A het dichtst bij het witte punt en punt B bij een grijs punt. Punt C is een probleem, omdat de afstand tot de bekende punten 1, 3 en 5 gelijk is. Voor punt C staan twee wegen open:

• De status blijft onbenoemd.
• De status wordt opnieuw bepaald, waarbij de afstanden tot de nieuw ingedeelde punten A en B meetellen.

Welke weg je kiest, hangt sterk af van de toepassing en de gegevens. Het oplossen van het probleem komt neer op twee vragen: op grond van welke eigenschappen vorm je de groepen, en hoe bepaal je tot welke groep een nieuw element behoort? Het antwoord hangt sterk af van de gebruikte gegevens en de gewenste eigenschappen, en de techniek vraagt om a-priori-informatie: enige kennis over de vorm van de uiteindelijke oplossing.

Een van de grote kwaliteiten van de methode ligt in de flexibiliteit van de afstandsbepaling. Je kunt er een vorm of patroon in opnemen. Dat is vooral nuttig bij het verwerken van beeldinformatie, zoals gezichtsherkenning in bewakingsbeelden en het opsporen van organen en botten in medische beelden. Nearest neighbor laat zich bovendien eenvoudig vertalen naar meerdere dimensies.

De beperkingen: de campagne van een autobedrijf

De techniek is bijzonder krachtig in patroonherkenning, mits je de instellingen juist kiest, en omdat ze twee technieken combineert, moeten de instellingen voor het clusteren en voor de afstandsbepaling tegelijk kloppen. De methode hangt daarom sterk af van de kwaliteit van de voorkennis over de situatie.

Stel dat een bedrijf meer auto’s uit het lagere middenklassesegment wil verkopen. Om potentiële klanten in een bepaalde buitenwijk op te sporen gebruikt de afdeling verkoop nearest neighbor. Het startpunt is het eigen klantenbestand in die wijk en de aanname dat buren vaak hetzelfde type auto hebben. De instellingen: clusteren vanuit de eigen klanten met een auto uit de lagere middenklasse, en de huizen nemen die maximaal twee huizen van een bekend huis af liggen. De analyse levert een serie adressen op die een uitnodiging voor de showroom met een goede aanbieding krijgen. Tot verbazing van de afdeling verkoop is de respons minimaal. Er zijn drie fouten gemaakt:

1. De aanleiding voor de campagne is het uitbreiden van het aantal klanten in de wijk, waaruit blijkt dat de dekking onvoldoende is: er zijn te weinig bekende punten.
2. Naastliggende huizen hoeven niet dezelfde eigenschappen te hebben (denk aan achterburen).
3. De gekozen afstandsbepaling is in combinatie met de beperkte dekking niet voldoende om alle mogelijke klanten te bereiken.

Na twee aanpassingen, het vergroten van het aantal bekende punten zodat de clustering verbetert en een afstandsmaat waarin ‘naaste buur’ beperkt is tot de naastwonende buren, is de actie ineens wél succesvol. Verdere verbetering is haalbaar door meer informatie in de clustering op te nemen, zoals merkentrouw.

Nearest neighbor versus neuraal netwerk

Nearest neighbor versus neuraal netwerk

Beide worden gebruikt voor patroonherkenning, maar het zijn totaal verschillende technieken.

Beide methoden gebruiken a-priorikennis: het neuraal netwerk om te leren, nearest neighbor voor de clustering. Het belangrijke verschil is dat een neuraal netwerk zich gedraagt als een black box waarop de gebruiker weinig of geen invloed heeft, terwijl bij nearest neighbor een foute keuze in een van de twee deelmethoden duidelijke gevolgen heeft. Welke methode het best toepasbaar is, hangt af van de situatie.

Verder lezen

• Predictive analytics
• Clusteranalyse
• Lineaire regressie
• Machine learning

Over de auteur

Herman van Dellen

Herman is een zeer ervaren data scientist die machine learning en statistiek al jarenlang toepast op gebieden als CRM, BI en datawarehousing. Hij bouwde zijn carrière op bij IBM, waar hij de Business Intelligence Services Unit oprichtte.

Over Diamond Decisions

Diamond Decisions helpt organisaties beter te worden door betere beslissingen mogelijk te maken. We starten niet bij data, dashboards of AI, maar bij de beslissing die beter moet, en bouwen van daaruit terug naar KPI’s, data en technologie. Dat doen we in vier stappen: inspiratie en alignment, business modeling, analytics en dataplatform en datagedreven beslissers. Zo zorgen we dat BI en AI geen IT-project blijven, maar elke dag waarde opleveren.