Kümeleme Değerlendirmesi

Beş ders boyunca her yöntem bir sayı istedi ve o sayı hep dışarıdan verildi: kaç küme, hangi kesme yüksekliği, hangi komşuluk yarıçapı, kaç bileşen. Her seferinde seçimin sonucu oynattığı ölçüldü, ama seçimin kendisinin nasıl yapılacağı ertelendi. Denetimli kursta bu soru kolaydı — doğrulama kümesindeki etiketlere bakılır ve en iyi sayıyı veren aday alınırdı. Burada etiket yok, dolayısıyla ölçüt de veriden kurulmak zorunda.

Bu ders üç iç geçerlilik ölçütü yazar ve aynı veriye uygular. Üçü de makul, üçü de yaygın bir sezgiyi sayıya çeviriyor, ve üçü üç ayrı küme sayısı seçiyor. Ardından ölçütler hiçbir yapı taşımayan bir bulutta koşturulur; orada da bir küme sayısı seçiyorlar. En sonda etiket, bu kursta ilk ve tek kez, dış geçerlilik için açılır ve iç ölçütlerin seçtikleriyle karşılaştırılır.

• KU45. Küme M27/K01–K03’ten gelen kurgu abone tablosunun 756 satırlık eğitim payıdır, tohum 20260218, altı ölçekli sayısal sütun. Etiket üretilir ama üçüncü bölüme kadar hiçbir hesaba girmez.
• KU46. Bölmeleme konunun ikinci dersindeki merkez temelli yordamdır ve her küme sayısı için aynı tohumla koşulur; ölçütler karşılaştırılabilir olsun diye bölmeleme yordamı sabit tutulur.
• KU47. Siluet katsayısı: bir nokta için kendi kümesindeki öbür noktalara ortalama uzaklık $a$, en yakın öbür kümedeki noktalara ortalama uzaklık $b$ alınır ve $(b-a)/\max(a,b)$ hesaplanır. Küme ortalaması alınır, büyük olan seçilir.
• KU48. Saçılma oranı: her kümenin merkezine ortalama uzaklığı o kümenin yarıçapı sayılır; bir küme çifti için iki yarıçapın toplamı merkezler arası uzaklığa bölünür, her küme için en kötü ortağı alınır ve ortalaması hesaplanır. Küçük olan seçilir.
• KU49. Boşluk ölçütü: kümedeki noktaların merkezlerine toplam uzaklığının doğal logaritması, hiçbir yapı taşımayan üç başvuru bulutunda aynı büyüklüğün ortalamasından çıkarılır. Büyük olan seçilir.
• KU50. Denenen küme sayısı 2’den 10’a kadar dokuz adaydır; üç ölçütle yirmi yedi karşılaştırma yapılır. M26/K05 aynı veriye çok sayıda soru sorulduğunda en iyi sonucun bir seçim olduğunu ölçtü; o sayılar tekrarlanmaz, kural sürer.
• KU51. Yapısız bulut, sütunları birbirinden bağımsız üretilmiş 756 noktadır. Önceki derslerin sütun içi karıştırmasından farkı, orada gerçek dağılımların korunmasıdır.
• KU52. Uyum göstergesi kendi tanımıyla kurulur: bütün nokta çiftleri gezilir ve bölmelemenin “aynı kümede mi” yanıtıyla etiketin “aynı sınıfta mı” yanıtının uyuştuğu çiftlerin oranı alınır. 756 nokta 285.390 çift eder.
• KU53. Dış geçerlilikte iki taban çizgisi kullanılır: aynı küme sayısına rastgele bölmeleme ve herkesi tek kümeye koyan tek küme. İkincisi gereklidir, çünkü etiket dengesiz olduğunda tek küme yüksek bir uyum oranı üretir.

Üç Ölçüt, Üç Ayrı Küme Sayısı

Üç ölçüt de aynı sezginin farklı biçimleridir: bir bölmeleme iyiyse aynı kümedeki noktalar birbirine yakın, farklı kümelerdekiler uzak olmalıdır. Ayrıldıkları yer, “yakın” ile “uzak” arasındaki dengeyi nasıl kurdukları ve küme sayısı büyüdükçe bunu nasıl cezalandırdıklarıdır.

# gecerlilik.py — MODELDIR. M27/K01–K03'un KURGU abone tablosu; etiket sutunu
# uretilir ama bu blokta ve sonrakinde HIC kullanilmaz.
import math
import statistics

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


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, hane, memnun))
for no, b, 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(
            b[1] * math.exp((r() + r() + r() - 1.5) * 0.62)
            * (1 - d * 0.05) * 100 + 0.5) / 100)
        r()
    if not v:
        continue
    ort, oyn, q = round(sum(v) / len(v), 2), round(max(v) - min(v), 2), uretec(TOHUM + 51000 + no)
    z = (0.052 * (sum(v) / len(v) - 20) + 0.85 * (min(v) == 0.0) + 0.026 * oyn
         + 0.24 * (hane >= 5) - 0.20 * (memnun >= 4) + b[2]
         + 0.9 * (no - 10001) / 1399 + (q() + q() + q() - 1.5) * 1.30)
    VERI.append({"ort_tuketim": ort, "oynaklik": oyn, "hane": hane, "memnuniyet": memnun,
                 "donem": len(v), "kisi_basi": round(ort / hane, 3), "supheli": int(z > 1.35)})

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]
ETIKET = [x["supheli"] for x in EGT]              # ucuncu bolume kadar acilmaz
KLER = range(2, 11)


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 bolmele(P, k, tohum, tur=40):                 # 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(len(P[0]))] if g else M[c]
    return e, M


def siluet(D, e, k):                              # OLCUT 1: buyuk olan secilir
    G = [[i for i in range(len(e)) if e[i] == c] for c in range(k)]
    t = 0.0
    for i in range(len(e)):
        o = e[i]
        if len(G[o]) < 2:
            continue
        a = sum(D[i][j] for j in G[o]) / (len(G[o]) - 1)
        b = min(sum(D[i][j] for j in G[c]) / len(G[c]) for c in range(k) if c != o and G[c])
        t += (b - a) / max(a, b)
    return t / len(e)


def sacilma(P, e, M, k):                          # OLCUT 2: kucuk olan secilir
    R = [statistics.fmean([math.dist(P[i], M[c]) for i in range(len(P)) if e[i] == c] or [0.0])
         for c in range(k)]
    return statistics.fmean(
        max((R[c] + R[j]) / max(math.dist(M[c], M[j]), 1e-9) for j in range(k) if j != c)
        for c in range(k))


def kume_ici(P, e, M):
    return sum(math.dist(P[i], M[e[i]]) for i in range(len(P)))


def yapisiz(n, d, tohum):                         # KURGU: hicbir yapi tasimayan bulut
    r = uretec(tohum)
    return [[(r() + r() + r() - 1.5) * 1.4142 for _ in range(d)] for _ in range(n)]


BASVURU = [yapisiz(756, len(SAYISAL), TOHUM + 300000 + 1000 * b) for b in range(3)]


def bosluk(P, k, W):                              # OLCUT 3: buyuk olan secilir
    return statistics.fmean(math.log(kume_ici(R, *bolmele(R, k, TOHUM + 200000 + k)))
                            for R in BASVURU) - math.log(W)


def supur(P, D):
    out = {}
    for k in KLER:
        e, M = bolmele(P, k, TOHUM + 200000 + k)
        out[k] = (siluet(D, e, k), sacilma(P, e, M, k), bosluk(P, k, kume_ici(P, e, M)))
    return out


def secim(t):
    return (max(t, key=lambda k: t[k][0]), min(t, key=lambda k: t[k][1]),
            max(t, key=lambda k: t[k][2]))


D = uzaklik_dizeyi(N)
VT = supur(N, D)
print(f"nokta {len(N)}, sutun {len(SAYISAL)}, denenen kume sayisi {len(KLER)}")
print(f"{'k':>4}{'siluet':>10}{'sacilma':>10}{'bosluk':>10}")
for k in KLER:
    print(f"{k:>4}{VT[k][0]:>10.4f}{VT[k][1]:>10.4f}{VT[k][2]:>10.4f}")
print(f"secilen k -> siluet {secim(VT)[0]}, sacilma {secim(VT)[1]}, bosluk {secim(VT)[2]}")
print(f"karsilastirilan aday {len(KLER) * 3}")

nokta 756, sutun 6, denenen kume sayisi 9
   k    siluet   sacilma    bosluk
   2    0.1954    1.8924   -0.2894
   3    0.2142    1.5466   -0.2481
   4    0.1760    1.6043   -0.2288
   5    0.1799    1.4596   -0.2148
   6    0.1928    1.3328   -0.1882
   7    0.1838    1.3481   -0.1865
   8    0.1810    1.3773   -0.1856
   9    0.1781    1.3388   -0.1646
  10    0.1833    1.3947   -0.1520
secilen k -> siluet 3, sacilma 6, bosluk 10
karsilastirilan aday 27

Üç ölçüt, üç yanıt: 3, 6 ve 10. Aynı veri, aynı bölmeleme yordamı, aynı tohum. Değişen tek şey “iyi bölmeleme” tanımıdır ve tanım değişince yanıt değişiyor.

Sayıların büyüklüğü de okunmalıdır. Siluetin en yüksek değeri 0,2142; ölçütün üst sınırı 1’dir ve 0,2142 kümelerin büyük ölçüde iç içe geçtiği anlamına gelir. Sıralama 3 ile 6 arasında 0,0214’lük bir farkla belirleniyor, yani ölçüt bir tepe göstermiyor, hafif bir eğim gösteriyor. Boşluk ölçütü ise hiç tepe yapmıyor: 2’den 10’a kadar tek yönde artıyor ve seçtiği değer, denenen aralığın son adayı. Bu ölçütün yanıtı veriden değil, süpürmenin nerede kesildiğinden geliyor.

Üstelik yirmi yedi karşılaştırmadan en iyisi alınıyor. M26/K05 aynı veriye çok sayıda soru sorulduğunda en yüksek sonucun bir bulgu değil bir seçim olduğunu ölçmüştü; kural burada küme sayısı için aynen geçerlidir.

Yapısız Bir Kümede Ölçütler

Bir ölçüt yalnız bir sayı üretiyorsa, o sayının ne zaman “yapı yok” dediğini bilmek gerekir. Üç ölçüt de en iyi adayı her zaman bulur; hiçbirinin “burada küme yok” diye bir çıktısı yoktur. Bunu görmenin yolu ölçütleri yapısız bir bulutta koşturmaktır.

YAP = yapisiz(756, len(SAYISAL), TOHUM + 777000)
YT = supur(YAP, uzaklik_dizeyi(YAP))
print(f"{'k':>4}{'siluet':>10}{'sacilma':>10}{'bosluk':>10}")
for k in KLER:
    print(f"{k:>4}{YT[k][0]:>10.4f}{YT[k][1]:>10.4f}{YT[k][2]:>10.4f}")
print(f"yapisiz kumede secilen k -> siluet {secim(YT)[0]}, sacilma {secim(YT)[1]}, "
      f"bosluk {secim(YT)[2]}")
print(f"en yuksek siluet: veri {VT[secim(VT)[0]][0]:.4f}, yapisiz {YT[secim(YT)[0]][0]:.4f}, "
      f"fark {VT[secim(VT)[0]][0] - YT[secim(YT)[0]][0]:+.4f}")

   k    siluet   sacilma    bosluk
   2    0.1169    2.6101   -0.0336
   3    0.1093    2.3145   -0.0405
   4    0.1136    2.0117   -0.0374
   5    0.1151    1.8629   -0.0408
   6    0.1142    1.8107   -0.0388
   7    0.1252    1.6415   -0.0360
   8    0.1135    1.7448   -0.0417
   9    0.1255    1.6649   -0.0301
  10    0.1201    1.6989   -0.0331
yapisiz kumede secilen k -> siluet 9, sacilma 7, bosluk 9
en yuksek siluet: veri 0.2142, yapisiz 0.1255, fark +0.0887

Bu bulutta hiçbir küme yoktur. Altı sütun birbirinden bağımsız üretildi, tek bir yoğunlaşma bölgesi yok. Yine de üç ölçüt üç yanıt veriyor: 9, 7 ve 9. Hiçbiri “yapı yok” demiyor, çünkü hiçbirinin böyle bir çıktısı yok — her ölçüt kendisine verilen adaylar arasından en iyisini işaret etmek zorunda.

Değerler karşılaştırıldığında durum daha da rahatsız edicidir. Yapısız bulutta en yüksek siluet 0,1255, gerçek veride 0,2142; fark 0,0887, oran yaklaşık 1,7 kat. Bu, sıfırdan farklı bir yapı olduğunu gösterir ama tek başına okunan bir 0,21 değerinin “belirgin kümeler” anlamına gelmediğini de gösterir. Boşluk ölçütünün yapısız bulutta -0,0301 ile -0,0417 arasında kalması beklenendir: yapısız veri başvuru bulutlarından ayrışmıyor. Aynı ölçütün gerçek veride de negatif kalması ayrı bir uyarıdır; merkez temelli bölmeleme bu kümede başvuru bulutlarındakinden daha uzun toplam uzaklık bırakıyor.

Etiketin Açılması

Bu kursta buraya kadar hiçbir yöntem etiketi görmedi. Burada, bir kez, açılır. Amaç modeli etiketle eğitmek değil, iç ölçütlerin seçtiği küme sayısının etiketin işaret ettiğiyle uyuşup uyuşmadığını sormaktır. Ölçü uyum göstergesidir: bütün nokta çiftleri gezilir ve bölmelemenin “aynı kümede” yanıtıyla etiketin “aynı sınıfta” yanıtının uyuştuğu çiftler sayılır.

def uyum_gostergesi(e, y):                        # DIS GECERLILIK: cift uyum orani
    n, ayni = len(y), 0
    for i in range(n):
        for j in range(i + 1, n):
            ayni += (e[i] == e[j]) == (y[i] == y[j])
    return ayni / (n * (n - 1) // 2)


def rastgele_atama(n, k, tohum):                  # TABAN CIZGISI: rastgele bolmeleme
    r = uretec(tohum)
    return [int(r() * k) for _ in range(n)]


print(f"etiket: {len(ETIKET)} abonenin {sum(ETIKET)}'i supheli "
      f"({sum(ETIKET) / len(ETIKET):.4f}); etiketin isaret ettigi kume sayisi 2")
print(f"{'k':>4}{'uyum':>10}{'rastgele':>10}{'fark':>9}")
UY = {}
for k in KLER:
    e, _ = bolmele(N, k, TOHUM + 200000 + k)
    UY[k] = (uyum_gostergesi(e, ETIKET),
             uyum_gostergesi(rastgele_atama(len(ETIKET), k, TOHUM + 900000 + k), ETIKET))
    print(f"{k:>4}{UY[k][0]:>10.4f}{UY[k][1]:>10.4f}{UY[k][0] - UY[k][1]:>+9.4f}")
TEK = uyum_gostergesi([0] * len(ETIKET), ETIKET)
en = max(UY, key=lambda k: UY[k][0])
print(f"tek kume tabani {TEK:.4f}; bunu gecen bolmeleme "
      f"{sum(1 for k in KLER if UY[k][0] > TEK)}/{len(KLER)}")
print(f"uyumu en yuksek bolmeleme k={en} ({UY[en][0]:.4f}), tek kume tabaninin "
      f"{UY[en][0] - TEK:+.4f} altinda")
print(f"ic olcutlerin sectigi k {list(secim(VT))}; etiketin isaret ettigi k 2")

etiket: 756 abonenin 168'i supheli (0.2222); etiketin isaret ettigi kume sayisi 2
   k      uyum  rastgele     fark
   2    0.5235    0.4996  +0.0239
   3    0.4690    0.4484  +0.0206
   4    0.4290    0.4225  +0.0065
   5    0.4195    0.4073  +0.0121
   6    0.4209    0.3967  +0.0241
   7    0.4051    0.3898  +0.0153
   8    0.4044    0.3840  +0.0204
   9    0.3936    0.3804  +0.0132
  10    0.3843    0.3778  +0.0065
tek kume tabani 0.6539; bunu gecen bolmeleme 0/9
uyumu en yuksek bolmeleme k=2 (0.5235), tek kume tabaninin -0.1304 altinda
ic olcutlerin sectigi k [3, 6, 10]; etiketin isaret ettigi k 2

Etiket iki sınıflıdır: 756 abonenin 168’i şüpheli, oran 0,2222. Dolayısıyla etiketin işaret ettiği küme sayısı 2’dir. İç ölçütlerin seçtikleri 3, 6 ve 10; hiçbiri 2 demedi.

Rastgele bölmeleme tabanına göre fark her küme sayısında pozitif ama küçük: en büyüğü 0,0241. Bölmeleme, etiketle rastgeleden biraz fazla uyuşuyor. Asıl sayı ikinci tabandadır. Herkesi tek kümeye koyan yordam 0,6539 alıyor ve dokuz bölmelemenin dokuzu da bunun altında kalıyor; en iyisi 0,1304 geride. Sebep etiketin dengesizliğidir: şüpheli oranı 0,2222 olduğunda rastgele seçilen iki abonenin aynı sınıfta olma olasılığı zaten yüksektir ve “hepsi aynı” demek bu çiftlerin tamamını doğru bilir.

Buradan çıkan sonuç kümelemenin işe yaramadığı değil, etiketi bulmadığıdır — ki bulması için bir sebep de yoktu, çünkü hiçbir yöntem etiketi görmedi. Kümeler tüketim düzeyine, oynaklığa ve hane büyüklüğüne göre ayrıştı; şüphe etiketi bu eksenlerin hiçbiriyle örtüşmüyor. Denetimsiz bir sonucu dış etikete göre ölçmek, çoğu zaman kümelemenin başarısını değil etiketin veride görünür olup olmadığını ölçer.

Özet

• Üç iç geçerlilik ölçütü aynı veride üç ayrı küme sayısı seçiyor: siluet katsayısı 3, saçılma oranı 6, boşluk ölçütü 10. Değişen tek şey “iyi bölmeleme” tanımıdır.
• Boşluk ölçütü tepe yapmıyor, denenen aralığın son adayını seçiyor; yanıtı veriden değil süpürmenin nerede kesildiğinden geliyor. Yirmi yedi karşılaştırmadan en iyisi alındı.
• Hiçbir yapı taşımayan bir bulutta aynı üç ölçüt yine bir küme sayısı seçiyor (9, 7 ve 9); en yüksek siluet orada 0,1255, gerçek veride 0,2142, fark 0,0887.
• Etiket kursta ilk ve tek kez açıldı: uyum göstergesi en iyi bölmelemede 0,5235, rastgele bölmeleme tabanının 0,0239 üstünde ama tek küme tabanının (0,6539) 0,1304 altında; dokuz bölmelemenin dokuzu da bu tabanın altında.
• İç ölçütlerin seçtiği küme sayıları (3, 6, 10) etiketin işaret ettiğiyle (2) uyuşmuyor; denetimsiz bir sonucu dış etiketle ölçmek kümelemenin değil, etiketin veride görünürlüğünün ölçüsüdür.

Sonraki Adım

Altı derste noktalar gruplandı ve her grup bir taban çizgisiyle yan yana okundu. Yöntemler birbirinden çok ayrıldı — merkez, bağlantı, yoğunluk, karışım — ama bir şeyi paylaştılar: hepsi bir noktanın bütün sütunlarına birden baktı ve iki nokta arasındaki uzaklığı bu sütunların toplamından okudu. Sütun sayısı arttıkça uzaklığın kendisinin ne olduğu hiçbir yerde sorulmadı; altı sütunla üç yüz sütunun aynı işlemi aynı anlamda ürettiği varsayıldı. Oysa sütun sayısı büyüdükçe uzaklıklar birbirine yaklaşır ve “en yakın” sözcüğü anlamını yitirir. Sonraki konu bu soruyla açılır: noktaları daha az sayıyla göstermek mümkün müdür, ve bu gösterimde ne kaybedilir. Ölçü artık bölmeleme değil geri kurma hatasıdır — az sayıdan yeniden kurulan noktalar özgün yerlerinden ne kadar uzakta kalıyor.