Karar Ağaçları

Önceki üç aile sütunları birlikte kullandı: uzaklık toplamı, olasılık çarpımı ve iç çarpım her kararda on iki sütunun hepsini işin içine soktu. Karar ağacı tersini yapar; her adımda tek bir sütun ve tek bir eşik seçer, kümeyi ikiye böler ve aynı işi iki parçada yineler.

Ağacın kendisi bu müfredatta yeni değil: M27/K01 ve K02 boyunca derinlik 6 sabit bir ağaç kullanıldı, kapasite arttıkça iki sayının ayrışması ve yaprak alt sınırının etkisi M27/K01’in genelleme konusunda ölçüldü. Burada o ölçümler tekrarlanmaz. Sorulmamış olan iki şey vardır: bölmeyi hangi ölçütün seçtiği ve derinliği baştan sınırlamak yerine büyümüş bir ağacı budamanın neyi geri aldığı.

• DO24. Küme, bölme ve taban çizgisi değişmez: 1.260 abonelik kurgu tablo, tohum 20260218, bölme 756/252/252, taban çizgisi sınamada 0,7579 ve doğrulamada 0,8135. Öznitelik kümesi K02’den gelen on iki sütundur. Ağaç sıralamaya baktığı için ölçekleme uygulanmaz; M27/K02 bu adımın ağaçtaki katkısının tam olarak sıfır olduğunu ölçtü.
• DO25. Bölme ölçütü, bir bölmenin ne kadar kazandırdığını ölçen işlevdir. Üçü karşılaştırılır: saflıksızlık, düzensizlik ve yanlış sınıflandırma oranı. Kazanç, bölmeden önceki değerden iki parçanın satır sayısıyla ağırlıklandırılmış değerinin çıkarılmasıdır.
• DO26. Her sütun için en çok on aday eşik denenir ve her yaprakta en az iki satır kalır. Derinlik süpürmesi, öğrenme eğrisi ve yaprak alt sınırı M27/K01’de ölçüldü ve tekrarlanmaz; buradaki derinlik 6 o kurstan gelen sabit, derinlik 12 ise “sınırsız büyüsün” karşılığıdır.
• DO27. Budama, büyümüş ağacın bir düğümünü yaprağa çevirmektir. Karar doğrulama kümesinden okunur: bir düğüm, yaprağa çevrildiğinde doğrulama kümesindeki hatası artmıyorsa çevrilir. Budama eşiği, ne kadar hata artışına göz yumulduğudur ve ayar değişkenidir.
• DO28. Yaprak sayısı ve yaprak derinliği ağacın büyüklük ölçüleridir; ikisi ayrı ayrı basılır.
• DO29. Seçim doğrulama kümesinden okunur; beraberlikte daha az yapraklı ağaç seçilir.
• DO30. Kırılganlık ölçümünde eğitim kümesinin yüzde 90’ı sekiz kez ayrı tohumla çekilir; doğrulama ve sınama kümeleri değişmez.

Bölme Ölçütü Ne Seçiyor

Kurulum kümeyi üretir, üç ölçütü yazar, kök bölmesini ve derinlik 6 ağaçlarını basar.

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



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),
         "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)


ALAN = ["ort_tuketim", "oynaklik", "hane", "memnuniyet", "donem", "kisi_basi",
        "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)


def oran(s):
    return sum(x["supheli"] for x in s) / len(s) if s else 0.0


def saflik(s):                              # safliksizlik
    p = oran(s)
    return 2 * p * (1 - p)


def duzensizlik(s):                         # duzensizlik
    p = oran(s)
    return 0.0 if p <= 0.0 or p >= 1.0 else -(p * math.log2(p) + (1 - p) * math.log2(1 - p))


def yanlis_oran(s):                         # yanlis siniflandirma orani
    p = oran(s)
    return min(p, 1 - p)


OLCUT = [("safliksizlik", saflik), ("duzensizlik", duzensizlik),
         ("yanlis oran", yanlis_oran)]


def en_iyi_bolme(s, f, enaz=2):
    en = None
    for a in ALAN:
        d = sorted({x[a] for x in s})
        for v in (d[1:] if len(d) < 10 else [d[int(i * len(d) / 10)] for i in range(1, 10)]):
            sol = [x for x in s if x[a] < v]
            sag = [x for x in s if x[a] >= v]
            if min(len(sol), len(sag)) < enaz:
                continue
            k = f(s) - (len(sol) * f(sol) + len(sag) * f(sag)) / len(s)
            if en is None or k > en[0]:
                en = (k, a, v, sol, sag)
    return en


def agac(s, derinlik, f, enaz=2):           # MODELDIR: karar agaci
    p, poz = oran(s), sum(x["supheli"] for x in s)
    en = en_iyi_bolme(s, f, enaz) if derinlik and len(s) >= 2 * enaz and 0.0 < p < 1.0 else None
    if en is None or en[0] <= 1e-9:
        return {"tahmin": int(p > 0.5), "n": len(s), "poz": poz}
    return {"alan": en[1], "esik": en[2], "n": len(s), "poz": poz,
            "sol": agac(en[3], derinlik - 1, f, enaz),
            "sag": agac(en[4], derinlik - 1, f, enaz)}


def tahmin(d, x):
    while "tahmin" not in d:
        d = d["sol"] if x[d["alan"]] < d["esik"] else d["sag"]
    return d["tahmin"]


def dogruluk(d, s):
    return sum(tahmin(d, x) == x["supheli"] for x in s) / len(s)


def bolmeler(d, yol=()):                    # (konum, sutun, esik) uclulari
    if "tahmin" in d:
        return []
    return ([(yol, d["alan"], round(d["esik"], 3))]
            + bolmeler(d["sol"], yol + ("s",)) + bolmeler(d["sag"], yol + ("g",)))


print(f"taban cizgisi sinamada {TABAN_SIN:.4f}; egitim {len(EGT)} satir")
print(f"{'olcut':<14}{'kok sutun':>11}{'esik':>8}{'kazanc':>9}{'sol/sag':>12}")
for ad, f in OLCUT:
    en = en_iyi_bolme(EGT, f)
    print(f"{ad:<14}{en[1]:>11}{en[2]:>8.2f}{en[0]:>9.5f}"
          f"{str(len(en[3])) + '/' + str(len(en[4])):>12}")
AGAC6 = {}
print(f"\n{'olcut (derinlik 6)':<20}{'yaprak':>7}{'dogrulama':>11}{'sinama':>8}")
for ad, f in OLCUT:
    AGAC6[ad] = agac(EGT, 6, f)
    print(f"{ad:<20}{len(bolmeler(AGAC6[ad])) + 1:>7}"
          f"{dogruluk(AGAC6[ad], DOG):>11.4f}{dogruluk(AGAC6[ad], SIN):>8.4f}")
B = {ad: set(bolmeler(t)) for ad, t in AGAC6.items()}
print(f"safliksizlik ile duzensizlik agaclarinin ortak bolmesi "
      f"{len(B['safliksizlik'] & B['duzensizlik'])}, "
      f"yanlis oran ile ortak bolmesi {len(B['safliksizlik'] & B['yanlis oran'])}")

taban cizgisi sinamada 0.7579; egitim 756 satir
olcut           kok sutun    esik   kazanc     sol/sag
safliksizlik     oynaklik   11.69  0.03923     511/245
duzensizlik      oynaklik   11.69  0.07761     511/245
yanlis oran      oynaklik   23.15  0.01984      695/61

olcut (derinlik 6)   yaprak  dogrulama  sinama
safliksizlik             48     0.8016  0.7897
duzensizlik              38     0.7778  0.7897
yanlis oran               8     0.7937  0.7698
safliksizlik ile duzensizlik agaclarinin ortak bolmesi 18, yanlis oran ile ortak bolmesi 0

Saflıksızlık ile düzensizlik kök bölmesinde birleşiyor: ikisi de oynaklık sütununu ve 11,69 eşiğini seçip kümeyi 511/245 olarak ayırıyor. Kazanç sayıları farklıdır — 0,03923 ve 0,07761 — çünkü iki ölçüt aynı büyüklüğü ölçmez; seçtikleri bölme aynıdır. Yanlış sınıflandırma oranı ise aynı kümede 695/61’lik bambaşka bir bölme seçiyor.

Fark ölçütün biçiminden gelir. Yanlış sınıflandırma oranı, sınıf oranının doğrusal parçalardan oluşan bir işlevidir: iki parçanın da çoğunluk sınıfı aynı kalıyorsa kazanç tam olarak sıfırdır, o bölme parçaları ne kadar saflaştırırsa saflaştırsın. Saflıksızlık ile düzensizlik kesin içbükeydir ve çoğunluk sınıfı değişmese bile saflaşmayı ödüllendirir. Bu yüzden yanlış oran ölçütü yalnız çoğunluğu çeviren bölmeleri görür ve ağacı sekiz yaprakta durdurur; sınama sayısı da 0,7698’de, ötekilerin 0,7897’sinin altında kalır.

Aynı kök, aynı ağaç anlamına gelmiyor. Saflıksızlık ağacı kırk yedi bölme, düzensizlik ağacı otuz yedi bölme taşıyor ve bunların yalnız on sekizi hem sütun hem eşik olarak ortak. Ölçüt kök bölmesinde ayrışmasa bile ağacın alt katlarında ayrışıyor; iki ağaç sınama kümesinde aynı sayıyı verirken farklı sorular soruyor.

Budama Derinlik Sınırından Ne Kadar Farklı

Derinlik sınırı ağacı her dalda aynı düzeyde keser. Budama ise ağacı önce serbest bırakır, sonra yalnız ödemeyen dalları geri alır; ödeyip ödemediği ayrılmış kümede ölçülür.

def hata(d, s, yaprak_olsa):
    if yaprak_olsa:
        t = int(d["poz"] / d["n"] > 0.5)
        return sum(1 for x in s if x["supheli"] != t)
    return sum(1 for x in s if tahmin(d, x) != x["supheli"])


def buda(d, s, esik, n):                    # ayrilmis kumeden okunan budama
    if "tahmin" in d:
        return d
    d = dict(d, sol=buda(d["sol"], [x for x in s if x[d["alan"]] < d["esik"]], esik, n),
             sag=buda(d["sag"], [x for x in s if x[d["alan"]] >= d["esik"]], esik, n))
    if hata(d, s, True) <= hata(d, s, False) + esik * n:
        return {"tahmin": int(d["poz"] / d["n"] > 0.5), "n": d["n"], "poz": d["poz"]}
    return d


def yaprak_derinlikleri(d, k=0):
    if "tahmin" in d:
        return [k]
    return yaprak_derinlikleri(d["sol"], k + 1) + yaprak_derinlikleri(d["sag"], k + 1)


BUDANMIS, ESIKLER = {}, (0.0, 0.004, 0.012)
print(f"{'olcut':<14}{'budama':>8}{'yaprak':>8}{'derinlik':>9}{'dogrulama':>11}{'sinama':>8}")
for ad, f in OLCUT:
    buyuk = agac(EGT, 12, f)
    yd = yaprak_derinlikleri(buyuk)
    print(f"{ad:<14}{'yok':>8}{len(yd):>8}{max(yd):>9}"
          f"{dogruluk(buyuk, DOG):>11.4f}{dogruluk(buyuk, SIN):>8.4f}")
    for esik in ESIKLER:
        b = buda(buyuk, DOG, esik, len(DOG))
        yd = yaprak_derinlikleri(b)
        BUDANMIS[(ad, esik)] = (dogruluk(b, DOG), dogruluk(b, SIN), len(yd), max(yd))
        print(f"{ad:<14}{esik:>8}{len(yd):>8}{max(yd):>9}"
              f"{BUDANMIS[(ad, esik)][0]:>11.4f}{BUDANMIS[(ad, esik)][1]:>8.4f}")
sec = max(BUDANMIS, key=lambda a: (BUDANMIS[a][0], BUDANMIS[a][2]))
print(f"\ndenenen aday {len(OLCUT) + len(BUDANMIS)} (olcut {len(OLCUT)} + budama {len(BUDANMIS)})")
print(f"dogrulamadan secilen: {sec[0]}, budama esigi {sec[1]} -> sinama "
      f"{BUDANMIS[sec][1]:.4f}, taban cizgisinin {BUDANMIS[sec][1] - TABAN_SIN:+.4f} ustunde")
b = buda(agac(EGT, 12, saflik), DOG, 0.004, len(DOG))
print(f"derinlik siniri 6: {len(bolmeler(AGAC6['safliksizlik'])) + 1} yaprak, sinama "
      f"{dogruluk(AGAC6['safliksizlik'], SIN):.4f}")
print(f"budama esigi 0.004: {len(yaprak_derinlikleri(b))} yaprak, sinama "
      f"{dogruluk(b, SIN):.4f}, 6'dan derin yaprak "
      f"{sum(1 for k in yaprak_derinlikleri(b) if k > 6)}")

olcut           budama  yaprak derinlik  dogrulama  sinama
safliksizlik       yok     127       12     0.7619  0.7341
safliksizlik       0.0      20        8     0.8413  0.7857
safliksizlik     0.004      11        8     0.8294  0.7857
safliksizlik     0.012       1        0     0.8135  0.7579
duzensizlik        yok     122       12     0.7381  0.7460
duzensizlik        0.0      22       12     0.8373  0.7817
duzensizlik      0.004       3        2     0.8214  0.7857
duzensizlik      0.012       1        0     0.8135  0.7579
yanlis oran        yok       8        4     0.7937  0.7698
yanlis oran        0.0       1        0     0.8135  0.7579
yanlis oran      0.004       1        0     0.8135  0.7579
yanlis oran      0.012       1        0     0.8135  0.7579

denenen aday 12 (olcut 3 + budama 9)
dogrulamadan secilen: safliksizlik, budama esigi 0.0 -> sinama 0.7857, taban cizgisinin +0.0278 ustunde
derinlik siniri 6: 48 yaprak, sinama 0.7897
budama esigi 0.004: 11 yaprak, sinama 0.7857, 6'dan derin yaprak 4

Budanmamış ağaç ölçünün her yerinde kötüdür: 127 yaprakla sınama kümesinde 0,7341 okuyor, yani taban çizgisinin 0,0238 altında. Aynı ağaç budandığında 20 yaprağa iniyor ve 0,7857’ye çıkıyor; doğrulama sayısı 0,7619’dan 0,8413’e gidiyor. Ailenin sayısı 0,7857’dir, taban çizgisini 0,0278 geçer ve 12 aday denenerek bulunmuştur.

Son üç satır budamanın derinlik sınırından farkını veriyor. Derinlik 6 ağacı 48 yaprakla 0,7897, budanmış ağaç 11 yaprakla 0,7857 okuyor: aradaki fark bir abone, yapraktaki fark dört kattan fazla. Daha önemlisi budanmış ağacın derinliği 8’dir ve dört yaprağı altıncı düzeyden derindedir. Derinlik sınırı bu dört yaprağı, ödeyip ödemediklerine bakmadan keserdi; budama onları tutup başka yerdeki otuz yedi yaprağı attı. İki adımın geri aldığı şey aynı değildir: biri düzeye, öteki katkıya bakar.

Yanlış oran ölçütünün satırları ayrı bir şey söylüyor: üç budama eşiğinde de ağaç tek yaprağa iniyor ve model taban çizgisine düşüyor. Sekiz yapraklık ağacının hiçbir bölmesi doğrulama kümesinde kendini ödemiyor.

Tek Ağacın Kararı Ne Kadar Sağlam

Seçilen ağaç bir sayı verdi. O sayının ne kadarının eğitim kümesinin tam olarak bu 756 satır olmasından geldiği ayrıca ölçülür.

def alt_orneklem(s, tohum, pay=0.9):        # egitim kumesinin yuzde 90'i
    r, k = uretec(tohum), list(s)
    for i in range(len(k) - 1, 0, -1):
        j = int(r() * (i + 1))
        k[i], k[j] = k[j], k[i]
    return k[:int(len(k) * pay)]


ORTAK, SAYI = None, []
print(f"{'orneklem':>9}{'kok bolme':>26}{'yaprak':>8}{'sinama':>8}")
for i in range(8):
    alt = alt_orneklem(EGT, TOHUM + 820000 + i * 13)
    t = buda(agac(alt, 12, saflik), DOG, 0.004, len(DOG))
    en = en_iyi_bolme(alt, saflik)
    b = set(bolmeler(t))
    ORTAK = b if ORTAK is None else ORTAK & b
    SAYI.append(dogruluk(t, SIN))
    print(f"{i + 1:>9}{en[1] + ' < ' + format(en[2], '.2f'):>26}"
          f"{len(yaprak_derinlikleri(t)):>8}{SAYI[-1]:>8.4f}")
print(f"sekiz agacin hepsinde bulunan bolme (sutun ve esik birlikte) {len(ORTAK)}")
print(f"sinama sayilari {min(SAYI):.4f} ile {max(SAYI):.4f} arasinda, "
      f"aralik {max(SAYI) - min(SAYI):.4f}")

 orneklem                 kok bolme  yaprak  sinama
        1          oynaklik < 13.99       3  0.7897
        2          oynaklik < 13.88      10  0.7897
        3          oynaklik < 13.80      13  0.7817
        4          oynaklik < 14.12       3  0.7897
        5          oynaklik < 11.41       8  0.7817
        6          oynaklik < 13.60       5  0.7619
        7          oynaklik < 13.91       6  0.7897
        8          oynaklik < 14.12      10  0.7857
sekiz agacin hepsinde bulunan bolme (sutun ve esik birlikte) 0
sinama sayilari 0.7619 ile 0.7897 arasinda, aralik 0.0278

Kök sütunu sekiz örneklemde de aynı kalıyor: oynaklık. Eşik ise 11,41 ile 14,12 arasında geziniyor ve yaprak sayısı 3 ile 13 arasında değişiyor — aynı yordam, aynı ayarlar, yalnız eğitim kümesinin onda biri değişmiş durumda. Sekiz ağacın hepsinde bulunan bölme sayısı sıfırdır: sütun ve eşik birlikte alındığında tek bir ortak bölme yok.

Sınama sayıları 0,7619 ile 0,7897 arasında, aralık 0,0278. Bu sayı ailenin taban çizgisi üstündeki farkının tamamına eşittir. Ölçülen fark, eğitim kümesinin hangi yüzde doksanının çekildiğine bağlı olarak tümüyle silinebiliyor.

Özet

• Saflıksızlık ile düzensizlik aynı kök bölmesini seçer (oynaklık, 11,69, 511/245); yanlış sınıflandırma oranı 695/61’lik başka bir bölme seçer, çünkü çoğunluğu çevirmeyen bölmelere tam olarak sıfır kazanç verir.
• Aynı kökten çıkan iki ağaç kırk yedi ve otuz yedi bölme taşır ve yalnız on sekizinde birleşir.
• Budanmamış derinlik 12 ağacı 127 yaprakla 0,7341, yani taban çizgisinin 0,0238 altında okur; budama aynı ağacı 20 yaprağa indirip 0,7857’ye çıkarır.
• Ailenin sayısı 0,7857’dir, taban çizgisini 0,0278 geçer ve 12 aday denenerek bulunmuştur.
• Budama derinlik sınırından farklı olarak katkıya bakar: 11 yapraklı budanmış ağacın dört yaprağı altıncı düzeyden derindir ve derinlik sınırı bunları ölçmeden keserdi.
• Yüzde doksanlık sekiz alt örneklemin ağaçlarında ortak tek bir bölme yoktur; sınama sayıları 0,0278 aralıkta geziniyor.

Sonraki Adım

Tek bir ağaç budandı, elde kalan sayı taban çizgisini 0,0278 geçti ve on iki aday denendi. Ama son tablo bu sayının altını oyuyor: aynı yordam, eğitim kümesinin onda biri değiştiğinde bambaşka bölmeler seçiyor ve verdiği sayı taban çizgisi üstündeki farkın tamamı kadar geziniyor. Tek ağacın kararı kırılgandır ve kırılganlık ağacın bir kusuru değil, tanımının sonucudur: her düğümde tek bir eşik seçilir ve o eşik en yakın rakibinden yalnız birkaç satırla ayrılıyorsa, birkaç satır değiştiğinde seçim de değişir. Sonraki ders bu kırılganlığı bir kusur olarak düzeltmek yerine kullanır: aynı yordamı farklı eğitim örneklemlerinde birden çok kez çalıştırıp kararları birleştirir. Ölçülecek şey ağaç sayısı arttıkça ayrılmış küme sayısının oturması ve değişkenliğin düşmesidir.