Doğrusal Olmayan Gömme

İki derste izdüşüm hep aynı biçimdeydi: her yeni sayı, eski sütunların ağırlıklı toplamıydı. Bu kısıt hatayı hesaplanabilir kıldı ve tekil değerlerden okunmasını sağladı. Bedeli de vardı — ağırlıklı toplam düz bir alt uzaya izdüşürür ve noktalar düz bir alt uzayda durmuyorsa o düzlem onları takip edemez. Kıvrılmış bir yüzey üzerinde birbirine yakın duran iki nokta, yüzeyi düzleme bastıran bir izdüşümde birbirinden uzağa düşebilir.

Bu dersin ele aldığı yaklaşımlar o kısıtı kaldırır. Ortak yanları şudur: uzaklıkları değil komşulukları hedeflerler. Her noktanın kimlere yakın olduğu özgün uzayda bir kez saptanır, sonra düşük boyutlu bir uzayda o komşuluk ilişkisini olabildiğince yeniden kuran bir yerleşim aranır. Aile içinde onlarca ayrı yordam vardır ve ayrıntılarda ayrışırlar; burada ortak çekirdek yazılır ve ölçülür. Ölçü de değişmek zorundadır, çünkü geri kurma hatası burada tanımsızdır: gömmeden özgün uzaya geri dönen bir yol yoktur. Sorulacak soru şudur — özgün uzayda en yakın k komşunun kaçı gömmede de komşu kalıyor.

• BA17. Ölçülen küme sınama kümesidir: 252 nokta, 12 ölçeklenmiş sütun. Ölçek yine yalnız eğitim kümesinden okunur.
• BA18. Komşuluk korunma oranı, her noktanın özgün uzaydaki en yakın $k$ komşusundan kaçının gömmedeki en yakın $k$ komşusu arasında da bulunduğunun, bütün noktalar üzerinden ortalamasıdır. $k = 10$ alınmıştır.
• BA19. Taban çizgisi rastgele yerleşimdir: 252 nokta düzleme rastgele serpilir. Beklenen değeri $k / (N-1)$’dir ve üç çekiliş ortalanır. Bu taban seçilmiştir çünkü öğrenmeyen bir yerleşimin komşuluk korumasını doğrudan verir.
• BA20. İkinci karşılaştırma doğrusal izdüşümdür: ilk dersin bileşen yönlerinden ilk iki ve ilk üçü. Aynı boyut sayısında karşılaştırma yapılabilsin diye iki boyut esas alınır.
• BA21. Yerleşim ders içinde yazılır ve modeldir: rastgele başlatılır, her adımda komşular birbirine çekilir ve rastgele seçilen komşu olmayan noktalar itilir, adım boyu doğrusal olarak sıfıra iner. Kitaplık çağrılmaz.
• BA22. İtme için nokta başına 10 rastgele örnek çekilir. Bütün çiftler taransaydı maliyet nokta sayısının karesiyle büyürdü.
• BA23. Ayar bütçesi altı adaydır: iki adım sayısı ile üç adım boyu. Denenen adayların hepsi basılır.
• BA24. Seçim ölçülen sayının kendisiyle yapılır ve ayrı bir küme kullanılmaz. Bu, sayının bir kısmını ölçütün kendisinden aldığı anlamına gelir; altı adayın aralığı bu yüzden basılır.
• BA25. Gömmenin birimi yoktur. Uzaklık karşılaştırmalarında gömme, ortalama ikili uzaklığı özgün uzayınkine eşitlenecek biçimde ölçeklenir; yoksa karşılaştırma ölçek seçimini ölçerdi.
• BA26. Aynı ayarla iki ayrı başlangıçtan iki koşum yapılır. Başlangıç duyarlılığı ölçünün parçasıdır.

Komşuluk Korunma Oranı ve Tabanı

Ölçü iki kümenin kesişimidir. Bir nokta için özgün uzaydaki en yakın on komşu bir küme, gömmedeki en yakın on komşu ikinci bir kümedir; kesişimin büyüklüğü ona bölünür ve bütün noktalar üzerinden ortalanır. Rastgele bir yerleşimde beklenen değer, on komşunun 251 aday arasından rastgele seçilmesi kadardır.

# ORTAK — MODELDIR. M27/K01'in KURGU abone tablosu ayni tohumla yeniden uretilir.
# Etiket sutunu bu kursta hic uretilmez.
import math

TOHUM, HAM, M32 = 20260218, 1400, 0xFFFFFFFF
BOLGE = [("kuzey", 0.28, 21), ("guney", 0.22, 17), ("dogu", 0.18, 26),
         ("bati", 0.14, 14), ("merkez", 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[1] 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({"no": 10001 + i, "bolge": b, "hane": hane, "memnuniyet": memnun})
for k in ABONE:
    r, v = uretec(TOHUM + 7000 + k["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(
            k["bolge"][2] * math.exp((r() + r() + r() - 1.5) * 0.62)
            * (1 - d * 0.05) * 100 + 0.5) / 100)
        r()
    if not v:
        continue
    ort = sum(v) / len(v)
    x = {"hane": k["hane"], "memnuniyet": k["memnuniyet"], "donem": len(v),
         "ort_tuketim": round(ort, 2), "oynaklik": round(max(v) - min(v), 2),
         "sifir_okuma": int(min(v) == 0.0), "kisi_basi": round(ort / k["hane"], 3)}
    for b in BOLGE:
        x["b_" + b[0]] = int(k["bolge"][0] == b[0])
    VERI.append(x)

ALAN = ["ort_tuketim", "oynaklik", "kisi_basi", "hane", "memnuniyet", "donem",
        "sifir_okuma", "b_kuzey", "b_guney", "b_dogu", "b_bati", "b_merkez"]
r, s = uretec(TOHUM + 90000), 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]
K = [VERI[i] for i in s]
EGT, SIN = K[:756], K[1008:]

n = len(ALAN)
ORT = {a: sum(x[a] for x in EGT) / len(EGT) for a in ALAN}
SAC = {a: max(1e-9, (sum((x[a] - ORT[a]) ** 2 for x in EGT) / len(EGT)) ** 0.5)
       for a in ALAN}
ZE = [[(x[a] - ORT[a]) / SAC[a] for a in ALAN] for x in EGT]
Z = [[(x[a] - ORT[a]) / SAC[a] for a in ALAN] for x in SIN]
N = len(Z)

def carp(m, v):
    return [sum(m[i][j] * v[j] for j in range(len(v))) for i in range(len(m))]


def diklestir(v, B):
    for u in B:
        c = sum(v[i] * u[i] for i in range(len(v)))
        v = [v[i] - c * u[i] for i in range(len(v))]
    return v


def yonleri_bul(Y):
    C = [[sum(z[i] * z[j] for z in Y) / len(Y) for j in range(n)] for i in range(n)]
    B = []
    for _ in range(n):
        v, lam = [1.0 / (i + 1) for i in range(n)], 0.0
        for _ in range(200):
            w = diklestir(carp(C, v), B)
            u = sum(q * q for q in w) ** 0.5
            if u < 1e-9:
                break
            v, lam = [q / u for q in w], u
        if lam < 1e-9:
            break
        B.append(v)
    return B


BILESEN, KOM = yonleri_bul(ZE), 10


def uzaklik(P, a, b):
    return sum((P[a][i] - P[b][i]) ** 2 for i in range(len(P[a]))) ** 0.5


def en_yakinlar(P, k):
    return [{b for _, b in sorted((uzaklik(P, a, b), b)
                                  for b in range(len(P)) if b != a)[:k]}
            for a in range(len(P))]


KOMSU = en_yakinlar(Z, KOM)


def korunma(P, k=KOM):
    q = en_yakinlar(P, k)
    return sum(len(KOMSU[a] & q[a]) for a in range(N)) / (N * k)


def izdusum(d):
    return [[sum(z[j] * BILESEN[i][j] for j in range(n)) for i in range(d)] for z in Z]


def rastgele_yerlesim(tohum, d=2):
    r = uretec(tohum)
    return [[r() * 2 - 1 for _ in range(d)] for _ in range(N)]


rs = sum(korunma(rastgele_yerlesim(TOHUM + 7 * (t + 1))) for t in range(3)) / 3
print(f"nokta {N}, sutun {n}, komsu sayisi {KOM}")
print(f"taban: rastgele yerlesim {rs:.4f} (beklenen {KOM / (N - 1):.4f})")
print(f"dogrusal izdusum 2 boyut {korunma(izdusum(2)):.4f}")
print(f"dogrusal izdusum 3 boyut {korunma(izdusum(3)):.4f}")

nokta 252, sutun 12, komsu sayisi 10
taban: rastgele yerlesim 0.0390 (beklenen 0.0398)
dogrusal izdusum 2 boyut 0.2639
dogrusal izdusum 3 boyut 0.3849

Taban çizgisi 0,0390 ve kuramsal beklentiye, yani 0,0398’e oturuyor. Doğrusal izdüşüm iki boyutta 0,2639 veriyor: tabanın 0,2249 üstünde, ama en yakın on komşunun yalnız dörtte biri. İlk dersin uzaklık tablosunda iki bileşenin ikili uzaklıkların ortalamasını 0,4965 katına indirdiği görülmüştü; bu satır aynı kaybın komşuluk cinsinden karşılığıdır. Uzaklıklar orantılı olarak kısalmıyor, sıralamaları da bozuluyor.

Komşuluğu Hedefleyen Bir Yerleşim

Yordam üç parçadır. Her nokta için özgün uzaydaki en yakın on komşu bir kez saptanır. Düzlemde rastgele bir yerleşim başlatılır. Sonra her adımda iki kuvvet uygulanır: komşular birbirine çekilir, komşu olmayan rastgele seçilmiş noktalar itilir. İtme kuvveti uzaklıkla azalır, böylece zaten uzak duran çiftler birbirini sonsuza itmez. Adım boyu doğrusal olarak sıfıra iner.

def gom(tohum, adim, eta, k=KOM, neg=10):
    # MODELDIR: komsuluk koruyan yerlesim kucuk olcekte, standart kitaplikla yazilir.
    r = uretec(tohum)
    Y = [[(r() - 0.5) * 0.1 for _ in range(2)] for _ in range(N)]
    kl = [sorted(KOMSU[a]) for a in range(N)]
    for it in range(adim):
        h = eta * (1 - it / adim)
        for a in range(N):
            gx = gy = 0.0
            for b in kl[a]:
                gx += Y[a][0] - Y[b][0]
                gy += Y[a][1] - Y[b][1]
            for _ in range(neg):
                c = int(r() * N)
                if c == a or c in KOMSU[a]:
                    continue
                dx, dy = Y[a][0] - Y[c][0], Y[a][1] - Y[c][1]
                w = 1.0 / (1.0 + dx * dx + dy * dy)
                gx -= w * dx
                gy -= w * dy
            Y[a][0] -= h * gx / k
            Y[a][1] -= h * gy / k
    return Y


print(f"{'adim':>5} {'adim boyu':>10} {'korunma':>9}")
en = None
for adim in (200, 400):
    for eta in (0.05, 0.10, 0.20):
        d = korunma(gom(TOHUM + 11, adim, eta))
        print(f"{adim:>5} {eta:>10.2f} {d:>9.4f}")
        if en is None or d > en[0]:
            en = (d, adim, eta)
print(f"denenen aday 6, secilen adim {en[1]}, adim boyu {en[2]:.2f}")
GOMME = gom(TOHUM + 11, en[1], en[2])
IKINCI = gom(TOHUM + 22, en[1], en[2])
print(f"gomme {korunma(GOMME):.4f}, ayni ayarla ikinci kosum {korunma(IKINCI):.4f}")

 adim  adim boyu   korunma
  200       0.05    0.4099
  200       0.10    0.4869
  200       0.20    0.4286
  400       0.05    0.5032
  400       0.10    0.4377
  400       0.20    0.3940
denenen aday 6, secilen adim 400, adim boyu 0.05
gomme 0.5032, ayni ayarla ikinci kosum 0.4806

Üç sayı yan yana duruyor. Taban 0,0390, doğrusal izdüşüm 0,2639, gömme 0,5032. Gömmenin doğrusal izdüşümden farkı 0,2393 ve bu fark tabandan doğrusal izdüşüme olan farkla (0,2249) hemen hemen aynı büyüklükte. Aynı iki boyutta, komşuluğu hedeflemek komşuluğu iki katına çıkarıyor.

Farkın nereden geldiği ayar tablosunda okunur. Altı adayın en iyisi 0,5032, en kötüsü 0,3940. En kötü aday bile doğrusal izdüşümü 0,1301 geçiyor, dolayısıyla üstünlük ayar seçiminden gelmiyor. Ama seçilen sayı ölçülen sayının kendisiyle seçildiği için 0,5032 bir üst sınırdır; dürüst aralık 0,3940 ile 0,5032’dir. Başlangıç duyarlılığı da aynı yöne işaret ediyor: aynı ayarla ikinci koşum 0,4806 veriyor. Gömme, kümelemede olduğu gibi, tek bir sayı değil bir sayı aralığı üretir.

Gömmedeki Mesafe Neyi Söyler

Komşuluk korunma oranının yüksek olması gömmenin uzaklıkları koruduğu anlamına gelmez. İkisi ayrı sorulardır ve gömme yalnız birincisine yanıt verir. Bunu ölçmenin iki yolu var: gömme en uzak çiftleri de koruyor mu, ve gömmede aynı uzaklıkta duran çiftlerin özgün uzaklıkları ne kadar dağınık.

def en_uzaklar(P, k):
    return [{b for _, b in sorted((-uzaklik(P, a, b), b)
                                  for b in range(len(P)) if b != a)[:k]}
            for a in range(len(P))]


UZAK = en_uzaklar(Z, KOM)


def ortalama_uzaklik(P):
    return sum(uzaklik(P, a, b) for a in range(N)
               for b in range(a + 1, N)) / (N * (N - 1) / 2)


OZ = ortalama_uzaklik(Z)
print(f"ozgun ortalama ikili uzaklik {OZ:.3f}")
for ad, P in (("dogrusal 2", izdusum(2)), ("gomme", GOMME), ("ikinci kosum", IKINCI)):
    q = en_uzaklar(P, KOM)
    uk = sum(len(UZAK[a] & q[a]) for a in range(N)) / (N * KOM)
    f = OZ / ortalama_uzaklik(P)
    Q = [[y * f for y in p] for p in P]
    b = sorted(uzaklik(Z, a, c) for a in range(N) for c in range(a + 1, N)
               if 0.95 * OZ <= uzaklik(Q, a, c) <= 1.05 * OZ)
    print(f"{ad:<13} uzak korunma {uk:.4f}  bant {len(b):>4} cift  ozgun uzaklik "
          f"{b[0]:.2f}-{b[-1]:.2f}  yuzde 10-90 {b[len(b) // 10]:.2f}-"
          f"{b[len(b) * 9 // 10]:.2f}")
f1, f2 = OZ / ortalama_uzaklik(GOMME), OZ / ortalama_uzaklik(IKINCI)
Q1 = [[y * f1 for y in p] for p in GOMME]
Q2 = [[y * f2 for y in p] for p in IKINCI]
s, c, buyuk = 0.0, 0, 0
for a in range(N):
    for b in range(a + 1, N):
        d1, d2 = uzaklik(Q1, a, b), uzaklik(Q2, a, b)
        o = abs(d1 - d2) / max(d1, d2, 1e-9)
        s, c, buyuk = s + o, c + 1, buyuk + (o > 0.5)
print(f"iki kosum arasinda ayni ciftin bagil farki: ortalama {s / c:.4f}, "
      f"yarisindan cok sapan cift orani {buyuk / c:.4f}")

ozgun ortalama ikili uzaklik 4.695
dogrusal 2    uzak korunma 0.6012  bant 1899 cift  ozgun uzaklik 2.87-7.20  yuzde 10-90 3.93-5.74
gomme         uzak korunma 0.0071  bant 2085 cift  ozgun uzaklik 3.47-9.46  yuzde 10-90 4.04-6.79
ikinci kosum  uzak korunma 0.0000  bant 5439 cift  ozgun uzaklik 3.39-9.21  yuzde 10-90 3.97-6.01
iki kosum arasinda ayni ciftin bagil farki: ortalama 0.2906, yarisindan cok sapan cift orani 0.2088

İlk sütun beklenmedik biçimde keskin. Doğrusal izdüşüm en uzak on çiftin 0,6012’sini koruyor; gömme 0,0071’ini, ikinci koşum ise hiçbirini. İki yaklaşım birbirinin tersini koruyor. Doğrusal izdüşüm büyük uzaklıkları taşır çünkü en çok değişkenliği taşıyan yönleri seçmiştir ve uzak çiftleri ayıran şey tam olarak odur; yakın komşuları ise ezer. Gömme yakın komşulukları kurtarır ve karşılığında uzaklığın büyük ölçeğini tümüyle atar. Gömmede iki nokta uzak duruyorsa bu, özgün uzayda uzak oldukları anlamına gelmez — yalnız komşu olmadıkları anlamına gelir.

İkinci ölçüm aynı şeyi tek bir aralıkla söylüyor. Ortalama ikili uzaklık eşitlendikten sonra gömmede 4,695’in yüzde beş çevresinde duran 2.085 çiftin özgün uzaklığı 3,47 ile 9,46 arasında değişiyor; yüzde 10 ile yüzde 90 arasındaki aralık bile 4,04–6,79. Aynı bantta doğrusal izdüşümün aralığı 2,87–7,20 ve yüzde 10–90 aralığı 3,93–5,74, yani belirgin biçimde dar. Gömmede iki nokta arasındaki mesafeye bakıp “şu kadar farklılar” demek, en büyüğü en küçüğünün 2,7 katı olan bir aralıktan rastgele bir sayı okumaktır.

Son satır kararı kapatıyor. Aynı ayarla yalnız başlangıcı değiştirmek, aynı çiftin gömülmüş uzaklığını ortalama 0,2906 bağıl farkla oynatıyor ve çiftlerin 0,2088’inde fark yarıdan büyük. Gömmenin koordinatları da, koordinatlar arasındaki uzaklık da koşuma bağlıdır. Bir gömmede raporlanabilecek tek sayı komşuluk korunma oranıdır; eksenler, yönler ve mesafeler raporlanamaz.

Özet

• Komşuluk korunma oranının tabanı rastgele yerleşimdir ve 0,0390’dır; kuramsal beklenti 0,0398 ile buna oturur.
• Doğrusal izdüşüm iki boyutta 0,2639, komşuluğu hedefleyen gömme 0,5032 verir; fark 0,2393’tür ve altı adayın en kötüsü olan 0,3940 bile doğrusal izdüşümü geçtiği için ayar seçiminden gelmez.
• Sayı bir aralıktır: ayar aralığı 0,3940–0,5032, aynı ayarla ikinci koşum 0,4806.
• İki yaklaşım birbirinin tersini korur: doğrusal izdüşüm en uzak çiftlerin 0,6012’sini, gömme 0,0071’ini korur.
• Gömme uzaklık koruma iddiası taşımaz: ortalama uzaklık eşitlendikten sonra gömmede aynı bantta duran çiftlerin özgün uzaklığı 3,47 ile 9,46 arasında değişir ve ikinci koşumda aynı çiftin uzaklığı ortalama 0,2906 bağıl farkla oynar.

Sonraki Adım

Üç derste noktalar daha az sayıya indirildi ve her seferinde ne kaybedildiği ölçüldü: geri kurma hatası, saklanan sayı adedi, komşuluk korunma oranı. Üç ölçünün de ortak bir yanı vardı — hepsi bütün noktalar üzerinden ortalandı. Bir izdüşüm 252 noktanın ortalamasında iyiyse iyi sayıldı, bir gömme komşulukların yarısını koruyorsa yarısını koruyor sayıldı. Ortalamanın altında kalan tek tek noktalara, örneğin geri kurma hatası ötekilerin on katı olan bir aboneye hiç bakılmadı. Oysa böyle bir noktanın kendisi bir bulgu olabilir: tabloya uymayan, tek başına duran bir kayıt. Sonraki ders bu soruyu ölçü hâline getirir — tek başına duran nokta nasıl işaretlenir ve işaretlenenin kaçı gerçekten öyledir.