DBSCAN med Scikit-Learn i Python

Introduktion

Du arbejder i en konsulentvirksomhed som data scientist. Det projekt, du i øjeblikket blev tildelt, har data fra studerende, der for nylig har afsluttet kurser om økonomi. Den finansielle virksomhed, der afholder kurserne, ønsker at forstå, om der er fælles faktorer, der påvirker eleverne til at købe de samme kurser eller til at købe forskellige kurser. Ved at forstå disse faktorer kan virksomheden oprette en elevprofil, klassificere hver elev efter profil og anbefale en liste over kurser.

Når du inspicerer data fra forskellige elevgrupper, er du stødt på tre dispositioner af punkter, som i 1, 2 og 3 nedenfor:

Bemærk, at i plot 1 er der lilla punkter organiseret i en halv cirkel, med en masse lyserøde punkter inde i den cirkel, en lille koncentration af orange punkter uden for den halvcirkel og fem grå punkter, der er langt fra alle andre.

I plot 2 er der en rund masse af lilla spidser, en anden med orange spidser, og også fire grå punkter, der er langt fra alle de andre.

Og i plot 3 kan vi se fire koncentrationer af punkter, lilla, blå, orange, lyserøde og tre mere fjerne grå punkter.

Hvis du nu skulle vælge en model, der kunne forstå nye elevdata og bestemme lignende grupper, er der så en klyngealgoritme, der kunne give interessante resultater til den slags data?

Ved beskrivelsen af ​​grundene nævnte vi udtryk som masse af punkter , koncentration af punkter, hvilket indikerer, at der er områder i alle grafer med større tæthed. Vi henviste også til cirkulær , halvcirkelformet figurer, som er svære at identificere ved at tegne en lige linje eller blot undersøge de nærmeste punkter. Derudover er der nogle fjerne punkter, der sandsynligvis afviger fra den primære datadistribution, hvilket introducerer flere udfordringer eller støj ved fastlæggelse af grupperne.

En tæthedsbaseret algoritme, der kan filtrere støj fra, som f.eks DBSCAN (Densitet-Based Spatial Cglans af Aapplikationer med Noise), er et stærkt valg til situationer med tættere områder, afrundede former og støj.

Om DBSCAN

DBSCAN er en af ​​de mest citerede algoritmer i forskning, dens første publikation udkom i 1996, dette er originalt DBSCAN papir. I papiret demonstrerer forskere, hvordan algoritmen kan identificere ikke-lineære rumlige klynger og håndtere data med højere dimensioner effektivt.

Hovedtanken bag DBSCAN er, at der er et minimum antal punkter, der vil være inden for en bestemt afstand eller radius fra det mest "centrale" klyngepunkt, kaldet kernepunkt. Punkterne inden for denne radius er kvarterpunkterne, og punkterne på kanten af ​​det kvarter er grænsepunkter or grænsepunkter. Radius eller naboafstand kaldes epsilon kvarter, ε-kvarter eller bare ε (symbolet for det græske bogstav epsilon).

Derudover, når der er punkter, der ikke er kernepunkter eller grænsepunkter, fordi de overskrider radius for at tilhøre en bestemt klynge og heller ikke har det mindste antal punkter til at være et kernepunkt, betragtes de som støjpunkter.

Det betyder, at vi har tre forskellige typer punkter, nemlig kerne, grænse , støj. Ydermere er det vigtigt at bemærke, at hovedideen grundlæggende er baseret på en radius eller afstand, hvilket gør DBSCAN – som de fleste klyngemodeller – afhængig af denne afstandsmetrik. Denne metrik kunne være euklidisk, Manhattan, Mahalanobis og mange flere. Derfor er det afgørende at vælge en passende afstandsmåling, der tager hensyn til konteksten af ​​dataene. For eksempel, hvis du bruger køreafstandsdata fra en GPS, kan det være interessant at bruge en metrik, der tager højde for gadelayout, såsom Manhattan-afstand.

For at finde kernepunktet vil DBSCAN først vælge et punkt tilfældigt, kortlægge alle punkter inden for dets ε-kvarter og sammenligne antallet af naboer til det valgte punkt med minimumsantallet af punkter. Hvis det valgte punkt har et lige stort antal eller flere naboer end minimumsantallet af punkter, vil det blive markeret som et kernepunkt. Dette kernepunkt og dets nabopunkter vil udgøre den første klynge.

Algoritmen vil derefter undersøge hvert punkt i den første klynge og se, om den har lige mange eller flere nabopunkter end minimumsantallet af punkter inden for ε. Hvis det gør det, vil disse nabopunkter også blive tilføjet til den første klynge. Denne proces vil fortsætte, indtil punkterne i den første klynge har færre naboer end minimumsantallet af punkter inden for ε. Når det sker, stopper algoritmen med at tilføje punkter til den klynge, identificerer et andet kernepunkt uden for klyngen og opretter en ny klynge for det nye kernepunkt.

DBSCAN gentager derefter den første klyngeproces med at finde alle punkter, der er forbundet med et nyt kernepunkt i den anden klynge, indtil der ikke er flere punkter, der skal tilføjes til klyngen. Det vil så støde på et andet kernepunkt og skabe en tredje klynge, eller det vil iterere gennem alle de punkter, som det ikke tidligere har set på. Hvis disse punkter er i ε afstand fra en klynge, føjes de til denne klynge og bliver til grænsepunkter. Hvis de ikke er det, betragtes de som støjpunkter.

Det er interessant at vide, hvordan DBSCAN-algoritmen fungerer, selvom der heldigvis ikke er behov for at kode algoritmen, når først Pythons Scikit-Learn-bibliotek allerede har en implementering.

Lad os se, hvordan det fungerer i praksis!

Import af data til klyngedannelse

For at se hvordan DBSCAN fungerer i praksis, vil vi ændre lidt på projekter og bruge et lille kundedatasæt, der har genre, alder, årlig indkomst og forbrugsscore på 200 kunder.

Forbrugsscoren går fra 0 til 100 og repræsenterer, hvor ofte en person bruger penge i et indkøbscenter på en skala fra 1 til 100. Med andre ord, hvis en kunde har en score på 0, bruger de aldrig penge, og hvis scoren er 100, er de den højeste bruger.

Efter at have downloadet datasættet, vil du se, at det er en CSV-fil (kommaseparerede værdier) kaldet shopping-data.csv, indlæser vi det i en DataFrame ved hjælp af Pandas og gemmer det i customer_data variabel:

import pandas as pd path_to_file = '../../datasets/dbscan/dbscan-with-python-and-scikit-learn-shopping-data.csv'
customer_data = pd.read_csv(path_to_file)

For at tage et kig på de første fem rækker af vores data, kan du udføre customer_data.head():

Dette resulterer i:

 CustomerID Genre Age Annual Income (k$) Spending Score (1-100)
0 1 Male 19 15 39
1 2 Male 21 15 81
2 3 Female 20 16 6
3 4 Female 23 16 77
4 5 Female 31 17 40

Ved at undersøge dataene kan vi se kunde-id-numre, genre, alder, indkomster i k$ og forbrugsscore. Husk, at nogle eller alle disse variabler vil blive brugt i modellen. For eksempel hvis vi skulle bruge Age , Spending Score (1-100) som variabler for DBSCAN, som bruger en afstandsmetrik, er det vigtigt at bringe dem til en fælles skala for at undgå at indføre forvrængninger, da Age måles i år og Spending Score (1-100) har et begrænset område fra 0 til 100. Det betyder, at vi vil udføre en form for dataskalering.

Vi kan også kontrollere, om dataene har brug for mere forbehandling bortset fra skalering ved at se, om typen af ​​data er konsistent, og kontrollere, om der mangler værdier, som skal behandles ved at udføre Panda's info() metode:

customer_data.info()

Dette viser:

<class 'pandas.core.frame.DataFrame'>
RangeIndex: 200 entries, 0 to 199
Data columns (total 5 columns): # Column Non-Null Count Dtype --- ------ -------------- ----- 0 CustomerID 200 non-null int64 1 Genre 200 non-null object 2 Age 200 non-null int64 3 Annual Income (k$) 200 non-null int64 4 Spending Score (1-100) 200 non-null int64 dtypes: int64(4), object(1)
memory usage: 7.9+ KB

Vi kan observere, at der ikke mangler værdier, fordi der er 200 ikke-nul indgange for hver kundefunktion. Vi kan også se, at det kun er genrespalten, der har tekstindhold, da det er en kategorisk variabel, som vises som object, og alle andre funktioner er numeriske af typen int64. Med hensyn til datatypekonsistens og fravær af nulværdier er vores data således klar til yderligere analyse.

Vi kan fortsætte med at visualisere dataene og bestemme, hvilke funktioner der ville være interessante at bruge i DBSCAN. Efter at have valgt disse funktioner, kan vi skalere dem.

Dette kundedatasæt er det samme som det, der bruges i vores definitive guide til hierarkisk klyngedannelse. For at lære mere om disse data, hvordan man udforsker dem og om afstandsmålinger, kan du tage et kig på Definitiv guide til hierarkisk klyngedannelse med Python og Scikit-Learn!

Visualisering af data

Ved at bruge Seaborn's pairplot(), kan vi plotte en scatter-graf for hver kombination af funktioner. Siden CustomerID er blot en identifikation og ikke en funktion, vi fjerner den med drop() inden plotning:

import seaborn as sns customer_data = customer_data.drop('CustomerID', axis=1) sns.pairplot(customer_data);

Dette udsender:

Når man ser på kombinationen af ​​funktioner produceret af pairplot, grafen af Annual Income (k$) med Spending Score (1-100) synes at vise omkring 5 grupper af punkter. Dette ser ud til at være den mest lovende kombination af funktioner. Vi kan oprette en liste med deres navne, vælg dem fra customer_data DataFrame, og gem valget i customer_data variabel igen til brug i vores fremtidige model.

selected_cols = ['Annual Income (k$)', 'Spending Score (1-100)']
customer_data = customer_data[selected_cols]

Efter at have valgt kolonnerne, kan vi udføre den skalering, der blev diskuteret i det foregående afsnit. For at bringe funktionerne til samme skala eller standardisere dem, kan vi importere Scikit-Learn's StandardScaler, opret det, tilpas vores data for at beregne dens middelværdi og standardafvigelse, og transformer dataene ved at trække deres middelværdi fra og dividere dem med standardafvigelsen. Dette kan gøres i ét trin med fit_transform() metode:

from sklearn.preprocessing import StandardScaler ss = StandardScaler() scaled_data = ss.fit_transform(customer_data)

Variablerne er nu skaleret, og vi kan undersøge dem ved blot at udskrive indholdet af scaled_data variabel. Alternativt kan vi også tilføje dem til en ny scaled_customer_data DataFrame sammen med kolonnenavne og brug head() metode igen:

scaled_customer_data = pd.DataFrame(columns=selected_cols, data=scaled_data)
scaled_customer_data.head()

Dette udsender:

 Annual Income (k$) Spending Score (1-100)
0 -1.738999 -0.434801
1 -1.738999 1.195704
2 -1.700830 -1.715913
3 -1.700830 1.040418
4 -1.662660 -0.395980 

Disse data er klar til klyngedannelse! Da vi introducerede DBSCAN, nævnte vi minimum antal point og epsilon. Disse to værdier skal vælges, før modellen oprettes. Lad os se, hvordan det gøres.

Valg af min. Prøver og Epsilon

For at vælge det mindste antal point for DBSCAN-klynger er der en tommelfingerregel, som siger, at det skal være lig med eller højere end antallet af dimensioner i dataene plus én, som i:

$$
tekst{min. points} >= tekst{datadimensioner} + 1
$$

Dimensionerne er antallet af kolonner i datarammen, vi bruger 2 kolonner, så min. point skal enten være 2+1, hvilket er 3, eller højere. For dette eksempel, lad os bruge 5 min. point.

$$
tekst{5 (min. point)} >= tekst{2 (datadimensioner)} + ​​1
$$

For nu at vælge værdien for ε er der en metode, hvor a Nærmeste naboer Algoritmen bruges til at finde afstandene til et foruddefineret antal nærmeste punkter for hvert punkt. Dette foruddefinerede antal naboer er min. punkter, vi lige har valgt minus 1. Så i vores tilfælde vil algoritmen finde de 5-1 eller 4 nærmeste punkter for hvert punkt i vores data. det er de k-naboer og vores k svarer til 4.

$$
tekst{k-naboer} = tekst{min. point} – 1
$$

Efter at have fundet naboerne, vil vi ordne deres afstande fra størst til mindste og plotte afstandene på y-aksen og punkterne på x-aksen. Ser vi på plottet, vil vi finde, hvor det ligner bøjningen af ​​en albue og y-aksepunktet, der beskriver, at bøjet albue er den foreslåede ε-værdi.

For at udføre disse trin kan vi importere algoritmen, tilpasse den til dataene, og derefter kan vi udtrække afstande og indekser for hvert punkt med kneighbors() metode:

from sklearn.neighbors import NearestNeighbors
import numpy as np nn = NearestNeighbors(n_neighbors=4) nbrs = nn.fit(scaled_customer_data)
distances, indices = nbrs.kneighbors(scaled_customer_data)

Efter at have fundet afstandene kan vi sortere dem fra største til mindste. Da afstandsarrayets første kolonne er af punktet til sig selv (hvilket betyder, at alle er 0), og den anden kolonne indeholder de mindste afstande, efterfulgt af den tredje kolonne, som har større afstande end den anden, og så videre, kan vi kun vælge værdierne i den anden kolonne og gem dem i distances variabel:

distances = np.sort(distances, axis=0)
distances = distances[:,1] 

Nu hvor vi har vores sorterede mindste afstande, kan vi importere matplotlib, plot afstandene, og tegn en rød linje på, hvor "albuebøjningen" er:

import matplotlib.pyplot as plt plt.figure(figsize=(6,3))
plt.plot(distances)
plt.axhline(y=0.24, color='r', linestyle='--', alpha=0.4) plt.title('Kneighbors distance graph')
plt.xlabel('Data points')
plt.ylabel('Epsilon value')
plt.show();

Dette er resultatet:

Bemærk, at når vi tegner linjen, vil vi finde ud af ε-værdien, i dette tilfælde er den det 0.24.

Vi har endelig vores minimumspoint og ε. Med begge variabler kan vi oprette og køre DBSCAN-modellen.

Oprettelse af en DBSCAN-model

For at skabe modellen kan vi importere den fra Scikit-Learn, oprette den med ε som er det samme som eps argument, og minimumspunkterne, som er mean_samples argument. Vi kan så gemme det i en variabel, lad os kalde det dbs og tilpasse det til de skalerede data:

from sklearn.cluster import DBSCAN dbs = DBSCAN(eps=0.24, min_samples=5)
dbs.fit(scaled_customer_data)

Lige sådan er vores DBSCAN-model blevet oprettet og trænet på dataene! For at udtrække resultaterne får vi adgang til labels_ ejendom. Vi kan også lave en ny labels kolonne i scaled_customer_data dataramme og fyld den med de forudsagte etiketter:

labels = dbs.labels_ scaled_customer_data['labels'] = labels
scaled_customer_data.head()

Dette er det endelige resultat:

 Annual Income (k$) Spending Score (1-100) labels
0 -1.738999 -0.434801 -1
1 -1.738999 1.195704 0
2 -1.700830 -1.715913 -1
3 -1.700830 1.040418 0
4 -1.662660 -0.395980 -1

Bemærk at vi har etiketter med -1 værdier; disse er støjpunkter, dem, der ikke tilhører nogen klynge. For at vide, hvor mange støjpunkter algoritmen fandt, kan vi tælle, hvor mange gange værdien -1 vises i vores etiketliste:

labels_list = list(scaled_customer_data['labels'])
n_noise = labels_list.count(-1)
print("Number of noise points:", n_noise)

Dette udsender:

Number of noise points: 62

Vi ved allerede, at 62 punkter af vores oprindelige data på 200 punkter blev betragtet som støj. Dette er meget støj, hvilket indikerer, at DBSCAN-klyngningen måske ikke betragtede mange punkter som en del af en klynge. Vi vil snart forstå, hvad der skete, når vi plotter dataene.

I starten, da vi observerede dataene, så det ud til at have 5 klynger af punkter. For at vide, hvor mange klynger DBSCAN har dannet, kan vi tælle antallet af etiketter, der ikke er -1. Der er mange måder at skrive den kode på; her har vi skrevet en for loop, som også vil fungere for data, hvor DBSCAN har fundet mange klynger:

total_labels = np.unique(labels) n_labels = 0
for n in total_labels: if n != -1: n_labels += 1
print("Number of clusters:", n_labels)

Dette udsender:

Number of clusters: 6

Vi kan se, at algoritmen forudsagde, at dataene havde 6 klynger med mange støjpunkter. Lad os visualisere det ved at plotte det med søborns scatterplot:

sns.scatterplot(data=scaled_customer_data, x='Annual Income (k$)', y='Spending Score (1-100)', hue='labels', palette='muted').set_title('DBSCAN found clusters');

Dette resulterer i:

Ser vi på plottet, kan vi se, at DBSCAN har fanget de punkter, som var tættere forbundet, og punkter, der kunne betragtes som en del af den samme klynge, var enten støj eller anses for at danne en anden mindre klynge.

Hvis vi fremhæver klyngene, så læg mærke til, hvordan DBSCAN får klynge 1 fuldstændigt, som er klyngen med mindre mellemrum mellem punkterne. Derefter får den delene af klynger 0 og 3, hvor punkterne er tæt sammen, idet mere adskilte punkter betragtes som støj. Den betragter også punkterne i den nederste venstre halvdel som støj og opdeler punkterne i den nederste højre i 3 klynger og fanger igen klynger 4, 2 og 5, hvor punkterne er tættere på hinanden.

Vi kan begynde at komme til den konklusion, at DBSCAN var fantastisk til at fange de tætte områder af klyngerne, men ikke så meget til at identificere det større skema af dataene, de 5 klyngers afgrænsninger. Det ville være interessant at teste flere klyngealgoritmer med vores data. Lad os se, om en metrik vil bekræfte denne hypotese.

Evaluering af algoritmen

For at evaluere DBSCAN vil vi bruge silhuet score som vil tage højde for afstanden mellem punkter i en samme klynge og afstandene mellem klynger.

For det første kan vi importere silhouette_score fra Scikit-Learn, så send det vores kolonner og etiketter:

from sklearn.metrics import silhouette_score s_score = silhouette_score(scaled_customer_data, labels)
print(f"Silhouette coefficient: {s_score:.3f}")

Dette udsender:

Silhouette coefficient: 0.506

Ifølge denne score ser det ud til, at DBSCAN kunne fange cirka 50 % af dataene.

Konklusion

DBSCAN fordele og ulemper

DBSCAN er en meget unik klyngealgoritme eller model.

Hvis vi ser på dens fordele, er den meget god til at opfange tætte områder i data og punkter, der ligger langt fra andre. Det betyder, at dataene ikke behøver at have en bestemt form og kan være omgivet af andre punkter, så længe de også er tæt forbundet.

Det kræver, at vi angiver minimumspunkter og ε, men det er ikke nødvendigt at angive antallet af klynger på forhånd, som for eksempel i K-Means. Det kan også bruges med meget store databaser, da det er designet til højdimensionelle data.

Hvad angår dens ulemper, har vi set, at den ikke kunne fange forskellige tætheder i samme klynge, så den har det svært med store forskelle i tætheder. Det afhænger også af afstandsmetrikken og skaleringen af ​​punkterne. Det betyder, at hvis dataene ikke er godt forstået, med forskelle i skala og med en afstandsmetrik, der ikke giver mening, vil den sandsynligvis ikke forstå det.

DBSCAN-udvidelser

Der er andre algoritmer, som f.eks Hierarkisk DBSCAN (HDBSCAN) , Bestillingspunkter for at identificere klyngestrukturen (OPTICS), som betragtes som udvidelser af DBSCAN.

Både HDBSCAN og OPTICS kan normalt præstere bedre, når der er klynger med varierende tætheder i dataene og er også mindre følsomme over for valget eller indledende min. point og ε-parametre.

• SEO Powered Content & PR Distribution. Bliv forstærket i dag.
• Platoblokkæde. Web3 Metaverse Intelligence. Viden forstærket. Adgang her.
• Kilde: https://stackabuse.com/dbscan-with-scikit-learn-in-python/