İşbirlikçi Süzgeçleme

Önceki ders öneriyi kalemin özniteliklerinden üretti. Her kalemin alanı, kanalı ve ücretli olup olmadığı katalogda yazılıydı; abonenin geçmişinden bir profil çıkarıldı ve kalemler o profile benzerliklerine göre sıralandı. O kurulumda her abone kendi başınadır: dosyasında ne varsa ona bakılır, başka hiçbir abonenin dosyasına bakılmaz. Oysa elde 360 abonelik bir tablo duruyor ve içinde hiç kullanılmamış bir bilgi var: aboneler birbirine benziyor. İki abone de taksitlendirme ve borç yapılandırmaya başvurmuşsa, birinin başvurduğu üçüncü kalem öbürü için de bir adaydır — ve bu tahmin, kalemlerin özniteliklerine hiç bakmadan yapılabilir.

İşbirlikçi süzgeçleme budur: öneri, kalemin ne olduğundan değil, kimlerin birlikte kullandığından üretilir. Bu dersin ölçtüğü iki şey var. Birincisi, kaç komşuya bakıldığının sıralamayı ne kadar oynattığı. İkincisi, dizey seyrekleştikçe komşuluğun nerede kırıldığı — çünkü ortak kalemi olmayan iki abone arasında benzerlik tanımlı değildir ve seyreklik tam olarak bunu üretir.

• ON21. Kurgu küme, ayırma kuralı ve ölçüt birinci dersten aynen sürer: 360 abone, 24 hizmet kalemi, tohum 20260218, en az iki etkileşimi olan abonenin son etkileşimi ayrılmış kümeye gider. Kod burada yeniden kurulur, sayılar değişmez.
• ON22. Kalem kataloğundan bu derste yalnız alan ve taban payı okunur; öznitelikler önceki dersin konusuydu ve işbirlikçi süzgeçleme onlara hiç bakmaz.
• ON23. Ölçü isabet@5 ve yanında ortalama sıradır. Birincinin yönü büyük iyidir, ikincininki küçük iyidir. Aday kümesi abonenin eğitimde görülmemiş kalemleridir.
• ON24. Taban çizgisi birinci dersteki en çok seçilen kalem sırasıdır; hiçbir abone ayrımı yapmaz ve bu kursta bir öneri yönteminin geçmesi gereken eşiktir.
• ON25. Benzerlik, iki ikili vektörün ortak kalem sayısının uzunluklarının köküne bölünmesidir. Ortak kalemi olmayan çift benzerlik listesine hiç girmez; sıfır benzerlik kaydedilmez ve bu, komşusuzluğun tanımıdır.
• ON26. Komşu sayısı $K$ bir ayar değişkenidir. Kullanıcı temelli tarafta 7, öğe temelli tarafta 6 aday denenmiştir; ayrı bir ayar kümesi ayrılmamıştır, çünkü ölçülen şey en iyi ayar değil, ayarın sıralamayı ne kadar oynattığıdır.
• ON27. Eşit puanlı kalemler arasında sıra katalog indisiyle çözülür. Katalog taban payına göre azalan sıradadır, dolayısıyla puanı sıfır olan bir abone için sıralama sessizce popülerlik sırasına düşer. Bu, son bölümde ayrıca ölçülür.
• ON28. Gösterilen kalem sayısı, sınav abonelerinin ilk beşlerinin birleşimidir ve kursun üçüncü sayısıdır: hiç gösterilmeyen kalem hiç seçilmez.
• ON29. Seyreklik süpürmesinde eğitim etkileşimlerinin bir payı tutulur, ayrılmış kalemler hiç değişmez; böylece beş satır aynı 167 abone üzerinde okunur.

Ortak Kalem Olmadan Komşu Yok

İlk blok kurguyu, ayırmayı ve taban çizgisini kurar.

# Kurgu katalog birinci dersten gelir; burada yalniz kalemin alani ve taban payi gerekir.
TOHUM, M32, N_ABONE = 20260218, 0xFFFFFFFF, 360
KALEM = [("odeme", 0.90), ("bildirim", 0.85), ("bildirim", 0.78), ("odeme", 0.62),
         ("olcum", 0.55), ("bildirim", 0.50), ("odeme", 0.44), ("sozlesme", 0.40),
         ("olcum", 0.36), ("bildirim", 0.32), ("odeme", 0.28), ("sozlesme", 0.25),
         ("olcum", 0.22), ("tesisat", 0.19), ("olcum", 0.16), ("sozlesme", 0.14),
         ("tesisat", 0.12), ("sozlesme", 0.10), ("olcum", 0.09), ("sozlesme", 0.08),
         ("tesisat", 0.07), ("odeme", 0.06), ("bildirim", 0.05), ("tesisat", 0.04)]
KESIM = {
    "tasarruf": {"odeme": 0.5, "olcum": 1.7, "sozlesme": 0.6, "bildirim": 1.5, "tesisat": 0.6},
    "odeme":    {"odeme": 1.9, "olcum": 0.5, "sozlesme": 0.6, "bildirim": 1.1, "tesisat": 0.3},
    "isyeri":   {"odeme": 0.7, "olcum": 0.9, "sozlesme": 1.6, "bildirim": 0.7, "tesisat": 1.9},
    "yeni":     {"odeme": 0.8, "olcum": 0.7, "sozlesme": 1.8, "bildirim": 1.3, "tesisat": 0.7}}
KESIM_AD, N_KALEM = list(KESIM), len(KALEM)


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


ABONE, ETKILESIM = [], {}
for i in range(N_ABONE):
    r = uretec(TOHUM + 7919 * i)
    a, kesim = 20001 + i, KESIM_AD[int(r() * 4)]
    etkinlik = 0.35 + 1.15 * r() ** 1.6
    ABONE.append(a)
    for j, (alan, pay) in enumerate(KALEM):
        egilim = min(0.95, KESIM[kesim][alan] * pay * etkinlik * 0.55)
        if r() < min(0.95, pay ** 0.55 * 0.72):     # sunulmus mu
            if r() < egilim:                        # secilmis mi
                ETKILESIM[(a, j)] = r()             # deger: sira damgasi
                if r() < 0.32:
                    r()                             # puan birakilmis; burada kullanilmaz
        else:
            r(), r(), r()

KAYIT, EGIT, AYRI = {}, {}, {}
for (a, j), damga in ETKILESIM.items():
    KAYIT.setdefault(a, []).append((damga, j))
GORULEN = {a: set() for a in ABONE}
for a, lst in KAYIT.items():
    lst.sort()
    if len(lst) >= 2:                                # ayirma kurali birinci derstendir
        AYRI[a] = lst[-1][1]
        lst = lst[:-1]
    for damga, j in lst:
        EGIT[(a, j)] = 1
        GORULEN[a].add(j)

SINAV = sorted(AYRI)
PAY = [sum(1 for (a, j) in EGIT if j == jj) for jj in range(N_KALEM)]


def olc(puan, gor=None, kimler=None, k=5):
    gor, kimler = gor or GORULEN, kimler or SINAV
    isabet, sira, gosterilen = 0, 0, set()
    for a in kimler:
        s = puan(a)
        aday = sorted((j for j in range(N_KALEM) if j not in gor[a]),
                      key=lambda j: (-s[j], j))
        gosterilen.update(aday[:k])
        p = aday.index(AYRI[a])
        isabet, sira = isabet + (p < k), sira + p + 1
    return isabet / len(kimler), sira / len(kimler), len(gosterilen)


print("etkilesim", len(ETKILESIM), "-- egitim", len(EGIT), "-- sinav abonesi", len(AYRI))
print("egitim dizeyinin seyrekligi",
      round(1 - len(EGIT) / (N_ABONE * N_KALEM), 4))
print("taban -- en cok secilen kalem: isabet@5 %.4f, ort sira %.2f, gosterilen %d/24"
      % olc(lambda a: PAY))

etkilesim 577 -- egitim 410 -- sinav abonesi 167
egitim dizeyinin seyrekligi 0.9525
taban -- en cok secilen kalem: isabet@5 0.6527, ort sira 4.74, gosterilen 9/24

Ayrılan kalemler çıkınca eğitim dizeyinin seyrekliği 0,9525’e çıkıyor. Üç yüz altmış satır, yirmi dört sütun ve 410 dolu hücre: yöntemin komşuluk kuracağı bütün malzeme budur.

Kullanıcı Temelli: Komşu Sayısı Sıralamayı Oynatıyor

Benzerlik yordamı bir kez yazılır ve iki yerde kullanılır — abonelerin kalem kümeleri verilirse abone benzerliği, kalemlerin abone kümeleri verilirse kalem benzerliği çıkar. Bir abonenin bir kaleme puanı, en benzer $K$ komşusundan o kaleme sahip olanların benzerlik toplamıdır.

def benzerlikler(kume, anahtar):
    n = {u: max(1e-9, len(kume[u])) ** 0.5 for u in anahtar}
    cikti = {}
    for u in anahtar:
        b = [(len(kume[u] & kume[v]) / (n[u] * n[v]), v)
             for v in anahtar if v != u and kume[u] & kume[v]]
        b.sort(key=lambda t: (-t[0], t[1]))
        cikti[u] = b
    return cikti


def kullanici_temelli(B, gor, K):
    def puan(a):
        s = [0.0] * N_KALEM
        for w, v in B[a][:K]:
            for j in gor[v]:
                s[j] += w
        return s
    return puan


def ilk_k(puan, a, gor, k=5):
    s = puan(a)
    return set(sorted((j for j in range(N_KALEM) if j not in gor[a]),
                      key=lambda j: (-s[j], j))[:k])


BENZ = benzerlikler(GORULEN, ABONE)
TABAN5 = {a: ilk_k(lambda x: PAY, a, GORULEN) for a in SINAV}
print(f"{'K':>4} {'isabet@5':>9} {'ort sira':>9} {'gosterilen':>11} "
      f"{'onceki K':>9} {'tabanla':>8}")
onceki = None
for K in (3, 5, 10, 20, 40, 80, 160):
    p = kullanici_temelli(BENZ, GORULEN, K)
    i, s, kap = olc(p)
    su = {a: ilk_k(p, a, GORULEN) for a in SINAV}
    o = ("%.2f" % (sum(len(su[a] & onceki[a]) for a in SINAV) / len(SINAV))
         if onceki else "--")
    t = sum(len(su[a] & TABAN5[a]) for a in SINAV) / len(SINAV)
    print(f"{K:>4} {i:>9.4f} {s:>9.2f} {kap:>11} {o:>9} {t:>8.2f}")
    onceki = su

   K  isabet@5  ort sira  gosterilen  onceki K  tabanla
   3    0.6946      4.66          16        --     4.07
   5    0.6886      4.64          18      4.89     4.01
  10    0.6707      4.80          19      4.71     3.85
  20    0.6168      5.25          20      4.51     3.62
  40    0.5988      5.54          20      4.14     3.49
  80    0.6467      5.28          18      4.08     3.96
 160    0.6647      5.18          14      4.72     4.12

En iyi ayar üç komşuda 0,6946, tabandan 0,0419 yukarıda. Ama aynı sütunun en kötü adayı kırk komşuda 0,5988, yani tabandan 0,0539 aşağıda. Yedi aday arasındaki oynama 0,0958’dir ve yöntemin en iyi ayarıyla tabanı geçtiği farkın iki katından fazladır. Komşu sayısı burada yöntemin bir ayrıntısı değil, sonucunu belirleyen şeydir: kötü seçilmiş bir $K$ ile işbirlikçi süzgeçleme hiçbir abone ayrımı yapmayan listeden daha kötüdür.

Altıncı sütun kazancın ne kadar dar olduğunu söylüyor. En iyi ayarda ilk beş listesinin 4,07’si zaten taban listesinin kalemidir; yöntem beş kalemden yalnız birini değiştirerek 0,0419 kazanıyor. Kırk komşuda örtüşme 3,49’a iniyor, yani liste en çok orada kişiselleşiyor — ve isabetin en düşük olduğu yer de orasıdır. Yüz altmışta örtüşme 4,12’ye geri tırmanıyor, çünkü komşu sayısı abone sayısının yarısına yaklaştığında ağırlıklı toplam bütün kümenin ortalamasına, yani popülerliğe yakınsıyor. Ayar değişkeni iki uçta da tabana çıkar.

Beşinci sütun oynaklığı doğrudan sayıyor: komşu sayısı bir adım değiştiğinde ilk beşin en iyi durumda 4,89’u, en kötü durumda 4,08’i yerinde kalıyor — her adımda ortalama bir kalem yer değiştiriyor.

Kazancın asıl göründüğü yer dördüncü sütundur. Taban 167 abonenin tamamına yalnız 9 ayrı kalem gösteriyordu. Kullanıcı temelli kurulum en iyi ayarında 16, yirmi komşuda 20 kalem gösteriyor. Yöntem isabette 0,0419 kazanırken kataloğun görünen kısmını neredeyse iki katına çıkarıyor, ve gösterilmeyen kalem bir sonraki dönemin verisine de girmediği için bu ikinci sayı birincisinden daha uzun ömürlüdür.

Öğe Temelli: Aynı Yordam, Dizeyin Öbür Kenarı

Aynı benzerlik yordamı dizeyin sütunlarına uygulanır: her kalem, kendisini seçen abonelerin kümesiyle temsil edilir ve iki kalem ortak abonelerinin sayısına göre benzeşir. Bir abonenin puanı, kendi kalemlerinin en benzer $K$ komşusuna dağıtılır. Bu sayım M27/K04’te ölçülen kaldıraçla aynı ham malzemeyi kullanır — iki kalemin birlikte görülme sayısı — ama orada bir kural çıkarılıyordu, burada bir sıralama üretiliyor ve kural çıkarma yordamı tekrarlanmıyor.

KGOR = {j: set(a for a in ABONE if j in GORULEN[a]) for j in range(N_KALEM)}
KBENZ = benzerlikler(KGOR, list(range(N_KALEM)))


def oge_temelli(K):
    def puan(a):
        s = [0.0] * N_KALEM
        for i in GORULEN[a]:
            for w, j in KBENZ[i][:K]:
                s[j] += w
        return s
    return puan


print(f"{'K':>4} {'isabet@5':>9} {'ort sira':>9} {'gosterilen':>11} {'tabanla':>8}")
for K in (2, 3, 5, 8, 12, 23):
    i, s, kap = olc(oge_temelli(K))
    su = {a: ilk_k(oge_temelli(K), a, GORULEN) for a in SINAV}
    t = sum(len(su[a] & TABAN5[a]) for a in SINAV) / len(SINAV)
    print(f"{K:>4} {i:>9.4f} {s:>9.2f} {kap:>11} {t:>8.2f}")

   K  isabet@5  ort sira  gosterilen  tabanla
   2    0.6467      5.20          18     3.37
   3    0.6467      5.21          18     3.32
   5    0.5329      5.75          21     2.93
   8    0.5329      6.03          21     3.00
  12    0.5329      6.50          21     2.95
  23    0.5449      6.48          21     2.92

Öğe temelli kurulumun en iyi adayı 0,6467, yani tabanın altında. Altı adayın hiçbiri 0,6527’yi geçmiyor. Bu, kullanıcı temelli tarafla karşılaştırıldığında ters bir sonuçtur ve nedeni sayılabilir: sınav abonelerinin eğitim kümesinde ortalama 1,78 kalemi var. Öğe temelli puan bu bir buçuk kalemin komşuluklarına dağıtılıyor, dolayısıyla toplam neredeyse tek bir kalemin komşu listesinden ibaret kalıyor. Kullanıcı temelli tarafta ise toplam üç ayrı abonenin bütün geçmişini topluyor. Seyrek dizeyde hangi kenarın daha çok gözlem taşıdığı yöntemin sırasını belirliyor, ve bu kurguda o kenar satırlardır.

Kurulumun kazandığı yer yine dördüncü sütundur: 21 kalem gösteriyor ve taban listesiyle örtüşmesi hiçbir ayarda 3,37’yi aşmıyor. Öğe temelli sıralama daha kişiselleşmiş ve daha geniş kapsamalıdır; bu kurguda bunun bedelini isabetten ödüyor. Aynı veride iki kurulum, aynı ölçüde iki ayrı yönde hareket ediyor.

Seyreklik Arttıkça Komşu Kalmıyor

Her iki kurulum tek bir şeye dayanır: iki abonenin ya da iki kalemin doğrudan ortak gözlemi. Eğitim etkileşimlerinin bir payı tutulup kalanı atılarak seyreklik yukarı çekilir; ayrılan kalemler değişmez, böylece beş satır aynı 167 abone üzerinde okunur. Komşu sayısı en iyi ayarında, yani üçte, sabitlenmiştir.

CIFT = sorted(EGIT)
print(f"{'pay':>5} {'egitim':>7} {'seyreklik':>10} {'komsusuz':>9} "
      f"{'isabet@5':>9} {'komsulu':>8} {'komsusuz':>9} {'taban':>7}")
for pay in (1.00, 0.75, 0.55, 0.40, 0.25):
    r = uretec(TOHUM + 9100)
    G = {a: set() for a in ABONE}
    for a, j in CIFT:
        if r() < pay:
            G[a].add(j)
    B = benzerlikler(G, ABONE)
    ps = [sum(1 for a in ABONE if j in G[a]) for j in range(N_KALEM)]
    kt = kullanici_temelli(B, G, 3)
    var = [a for a in SINAV if B[a]]
    yok = [a for a in SINAV if not B[a]]
    t = sum(len(v) for v in G.values())
    iy = "%.4f" % olc(kt, G, yok)[0] if yok else "--"
    print(f"{pay:>5.2f} {t:>7} {1 - t / (N_ABONE * N_KALEM):>10.4f} {len(yok):>9} "
          f"{olc(kt, G)[0]:>9.4f} {olc(kt, G, var)[0]:>8.4f} {iy:>9} "
          f"{olc(lambda a: ps, G)[0]:>7.4f}")

  pay  egitim  seyreklik  komsusuz  isabet@5  komsulu  komsusuz   taban
 1.00     410     0.9525         0    0.6946   0.6946        --  0.6527
 0.75     308     0.9644        20    0.6886   0.6803    0.7500  0.6467
 0.55     221     0.9744        52    0.6587   0.6783    0.6154  0.6347
 0.40     167     0.9807        75    0.6587   0.6739    0.6400  0.6407
 0.25      97     0.9888       105    0.6407   0.6613    0.6286  0.6347

Seyreklik 0,9525’ten 0,9888’e çıkarken hiç komşusu kalmayan sınav abonesi sıfırdan 105’e çıkıyor — 167 abonenin yarısından fazlası. Bu abonelerin puan vektörü baştan sona sıfırdır: işbirlikçi süzgeçleme onlar için hiçbir şey üretmiyor.

Beşinci sütun buna rağmen 0,6946’dan yalnız 0,6407’ye iniyor. Ölçünün bu kadar az düşmesi yöntemin seyrekliğe dayanıklı olduğunu göstermiyor; yedinci sütun nedeni söylüyor. Komşusuz abonelerde isabet 0,6286 — komşusu olanlardaki 0,6613’ün yalnız 0,0327 altında. Oysa o abonelerde yöntem hiç çalışmadı. Sayı, ON27’de yazılan eşitlik çözümünden geliyor: bütün puanlar sıfır olunca sıralama katalog indisine düşüyor ve katalog taban payına göre azalan sırada. Yani komşusuz abone sessizce taban çizgisiyle aynı listeyi alıyor, ve ölçü yöntemin sayısı gibi görünen bir tabanın sayısını basıyor.

Bu, kursun kuralının bir başka yüzüdür. Yöntemin sayısını okurken kaç abone için gerçekten çalıştığı yazılmazsa, ölçü yöntemin değil ölçüm düzeninin ürettiği bir şeydir. Sütunlar ayrı basıldığında kayıp görünür oluyor: 0,25 payında yöntem 167 abonenin 62’sinde çalışıyor ve orada 0,6613 veriyor, kalan 105’inde çalışmıyor ve orada 0,6286’yı katalog sırası veriyor. Taban ise beş satır boyunca 0,6527 ile 0,6347 arasında yerinde duruyor.

Özet

• İşbirlikçi süzgeçleme öneriyi kalemin özniteliklerinden değil, kalemleri birlikte seçen abonelerden üretir; tek bir benzerlik yordamı dizeyin iki kenarında da çalışır.
• Eğitim dizeyi 410 etkileşimle 0,9525 seyrek; taban çizgisi olan en çok seçilen kalem sırası 0,6527 isabet@5 veriyor ve 24 kalemin yalnız 9’unu gösteriyor.
• Kullanıcı temelli kurulum üç komşuyla 0,6946 veriyor, tabandan 0,0419 yukarıda; ama ilk beşinin 4,07’si zaten taban listesinin kalemidir ve asıl kazanç 9 yerine 16 kalem göstermektir.
• Komşu sayısı bir ayar değişkenidir: yedi aday 0,5988 ile 0,6946 arasında oynuyor ve bu 0,0958’lik bant, yöntemin tabanı geçtiği farkın iki katından fazla.
• Öğe temelli kurulum en iyi ayarında 0,6467’de kalıp tabanın altına düşüyor, çünkü sınav abonesi başına ortalama 1,78 eğitim kalemi var; buna karşılık 21 kalem gösteriyor.
• Seyreklik 0,9525’ten 0,9888’e çıkarıldığında komşusuz abone 0’dan 105’e çıkıyor; ölçünün 0,6407’de kalması yöntemden değil, puanlar sıfırlanınca devreye giren katalog sırasından geliyor.

Sonraki Adım

Komşuluk tek bir şeye dayanıyor: iki abonenin ya da iki kalemin doğrudan ortak gözlemi. Ortak gözlem yoksa benzerlik listeye hiç girmiyor ve son tablo bunun bedelini gösterdi. Oysa ortak kalemi olmayan iki abone birbirine gerçekten benzemiyor olmak zorunda değil: biri taksitlendirmeye, öbürü borç yapılandırmaya başvurmuşsa ikisi de ödeme alanında duruyor, ama benzerlikleri sıfır çıkıyor. Bu ortaklığı yakalamak için benzerliği hücre hücre değil, her aboneyi ve her kalemi az sayıda gizli etkene yerleştiren bir gösterim üzerinden okumak gerekir. Sonraki ders dizeyi böyle iki küçük dizeyin çarpımı olarak yazar, ve ölçülecek asıl karar şudur: dizeyin gözlenmeyen hücreleri hesaba sıfır olarak mı girecek, yoksa hiç girmeyecek mi. İki kurulum aynı veride iki ayrı sıralama üretir.