En Yakın Komşu

Doğrusal modeller konusu beş ders boyunca tek bir biçim üzerinde çalıştı: model, öznitelik uzayında bir doğru ya da bir düzlem çiziyordu. Polinom öznitelikleri bu biçimi esnetti ama esneme yine sabit katsayılı bir denklemin içinde kaldı. Konunun kapanışı bir soruyu açık bıraktı: iki sınıfı ayıran sınırın kendisinin eğri olduğu bir kümede ne olur, ve o eğriyi elle yazmadan bulan bir aile kaç sayı eder.

Bu ders o soruya en aykırı yanıtla başlar: hiç denklem kurmayan bir model. Örnek tabanlı yordam eğitim sırasında hiçbir şey hesaplamaz; eğitim kümesini olduğu gibi saklar ve bir aboneyi sınıflandırırken ona en yakın eğitim satırlarına bakıp çoğunluğun etiketini verir. Karar sınırı burada yazılmaz, örneklerin yerleşiminden doğar ve eğri olması için ayrıca bir şey yapılmaz. Bedeli vardır ve ders o bedeli kursun üç sayısıyla ölçer: taban çizgisi, ailenin sayısı ve o sayıyı bulmak için denenen aday sayısı.

• DO1. Küme M27/K01 ve K02’den gelen kurgu abone tablosudur: 1.260 abone, tohum 20260218, bölme 756/252/252, sınama kümesinde taban çizgisi 0,7579. Taban çizgisi en sık sınıfı, yani “şüpheli değil”i söyleyen yordamdır.
• DO2. Öznitelik kümesi M27/K02’nin bıraktığı haliyle alınır ve kurs boyunca sabit tutulur: beş sayısal sütun, kişi başına tüketim oranı, sıfır okuma göstergesi ve beş bölge sütunu, toplam on iki. Metinden türetilen sütunlar M27/K06’ya bırakıldığı için dışarıda kalır. Değişen tek şey modeldir.
• DO3. Ölçü doğruluktur ve sınama kümesi 252 abonedir; bir abone 0,0040 eder.
• DO4. Ölçekleme M27/K02’nin ölçekleme dersinde kurulan biçimiyle uygulanır: standart puan, yalnız eğitim kümesinden öğrenilir ve öteki iki kümeye uygulanır. Uzaklık toplayan bir yordamda ölçek bir sütun ağırlığıdır; K02 bu kararın işaretinin aileye göre değiştiğini ölçtü ve o sayılar burada tekrarlanmaz.
• DO5. Ayar değişkeni, modelin veriden öğrenmediği, dışarıdan verilen sayıdır. Bu ailede iki tanedir: komşu sayısı ve uzaklık ölçütü.
• DO6. Seçim doğrulama kümesinden okunur. Sınama kümesindeki sayı yalnız bildirilir; aynı tablodan sınama kümesine göre seçim yapılsaydı ne çıkacağı ayrıca basılır.
• DO7. Komşu sayıları tek seçilir, böylece oylamada beraberlik oluşmaz.
• DO8. Boyut laneti ölçümünde eklenen sütunlar kurgudur, aynı üreteçten gelir ve etiketle hiçbir ilişki taşımaz.

Eğitimi Olmayan Bir Model

Kurulum kümeyi yeniden üretir, ölçeği eğitim kümesinden öğrenir ve yordamı yazar.

# komsu.py — MODELDIR. M27/K01 ve K02'nin KURGU abone tablosu ayni tohumla
# yeniden uretilir; oznitelik kumesi K02'den gelir ve kurs boyunca sabittir.
import math
import statistics

TOHUM, HAM, M32 = 20260218, 1400, 0xFFFFFFFF
BOLGE = [("kuzey", 0.28, 21, 0.00), ("guney", 0.22, 17, -0.10),
         ("dogu", 0.18, 26, 0.30), ("bati", 0.14, 14, -0.05),
         ("merkez", 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[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, oyn, r = sum(v) / len(v), max(v) - min(v), uretec(TOHUM + 51000 + k["no"])
    z = (0.052 * (ort - 20) + 0.85 * (min(v) == 0.0) + 0.026 * oyn
         + 0.24 * (k["hane"] >= 5) - 0.20 * (k["memnuniyet"] >= 4) + k["bolge"][3]
         + 0.9 * (k["no"] - 10001) / 1399 + (r() + r() + r() - 1.5) * 1.30)
    x = {"hane": k["hane"], "memnuniyet": k["memnuniyet"], "donem": len(v),
         "ort_tuketim": round(ort, 2), "oynaklik": round(oyn, 2), "bolge_ad": k["bolge"][0],
         "sifir_okuma": int(min(v) == 0.0), "supheli": int(z > 1.35)}
    for b in BOLGE:
        x["b_" + b[0]] = int(k["bolge"][0] == b[0])
    x["kisi_basi"] = round(x["ort_tuketim"] / x["hane"], 3)
    VERI.append(x)

SAYISAL = ["ort_tuketim", "oynaklik", "hane", "memnuniyet", "donem", "kisi_basi"]
ALAN = SAYISAL + ["sifir_okuma", "b_kuzey", "b_guney", "b_dogu", "b_bati", "b_merkez"]


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]


K = karistir(VERI, TOHUM + 90000)
EGT, DOG, SIN = K[:756], K[756:1008], K[1008:]
TABAN_SIN = sum(x["supheli"] == 0 for x in SIN) / len(SIN)
TABAN_DOG = sum(x["supheli"] == 0 for x in DOG) / len(DOG)
OLCEK = {a: (statistics.fmean(x[a] for x in EGT),
             statistics.pstdev([x[a] for x in EGT])) for a in SAYISAL}


def olcekle(s):
    return [dict(x, **{a: (x[a] - OLCEK[a][0]) / OLCEK[a][1] for a in OLCEK}) for x in s]


def vektor(s, alan=None):
    return [([x[a] for a in (alan or ALAN)], x["supheli"]) for x in s]


def mutlak_fark(a, b):
    return sum(abs(p - q) for p, q in zip(a, b))


def komsu_dogruluk(egt, hedef, k, olcut):   # MODELDIR: ornek tabanli yordam
    d = 0
    for v, y in hedef:
        u = sorted((olcut(v, w), t) for w, t in egt)
        d += (sum(t for _, t in u[:k]) * 2 > k) == y
    return d / len(hedef)


E, D, S = olcekle(EGT), olcekle(DOG), olcekle(SIN)
VE, VD, VS = vektor(E), vektor(D), vektor(S)
print(f"egitim {len(EGT)}, dogrulama {len(DOG)}, sinama {len(SIN)}, sutun {len(ALAN)}")
print(f"taban cizgisi: sinamada {TABAN_SIN:.4f}, dogrulamada {TABAN_DOG:.4f}")
print(f"olceksiz sutunlar (mutlak fark, k=31) sinama "
      f"{komsu_dogruluk(vektor(EGT), vektor(SIN), 31, mutlak_fark):.4f}")
print(f"olcekli sutunlar  (mutlak fark, k=31) sinama "
      f"{komsu_dogruluk(VE, VS, 31, mutlak_fark):.4f}")

egitim 756, dogrulama 252, sinama 252, sutun 12
taban cizgisi: sinamada 0.7579, dogrulamada 0.8135
olceksiz sutunlar (mutlak fark, k=31) sinama 0.7778
olcekli sutunlar  (mutlak fark, k=31) sinama 0.7937

komsu_dogruluk işlevinin gövdesinde model kurma adımı yoktur. Öteki ailelerde ağırlık, katsayı ya da bölme eşiği çıkaran bir aşama bulunur; burada o aşama boştur ve modelin kendisi 756 satırlık eğitim kümesidir. Bunun bir sonucu tahmin tarafında görünür: her yeni abone için 756 uzaklık hesaplanır ve sıralanır. Aile eğitimin maliyetini tahmine devreder.

İkinci gözlem ölçek satırındadır. Aynı yordam ölçeksiz sütunlarla 0,7778, ölçekli sütunlarla 0,7937 okuyor. Sebep, uzaklığın bir toplam olmasıdır: on iki farkın toplamında ortalama tüketimin ham aralığı bölge sütununun aralığından kırk kat geniştir, dolayısıyla ölçeksiz uzaklık sessizce bir ağırlıklandırmadır. M27/K02 bu kararı üç ailede ayrı ayrı ölçtü ve işaretinin aileye göre değiştiğini gösterdi; burada ölçekleme bir düzeltme olarak değil, uzaklık kavramının sütunlar arasında karşılaştırılabilir olmasının koşulu olarak duruyor.

Bir sayı daha dikkat ister: taban çizgisi iki kümede aynı değildir. Sınama kümesinde 0,7579, doğrulama kümesinde 0,8135. Aynı bölmeden çıkan iki küme, şüpheli oranı bakımından 0,0556 kadar ayrışmış durumda. Bu, bir modelin doğrulama sayısının sınama sayısıyla doğrudan karşılaştırılamayacağı anlamına gelir; her sayı kendi kümesinin tabanına göre okunur.

Yirmi Dört Aday

Ailenin iki ayar değişkeni vardır ve ikisi de veriden öğrenilmez. Komşu sayısı kararın kaç örneğe dayandığını belirler. Uzaklık ölçütü ise “yakın” sözcüğünün tanımıdır: farkların karelerini toplayan kare uzaklık, mutlak farkları toplayan mutlak fark ve yalnız en büyük tek farka bakan en büyük fark. Üçü aynı kümede aynı sıralamayı vermez.

def kare_uzaklik(a, b):
    return sum((p - q) * (p - q) for p, q in zip(a, b))


def en_buyuk_fark(a, b):
    return max(abs(p - q) for p, q in zip(a, b))


KLER = [1, 3, 5, 9, 15, 21, 31, 45]
OLCUTLER = [("kare uzaklik", kare_uzaklik), ("mutlak fark", mutlak_fark),
            ("en buyuk fark", en_buyuk_fark)]


def komsu_listesi(egt, hedef, olcut):
    return [([t for _, t in sorted((olcut(v, w), t) for w, t in egt)][:max(KLER)], y)
            for v, y in hedef]


ADAY = {}
for ad, olcut in OLCUTLER:
    kd, ks = komsu_listesi(VE, VD, olcut), komsu_listesi(VE, VS, olcut)
    for k in KLER:
        ADAY[(ad, k)] = (sum((sum(t[:k]) * 2 > k) == y for t, y in kd) / len(kd),
                         sum((sum(t[:k]) * 2 > k) == y for t, y in ks) / len(ks))

for i, kume in enumerate(("dogrulama", "sinama")):
    print(f"{kume + ' k =':<16}" + "".join(f"{k:>8}" for k in KLER))
    for ad, _ in OLCUTLER:
        print(f"{ad:<16}" + "".join(f"{ADAY[(ad, k)][i]:>8.4f}" for k in KLER))
sd = max(ADAY, key=lambda a: (ADAY[a][0], -a[1]))
ss = max(ADAY, key=lambda a: (ADAY[a][1], -a[1]))
print(f"\ndenenen aday {len(ADAY)}")
print(f"dogrulamadan secilen: {sd[0]}, k={sd[1]} -> dogrulama {ADAY[sd][0]:.4f}, "
      f"sinama {ADAY[sd][1]:.4f}")
print(f"sinamadan secilen:    {ss[0]}, k={ss[1]} -> dogrulama {ADAY[ss][0]:.4f}, "
      f"sinama {ADAY[ss][1]:.4f}")
print(f"secilen adayda dogrulama - sinama {ADAY[sd][0] - ADAY[sd][1]:+.4f}; "
      f"ailenin sayisi taban cizgisinin {ADAY[sd][1] - TABAN_SIN:+.4f} ustunde")
print(f"dogrulama tabanini gecen aday {sum(1 for a in ADAY if ADAY[a][0] > TABAN_DOG)}, "
      f"sinama tabanini gecen {sum(1 for a in ADAY if ADAY[a][1] > TABAN_SIN)}")

dogrulama k =          1       3       5       9      15      21      31      45
kare uzaklik      0.7540  0.7738  0.7698  0.8214  0.8175  0.8254  0.8214  0.8254
mutlak fark       0.7778  0.7738  0.7937  0.8254  0.8214  0.8214  0.8294  0.8254
en buyuk fark     0.7500  0.7897  0.8056  0.8214  0.8056  0.8095  0.8056  0.8135
sinama k =             1       3       5       9      15      21      31      45
kare uzaklik      0.7262  0.7341  0.7341  0.7579  0.7619  0.7738  0.7778  0.7937
mutlak fark       0.7063  0.7262  0.7302  0.7698  0.7698  0.7619  0.7937  0.7937
en buyuk fark     0.7262  0.7460  0.7619  0.7817  0.7897  0.7738  0.7579  0.7778

denenen aday 24
dogrulamadan secilen: mutlak fark, k=31 -> dogrulama 0.8294, sinama 0.7937
sinamadan secilen:    mutlak fark, k=31 -> dogrulama 0.8294, sinama 0.7937
secilen adayda dogrulama - sinama +0.0357; ailenin sayisi taban cizgisinin +0.0357 ustunde
dogrulama tabanini gecen aday 11, sinama tabanini gecen 14

İlk sütun ailenin en tanınmış kusurunu veriyor. Tek komşuya bakan yordam sınama kümesinde üç ölçütte de taban çizgisinin altındadır: 0,7262, 0,7063 ve 0,7262. Bir komşu, eğitim kümesindeki tek bir satırın etiketini kopyalamaktır; o satır yanlış tarafta duruyorsa karar da yanlış tarafta durur. Komşu sayısı büyüdükçe her karar daha çok satıra dayanır ve sayı yükselir.

Doğrulama kümesinden okunan seçim mutlak fark ile 31 komşudur; o adayın doğrulama sayısı 0,8294, sınama sayısı 0,7937. Ailenin sayısı 0,7937’dir ve taban çizgisini 0,0357, yani dokuz abone geçer. Aynı tablodan sınama kümesine göre seçim yapılsaydı seçilen aday değişmezdi — bu bir şanstır ve tabloda görülüyor, çünkü sınamada 0,7937 üç ayrı adayda birden çıkıyor. Değişen şey aday değil bildirilen sayı olurdu: seçim kümesindeki 0,8294 raporlansaydı aile dokuz abone yerine on sekiz abone kazanmış görünürdü. Doğrulama kümesi seçim için harcanmış bir kümedir ve üzerinde okunan en yüksek sayı bir genelleme kestirimi değildir.

Denenen aday sayısı 24‘tür ve bu sayı ailenin sayısının yanında durmadan okunamaz. Yirmi dört adayın doğrulama kümesinde yalnız 11’i kendi tabanını geçiyor; on üç aday hiçbir şey söylemeyen yordamdan kötü. Aile “taban çizgisini 0,0357 geçti” cümlesi, “yirmi dört adayın en iyisi taban çizgisini 0,0357 geçti” cümlesiyle aynı şey değildir.

Boyut Laneti

Uzaklık, sütun sayısı büyüdükçe ayırt edici olmaktan çıkar. Mekanizma toplamın kendisindedir: her yeni sütun toplama bir terim ekler ve terimler birbirinden bağımsızsa toplam, sütun sayısı büyüdükçe ortak bir ortalamaya yaklaşır. Sonuçta en uzak komşu ile en yakın komşu arasındaki oran 1’e iner ve “en yakın” sözcüğü anlamını yitirir. Bu, boyut laneti adıyla anılır ve sayılabilir.

def gurultulu(s, d, tohum):                 # KURGU: hicbir bilgi tasimayan sutunlar
    out = []
    for i, x in enumerate(s):
        r = uretec(tohum + i)
        out.append(([x[a] for a in ALAN] + [(r() + r() + r() - 1.5) * 1.15
                                            for _ in range(d)], x["supheli"]))
    return out


print(f"{'sutun':>6} {'en uzak / en yakin':>19} {'sinama':>8} {'tabana gore':>12}")
for d in (0, 4, 12, 40, 120):
    GE, GS = gurultulu(E, d, TOHUM + 300000), gurultulu(S, d, TOHUM + 700000)
    oran, dogru = [], 0
    for v, y in GS:
        u = sorted((mutlak_fark(v, w), t) for w, t in GE)
        oran.append(u[-1][0] / u[0][0])
        dogru += (sum(t for _, t in u[:31]) * 2 > 31) == y
    print(f"{len(ALAN) + d:>6} {statistics.fmean(oran):>19.2f} "
          f"{dogru / len(GS):>8.4f} {dogru / len(GS) - TABAN_SIN:>+12.4f}")

 sutun  en uzak / en yakin   sinama  tabana gore
    12               26.91   0.7937      +0.0357
    16                6.70   0.7817      +0.0238
    24                3.46   0.7738      +0.0159
    52                2.01   0.7698      +0.0119
   132                1.49   0.7579      +0.0000

İki sütun birlikte okunur. On iki sütunda en uzak eğitim satırı en yakın olandan 26,91 kat uzaktadır ve “komşu” sözcüğünün karşılığı vardır. Dört gürültü sütunu eklendiğinde oran 6,70’e, kırk sütunda 2,01’e iner. Yüz yirmi gürültü sütununda oran 1,49’dur: en yakın eğitim satırı ile en uzak olan arasında yarım kattan az fark kalmıştır ve model tam olarak taban çizgisine, 0,7579’a oturur. Aile artık hiçbir şey öğrenmemektedir.

Eklenen sütunların hiçbiri yanlış bilgi taşımıyor; hiç bilgi taşımıyorlar. Fark, ailenin bu sütunları görmezden gelememesinden gelir. Her bölmede tek bir sütun seçen bir karar ağacı, bilgisiz sütunu bölme adayı olarak seçmeyerek dışarıda bırakabilir; katsayı öğrenen bir doğrusal model o sütunun katsayısını küçültebilir. Uzaklık toplamının böyle bir aracı yoktur, çünkü uzaklık öğrenilmez, tanımlanır. Öznitelik seçimi ve boyut azaltma bu ailede bir iyileştirme değil, işleyebilmesinin koşuludur.

Özet

• Örnek tabanlı yordamın eğitim aşaması boştur; model 756 satırlık eğitim kümesinin kendisidir ve maliyet tahmin tarafındadır: her abone için 756 uzaklık hesaplanır.
• Doğrulama kümesinden seçilen aday mutlak fark ile 31 komşudur; ailenin sınama kümesindeki sayısı 0,7937, taban çizgisinin 0,0357 üstünde, ve bu sayı 24 aday denenerek bulundu.
• Aynı adayın doğrulama kümesindeki sayısı 0,8294’tür; seçim kümesinden okunan sayı bildirilseydi aile dokuz abone yerine on sekiz abone kazanmış görünürdü.
• Tek komşuya bakan yordam üç uzaklık ölçütünde de sınama kümesinde taban çizgisinin altına düşer (0,7262, 0,7063 ve 0,7262); yirmi dört adayın on üçü doğrulama kümesinde kendi tabanını geçemiyor.
• Sütun sayısı 12’den 132’ye çıktığında en uzak komşunun en yakın komşuya oranı 26,91’den 1,49’a iner ve ailenin sayısı tam olarak taban çizgisine, 0,7579’a oturur.

Sonraki Adım

Bu ailede on iki sütun tek bir uzaklık toplamında eriyor: bölge göstergesiyle ortalama tüketim aynı toplamda buluşuyor ve kararı hangisinin taşıdığı görünmüyor. Kategorik bir alan için “uzaklık” zaten zorlama bir kavramdır; bölge sütunları beş ikili sütuna açıldıktan sonra iki farklı bölge arasındaki fark her zaman aynı sayıdır. Sonraki ders sütunları toplamayan, sayan bir aile alır: her öznitelik değerinin her sınıf altında kaç kez görüldüğünü sayar ve bu sayımları çarpar. Çarpmanın geçerli olabilmesi için sütunların, sınıf verildiğinde birbirinden bağımsız olması gerekir; bu kümede değildir. Ders varsayımın bozulmasının iki ayrı sonucunu ayrı ayrı sayar — olasılık çıktısının uçlara gitmesi ile sıralamanın ayakta kalması — ve hiç görülmemiş bir sayımın modeli tümüyle susturmasının düzleştirmeyle nasıl çözüldüğünü ölçer.