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

k-means: etiketsiz gruplar

LiDAR noktalarını nesnelere ayırmak, tek bir cevap verilmeden

Veri. Robot süpürgenin LiDAR'ı odayı taradı ve 600 nokta gördü: 250'si duvarda, 200'ü kanepede, 150'si masa ayaklarında. Program hangi noktanın hangi nesneye ait olduğunu hiç görmez; yalnız kaç grup arayacağını bilir: k = 3.

cevap verilmedi600 nokta · k = 3

1 / 69

Grup sayısı k 3Tohum 17

kmeans.pypython

import numpy as np
X = np.genfromtxt('lidar-2b.csv', delimiter=',', skip_header=1) # 600 nokta (x, y), metre
k = 3 # bulunacak grup sayısı
rng = np.random.default_rng(17)
best = np.inf # henüz deneme yok
for start in range(10): # on rastgele başlangıç
C = X[rng.choice(len(X), k, replace=False)] # üç nokta merkez olur
while True:
old = C.copy() # merkezleri hatırla
d = ((X[:, None] - C) ** 2).sum(2) # her merkeze uzaklık²
g = d.argmin(1) # en yakın merkez kazanır
C = np.array([X[g == j].mean(0) for j in range(k)]) # ortalamaya taşı
if np.allclose(C, old): break # kimse kıpırdamadı
s = d.min(1).sum() # toplam kare uzaklık
if s < best: best, keep = s, g # en sıkısını sakla
print(np.bincount(keep)) # grup başına nokta
history = {'k': [], 'inertia': [], 'silhouette': []} # dirsek: k = 1…8 için aynı on deneme
D = np.sqrt(((X[:, None] - X) ** 2).sum(2)) # 600 × 600 uzaklık (siluet için)
for kk in range(1, 9):
rng, bs = np.random.default_rng(17), np.inf
for start in range(10):
C = X[rng.choice(len(X), kk, replace=False)]
while True:
old, g = C.copy(), ((X[:, None] - C) ** 2).sum(2).argmin(1)
C = np.array([X[g == j].mean(0) if (g == j).any() else C[j] for j in range(kk)]) # boş grup yerinde kalır
if np.allclose(C, old): break
s = ((X - C[g]) ** 2).sum() # inertia: grup içi kare uzaklık
if s < bs: bs, bg = s, g
M = np.eye(kk)[bg]; n = M.sum(0); S = D @ M # her noktadan her gruba toplam uzaklık
a = (S * M).sum(1) / np.maximum(n[bg] - 1, 1) # kendi grubuna ortalama uzaklık
b = np.where((M > 0) | (n == 0), np.inf, S / np.maximum(n, 1)).min(1) # en yakın diğer gruba
sil = ((b - a) / np.maximum(a, b))[n[bg] > 1].sum() / len(X) if kk > 1 else 0.0 # siluet skoru (−1…1)
for key, v in zip(history, (kk, bs, sil)): history[key].append(float(v))
print(f'k={kk} inertia={bs:9.1f} siluet={sil:.3f}') # son ölçümler tablosu
import csv
with open('egitim_gecmisi.csv', 'w', newline='') as f: # geçmişi CSV'ye yaz
csv.writer(f).writerows([list(history), *zip(*history.values())]) # satır başına bir k
try:
import matplotlib.pyplot as plt # varsa grafik çiz
fig, (a1, a2) = plt.subplots(1, 2, figsize=(9, 3.5))
a1.plot(history['k'], history['inertia'], 'o-'); a1.set_title('elbow'); a2.plot(history['k'], history['silhouette'], 'o-')
a2.set_title('silhouette'); 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 →

Oda taraması (2B LiDAR)lidar-2b.csv · 600 satır · 2 sütun
Veri setini indir
Çiçek ölçüleri (iris benzeri)alıştırmacicek-olculeri.csv · 150 satır · 5 sütun
Veri setini indir

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.

kmeans.pypython

import numpy as np
X = np.genfromtxt('lidar-2b.csv', delimiter=',', skip_header=1)  # 600 nokta (x, y), metre
k = 3                                         # bulunacak grup sayısı
rng = np.random.default_rng(17)
best = np.inf                                 # henüz deneme yok
for start in range(10):                       # on rastgele başlangıç
    C = X[rng.choice(len(X), k, replace=False)]  # üç nokta merkez olur
    while True:
        old = C.copy()                        # merkezleri hatırla
        d = ((X[:, None] - C) ** 2).sum(2)    # her merkeze uzaklık²
        g = d.argmin(1)                       # en yakın merkez kazanır
        C = np.array([X[g == j].mean(0) for j in range(k)])  # ortalamaya taşı
        if np.allclose(C, old): break         # kimse kıpırdamadı
    s = d.min(1).sum()                        # toplam kare uzaklık
    if s < best: best, keep = s, g            # en sıkısını sakla
print(np.bincount(keep))                      # grup başına nokta
history = {'k': [], 'inertia': [], 'silhouette': []}  # dirsek: k = 1…8 için aynı on deneme
D = np.sqrt(((X[:, None] - X) ** 2).sum(2))   # 600 × 600 uzaklık (siluet için)
for kk in range(1, 9):
    rng, bs = np.random.default_rng(17), np.inf
    for start in range(10):
        C = X[rng.choice(len(X), kk, replace=False)]
        while True:
            old, g = C.copy(), ((X[:, None] - C) ** 2).sum(2).argmin(1)
            C = np.array([X[g == j].mean(0) if (g == j).any() else C[j] for j in range(kk)])  # boş grup yerinde kalır
            if np.allclose(C, old): break
        s = ((X - C[g]) ** 2).sum()           # inertia: grup içi kare uzaklık
        if s < bs: bs, bg = s, g
    M = np.eye(kk)[bg]; n = M.sum(0); S = D @ M  # her noktadan her gruba toplam uzaklık
    a = (S * M).sum(1) / np.maximum(n[bg] - 1, 1)  # kendi grubuna ortalama uzaklık
    b = np.where((M > 0) | (n == 0), np.inf, S / np.maximum(n, 1)).min(1)  # en yakın diğer gruba
    sil = ((b - a) / np.maximum(a, b))[n[bg] > 1].sum() / len(X) if kk > 1 else 0.0  # siluet skoru (−1…1)
    for key, v in zip(history, (kk, bs, sil)): history[key].append(float(v))
    print(f'k={kk}  inertia={bs:9.1f}  siluet={sil:.3f}')  # son ölçümler tablosu
import csv
with open('egitim_gecmisi.csv', 'w', newline='') as f:  # geçmişi CSV'ye yaz
    csv.writer(f).writerows([list(history), *zip(*history.values())])  # satır başına bir k
try:
    import matplotlib.pyplot as plt           # varsa grafik çiz
    fig, (a1, a2) = plt.subplots(1, 2, figsize=(9, 3.5))
    a1.plot(history['k'], history['inertia'], 'o-'); a1.set_title('elbow'); a2.plot(history['k'], history['silhouette'], 'o-')
    a2.set_title('silhouette'); 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 deneme rastgele üç noktayı merkez seçerek başlar.
Her nokta en yakın merkeze katılır.
Her merkez, kendi noktalarının ortalamasına taşınır. Hiçbir merkez kıpırdamayana kadar tekrar.
Bazı denemeler kötü bir başlangıçta takılır. Bu yüzden on deneme yapılır, toplam kare uzaklığı en küçük olan kalır.
Şunu dene: k’yı 2 yap. İki grup tek gruba birleşir (200 · 400 nokta). Sonra 5 yap: büyük gruplar ikiye bölünür. k-ortalamalar grup sayısını kendisi bulamaz, onu sen verirsin; doğru k’yı seçmek için grafiğe bakmak ya da farklı k’ları karşılaştırmak gerekir.

Neden önemli

Cevap gerektirmez: kimsenin etiketlemediği verideki grupları bulur. Robotikte LiDAR ve derinlik kamerası noktalarını engellere ayırmakta, renk kümelemede ve harita sıkıştırmada kullanılır. Vektör arama kütüphanesi FAISS da devasa koleksiyonları k-means ile gruplara böler; arama yalnız en yakın birkaç gruba bakar.

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