De Machine Learning “Adventskalender” Dag 10: DBSCAN in Excel

Hier zijn we op dag 10 van mijn Machine Learning “Adventskalender”. Ik wil u graag bedanken voor uw steun.

Ik bouw deze Google Spreadsheet-bestanden al jaren. Ze evolueerden beetje bij beetje. Maar als het tijd is om ze te publiceren, heb ik altijd uren nodig om alles te reorganiseren, de lay-out op te schonen en ze prettig leesbaar te maken.

Vandaag verhuizen we naar DBSCAN.

DBSCAN leert geen parametrisch model

Net als LOF is DBSCAN dat ook niet een parametrisch model. Er is geen formule om op te slaan, geen regels, geen zwaartepunten en niets compacts om later opnieuw te gebruiken.

Wij moeten de hele dataset omdat de dichtheidsstructuur van alle punten afhangt.

De volledige naam is Op dichtheid gebaseerde ruimtelijke clustering van toepassingen met ruis.

Maar let op: deze ‘dichtheid’ is geen Gaussiaanse dichtheid.

Het is een op basis van tellingen idee van dichtheid. Gewoon “hoeveel buren wonen er bij mij in de buurt”.

Waarom DBSCAN speciaal is

Zoals de naam al aangeeft, doet DBSCAN dat twee dingen tegelijk:

• het vindt clusters
• het markeert afwijkingen (de punten die niet tot een cluster behoren)

Dit is precies waarom ik de algoritmen in deze volgorde presenteer:

• k-middelen En GMM Zijn clustermodellen. Ze leveren een compact object op: zwaartepunten voor k-gemiddelden, gemiddelden en varianties voor GMM.
• Isolatie Bos En LOF Zijn pure anomaliedetectiemodellen. Hun enige doel is om ongebruikelijke punten te vinden.
• DBSCAN zit ertussen. Het doet beide clustering en detectie van afwijkingenuitsluitend gebaseerd op het begrip buurtdichtheid.

Een kleine dataset om dingen 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–3nog een in de buurt 7–8En 12 alleen wonen.

DBSCAN geeft precies deze intuïtie weer.

Samenvatting in 3 stappen

vraagt ​​DBSCAN drie eenvoudige vragen voor elk punt:

1. Hoeveel buren heeft u binnen een kleine straal (eps)?
2. Heb je genoeg buren om een ​​Kernpunt (minPts) te worden?
3. Als we eenmaal de Kernpunten kennen, tot welke verbonden groep behoort u dan?

Hier is de 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 buurten begrijpen, wordt DBSCAN heel gemakkelijk te beschrijven.
Alles wat het algoritme doet, past erin 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 waarvan de afstand kleiner is dan eps.
Dit zijn de buren.

Dit geeft ons het eerste idee van dichtheid:
een punt met veel buren ligt in een dicht gebied,
een punt met weinig buren woont in een schaars gebied.

Voor een eendimensionaal speelgoedvoorbeeld als het onze is een gebruikelijke keuze:
eps = 2

We tekenen een klein interval met straal 2 rond elk punt.

Waarom heet het eps?

De naam eps komt van de Griekse letter ε (epsilon)dat traditioneel in de wiskunde wordt gebruikt om a weer te geven kleine hoeveelheid of een kleine straal rond een punt.
Dus in DBSCAN, eps is letterlijk “de kleine buurtradius”.

Het beantwoordt de vraag:
Hoe ver kijken we rond elk punt?

Dus in Excel is de eerste stap het berekenen van de paarsgewijze afstandsmatrixen tel vervolgens hoeveel buren elk punt binnen eps heeft.

Stap 2 – Kernpunten en dichtheidsconnectiviteit

Nu we de buren uit stap 1 kennen, solliciteren we minPts om te beslissen welke punten dat zijn Kern.

minPts betekent hier het minimum aantal punten.

Het is het kleinste aantal buren dat een punt moet hebben (binnen de eps-straal) om als a te worden beschouwd Kern punt.

Een punt is Core als het dat tenminste heeft minPts buren binnen eps.
Anders kan het worden Grens of Lawaai.

Met eps = 2 En minPts = 2we hebben er 12 die niet Core zijn.

Zodra de Kernpunten bekend zijn, kijken we eenvoudigweg welke punten dat zijn dichtheid bereikbaar van hen. Als een punt kan worden bereikt door binnen eps van het ene Kernpunt naar het andere 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 connectiviteit om te zetten in daadwerkelijke clusters.

Zodra de connectiviteitsmatrix klaar is, verschijnen de clusters op natuurlijke wijze.
DBSCAN groepeert eenvoudigweg alle verbonden punten samen.

Om elke groep een eenvoudige en reproduceerbare naam te geven, gebruiken we een zeer intuïtieve regel:

Het clusterlabel is het kleinste punt in de verbonden groep.

Bijvoorbeeld:

• Groep {1, 2, 3} wordt cluster 1
• Groep {7, 8} wordt cluster 7
• Een punt als 12 zonder Kernburen wordt Lawaai

Dit is precies wat we in Excel zullen weergeven met behulp van formules.

Laatste gedachten

DBSCAN is perfect om het idee van lokale dichtheid te onderwijzen.

Er is geen waarschijnlijkheid, geen Gaussiaanse formule, geen schattingsstap.
Gewoon afstanden, 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 behoudt dezelfde intuïtie, maar kijkt ernaar alle stralen en houdt wat stabiel blijft.
Het is veel robuuster en komt veel dichter in de buurt van hoe 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 een paar andere die we nog niet hebben behandeld.

Het is een goede gelegenheid om een ​​kleine kaart te tekenen die deze algoritmen met elkaar verbindt en laat zien waar elk van hen zich in het bredere landschap bevindt.

• Op afstand gebaseerde modellen
  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 een vloeiende dichtheid en extraheren clusters uit de structuur ervan.
• Buurtgebaseerde modellen
  DBSCAN, OPTICS, HDBSCAN en LOF definiëren clusters en afwijkingen op basis van lokale connectiviteit in plaats van mondiale afstand.
• Grafiekgebaseerde modellen
  Spectrale clustering, Leuven en Leiden vertrouwen op de structuur binnen gelijkenisgrafieken.

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 soort structuren dat u verwacht te vinden.

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 wegneemt.
• OPTICS leidt uiteraard tot HDBSCAN, dat dichtheidsconnectiviteit omzet in een stabiele hiërarchie.
• HAC- en Spectral-clustering bouwen beide clusters op vanaf paarsgewijze afstanden, maar Spectral voegt een op grafieken gebaseerde weergave toe.
• LOF gebruikt dezelfde buurten als DBSCAN, maar alleen voor anomaliedetectie.

Er zijn nog veel meer modellen, maar dit geeft een idee van het landschap en waar DBSCAN daarin past.

Morgen zullen we de adventskalender voortzetten met modellen die ‘klassieker’ zijn en veel worden gebruikt in het dagelijkse machine learning.
Bedankt voor het volgen van de reis tot nu toe, en tot morgen.