Kümeleme Problemi

Denetimli öğrenme kursu yirmi derste yedi model ailesini aynı kurgu abone tablosunda denedi ve her sayının yanına bütçesini yazdı. Bu ölçümlerin hepsinin ortak bir dayanağı vardı ve o dayanak hiç sorgulanmadı — etiket. Taban çizgisi en sık etiketi söylüyordu, ölçüt tahmin edilen etiketle gerçeğini karşılaştırıyordu, ayar araması doğrulama kümesindeki etiketlere bakıyordu. Etiket sütunu kaldırıldığında bu üç mekanizmanın üçü birden çalışmaz.

Bu ders o durumla başlar. Elde etiketi olmayan bir tablo vardır ve amaç benzeyen aboneleri bir araya toplamaktır. Sorun yöntemin bulunmasında değil — bir bölmeleme üretmek kolaydır, rastgele atama da bir bölmeleme üretir. Sorun, üretilen bölmelemenin neye göre ölçüleceğindedir. Ölçü kurulmadan önce de daha temel bir karar durur: “benzer” sözcüğünün tanımı.

• KU1. Küme, bu kursta noktaların bir alt öbeğidir; M17’nin veritabanı kümesi bir sunucu öbeğiydi, veri kümesi ise satırların tamamıdır.
• KU2. Küme M27/K01–K03’ten gelen kurgu abone tablosudur: tohum 20260218, 1.260 abone, bölme 756/252/252. Yordam eğitim kümesindeki 756 abone üzerinde çalışır.
• KU3. Şüpheli sütunu bu kursta üretilmez. Hiçbir yöntem etiketi görmez; etiket yalnız konunun son dersinde, dış geçerlilik ölçülürken bir kez kullanılacaktır.
• KU4. Sütunlar altı sayısal alandır: ortalama tüketim, oynaklık, kişi başına tüketim, hane büyüklüğü, memnuniyet ve dönem sayısı. Bölge göstergeleri dışarıda kalır, çünkü iki bölge arasındaki “uzaklık” ikili sütunlarda her zaman aynı sabittir.
• KU5. Bölmeleme, her noktayı tam olarak bir kümeye atayan bir yerleştirmedir. Ölçüsü küme içi toplam uzaklıktır: her noktanın kendi kümesinin merkezine uzaklığının toplamı, nokta sayısına bölünmüş hali; küçük olması iyidir. M27/K01’in uygulama alanları dersinde basılan sayılar başka bir sütun kümesinden geldiği için tekrarlanmaz.
• KU6. Üç taban çizgisi kullanılır: rastgele atama, tek küme ve tek sütuna göre dilimleme. Rastgele atamanın sayısı beş tohumun ortalamasıdır; tek tohum kendi salınımını gizler.
• KU7. Küme sayısı 4’te, yordam da sabit tutulur: en uzak nokta tohumlamasıyla dört çekirdek seçilir ve iki düzeltme turu yapılır. Küme sayısının ayar değişkeni olması ve başlangıcın sonucu oynatması sonraki derse aittir; burada değişen tek şey benzerlik tanımıdır.
• KU8. Farklı tanımların sayıları birbiriyle karşılaştırılamaz, çünkü her tanım kendi uzaklığını ölçer; karşılaştırılabilir olan yalnız kendi tabanına göre farktır.

Benzerlik Tanımı Bir Seçimdir

Bir kümeleme yordamı “yakın” sözcüğünün karşılığını veriden öğrenmez; dışarıdan alır. Birinci tanım sütunları ham ölçekte bırakıp farkların karesini toplar: ortalama tüketimin aralığı hane büyüklüğünün aralığından yaklaşık on kat geniş olduğu için toplam sessizce bir ağırlıklandırmadır. İkincisi her sütunu standart puana çevirir ve altı sütun eşit ağırlık alır. Üçüncüsü her değeri sütun içindeki sırasının yüzdesine çevirip mutlak farkları toplar; uç değerler sıkışır, yalnız sıralama kalır.

Tanım yalnız uzaklığı değil, merkezin ne olduğunu da belirler: kare uzaklığı en küçüğe indiren merkez ortalama vektördür, mutlak farkı en küçüğe indiren merkez ortanca vektördür. Üç tanım tek bir abonenin en yakın komşusunu bile aynı seçmez.

# kumeleme.py — MODELDIR. M27/K01–K03'un KURGU abone tablosu ayni tohumla
# yeniden kurulur; supheli sutunu bu kursta uretilmez, hicbir yordam etiket gormez.
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]
N = len(EGT)
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)]
STD_V = [[(v[j] - ORT[j]) / SAP[j] for j in range(len(ALAN))] for v in HAM_V]


def sira_yuzdesi(sutun):                    # deger, sutundaki ortalama sirasinin yuzdesine doner
    s, yer = sorted(range(len(sutun)), key=lambda i: sutun[i]), {}
    for p, i in enumerate(s):
        yer.setdefault(sutun[i], []).append(p)
    orta = {v: statistics.fmean(p) / (len(s) - 1) for v, p in yer.items()}
    return [orta[x] for x in sutun]


SIRA_S = [sira_yuzdesi(c) for c in zip(*HAM_V)]
SIRA_V = [[SIRA_S[j][i] for j in range(len(ALAN))] for i in range(N)]


kare = lambda a, b: sum((p - q) * (p - q) for p, q in zip(a, b))
mutlak = lambda a, b: sum(abs(p - q) for p, q in zip(a, b))
ort_merkez = lambda g: [statistics.fmean(c) for c in zip(*g)]
ortanca_merkez = lambda g: [statistics.median(c) for c in zip(*g)]

TANIM = [("ham olcek, kare uzaklik", HAM_V, kare, ort_merkez),
         ("standart puan, kare uzaklik", STD_V, kare, ort_merkez),
         ("sira yuzdesi, mutlak fark", SIRA_V, mutlak, ortanca_merkez)]

print(f"kumelenen abone {N}, sutun {len(ALAN)}, etiket sutunu yok")
print(f"{'':<28}{'komsu':>7}" + "".join(f"{a:>12}" for a in ALAN))
print(f"{'abone 48 (kendisi)':<28}{'--':>7}" + "".join(f"{EGT[48][a]:>12.3f}" for a in ALAN))
for ad, V, uzak, _ in TANIM:
    j = min((x for x in range(N) if x != 48), key=lambda x: (uzak(V[48], V[x]), x))
    print(f"{ad:<28}{j:>7}" + "".join(f"{EGT[j][a]:>12.3f}" for a in ALAN))

kumelenen abone 756, sutun 6, etiket sutunu yok
                              komsu ort_tuketim    oynaklik   kisi_basi        hane  memnuniyet       donem
abone 48 (kendisi)               --      16.090      10.560       3.218       5.000       4.000       3.000
ham olcek, kare uzaklik         711      16.280      10.600       4.070       4.000       4.000       2.000
standart puan, kare uzaklik      52      13.540      11.990       2.708       5.000       4.000       3.000
sira yuzdesi, mutlak fark       241      17.400       9.830       2.900       6.000       4.000       3.000

Üç satır aynı aboneye üç ayrı komşu veriyor ve gerekçe her satırda görünüyor. Ham ölçekte seçilen 711 numaralı abonenin ortalama tüketimi 48 numaralınınkinden yalnız 0,19 uzakta; hane ve dönem sütunları tutmuyor ama bunların farkı toplama en çok 2 katıyor. Standart puanla seçilen 52 numaralı abonenin tüketimi 2,55 uzakta, buna karşılık hane, memnuniyet ve dönem sütunlarının üçü de tutuyor: bir sütundaki tam uyum bir sapmalık farkı dengeliyor.

Üç komşunun hiçbiri yanlış değildir. Üçü de “en yakın” tanımına uyuyor; yalnız üç ayrı tanıma.

Üç Taban Çizgisi

Küme içi toplam uzaklık tek başına yorumlanamaz; sayının büyük mü küçük mü olduğu, aynı ölçüyle üretilmiş bir karşılaştırma noktası olmadan bilinemez. Üç taban üç ayrı soruyu yanıtlar. Rastgele atama hiçbir yapı kullanmadan aynı sayıda küme üretir: “bu bölmeleme şanstan ne kadar iyi”. Tek küme noktaları bir arada tutar: “bölmek hiç bölmemeye göre ne kazandırdı”. Tek sütuna göre dilimleme noktaları ortalama tüketime göre dört eşit dilime böler: “bütün sütunlara bakmak, tek sütuna bakan bir çözüme göre ne kazandırdı”. Üçüncüsü en zorlu tabandır, çünkü öğrenmese de veriyi kullanır.

KUME = 4


def ic_uzaklik(V, uzak, merkez, atama):     # kume ici toplam uzaklik, nokta basina
    t = 0.0
    for c in set(atama):
        g = [V[i] for i in range(len(V)) if atama[i] == c]
        t += sum(uzak(v, merkez(g)) for v in g)
    return t / len(V)


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


def sutuna_gore(V, j, k):                   # TABAN 3: tek sutunu k esit dilime boler
    s, a = sorted(range(len(V)), key=lambda i: (V[i][j], i)), [0] * len(V)
    for p, i in enumerate(s):
        a[i] = min(k - 1, p * k // len(V))
    return a


def bolumle(V, uzak, merkez, k, tur=2):     # MODELDIR: en uzak nokta tohumlama + iki tur
    cek = [min(range(len(V)), key=lambda i: (uzak(V[i], merkez(V)), i))]
    while len(cek) < k:
        cek.append(max(range(len(V)),
                       key=lambda i: (min(uzak(V[i], V[c]) for c in cek), -i)))
    M = [V[c] for c in cek]
    for _ in range(tur + 1):
        a = [min(range(k), key=lambda c: uzak(v, M[c])) for v in V]
        M = [merkez([V[i] for i in range(len(V)) if a[i] == c]) for c in range(k)]
    return a


_, V2, U2, M2 = TANIM[1]
RAS = [ic_uzaklik(V2, U2, M2, rastgele_atama(N, KUME, TOHUM + 400 + t)) for t in range(5)]
A2 = bolumle(V2, U2, M2, KUME)
tek, ras = ic_uzaklik(V2, U2, M2, [0] * N), statistics.fmean(RAS)
dilim = ic_uzaklik(V2, U2, M2, sutuna_gore(V2, 0, KUME))
yon = ic_uzaklik(V2, U2, M2, A2)
print(f"standart puan, kare uzaklik tanimiyla, k = 4\n"
      f"  taban - tek kume          {tek:8.4f}\n"
      f"  taban - rastgele atama    {ras:8.4f}   (bes tohum: {min(RAS):.4f} - {max(RAS):.4f})\n"
      f"  taban - ort_tuketim dilim {dilim:8.4f}\n"
      f"  yontem                    {yon:8.4f}"
      f"   kume boylari {sorted(A2.count(c) for c in range(KUME))}\n"
      f"  fark: rastgeleye gore {ras - yon:+.4f}, dilime gore {dilim - yon:+.4f}")

standart puan, kare uzaklik tanimiyla, k = 4
  taban - tek kume            6.0000
  taban - rastgele atama      5.9790   (bes tohum: 5.9763 - 5.9819)
  taban - ort_tuketim dilim   4.9044
  yontem                      3.8910   kume boylari [61, 67, 117, 511]
  fark: rastgeleye gore +2.0880, dilime gore +1.0134

Tek kümenin sayısı tam olarak 6,0000, yani sütun sayısı. Bu bir rastlantı değil: her sütun standart puana çevrildiğinde birim değişkenlik taşır, dolayısıyla tek merkeze uzaklığın nokta başına toplamı sütun sayısına eşit çıkar. Ölçünün üst sınırı hesapla bilinir ve her bölmeleme bu 6,0000’ı ne kadar aşağı çektiğine göre okunur.

İkinci satır bu kursun en önemli sayısıdır. Rastgele atama 5,9790 veriyor — tek kümeden yalnız 0,0210 aşağıda. Dört rastgele gruba bölmek hiç bölmemeye göre neredeyse hiçbir şey kazandırmıyor, çünkü rastgele bir kümenin merkezi verinin genel merkezine düşüyor. Beş tohumun salınımı 0,0056, yani ölçülen farkların yanında ihmal edilebilir.

Üçüncü satır tabloyu değiştiriyor. Yalnız ortalama tüketime bakıp dört eşit dilime bölmek 4,9044 veriyor. Yöntemin sayısı 3,8910 ve fark hangi tabanın yazıldığına göre 2,0880 ya da 1,0134’tür. Dilimleme yazılmasaydı yöntem, altı sütuna birden bakmanın kazandırdığı 1,0134’ü kendi hanesine yazardı. Taban çizgisinin seçimi bir ölçüm kararıdır; gerekçesiyle yazılmadığında bildirilen fark bir bulgu değil bir seçimdir.

Aynı Küme, Üç Bölmeleme

Yordam ve küme sayısı sabit tutulup yalnız benzerlik tanımı değiştirildiğinde ne olduğu üçüncü blokta ölçülür. İki bölmelemenin ayrışması, kümeleri eşleştirmeden, nokta çiftleri üzerinden sayılır: 756 abonenin 285.390 çifti vardır ve her çift için iki bölmeleme “aynı kümede” ya da “ayrı kümelerde” der. Uyuşmazlık, farklı yanıt verdikleri çiftlerin oranıdır.

BOLME = []
print(f"{'tanim':<28}{'tek kume':>10}{'rastgele':>10}{'dilim':>10}"
      f"{'yontem':>10}{'rastgeleye gore pay':>21}")
for ad, V, uzak, merkez in TANIM:
    a = bolumle(V, uzak, merkez, KUME)
    BOLME.append((ad, a))
    tek = ic_uzaklik(V, uzak, merkez, [0] * N)
    ras = statistics.fmean(ic_uzaklik(V, uzak, merkez, rastgele_atama(N, KUME, TOHUM + 400 + t))
                           for t in range(5))
    sut = ic_uzaklik(V, uzak, merkez, sutuna_gore(V, 0, KUME))
    y = ic_uzaklik(V, uzak, merkez, a)
    print(f"{ad:<28}{tek:>10.4f}{ras:>10.4f}{sut:>10.4f}{y:>10.4f}{(ras - y) / ras:>21.3f}")


def uyusmazlik(a, b):                       # iki bolmeleme kac nokta ciftinde ayrisiyor
    ayrisan = sum((a[i] == a[j]) != (b[i] == b[j])
                  for i in range(len(a)) for j in range(i + 1, len(a)))
    return 2 * ayrisan / (len(a) * (len(a) - 1))


print("\nbolmelemeler arasi uyusmazlik (ayrisan nokta cifti orani)")
for i in range(3):
    for j in range(i + 1, 3):
        print(f"  {BOLME[i][0]:<28} - {BOLME[j][0]:<28} {uyusmazlik(BOLME[i][1], BOLME[j][1]):.4f}")
print("\nen buyuk kumenin ortalamalari")
for ad, a in BOLME:
    g = [EGT[i] for i in range(N) if a[i] == max(a, key=a.count)]
    print(f"  {ad:<28} n {len(g):>4}" + "".join(
        f"  {x}={statistics.fmean(k[x] for k in g):.2f}"
        for x in ("ort_tuketim", "oynaklik")))

tanim                         tek kume  rastgele     dilim    yontem  rastgeleye gore pay
ham olcek, kare uzaklik       130.6679  130.2948   92.4562   61.8604                0.525
standart puan, kare uzaklik     6.0000    5.9790    4.9044    3.8910                0.349
sira yuzdesi, mutlak fark       1.3983    1.3907    1.1475    0.9809                0.295

bolmelemeler arasi uyusmazlik (ayrisan nokta cifti orani)
  ham olcek, kare uzaklik      - standart puan, kare uzaklik  0.4192
  ham olcek, kare uzaklik      - sira yuzdesi, mutlak fark    0.4801
  standart puan, kare uzaklik  - sira yuzdesi, mutlak fark    0.3750

en buyuk kumenin ortalamalari
  ham olcek, kare uzaklik      n  509  ort_tuketim=17.40  oynaklik=6.86
  standart puan, kare uzaklik  n  511  ort_tuketim=19.18  oynaklik=11.97
  sira yuzdesi, mutlak fark    n  325  ort_tuketim=21.50  oynaklik=12.66

Birinci tablo okunurken bir kural işler: satırlar arasında karşılaştırma yapılamaz. 61,8604 ile 0,9809 aynı ölçünün iki değeri değildir; biri metreküp karesi, öteki yüzdelik farkların toplamı mertebesindedir. Karşılaştırılabilir olan tek sütun sağdaki paydır: her tanımın kendi rastgele tabanına göre kazancı sırasıyla 0,525, 0,349 ve 0,295. Ham ölçekte pay en yüksek çıkıyor, ama bu tanımı daha iyi yapmaz — orada toplam saçılmanın neredeyse tamamı tek bir sütundan geldiği için bölmek o sütunu kesmekle aynı şeydir. Payın büyüklüğü tanımın başarısını değil, veriye ne kadar tek yönlü baktığını ölçüyor.

İkinci tablo dersin asıl sonucudur. Üç bölmeleme, nokta çiftlerinin 0,3750 ile 0,4801 arası bir payında birbirinden ayrılıyor. Ham ölçek ile sıra yüzdesi arasındaki 0,4801, 285.390 çiftin 137.002’sinde iki bölmelemenin ters yanıt verdiği anlamına gelir. Bunlar aynı veriyi, aynı yordamla, aynı küme sayısıyla bölen üç koşumdur; değişen tek şey uzaklığın tanımıdır.

Üçüncü tablo farkın nerede oturduğunu gösteriyor. Ham ölçekte en büyük küme 509 abonelik ve ortalama oynaklığı 6,86 — düşük oynaklıklı orta tüketimliler bir arada. Standart puanda küme benzer boyda ama ortalama oynaklığı 11,97: oynaklık sütunu artık tüketim kadar söz sahibi. Sıra yüzdesinde en büyük küme 325’e düşüyor, çünkü uç değerler sıralamaya çevrilince noktaları birbirinden uzaklaştırmıyor.

Bu üç bölmelemeden birinin doğru olduğunu söyleyecek bir ölçüt yoktur. Her tanım kendi ölçüsünde kendi bölmelemesini en iyi bulur ve tanımlar arasında bir üst mahkeme kurulamaz, çünkü kurmak için yine bir uzaklık tanımı seçmek gerekir. Denetimli kursta bu soru etiketle kapanıyordu; burada kapanmaz.

Özet

• Etiket kaldırıldığında ölçünün üç bileşeni de kurulmak zorundadır: taban çizgisi, yöntemin sayısı ve fark. Kümelemede taban çizgisi hazır gelmez, seçilir ve gerekçelendirilir.
• Standart puan tanımında tek küme 6,0000, rastgele atama 5,9790 verir; öğrenmeyen bir bölmeleme ölçüyü nokta başına yalnız 0,0210 oynatır ve beş tohumdaki salınımı 0,0056’dır.
• Yöntemin sayısı 3,8910’dur; farkı rastgele tabana göre 2,0880, dilimleme tabanına göre 1,0134. Hangi tabanın yazıldığı bildirilen kazancı iki katına yakın oynatır.
• Üç benzerlik tanımı aynı 756 aboneyi aynı yordamla böldüğünde nokta çiftlerinin 0,3750 ile 0,4801 arası bir payında ayrışan üç bölmeleme çıkar; ham ölçek ile sıra yüzdesi 285.390 çiftin 137.002’sinde ters yanıt verir.
• Tanımların sayıları karşılaştırılamaz; okunabilen tek şey kendi tabanına göre oransal kazançtır ve o pay tanımın doğruluğunu değil, veriye ne kadar tek yönlü baktığını ölçer.

Sonraki Adım

Bu derste yordam bilerek dondurulmuştu: çekirdekler tek bir kuralla seçildi, iki düzeltme turu yapıldı, küme sayısı 4’te tutuldu. Üç sabitin üçü de birer karardır. Sonraki ders ikisini çözer: yineleme durana kadar sürdürüldüğünde ve çekirdekler rastgele seçildiğinde aynı küme sayısıyla kaç ayrı bölmeleme çıkıyor, en iyi ile en kötü koşum arasındaki fark ne kadar. Ardından küme sayısı bir ayar değişkeni olarak ele alınır; küme içi toplam uzaklık küme sayısı arttıkça tek yönde azaldığı için en iyi değeri gösteremez ve ardışık farkların oluşturduğu “dirsek” bir karar noktası olarak sayılır.