Min Value: Benzersiz Değerlerin Sayısı Nasıl Tahmin Edilir

Linear Counting hakkındaki önceki yazıda bir veri kümesindeki benzersiz değerlerin sayısını hesaplamak ve tahmin etmek için temel algoritmaları gördük. Bugün sırada, makul bir doğrulukla ve küçük bellek ihtiyacıyla benzersiz değerlerin sayısını tahmin etmeyi sağlayan başka bir olasılıksal algoritma var.

Min Value

Bu yazıda yalnızca birim aralıktaki (0, 1) gerçek sayılarla çalışacağız. Bu aralıktan alınmış, düzgün dağılmış bir sayı kümesi düşünelim; örneğin {0,25; 0,5; 0,75} kümesi. Komşu sayılar birbirinden (sıfırdan ve birden de) tam olarak 0,25 uzaklıktadır. Bu, benzersiz elemanların sayısını bulmamıza nasıl yardım eder?

Sana birim aralıktan alınmış böyle düzgün dağılmış bir sayı kümesi olduğunu ve bu sayıların birbirine uzaklığının tam olarak 0,2 olduğunu söylesem — böyle bir kümenin kaç elemanı olduğunu hesaplayabilir misin? Tabii ki, bu küme {0,2; 0,4; 0,6; 0,8} kümesidir ve kardinalitesi dörttür. Girdide birim aralıktan düzgün dağılmış sayılar varsa ve komşu sayıların uzaklığını biliyorsak eleman sayısını kolayca hesaplayabiliriz.

Üstelik komşu sayılar arasındaki uzaklık, kümenin en küçük elemanına eşittir — {0,25; 0,5; 0,75} kümesinin komşu elemanlarının uzaklığı 0,25’tir vb. Düzgün dağılmış sayıların eleman sayısını hesaplarken en küçük elemanı bir şekilde bulmamız yeter. Sonra eleman sayısı p’yi şu basit formülle hesaplayabiliriz:

$$p=\frac{1}{m}-1$$

Burada m söz konusu en küçük elemandır.

Yine Özetleyeceğiz…

Peki girdide birim aralığa düzgün dağılma koşulunu sağlamayan string’ler ya da başka değerler varsa bunu nasıl kullanacağız? Yine eski güzel özet fonksiyonundan yardım alacağız; o, her girdi için birim aralıktan bir rasyonel sayı döndürebilir. Böyle bir özet fonksiyonu kurmak kolaydır.

Bununla verilerden rasyonel sayılar elde ederiz, ama bu sayıların düzgün dağılmasını nasıl sağlayacağız? Bu artık mümkün değil, ama başka bir yoldan yardım alabiliriz. Bizim açımızdan özet fonksiyonu oldukça “rastgele” davranır. “selam”, “selan” ve “selao” gibi birbirine çok benzeyen sözcükler için özet fonksiyonu büyük ihtimalle çok farklı sağlama toplamları döndürecektir. Başka bir deyişle: bin farklı değeri birim aralığa özetlersek, sayıların büyük çoğunluğunun örneğin yarıdan küçük çıkması çok düşük bir ihtimaldir. Tersine, bu sayıların aşağı yukarı düzenli dağılmış olması çok muhtemeldir. Ne kadar çok veriyi özetlersek dağılım o kadar düzenli olur.

Bu fikirden basit bir algoritma çıkar: girdi verilerinin üzerinden geçeriz, her elemanı birim aralığa özetleriz ve en küçük elemanı aklımızda tutarız. Benzersiz eleman sayısını önceki formüle göre tahmin ederiz. Python’da uygulaması:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values)
    minimum = min(numbers_from_unit_interval)
    return int(1 / minimum) - 1

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

unit_interval_hash fonksiyonu bize (0, 1] aralığından bir ondalık sayı döndürür. count_unique_using_minimum fonksiyonu önce tüm girdi değerlerini bu tür sayılara çevirir, minimumu bulur ve 1 / minimum - 1 değerini döndürür. Veri kümesinde kaç tane aynı değer olduğunun hiç önemli olmadığına dikkat et — iki aynı değer için özet fonksiyonu aynı rasyonel sayıyı döndürür ve bu, ortaya çıkan minimumu hiç etkilemez. Bu yüzden bu algoritmayla benzersiz elemanların sayısını hesaplarız.

Sonuçlar nasıl? (Her satırda tahmin edilen kardinalite var, doğru kardinalite ise 10.000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Pek iyi değil, değil mi? Algoritma, her birinde on bin benzersiz değer bulunan on farklı kimlik kümesinden geçti. Hesaplanan tahminlerin çoğu gerçek değerden epey uzak. Bunların ortalamasını alsak 18.352 değerine ulaşırız. Yine de çok uzak, ama öte yandan bellek ihtiyacına bak — sabit! Minimumu bulmak için belleğinde yalnızca bir değişken tutman yeter; güncel minimumu ona yazarsın, hepsi bu. Yani evet, tahmin berbat, ama neredeyse hiçbir şeye mal olmuyor.

Algoritmayı İyileştirelim

Algoritmanın her şeyden önce kararsız olduğunu görüyoruz — bir seferinde oldukça iyi bir tahmin (9362) veriyor, bir sonrakinde tamamen yanlış bir tahmin (65536). Bundan nasıl kurtuluruz? Girdi verilerini birkaç parçaya bölüp her parça için benzersiz eleman sayısını hesaplayabilir ve sonunda hepsinin ortalamasını güzelce alabiliriz. Kimliğimizin ilk karakterine göre karar verebiliriz. Yani önce “a” harfiyle başlayan kimlikler için benzersiz değer sayısını, sonra “b” harfiyle başlayanlar için ayrı ayrı hesaplarız, vb. Kod:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    min_values = {}
    for item in values:
        first_char = str(item)[0]
        hashed_value = unit_interval_hash(item, n)
        min_values[first_char] = min(min_values.get(first_char, 1), hashed_value)
    average_minimum = sum(min_values.values()) / len(min_values)
    return (int(1 / average_minimum) - 1) * len(min_values)

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Değişiklikler count_unique_using_minimum fonksiyonunda. min_values değişkeninde her grup için minimumu saklıyoruz. Sonunda tüm minimumları toplayıp saklanan değerlerin sayısına bölüyoruz — ortalama minimumu elde ediyoruz. 1/average_minimum ifadesiyle her gruptaki benzersiz değerlerin ortalama sayısını buluyoruz; bu değeri grup sayısıyla çarpınca, verilen veri kümesindeki benzersiz değerlerin tahmini sayısını elde ediyoruz. Peki bu değiştirilmiş yöntem nasıl çalışıyor?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Hâlâ iyi değil, ama kesinlikle daha iyi. Algoritma daha kararlı. Fonksiyonu, grupları ilk karaktere göre değil de örneğin kimliğin ilk iki karakterine göre oluşturacak şekilde değiştirmeyi deneyebiliriz, yani şöyle:

first_char = str(item)[0:2] # ToDo: choose better name for variable

O zaman sonuçlar şöyle olur:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Hmm, bu artık hiç de kötü değil, değil mi? Bir de yüz bin benzersiz değeri, ilk iki karakteri ve n = 24 değerini deneyelim; şu sonuçları elde ederiz:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

İdare eder. Ama merak etme, daha iyi algoritmalar hâlâ var.

Peki bellek ihtiyacı nasıl? Her grup için minimumu saklamamız gerekiyor, başka hiçbir şey değil. Kimlikler onaltılık (hex) biçimdeyse, en fazla 16^x tane minimum değer saklamamız gerekir; burada x, grup anahtarını oluşturduğumuz karakterlerin sayısıdır. Bir minimum bir rasyonel sayıdır, yani double ya da float gibi bir türdür.

Sonda bir not: girdiyi birkaç gruba bölmeyi ancak girdimizde rastgele bir string gibi davranan kimlikler olduğu için yapabildik. Girdide rastgele bir string değil de belirli bir biçimde veriler olsaydı bölmeyi başka türlü yapmamız gerekirdi. Örneğin her kimlik userid- önekiyle başlasaydı, gruplara ilk karaktere göre bölmek herhalde pek işe yaramazdı, değil mi?