Wat is nearest neighbor methode: patroon- en beeldherkenning volgens naastebuurmethodiek

Achterburen en overburen

Aangaande achterburen en overburen is het vaak lastiger om uitspraken te doen. Soms wonen deze mensen in andere huizen waardoor ze voldoen aan andere eigenschappen, maar ook nu zijn er grote overeenkomsten mogelijk. Uiteindelijk lijkt het erop dat zolang de huizen qua grootte vergelijkbaar zijn de overeenkomsten kleiner worden naarmate de afstand toeneemt.

Omgekeerd betekent dit dat de eigenschappen van de bewoners van een willekeurig huis bepaald kunnen worden door eerst te bepalen in welk deel van de wijk het ligt. Vervolgens worden de eigenschappen van de bewoners gelijkgesteld aan die van het dichtstbijzijnde huis waarvan de eigenschappen bekend zijn, de naaste buur (nearest neighbor).

Patroonherkenning met nearest neighbor

De techniek van de nearest neighbor / naaste buur pas je vooral toe bij patroon- en beeldherkenning. Ze bestaat feitelijk uit een combinatie van clusteren met elementen uit lineaire regressie. Om dit duidelijk te maken wordt eerst het simpele voorbeeld van de buitenwijk scherper gedefinieerd en wordt de verbinding gemaakt richting patronen beeldherkenning.

Het probleem van de naaste buur

De belangrijke vraag uit de inleiding was hoe de (eigenschappen van de) buren beschreven kunnen worden vanuit de eigenschappen van de bewoners van een willekeurig ander huis. Hierbij nemen we aan dat de overeenkomsten tussen de bewoners van verschillende huizen groter is naarmate ze dichter bij elkaar wonen. Gezond verstand leert dat nauwkeurig bepalen van alle eigenschappen onmogelijk is, maar dat het zeker moet lukken om bewoners in verschillende groepen in te delen.

Afhankelijk van de groep waarin bewoners worden ingedeeld zijn hun eigenschappen bekend. Feitelijk betekent dit het clusteren van de bewoners van de buitenwijk op grond van een aantal bepalende eigenschappen. Het bepalen van de verschillende groepen moet je echter doen met de gegevens van een beperkt aantal bewoners, soms zelfs op basis van gegevens van andere (buiten)wijken.

Welke factoren spelen allemaal mee?

De volgende stap is dat je van elk huis onder beschouwing de nearest neighbor moet bepalen. Met andere woorden welk al ingedeeld huis ligt er zo dicht mogelijk bij. De vraag is dan natuurlijk op welke manier je die afstand moet bepalen en vooral welke factoren er meespelen. Is alleen de meetkundige afstand van belang of spelen andere factoren, zoals een andere straat, ook een rol? Met andere woorden, het begrip afstand is niet per definitie identiek aan de meetkundige afstand. De meetkundige afstand bepaal je op een manier die gelijkwaardig is aan de methode die je volgt bij lineaire regressie. Zo nodig ga je deze berekende afstand aanpassen op grond van aanvullende factoren.
Het Big Data boek 'De intelligente, datagedreven organisatie' Het big data-boek (een compleet recept voor datagedreven werken in 10 stappen) gaat dieper in op de datamining-technieken, zoals nearest neighbor, die essentieel zijn in het herkennen van patronen en informatie in je data. Maak de business case voor data science in jouw organisatie en wordt intelligenter met dit boek.bekijk het Big Data boek 'De intelligente, datagedreven organisatie'De training R & data mining Tijdens de Training R & data mining maak je in 3 intensieve dagen kennis met het vakgebied Predictive Analytics, data mining & text mining. Ook het concept Big Data, privacy en ethiek komen natuurlijk langs, maar je leert vooral programmeren in R & WEKA.bekijk de training R & data mining

Schema nearest neighbor

Dit probleem laat zich eenvoudig schematiseren. Neem aan dat van een beperkt aantal punten (1 tot 5) de eigenschappen bekend zijn. Elk van deze punten valt op grond van zijn eigenschappen in een bepaalde groep (grijstint) waarvan de uitbreiding niet bekend is. De verdeling van de (bekende) punten over de groepen is:

1. grijs voor de punten 1 en 2
2. wit voor punt 3
3. zwart voor de punt 4 en 5

De drie punten a, b en c moeten in één van de drie groepen worden ingedeeld. Kijkend naar dit schema is het logisch dat punt A in de witte groep komt en punt B in de grijze groep. Punt C lijkt een probleem te worden omdat de afstand tot elk van de bekende punten 1, 3 en 5 gelijk is. Opnieuw zegt ons gevoel dat na het indelen van de punten A en B, het mogelijk moet zijn om punt C ook in te delen. De vraag is nu alleen nog hoe een dergelijke (intuïtieve) oplossing verpakt kan worden in een formele oplossing.

Samengevat betekent het oplossen van dit probleem het vinden van de antwoorden op twee vragen:

• Op grond van welke eigenschappen ga je de verschillende groepen indelen?
• Hoe bepaal je tot welke groep een willekeurig nieuw element behoort?

Merk hierbij op dat het antwoord sterk afhankelijk is van de gebruikte gegevens en van de gewenste eigenschappen. Ook vraagt het gebruik van de techniek van de naaste buur om gebruik van a priori informatie. Er moet dus enige kennis zijn aangaande de vorm van de uiteindelijke oplossing.

De oplossingen voor nearest neighbor

Het antwoord op de eerste vraag is een indeling van de verschillende huishoudens in groepen op grond van hun specifieke eigenschappen. Na de clustering zijn de vijf punten met bekende eigenschappen opgedeeld in drie groepen.

Voor de afstand ga je in dit voorbeeld de meetkundige afstand nemen zoals gebruikt bij lineaire regressie. Dit is de afstand die gemeten kan worden met bijvoorbeeld een meetlat. Door nu de afstanden tot de bekende punten (1 tot met 5) te bepalen is het mogelijk de niet ingedeelde punten (a, b en c) aan een groep toe te kennen. Op grond van de gevonden afstanden ligt punt A het dichtst bij het witte punt en punt B bij het grijze punt. Bij punt C is een keuze niet mogelijk omdat de afstand tot drie verschillende bekende punten (de punten 1, 3 en 5) gelijk is. Voor de status van punt C staan nu twee wegen open:

1. De status blijft onbenoemd.
2. De status ga je opnieuw bepalen, waarbij de afstanden van punten A en B meetellen.

Welke weg je verder volgt hangt sterk af van de applicatie en de gegevens, maar dit moet je van geval tot geval bepalen.

Een van de grote kwaliteiten van deze methode ligt in de flexibiliteit van de afstandsbepaling. Zo is het mogelijk om in deze afstandsbepaling een vorm of patroon op te nemen. Dit is vooral nuttig bij het verwerken van beeldinformatie zoals gezichtsherkenning in bewakingsbeelden en het opsporen van organen en botten in medische beelden. In dit laatste geval speelt ook mee dat de naaste buur zich eenvoudig laat vertalen naar meerdere dimensies.

De beperkingen van naaste buur

De techniek van de naaste buur is bijzonder krachtig als het gaat om patroonherkenning, mits je de instellingen juist kiest. En omdat naaste buur feitelijk een combinatie is van twee enkelvoudige technieken, gaat het om de juiste instellingen voor deze twee technieken gelijktijdig. Anders gezegd, de instellingen voor het clusteren en de afstandsbepaling moeten kloppen. Dit betekent dat de methode sterk afhankelijk is van de kwaliteit van de a priori kennis van de situatie en van het gebruik van deze kennis.

Stel een bedrijf wil graag meer auto’s verkopen uit het lagere middenklassesegment. Om potentiële klanten in een bepaalde buitenwijk op te sporen wil de afdeling verkoop de nearest neighbor gebruiken. Als startpunt gebruiken ze hun klantenbestand in een bepaalde buitenwijk en de aanname dat buren (gedefinieerd als de bewoners van het naastliggende huis) vaak hetzelfde type auto hebben. Dit betekent dat de volgende instellingen gebruikt worden:

• Clusteren vanuit de eigen klanten die een auto uit de lagere middenklasse hebben.
• Afstand door de huizen te nemen die maximaal op twee huizen afstand liggen van een bekend huis.

Deze analyse levert een serie adressen op waar het bedrijf een uitnodiging naar stuurt voor een bezoek aan de showroom en een goede aanbieding. Tot verbazing van de afdeling verkoop is de respons minimaal.

Een aantal opvallende fouten

Hoewel de opzet van de analyse in eerste instantie goed lijkt, wordt er toch een aantal opvallende fouten gemaakt:

• Fout 1: de motivatie tot de campagne is het uitbreiden van het aantal klanten in de betreffende wijk. Hieruit blijkt dat de dekking niet voldoende is waardoor er te weinig bekende punten zijn.
• Fout 2: naastliggende huizen hoeven niet dezelfde eigenschappen te hebben (denk maar eens aan achterburen).
• Fout 3: de gekozen afstandsbepaling is in combinatie met de beperkte dekking van de wijk niet voldoende om alle mogelijke klanten te bereiken.

Dit betekent dat voor een succesvolle actie aanpassingen nodig zijn zoals:

• Aanpassing 1: vergroting van het aantal bekende punten waardoor de clustering verbetert.
• Aanpassing 2: gebruikmaken van een afstandsmeting waarin het begrip naaste buur beperkt wordt tot de naastwonende buren.

Actie met nearest neighbor ineens wel succesvol

Na het doorvoeren van de aanpassingen blijkt de actie ineens wel succesvol te zijn om de volgende redenen:

• Betere clusteranalyse van de bekende informatie. Gebruik van een afstandsdefinitie die beter bij het begrip ‘buren’ aansluit. Verdere verbeteringen zijn nog haalbaar door meer informatie in de clustering op te nemen zoals merkentrouw (rijders van bepaalde automerken hebben de neiging om niet over te stappen naar een ander merk terwijl dit ook andersom kan zijn).
• Redenerend vanuit de belangrijkste toepassing zoals patroonherkenning lijkt naaste buur een concurrent van het neurale netwerk. Echter, ondanks de grote overlap in toepassingsgebied, zijn het twee totaal verschillende technieken.
• Neuraal netwerk: bepaalt uitgaand van een bepaalde verzameling gegevens een zeker onderling verband waaruit een antwoord volgt, eventueel met een zekere waarschijnlijkheid.
• Nearest neighbor: maakt een schatting van eigenschappen van een onbekend element door een afstandsfunctie te gebruiken.

Beide methoden maken gebruik van a priori kennis: het neuraal netwerk om te leren, de nearest neighbor voor de clustering. Belangrijk verschil is dat een neuraal netwerk zich gedraagt als een “black box” waarbij de gebruiker geen of weinig invloed heeft op het proces. Dit terwijl bij de naaste buur een foute keuze van de gebruiker in één van de deelmethodes duidelijke gevolgen heeft. Het hangt daarom van de actuele situatie af welke methode het best toepasbaar is. Dit is opnieuw een keuze van de gebruiker.

Meer weten over nearest neighbor technieken?

De specialisten van Passionned Group kennen als geen ander de (on)mogelijkheden van nearest neighbor en de verschillende predictive analytics tools. Maak vrijblijvend een afspraak met een van onze experts in machine learning en laat je verrassen door wat wij voor je in petto hebben.

Over Passionned Group

De nearest neighbor specialisten van de Passionned Group helpen je graag met het opzetten en verfijnen van data mining algoritmes & data science trajecten. Met als doel jouw organisatie slimmer te laten werken. Om het jaar organiseren wij de verkiezing tot de Slimste organisatie van Nederland. De vorige editie is gewonnen door fietsenwinkel.nl.

neem contact met ons op