Hiyerarşik Kümeleme

Önceki dersin yordamı küme sayısını başlamadan önce istiyordu ve her koşum tek bir bölmeleme üretiyordu. Üç ayrı k için üç ayrı arama yapıldığında çıkan üç sonuç birbiriyle ilişkisizdi: üç kümeli bölmelemenin kümeleri, beş kümeli bölmelemenin kümelerinin birleşimi değildi. Dirseğin üç ayrı okuması üç ayrı k seçtiğine göre bu, karar verilemeyen bir noktada üç ilişkisiz cevap demekti.

Bu ders sırayı tersine çevirir. Her abone kendi kümesiyle başlar, her adımda en yakın iki küme birleştirilir ve 200 aboneden tek kümeye kadar iç içe geçmiş bir aile üretilir. Küme sayısı artık girdi değildir; ağacın hangi yükseklikten kesildiği sorusunun yanıtıdır. Buna karşılık yeni bir karar belirir ve dersin ölçtüğü şey odur: “en yakın iki küme” ifadesi nokta uzaklığından türetilemez, çünkü iki küme arasındaki uzaklığın kendisi ayrıca tanımlanmalıdır.

• KU16. Küme, sütunlar ve benzerlik tanımı önceki dersteki gibidir; ölçek yine 756 abonelik eğitim kümesinden öğrenilir. Kümeleme ise ilk 200 abone üzerinde yapılır: birleştirmeli yordamın maliyeti nokta sayısının küpüyle büyür. Bu bir ölçek kararıdır ve buradaki sayılar 756 abone için değil, bu 200 abone içindir.
• KU17. Nokta uzaklığı standart puanlarda kare uzaklığın kareköküdür; birleştirme yükseklikleri sütun birimiyle okunabilsin diye karekök alınır.
• KU18. Bağlantı ölçütü, iki küme arasındaki uzaklığın tanımıdır. Üçü denenir: tek bağlantı en yakın nokta çiftini, tam bağlantı en uzak nokta çiftini, ortalama bağlantı bütün nokta çiftlerinin ortalamasını alır.
• KU19. Birleştirme yüksekliği, o adımda birleştirilen iki küme arasındaki bağlantı uzaklığıdır; ölçüte özgüdür ve ölçütler arasında karşılaştırılamaz.
• KU20. Yordam belirlenimcidir; başlangıç seçimi yoktur ve eşit uzaklıkta iki aday çıkarsa küçük numaralı çift seçilir.
• KU21. Ölçü yine küme içi toplam uzaklıktır, taban çizgileri rastgele atama ve tek kümedir. Ağaçtan k küme okumak için kökten başlanır ve en yüksek dal, k dal kalana kadar açılır.
• KU22. İki bölmelemenin ayrışması iki ölçüyle verilir: ayrışan nokta çifti oranı ve en iyi küme eşleştirmesiyle ayrı düşen nokta sayısı; ikincisi için dört kümenin 24 eşleştirmesi denenir.
• KU23. Ölçüt, önceki dersin yordamının doğrudan en küçüğe indirmeye çalıştığı sayıdır; hiyerarşik yordamlar onu hedeflemez. Karşılaştırma bu yüzden ölçütün lehinedir.

Birleştirerek Kurulan Ağaç

Yordamın iskeleti kısadır: kümeler arası uzaklıklar tutulur, en küçüğü bulunur, iki küme birleştirilir ve yeni kümenin ötekilere uzaklığı bağlantı ölçütünün kuralıyla eskilerinden hesaplanır. Bu son adım yordamı ucuzlatır — birleşme sonrası hiçbir nokta çiftine yeniden bakılmaz. Üç ölçüt yalnız o tek satırda ayrılır.

# hiyerarsik.py — MODELDIR. Ayni KURGU abone tablosu, ayni tohum, ayni standart
# puan tanimi; etiket yine uretilmez.
import itertools
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]

ALT = 200
W = V[:ALT]
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)]
uzak = lambda a, b: math.sqrt(kare(a, b))

BAGLANTI = {"tek": lambda da, db, na, nb: min(da, db),
            "tam": lambda da, db, na, nb: max(da, db),
            "ortalama": lambda da, db, na, nb: (na * da + nb * db) / (na + nb)}


def birlestir(kural):                       # MODELDIR: en yakin iki kumeyi birlestir
    D = {(i, j): uzak(W[i], W[j]) for i in range(ALT) for j in range(i + 1, ALT)}
    ikili = lambda x, y: (x, y) if x < y else (y, x)
    etkin, boy, cocuk, yukseklik, yeni = list(range(ALT)), {i: 1 for i in range(ALT)}, {}, {}, ALT
    while len(etkin) > 1:
        a, b = min(((x, y) for i, x in enumerate(etkin) for y in etkin[i + 1:]),
                   key=lambda p: (D[ikili(*p)], p))
        cocuk[yeni], yukseklik[yeni] = (a, b), D[ikili(a, b)]
        for c in etkin:
            if c not in (a, b):
                D[ikili(c, yeni)] = kural(D[ikili(a, c)], D[ikili(b, c)], boy[a], boy[b])
        boy[yeni] = boy[a] + boy[b]
        etkin = [c for c in etkin if c not in (a, b)] + [yeni]
        yeni += 1
    return cocuk, yukseklik, boy, yeni - 1


AGAC = {ad: birlestir(kural) for ad, kural in BAGLANTI.items()}
print(f"alt kume {ALT} abone; her baglanti olcutu {ALT - 1} birlestirme yapti")
for ad, (_, yukseklik, _, _) in AGAC.items():
    h = sorted(yukseklik.values())
    print(f"  {ad:<9} en kucuk birlestirme {h[0]:.3f}, ortanca {statistics.median(h):.3f}, "
          f"son uc {h[-3]:.3f} {h[-2]:.3f} {h[-1]:.3f}")

alt kume 200 abone; her baglanti olcutu 199 birlestirme yapti
  tek       en kucuk birlestirme 0.079, ortanca 0.896, son uc 1.977 2.173 2.245
  tam       en kucuk birlestirme 0.079, ortanca 1.211, son uc 6.370 6.791 8.917
  ortalama  en kucuk birlestirme 0.079, ortanca 1.086, son uc 4.536 4.715 4.994

Üç ölçüt de aynı yerden başlıyor. İlk birleştirme her üçünde 0,079; tek nokta içeren iki küme arasında en yakın, en uzak ve ortalama çift aynı çift olduğu için ölçütler tek elemanlı kümelerde ayrışamaz. Ayrışma kümeler büyüdükçe başlıyor ve tepede uçurum var: son birleştirme tek bağlantıda 2,245, ortalama bağlantıda 4,994, tam bağlantıda 8,917. Yükseklik verinin değil ölçütün birimidir ve iki ağacın yükseklikleri yan yana okunamaz.

Ağaç Şeması ve Kesme Yüksekliği

Ağaç metin olarak basılır: her satır bir dalı, girinti dalın derinliğini, h birleştirme yüksekliğini, n dalın altındaki abone sayısını verir. Üç düzeyle sınırlandırılmıştır, daha derin dallar tek satırda özetlenir.

def sema(ad, ust=3, en_az=15):
    cocuk, yukseklik, boy, kok = AGAC[ad]
    print(f"agac semasi — {ad} baglanti, ust {ust} duzey")
    yig = [(kok, 0)]
    while yig:
        d, dr = yig.pop()
        if d in cocuk and boy[d] >= en_az and dr < ust:
            print(f"  {'  ' * dr}h={yukseklik[d]:.3f}  n={boy[d]}")
            yig.extend((c, dr + 1) for c in sorted(cocuk[d], key=lambda c: boy[c]))
        else:
            print(f"  {'  ' * dr}dal       n={boy[d]}")


sema("ortalama")
sema("tek")


def kume_sayisi(ad, h):                     # h yuksekliginin ustunde kac birlestirme kaldi
    _, yukseklik, _, _ = AGAC[ad]
    return sum(1 for y in yukseklik.values() if y > h) + 1


print(f"\n{'kesme yuksekligi':>18}" + "".join(f"{ad:>12}" for ad in BAGLANTI))
for h in (1.0, 1.5, 2.0, 3.0, 4.0, 5.0):
    print(f"{h:>18.1f}" + "".join(f"{kume_sayisi(ad, h):>12}" for ad in BAGLANTI))

agac semasi — ortalama baglanti, ust 3 duzey
  h=4.994  n=200
    h=4.715  n=198
      h=3.704  n=181
        dal       n=140
        dal       n=41
      h=4.536  n=17
        dal       n=15
        dal       n=2
    dal       n=2
agac semasi — tek baglanti, ust 3 duzey
  h=2.245  n=200
    h=2.173  n=199
      h=1.977  n=198
        dal       n=197
        dal       n=1
      dal       n=1
    dal       n=1

  kesme yuksekligi         tek         tam    ortalama
               1.0          62         123         114
               1.5          16          80          59
               2.0           3          56          37
               3.0           1          26          10
               4.0           1          13           4
               5.0           1           9           1

İki şema iki ayrı ağaç gösteriyor. Ortalama bağlantıda kök 200’ü 198 ile 2’ye, sonra 181 ile 17’ye, sonra 140 ile 41’e ayırıyor; her adımda iki yanı da dolu bir bölünme var. Tek bağlantıda ise her adımda tek bir abone kopuyor: 200’den 199, ondan 198, ondan 197. Sebep ölçütün tanımındadır — en yakın çifte bakıldığı için büyük bir kümeye yakın duran her nokta o kümeye eklenir. Ağaç bir zincire dönüşür ve üstten kesildiğinde verdiği şey bir bölmeleme değil, tek küme artı birkaç tek noktadır.

Alt tablo kesme yüksekliğinin ne olduğunu gösteriyor. 2,0 yüksekliğinden kesmek tek bağlantıda 3, ortalama bağlantıda 37, tam bağlantıda 56 küme verir; tek bir sayı, üç ölçütte on sekiz kat oynayan bir küme sayısına karşılık geliyor. 5,0’da tek ve ortalama bağlantı 1 küme derken tam bağlantı hâlâ 9 küme sayıyor. Kesme yüksekliği bu yüzden bir gözlem değil bir karardır; küme sayısını ağaçtan okuma iddiası, kararın yerini değiştirmekten başka bir şey yapmaz.

Bağlantı Ölçütünün Oynattığı Bölmeleme

Üç ağaç dört kümeye kadar açılıp aynı ölçüyle, aynı tabanla karşılaştırılır. Yanına önceki dersin merkez temelli yordamı da aynı 200 abone üzerinde konur.

def kesim_k(ad, k):                         # kokten baslayip en yuksek dali k'ya kadar ac
    cocuk, yukseklik, _, kok = AGAC[ad]
    dallar = [kok]
    while len(dallar) < k:
        d = max((x for x in dallar if x in cocuk), key=lambda x: yukseklik[x])
        dallar = [x for x in dallar if x != d] + list(cocuk[d])
    a = [0] * ALT
    for c, d in enumerate(dallar):
        yig = [d]
        while yig:
            x = yig.pop()
            if x in cocuk:
                yig.extend(cocuk[x])
            else:
                a[x] = c
    return a


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


def uyusmazlik(a, b):
    ay = sum((a[i] == a[j]) != (b[i] == b[j]) for i in range(ALT) for j in range(i + 1, ALT))
    return 2 * ay / (ALT * (ALT - 1))


def ayri_nokta(a, b, k):                    # en iyi kume eslestirmesiyle uyusmayan nokta
    return ALT - max(sum(p[a[i]] == b[i] for i in range(ALT))
                     for p in itertools.permutations(range(k)))


def k_ortalamalar(k, tohum, kosum=12):      # 02. dersin yordami, ayni alt kumede
    r, en_iyi = uretec(tohum), None
    for _ in range(kosum):
        s = []
        while len(s) < k:
            j = int(r() * ALT)
            if j not in s:
                s.append(j)
        M, a = [W[j] for j in s], None
        for _tur in range(60):
            y = [min(range(k), key=lambda c: kare(v, M[c])) for v in W]
            if y == a:
                break
            a = y
            M = [merkez([W[i] for i in range(ALT) if a[i] == c]) or M[c] for c in range(k)]
        u = ic_uzaklik(a, k)
        en_iyi = u if en_iyi is None else min(en_iyi, u)
    return en_iyi


def rastgele_atama(k, tohum):               # TABAN: hicbir yapi kullanmaz
    r = uretec(tohum)
    return [int(r() * k) for _ in range(ALT)]


K = 4
P = {ad: kesim_k(ad, K) for ad in BAGLANTI}
taban = statistics.fmean(ic_uzaklik(rastgele_atama(K, TOHUM + 33300 + t), K) for t in range(5))
print(f"k = {K}, {ALT} abone")
print(f"  {'taban - tek kume':<24} {ic_uzaklik([0] * ALT, K):.4f}")
print(f"  {'taban - rastgele atama':<24} {taban:.4f}")
for ad in BAGLANTI:
    u = ic_uzaklik(P[ad], K)
    print(f"  {ad + ' baglanti':<24} {u:.4f}   fark {taban - u:+.4f}"
          f"   kume boylari {sorted(P[ad].count(c) for c in range(K))}")
print(f"  {'k-ortalamalar (12 kosum)':<24} {k_ortalamalar(K, TOHUM + 44400):.4f}")
print("\nbaglanti olcutleri arasi ayrisma")
A = list(BAGLANTI)
for i in range(3):
    for j in range(i + 1, 3):
        print(f"  {A[i]:<9} - {A[j]:<9} nokta cifti {uyusmazlik(P[A[i]], P[A[j]]):.4f}, "
              f"ayri dusen nokta {ayri_nokta(P[A[i]], P[A[j]], K):>3} / {ALT}")

k = 4, 200 abone
  taban - tek kume         6.3473
  taban - rastgele atama   6.2340
  tek baglanti             6.0849   fark +0.1492   kume boylari [1, 1, 1, 197]
  tam baglanti             4.5419   fark +1.6922   kume boylari [6, 16, 65, 113]
  ortalama baglanti        5.0080   fark +1.2260   kume boylari [2, 2, 15, 181]
  k-ortalamalar (12 kosum) 3.4245

baglanti olcutleri arasi ayrisma
  tek       - tam       nokta cifti 0.5451, ayri dusen nokta  86 / 200
  tek       - ortalama  nokta cifti 0.1477, ayri dusen nokta  17 / 200
  tam       - ortalama  nokta cifti 0.4673, ayri dusen nokta  82 / 200

Tek bağlantının sayısı 6,0849 ve rastgele atama tabanını yalnız 0,1492 geçiyor. Küme boyları gerekçeyi veriyor: [1, 1, 1, 197]. Dört küme istendi, üç tanesi tek abone; sonuç öğrenmeyen bir yordamdan ayırt edilemeyecek kadar ona yakın. Tam bağlantı 4,5419 ile tabanı 1,6922 geçiyor ve boyları [6, 16, 65, 113] — en dengeli bölmeleme onunki, çünkü en uzak çifte bakan ölçüt geniş kümeleri cezalandırıyor. Ortalama bağlantı ikisinin arasında: 5,0080, fark 1,2260. Bağlantı ölçütünün seçimi, tabanı geçen farkı 0,1492 ile 1,6922 arasında, yani on bir kattan fazla oynatıyor.

Alt tablo aynı şeyi bölmeleme düzeyinde sayıyor. Tek ile tam bağlantı nokta çiftlerinin 0,5451’inde ayrışıyor ve en iyi eşleştirmeyle bile 86 abone ayrı yerlere düşüyor — 200 abonenin kırk üç yüzdesi. Tek ile ortalama bağlantı arasındaki ayrışma çok daha küçük, 17 abone; ortalama bağlantı da bir büyük kümeye eğilimli olduğu için tekle akraba kalıyor. Tam ile ortalama bağlantı ise 82 abonede ayrışıyor.

Son satırdaki 3,4245 dikkatli okunmalıdır. Önceki dersin merkez temelli yordamı bu ölçüde üçünü de açık farkla geçiyor, ama ölçü onun doğrudan en küçüğe indirmeye çalıştığı sayıdır; hiyerarşik yordamlar hiçbir adımda bu toplamı hesaplamaz bile. Karşılaştırma yordamların değerini değil, ölçütün kimin tarafında durduğunu gösteriyor. Ölçütü bağlantı uzaklıklarının tutarlılığı ya da zincirlemeye direnç olarak seçseydik sıralama tersine dönerdi.

Özet

• Birleştirmeli yordam küme sayısını girdi olmaktan çıkarır; iç içe geçmiş bir küme ailesi üretir ve karar kesme yüksekliğine taşınır.
• Üç bağlantı ölçütü aynı ilk birleştirmeden (0,079) başlar ama kökleri 2,245, 4,994 ve 8,917’dir; yükseklik ölçütün birimidir ve ölçütler arasında karşılaştırılamaz.
• 2,0 yüksekliğinden kesmek tek bağlantıda 3, ortalama bağlantıda 37, tam bağlantıda 56 küme verir.
• Dört kümede tek bağlantı 6,0849 ile rastgele atama tabanını yalnız 0,1492 geçer ve [1, 1, 1, 197] üretir; tam bağlantı 4,5419 ile 1,6922 geçer. Ölçütün seçimi farkı on bir kattan fazla oynatır.
• Tek ile tam bağlantı 200 abonenin 86’sını en iyi eşleştirmede bile ayrı yerlere düşürür; merkez temelli yordamın 3,4245’i ise ölçünün onun hedefi olmasıyla birlikte okunur.

Sonraki Adım

Üç derste dört yordam denendi — tek geçişli merkez seçimi, yinelemeli merkez güncellemesi ve üç bağlantı ölçütü — ve hepsi tek bir varsayımı paylaştı: her nokta bir kümeye atanmak zorundadır. Tek bağlantının [1, 1, 1, 197] bölmelemesi bu varsayımın bedelini gösteriyor. Üç abone kendi başına duruyor ama yordam onları “küme” ilan etmek zorunda kaldı, çünkü elinde başka bir kutu yok. Aynı biçimde, tam bağlantının 113 abonelik kümesinin kenarında duran ve hiçbir merkeze gerçekten yakın olmayan noktalar da bir kümeye yazıldı. Hiçbir kümeye ait olmayan nokta diye bir şey yoktu. Sonraki ders bu varsayımı kaldıran bir aileyi alır — noktaların yoğunluğuna bakan, seyrek bölgelerdeki noktaları gürültü olarak dışarıda bırakan ve küme sayısını hiç sormayan bir yordam — ve dışarıda bırakılan nokta sayısının kendisi bir ölçüye dönüşür.