DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN (gürültülü uygulamaların yoğunluk tabanlı uzamsal kümelenmesi), birbirine yakın noktaları kümeler halinde gruplayan ve seyrek bölgelerdeki noktaları gürültü olarak etiketleyen bir denetimsiz öğrenme algoritmasıdır. Martin Ester, Hans-Peter Kriegel, Jörg Sander ve Xiaowei Xu, algoritmayı 1996'da KDD konferansında tanıttı. Önceden belirlenmiş küme sayısına ihtiyaç duymaz, halkalar, hilaller veya kıvrımlı yollar gibi her biçimdeki kümeleri bulur ve gürültü etiketi basit bir anomali tespiti biçimi olarak da işlev görür. Algoritmanın tamamı iki parametreyle kontrol edilir: komşuluk yarıçapı ve bir komşuluğun yoğun sayılması için gereken nokta sayısı.

Çekirdek Noktalar, Sınır Noktaları ve Gürültü#

DBSCAN her noktanın eps mesafesi içindeki noktalar kümesinden oluşan komşuluğunu inceler ve üyelerini sayar:

• Çekirdek nokta: scikit-learn uygulamasında kendisi de sayılmak üzere, komşuluğunda en az min_samples nokta bulunur. Çekirdek noktalar kümenin yoğun iç bölgesini oluşturur.
• Sınır noktası: Çekirdek nokta olmak için yeterli komşusu yoktur, ancak bir çekirdek noktanın eps mesafesinde yer alır. Sınır noktaları kümenin kenarlarını oluşturur.
• Gürültü noktası: İki türden de değildir; dolayısıyla hiçbir kümeye ait olmaz ve -1 etiketini alır.

Bir küme, ziyaret edilmemiş herhangi bir çekirdek noktadan büyür. DBSCAN bu noktanın komşuluğundaki tüm noktaları ekler, ardından yeni eklenen her çekirdek noktadan işlemi yineler ve başka noktalara erişilemeyene kadar devam eder; böylece örtüşen yoğun komşuluklardan oluşan bir zincir, nasıl kıvrılırsa kıvrılsın tek bir kümeye dönüşür. Sınır noktaları kümeyi genişletmeden kümeye katılır. Belirli bir girdi sırası için sonuç deterministiktir; ancak iki kümenin erişim alanındaki bir sınır noktası, kendisine ilk ulaşan kümeye katılır. Bu nedenle verileri karıştırmak sınır noktalarının kümeler arasında yer değiştirmesine yol açabilir.

eps ve min_samples Seçimi#

eps yarıçapı en önemli parametredir ve verilerin ölçeğine bağlıdır; bu nedenle özellikler genellikle önce standartlaştırılır. Yarıçap çok küçük olduğunda noktaların çoğu gürültü olarak kalır, çok büyük olduğunda ise komşu kümeler birleşir. Yaygın sezgisel yöntem, her noktanın k'inci en yakın komşusuna olan mesafesini sıralamaktır; burada k, min_samples değerine eşittir. Eğrinin dik biçimde yükselmeye başladığı dirsek noktasında eps seçilir. Daha büyük min_samples değerleri, kümelemenin gürültüye karşı daha toleranslı olmasını sağlar ve büyük ya da gürültülü veri kümelerinde yaygındır. Görüntü gömüleri gibi yüksek boyutlu uzaylarda noktalar arasındaki mesafeler birbirine benzer hale gelir; bu nedenle uygulayıcılar DBSCAN'i çalıştırmadan önce genellikle temel bileşen analizi (PCA) gibi boyut indirgeme yöntemlerini uygular.

DBSCAN, K-Means ve HDBSCAN Karşılaştırması#

K-means kümeleme, küme sayısının önceden belirlenmesini gerektirir, her noktayı en yakın ağırlık merkezine atar ve bu nedenle kompakt, yuvarlak kümeleri tercih eder; aykırı değerleri de bir kümeye dahil eder. DBSCAN, küme sayısını yoğunluğa göre bulur ve aykırı değerleri dışarıda bırakır. Zayıf yanı, tek bir genel eps kullanmasıdır: Kümelerin yoğunlukları çok farklı olduğunda, seyrek kümeleri gürültüden ve yoğun kümeleri birbirinden ayıracak tek bir yarıçap yoktur. HDBSCAN, DBSCAN'i eps değerlerinin tümünde çalıştırıp en kararlı kümeleri tutarak bu sorunu çözer; her iki algoritma da ilgili OPTICS algoritmasının yanı sıra scikit-learn kümeleme modülünde bulunur.

Bu örnek, rastgele eklenmiş 20 aykırı değerle iç içe geçen iki hilali kümelendirir ve her sonucu gerçek gruplarla düzeltilmiş Rand indeksi üzerinden puanlar; 1.0 kusursuz eşleşmedir:

import numpy as np
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import adjusted_rand_score

# Two interleaving crescents plus 20 scattered outliers (true label -1)
X, y = make_moons(n_samples=300, noise=0.05, random_state=0)
rng = np.random.default_rng(0)
X = np.vstack([X, rng.uniform(-1.5, 2.5, size=(20, 2))])
y = np.concatenate([y, np.full(20, -1)])

# DBSCAN infers clusters from density; k-means is told there are 2
db_labels = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)
km_labels = KMeans(n_clusters=2, random_state=0).fit_predict(X)

print(f"DBSCAN: {db_labels.max() + 1} clusters, {(db_labels == -1).sum()} noise points")
print(f"ARI: DBSCAN {adjusted_rand_score(y, db_labels):.2f}, k-means {adjusted_rand_score(y, km_labels):.2f}")

Betik, DBSCAN için 2 küme ve 15 gürültü noktası; düzeltilmiş Rand indeksi içinse DBSCAN'de 0.97, k-means'te 0.20 yazdırır. DBSCAN iki hilalin de şeklini izler ve bunlardan uzakta kalan aykırı değerleri ayırır; k-means ise doğru küme sayısı verilmiş olsa bile hilalleri düz bir sınırla keser.

Gerçek Dünya Uygulamaları#

• LiDAR algısı: Otonom araç ve robotik iş akışlarında LiDAR taramasından zemin noktaları çıkarılır, ardından kalan 3B noktalar ayrı engeller halinde kümelenir. Nesne sayısı bilinmediğinden yoğunluk tabanlı kümeleme yaygın bir tercihtir.
• Algılama son işleme: result.boxes.xywh olarak erişilebilen YOLO26 algılamalarının kutu merkezleri, kalabalıktaki insan gruplarını veya üretim hattında yinelenen kusur konumlarını bulmak için DBSCAN ile kümelenebilir; tek başına kalan algılamalar gürültü olarak dışarıda bırakılır.
• Dolandırıcılık ve sensör izleme: -1 olarak etiketlenen işlemler veya ölçümler, normal davranışın yoğun kümelerinden çok uzakta yer alır ve incelenmek üzere aday hâline gelir.
• Jeo-uzamsal analiz: Teslimat ve araç çağırma şirketleri, sık durulan yerleri ve yolcu alma noktalarının yoğunlaştığı bölgeleri bulmak için GPS noktalarını kümelendirir. Scikit-learn'ın DBSCAN'i, enlem ve boylamın radyan cinsinden verildiği metric="haversine" değerini kabul eder; bu durumda eps, birim küre üzerindeki açıdır ve 100 metrelik yarıçap eps = 0.1 / 6371 olur; hesaplamada Dünya'nın ortalama yarıçapı olan 6.371 km kullanılır.