Hier zijn we op dag 10 van mijn Machine Learning “Adventskalender”. Ik wil je bedanken voor je steun.
Ik maak deze Google Spreadsheet-bestanden al jaren. Ze evolueerden beetje bij beetje. Maar als het tijd is om het te publiceren, kost het me altijd uren om alles opnieuw te ordenen, de lay-out op te schonen en het leesbaar te maken.
Vandaag verhuizen we naar DBSCAN.
DBSCAN leert geen parametrische modellen
Net als LOF ook DBSCAN Nee parametrisch model. Er zijn geen formules om op te slaan, geen regels, geen zwaartepunten en geen compacts om later opnieuw te gebruiken.
Wij moeten er voor zorgen de gehele dataset omdat de dichtheid van de structuur van alle punten afhangt.
Zijn volledige naam is Op dichtheid gebaseerde ruimtelijke clustering in luidruchtige toepassingen.
Maar wees voorzichtig: deze ‘dichtheid’ is geen Gaussiaanse dichtheid.
Dit is een op basis van tellingen definitie van dichtheid. Gewoon “hoeveel buren wonen er bij mij in de buurt”.
Waarom DBSCAN speciaal is
Zoals de naam al doet vermoeden, doet DBSCAN precies dat twee dingen tegelijk:
- het vindt clusters
- het markeert afwijkingen (punten die niet tot een cluster behoren)
Dit is de reden waarom ik het algoritme in deze volgorde heb gepresenteerd:
- k-methode En GM is clustermodel. Ze produceren compacte objecten: zwaartepunten voor k-gemiddelden, gemiddelde en variantie voor GMM.
- Isolatie Bos En LOF is puur anomaliedetectiemodel. Hun enige doel is om ongebruikelijke punten te vinden.
- DBSCAN tussen de twee zitten. Hij deed het allebei clustering en detectie van afwijkingenuitsluitend gebaseerd op het idee van buurtdichtheid.
Kleine datasets om alles intuïtief te houden
We blijven bij dezelfde kleine dataset die we voor LOF hebben gebruikt: 1, 2, 3, 7, 8, 12
Als je naar deze cijfers kijkt, zie je al twee compacte groepen:
één rond 1–2–3anderen in de buurt 7–8En 12 woon alleen.
DBSCAN legt deze intuïtie precies vast.
Samenvatting in 3 stappen
vroeg DBSCAN drie eenvoudige vragen voor elk punt:
- Hoeveel buren heeft u in een kleine straal (eps)?
- Heb je genoeg buren om Kernpunten (minPts) te zijn?
- Nu we de Kernpunten kennen, in welke groep val jij?
Het volgende is een samenvatting van het DBSCAN-algoritme in 3 stappen:
Laten we stap voor stap beginnen.
DBSCAN in 3 stappen
Nu we het idee van dichtheid en omgeving begrijpen, wordt DBSCAN heel gemakkelijk uit te leggen.
Alles wat het algoritme doet komt overeen drie eenvoudige stappen.
Stap 1 – Tel de buren
Het doel is om te controleren hoeveel buren elk punt heeft.
We nemen een kleine straal genaamd eps.
Voor elk punt kijken we naar alle andere punten en markeren de punten die minder dan eps verwijderd zijn.
Dit is buurman.
Dit geeft ons een eerste idee van de dichtheid:
een punt met veel buren ligt in een dicht gebied,
een punt met weinig buren woont in een schaars gebied.
Voor voorbeelden van eendimensionaal speelgoed zoals het onze zijn de gebruikelijke keuzes:
eps = 2
Rond elk punt tekenen we kleine intervallen met straal 2.
Waarom heet het zo eps?
Naam eps komt uit een Griekse letter ε (epsilon)die traditioneel in de wiskunde wordt gebruikt om a weer te geven kleine hoeveelheid of een kleine straal rond een punt.
Dus in DBSCAN, eps betekent letterlijk “kleine omgevingsradius”.
Dit beantwoordt de vraag:
Hoe ver kunnen we rond elk punt kijken?
In Excel is de eerste stap dus het berekenen paarsgewijze afstandsmatrixtel vervolgens hoeveel buren elk punt in de eps heeft.
Stap 2 – Kernpunten en dichtheidsconnectiviteit
Nu we de buren uit stap 1 kennen, passen we ze toe minutenPts om te beslissen welke punten moeten worden genomen Kern.
minPts betekent hier het minimum aantal punten.
Dit is het kleinste aantal buren dat een punt moet hebben (binnen een eps-straal) om als a te worden beschouwd Kern punt.
Een punt wordt een Kern genoemd als het tenminste een punt heeft minutenPts buren binnen eps.
Anders kan het gebeuren Grens of Lawaai.
Met eps = 2 En minPts = 2we hebben er 12 die niet Core zijn.
Zodra de kernpunten bekend zijn, hoeven we alleen nog maar eventuele punten te controleren kan worden bereikt met dichtheid van hen. Als een punt kan worden bereikt door in een eps van het ene Kernpunt naar het andere Kernpunt te gaan, behoort het tot dezelfde groep.
In Excel kunnen we dit weergeven als een eenvoudige connectiviteitstabel die laat zien welke punten verbonden zijn via Kernburen.
Deze connectiviteit is wat DBSCAN gebruikt om clusters te vormen in stap 3.
Stap 3 – Clusterlabels toewijzen
Het doel is om van connectiviteit een echt cluster te maken.
Zodra de connectiviteitsmatrix klaar is, zullen er op natuurlijke wijze clusters ontstaan.
DBSCAN groepeert eenvoudigweg alle verbonden punten samen.
Om elke groep een eenvoudige en reproduceerbare naam te geven, gebruiken we een zeer intuïtieve regel:
Een clusterlabel is het kleinste punt in een verbonden groep.
Bijvoorbeeld:
- De groep {1, 2, 3} wordt een cluster 1
- Groep {7, 8} wordt cluster 7
- Zoiets als 12 zonder buren wordt Core Lawaai
Dit is wat we in Excel zullen weergeven met behulp van formules.
Laatste gedachten
DBSCAN is perfect om het idee van lokale dichtheid te onderwijzen.
Er zijn geen waarschijnlijkheden, geen Gaussiaanse formules, geen schattingsstappen.
Even afstand, buren en een kleine straal.
Maar deze eenvoud beperkt het ook.
Omdat DBSCAN voor iedereen één vaste straal gebruikt, kan het zich niet aanpassen als de dataset clusters van verschillende schalen bevat.
HDBSCAN handhaaft dezelfde intuïtie, maar ziet alle straal en houdt wat stabiel blijft.
Dit is veel krachtiger en lijkt meer op de manier waarop mensen van nature clusters zien.
Met DBSCAN hebben we een natuurlijk moment bereikt om een stap terug te doen en de modellen zonder toezicht die we tot nu toe hebben onderzocht samen te vatten, evenals enkele andere die we nog niet hebben behandeld.
Dit is een goede gelegenheid om een kleine kaart te tekenen die deze algoritmen met elkaar verbindt en de positie van elk algoritme in het bredere landschap laat zien.
- Op afstand gebaseerd model
K-middelen, K-medoïden en hiërarchische clustering (HAC) werken door afstanden tussen punten of tussen groepen te vergelijken. - Op dichtheid gebaseerde modellen
Mean Shift en Gaussian Mixture Models (GMM) schatten de fijne dichtheid en extraheren clusters uit hun structuur. - Omgevingsgebaseerd model
DBSCAN, OPTICS, HDBSCAN en LOF definiëren clusters en afwijkingen op basis van lokale connectiviteit, niet op mondiale afstand. - Op grafieken gebaseerde modellen
Spectrale, Leuvense en Leidse clustering zijn afhankelijk van de structuur in de gelijkenisgrafiek.
Elke groep weerspiegelt een andere filosofie over wat een ‘cluster’ is.
Uw keuze voor een algoritme hangt vaak minder af van de theorie en meer van de vorm van de gegevens, de schaal van de dichtheid ervan en het type structuur dat u wilt ontdekken.
Hier ziet u hoe deze methoden met elkaar verbonden zijn:
- K-betekent generaliseert naar GMM wanneer u harde opdrachten vervangt door probabilistische dichtheden.
- DBSCAN generaliseert naar OPTICS wanneer u de noodzaak voor een enkele eps-waarde verwijdert.
- OPTICS leidt uiteraard tot HDBSCAN, waardoor dichtheidsconnectiviteit in een stabiele hiërarchie wordt omgezet.
- HAC- en Spectral-clustering bouwen beide clusters op vanaf paarsgewijze afstanden, maar Spectral voegt een op grafieken gebaseerde weergave toe.
- LOF gebruikt dezelfde omgeving als DBSCAN, maar alleen voor anomaliedetectie.
Er zijn nog veel meer modellen, maar deze geven een beeld van het landschap en de positie van DBSCAN daarin.
Morgen zullen we de adventskalender voortzetten met een meer ‘klassiek’ model dat veel gebruikt wordt in het dagelijkse machine learning.
Bedankt dat je de reis tot nu toe hebt gevolgd, en tot morgen.
