MerQuR+İstatistik Sözlüğü

İstatistik Sözlüğü → DBSCAN Mekânsal Kümeleme

DBSCAN Mekânsal Kümelemeanaliz

Konum noktalarını yoğunluğa göre kümelere ayıran, yeterince kalabalık bölgeleri küme, seyrek bölgelerde kalan noktaları ise gürültü olarak işaretleyen ve küme sayısının önceden verilmesini gerektirmeyen kümeleme yöntemi.

Kavram

Haritadaki noktalar çoğu zaman düzensiz biçimli, farklı büyüklükte yoğun bölgeler oluşturur ve arada dağınık tek tük noktalar bulunur. K-ortalamalar gibi yöntemler küme sayısının önceden bilinmesini ister, kümeleri yuvarlak varsayar ve her noktayı bir kümeye atamak zorundadır. DBSCAN ise kümeyi 'birbirine yeterince yakın noktaların kesintisiz zinciri' olarak tanımlar; bu sayede uzun, kıvrımlı ya da düzensiz kümeleri bulabilir ve hiçbir kümeye ait olmayan noktaları gürültü olarak ayırır.

Yöntem iki parametreyle çalışır: yarıçap (eps) ve en az nokta sayısı (minPts). Bir noktanın eps yarıçaplı çevresinde en az minPts nokta varsa o nokta bir çekirdek noktadır. Birbirinin çevresinde kalan çekirdek noktalar aynı kümeye bağlanır; bir çekirdeğin çevresinde olup kendisi çekirdek olmayan noktalar sınır noktası olarak kümeye katılır, kalanlar gürültüdür. Uzaklıklar enlem-boylam verisinde büyük daire (haversine) uzaklığıyla ölçülür. HDBSCAN eps'i hiç istemeden farklı yoğunluklu kümeleri bulur; OPTICS ise noktaları erişilebilirlik grafiğinde sıralayarak farklı eps değerlerindeki küme yapısını tek bakışta gösterir.

Sonuçlar eps ve minPts seçimine çok duyarlıdır: küçük eps çok sayıda küçük küme ve bol gürültü, büyük eps birkaç büyük küme verir. k-uzaklık grafiğinin dirsek noktası iyi bir başlangıç değeridir, ama bulunan kümeler farklı değerlerle denetlenmelidir. DBSCAN tek bir yoğunluk eşiği kullandığından yoğunlukları çok farklı kümeleri aynı anda yakalamakta zorlanır. Yöntem kümelerin istatistiksel anlamlılığını sınamaz; betimsel bir gruplamadır.

Ne zaman kullanılır?

  • Olay, ziyaretçi, çağrı ya da gözlem noktalarını küme sayısını bilmeden yoğun bölgelere ayırmak ve dağınık noktaları gürültü olarak ayıklamak için.
  • Kümelerin yoğunlukları birbirinden çok farklıysa HDBSCAN; farklı yarıçaplardaki küme yapısı birlikte incelenecekse OPTICS kullanılır.
  • Noktaları kümelere atamak yerine yalnızca yoğunluk yüzeyi görmek yeterliyse KDE; bir değerin anlamlı yüksek ya da düşük kümeleri aranıyorsa Getis-Ord Gi* tercih edilir.

Gündelik bir örnek

Bir taksi şirketi, bir hafta içinde gelen 5.000 çağrının konumlarını inceliyor ve boş taksilerin nerelerde bekletileceğine karar vermek istiyor. DBSCAN'e eps = 150 metre ve en az 20 çağrı verildiğinde, örneğin otogar, hastane, havalimanı girişi ve bir alışveriş merkezi çevresinde dört yoğun küme bulur; sahil boyunca uzanan bir eğlence şeridi de kıvrımlı biçimine rağmen tek bir küme olarak çıkar. Kentin dört bir yanına dağılmış tek tük çağrılar ise gürültü olarak işaretlenir; şirket bekleme noktalarını kümelerin merkezlerine yerleştirebilir.

MerQur'da parametreler

Sınıflandır / Yöntem

Kavram: Sınıflandır, noktaları analizden önce kategorik bir sütuna göre renklendiren bir veri keşfi adımıdır; Yöntem harita sekmesinde çalıştırılacak mekânsal analizi seçer. DBSCAN, noktaları yoğunluklarına göre kümelere ayırır.

Gündelik örnek: Çağrılar 'gündüz' ve 'gece' diye renklendirilirse gece çağrılarının eğlence şeridinde toplandığı kümeleme yapılmadan önce görülebilir. 'Çağrılar hangi yoğun bölgelere ayrılıyor?' sorusu için DBSCAN seçilir.

Ne işe yarar: Sınıflandır noktaları kategoriye göre renklendirir (veri keşfi); Yöntem harita yöntemini seçer.

Sonuca etkisi: Sayısal çıktıyı değiştirmez.

Yarıçap (eps)

Kavram: eps, iki noktanın komşu sayılacağı en büyük uzaklıktır ve 'yoğun' sözcüğünün mekânsal ölçeğini tanımlar. k-uzaklık grafiği her noktanın k'inci en yakın komşusuna uzaklığını sıralar; eğrinin birden dikleştiği dirsek, kümelerin içi ile gürültü arasındaki doğal sınırı gösterdiği için iyi bir başlangıç değeridir.

Gündelik örnek: eps = 150 metre, bir taksinin birkaç dakikada yürünerek ulaşılabilecek mesafede bekleyebileceği bir ölçektir. eps 20 metre seçilirse otogar bile dağınık küçük parçalara bölünür; 2 km seçilirse kent merkezindeki bütün çağrılar tek bir dev küme olur.

Ne işe yarar: İki noktanın komşu sayılacağı en büyük büyük-daire uzaklığını (m) belirler. Form açılırken k-uzaklık (k = 4) diz noktası önerisi yazılır; olay ölçeğine uygun fiziksel mesafe veya k-uzaklık grafiğindeki dirsek seçilir. HDBSCAN'da gerekmez.

Sonuca etkisi: Küme sayısını, gürültü sayısını ve küme birleşimlerini belirler.

Doğrulama verisinde: quakes'te (en az 5) öneri 77 888.297 m için 8 küme ve 41 gürültü; 20 km için 31 küme ve 582 gürültü; 50 km için 22 ve 163; 100 km için 5 ve 27; 1 m için tüm noktalar gürültü.

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

Min. nokta

Kavram: Bir noktanın çekirdek nokta sayılması için eps çevresinde (kendisi dahil) bulunması gereken en az nokta sayısıdır. Büyük değerler yalnızca gerçekten kalabalık bölgeleri küme sayar ve daha çok noktayı gürültüye atar; küçük değerler birkaç tesadüfi yakın noktayı da küme yapabilir.

Gündelik örnek: En az 20 çağrı istendiğinde bir hafta boyunca yalnızca birkaç çağrının geldiği bir apartman önü küme sayılmaz. En az 3 seçilseydi kentin her yanında anlamı belirsiz onlarca küçük küme oluşurdu.

Ne işe yarar: Çekirdek nokta için eps içinde gereken nokta sayısını (kendisi dahil) belirler. Değişince öneri etiketi güncellenir; eps alanı "Oneriyi uygula"ya basılmadan değişmez.

Sonuca etkisi: Büyüdükçe küme sayısı azalır, gürültü artar.

Doğrulama verisinde: 50 km'de 2 için 46 küme ve 52 gürültü; 5 için 22 ve 163; 10 için 12 ve 364.

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

Algoritma (DBSCAN, HDBSCAN, OPTICS)

Kavram: DBSCAN tek bir sabit yarıçapla çalışır. HDBSCAN farklı yarıçaplardaki kümelerin hiyerarşisini kurar ve en kararlı kümeleri seçer; bu sayede eps gerektirmez ve yoğunluğu farklı kümeleri birlikte bulur. OPTICS noktaları erişilebilirlik uzaklığına göre sıralar; bu grafiğin belirli bir eps düzeyinde kesilmesi DBSCAN'e benzer kümeler verir.

Gündelik örnek: Havalimanı çağrıları çok yoğun, bir semt pazarının çevresi ise daha seyrek ama yine de belirgin bir küme oluşturuyorsa tek bir eps ikisini birden yakalamakta zorlanır. HDBSCAN her ikisini de kendi yoğunluğunda küme olarak bulabilir.

Ne işe yarar: DBSCAN sabit eps kullanır. HDBSCAN eps gerektirmez, farklı yoğunluklu kümeleri bulur (minPts = en az örnek). OPTICS erişilebilirlik grafiği üretir; kümeler grafiğin eps'te kesilmesiyle elde edilir.

Sonuca etkisi: Küme yapısını belirgin biçimde değiştirir.

Doğrulama verisinde: HDBSCAN en az 10 için 17 küme ve 326 gürültü; en az 5 için 37 ve 263. OPTICS 50 km'de 22 küme ve 180 gürültü.

Tanı ([Parametreler] onay kutusu)

Kavram: Tanı, noktaların çekirdek, sınır ve gürültü olarak dağılımını ve silüet değerini verir. Silüet, her noktanın kendi kümesine öteki kümelerden ne kadar daha yakın olduğunu −1 ile 1 arasında özetler; 1'e yakın değerler iyi ayrışmış kümeleri gösterir.

Gündelik örnek: Çağrıların büyük kısmı çekirdek noktaysa kümeler sağlam ve kalabalıktır; sınır noktası çoksa kümelerin kenarları dağınıktır. Silüet 0,1 gibi düşük çıkarsa bazı kümeler birbirine çok yakın demektir ve eps küçültülerek ayrıştırılabilir.

Ne işe yarar: Çekirdek/sınır/gürültü dökümünü ve gürültü dışı silüeti (-1..1; en az 2 küme gerekir) verir.

Sonuca etkisi: Kümeleme sonucunu değiştirmez, ek çıktı üretir.

Doğrulama verisinde: 50 km'de çekirdek 746, sınır 91, silüet 0.1493; Boston 2000 m ve en az 10 için 320, 68 ve 0.1658.

→ Siluet katsayısı

Küme tablosu (sonuç penceresi, otomatik)

Kavram: Küme tablosu her kümenin nokta sayısını, merkezini ve noktalarını çevreleyen en küçük dışbükey çokgenin (dışbükey zarf) alanını verir. Bu bilgiler kümelerin büyüklüğünü ve yayılımını karşılaştırmayı sağlar.

Gündelik örnek: Tablo, otogar kümesinin 900 çağrıyla en kalabalık, eğlence şeridinin ise en geniş alana yayılan küme olduğunu gösterebilir. Taksi şirketi bekleme noktalarını küme merkezlerine, araç sayısını küme büyüklüğüne göre belirleyebilir.

Ne işe yarar: Küme n, merkez ve dışbükey zarf alanını verir.

Sonuca etkisi: Kümeleme sonucunu değiştirmez; kümeleri özetler.

Doğrulama verisinde: 180. meridyeni kesen quakes kümesinde en büyük küme zarfı 298 358.67 km2.

Değer (yok, sütun)

Kavram: DBSCAN yalnızca konumları kullanır; noktaların taşıdığı bir değer kümelemeye girmez. Değer sütunu bu yöntemde etkisizdir.

Gündelik örnek: Her çağrının ücret bilgisi olsa bile kümeler yalnızca çağrıların nerede yapıldığına göre kurulur. Pahalı yolculukların nerede toplandığı sorulacaksa Getis-Ord Gi* gibi değer kullanan bir yöntem gerekir.

Ne işe yarar: Kümelemede kullanılmaz.

Sonuca etkisi: Seçim sonucu değiştirmez.

Gerçek veride örnek

Veri: Fiji depremleri, R datasets quakes

Değişkenler: 1000 deprem odağı (enlem/boylam, 180. meridyeni kesiyor); yarıçap k-uzaklık önerisiyle dolu

  • Soru: Fiji yakınındaki 1000 deprem odağı mekânda hangi yoğun kümelere ayrılıyor?
  • Yöntem: DBSCAN, büyük daire uzaklığı; en az 5 nokta, yarıçap k-uzaklık grafiğinin diz noktasından eps = 77.9 km.
  • Sonuç: 8 küme ve 41 gürültü noktası; en büyük küme 743 odak (merkez -21.36, -177.49), ikinci 120 odak (merkez -13.61, 166.84), üçüncü 48 odak.
  • Ek bulgu: Veri 180. meridyeni keser; boylam farkları sarıldığı için meridyenin iki yakasındaki odaklar tek küme olarak bulunur.
  • Sınırlılık: Sonuç eps ve en az nokta seçimine duyarlıdır; diz önerisi bir başlangıç değeridir, farklı eps ile denetlenmelidir.
  • Rapor satırı: DBSCAN (eps = 77.9 km, minPts = 5) 8 küme ve 41 gürültü noktası verdi.

İlgili kavramlar

ε komşuluğu ve en az nokta sayısı (DBSCAN)Siluet katsayısıUzaklık ölçüsü (Öklid, Manhattan, Gower, büyük daire)Küme sayısının seçimiDirsek yöntemi ve k-uzaklık grafiği

Ö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.