Torbalanmış Ağaç Toplulukları

Önceki ders karar ağacının bölme ölçütünü ve budamayı ayırdı; budanmış ağaç taban çizgisini geçti ve dört derste denenen aileler arasında en okunaklı model oldu. Bir özelliği ölçülmeden kaldı: eğitim kümesi biraz değiştiğinde ağaç bambaşka bölmeler seçiyor. Kök kayınca altındaki her şey kayar; tek ağacın verdiği sayı bir ölçüm değil bir çekilişin sonucudur.

Bu ders önce o çekilişi sayar, sonra daraltmanın yolunu kurar. Torbalama (bagging) aynı yordamı geri koyarak çekilmiş birçok örneklem üzerinde ayrı ayrı çalıştırıp ağaçların çoğunluk oyunu alır. Öznitelik rastgeleliği ikinci bir ayrım ekler: her ağaç bölmelerini rastgele seçilmiş bir alt sütun kümesinden seçer. Ölçülen tek sayı değil ikidir: topluluğun sayısı ve o sayının saçılması.

• DO31. Küme M27/K01’in kurgu abone tablosudur: 1.260 abone, 756/252/252, tohum 20260218. Taban çizgisi sınamada 0,7579, doğrulamada 0,8135’tir; kursun taşıdığı sayı sınamadakidir.
• DO32. Öznitelik kümesi M27/K02’den gelir ve on bir sütundur; değişen tek şey model.
• DO33. Karşılaştırma noktası önceki derslerin ağacıdır: derinlik 6, yaprak alt sınırı 2, bölme ölçütü saflıksızlık azalması. Eşikler eğitim kümesinden bir kez çıkarılır ve sütun başına en çok yirmi dörttür; bu bir hız kararıdır, seçilebilecek bölmeleri değiştirmez.
• DO34. Torba örneklemi 756 satırlıktır ve geri koyarak çekilir. Geri koyarak örnekleme M26’nın Uygulamalı İstatistik kursunda kuruldu; yöntemi tekrarlanmaz.
• DO35. Karar çoğunluk oyudur: olumlu diyen ağaçların oranı 0,5’i geçerse abone şüpheli sayılır. Eşik M27/K02’den sabittir; seçimi model değerlendirmeye bırakılır.
• DO36. Denenen aday sayısı 31’dir: yedi ağaç sayısı ve yirmi dört alan-derinlik çifti. Seçim doğrulama kümesinden okunur; sınama kümesi yalnız son satırda görünür.

Tek Ağacın Saçılması

Kurulum tabloyu üretir, sütunları eşiklere kutular ve karşılaştırma noktası olan tek ağacı basar.

# torbalama.py — MODELDIR. M27/K01'in KURGU abone tablosu ayni tohumla yeniden
# uretilir; oznitelik kumesi K02'den gelir ve kurs boyunca sabit tutulur.
import bisect
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])
    VERI.append(x)


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:]
ALAN = ["ort_tuketim", "oynaklik", "hane", "memnuniyet", "donem", "sifir_okuma",
        "b_kuzey", "b_guney", "b_dogu", "b_bati", "b_merkez"]
ESIK = {}
for a in ALAN:
    d = sorted({x[a] for x in EGT})
    ESIK[a] = d[1:] if len(d) <= 24 else [d[int(i * len(d) / 25)] for i in range(1, 25)]
KOVA = [len(ESIK[a]) + 1 for a in ALAN]


def kutula(s):                              # her satir: kova numaralari ve etiket
    return [(tuple(bisect.bisect_right(ESIK[a], x[a]) for a in ALAN), x["supheli"])
            for x in s]


KE, KD, KS = kutula(EGT), kutula(DOG), kutula(SIN)
TUM = list(range(len(ALAN)))


def agac(orn, derinlik, alanlar, enaz=2):   # MODELDIR: karar agaci
    n, p, en = len(orn), sum(y for _, y in orn), None
    if derinlik and n >= 2 * enaz and 0 < p < n:
        for k in alanlar:
            say, poz = [0] * KOVA[k], [0] * KOVA[k]
            for b, y in orn:
                say[b[k]] += 1
                poz[b[k]] += y
            sc = sp = 0
            for j in range(KOVA[k] - 1):
                sc, sp = sc + say[j], sp + poz[j]
                if sc < enaz or n - sc < enaz:
                    continue
                kazanc = sp * sp / sc + (p - sp) ** 2 / (n - sc) - p * p / n
                if en is None or kazanc > en[0]:
                    en = (kazanc, k, j)
    if en is None or en[0] <= 1e-9:
        return p / n
    _, k, j = en
    return (k, j, agac([o for o in orn if o[0][k] <= j], derinlik - 1, alanlar, enaz),
            agac([o for o in orn if o[0][k] > j], derinlik - 1, alanlar, enaz))


def oran(d, b):
    while type(d) is tuple:
        d = d[2] if b[d[0]] <= d[1] else d[3]
    return d


def dogruluk(d, kume):
    return sum((oran(d, b) > 0.5) == y for b, y in kume) / len(kume)


def taban(kume):
    return sum(y == 0 for _, y in kume) / len(kume)


TEK = agac(KE, 6, TUM)
print(f"taban cizgisi        dogrulama {taban(KD):.4f}  sinama {taban(KS):.4f}")
print(f"tek agac derinlik 6  dogrulama {dogruluk(TEK, KD):.4f}  "
      f"sinama {dogruluk(TEK, KS):.4f}  egitim {dogruluk(TEK, KE):.4f}")

taban cizgisi        dogrulama 0.8135  sinama 0.7579
tek agac derinlik 6  dogrulama 0.8056  sinama 0.7778  egitim 0.8426

İki ayrılmış küme aynı yordamla iki ayrı taban veriyor: sınamada 0,7579, doğrulamada 0,8135. Ağaç sınamada 0,7778 okuyup tabanı 0,0199 geçiyor, doğrulamada 0,8056’da kalıp kendi tabanının 0,0079 altına düşüyor.

Kırılganlık şöyle sayılır: eğitim kümesinden geri koyarak 41 örneklem çekilir, her birine aynı yordamla bir ağaç kurulur. Değişen tek şey hangi satırın kaç kez göründüğüdür.

def sacilma(v):
    o = sum(v) / len(v)
    return (sum((q - o) ** 2 for q in v) / len(v)) ** 0.5


def orman(tohum, sayi, m, derinlik):        # MODELDIR: torbalanmis agac toplulugu
    r, agaclar, torbalar = uretec(tohum), [], []
    for _ in range(sayi):
        secim = [int(r() * len(KE)) for _ in range(len(KE))]
        havuz, alanlar = list(TUM), []
        for _ in range(min(m, len(TUM))):
            alanlar.append(havuz.pop(int(r() * len(havuz))))
        agaclar.append(agac([KE[i] for i in secim], derinlik, sorted(alanlar)))
        torbalar.append(set(secim))
    return agaclar, torbalar


def oy(agaclar, b):                         # cogunluk oyu: olumlu diyen agac orani
    return sum(oran(d, b) > 0.5 for d in agaclar) / len(agaclar)


def orman_dogruluk(agaclar, kume):
    return sum((oy(agaclar, b) > 0.5) == y for b, y in kume) / len(kume)


ORMANLAR = [orman(TOHUM + 13 * i, 41, 11, 6) for i in range(5)]
AGACLAR = ORMANLAR[0][0]
kok = {}
for d in AGACLAR:
    kok[(d[0], d[1])] = kok.get((d[0], d[1]), 0) + 1
etiket = [[oran(d, b) > 0.5 for b, _ in KD] for d in AGACLAR]
ayri = [sum(u != v for u, v in zip(etiket[i], etiket[j]))
        for i in range(len(AGACLAR)) for j in range(i + 1, len(AGACLAR))]
print(f"kok bolmesi icin {len(kok)} ayri (alan, esik) cifti, "
      f"en siki {max(kok.values())} agacta")
print(f"{'tek agac':<12} {'ortalama':>9} {'sacilma':>9} {'en dusuk':>9} {'en yuksek':>10}")
for ad, kume in (("dogrulama", KD), ("sinama", KS)):
    v = [dogruluk(d, kume) for d in AGACLAR]
    print(f"{'  ' + ad:<12} {sum(v) / len(v):>9.4f} {sacilma(v):>9.4f} "
          f"{min(v):>9.4f} {max(v):>10.4f}")
print(f"iki agacin ayri sinifladigi abone (252 icinde): ortalama "
      f"{sum(ayri) / len(ayri):.1f}, en az {min(ayri)}, en cok {max(ayri)}")
print(f"ayni 41 agacin oyu   dogrulama {orman_dogruluk(AGACLAR, KD):.4f}  "
      f"sinama {orman_dogruluk(AGACLAR, KS):.4f}")

kok bolmesi icin 9 ayri (alan, esik) cifti, en siki 16 agacta
tek agac      ortalama   sacilma  en dusuk  en yuksek
  dogrulama     0.7744    0.0218    0.7222     0.8135
  sinama        0.7489    0.0246    0.6905     0.7897
iki agacin ayri sinifladigi abone (252 icinde): ortalama 46.2, en az 24, en cok 77
ayni 41 agacin oyu   dogrulama 0.8095  sinama 0.7698

Kök bölmesi 41 ağacın hepsinde aynı değil: dokuz ayrı alan-eşik çifti kök oluyor, en sık görüleni yalnız 16 ağaçta. Altındaki her şeyi belirleyen bölme, örneklem değişince ağaçların yüzde altmışında başka bir yere kayıyor.

İkinci sayı daha somut: rastgele iki ağaç 252 abonenin ortalama 46,2’sini ayrı sınıflıyor, en yakın çiftte 24, en uzak çiftte 77 aboneyi.

Üçüncüsü bunun ayrılmış kümeye yansımasıdır. Tek ağaçların sınama sayısı ortalama 0,7489, saçılma 0,0246, aralık 0,6905 ile 0,7897; iki uç arası 25 abone eder. Bir modelin sayısını tek örneklemden okumak, bu aralıktan rastgele bir nokta seçmektir. Saçılma, ortalamadan kare uzaklıkların ortalamasının kareköküdür.

Son satır aynı 41 ağacın oyudur: doğrulama 0,8095, sınama 0,7698. Bu sayı tek ağaçların ortalaması 0,7489’un 0,0209 üstünde, ama tek ağacın 0,7778’inin altında: bütün sütunlar her ağaca açıkken torbalama ortalamayı yukarı çekiyor, tek ağacı geçmiyor.

Ağaç Sayısı ve Değişkenlik

Torbalamanın asıl kattığı ortalamada değil saçılmadadır. Beş tohumla beş topluluk kurulur, her birinin ilk 1, 3, 5, 11, 21, 31 ve 41 ağacı ayrı ayrı oylanır.

print(f"{'agac':>5} {'dogrulama':>10} {'sacilma':>9} {'sinama':>9} {'sacilma':>9}")
for sayi in (1, 3, 5, 11, 21, 31, 41):
    vd = [orman_dogruluk(a[:sayi], KD) for a, _ in ORMANLAR]
    vs = [orman_dogruluk(a[:sayi], KS) for a, _ in ORMANLAR]
    print(f"{sayi:>5} {sum(vd) / 5:>10.4f} {sacilma(vd):>9.4f} "
          f"{sum(vs) / 5:>9.4f} {sacilma(vs):>9.4f}")

 agac  dogrulama   sacilma    sinama   sacilma
    1     0.7786    0.0193    0.7627    0.0088
    3     0.7944    0.0136    0.7762    0.0102
    5     0.8032    0.0096    0.7778    0.0148
   11     0.7984    0.0095    0.7722    0.0122
   21     0.8103    0.0105    0.7762    0.0082
   31     0.8183    0.0119    0.7754    0.0124
   41     0.8214    0.0075    0.7778    0.0066

Saçılma sütunları dersin ölçüsüdür. Tek ağaçta doğrulama saçılması 0,0193, 41 ağaçta 0,0075: beş koşum arasındaki fark 2,6 kat daralıyor. Ortalama 0,7786’dan 0,8214’e yükseliyor ama düzgün değil; 5 ağaçta 0,8032, 11 ağaçta 0,7984. Ağaç eklemek her adımda daha iyi bir sayı vermez; verdiği şey, tekrarda daha az oynayan bir sayıdır. Sınamada da öyle: 0,7627’den 0,7778’e, kazanç dört abone, saçılma 0,0088’den 0,0066’ya. Bedel 41 kat hesaptır.

Öznitelik Rastgeleliği ve Torba Dışı Kestirim

Torbalanmış ağaçlar birbirine benziyor, çünkü hepsi aynı on bir sütuna bakıp aynı güçlü sütunu kökte buluyor. İkinci bir rastgelelik kaynağı bunu kırar: her ağaç bölmelerini rastgele seçilmiş m sütunluk bir alt kümeden seçer. Izgara m değerini ikiden on bire, derinliği üçten sekize taşır. Üçüncü bir sayı daha üretilir: torba dışı (out-of-bag) kestirim her eğitim satırını yalnız o satırı torbasına almamış ağaçlara oylatır ve ayrılmış kümeye dokunmadan bir sayı verir.

def torba_disi(agaclar, torbalar):          # her satiri, onu gormeyen agaclar oylar
    dis = [(b, y, [d for d, c in zip(agaclar, torbalar) if i not in c])
           for i, (b, y) in enumerate(KE)]
    return sum((oy(v, b) > 0.5) == y for b, y, v in dis if v) / sum(1 for *_, v in dis if v)


ADAY, IZGARA = 7, {}
print(f"{'m':>3}" + "".join(f"{'derinlik ' + str(d):>16}" for d in (3, 4, 6, 8)))
for m in (2, 3, 4, 6, 8, 11):
    satir = []
    for derinlik in (3, 4, 6, 8):
        a, t = orman(TOHUM, 41, m, derinlik)
        IZGARA[(m, derinlik)] = (orman_dogruluk(a, KD), orman_dogruluk(a, KS),
                                 torba_disi(a, t))
        ADAY += 1
        satir.append(f"{IZGARA[(m, derinlik)][0]:.4f}/{IZGARA[(m, derinlik)][1]:.4f}")
    print(f"{m:>3}" + "".join(f"{q:>16}" for q in satir))
SIRA = [(m, d) for m in (2, 3, 4, 6, 8, 11) for d in (3, 4, 6, 8)]


def enustte(sutun):
    e = max(IZGARA[k][sutun] for k in SIRA)
    return next(k for k in SIRA if IZGARA[k][sutun] == e)


for ad, sutun in (("dogrulamadan", 0), ("sinamadan", 1), ("torba disindan", 2)):
    m, derinlik = enustte(sutun)
    d, s, o = IZGARA[(m, derinlik)]
    print(f"secim {ad:<15} m={m:<3} derinlik={derinlik:<3} "
          f"dogrulama {d:.4f}  sinama {s:.4f}  torba disi {o:.4f}")
m, derinlik = enustte(0)
print(f"denenen aday {ADAY}, ailenin sayisi {IZGARA[(m, derinlik)][1]:.4f}, "
      f"taban cizgisi ustu {IZGARA[(m, derinlik)][1] - taban(KS):+.4f}")

  m      derinlik 3      derinlik 4      derinlik 6      derinlik 8
  2   0.8135/0.7579   0.8135/0.7579   0.8135/0.7579   0.8135/0.7579
  3   0.8095/0.7540   0.8135/0.7579   0.8175/0.7619   0.8095/0.7579
  4   0.8175/0.7698   0.8214/0.7817   0.8175/0.7817   0.8254/0.7817
  6   0.8214/0.7778   0.8413/0.7897   0.8373/0.7937   0.8413/0.7857
  8   0.8254/0.7857   0.8214/0.7817   0.8254/0.7698   0.8294/0.7738
 11   0.8175/0.7857   0.8214/0.7778   0.8095/0.7698   0.8016/0.7698
secim dogrulamadan    m=6   derinlik=4   dogrulama 0.8413  sinama 0.7897  torba disi 0.7884
secim sinamadan       m=6   derinlik=6   dogrulama 0.8373  sinama 0.7937  torba disi 0.7950
secim torba disindan  m=6   derinlik=8   dogrulama 0.8413  sinama 0.7857  torba disi 0.7989
denenen aday 31, ailenin sayisi 0.7897, taban cizgisi ustu +0.0317

Üst satır rastgeleliğin sınırını gösteriyor: m iki olduğunda topluluk dört derinlikte de tam olarak taban çizgisini veriyor, çünkü iki sütunlu ağaçların oyu hiçbir aboneyi şüpheli tarafa geçirmiyor. m altı olduğunda doğrulamada 0,8413, sınamada 0,7897 çıkıyor; m on bir, yani rastgelelik yokken, sayı 0,7778’e geriliyor. Rastgeleliğin kattığı fark bu sütundur, üç ile dört abone.

Son üç satır kursun kuralını ödüyor. Doğrulamadan okunan seçim m altı ve derinlik dört diyor; o adayın sınama sayısı 0,7897. Sınamadan okunsaydı derinlik altı seçilir, sayı 0,7937 olurdu; fark 0,0040, tek abone. Küçük, ama yönü sabittir: seçim de ölçüm de aynı 252 satırdan yapılırsa sayı büyür.

Torba dışı sütunu daha keskin. Seçilen adayın doğrulama sayısı 0,8413, sınama sayısı 0,7897, torba dışı kestirimi 0,7884: sınamaya 0,0013, doğrulamaya 0,0516 uzakta. Torba dışı 756 satırdan okunur ve ayrılmış küme harcamaz; doğrulama 252 satırdan okunur ve her bakışta tükenir.

Ailenin sayısı 0,7897, denenen aday 31; taban çizgisinin 0,0318 üstünde. Asıl fark şurada: tek ağacın sayısı 0,6905 ile 0,7897 arasında bir çekilişti, topluluğunki değil.

Özet

• Aynı yordam 41 torba örnekleminde kök için dokuz ayrı alan-eşik çifti seçiyor; iki ağaç 252 abonenin ortalama 46,2’sini ayrı sınıflıyor.
• Tek ağacın sınama sayısı 0,6905 ile 0,7897 arasında geziniyor, saçılması 0,0246; tek örneklemden okunan sayı bu aralıktan rastgele seçilmiş bir noktadır.
• Ağaç sayısı 1’den 41’e çıkınca doğrulama saçılması 0,0193’ten 0,0075’e, ortalama 0,7786’dan 0,8214’e gidiyor; artış düzgün değil, düşüş düzgün.
• Öznitelik rastgeleliği olmadan torbalama tek ağacı geçmiyor: on bir sütun açıkken sınama 0,7698, tek ağaçta 0,7778; m altı olduğunda 0,7897.
• Torba dışı kestirim 0,7884, sınamaya 0,0013 ve doğrulamaya 0,0516 uzakta; ayrılmış küme harcamadan okunur.

Sonraki Adım

Torbalama ağaçları birbirinden bağımsız kurar: 41 ağacın hiçbiri ötekinin nerede yanıldığını bilmiyor, hepsi aynı problemi baştan çözüp sonunda oy veriyor. Bağımsızlık saçılmayı düşürdü, ortalamayı yalnız dört abone taşıdı. Ağaçlar birbirini görseydi ne olurdu: ikinci ağaç yalnız birincinin yanıldığı yere baksaydı, üçüncü ilk ikisinin kalan hatasına. Sonraki ders bu ardışık düzeni kurar ve iki ayar değişkenini karşı karşıya getirir: kaç tur sürüleceği ve her turun hangi büyüklükte bir adımla ekleneceği. İkisi birbirinin yerine geçer; aynı sayı küçük adımla çok turda ya da büyük adımla az turda çıkar ve iki yolun bütçesi aynı değildir.