k-Ortalamalar

Önceki ders yordamı bilerek dondurmuştu: çekirdekler tek bir kuralla seçildi, iki düzeltme turu yapıldı, küme sayısı 4’te tutuldu. Değişen tek şey benzerlik tanımıydı. Bu ders tanımı sabitler — standart puan ile kare uzaklık — ve dondurulan üç sabitten ikisini serbest bırakır: yineleme durana kadar sürdürülür, çekirdekler rastgele seçilir.

Ortaya çıkan yordam kısadır: her nokta en yakın merkeze atanır, her merkez kendi kümesinin ortalamasına taşınır, değişiklik kalmayana kadar yinelenir. Ders bunun iki ayrı yerde karar ürettiğini ölçer. Birincisi başlangıçtır: aynı küme sayısıyla farklı çekirdeklerden koşulduğunda kaç ayrı bölmeleme çıkıyor. İkincisi küme sayısının kendisidir; k dışarıdan verilen bir ayar değişkenidir ve seçimi bir aramadır.

• KU9. Küme, sütunlar, bölme ve ölçü önceki dersteki gibidir: kurgu abone tablosu, tohum 20260218, eğitim kümesindeki 756 abone, altı sayısal sütun, standart puan, kare uzaklık. Etiket yine üretilmez.
• KU10. Ölçü yine küme içi toplam uzaklıktır, nokta başına, küçük iyidir.
• KU11. Taban çizgisi rastgele atamadır ve her k için ayrı hesaplanır; taban küme sayısıyla değiştiği için tek bir sayı bütün tabloya yazılamaz.
• KU12. Çekirdekler kümedeki ayrı noktalardan seçilir; boş kalan bir küme olursa merkezi yerinde bırakılır.
• KU13. Yineleme, atama iki tur üst üste değişmediğinde durur; üst sınır 60 turdur ve hiçbir koşum bu sınıra dayanmaz. Kayan noktalı sayı == ile karşılaştırılmaz — durma ölçütü atama listesinin eşitliğidir, yani tam sayı karşılaştırmasıdır.
• KU14. İki bölmelemenin farkı, önceki derste kurulan ayrışan nokta çifti oranıyla ölçülür.
• KU15. Küme sayısı süpürmesinde her k için 12 başlangıç denenir ve en iyisi alınır; denenen aday sayısı yazılır. Bildirilen sayı arama bütçesinin de bir işlevidir.

Yinelemenin Durduğu Yer

Yordam iki adımın dönüşümlü tekrarıdır ve her adım ölçüyü ayrı bir yönden düşürür. Atama adımı merkezleri sabit tutup her noktayı en yakınına verir. Güncelleme adımı atamayı sabit tutup her merkezi kendi kümesinin ortalamasına taşır; kare uzaklık toplamını en küçüğe indiren nokta ortalama olduğu için bu adım da ölçüyü düşürür ya da aynı bırakır. Ölçü hiç artmadığı ve aşağıdan sınırlı olduğu için yineleme durmak zorundadır. Durduğu yer hakkında ise bu akıl yürütme hiçbir şey söylemez.

# k_ortalamalar.py — MODELDIR. 01. dersin KURGU kumesi ve standart puan tanimi
# ayni tohumla yeniden kurulur; etiket yine uretilmez.
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


VERI = []
for i in range(HAM):
    r = uretec(TOHUM + i)
    temel = BOLGE[ayrik(r(), [x[0] for x in BOLGE])][1]
    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:
        continue
    r, v = uretec(TOHUM + 17001 + i), []
    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(
            temel * math.exp((r() + r() + r() - 1.5) * 0.62)
            * (1 - d * 0.05) * 100 + 0.5) / 100)
        r()
    if v:
        x = {"ort_tuketim": round(sum(v) / len(v), 2), "oynaklik": round(max(v) - min(v), 2),
             "hane": hane, "memnuniyet": memnun, "donem": len(v)}
        x["kisi_basi"] = round(x["ort_tuketim"] / hane, 3)
        VERI.append(x)

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


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]
HAM_V = [[x[a] for a in ALAN] for x in EGT]
ORT = [statistics.fmean(c) for c in zip(*HAM_V)]
SAP = [statistics.pstdev(c) for c in zip(*HAM_V)]
V = [[(v[j] - ORT[j]) / SAP[j] for j in range(len(ALAN))] for v in HAM_V]
N = len(V)

kare = lambda a, b: sum((p - q) * (p - q) for p, q in zip(a, b))
merkez = lambda g: [statistics.fmean(c) for c in zip(*g)]


def ic_uzaklik(atama, k):                   # kume ici toplam uzaklik, nokta basina
    t = 0.0
    for c in range(k):
        g = [V[i] for i in range(N) if atama[i] == c]
        if g:
            t += sum(kare(v, merkez(g)) for v in g)
    return t / N


def cekirdek(r, k):                         # k ayri noktayi baslangic merkezi sec
    s = []
    while len(s) < k:
        j = int(r() * N)
        if j not in s:
            s.append(j)
    return [V[j] for j in s]


def k_ortalamalar(M, ust=60):               # MODELDIR: ata, merkezleri guncelle, yinele
    k, onceki = len(M), None
    for tur in range(1, ust + 1):
        a = [min(range(k), key=lambda c: kare(v, M[c])) for v in V]
        if a == onceki:
            return a, tur
        onceki = a
        M = [merkez([V[i] for i in range(N) if a[i] == c]) or M[c] for c in range(k)]
    return a, ust


r = uretec(TOHUM + 5100)
M0 = cekirdek(r, 4)
print("tek bir baslangictan yakinsama izi (k = 4)")
for tur in range(1, 9):
    a = [min(range(4), key=lambda c: kare(v, M0[c])) for v in V]
    print(f"  tur {tur}  kume ici toplam uzaklik {ic_uzaklik(a, 4):.4f}"
          f"  kume boylari {sorted(a.count(c) for c in range(4))}")
    M0 = [merkez([V[i] for i in range(N) if a[i] == c]) or M0[c] for c in range(4)]

tek bir baslangictan yakinsama izi (k = 4)
  tur 1  kume ici toplam uzaklik 4.2484  kume boylari [109, 159, 233, 255]
  tur 2  kume ici toplam uzaklik 3.9366  kume boylari [148, 166, 213, 229]
  tur 3  kume ici toplam uzaklik 3.7729  kume boylari [153, 180, 198, 225]
  tur 4  kume ici toplam uzaklik 3.6519  kume boylari [145, 175, 201, 235]
  tur 5  kume ici toplam uzaklik 3.6125  kume boylari [140, 170, 215, 231]
  tur 6  kume ici toplam uzaklik 3.6058  kume boylari [137, 172, 221, 226]
  tur 7  kume ici toplam uzaklik 3.6050  kume boylari [138, 171, 222, 225]
  tur 8  kume ici toplam uzaklik 3.6049  kume boylari [138, 170, 223, 225]

İlk turda 4,2484 olan sayı sekizinci turda 3,6049’a iniyor ve düşüş hızla yavaşlıyor: ilk üç tur toplam 0,4755 kazandırırken son üç tur 0,0076 kazandırıyor. Küme boyları da yerine oturuyor, ilk turdaki 109–255 aralığı 138–225’e daralıyor. Önceki dersin iki düzeltme turlu yordamı 3,8910’da kesilmişti; burada üçüncü tur bile onun altına iniyor.

Bu izin söylemediği şey daha önemlidir. Sayının düşüp durması, durduğu yerin elde edilebilecek en düşük sayı olduğunu göstermez. Her tur bir önceki bölmelemeye komşu bölmelemeleri deniyor; hiçbir tur uzaktaki bir yerleşimi denemiyor. Yordam bu yüzden başladığı yere yakın bir çözümde durur.

Aynı k, Farklı Başlangıç

Başlangıcın ne kadar belirleyici olduğu, aynı küme sayısıyla otuz farklı çekirdek kümesinden koşularak ölçülür. Bir bölmelemenin kimliği, küme numaralarından bağımsız olarak, hangi noktaların birlikte durduğudur.

def olcut(a, k):                            # bolmelemenin etiketten bagimsiz kimligi
    return frozenset(frozenset(i for i in range(N) if a[i] == c) for c in range(k))


def uyusmazlik(a, b):                       # iki bolmeleme kac nokta ciftinde ayrisiyor
    ayrisan = sum((a[i] == a[j]) != (b[i] == b[j])
                  for i in range(N) for j in range(i + 1, N))
    return 2 * ayrisan / (N * (N - 1))


r, KOSUM = uretec(TOHUM + 7700), 30
SONUC = []
for s in range(KOSUM):
    a, tur = k_ortalamalar(cekirdek(r, 4))
    SONUC.append((ic_uzaklik(a, 4), tur, a))
SONUC.sort(key=lambda x: x[0])
AYRI = {olcut(a, 4) for _, _, a in SONUC}
print(f"{KOSUM} rastgele baslangic, k = 4 -> ayri bolmeleme {len(AYRI)}")
print("  siralanmis kume ici toplam uzakliklar")
for b in range(0, KOSUM, 10):
    print("   " + " ".join(f"{u:.4f}" for u, _, _ in SONUC[b:b + 10]))
print(f"  en iyi {SONUC[0][0]:.4f}, ortanca {SONUC[KOSUM // 2][0]:.4f}, "
      f"en kotu {SONUC[-1][0]:.4f}, aralik {SONUC[-1][0] - SONUC[0][0]:.4f}")
print(f"  yakinsama turu en az {min(t for _, t, _ in SONUC)}, "
      f"en cok {max(t for _, t, _ in SONUC)}")
print(f"  01. dersin tek gecisli yordami 3.8910 vermisti; iyilesme "
      f"{3.8910 - SONUC[0][0]:.4f}")
print(f"  en iyi - ikinci en iyi: sayi farki {SONUC[1][0] - SONUC[0][0]:.6f}, "
      f"ayrisan nokta cifti {uyusmazlik(SONUC[0][2], SONUC[1][2]):.4f}")
print(f"  en iyi - en kotu:       sayi farki {SONUC[-1][0] - SONUC[0][0]:.4f}, "
      f"ayrisan nokta cifti {uyusmazlik(SONUC[0][2], SONUC[-1][2]):.4f}")

30 rastgele baslangic, k = 4 -> ayri bolmeleme 26
  siralanmis kume ici toplam uzakliklar
   3.5649 3.5649 3.5656 3.5656 3.5656 3.5658 3.5711 3.5711 3.5711 3.5711
   3.5711 3.5712 3.5712 3.5727 3.5903 3.5906 3.5936 3.5936 3.5941 3.5955
   3.5956 3.5957 3.5981 3.5995 3.6026 3.6077 3.6165 3.7467 3.7744 3.7763
  en iyi 3.5649, ortanca 3.5906, en kotu 3.7763, aralik 0.2115
  yakinsama turu en az 11, en cok 52
  01. dersin tek gecisli yordami 3.8910 vermisti; iyilesme 0.3261
  en iyi - ikinci en iyi: sayi farki 0.000028, ayrisan nokta cifti 0.0037
  en iyi - en kotu:       sayi farki 0.2115, ayrisan nokta cifti 0.2844

Otuz koşum 26 ayrı bölmeleme verdi. Aynı veri, aynı yordam, aynı küme sayısı; değişen tek şey başlangıç noktaları. Sayılar dar bir bantta duruyor — 3,5649 ile 3,7763 arası — ve otuz koşumun yirmi yedisi 3,62’nin altında. Rastgele atama tabanı bu küme sayısında 5,9730 olduğuna göre koşumların hepsi tabanı geniş farkla geçiyor; en kötüsü bile tabanın 2,1967 altında.

Alt iki satır dersin asıl bulgusudur. En iyi iki koşumun sayıları arasındaki fark 0,000028, yani dört ondalıkta aynı sayı; buna karşılık iki bölmeleme nokta çiftlerinin 0,0037’sinde ayrışıyor. En iyi ile en kötü koşum arasında sayı farkı 0,2115, ayrışma 0,2844 — çiftlerin dörtte birinden fazlası. Küme içi toplam uzaklık bir bölmelemeyi tek bir sayıya indirir ve o sayının aynı kalmasıyla korunan şey, kimin kiminle aynı kümede olduğu değildir.

Yakınsama turu 11 ile 52 arasında değişiyor ve hiçbir koşum 60 turluk sınıra dayanmıyor. Yineleme gerçekten duruyor, ama nerede durduğu çekirdeklerin nereye düştüğüne bağlı.

Küme Sayısı Bir Ayar Değişkeni

k modelin veriden öğrendiği bir şey değil, dışarıdan verilen bir sayıdır — M27/K03’ün terimiyle bir ayar değişkeni. Ölçüye bakarak seçmek doğrudan işlemez: küme sayısı arttıkça küme içi toplam uzaklık tek yönde azalır ve en küçük değeri her noktanın kendi kümesi olduğu bölmeleme verir. Okuma bu yüzden sayının kendisinden değil ardışık farklardan yapılır; farkların keskin biçimde küçüldüğü yere dirsek denir.

def rastgele_taban(k, tohum):
    r = uretec(tohum)
    return ic_uzaklik([int(r() * k) for _ in range(N)], k)


BASLANGIC, ADAY, ICUZ = 12, 0, {}
print(f"{'k':>3}{'taban':>9}{'yontem':>9}{'fark':>9}{'ardisik fark':>14}{'dusus orani':>13}")
for k in range(1, 11):
    r = uretec(TOHUM + 8800 + k)
    ICUZ[k] = min(ic_uzaklik(k_ortalamalar(cekirdek(r, k))[0], k) for _ in range(BASLANGIC))
    ADAY += BASLANGIC
    taban = statistics.fmean(rastgele_taban(k, TOHUM + 9900 + 50 * k + t) for t in range(5))
    d = "" if k == 1 else f"{ICUZ[k - 1] - ICUZ[k]:14.4f}"
    o = "" if k == 1 else f"{(ICUZ[k - 1] - ICUZ[k]) / ICUZ[k - 1]:13.3f}"
    print(f"{k:>3}{taban:>9.4f}{ICUZ[k]:>9.4f}{taban - ICUZ[k]:>9.4f}{d}{o}")
print(f"denenen aday {ADAY} kosum ({BASLANGIC} baslangic x 10 kume sayisi)")

FARK = {k: ICUZ[k - 1] - ICUZ[k] for k in range(2, 11)}
kir = max(range(2, 10), key=lambda k: FARK[k] - FARK[k + 1])
esik = min(k for k in range(2, 11) if FARK[k] / ICUZ[k - 1] < 0.10)
egim = (ICUZ[10] - ICUZ[1]) / 9
sapma = {k: (ICUZ[1] + egim * (k - 1)) - ICUZ[k] for k in range(2, 10)}
kiris = max(sapma, key=sapma.get)
ikinci = sorted(sapma, key=sapma.get)[-2]
print("\ndirsegin uc ayri okumasi")
print(f"  ardisik farkin en cok azaldigi k      {kir}")
print(f"  dusus orani ilk kez 0.10'un altina indigi k  {esik}")
print(f"  uc noktayi birlestiren kirise en uzak k      {kiris}"
      f"   (sapma {sapma[kiris]:.4f}; ikincisi k = {ikinci}, sapma {sapma[ikinci]:.4f})")
print(f"  ardisik farklar tek yonlu degil: k = 9'da {FARK[9]:.4f}, k = 10'da {FARK[10]:.4f}")

  k    taban   yontem     fark  ardisik fark  dusus orani
  1   6.0000   6.0000   0.0000
  2   5.9928   4.8521   1.1407        1.1479        0.191
  3   5.9894   3.9996   1.9897        0.8524        0.176
  4   5.9730   3.5655   2.4075        0.4342        0.109
  5   5.9721   3.2151   2.7570        0.3504        0.098
  6   5.9635   2.8969   3.0666        0.3182        0.099
  7   5.9486   2.6732   3.2754        0.2237        0.077
  8   5.9384   2.5020   3.4365        0.1712        0.064
  9   5.9443   2.3874   3.5568        0.1146        0.046
 10   5.9181   2.2570   3.6611        0.1304        0.055
denenen aday 120 kosum (12 baslangic x 10 kume sayisi)

dirsegin uc ayri okumasi
  ardisik farkin en cok azaldigi k      3
  dusus orani ilk kez 0.10'un altina indigi k  5
  uc noktayi birlestiren kirise en uzak k      4   (sapma 1.1869; ikincisi k = 3, sapma 1.1686)
  ardisik farklar tek yonlu degil: k = 9'da 0.1146, k = 10'da 0.1304

Taban sütunu tek başına bir uyarıdır. Rastgele atamanın sayısı da k büyüdükçe düşüyor: 6,0000’dan 5,9181’e. Düşüş küçüktür ama gerçektir, çünkü her yeni küme kendi merkezini kendi noktalarından kestirir ve kestirim gürültüsü ölçüyü aşağı çeker. Öğrenmeyen bir yordamın sayısı bile k arttıkça iyileşiyorsa, yöntemin düşüşünün tamamı yapıya bağlanamaz. Fark sütunu bu yüzden gereklidir.

Dirsek ise tablodan tek bir yanıt vermiyor. Aynı on satır üzerinde üç yaygın okuma denendi ve üçü üç ayrı küme sayısı seçti: ardışık farkın en çok azaldığı yer k = 3, düşüş oranının ilk kez 0,10’un altına indiği yer k = 5, uç noktaları birleştiren kirişe en uzak nokta k = 4. Üçüncüsünde kazananın sapması 1,1869, ikincisininki 1,1686 — aradaki fark yüzde ikiden az. Son satır tabloyu büsbütün kapatıyor: ardışık farklar tek yönlü bile değil, k = 9’da 0,1146 iken k = 10’da 0,1304’e çıkıyor.

Denenen aday sayısı 120 koşumdur ve bu sayı bildirilen her hücrenin yanında durur. k = 4 satırındaki 3,5655, on iki başlangıcın en iyisidir; otuz başlangıçla yapılan arama aynı k için 3,5649 bulmuştu. Aradaki 0,0006 veriden değil arama bütçesinden gelir.

Özet

• Yordam iki adımın dönüşümlü tekrarıdır ve her adım ölçüyü düşürür ya da aynı bırakır; yineleme bu yüzden durmak zorundadır, ama durduğu yerin en iyi olduğu güvence altında değildir.
• Otuz rastgele başlangıç k = 4’te 26 ayrı bölmeleme verdi; sayılar 3,5649 ile 3,7763 arasında, yakınsama 11 ile 52 tur arasında değişti.
• Sayı farkı ile bölmeleme farkı aynı şey değildir: dört ondalıkta aynı sayıyı veren iki koşum nokta çiftlerinin 0,0037’sinde, en iyi ile en kötü koşum 0,2844’ünde ayrışıyor.
• Rastgele atama tabanı da küme sayısıyla düşer, 6,0000’dan 5,9181’e; yöntemin farkı bu taban çıkarıldıktan sonra 2,4075’ten 3,6611’e çıkar.
• Dirseğin üç ayrı okuması üç ayrı küme sayısı seçti — 3, 5 ve 4 — ve ardışık farklar tek yönlü bile değil; seçilen sayı 120 koşumluk bir arama bütçesinin sonucudur.

Sonraki Adım

Bu yordamın iki kısıtı birbirine bağlıdır: küme sayısı başlamadan önce verilmek zorundadır ve her koşum tek bir bölmeleme üretir. k = 3, k = 4 ve k = 5 için üç ayrı arama yapıldı ve üç sonuç birbiriyle ilişkisiz çıktı — k = 3’ün kümeleri k = 5’in kümelerinin birleşimleri değil. Sonraki ders sırayı tersine çeviren bir aileyi alır: her nokta kendi kümesiyle başlar, en yakın iki küme birleştirilir ve tek kümeye kadar iç içe geçmiş bir küme ailesi üretilir. Küme sayısı burada girdi değil, ağacın hangi yükseklikten kesildiği sorusunun yanıtıdır. Buna karşılık yeni bir karar belirir: “en yakın iki küme” ifadesi nokta uzaklığından türetilemez, kümeler arası uzaklık ayrıca tanımlanmalıdır. Ders üç bağlantı ölçütünün aynı veride kaç noktada ayrıştığını sayar ve ağaç şemasını metin olarak basar.