Vektör Veritabanları

Önceki üç ders gömmeyi bir arama anahtarı olarak kurdu, alan uyumunun ne kadarını taşıdığını ölçtü ve iki benzerlik ölçütünün aynı sorguda ayrıştığı yeri saydı. Üçünün de ortak bir sessiz varsayımı vardı: bir sorgu geldiğinde dağarcıktaki her belgeyle karşılaştırılıyordu. İki yüz belgede bu varsayım ucuzdur. Dağarcık büyüdüğünde ucuz olmaktan çıkar, çünkü karşılaştırma sayısı belge sayısıyla doğru orantılı büyür ve her sorgu dağarcığın tamamını okumak zorunda kalır.

Vektör deposu bu yükü bir dizin ile azaltır: sorgu geldiğinde dağarcığın yalnız bir kısmına bakılır. Bir kısmına bakmak, doğru komşunun bakılmayan kısımda kalabilmesi demektir; bu yüzden dizinli aramaya yaklaşık komşu arama denir ve tam taramanın verdiği yanıtı vermek zorunda değildir. Bu dersin ölçtüğü şey o farktır: yaklaşıklığın kaybettirdiği. Tam tarama tabanına karşı iki dizin yapısının anması ile karşılaştırma sayısı yan yana basılır, ve ikisinden birinin saklamayı katlamasına karşın tabanın hem altında hem de pahalı kaldığı gösterilir.

• GM31. Dağarcık, gömme yordamı ve sorgu kümesi kurgudur; gerçek bir gömme uç noktası ya da vektör deposu çağrılmaz. Tohum 20260218.
• GM32. Benzetici yüzeyi önce kavrama, kavramı sonra otuz iki boyuta indirir; belge dili ile sorgu dili hiçbir belirteç paylaşmaz. Bu dersin bütün ölçümleri alan içi gömmeyle yapılır.
• GM33. Taban tam taramadır: her sorgu iki yüz belgenin hepsiyle karşılaştırılır ve ilk beş sonuç alınır.
• GM34. Erişim anması bu derste dizine karşı okunur: dizinin ilk beşi ile tam taramanın ilk beşinin kesişiminin beşe oranı. Anma 1,0000 dizinin tabanla aynı yanıtı verdiği anlamına gelir, doğru yanıtı verdiği anlamına gelmez.
• GM35. Kavram kesinliği getirilen beş belgenin sorgunun hedef kavramını taşıma payıdır ve tabanın kendi kalitesini gösterir.
• GM36. Karşılaştırma sayısı tek bir sorguda hesaplanan açı benzerliği adedidir. Süre yazılmaz; dizinin kurulum bedeli ayrıca saklanan kenar ya da temsilci sayısı olarak sayılır.
• GM37. Dizin yapıları davranışlarıyla anılır: kovalı dizin ve komşuluk çizgesi. Hiçbir vektör deposu, kitaplık ya da yöntem adı yazılmaz.
• GM38. Kovalı dizinin kurulumu tohuma bağlıdır. Bu dersin iki koşumu aynı sorgu kümesinin iki ayrı dizin kurulumunda ölçülmesidir; aradaki fark bu iş yükünün eşiğidir ve altındaki farklar ölçülmemiş sayılır.

En yakın komşu yordamının kendisi Makine Öğrenmesi ve Veri Bilimi müfredatının Denetimsiz Öğrenme kursunda kuruldu ve ölçüldü; burada tekrarlanmaz. Eklenen tek şey, o yordamın tamamını çalıştırmamanın bedelidir.

Tam Taramanın Tabanı

Aşağıdaki blok kurgu dağarcığı ve gömme benzeticisini kurar, sonra tabanı basar. Taban iki sayı verir: dizinin kaçırdığını ölçeceğimiz sonuç kümesi ve o kümenin kendi kalitesi.

# KURGU dagarcik ve KURGU gomme benzeticisi. Gercek bir uc nokta cagrilmaz.
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 = 5
VEK = [gom(metin(d)) for d in BELGE]
QV = [gom(q["metin"]) for q in SORGU]
TABAN = [sorted(range(len(VEK)), key=lambda i: -aci(qv, VEK[i]))[:K] for qv in QV]


def kavram_kesinligi(getirilen):
    d = sum(BELGE[i]["ana"] == SORGU[n]["kavram"]
            for n, g in enumerate(getirilen) for i in g)
    return d / (len(getirilen) * K)


print(f"dagarcik {len(BELGE)} belge , farkli vektor "
      f"{len({tuple(v) for v in VEK})} , sorgu {len(SORGU)}")
print(f"tam tarama: sorgu basina {len(VEK)} karsilastirma , "
      f"toplam {len(VEK) * len(SORGU)}")
print(f"ilk {K} sonucun kavram kesinligi {kavram_kesinligi(TABAN):.4f}")

dagarcik 200 belge , farkli vektor 52 , sorgu 40
tam tarama: sorgu basina 200 karsilastirma , toplam 8000
ilk 5 sonucun kavram kesinligi 0.4600

İkinci satır dizin gerekçesinin tamamıdır: kırk sorgu için sekiz bin açı hesabı. Üçüncü satır ise tabanın kendisini ölçüyor. Tam tarama, getirdiği beş belgenin ancak 0,4600’ünde sorgunun hedef kavramını taşıyor. Taban kusursuz değildir; dizin bunun üstüne çıkamaz, ancak buna yaklaşır ya da bundan uzaklaşır.

İlk satırın son sayısı sonraki bölümde işe yarayacak: iki yüz belge var ama yalnız 52 farklı vektör. Belgeler kavram kümelerini paylaşıyor, dolayısıyla vektör uzayında üst üste biniyorlar.

Kovalı Dizin

Kovalı dizin dağarcığı önceden bölümlere ayırır. Tohumla seçilen bir avuç belge temsilci olur, her belge kendisine en benzeyen temsilcinin kovasına girer. Sorgu geldiğinde önce temsilcilerle karşılaştırılır, sonra yalnız en yakın sonda kadar kovanın içine bakılır.

def kovali_kur(kova, tohum):
    """KURGU kovali dizin: tohumla secilen temsilcilere tek gecislik atama."""
    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 kovali_ara(qv, temsil, uye, sonda, k=K):
    sira = sorted(range(len(temsil)), key=lambda c: -aci(qv, VEK[temsil[c]]))
    aday = [i for c in sira[:sonda] for i in uye[c]]
    return sorted(aday, key=lambda i: -aci(qv, VEK[i]))[:k], len(temsil) + len(aday)


def anma(bulunan, taban):
    return len(set(bulunan) & set(taban)) / len(taban)


def kovali_olc(kova, sonda, tohum=TOHUM):
    temsil, uye = kovali_kur(kova, tohum)
    a = kars = 0
    getirilen = []
    for n, qv in enumerate(QV):
        b, c = kovali_ara(qv, temsil, uye, sonda)
        getirilen.append(b)
        a += anma(b, TABAN[n])
        kars += c
    return a / len(QV), kars / len(QV), kavram_kesinligi(getirilen)


print("kova sonda   anma  karsilastirma  kavram kesinligi")
for kova, sonda in ((8, 1), (16, 1), (16, 2), (16, 4), (25, 2), (25, 4)):
    a, c, kk = kovali_olc(kova, sonda)
    print(f"{kova:>4} {sonda:>5} {a:>6.4f} {c:>14.1f} {kk:>17.4f}")
u = [kovali_olc(16, 2, TOHUM + t)[0] for t in (0, 1)]
print(f"iki kurulum kova=16 sonda=2: {u[0]:.4f} , {u[1]:.4f}"
      f" -- fark {abs(u[0] - u[1]):.4f}")

kova sonda   anma  karsilastirma  kavram kesinligi
   8     1 0.5600           39.7            0.4150
  16     1 0.7000           34.8            0.3600
  16     2 0.9600           47.2            0.4500
  16     4 1.0000           69.2            0.4600
  25     2 0.9000           45.0            0.4300
  25     4 1.0000           61.6            0.4600
iki kurulum kova=16 sonda=2: 0.9600 , 0.9400 -- fark 0.0200

Son satır bu dersin eşiğini veriyor. Aynı sorgu kümesi, aynı ayar, yalnız temsilcileri seçen tohum farklı: 0,9600 ve 0,9400. Kurulum farkı 0,0200 taşıyor, dolayısıyla tablodaki bu büyüklükteki farklar ölçülmüş sayılmaz. Kovalı dizin belirlenmiş bir yapı değildir; hangi belgelerin temsilci olduğu sonucu oynatır.

Tablonun ana okuması dört sayıdadır. Kova 16 ve sonda 4’te anma 1,0000: dizin tam taramanın verdiği beş belgenin beşini de veriyor, ve bunu 200 yerine 69,2 karşılaştırmayla yapıyor. Sonda 2’ye inince anma 0,9600’e düşer, karşılaştırma 47,2’ye. Aradaki 0,0400 eşiğin iki katıdır, yani gerçek bir kayıptır; karşılıkta karşılaştırmanın üçte biri kazanılır. Sonda 1’de tablo kırılır: anma 0,7000 ve karşılaştırma 34,8. Yalnız bir kova daha az okumak, karşılaştırmanın dörtte birini kazandırıp anmanın dörtte birini götürüyor.

Son sütun bunun yanıtta ne demek olduğunu söylüyor. Tam taramanın kavram kesinliği 0,4600’dü; kova 16 sonda 1’de 0,3600‘e iniyor. Dizin yalnız aday kümesini daraltmıyor, getirilen belgelerin doğruluğunu da düşürüyor. Kaybın anma sütunundaki 0,3000’lik düşüşten küçük görünmesinin nedeni tabanın zaten yarısından azını doğru getirmesidir: dizin, tabanın kaçırdıklarını kaçırmaya devam ederken tabanın yakaladıklarının bir kısmını da kaçırır. Bir ölçüde okunmayan bir bedel budur ve kursun kuralı bu yüzden iki sütun ister.

Komşuluk Çizgesi ve Erişilebilirlik

İkinci yapı dağarcığı bölmez, bağlar. Her belge kendisine en benzeyen belirli sayıda belgeye bir kenarla bağlanır; arama bir giriş düğümünden başlar ve komşuları arasında sorguya daha yakın biri varsa oraya geçer. Karşılaştırma yalnız yürünen yolda yapılır.

def cizge_kur(derece):
    """KURGU komsuluk cizgesi: her belge en benzer 'derece' belgeye baglanir."""
    c = []
    for i in range(len(VEK)):
        s = sorted(range(len(VEK)), key=lambda j: -aci(VEK[i], VEK[j]))
        c.append([j for j in s if j != i][:derece])
    return c


def erisilebilir(cizge, giris=0):
    gor, yigit = {giris}, [giris]
    while yigit:
        for j in cizge[yigit.pop()]:
            if j not in gor:
                gor.add(j)
                yigit.append(j)
    return len(gor)


def cizge_ara(qv, cizge, giris=0, k=K):
    puan, kars, acilan = {giris: aci(qv, VEK[giris])}, 1, set()
    while True:
        bek = [i for i in puan if i not in acilan]
        if not bek or max(puan[i] for i in bek) < max(puan.values()):
            break
        i = max(bek, key=lambda x: puan[x])
        acilan.add(i)
        for j in cizge[i]:
            if j not in puan:
                puan[j] = aci(qv, VEK[j])
                kars += 1
    return sorted(puan, key=lambda x: -puan[x])[:k], kars


print("derece  kenar  erisilebilir   anma  karsilastirma")
for derece in (8, 16, 32, 48):
    cizge = cizge_kur(derece)
    a = kars = 0
    for n, qv in enumerate(QV):
        b, c = cizge_ara(qv, cizge)
        a += anma(b, TABAN[n])
        kars += c
    print(f"{derece:>6} {derece * len(VEK):>6} {erisilebilir(cizge):>13}"
          f" {a / len(QV):>6.4f} {kars / len(QV):>14.1f}")

derece  kenar  erisilebilir   anma  karsilastirma
     8   1600            27 0.0800           14.0
    16   3200            31 0.1750           26.0
    32   6400           200 0.5250           60.6
    48   9600           200 0.7650           84.7

Erişilebilirlik sütunu bu tablonun açıklamasıdır ve hiçbir sorguya bağlı değildir: giriş düğümünden kenarları izleyerek kaç belgeye ulaşılabildiğini sayar. Derece 8’de bu sayı 200 değil 27‘dir. Çizge parçalı; giriş düğümünün bulunduğu bileşen dağarcığın yedide birinden küçük. Arama ne kadar bütçe alırsa alsın kalan 173 belgeye bakamaz, dolayısıyla anma 0,0800’de tavan yapar. Bu, aramanın değil yapının sayısıdır ve koşumdan bağımsızdır.

Parçalılığın nedeni ilk bloktaki 52 sayısıdır. İki yüz belge yalnız 52 farklı vektöre oturuyor, yani her belgenin en yakın komşuları kendisiyle aynı vektöre sahip belgeler. Derece 8 iken bir düğümün sekiz komşusunun tamamı kendi ikizidir ve kenarlar o adacığın dışına çıkmaz. Derece 32’de ikizlerin sayısı aşılıyor, kenarlar başka kavramlara uzanıyor ve erişilebilirlik bir anda 200 oluyor.

Bağlanan çizge bile tabanı yakalayamıyor. Derece 48’de anma 0,7650 ve karşılaştırma 84,7. Aynı sorgu kümesinde kovalı dizin, kova 16 ve sonda 2 ile 0,9600 anmayı 47,2 karşılaştırmayla veriyordu. Çizge hem daha az doğru hem daha pahalı, üstelik 9600 kenar saklıyor; kovalı dizinin sakladığı ise 16 temsilci ile 200 üyelik kaydı, yani 216 sayıdır. Eklenen düzenek burada işi iyileştirmiyor, iki eksende birden kötüleştiriyor. Yaklaşık komşu aramanın hangi yapıyla kurulacağı bir zevk meselesi değildir; dağarcığın vektör uzayındaki dağılımı bir yapıyı çalışır, öbürünü çalışmaz kılar. Tekrar eden belgelerin çok olduğu bir dağarcıkta çizge tıkanır, bölümleme tıkanmaz.

Özet

• Tam tarama sorgu başına 200 karşılaştırma ister ve getirdiği beş belgenin 0,4600’ünde hedef kavramı taşır; taban kusursuz değildir ve dizin bunun üstüne çıkamaz.
• Kovalı dizin kova 16 sonda 4 ile anmayı 1,0000’de tutup karşılaştırmayı 69,2’ye, sonda 2 ile 0,9600 anmayla 47,2’ye indirir; sonda 1’de anma 0,7000’e düşer.
• Dizin yalnız aday kümesini değil yanıtı da bozar: kova 16 sonda 1’de ilk beşin kavram kesinliği 0,4600’den 0,3600’e iner.
• Komşuluk çizgesinde anmanın tavanı erişilebilirliktir; derece 8’de giriş düğümünden yalnız 27 belgeye ulaşılabildiği için anma 0,0800’de kalır ve bu sayı koşumdan bağımsızdır.
• Bağlanmış çizge bile kovalı dizinin altında kalır: derece 48’de 9600 kenar, 84,7 karşılaştırma ve 0,7650 anma; eklenen düzenek burada iki eksende birden kaybettirir.
• İki dizin kurulumu arasındaki fark 0,0200’dür; bu iş yükünde daha küçük farklar ölçülmemiş sayılır.

Sonraki Adım

Bu dersin bütün ölçümlerinde sorgu dağarcığın tamamına yöneltildi; dizin yalnız o dağarcığın neresine bakılacağını kısıtladı. Gerçek bir erişim isteği çoğu zaman böyle gelmez: yalnız belirli bir sınıftaki, belirli bir dönemdeki ya da belirli bir bölgeye ait belgeler istenir. Bu kısıt vektör aramasının önüne mi arkasına mı konur ve ikisi arasındaki fark nedir. Sonraki ders bir meta veri süzgecini kovalı dizinle yan yana koyar ve süzgeç seçiciliği arttıkça anmaya ne olduğunu sayar: dizin bütün dağarcık üzerine kurulduğu için, süzgeç daraldıkça bakılan kovaların içinde ayakta kalan aday sayısı çöker ve bir noktadan sonra dizinsiz arama dizinliden hem daha doğru hem daha ucuz hâle gelir.