--- title: 'Hiyerarşik Kümeleme' source: 'https://academia.sh/tr/kurslar/denetimsiz-ogrenme/hiyerarsik-kumeleme' course: 'Denetimsiz Öğrenme' language: tr updated: '2026-08-17T18:10:22+00:00' license: 'CC BY-SA 4.0' --- # Hiyerarşik Kümeleme Küme sayısını girdi olmaktan çıkarıp kesme kararına dönüştüren bir aile ve o kararın bedeli: aynı 200 abonede tek, tam ve ortalama bağlantı aynı ilk birleştirmeden (0,079) başlayıp 2,245, 8,917 ve 4,994'te biter; 2,0 yüksekliğinden kesildiğinde sırasıyla 3, 56 ve 37 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; iki bağlantı 200 abonenin 86'sını ayrı yerlere düşürür. Ö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ık**tır, taban çizgileri **rastgele atama** ve **tek küme**dir. 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. ```python # 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. ```python 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. ```python 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.