DBSCAN (Yoğunluk Tabanlı Kümeleme (DBSCAN))

#machine-learning #clustering #data-mining #unsupervised-learning

Yoğunluk tabanlı kümeleme algoritması; keyfi şekilli kümeler tespit eder ve aykırı noktaları gürültü olarak etiketler, küme sayısını önceden gerektirmez.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise), 1996 yılında Martin Ester ve ekibi tarafından tanıtılan, yoğunluk tabanlı bir kümeleme algoritmasıdır. K-Means gibi yöntemlerin aksine, küme sayısını önceden belirleme zorunluluğu taşımaz ve keyfi geometrik şekillerdeki kümeleri tespit edebilir. Bunun yanı sıra gürültü noktalarını açıkça etiketleyerek aykırı değer tespitine de doğal destek verir. Algoritma iki temel parametreye dayanır: ε (epsilon), bir noktanın komşuluk yarıçapını tanımlar; minPts ise bir bölgenin çekirdek nokta sayılabilmesi için gereken asgari komşu sayısıdır. DBSCAN her nokta için ε yarıçaplı komşuluk bölgesini inceler. MinPts veya daha fazla komşuya sahip noktalar çekirdek nokta olarak sınıflandırılır ve bir kümenin çekirdeğini oluşturur. Bir çekirdek noktanın ε-komşuluğunda bulunan ancak kendisi çekirdek olmayan noktalar kenar nokta (border point) adını alır. Hiçbir çekirdek noktanın ε-komşuluğunda yer almayan noktalar ise gürültü (noise) olarak etiketlenir ve -1 etiketi atanır. Algoritma, birbirine yoğunluk-bağlantılı tüm noktaları tek bir kümede toplar. Parametre seçimi DBSCAN'ın başarısını doğrudan belirler. ε için yaygın yöntem k-en yakın komşu (kNN) grafiğidir: her noktanın minPts'inci en yakın komşusuna mesafesi grafiğe dökülerek dirsek (elbow) noktası bulunur. minPts için genel kural, boyut sayısının iki katı (2×d) olmakla birlikte veri setinin yoğunluğuna göre ayarlanması önerilir. Büyük veri kümelerinde standart DBSCAN O(n²) zaman karmaşıklığı gösterir. Bu kısıtlamayı aşmak için HDBSCAN (Hierarchical DBSCAN), OPTICS ve Approximated DBSCAN gibi varyantlar geliştirilmiştir. HDBSCAN, sabit ε yerine adaptif yoğunluk eşiği kullanarak değişken yoğunluktaki karmaşık küme yapılarını başarıyla tespit eder ve Python'daki hdbscan kütüphanesiyle kolayca uygulanabilir. DBSCAN başlıca şu alanlarda kullanılır: coğrafi veri analizinde olay noktalarını doğal kümeler halinde gruplama, anomali tespitinde gürültü noktalarını anormallik göstergesi olarak değerlendirme, görüntü bölütlemede piksel uzayında renk ve doku benzerliğine göre bölge oluşturma ve müşteri segmentasyonunda keyfi şekilli davranış gruplarını belirleme. Scikit-learn'ün sklearn.cluster.DBSCAN sınıfı, algoritmayı yalnızca birkaç satır Python kodu ile kullanılabilir hale getirir.

DBSCAN Nasıl Çalışır? Adım Adım Algoritma

DBSCAN, her nokta için ε yarıçaplı bir komşuluk bölgesi tanımlar. MinPts veya daha fazla komşuya sahip noktalar çekirdek nokta olarak sınıflandırılır ve bir kümenin çekirdeğini oluşturur. Bir çekirdek noktanın ε-komşuluğunda bulunan ancak kendisi çekirdek olmayan noktalar kenar nokta (border point) adını alır. Hiçbir çekirdek noktanın ε-komşuluğunda yer almayan noktalar ise gürültü (noise) olarak etiketlenir. Algoritma, birbirine yoğunluk-bağlantılı (density-connected) tüm noktaları tek bir kümede toplar ve bunu tüm veri noktaları işlenene kadar tekrarlar.

K-Means, DBSCAN ve Hiyerarşik Kümeleme Karşılaştırması

  • check_circle K-Means: Küme sayısını (k) önceden gerektirir, yalnızca küresel şekilli kümeler için uygundur, aykırı değerlere karşı duyarlıdır. Büyük verilerde hızlı ve ölçeklenebilir.
  • check_circle DBSCAN: Küme sayısı otomatik belirlenir, keyfi şekilli kümeler tespit edilebilir, gürültü noktaları açıkça etiketlenir. ε ve minPts parametre seçimi deneyim gerektirir.
  • check_circle HDBSCAN: DBSCAN'ın hiyerarşik versiyonu; sabit ε yerine adaptif yoğunluk eşiği kullanır. Değişken yoğunluktaki karmaşık kümeler için önerilir.
  • check_circle Aglomeratif Hiyerarşik Kümeleme: Dendrogram oluşturarak farklı çözünürlüklerde kümeleri görselleştirir. Küçük-orta ölçekli verilerde yorumlanabilirliği yüksek, büyük verilerde yavaş.

Parametre Seçimi: ε ve minPts Nasıl Belirlenir?

DBSCAN'ın başarısı doğru parametre seçimine bağlıdır. ε için yaygın yöntem k-en yakın komşu (kNN) grafiğidir: her noktanın minPts'inci en yakın komşusuna olan uzaklıklar sıralanır ve ani kırılma noktası ε olarak seçilir. minPts için genel kural boyut sayısının iki katı artı birdir (D×2+1); ancak gürültülü verilerde daha yüksek değerler tercih edilmelidir. Yüksek boyutlu verilerde boyutluluk laneti nedeniyle ε'nun anlamlı bir ayrım yapamaması durumu oluşabilir; bu durumda önce PCA ile boyut indirgeme uygulanması önerilir.

Uygulama Alanları

  • check_circle Coğrafi veri analizi: Harita üzerindeki olay noktalarını (trafik kazası, suç, deprem artçısı) doğal kümeler halinde gruplar; şehir planlaması ve güvenlik analizinde kullanılır.
  • check_circle Anomali tespiti: Gürültü olarak etiketlenen noktalar sistem anormalisi, kredi kartı dolandırıcılığı veya ağ saldırısı göstergesi olabilir.
  • check_circle Görüntü bölütleme: Piksel uzayında renk ve doku benzerliklerine göre bölgeler oluşturur; tıbbi görüntülemede tümör sınırlarını belirlemeye yardımcı olur.
  • check_circle Müşteri segmentasyonu: Satın alma davranışı verilerinde keyfi şekilli müşteri gruplarını tespit eder; zorla k adet küme oluşturulmasını gerektirmez.

Python'da DBSCAN Kullanımı

scikit-learn'de DBSCAN uygulamak birkaç satır kodla tamamlanır: `from sklearn.cluster import DBSCAN; db = DBSCAN(eps=0.5, min_samples=5).fit(X)`. Etiketler `db.labels_` ile alınır; -1 değeri gürültü noktalarını gösterir. HDBSCAN için `hdbscan` paketi veya scikit-learn 1.3+'daki yeni implementasyon kullanılabilir. Büyük veri setlerinde yaklaşık komşu araması (approximate nearest neighbor) ile hızlandırılmış DBSCAN varyantları tercih edilir: Ball Tree ve KD-Tree indeks yapıları performansı önemli ölçüde artırır.

Sık Sorulan Sorular

  • check_circle DBSCAN küme sayısını nasıl belirler?: DBSCAN küme sayısını önceden gerektirmez; yoğunluk-bağlantılı nokta gruplarını otomatik olarak tespit eder. Ortaya çıkan küme sayısı tamamen veri dağılımına bağlıdır.
  • check_circle ε parametresini nasıl seçmeliyim?: Her noktanın minPts'inci en yakın komşusuna mesafesini grafik üzerinde çizin ve dirsek (elbow) noktasını ε olarak seçin. Bu kNN grafiği yöntemi pratik ve yaygın kullanılan bir yaklaşımdır.
  • check_circle DBSCAN yüksek boyutlu verilerde işe yarar mı?: Boyut laneti nedeniyle yüksek boyutlarda Öklid mesafesi anlamını yitirir ve tüm noktalar birbirine benzer uzaklıkta görünür. Bu durumda boyut indirgeme (PCA, UMAP) ön adımı olarak önerilir.
  • check_circle DBSCAN ile HDBSCAN arasındaki fark nedir?: HDBSCAN, sabit ε parametresini kaldırarak adaptif yoğunluk eşiği kullanır. Değişken yoğunluktaki küme yapılarını daha iyi tespit eder ve parametre seçimini kolaylaştırır.
  • check_circle Python'da DBSCAN nasıl kullanılır?: sklearn.cluster.DBSCAN sınıfıyla kullanılır: DBSCAN(eps=0.5, min_samples=5).fit(X). Etiketler labels_ özniteliğinde tutulur; -1 gürültü noktalarını gösterir.