Meta Veri Süzme

Önceki derste sorgu dağarcığın tamamına yöneltildi ve dizin yalnız o dağarcığın neresine bakılacağını kısıtladı. Erişim isteği çoğu zaman böyle gelmez. Saha ekibi belirli bir bölgenin kayıtlarını, destek masası belirli bir sınıftaki belgeleri, denetim belirli bir dönemi ister. Bu kısıt bir benzerlik sorusu değildir; meta veri üzerinde tanımlı kesin bir koşuldur ve sağlanması ya da sağlanmaması ölçü kabul etmez.

İki yordamın birleştirilmesinin tek bir doğru sırası yoktur. Süzgeç vektör aramasından sonra uygulanırsa arama dizinin tamamı üzerinde çalışır ve sonuçların bir kısmı elenir. Önce uygulanırsa arama yalnız eşleşen belgeler üzerinde çalışır, ama dizin bütün dağarcık üzerine kurulmuştur ve daraltılmış uzayda ne söz verdiği belirsizdir. Bu ders iki sırayı da ölçer ve üçüncü bir sayıyı yanlarına koyar: süzgeci uygulayıp dizini hiç kullanmamanın bedeli. Süzgeç daraldıkça bu üçüncü seçeneğin hem daha doğru hem daha ucuz hâle geldiği bir nokta çıkar.

• GM39. Dağarcık, gömme yordamı, sorgu kümesi ve meta veri katmanı kurgudur; gerçek bir vektör deposu ya da gömme uç noktası çağrılmaz. Tohum 20260218.
• GM40. Meta veri bu derste tek alandır: her belgeye tohumdan türeyen bir bölge kodu (1 ile 16 arası) verilir. Süzgeç bölge <= genişlik koşuludur; genişlik küçüldükçe süzgeç seçicileşir.
• GM41. Süzgeç kesindir: eşleşmeyen bir belge hiçbir benzerlik değerinde sonuca giremez. Bu, benzerlik eşiğinden farklı bir kısıttır.
• GM42. Doğru yanıt her genişlikte süzülmüş kümenin tam taramasıdır: eşleşen belgelerin hepsiyle karşılaştırma ve ilk beş. Anma, yordamın getirdiği kümenin bu beşlikle kesişiminin oranıdır; eşleşen belge sayısı beşten azsa payda o sayıdır.
• GM43. Süzgeç sonrası yordam dizinden ilk getir sonucu alır ve içlerinden eşleşmeyenleri atar. Dizin içinde süzme aynı kovalara bakar ama eşleşmeyen belgeleri aday kümesine hiç almaz.
• GM44. Dizin önceki derste ölçülen ayarla kurulur: kovalı dizin, 16 kova, 2 sonda. Bu ayar süzgeçsiz durumda 0,9600 anma veriyordu ve bu dersin karşılaştırma tabanıdır.
• GM45. Karşılaştırma sayısı tek sorguda hesaplanan açı benzerliği adedidir: temsilci sayısı artı bakılan aday sayısı. Süzgecin kendisi bir eşitlik sınamasıdır ve bu sayıya girmez.
• GM46. Aday sayısı sondalanan kovaların içinde süzgeci geçen belge adedidir; komşuluğun bozulması bu sütunda görünür.
• GM47. İki koşum aynı sorgu kümesinin iki ayrı dizin kurulumunda ölçülmesidir. Önceki derste bu fark süzgeçsiz durumda 0,0200 çıkmıştı; bu dersin bir bulgusu farkın süzgeçle birlikte büyümesidir.

Süzgeçli sorgunun kendisi Veritabanları müfredatının İleri SQL ile Arama Motorları ve Metin Erişimi kurslarında kuruldu ve ölçüldü; süzme yordamı burada tekrarlanmaz. Eklenen tek şey, süzgecin vektör komşuluğuna ne yaptığıdır.

Süzgecin Daralttığı Uzay

Aşağıdaki blok dağarcığı ve gömme benzeticisini kurar, üstüne meta veri katmanını ekler ve süzgeçsiz tabanı basar.

# KURGU dagarcik, KURGU gomme benzeticisi ve KURGU meta veri. Gercek uc nokta yok.
TOHUM, M32 = 20260218, 0xFFFFFFFF
BOYUT = 32


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


# ---- KURGU anlam ekseni: her kavramin belge dilinde ve sorgu dilinde ayri yuzeyi var
SINIF = ["tarife", "ariza", "sayac", "kesinti", "bakim"]
KOD = {"tarife": "TR", "ariza": "AR", "sayac": "SY", "kesinti": "KS", "bakim": "BK"}
KAVRAM = {                       # kavram: (sinif, belge yuzeyi, sorgu yuzeyi)
    "basamak":   ("tarife", "kademe esigi", "hangi dilimdeyim"),
    "birim":     ("tarife", "birim ucret", "metrekup fiyati"),
    "abonetip":  ("tarife", "abone tipi", "mesken mi isyeri mi"),
    "gecis":     ("tarife", "tarife gecisi", "plan degistirme"),
    "arizakod":  ("ariza", "ariza kodu", "hata numarasi"),
    "sizinti":   ("ariza", "hat sizintisi", "su kacagi"),
    "basinc":    ("ariza", "basinc dususu", "zayif akis"),
    "ekip":      ("ariza", "saha ekibi", "gorevli ne zaman gelir"),
    "endeks":    ("sayac", "endeks degeri", "sayac ustundeki rakam"),
    "okuma":     ("sayac", "okuma yordami", "nasil kaydediliyor"),
    "degisim":   ("sayac", "sayac degisimi", "cihaz yenileme"),
    "dogrula":   ("sayac", "okuma dogrulamasi", "yanlis girilmis mi"),
    "planli":    ("kesinti", "planli kesinti", "onceden duyurulan durma"),
    "duyuru":    ("kesinti", "duyuru kanali", "nereden ogrenirim"),
    "sure":      ("kesinti", "kesinti suresi", "ne kadar surer"),
    "geridonus": ("kesinti", "yeniden verme", "ne zaman gelir"),
    "periyot":   ("bakim", "periyodik bakim", "duzenli kontrol"),
    "vana":      ("bakim", "vana kontrolu", "musluk kapatma duzeni"),
    "filtre":    ("bakim", "filtre degisimi", "temizleme parcasi"),
    "kalib":     ("bakim", "kalibrasyon kaydi", "olcum ayari"),
}
ANAHTAR = list(KAVRAM)
ORTAK = ["kayit", "bolge", "donem", "islem", "form", "onay", "not"]

BELGE = []
for i in range(200):
    r = uretec(TOHUM + 7919 * i)
    s = SINIF[ayrik(r(), [0.22, 0.24, 0.20, 0.18, 0.16])]
    kav = [k for k in ANAHTAR if KAVRAM[k][0] == s]
    ana = kav[int(r() * len(kav))]
    n = 2 + int(r() * 4)
    par, kavlar = [], [ana]
    for _ in range(n):
        y = kav[int(r() * len(kav))]
        kavlar.append(y)
        o = ORTAK[int(r() * len(ORTAK))]
        par.append(f"{KAVRAM[y][1]} icin {o} tutulur ve {KAVRAM[ana][1]} ile birlikte yazilir")
    BELGE.append({"kod": f"{KOD[s]}{i + 1:03d}", "sinif": s, "ana": ana, "kavram": kavlar,
                  "baslik": f"{KAVRAM[ana][1]} yordami", "par": par})


def metin(d):
    return d["baslik"] + " " + " ".join(d["par"])


def _kavramla(m):                # yuzey once kavrama cevrilir
    v = [0.0] * len(ANAHTAR)
    dm = " " + m.lower() + " "
    for i, k in enumerate(ANAHTAR):
        if KAVRAM[k][1] in dm:
            v[i] += 1.0
        if KAVRAM[k][2] in dm:
            v[i] += 1.0
    return v


IZDUS = []
for i in range(len(ANAHTAR)):
    r = uretec(TOHUM ^ (i + 1) * 2654435761)
    IZDUS.append([r() * 2 - 1 for _ in range(64)])


def gom(m, boyut=BOYUT):         # kavram sonra boyuta dusurulur
    v = [0.0] * boyut
    for i, a in enumerate(_kavramla(m)):
        if a:
            for j in range(boyut):
                v[j] += a * IZDUS[i][j % 64]
    n = sum(x * x for x in v) ** 0.5
    return [x / n for x in v] if n else v


def aci(a, b):
    return sum(x * y for x, y in zip(a, b))


SORGU = []                       # KURGU sorgu kumesi: sorgu dili belge dilinden ayri
for i in range(40):
    r = uretec(TOHUM + 104729 * i)
    d = BELGE[int(r() * len(BELGE))]
    SORGU.append({"metin": f"{KAVRAM[d['ana']][2]} {ORTAK[int(r() * len(ORTAK))]}",
                  "sinif": d["sinif"], "kavram": d["ana"]})

K, SONDA = 5, 2
GENISLIK = (16, 8, 4, 2, 1)
VEK = [gom(metin(d)) for d in BELGE]
QV = [gom(q["metin"]) for q in SORGU]
BOLGE = [1 + int(uretec(TOHUM ^ (i + 1) * 40503)() * 16) for i in range(len(BELGE))]


def esleseni(g):
    return [i for i in range(len(VEK)) if BOLGE[i] <= g]


def gercek(qv, g, k=K):          # dogru yanit: suzulmus kumenin tam taramasi
    return sorted(esleseni(g), key=lambda i: -aci(qv, VEK[i]))[:k]


def kovali_kur(kova, tohum):
    r, temsil = uretec(tohum), []
    while len(temsil) < kova:
        i = int(r() * len(VEK))
        if i not in temsil:
            temsil.append(i)
    uye = [[] for _ in temsil]
    for i in range(len(VEK)):
        uye[max(range(kova), key=lambda c: aci(VEK[i], VEK[temsil[c]]))].append(i)
    return temsil, uye


def sondalanan(qv, temsil, uye):
    sira = sorted(range(len(temsil)), key=lambda c: -aci(qv, VEK[temsil[c]]))
    return [i for c in sira[:SONDA] for i in uye[c]]


def anma(bulunan, dogru):
    return len(set(bulunan) & set(dogru)) / max(1, len(dogru))


TEMSIL, UYE = kovali_kur(16, TOHUM)
tam = sum(anma(sorted(sondalanan(qv, TEMSIL, UYE),
                      key=lambda i: -aci(qv, VEK[i]))[:K], gercek(qv, 16)) for qv in QV)
print(f"dagarcik {len(BELGE)} belge , 16 bolge , sorgu {len(SORGU)}")
print("suzgec genisligi " + " / ".join(str(g) for g in GENISLIK)
      + " -> eslesen " + " / ".join(str(len(esleseni(g))) for g in GENISLIK))
print(f"suzgecsiz taban: kovali dizin (kova 16 , sonda {SONDA}) anma {tam / len(QV):.4f} , "
      f"{len(TEMSIL) + sum(len(sondalanan(qv, TEMSIL, UYE)) for qv in QV) / len(QV):.1f}"
      f" karsilastirma , tam tarama {len(VEK)}")

dagarcik 200 belge , 16 bolge , sorgu 40
suzgec genisligi 16 / 8 / 4 / 2 / 1 -> eslesen 200 / 101 / 52 / 27 / 18
suzgecsiz taban: kovali dizin (kova 16 , sonda 2) anma 0.9600 , 47.2 karsilastirma , tam tarama 200

Beş genişlik dağarcığı 200’den 18 belgeye kadar daraltıyor. Süzgeçsiz taban önceki dersin satırıdır: dizin tam taramanın verdiği beşliğin 0,9600’ünü 47,2 karşılaştırmayla getiriyor. Sorulacak soru şu: bu sayı süzgeç eklendiğinde de geçerli mi.

Süzgeci Sonra Uygulamak

En az iş isteyen birleştirme, aramayı hiç değiştirmeden sonucu elemektir. Dizin ilk getir kadar belgeyi verir, eşleşmeyenler atılır, kalanın ilk beşi döndürülür.

def suzgec_sonrasi(qv, g, getir):
    ust = sorted(sondalanan(qv, TEMSIL, UYE), key=lambda i: -aci(qv, VEK[i]))[:getir]
    return [i for i in ust if BOLGE[i] <= g][:K]


print("genislik  anma(getir 5)  eksik sonuc  anma(getir 15)  anma(getir 50)")
for g in GENISLIK[1:]:
    s, eksik = [0.0, 0.0, 0.0], 0
    for qv in QV:
        d = gercek(qv, g)
        for n, getir in enumerate((5, 15, 50)):
            s[n] += anma(suzgec_sonrasi(qv, g, getir), d)
        eksik += len(suzgec_sonrasi(qv, g, 5)) < len(d)
    print(f"{g:>8} {s[0] / len(QV):>14.4f} {eksik:>12} {s[1] / len(QV):>15.4f}"
          f" {s[2] / len(QV):>15.4f}")

genislik  anma(getir 5)  eksik sonuc  anma(getir 15)  anma(getir 50)
       8         0.4450           37          0.8700          0.8700
       4         0.1950           40          0.6900          0.7700
       2         0.1050           40          0.3850          0.6250
       1         0.0900           40          0.2600          0.4750

İlk sütun süzgeçsiz 0,9600’den başlıyordu; genişlik 8’de 0,4450‘ye, genişlik 1’de 0,0900‘e iniyor. Üçüncü sütun nedeni söylüyor: genişlik 4’ten aşağıda kırk sorgunun kırkı doğru yanıttan daha az sonuç döndürüyor. Dizin beş belge veriyor, süzgeç dördünü ya da beşini atıyor, geriye ya bir sonuç kalıyor ya hiçbiri. Ortada bir sıralama sorunu yok; sonuç kutusu boşalıyor.

Bilinen çare fazladan getirmektir: beş yerine on beş, elli belge alıp öyle elemek. Son iki sütun bunun ne kadar işe yaradığını gösteriyor. Genişlik 8’de on beşe çıkmak 0,4450’yi 0,8700’e taşıyor ve elliye çıkmak hiçbir şey eklemiyor. Genişlik 1’de elli belge getirmek ancak 0,4750 veriyor. Fazladan getirme bir tavana çarpıyor, ve o tavan bir sonraki bölümün ilk sütunudur: sondalanan kovaların içinde süzgeci geçen belge sayısı. Elli belge istemek, kovalarda o kadar uygun belge yoksa elli belge getirmez.

Süzgeci Dizinin İçinde Uygulamak

İkinci yordam eşleşmeyen belgeyi aday kümesine hiç almaz. Aynı kovalara bakılır, ama sayılan ve sıralanan yalnız süzgeci geçenlerdir.

def dizin_icinde(qv, g, temsil, uye):
    aday = [i for i in sondalanan(qv, temsil, uye) if BOLGE[i] <= g]
    return sorted(aday, key=lambda i: -aci(qv, VEK[i]))[:K], len(aday)


IKINCI = kovali_kur(16, TOHUM + 1)
print("genislik  aday  anma  karsilastirma  tam tarama  iki kurulum farki")
for g in GENISLIK:
    a = b = 0.0
    ad = 0
    for qv in QV:
        d = gercek(qv, g)
        r1, n1 = dizin_icinde(qv, g, TEMSIL, UYE)
        a += anma(r1, d)
        b += anma(dizin_icinde(qv, g, *IKINCI)[0], d)
        ad += n1
    print(f"{g:>8} {ad / len(QV):>5.1f} {a / len(QV):>5.4f} "
          f"{len(TEMSIL) + ad / len(QV):>14.1f} {len(esleseni(g)):>11}"
          f" {abs(a - b) / len(QV):>19.4f}")

genislik  aday  anma  karsilastirma  tam tarama  iki kurulum farki
      16  31.2 0.9600           47.2         200              0.0200
       8  15.7 0.8700           31.6         101              0.1300
       4   7.8 0.7700           23.9          52              0.0950
       2   4.0 0.6250           20.0          27              0.1250
       1   2.8 0.4750           18.8          18              0.1100

Aday sütunu komşuluğun bozulmasıdır. Süzgeçsizken dizin sorgu başına 31,2 belge tartıyor; genişlik 1’de 2,8. Kovalar dağarcığın tamamı üzerine kurulmuştu ve bir kova, bölgelere göre değil benzerliğe göre doldu. Süzgeç daraldıkça bir kovanın içinde ayakta kalan belge sayısı düşüyor ve dizin, beş sonuç seçmesi gereken yerde üç belge arasından seçim yapar duruma geliyor. Anma 0,9600’den 0,4750’ye bu yüzden iniyor.

Asıl karar son üç sütunda okunuyor. Karşılaştırma 47,2’den 18,8’e düşerken tam tarama sütunu 200’den 18’e düşüyor. Süzgeçsiz durumda dizin tam taramanın dörtte biri kadar iş yapıyordu; genişlik 1’de daha çok iş yapıyor. Genişlik 1 satırı yan yana şu iki şeyi söylüyor: dizin 18,8 karşılaştırmayla 0,4750, süzülmüş kümenin tam taraması 18 karşılaştırmayla 1,0000. Yaklaşık arama burada hem pahalı hem yanlıştır. Kesişme genişlik 2 ile 1 arasındadır: genişlik 2’de dizin hâlâ yedi karşılaştırma ucuzdur ama 0,3750 anma bırakır, genişlik 1’de ucuzluğu da biter. Bu noktanın altında dizini atlayıp eşleşen belgeleri baştan sona taramak her iki eksende kazanır. Eklenen düzeneğin işi kötüleştirmesi bu dersin ikinci örneğidir ve nedeni dizinin kötü kurulmuş olması değildir: dizin, sorgunun soracağı kısıttan habersiz kurulmuştur.

Son sütun bir de kararsızlık ekliyor. Süzgeçsizken iki dizin kurulumu arasındaki fark 0,0200’dü, yani önceki dersin eşiği. Süzgeçliyken fark 0,0950 ile 0,1300 arasında, eşiğin beş katı. Aynı dağarcık, aynı sorgu, aynı ayar; değişen yalnız hangi belgelerin temsilci olduğu. Dar bir süzgeçle çalışan bir kurulumda ölçülen anma, o kurulumun sayısıdır ve tekrar kurulduğunda taşınmaz.

Özet

• Meta veri süzgeci kesin bir kısıttır ve benzerlik eşiğinden farklıdır; eşleşmeyen belge hiçbir benzerlik değerinde sonuca giremez.
• Süzgeci aramadan sonra uygulamak sonuç kutusunu boşaltır: genişlik 4 ve altında kırk sorgunun kırkı beş sonuçtan azını döndürür ve anma 0,9600’den 0,0900’e iner.
• Fazladan getirme bu kaybı kısmen kapatır ama bir tavana çarpar; genişlik 8’de elli belge getirmek on beş belge getirmenin verdiği 0,8700’ün üstüne çıkmaz.
• Dizin içinde süzmede aday sayısı 31,2’den 2,8’e, anma 0,9600’den 0,4750’ye iner; kovalar benzerliğe göre doldurulduğu için süzgeç kovanın içini boşaltır.
• Genişlik 1’de dizin 18,8 karşılaştırmayla 0,4750, süzülmüş kümenin tam taraması 18 karşılaştırmayla 1,0000 verir; eşik genişlik 2 civarındadır ve altında dizin iki eksende birden kaybettirir.
• İki dizin kurulumu arasındaki fark süzgeçsizken 0,0200, süzgeçliyken 0,0950 ile 0,1300 arasındadır; dar süzgeçle ölçülen anma kuruluma bağlıdır.

Sonraki Adım

Bu dersin bütün ölçümlerinde sorgu ile belge arasındaki bağ tek bir yerden kuruldu: gömme vektörlerinin açısı. Süzgeç bu bağı daralttı ama değiştirmedi. Oysa dağarcıkta sorgunun sözcüklerini birebir taşıyan belgeler de var ve onları bulmak için gömmeye hiç gerek yok; bir belge kodu, bir tarih ya da bir hata numarası arandığında anlam benzerliği aranan şeyin yanından geçer. Sonraki ders anahtar sözcük eşleşmesi ile gömme aramasını aynı sorgu kümesinde ayrı ayrı ölçer, sonra ikisinin sıralarını birleştirir ve birleştirmenin ne kattığını sayar. Beklenen şey toplamın parçalarından iyi olmasıdır; ölçülen şey bir sorgu sınıfında birleşiğin ikisinden de kötü kalmasıdır.