LogLog: Benzersiz Değerlerin Sayısı Nasıl Tahmin Edilir
Linear Counting ve Min Value ile ilgili önceki bölümlerden sonra, veri kümesindeki benzersiz değerlerin sayısını tahmin eden neredeyse en iyi olasılıksal algoritmaya, LogLog’a nihayet geldik. Ondan daha iyisi yalnızca küçük kardeşi HyperLogLog; o da LogLog’dan türüyor, ama onu da bir sonraki yazıda anlatacağız.
Problemi bir kez daha hatırlayalım. Girdi olarak bir veri kümemiz/çoklu kümemiz var; örneğin kimliklerden (ID) oluşan bir dizi ya da üreteç (generator). Bu dizide bazı değerler birden çok kez geçiyor ve biz bu dizideki benzersiz değerlerin sayısını bulmak istiyoruz. Bu sayıya kardinalite diyeceğiz. Kardinalitenin gerçekten çok büyük olmasını bekliyoruz; yoksa bilinen klasik algoritmaları kullanabiliriz.
LogLog Algoritmasının Fikri
İkili vektörlerden oluşan bir küme düşün. Korkma, örneğin 0001011001001100, uzunluğu 16 olan bir ikili vektördür. Diyelim ki uzunluğu 32 olan ikili vektörlerimiz var ve bunlardan toplam bir milyon tane var; hepsi tamamen rastgele üretilmiş. Kaç vektör sıfırla bitecek?
Bunu kesin olarak bilemeyiz, ama vektörleri gerçekten rastgele ürettiysek yaklaşık yarısı, yani 500 bin tanesi sıfırla bitmeli. Kaç vektör 00 ile bitecek? Dörtte biri. 000 ile? Sekizde biri. Ve böyle devam eder. Bunu kabaca şöyle gösterebiliriz:
vektör örüntüsü tüm vektörler içindeki oran
...xxxxxx0 %50
...xxxxx00 %25
...xxxx000 %12,5
...xxx0000 %6,25
... ...
Uzunluğu d olan bir sonek (sonek, başka bir dizgenin sonunda yer alan dizgedir — önekin tersi) için, bu sonekle biten v tane vektör bulmayı bekleriz. v değerini şöyle hesaplarız:
Burada N, kümedeki bütün vektörlerin sayısıdır. Uzunluğu 3 olan bir sonek (örneğin …010) 1/2^3 N = 1/8 N vektörde, yani bütün vektörlerin %12,5’inde görülmelidir.
Şimdi kafa karıştıran küçük bir işlem yapacağız. 1024 benzersiz vektörden oluşan bir çoklu küme olsun. Kaç vektör 0000000000 sonekiyle (on sıfır) bitmeli? Formülde yerine koyarsak
Hoppala, bir tane! Rastgele üretilmiş bin ikili vektörde on sıfırla biten tam olarak bir vektör olmalı. Peki bu bilgiyi benzersiz elemanların sayısını tahmin etmek için nasıl kullanırız? Aslında işi tersinden de yapabiliriz. Girdideki bütün ikili vektörleri taradık ve kümede on sıfırla biten tek bir vektör olduğunu gördük diyelim. O zaman kümede 1024 vektör olduğunu tahmin edebiliriz!
Genelleştirip Algoritmayı Kuruyoruz
Amaç, yalnızca tek bir vektörde bulunan ve mümkün olduğunca kısa olan bir sonek bulmak olmalı. Ama bunu yapmak çok zor; çünkü böyle bir vektörü gerçekten bulmak için bütün sonekleri saklamamız gerekirdi, bunu da istemiyoruz, çünkü çok fazla bellek kaplardı. Bunun yerine vektörün sonundaki en uzun sıfır dizisini aramakla yetineceğiz.
Yani bütün vektörleri tararız, her vektörün sonunda kaç sıfır olduğunu hesaplarız ve bu değerlerin maksimumunu tek bir değişkende tutarız. Bütün vektörleri taradıktan sonra, yalnızca sıfırlardan oluşan en uzun sonekin uzunluğunu biliriz. Bu uzunluğu d harfiyle gösteririz. Şimdi önceki formülü, N değişkeni yalnız kalacak, yani algoritmanın girdisi değil çıktısı olacak biçimde düzenleyelim. Bu arada v yerine bir yazabiliriz, çünkü böyle tam olarak bir vektör bulmayı bekliyoruz, yani v=1 olmasını bekliyoruz.
Demek ki sıfırlardan oluşan en uzun sonekin uzunluğunu, yani d değerini bulursak, kardinaliteyi N=2d formülüyle tahmin ederiz.
Rastgele İkili Vektörler Nasıl Elde Edilir?
Algoritma rastgele ikili vektörlerle zaten çalışıyor, peki bu yöntemi gerçek verilere nasıl uygularız? Her zamanki gibi burada da uygun bir özet fonksiyonu (hash fonksiyonu) kullanacağız. Girdi olarak bir veri kümemiz varsa, örneğin kimlikler (string), önce bunların hash’ini alırız. n bitlik bir özet fonksiyonunun çıktısı n bittir ve bunlar pratik açıdan rastgele üretilmiş ikili vektörlere benzer.
Artık algoritmamızı yazabiliriz:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def count_unique(values):
max_zero_suffix_length = 0
for value in values:
zeroes_length = trailing_zeroes(hash(value))
max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
return 2 ** max_zero_suffix_length
trailing_zeroes fonksiyonu bir sayının sonundaki sıfırların sayısını döndürür. Bunu nasıl yapıyor? Koddan anlamadıysan hiç sorma bence. Peki fonksiyon ne kadar başarılı? Yüz bin benzersiz eleman içeren bir küme için fonksiyon tahmin olarak 524.288 döndürdü.
Eh…
Pek iyi sayılmaz, değil mi? Ama sorun değil! Algoritmayı, önceki Min Value algoritmasında yaptığımız gibi iyileştirmeye çalışacağız. Girdi verilerini birkaç ayrık gruba böleriz, her grup için sıfırlardan oluşan en uzun soneki hesaplarız, sonunda sıfır sonekinin ortalama uzunluğunu bulur ve benzersiz elemanların sayısını tahmin etmek için onu kullanırız.
Örneğin her vektörün son iki bitinin, vektörün ait olduğu grubun numarasını belirlemesini seçebiliriz. Şu altı vektörü
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
bitiş kısımlarına göre dört gruba ayırabiliriz:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Sonra her vektördeki en uzun sıfır sonekinin uzunluğunu hesaplarız; ancak grup numarası olarak kullandığımız bitleri atlarız. Sıfırlardan oluşan “sonekleri” yeşil işaretleyelim:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
Sonuçta ilgili gruptaki en uzun sıfır soneklerinin uzunlukları elimizde. Bu uzunluklardan aritmetik ortalamayı hesaplayabiliriz; sonuç 2,75 çıkar. Bu değeri formülde yerine koyarsak
çıkar. Bu, her gruptaki benzersiz elemanların ortalama sayısıdır. Elbette hiç de tutmuyor, ama buna takılmayalım; küçük kümelerde LogLog algoritması berbat sonuçlar verir.
Bütün kümenin kardinalitesini tahmin etmek için bu değeri grup sayısıyla da çarpmamız gerekir: 6,727 · 4 = 26,908. Algoritma kümede yaklaşık 27 benzersiz değer olduğunu hesapladı. Aslında altı tane vardı, yani tamamen yanlış, ama şu an gerçekten önemli değil.
Algoritmanın Uygulanması
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(values, k):
num_buckets = 2 ** k
max_zeroes = [0] * num_buckets
for value in values:
h = hash(value)
bucket_index = h & (num_buckets - 1)
bucket_hash = h >> k
num_zeros = trailing_zeroes(bucket_hash)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets
k parametresi, kaç bitin grup indeksi olarak alınacağını belirler. Bu parametre algoritmanın doğruluğunu belirler — k ne kadar büyükse doğruluk o kadar yüksektir. bucket_index değişkeninde grup numarası saklanır. Eşittir işaretinin sağ tarafındaki o büyü nasıl çalışıyor?
num_buckets değişkeninde grup sayısı vardır; bu her zaman ikinin kuvvetidir. Örneğin k = 3 ise num_buckets=8 olur. 8 sayısı ikili sistemde 1000 biçimindedir. Ondan bir çıkarırsak 0111 biçimindeki 7 sayısını elde ederiz. num_buckets sayısından bir çıkardığımızda her zaman sonunda k tane bir, öncesinde ise yalnızca sıfırlar olan bir sayı elde ederiz. Sonra mantıksal VE işlemini (yani & operatörünü) uygularız. 1110110010100101 vektörü için bu işlem şöyle görünür:
1110110010100101
& 0000000000000111
------------------
0000000000000101
Bütün bu büyünün amacı, başında yalnızca sıfırlar bulunan ve son k biti verilen h hash’iyle aynı olan bir sayı elde etmektir.
Sonra bucket_hash değerini hesaplarız. Bu, asıl hash’ten son k bitin atılmasıyla elde edilir; bunun için hash’in tamamını k bit sağa kaydırırız. Kaydırma, sayıdaki bütün bitleri k bit sağa iter ve sayıyı soldan sıfırlarla doldurur. (Bir bit sağa kaydırma, sayıyı ikiye bölüp kalanı atmakla aynı davranır.) 1110110010100101 vektöründen üç bit kaydırınca 0001110110010100 elde ederiz. Bu vektör bucket_hash değişkeninde saklanır.
Sonra bu vektörün sonundaki sıfırların sayısını hesaplarız; bu değer max_zeroes dizisinde bucket_index indeksinde saklanan mevcut maksimumdan büyükse değeri üzerine yazarız.
En sonunda bütün gruplardaki sıfır sayısının ortalamasını hesaplar ve her gruptaki ortalama benzersiz eleman sayısını buluruz (2 ** average_max_zeros). Toplam num_buckets grubumuz olduğundan bu değeri grup sayısıyla çarparız ve benzersiz elemanların sayısı için nihai tahmini elde ederiz. Oh, hiç de acıtmadı. İşte 250.000 benzersiz eleman içeren ve k=10 olan birkaç veri kümesi için sonuçlar:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Yoook, hâlâ yanlış :-(. Ama oldukça yaklaştık, merak etme. Bütün sonuçların doğru sonuçtan büyük olduğuna dikkat et. Algoritmanın seyrinde çeşitli hatalar birikir ve bu yüzden tahmin doğru sonuçtan belirgin biçimde büyük çıkar. Yine de bu hatalar epeyce sabittir ve hatanın ne kadar büyük olduğu kestirilebilir. Tahmini 0.79402 gibi deneysel bir sabitle çarparsak çok daha iyi sonuçlar elde ederiz:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Bir de kardinalitesi bir milyon olan bir çoklu kümeyi denedim; sonuçlar:
Sonuç Hata
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Çok güzel! Hata %2,5’in altında kalıyor, bu da iyi bir performans. Ve işte bu, hanımlar beyler, LogLog algoritması. Sabitle birlikte nihai uygulama şöyle görünüyor:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(values, k):
num_buckets = 2 ** k
max_zeroes = [0] * num_buckets
for value in values:
h = hash(value)
bucket_index = h & (num_buckets - 1)
bucket_hash = h >> k
num_zeros = trailing_zeroes(bucket_hash)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets * 0.79402
Efsanevi ve en en iyi HyperLogLog’u elde etmek için bu algoritmanın nasıl geliştirileceğini bir sonraki yazıda anlatacağız. Şimdilik algoritmanın bellek açısından ne kadar yük getirdiğine bakalım.
Bellek İhtiyacı
Algoritma, kapladığı bellek açısından çok verimlidir. Hatırlamamız gereken tek şey, maksimumları tutan dizidir. Bu dizinin uzunluğu k değerine, yani vektörden grup indeksi olarak aldığımız bit sayısına bağlıdır. Belirli bir k için toplam 2k farklı grubumuz vardır ve bu yüzden maksimum dizisinin uzunluğu 2k olur. Bu değere uygulamada num_buckets adını verdik.
Dizinin bir hücresi ne kadar büyük olmalı? İçine sıfır soneklerinin uzunluklarını koyacağız. Baştan söyleyeyim, 64 bitlik bir hash büyük olasılıkla dünyadaki akla gelebilecek bütün çoklu kümeler için yeterlidir; yani bu diziye 0’dan (yalnızca birlerden oluşan vektör) 64’e (yalnızca sıfırlardan oluşan vektör) kadar sayıları koyabilmemiz gerekir. Ayrıca k her zaman sıfırdan büyük olacaksa, yalnızca 0’dan 63’e kadar sayıları saklamamız yeter. Bunun için yalnızca 6 bit yeter, o kadar; çünkü 26 = 64.
Evet, bir hücresi 6 bit olan bir “dizi” bize yeter. Ayrıca k=10 değerinin, kardinaliteyi yüz milyonlar mertebesine kadar oldukça iyi tahmin etmeye yettiğini de söyleyebilirim. Bu şekilde ayarlanmış algoritma, her hücresi 6 bit yer kaplayan, 210 = 1024 uzunluğunda bir dizi oluşturur. Bu dizi toplam 6.144 bit, yani 768 bayt kaplar. Bir kilobayttan bile az.
Hepsi bu kadar.
Başka bir şey saklamamız gerekmiyor; hesaplanan hash’leri hemen atabiliriz, vektörün sonundaki sıfır sayısını bilmemiz yeter.
Dikkat et: örneğin 128 bit döndüren daha büyük bir özet fonksiyonu kullansaydın, bellek ihtiyacı pek değişmezdi. Çünkü 0’dan 127’ye kadar sayıları saklamamız gerekirdi, bunun için de 7 bit yeter. Yani bellek ihtiyacını esas olarak k parametresi, yani grup sayısı belirler.
LogLog en çok kardinalitesi gerçekten büyük çoklu kümeleri saymamız gereken yerlerde işe yarar. Yukarıdaki basit örnekte de görüldüğü gibi, LogLog, kardinalitesi küçük olan çoklu kümelerle pek iyi başa çıkamaz. Buna da çare bulunabilir; örneğin çoklu kümenin kardinalitesinin düşük olduğunu fark edersek, tahmin için başka bir algoritma, örneğin daha önce anlattığımız Linear Counting algoritmasını kullanabiliriz. Bundan da bir sonraki yazıda söz edeceğiz.
Kaynaklar:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (LogLog kodu aşağı yukarı buradan alınmıştır)
Bölümler: Linear Counting: Benzersiz Değerlerin Sayısı Nasıl Tahmin Edilir, Min Value: Benzersiz Değerlerin Sayısı Nasıl Tahmin Edilir, LogLog: Benzersiz Değerlerin Sayısı Nasıl Tahmin Edilir, HyperLogLog: Benzersiz Değerlerin Sayısı Ne Kadar Doğru Tahmin Edilir
