Ok, laten we het eens over DBSCAN hebben.
Density-based spatial clustering of applications with noise (DBSCAN) is een bekend data clustering algoritme dat veel wordt gebruikt in data mining en machine learning.
Gebaseerd op een verzameling punten (laten we denken in een tweedimensionale ruimte zoals geïllustreerd in de figuur), groepeert DBSCAN punten die dicht bij elkaar liggen op basis van een afstandsmeting (meestal Euclidische afstand) en een minimum aantal punten. Het markeert ook de punten die zich in gebieden met een lage dichtheid bevinden als uitschieters.
Parameters:
Het DBSCAN-algoritme vereist in principe 2 parameters:
eps: specificeert hoe dicht punten bij elkaar moeten liggen om als deel van een cluster te worden beschouwd. Dit betekent dat als de afstand tussen twee punten kleiner of gelijk is aan deze waarde (eps), deze punten als buren worden beschouwd.
minPoints: het minimum aantal punten om een dichte regio te vormen. Als we de parameter minPoints bijvoorbeeld instellen op 5, dan hebben we ten minste 5 punten nodig om een dicht gebied te vormen.
Parameterschatting:
Het schatten van parameters is een probleem voor elke dataminingtaak. Om goede parameters te kiezen moeten we begrijpen hoe ze worden gebruikt en op zijn minst een basiskennis hebben over de dataset die zal worden gebruikt.
eps: als de gekozen eps-waarde te klein is, zal een groot deel van de gegevens niet worden geclusterd. Het zal worden beschouwd als uitbijters omdat niet voldoen aan het aantal punten om een dichte regio te creëren. Anderzijds, als de gekozen waarde te hoog is, zullen clusters samensmelten en zal de meerderheid van de objecten in dezelfde cluster zitten. De eps moet worden gekozen op basis van de afstand van de dataset (we kunnen een k-afstandsgrafiek gebruiken om die te vinden), maar in het algemeen zijn kleine eps-waarden te verkiezen.
minPoints: Als algemene regel kan een minimum minPoints worden afgeleid uit een aantal dimensies (D) in de dataset, als minPoints ≥ D + 1. Grotere waarden zijn gewoonlijk beter voor gegevensreeksen met ruis en zullen meer significante clusters vormen. De minimumwaarde voor de minPoints moet 3 zijn, maar hoe groter de gegevensverzameling, hoe groter de minPoints waarde die moet worden gekozen.
U vindt hier meer over parameterschatting.
Waarom moeten we DBSCAN gebruiken?
Het DBSCAN-algoritme moet worden gebruikt om associaties en structuren in gegevens te vinden die moeilijk handmatig te vinden zijn, maar die relevant en nuttig kunnen zijn om patronen te vinden en trends te voorspellen.
Clusteringmethoden worden gewoonlijk gebruikt in de biologie, geneeskunde, sociale wetenschappen, archeologie, marketing, tekenherkenning, managementsystemen enzovoort.
Laten we eens denken aan een praktisch gebruik van DBSCAN. Stel, we hebben een e-commerce en we willen onze verkoop verbeteren door onze klanten relevante producten aan te bevelen. We weten niet precies waar onze klanten naar op zoek zijn, maar op basis van een dataset kunnen we een relevant product voorspellen en aanbevelen aan een specifieke klant. Wij kunnen DBSCAN toepassen op onze dataset (gebaseerd op de e-commerce database) en clusters vinden op basis van de producten die de gebruikers hebben gekocht. Met behulp van deze clusters kunnen we overeenkomsten vinden tussen klanten, bijvoorbeeld, de klant A heeft 1 pen, 1 boek en 1 schaar gekocht en de klant B heeft 1 boek en 1 schaar gekocht, dan kunnen we 1 pen aanbevelen aan de klant B. Dit is slechts een klein voorbeeld van het gebruik van DBSCAN, maar het kan in veel toepassingen op verschillende gebieden worden gebruikt.
Hoe kunnen we het gemakkelijk implementeren?
Zoals ik al schreef (tip: geloof niet alles wat ik schrijf) is DBSCAN een bekend algoritme, daarom hoef je je geen zorgen te maken over het zelf implementeren ervan. Je kunt een van de bibliotheken/pakketten gebruiken die op het internet te vinden zijn. Hier is een lijst van links waar je de DBSCAN implementatie kunt vinden: Matlab, R, Python.
Ik heb ook een applicatie ontwikkeld (in het Portugees) om op een didactische manier uit te leggen hoe DBSCAN werkt. De applicatie is geschreven in C++ en je kunt hem vinden op Github.