Dbscan clustering
Dichtheid als basis
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is een clusteralgoritme dat clusters definieert als gebieden met hoge dichtheid, gescheiden door gebieden met lage dichtheid. Het algoritme heeft twee parameters: eps (de maximale afstand tussen twee punten om als buren te worden beschouwd) en minPts (het minimum aantal punten in een buurt om een kernpunt te vormen). Een punt is een kernpunt als er binnen een straal van eps ten minste minPts punten liggen, inclusief het punt zelf. Randpunten liggen binnen de buurt van een kernpunt maar hebben zelf niet genoeg buren. Alle andere punten zijn ruis. Clusters worden gevormd door kernpunten en hun bereikbare buren. DBSCAN kan clusters van willekeurige vorm vinden, in tegenstelling tot K-Means dat bolvormige clusters veronderstelt. Het hoeft het aantal clusters niet vooraf te specificeren en is robuust tegen uitbijters. Nadelen zijn de gevoeligheid voor de parameters eps en minPts, en de moeilijkheid om clusters van sterk verschillende dichtheden te vinden. Bij hoogdimensionale data presteert DBSCAN slecht door de vloek van dimensionaliteit. Het wordt veel gebruikt in geospatiale analyse, anomaliedetectie en beeldsegmentatie.
Parameters en varianten
De keuze van eps en minPts is cruciaal voor DBSCAN. Een veelgebruikte vuistregel is minPts = 2 * aantal dimensies. Voor eps kan een k-distance plot helpen: men berekent voor elk punt de afstand tot de k-de dichtstbijzijnde buur (met k = minPts) en sorteert deze afstanden. De 'knie' in de plot geeft een geschikte eps. DBSCAN is niet deterministisch voor randpunten: een randpunt kan tot meerdere clusters behoren, afhankelijk van de verwerkingsvolgorde. Er bestaan varianten zoals OPTICS, die een ordening van punten naar dichtheid produceert en daardoor beter omgaat met variërende dichtheden. HDBSCAN is een hiërarchische variant die automatisch de beste clustering selecteert en minder gevoelig is voor parameters. DBSCAN wordt toegepast in het detecteren van fraude, het groeperen van GPS-coördinaten, het identificeren van sterrenstelsels en het segmenteren van medische beelden. Het is ook nuttig bij het opschonen van data: ruispunten kunnen worden verwijderd. Een beperking is de rekencomplexiteit: zonder indexstructuur is deze O(n^2). Met een R-tree of KD-tree kan dit worden teruggebracht tot O(n log n). DBSCAN blijft een krachtig hulpmiddel voor unsupervised learning.