MerQuR+İstatistik Sözlüğü

İstatistik Sözlüğü → DBSCAN / HDBSCAN

DBSCAN / HDBSCANanaliz

Noktaların yoğun biçimde toplandığı bölgeleri küme, seyrek bölgelerde kalan noktaları gürültü (aykırı) olarak ayıran ve küme sayısının önceden verilmesini gerektirmeyen yoğunluğa dayalı kümeleme yöntemi.

Kavram

K-ortalamalar gibi yöntemler kümelerin yuvarlak ve benzer büyüklükte olduğunu örtük olarak varsayar ve her noktayı mutlaka bir kümeye atar. Oysa gerçek verilerde kümeler hilal, şerit ya da düzensiz biçimli olabilir ve bazı noktalar hiçbir gruba ait değildir. DBSCAN kümeyi 'noktaların sık toplandığı, seyrek bölgelerle birbirinden ayrılan alan' olarak tanımlar; böylece biçimi ne olursa olsun yoğun bölgeleri bulur ve yalnız kalan noktaları gürültü olarak ayırır.

Yöntem iki ayara dayanır: komşuluk yarıçapı ε ve en küçük örnek sayısı (minPts). Bir noktanın ε yarıçapında (kendisi dahil) en az minPts nokta varsa o nokta çekirdek noktadır. Birbirinin komşuluğunda olan çekirdek noktalar zincirleme bağlanarak bir küme oluşturur; bir çekirdeğin komşuluğunda olan ama kendisi çekirdek olmayan noktalar sınır noktası olarak kümeye katılır; hiçbir çekirdeğin komşuluğuna girmeyen noktalar gürültü sayılır. HDBSCAN, tek bir ε seçmek yerine tüm yoğunluk düzeylerini tarayan bir hiyerarşi kurar ve en kararlı kümeleri seçer; bu nedenle farklı yoğunluktaki kümeleri birlikte bulabilir.

DBSCAN'ın en büyük zorluğu ε seçimidir: küçük ε pek çok noktayı gürültü yapar ve kümeleri parçalar, büyük ε ayrı kümeleri birleştirir. k-uzaklık (dirsek) grafiği uygun ε için yol gösterir. Tek bir ε kullanıldığı için yoğunluğu çok farklı kümeler aynı anda iyi ayrılamaz; bu durumda HDBSCAN tercih edilir. Uzaklıklar ölçeğe duyarlıdır, değişkenler genellikle standartlaştırılmalıdır; değişken sayısı arttıkça yoğunluk kavramı zayıflar. Gürültü olarak işaretlenen noktalar silinecek hatalar değil, ayrıca incelenmesi gereken sıra dışı gözlemlerdir.

Ne zaman kullanılır?

  • Kümelerin biçimi düzensiz olduğunda, küme sayısı bilinmediğinde ve aykırı noktaların ayrıca belirlenmesi istendiğinde; özellikle konumsal verilerde (kaza ya da deprem noktaları, nokta bulutları, GPS kayıtları).
  • Kümelerin yoğunlukları belirgin biçimde farklıysa ya da uygun ε değeri kestirilemiyorsa DBSCAN yerine HDBSCAN kullanılır.
  • Kümeler kabaca yuvarlak ve benzer büyüklükteyse ve her gözlemin bir gruba atanması gerekiyorsa K-ortalamalar; iç içe yapı görülmek isteniyorsa hiyerarşik kümeleme daha uygundur.

Gündelik bir örnek

Bir belediyenin trafik birimi, son üç yılda yaşanan 600 kazanın harita koordinatlarını inceliyor. Kazaların bir kısmı belirli kavşaklarda ve bir bulvar boyunca sıkışık biçimde toplanmış, diğerleri kent geneline dağınık. DBSCAN, örneğin 150 metre içinde en az 8 kazanın bulunduğu yerleri 'kara nokta' kümesi olarak işaretler; bulvar boyunca uzanan kaza şeridini de yuvarlak olmamasına karşın tek bir küme olarak yakalar. Tek başına kalan kazalar gürültü sayılır ve belediye düzenleme önceliğini kümelere verir.

MerQur'da parametreler

ε (eps; 0.01 = otomatik)

Kavram: ε, bir noktanın 'komşuluğu' sayılan yarıçaptır; yoğunluk bu yarıçap içindeki nokta sayısıyla ölçülür. Küçük ε yalnız çok sık bölgeleri küme sayar, büyük ε seyrek bölgeleri de kümelere katar ve ayrı kümeleri birleştirebilir.

Gündelik örnek: ε = 50 metre seçilirse yalnız aynı kavşağın köşelerinde üst üste yaşanan kazalar küme oluşturur ve birçok kaza gürültü sayılır. ε = 1 kilometre seçilirse komşu mahallelerdeki kara noktalar tek bir dev kümede birleşir.

Ne işe yarar: Komşuluk yarıçapı; ε içinde en az "en küçük örnek" nokta (kendisi dahil) bulunan nokta çekirdektir. Otomatik ε, k-uzaklıkların (k = en küçük örnek) %90 yüzdeliğidir.

Sonuca etkisi: Küçük ε çok gürültü ve çok sayıda küçük küme, büyük ε az gürültü ve birleşen kümeler verir; tüm sayılar değişir.

Doğrulama verisinde: (iris z, en küçük örnek 5): ε 0.3: 3 küme ve 120 gürültü; 0.5: 2 ve 34; 1.0: 2 ve 3; otomatik ε = 0.7565.

→ ε komşuluğu ve en az nokta sayısı (DBSCAN)

Min. örnek (minPts)

Kavram: Bir noktanın çekirdek nokta sayılması için ε komşuluğunda (kendisi dahil) bulunması gereken en az nokta sayısıdır; yoğunluğun eşiğini belirler. Büyük değer daha az çekirdek nokta ve daha çok gürültü, küçük değer gürültüye duyarlı küçük kümeler verir.

Gündelik örnek: minPts = 3 ise üç kazanın yaşandığı her köşe bir kara nokta adayı olur ve tesadüfi yakınlıklar da küme sayılabilir. minPts = 10 istenirse yalnız gerçekten tekrarlayan kaza yerleri küme olarak kalır.

Ne işe yarar: Bir noktanın çekirdek sayılması için ε komşuluğunda gereken en az nokta sayısı (nokta dahil).

Sonuca etkisi: Büyük değer çekirdek nokta sayısını azaltır, gürültüyü artırır; küme sayısı değişir.

Doğrulama verisinde: (iris z, ε 0.5): 2: 9 küme ve 13 gürültü; 3: 7 ve 17; 5: 2 ve 34; 10: 3 ve 89. En küçük örnek 2, tek bağlantılı hiyerarşik kümelemenin ε yüksekliğinde kesimine denktir.

→ ε komşuluğu ve en az nokta sayısı (DBSCAN)

Eksik Veri

Kavram: Eksik ölçümü olan gözlemlerin analizden çıkarılmasını ya da eksik değerin ortalama, medyan veya en benzer gözlemlerden tahminle doldurulmasını sağlar. Doldurulan değerler noktaları yapay olarak 'ortalamaya' yaklaştırabileceğinden yoğunluk yapısını etkileyebilir.

Gündelik örnek: Bazı kaza kayıtlarında koordinatlardan biri eksikse, bu kayıtları silmek en güvenli yoldur; eksik koordinatı kent ortalamasıyla doldurmak kazaları haritada kent merkezine yığar ve sahte bir küme yaratabilir.

Ne işe yarar: Eksik değerli satırları atar ya da ham ölçekte ortalama, medyan veya 5 en yakın komşuyla doldurur.

Sonuca etkisi: n ve dolayısıyla kümeler ve gürültü sayısı değişir.

Doğrulama verisinde: (airquality, z, ε = 1.0): sil: 1 küme ve 12 gürültü (n = 111); ortalama: 1 ve 24; medyan: 1 ve 20; KNN: 2 ve 9 (n = 153). ε = 0.5'te tüm noktalar gürültüdür; bu durumda silhouette tanımsızdır ve "-" gösterilir.

→ Basit atama (ortalama, medyan, kNN ile doldurma)

Uzaklık metriği (Öklid / Manhattan / Chebyshev / Haversine (enlem, boylam; ε km))

Kavram: Noktalar arasındaki uzaklığın nasıl ölçüleceğidir: Öklid düz çizgi, Manhattan eksenler boyunca toplam fark, Chebyshev en büyük tek farktır. Haversine, enlem ve boylamdan yeryüzü üzerindeki büyük daire uzaklığını kilometre olarak verir; coğrafi koordinatlarla çalışırken derece cinsinden düz uzaklık yanıltıcı olduğu için kullanılır.

Gündelik örnek: Kazaların enlem ve boylamı derece olarak kayıtlıysa bir derecelik boylam farkı ekvatorda ve kuzey enlemlerinde farklı mesafelere karşılık gelir. Haversine ile ε doğrudan '0,15 km' olarak verilir ve kümeler gerçek mesafeye göre kurulur.

Ne işe yarar: Noktalar arası uzaklık; Haversine enlem ve boylamdan büyük daire uzaklığını km olarak verir (ε km'dir).

Sonuca etkisi: Komşuluklar ve dolayısıyla kümeler ve gürültü değişir.

Doğrulama verisinde: iris z Manhattan 4 küme ve 110 gürültü; Chebyshev 2 ve 7; quakes haversine (km, ham): ε 50: 22 ve 163; otomatik ε = 71.2503 km: 9 ve 57; ε 100 ve en küçük örnek 10: 5 ve 48. Haversine büyük daire formülüyle, Dünya yarıçapı 6371.0088 km alınarak hesaplanır.

→ Uzaklık ölçüsü (Öklid, Manhattan, Gower, büyük daire)

z-standartlaştır

Kavram: Değişkenleri ortalaması 0, standart sapması 1 olacak biçimde dönüştürür. Değişkenler farklı birimlerdeyse büyük birimli değişken komşulukları belirler; standartlaştırma bunu önler, ama uygun ε değeri de artık standart sapma birimlerinde düşünülmelidir.

Gündelik örnek: Kazalar konumun yanında saat (0-24) ve araç hızı (0-150 km/sa) ile de kümelenecekse hız, saate göre çok daha büyük sayılar aldığı için komşulukları tek başına belirler. Standartlaştırmadan sonra üç değişken de benzer ağırlık taşır.

Ne işe yarar: Değişkenleri z-puanına çevirir (n-1 paydalı).

Sonuca etkisi: Ölçekleri farklı değişkenlerde komşuluklar değişir; uygun ε değeri dönüşüme göre değişir.

Doğrulama verisinde: Kapalıyken iris ε 0.5: 2 küme ve 17 gürültü; ε 0.7: 2 ve 3; otomatik ε = 0.6164: 2 ve 9; ruspini ε 15: 4 ve 3. Açıkken z, n-1 paydalı standart sapmayla hesaplanır.

→ z-puanı (standartlaştırma)

Grafik (Küme saçılımı / k-uzaklık (dirsek) grafiği) ve Küme üyeliğini kaydet

Kavram: Küme saçılımı kümeleri ve gürültü noktalarını renklerle gösterir. k-uzaklık grafiği, her noktanın k'ıncı en yakın komşusuna uzaklığını küçükten büyüğe sıralar; eğrinin aniden yükseldiği 'dirsek' noktası uygun ε için iyi bir adaydır. Kaydetme seçeneği küme numarasını (gürültü dahil) veri setine yazar.

Gündelik örnek: k-uzaklık grafiğinde kazaların çoğu 8'inci en yakın komşusuna 100-150 metre uzaklıktayken eğri 200 metreden sonra hızla yükseliyorsa ε için 150-200 metre makul bir seçimdir. Kaydedilen küme sütunuyla her kazanın hangi kara noktaya ait olduğu tabloda görülür.

Ne işe yarar: Küme saçılımı ya da k-uzaklık (dirsek) grafiği; küme numarasının veri setine yazılması.

Sonuca etkisi: Yalnız grafik ya da veri setine sütun ekler; sayısal sonuçlar değişmez.

→ Saçılım (dağılım) grafiği

Algoritma (DBSCAN / HDBSCAN)

Kavram: DBSCAN tek bir yoğunluk eşiğiyle (ε) çalışır; HDBSCAN ise tüm olası ε değerleri boyunca kümelerin nasıl doğup birleştiğini izleyen bir hiyerarşi kurar ve en uzun süre varlığını koruyan (en kararlı) kümeleri seçer. Böylece hem sık hem seyrek kümeleri aynı anda bulabilir ve ε seçme sorununu ortadan kaldırır.

Gündelik örnek: Kent merkezindeki kavşaklarda kazalar çok sık, çevre yolundaki tehlikeli virajda ise daha seyrek ama yine de belirgin biçimde toplanmışsa tek bir ε ya merkezi birleştirir ya da virajı kaçırır. HDBSCAN her iki kara noktayı kendi yoğunluk düzeyinde ayrı ayrı yakalayabilir.

Ne işe yarar: HDBSCAN ε gerektirmez; en küçük örnek hem çekirdek uzaklığı hem en küçük küme boyutudur.

Sonuca etkisi: HDBSCAN'de ε kullanılmaz; kümeler yoğunluk hiyerarşisinden seçilir ve küme ve gürültü sayıları değişir.

Doğrulama verisinde: iris z: 2 küme ve 2 gürültü. moons (ham, minPts 5): 3 küme, 0 gürültü, 25/25/50. DS3 (ham, minPts 25): 6 küme ve 813 gürültü.

Gerçek veride örnek

Veri: Fisher 1936 iris, R datasets (n = 150)

Değişkenler: özellikler Sepal.Length, Sepal.Width, Petal.Length, Petal.Width (çanak ve taç yaprak ölçüleri)

  • Soru: iris çiçeklerinin dört ölçümü, yoğunluk temelinde kaç doğal kümeye ayrılıyor ve hangi gözlemler hiçbir kümeye ait değil (gürültü)?
  • Ayar: Değişkenler z-puanına çevrildi; komşuluk yarıçapı ε = 0.5, en küçük örnek 5 (nokta dahil). k-uzaklık yüzdelikleri (%50 = 0.4601, %90 = 0.7565) ε = 0.5'in dağılımın ortalarında, oldukça dar bir seçim olduğunu gösterir.
  • Sonuç: 2 küme bulundu (45 ve 71 nokta); 34 nokta (%22.7) gürültü sayıldı. Noktaların 93'ü çekirdek, 23'ü sınır noktasıdır.
  • Küme kalitesi: Gürültü dışındaki noktalarda ortalama silhouette 0.6559; kümeler iyi ayrışmıştır.
  • Betimsel: Birinci küme setosa türüne karşılık gelir; versicolor ve virginica birbirine çok yakın olduğundan tek kümede birleşir. Gürültünün çoğu bu iki türün seyrek uç gözlemleridir.
  • Sınırlılık: Sonuç ε'a çok duyarlıdır (ε = 0.3'te 3 küme ve 120 gürültü, ε = 1.0'da 2 küme ve 3 gürültü); ε k-uzaklık grafiğinin dirseğinden seçilmelidir.
  • APA: DBSCAN (ε = 0.5, minPts = 5, z-puanı) iki küme (n = 45 ve 71) ve 34 gürültü noktası verdi; ortalama silhouette = .66.

İlgili kavramlar

Saçılım (dağılım) grafiğiε komşuluğu ve en az nokta sayısı (DBSCAN)z-puanı (standartlaştırma)Basit atama (ortalama, medyan, kNN ile doldurma)Uzaklık ölçüsü (Öklid, Manhattan, Gower, büyük daire)Dirsek yöntemi ve k-uzaklık grafiğiAykırı değerKüme sayısının seçimi

Örneklerdeki sayılar MerQur'un bağımsız, kamuya açık doğrulama verileri üzerindeki çıktılarıdır; ayrıntılar için MerQur Teknik Not'a bakınız.