DBSCAN

Ezeken a videókon a DBSCAN nem felügyelt klaszterezés működését látjuk.

Láthatjuk, ahogy pontról pontra kialakulnak a különböző, előre nem meghatározott számú klaszterek, illetve külön színnel jelölésre kerülnek a sehova sem tartozó pontok, az úgynevezett outlier-ek (anomáliadetekció).

A kód az első ebben az esetben 300 pontot generál le véletlenszerűen egy 100-szor 100-as kétdimenziós síkon (az egységtávolság az 1) és 7,3-om egységű Epszilon paraméterrel (környezeti sugár) és 4 minimális szomszéddal csoportosítja a pontokat.

A kód a második esetben egy szomorú arcot generál véletlenszerűen egy 500-szor 500-as kétdimenziós síkon (az egységtávolság 1) és 65 egységű Epszilon paraméterrel (környezeti sugár) és 3 minimális szomszéddal csoportosítja a pontokat.

A DBSCAN (Density-Based Spatial Clustering of Applications with Noise) egy sűrűség-alapú klaszterezési algoritmus, amely az adatok klaszterekbe történő csoportosítására szolgál anélkül, hogy előre meg kellene határozni a klaszterek számát. Ez az algoritmus különösen hasznos, ha az adatokban zaj van (outlierek) és az adatok sűrűségi mintázatokat követnek.

Működési elv
A DBSCAN algoritmus az alábbi alapelvekre épít:

Adatpontok sűrűsége: A DBSCAN a környezetét (szomszédos adatpontokat) vizsgálja, és két alapvető paramétert használ:

Eps (ε): A távolság, amely meghatározza, hogy egy adatpont közvetlen szomszédja-e egy másik adatpontnak.
MinPts: Az a minimális számú adatpont, amelynek a szomszédságában egy adatpontnak kell lennie ahhoz, hogy egy klaszter magját képezze.

Három típusú adatpont:

Magpontok: Azok az adatpontok, amelyeknek legalább MinPts szomszédja van egy Eps távolságon belül.
Szomszédos pontok: Azok a pontok, amelyek egy magpont szomszédságában találhatók, de nem magpontok.
Zajpontok (outlierek): Azok a pontok, amelyek nem tartoznak egyetlen klaszterhez sem, mivel minden szomszédjuktól epszilon távolságon kívül esnek.

Klaszterezési folyamat:

A DBSCAN egy tetszőleges adatpontot választ ki, és ha több, mint MinPts szomszéddal rendelkezik epszilon távolságon belül, akkor egy klasztert kezd el kialakítani.
A klaszterek folytatódnak az összes szomszédos pont hozzáadásával.
Azokat az adatpontokat, amelyek nem tartoznak egy klaszterhez, zajpontoknak tekintjük.

Alkalmazási területek
Sűrűség alapú klaszterezés: DBSCAN különösen hasznos olyan esetekben, amikor a klaszterek alakja nem szabályos (pl. gömb alakú), és amikor az adatok között zajpontok vagy outlierek vannak. Nem szükséges előre meghatározni a klaszterek számát.

Főbb alkalmazási területek:

Geográfiai adatelemzés: DBSCAN-t alkalmazhatunk olyan esetekben, mint például a helyadatok (GPS adatok), ahol a térbeli eloszlás alapján kell az adatokat klaszterekbe sorolni (pl. városok, éttermek, üzletek klaszterezése).

Anomáliák detektálása: Zajpontok vagy outlierek azonosítása az adatokban. Ha egy adatpont nem tartozik egyetlen klaszterhez sem, akkor azt zajpontnak tekinthetjük, így alkalmas lehet a rendellenes események vagy hibás adatok detektálására.

Képfeldolgozás: A DBSCAN alkalmazható képeken található objektumok csoportosítására vagy egyes vizuális mintázatok azonosítására.

Hálózati adatbányászat: Internetes vagy közlekedési hálózatokban, például közlekedési adatokban, ahol fontos az egyes útvonalak, csomópontok és azok közötti kapcsolatok sűrűségének elemzése.

Előnyök:

Képes klasztereket találni anélkül, hogy előre meghatároznánk a klaszterek számát.
Jó a zajpontok és az outlierek kezelésére.
Képes kezelni a különböző alakú klasztereket (nem csupán gömböket).

Hátrányok:

Az algoritmus érzékeny a paraméterekre, különösen az Eps és MinPts értékekre.
Nagy, sűrű adatbázisokkal vagy nagyon nagy adatmennyiségekkel lassú lehet.

Példa

Tegyük fel, hogy egy város közlekedési adatain dolgozunk, és szeretnénk megtalálni azokat a területeket, ahol a forgalom sűrűsége magas. A DBSCAN segítségével a forgalmi adatokat klaszterekbe sorolhatjuk, és így azonosíthatjuk a zsúfolt, forgalmas területeket (mint a központi csomópontok), míg a ritkábban használt utak, vagy a zajos adatokat (pl. hibás GPS-koordináták) outlierekként kezelhetjük.

Összességében a DBSCAN egy erőteljes eszköz a sűrűség-alapú klaszterezéshez, különösen akkor, ha nem ismert előre a klaszterek száma, és ha az adatainkban zajpontok vagy outlierek vannak.

import numpy as np

# Távolság számítása két pont között (euklideszi távolság)

def euclidean_distance(point1, point2):

return np.sqrt(np.sum((point1 - point2) ** 2))

# Szomszédok keresése (Eps távolságon belüli pontok)

def region_query(data, point_idx, eps):

neighbors = []

for i in range(len(data)):

if euclidean_distance(data[point_idx], data[i]) <= eps:

neighbors.append(i)

return neighbors

# Klaszter kibővítése

def expand_cluster(data, labels, point_idx, neighbors, cluster_id, eps, min_pts, visited):

labels[point_idx] = cluster_id

i = 0

while i < len(neighbors): neighbor_idx = neighbors[i] if not visited[neighbor_idx]: visited[neighbor_idx] = True new_neighbors = region_query(data, neighbor_idx, eps) if len(new_neighbors) >= min_pts:

neighbors.extend(new_neighbors)

if labels[neighbor_idx] == -1:

labels[neighbor_idx] = cluster_id

i += 1

return labels

# DBSCAN algoritmus

def dbscan(data, eps, min_pts):

labels = np.full(len(data), -1)

visited = np.full(len(data), False)

cluster_id = 0

for i in range(len(data)):

if visited[i]:

continue

visited[i] = True

neighbors = region_query(data, i, eps)

if len(neighbors) < min_pts:

labels[i] = -1 # Zajpont

else:

cluster_id += 1

labels = expand_cluster(data, labels, i, neighbors, cluster_id, eps, min_pts, visited)

return labels

# Pontok generálása

np.random.seed(42)

data = np.random.rand(300, 2) * 100 # 300 pont két dimenzióban, 0 és 100 között

# Paraméterek beállítása

eps = 7.3 # Sugár

min_pts = 4 # Minimális szomszédok száma

# DBSCAN alkalmazása az adatkészletre

labels = dbscan(data, eps, min_pts)