Yoğunluk Tabanlı Kümeleme

Önceki üç ders aynı örtük kuralı paylaşıyordu: bölmeleme, kümedeki her noktayı bir kümeye atamak zorundaydı. Benzerlik tanımı, başlangıç noktası ve bağlantı ölçütü bölmelemeyi değiştiriyordu, ama hiçbirinde “bu nokta hiçbir kümeye ait değil” gibi bir çıktı yoktu. Merkezlerden uzakta, tek başına kalmış bir abone de en yakın merkeze yazılıyor ve o kümenin ortalamasını kendi yönüne çekiyordu.

Bu ders o zorunluluğu kaldıran bir aile alır. Yoğunluk tabanlı kümeleme küme sayısını girdi olarak istemez; “küme” sözcüğünü yerel bir kalabalık üzerinden tanımlar ve kalabalığa bağlanamayan noktaları gürültü noktası olarak dışarıda bırakır. Bedeli, dışarıda bırakma kararının iki ayar değişkenine bağlı olmasıdır; bu iki sayı çıkan küme sayısını da gürültü sayısını da geniş bir aralıkta oynatır.

• KU31. Küme M27/K01–K03’ten gelen kurgu abone tablosudur: 1.260 abone, tohum 20260218, bölme 756/252/252. Kümeleme yalnız 756 satırlık eğitim payı üzerinde çalışır; etiket sütunu bu kursta bir kenara konmuştur ve hiçbir yöntem onu görmez.
• KU32. Altı sayısal sütun eğitim payından öğrenilen standart puanla ölçeklenir. Bölge göstergeleri dışarıda kalır: iki ayrı bölgeden gelen her nokta çiftine aynı sabit katkı eklenirdi ve bu, yoğunluğa sessizce konmuş bir ağırlık olurdu. Uzaklık kare uzaklığın kareköküdür, böylece yarıçap ölçeklenmiş sütunlarla aynı birimde okunur.
• KU33. Çekirdek nokta, komşuluk yarıçapı içinde kendisiyle birlikte en az m nokta bulunan noktadır. Bir çekirdek noktanın yarıçapına giren ama kendisi çekirdek olmayan nokta sınır noktası, hiçbir çekirdek noktanın yarıçapına girmeyen nokta gürültü noktasıdır.
• KU34. Bu dersin taban çizgisi rastgele işaretlemedir: yöntemin çıktısı bir işaretleme olduğu için taban da işaretleme olmalıdır. Tek küme tabanı hiçbir noktayı işaretlemez ve karşılaştırılacak sayı üretmez.
• KU35. Yapısız başvuru sütun içi yeniden karıştırmayla kurulur: her sütun kendi içinde bağımsız karıştırılır, sütunun dağılımı birebir korunur, yalnız sütunlar arası ilişki bozulur. Araç M26/K05’in yeniden karıştırma sınamasınındır; sınama kuramı burada tekrarlanmaz.
• KU36. Halka kurgusu bu ders için üretilmiş ayrı bir kurgu kümedir; abone tablosuyla ilgisi yoktur ve yalnız biçim karşılaştırması için kullanılır.

Çekirdek, Sınır ve Gürültü Noktası

Yordam üç satırlık bir tanımdan doğar. Her nokta için komşuluk yarıçapı içindeki komşular sayılır; sayı eşiği aşıyorsa nokta çekirdektir. Birbirinin yarıçapına giren çekirdek noktalar aynı kümeye bağlanır ve bağlantı zincir gibi yayılır. Zincir bir sınır noktasına ulaştığında durur: sınır noktası kümeye katılır ama kümeyi genişletmez.

# yogunluk.py — MODELDIR. M27/K01–K03'un KURGU abone tablosu ayni tohumla
# yeniden uretilir; etiket sutunu bu kursta bilerek bir kenara konur.
import math
import statistics

TOHUM, HAM, M32 = 20260218, 1400, 0xFFFFFFFF
BOLGE = [(0.28, 21), (0.22, 17), (0.18, 26), (0.14, 14), (0.18, 23)]


def uretec(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def sonraki():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return sonraki


def ayrik(u, w):
    t = 0.0
    for i, x in enumerate(w):
        t += x
        if u < t:
            return i
    return len(w) - 1


ABONE, VERI = [], []
for i in range(HAM):
    r = uretec(TOHUM + i)
    b = BOLGE[ayrik(r(), [x[0] for x in BOLGE])]
    hane = 1 + ayrik(r(), [0.06, 0.24, 0.30, 0.24, 0.11, 0.05])
    memnun = 1 + ayrik(r(), [0.08, 0.14, 0.27, 0.34, 0.17])
    if r() >= 0.046:
        ABONE.append((10001 + i, b[1], hane, memnun))
for no, taban, hane, memnun in ABONE:
    r, v = uretec(TOHUM + 7000 + no), []
    for d in range(ayrik(r(), [0.05, 0.12, 0.21, 0.62])):
        v.append(0.0 if r() < 0.038 else math.floor(
            taban * math.exp((r() + r() + r() - 1.5) * 0.62)
            * (1 - d * 0.05) * 100 + 0.5) / 100)
        r()
    if v:
        ort = round(sum(v) / len(v), 2)
        VERI.append({"ort_tuketim": ort, "oynaklik": round(max(v) - min(v), 2),
                     "hane": hane, "memnuniyet": memnun, "donem": len(v),
                     "kisi_basi": round(ort / hane, 3)})

SAYISAL = ["ort_tuketim", "oynaklik", "hane", "memnuniyet", "donem", "kisi_basi"]


def karistir(veri, tohum):
    r, s = uretec(tohum), list(range(len(veri)))
    for i in range(len(s) - 1, 0, -1):
        j = int(r() * (i + 1))
        s[i], s[j] = s[j], s[i]
    return [veri[i] for i in s]


EGT = karistir(VERI, TOHUM + 90000)[:756]
OLCEK = {a: (statistics.fmean(x[a] for x in EGT),
             statistics.pstdev([x[a] for x in EGT])) for a in SAYISAL}
N = [[(x[a] - OLCEK[a][0]) / OLCEK[a][1] for a in SAYISAL] for x in EGT]


def uzaklik_dizeyi(P):
    D = [[0.0] * len(P) for _ in P]
    for i in range(len(P)):
        for j in range(i + 1, len(P)):
            D[i][j] = D[j][i] = math.dist(P[i], P[j])
    return D


def komsuluk(D, e):
    return [[j for j in range(len(D)) if j != i and D[i][j] <= e] for i in range(len(D))]


def yogunluk_kumele(kom, m):            # MODELDIR: yogunluk tabanli bolmeleme
    cek = [len(k) + 1 >= m for k in kom]         # cekirdek nokta
    etk, c = [-1] * len(kom), 0
    for i in range(len(kom)):
        if etk[i] != -1 or not cek[i]:
            continue
        etk[i], yigin = c, [i]
        while yigin:
            u = yigin.pop()
            if not cek[u]:                       # sinir noktasi genislemez
                continue
            for v in kom[u]:
                if etk[v] == -1:
                    etk[v], _ = c, yigin.append(v)
        c += 1
    return etk, c, sum(1 for x in etk if x == -1)


D = uzaklik_dizeyi(N)
BES = [sorted(D[i])[5] for i in range(len(N))]   # besinci en yakin komsuya uzaklik
ETK, KUME, GURULTU = yogunluk_kumele(komsuluk(D, 1.2), 5)
gur = [i for i in range(len(N)) if ETK[i] == -1]
rs = karistir(list(range(len(N))), TOHUM + 410000)[:len(gur)]
buyuk = sorted((ETK.count(c) for c in range(KUME)), reverse=True)
print(f"nokta {len(N)}, sutun {len(SAYISAL)}")
print(f"e=1.20 m=5 -> kume {KUME}, gurultu {GURULTU}, buyuklukler {buyuk}")
print(f"besinci komsu uzakligi: gurultu {statistics.fmean(BES[i] for i in gur):.4f}, "
      f"rastgele isaretlenen {statistics.fmean(BES[i] for i in rs):.4f}, "
      f"tumu {statistics.fmean(BES):.4f}")

nokta 756, sutun 6
e=1.20 m=5 -> kume 6, gurultu 73, buyuklukler [454, 112, 82, 23, 6, 6]
besinci komsu uzakligi: gurultu 1.7551, rastgele isaretlenen 1.0200, tumu 0.9611

İlk okunacak şey küme büyüklükleridir: 454, 112, 82, 23, 6, 6. Yöntem eşit büyüklükte kümeler üretmiyor; 756 noktanın 454’ü tek bir kümede toplanıyor, son iki küme altışar noktadan oluşuyor. Merkez temelli bölmeleme böyle bir çıktı veremez, çünkü her merkez kendine yakın noktaları çeker ve büyüklükler dengelenir. Burada büyüklüğü belirleyen merkez değil bağlantı zinciridir.

İkinci sayı 73’tür: bu ayarda 756 abonenin 73’ü hiçbir kümeye bağlanmıyor. Ama bir işaretlemenin kendi başına anlamı yoktur. Taban çizgisi olarak aynı sayıda noktayı rastgele işaretleyen yordam seçilir, çünkü yöntemin ürettiği şey bir bölmeleme değil bir işaretlemedir. Ölçü, işaretlenen noktaların beşinci en yakın komşusuna uzaklığıdır: yöntemin işaretlediği 73 noktada ortalama 1,7551, rastgele işaretlenen 73 noktada 1,0200, tüm kümede 0,9611. Fark 0,7351.

Fark nereden geliyor sorusunun yanıtı burada rahatsız edicidir: ölçütten. En az nokta sayısı beş olduğu için yöntem tam olarak “dördüncü komşusu yarıçap içinde mi” sorusuna bakarak işaretliyor ve beşinci komşu uzaklığı neredeyse aynı büyüklüktür. Bir yöntemi kendi ölçütüyle sınamak, tanımı yeniden yazmaktan başka bir şey değildir; kullanılabilir bir fark için ölçütün dışına çıkmak gerekir.

İki Ayar Değişkeninin Süpürülmesi

Küme sayısı bu ailede girdi değildir, ama iki ayar değişkeni vardır ve ikisi de veriden öğrenilmez. M27/K03’ün kuralı sürer: denenen aday sayısı yazılır. Süpürme altı yarıçap ile üç eşiği çaprazlar, her hücrede küme sayısı ile gürültü sayısını birlikte basar ve aynı süpürme sütunları kendi içinde karıştırılmış kümede de koşturulur.

def sutun_karistir(P, tohum):
    Y = [list(x) for x in P]
    for s in range(len(P[0])):
        for i, j in enumerate(karistir(list(range(len(P))), tohum + s * 17)):
            Y[i][s] = P[j][s]
    return Y


YAP = sutun_karistir(N, TOHUM + 610000)          # KURGU: sutun ici yeniden karistirma
DY = uzaklik_dizeyi(YAP)
ELER, MLER, SUPURME = (0.6, 0.8, 1.0, 1.2, 1.5, 1.8), (3, 5, 9), []
print(f"{'e':>5}" + "".join(f"{'m=' + str(m):>12}" for m in MLER) + "   (kume/gurultu)")
for e in ELER:
    kv, ky, sv, sy = komsuluk(D, e), komsuluk(DY, e), [], []
    for m in MLER:
        _, c, g = yogunluk_kumele(kv, m)
        _, cy, gy = yogunluk_kumele(ky, m)
        SUPURME.append((c, g, cy, gy))
        sv.append(f"{c}/{g}")
        sy.append(f"{cy}/{gy}")
    print(f"{e:>5.2f}" + "".join(f"{x:>12}" for x in sv) + "   veri")
    print(f"{'':>5}" + "".join(f"{x:>12}" for x in sy) + "   karistirilmis")
print(f"\ndenenen aday {len(SUPURME)}; kume sayisi {min(s[0] for s in SUPURME)} ile "
      f"{max(s[0] for s in SUPURME)} arasinda, gurultu {min(s[1] for s in SUPURME)} ile "
      f"{max(s[1] for s in SUPURME)} arasinda")
print(f"gurultunun karistirilmis kumeden az oldugu ayar "
      f"{sum(1 for s in SUPURME if s[1] < s[3])}/{len(SUPURME)}; "
      f"kume sayisinin farkli oldugu ayar {sum(1 for s in SUPURME if s[0] != s[2])}")

    e         m=3         m=5         m=9   (kume/gurultu)
 0.60      56/332      23/490       6/674   veri
           33/602       6/720       0/756   karistirilmis
 0.80      52/220      24/356      10/550   veri
           35/468      13/595       1/742   karistirilmis
 1.00       15/74       6/132       4/230   veri
           16/232       6/332       2/449   karistirilmis
 1.20       13/39        6/73       4/118   veri
            6/113       6/171       3/275   karistirilmis
 1.50        2/17        1/26        1/43   veri
             3/46        2/57        1/89   karistirilmis
 1.80         1/4         1/5         1/6   veri
             2/14        1/22        1/30   karistirilmis

denenen aday 18; kume sayisi 1 ile 56 arasinda, gurultu 4 ile 674 arasinda
gurultunun karistirilmis kumeden az oldugu ayar 18/18; kume sayisinin farkli oldugu ayar 13

Aynı veride küme sayısı 1 ile 56, gürültü sayısı 4 ile 674 arasında geziniyor. Yarıçap 0,60 ve eşik 9 olduğunda 756 abonenin 674’ü gürültü sayılıyor, yarıçap 1,80 olduğunda 4’ü. “Bu veride kaç küme var” sorusunun yanıtı sorunun kendisinden değil, iki ayarın seçilmesinden sonra doğuyor.

Karıştırılmış satırlar farkın kaynağını ayırır. Sütun içi karıştırma her sütunun kendi dağılımını birebir korur; bozduğu tek şey sütunlar arasındaki ilişkidir, dolayısıyla iki koşum arasındaki her fark sütunlar arası yapıdan gelir. Gürültü sayısı on sekiz ayarın on sekizinde karıştırılmış kümede daha yüksek: yarıçap 1,20 ve eşik 5’te 73’e karşı 171. Aynı yoğunluk eşiğinde gerçek küme daha derli topludur ve bu fark veriden gelir.

Küme sayısı bunu söylemez. On sekiz ayarın beşinde iki koşum aynı küme sayısını veriyor, geri kalanında fark bir yön taşımıyor: yarıçap 0,60 ile eşik 3’te gerçek veri 56, karıştırılmış küme 33 çıkarıyor, ama yarıçap 1,00’de sıralama tersine dönüyor. Yapısız bir kümede de “küme” bulunur; bulunan kümelerin sayısı yapının kanıtı değildir.

Merkezin Bölemediği Biçim

Bu ailenin merkez temelli aileden ayrıldığı yer küme sayısı değil, kümenin biçimidir. Merkez temelli bölmeleme uzayı merkezler arasındaki dik doğrularla böler ve çıkan parçalar her zaman dışbükeydir. Ortak merkezli iki halka bu bölmelemenin altından kalkamayacağı en yalın biçimdir: iç halkanın da dış halkanın da merkezi aynı noktadır.

def halka(n, yaricap, tohum):                    # KURGU: merkezi ortak iki halka
    r, p = uretec(tohum), []
    for _ in range(n):
        a, s = r() * 2 * math.pi, yaricap + (r() + r() + r() - 1.5) * 0.30
        p.append([s * math.cos(a), s * math.sin(a)])
    return p


H = halka(120, 1.0, TOHUM + 800000) + halka(240, 3.2, TOHUM + 801000)
DH = uzaklik_dizeyi(H)


def merkez_bolmele(P, k, tohum, tur=60):         # MODELDIR: merkez temelli bolmeleme
    r = uretec(tohum)
    M, e = [list(P[int(r() * len(P))]) for _ in range(k)], [0] * len(P)
    for _ in range(tur):
        for i, x in enumerate(P):
            e[i] = min(range(k), key=lambda c: math.dist(x, M[c]))
        for c in range(k):
            g = [P[i] for i in range(len(P)) if e[i] == c]
            M[c] = [statistics.fmean(x[d] for x in g) for d in range(2)] if g else M[c]
    return e


def kume_ici(P, e):                              # olcut 1: merkezlere toplam uzaklik
    t = 0.0
    for c in set(e):
        g = [P[i] for i in range(len(P)) if e[i] == c]
        m = [statistics.fmean(x[d] for x in g) for d in range(2)]
        t += sum(math.dist(x, m) for x in g)
    return t


def en_uzun_bag(P, e, D):                        # olcut 2: en uzun zorunlu baglanti
    u = 0.0
    for c in set(e):
        idx = [i for i in range(len(P)) if e[i] == c]
        ic, kal = [idx[0]], set(idx[1:])
        while kal:
            d, v = min((min(D[j][i] for i in ic), j) for j in kal)
            u, _ = max(u, d), ic.append(v)
            kal.discard(v)
    return u


EM = merkez_bolmele(H, 2, TOHUM + 805000)
EY, cy, gy = yogunluk_kumele(komsuluk(DH, 0.6), 4)
print(f"halka noktalari {len(H)}; ic halka 120, dis halka 240")
print(f"merkez temelli k=2 -> buyuklukler {[EM.count(0), EM.count(1)]}")
print(f"yogunluk e=0.60 m=4 -> kume {cy}, gurultu {gy}, "
      f"buyuklukler {[EY.count(0), EY.count(1)]}")
print(f"{'olcut':<26}{'merkez temelli':>16}{'yogunluk tabanli':>18}")
print(f"{'kume ici toplam uzaklik':<26}{kume_ici(H, EM):>16.2f}{kume_ici(H, EY):>18.2f}")
print(f"{'en uzun zorunlu baglanti':<26}{en_uzun_bag(H, EM, DH):>16.4f}"
      f"{en_uzun_bag(H, EY, DH):>18.4f}")
print(f"iki bolmelemenin ayristigi nokta "
      f"{sum(1 for i in range(len(H)) if (EM[i] == EM[0]) != (EY[i] == EY[0]))}")

halka noktalari 360; ic halka 120, dis halka 240
merkez temelli k=2 -> buyuklukler [171, 189]
yogunluk e=0.60 m=4 -> kume 2, gurultu 0, buyuklukler [120, 240]
olcut                       merkez temelli  yogunluk tabanli
kume ici toplam uzaklik             703.25            878.71
en uzun zorunlu baglanti            1.6311            0.5041
iki bolmelemenin ayristigi nokta 153

İki bölmeleme 360 noktanın 153’ünde ayrışıyor. Merkez temelli yordam 171 ve 189 büyüklüğünde iki parça veriyor: her iki halkayı da ortadan kesen bir doğru çiziyor. Yoğunluk tabanlı yordam 120 ve 240 veriyor, iki halkayı ayırıyor ve tek bir noktayı bile gürültüye atmıyor.

Buradan “yoğunluk tabanlı yöntem doğru sonucu buldu” çıkarmak, kursun uyardığı hatanın tam kendisidir. İki ölçüt basılıyor ve ters sıralama veriyorlar. Küme içi toplam uzaklıkta merkez temelli bölmeleme 703,25 ile önde, yoğunluk tabanlı bölmeleme 878,71 ile geride — bu şaşırtıcı değildir, çünkü merkez temelli yordam tam olarak bu sayıyı küçültmek üzere çalışır. Bir kümeyi bir arada tutmak için katlanılması gereken en büyük sıçramada sıralama tersine döner: 1,6311’e karşı 0,5041.

Hangi bölmelemenin daha iyi olduğu sorusunun yanıtı yoktur, çünkü soru eksiktir. Yanıtlanabilir soru şudur: hangi ölçüte göre. Ölçüt “merkezlerden ortalama uzaklık” ise merkez temelli bölmeleme kazanır, “bir arada durma” ise yoğunluk tabanlı bölmeleme. Fark veriden değil ölçütten gelir; aynı 360 nokta üzerinde iki ayrı soru soruluyor.

Özet

• Yoğunluk tabanlı kümeleme her noktayı bir kümeye atamak zorunda değildir; seçilen ayarda 756 noktanın 73’ü dışarıda kalıyor ve küme büyüklükleri 454 ile 6 arasında dağılıyor.
• İşaretlenen 73 noktanın beşinci komşu uzaklığı 1,7551, aynı sayıda noktayı rastgele işaretleyen taban çizgisinde 1,0200; fark 0,7351 ama bu fark ölçütün kendisinden gelir, çünkü yöntem neredeyse aynı büyüklüğe bakarak işaretliyor.
• On sekiz ayar bileşiminde küme sayısı 1 ile 56, gürültü sayısı 4 ile 674 arasında değişiyor.
• Sütun içi yeniden karıştırılmış kümede gürültü sayısı on sekiz ayarın on sekizinde daha yüksek (1,20 ve 5’te 73’e karşı 171); bu fark veriden gelir. Küme sayısı ayrım yapmaz.
• Ortak merkezli iki halkada iki bölmeleme 360 noktanın 153’ünde ayrışıyor ve iki ölçüt ters sıralama veriyor: küme içi toplam uzaklıkta 703,25’e karşı 878,71, en uzun zorunlu bağlantıda 1,6311’e karşı 0,5041.

Sonraki Adım

Bu ailede bir nokta ya bir kümededir, ya sınırdadır, ya da dışarıdadır; üç durum da kesindir. Oysa iki yoğun bölgenin tam ortasına düşen bir abone için bu kesinlik uydurmadır: yordam onu bir tarafa yazar ve ne kadar zor bir kararla yazdığını kaydetmez. Sonraki ders atamayı bir sayıya çevirir. Her nokta her kümeye bir sorumluluk payıyla bağlanır, paylar toplamı bire eşittir ve payları birbirine yakın olan nokta kararsızdır. Kümeler merkez ve değişkenlikle tanımlanan bir karışım modeli olarak yazılır, parametreler yinelemeli bir kestirimle bulunur ve iki sayı ölçülür: kaç nokta iki kümeye de yakın payla bağlı, ve bu paylar sert atamaya indirildiğinde ne kadar bilgi kayboluyor.