Bölüm 3 · Klasik algoritmalar · Ders 19

DBSCAN: yoğunluğa göre kümeler

Kıvrık raf sıralarını LiDAR noktalarından bulmak, gürültüyü ayıklayarak

Veri. Depoda gezen bir otonom forklift zemin seviyesindeki LiDAR’ıyla 365 nokta topladı: iki kıvrık raf sırası ile yuvarlak bir raf (110’ar nokta), bir de tozdan ve yansımadan gelen 35 seyrek gürültü noktası. Kaç nesne olduğunu bilmiyoruz. k-means burada işe yaramaz: hilalleri ortadan böler ve gürültüyü de bir kümeye zorla katar.

LiDAR taraması: 365 nokta, etiket yok365 nokta · eps = 0,50 m · minPts = 5

1 / 63

eps (m) 0.5minPts 5

dbscan.pypython

import numpy as np
rng = np.random.default_rng(3)
def yay(cx, cy, r, a0, a1, n): # kıvrık raf sırası
a = rng.uniform(a0, a1, n)
p = np.c_[cx + r * np.cos(a), cy + r * np.sin(a)]
return p + rng.normal(0, 0.1, (n, 2)) # 10 cm ölçüm gürültüsü
X = np.vstack([yay(4, 2.8, 3, 0.3, 2.8, 110), # hilal 1
yay(7, 5.2, 3, 3.4, 6.0, 110), # hilal 2
yay(12.5, 4, 1.2, 0, 6.3, 110), # yuvarlak raf
rng.uniform(0, [15, 8], (35, 2))]) # gürültü
eps, min_pts = 0.5, 5 # metre, nokta
D = np.linalg.norm(X[:, None] - X, axis=2) # bütün uzaklıklar
N = D <= eps; cekirdek = N.sum(1) >= min_pts # çekirdek noktalar
etiket = np.full(len(X), -1); k = 0 # −1: etiketsiz
for i in np.flatnonzero(cekirdek):
if etiket[i] != -1: continue # zaten bir kümede
etiket[i] = k; kuyruk = [i] # yeni küme
while kuyruk:
j = kuyruk.pop(0) # sıradaki nokta
if not cekirdek[j]: continue # sınır: genişlemez
yeni = np.flatnonzero(N[j] & (etiket == -1)) # çemberdeki etiketsizler
etiket[yeni] = k; kuyruk += list(yeni)
k += 1
print(k, 'küme ·', (etiket == -1).sum(), 'gürültü')
def kume(eps): # aynı algoritma, fonksiyon olarak
N, c = D <= eps, (D <= eps).sum(1) >= min_pts
e, k = np.full(len(X), -1), 0
for i in np.flatnonzero(c):
if e[i] != -1: continue
e[i] = k; q = [i]
while q:
j = q.pop(0)
if not c[j]: continue
y = np.flatnonzero(N[j] & (e == -1))
e[y] = k; q += list(y)
k += 1
return e, k
def siluet(e): # ortalama siluet, gürültü hariç
m = e >= 0; L = np.unique(e[m])
if len(L) < 2: return 0.0
Dm, em = D[np.ix_(m, m)], e[m]
own = em[:, None] == L; cnt = own.sum(0)
S = np.stack([Dm[:, em == l].sum(1) for l in L], 1) # kümelere uzaklık toplamı
n = own @ cnt # kendi kümesinin boyu
a = (S * own).sum(1) / np.maximum(n - 1, 1) # kendi kümesine ort.
b = np.where(own, np.inf, S / cnt).min(1) # en yakın diğer küme
s = np.where(n > 1, (b - a) / np.maximum(a, b), 0)
return float(s.mean())
history = {'eps': [], 'clusters': [], # eps taraması
'noise_share': [], 'silhouette': []}
for e_ in np.round(np.arange(0.1, 1.501, 0.05), 2):
lab, kk = kume(e_)
r = [e_, kk, (lab == -1).mean(), siluet(lab)]
for c_, v in zip(history, r): history[c_] += [float(v)]
fin = [('clusters', k), # son ölçümler
('noise_share', (etiket == -1).mean()),
('silhouette', siluet(etiket))]
for c_, v in fin: print(f'{c_:<12}{v:>8.3f}')
import csv
with open('egitim_gecmisi.csv', 'w', newline='') as f: # satır başına bir eps
csv.writer(f).writerows([list(history),
*zip(*history.values())])
try:
import matplotlib.pyplot as plt # varsa grafik çiz
for c_ in ('silhouette', 'noise_share'):
plt.plot(history['eps'], history[c_], label=c_)
plt.xlabel('eps (m)'); plt.legend(); plt.show()
except ImportError:
print('matplotlib yok: grafik atlandı')

Eğitim paneli

Eğitim çalıştırılıyor…

Sahnedeki her sayı, aynı algoritmanın tarayıcında yapılan gerçek çalıştırmasından gelir (sabit tohum, her seferinde aynı sonuç). Python kodunu kendi bilgisayarında çalıştırırsan rastgele başlangıçlar farklı olacağı için sayılar biraz değişebilir.

Veri seti

Tüm veri setleri →

Bu dersin kodu verisini kendi içinde üretir; indirilecek dosya yok. Kodu yine de aşağıda tarayıcında çalıştırabilirsin.

Kodu tarayıcıda çalıştırPython · NumPy · matplotlib · Pyodide

Python ve NumPy bu sayfada, tarayıcında çalışır (Pyodide). Kodu değiştirip yeniden çalıştırabilirsin; dersin veri setleri çalışma klasöründe hazır. Kod matplotlib kullanırsa grafikler çıktının altında görünür, yazdığı dosyalar (ör. egitim_gecmisi.csv) indirilebilir.

dbscan.pypython

import numpy as np
rng = np.random.default_rng(3)
def yay(cx, cy, r, a0, a1, n):                # kıvrık raf sırası
    a = rng.uniform(a0, a1, n)
    p = np.c_[cx + r * np.cos(a), cy + r * np.sin(a)]
    return p + rng.normal(0, 0.1, (n, 2))     # 10 cm ölçüm gürültüsü
X = np.vstack([yay(4, 2.8, 3, 0.3, 2.8, 110),  # hilal 1
               yay(7, 5.2, 3, 3.4, 6.0, 110),  # hilal 2
               yay(12.5, 4, 1.2, 0, 6.3, 110),  # yuvarlak raf
               rng.uniform(0, [15, 8], (35, 2))])  # gürültü
eps, min_pts = 0.5, 5                         # metre, nokta
D = np.linalg.norm(X[:, None] - X, axis=2)    # bütün uzaklıklar
N = D <= eps; cekirdek = N.sum(1) >= min_pts  # çekirdek noktalar
etiket = np.full(len(X), -1); k = 0           # −1: etiketsiz
for i in np.flatnonzero(cekirdek):
    if etiket[i] != -1: continue              # zaten bir kümede
    etiket[i] = k; kuyruk = [i]               # yeni küme
    while kuyruk:
        j = kuyruk.pop(0)                     # sıradaki nokta
        if not cekirdek[j]: continue          # sınır: genişlemez
        yeni = np.flatnonzero(N[j] & (etiket == -1))  # çemberdeki etiketsizler
        etiket[yeni] = k; kuyruk += list(yeni)
    k += 1
print(k, 'küme ·', (etiket == -1).sum(), 'gürültü')
def kume(eps):                                # aynı algoritma, fonksiyon olarak
    N, c = D <= eps, (D <= eps).sum(1) >= min_pts
    e, k = np.full(len(X), -1), 0
    for i in np.flatnonzero(c):
        if e[i] != -1: continue
        e[i] = k; q = [i]
        while q:
            j = q.pop(0)
            if not c[j]: continue
            y = np.flatnonzero(N[j] & (e == -1))
            e[y] = k; q += list(y)
        k += 1
    return e, k
def siluet(e):                                # ortalama siluet, gürültü hariç
    m = e >= 0; L = np.unique(e[m])
    if len(L) < 2: return 0.0
    Dm, em = D[np.ix_(m, m)], e[m]
    own = em[:, None] == L; cnt = own.sum(0)
    S = np.stack([Dm[:, em == l].sum(1) for l in L], 1)  # kümelere uzaklık toplamı
    n = own @ cnt                             # kendi kümesinin boyu
    a = (S * own).sum(1) / np.maximum(n - 1, 1)  # kendi kümesine ort.
    b = np.where(own, np.inf, S / cnt).min(1)  # en yakın diğer küme
    s = np.where(n > 1, (b - a) / np.maximum(a, b), 0)
    return float(s.mean())
history = {'eps': [], 'clusters': [],         # eps taraması
           'noise_share': [], 'silhouette': []}
for e_ in np.round(np.arange(0.1, 1.501, 0.05), 2):
    lab, kk = kume(e_)
    r = [e_, kk, (lab == -1).mean(), siluet(lab)]
    for c_, v in zip(history, r): history[c_] += [float(v)]
fin = [('clusters', k),                       # son ölçümler
       ('noise_share', (etiket == -1).mean()),
       ('silhouette', siluet(etiket))]
for c_, v in fin: print(f'{c_:<12}{v:>8.3f}')
import csv
with open('egitim_gecmisi.csv', 'w', newline='') as f:  # satır başına bir eps
    csv.writer(f).writerows([list(history),
                             *zip(*history.values())])
try:
    import matplotlib.pyplot as plt           # varsa grafik çiz
    for c_ in ('silhouette', 'noise_share'):
        plt.plot(history['eps'], history[c_], label=c_)
    plt.xlabel('eps (m)'); plt.legend(); plt.show()
except ImportError:
    print('matplotlib yok: grafik atlandı')

Kendi CSV’ni yükle

Çıktı

Çıktı burada görünecek.

Nasıl çalışır

Her noktanın çevresine eps yarıçaplı bir çember çizilir; içinde (kendisi dahil) en az minPts nokta varsa o nokta çekirdektir.
Etiketsiz bir çekirdekten yeni küme başlar. Kuyruktan çıkan her çekirdek, çemberindeki etiketsiz noktaları kümeye katar (genişlik öncelikli arama).
Çekirdek olmayan ama bir çekirdeğin çemberine düşen nokta sınır noktasıdır: kümeye girer ama küme ondan genişlemez.
Hiçbir kümeye ulaşılamayan noktalar gürültüdür. Küme sayısını kimse söylemez; yoğunluk belirler.
Şunu dene: eps’i 0,15 yap; çember çok küçülür, noktaların yarıdan fazlası gürültü olur. 0,8 yaparsan iki hilal birbirine bağlanıp tek küme olur.

Neden önemli

DBSCAN, LiDAR ve derinlik kamerası nokta bulutlarını engellere ayırmanın en yaygın yollarından biridir: küme sayısını bilmek gerekmez, biçim serbesttir ve tek tük yansımalar gürültü olarak atılır. Otonom araçlarda ve depo robotlarında engel çıkarma, harita temizleme ve GPS izlerinden durak bulma gibi işlerde kullanılır.

ESOF 323, 11. hafta: robotlarda derin öğrenme →