Büyük veri
içindeki benzer öğeleri bulma, sıkça karşılaşılan ve çözülmesi kolay olmayan
bir problem dizisi yaratmaktadır. Birbirine benzeyen bazı çözüm yolları
içinden, biz bu yazıda çoğunlukla Mining
of Massive Datasets
[1] kitabının üçüncü bölümünde anlatılan çözümü temel alacağız. Bu çözümü
anlamaya çalışan okuyucunun karşısına iki zorluk çıkmaktadır. Birincisi, çözüm
temel olasılık, küme teorisi ve matris bilgisi gerektirdiğinden, bu konulara
uzak olan ya da uzak kalmış kişiler için sıkıntı oluşturabilir. İkincisi,
algoritma birden fazla alt algoritmadan oluşmakta ve bu algoritmaların birbiri
ile olan ilişkisi çözümün anlaşılmasını zorlaştırmaktadır. Bu nedenle çözümü
anlatırken, bu zorlukları aşmak adına araya bazı ek bilgiler girecek ve
örneklemeler vereceğim. Umarım bu zor konuyu, daha anlaşılır yapabilirim.
Problemin
tanımı
Büyük verilerin işlenmesi
konusu kapsamında bakıldığında benzer öğeleri bulma problemi
iki ana alt grupta toplanır. Bunlar benzerliğin;
- Kümelerin kesişimi problemine dönüştürülebildiği problemler,
- Kümelerin kesişimi problemine dönüştürülemediği ve herhangi bir uzayda uzaklık ölçme teorisinin kullanıldığı problemler.
İkinci bahsettiğimiz
problemlere bir örnek, kısıtlama ve kontrol olmayan bir ara yüz vasıtası ile serbestçe
girilmiş adres alanının çözümlenip diğer adresler ile karşılaştırılması
probleminde karşımıza çıkar. Bu durumda yazım yanlışları ve kısaltmalar çokça
yapıldığı için, kelimelerin üzerinde tanımlanan çok boyutlu bir uzayda,
kelimelerin birbirine yakınlığı için bir metrik, uzaklık fonksiyonu tanımlanır.
Bu şekilde ‘Hakn
Caddsi’ yazıldığında ‘Hakan Caddesi’ olduğu ortaya çıkarılabilir. Bu
fonksiyonlara klasik bir örnek Düzenleme
Uzaklığı (ing. Edit Distance) fonksiyonudur. Bu konuyu ileride ayrı bir yazıda
ele almayı düşünüyorum.
Bu yazımızda birinci kategorideki, kümelerin kesişimi
problemine dönüştürülebilenler ile ilgileneceğiz.
Kümelerin
kesişimi problemine dönüştürmek
- Web’de birbirine benzeyen sayfaları bulma,
- İzinsiz kopyaların bulunması,
- Aynaların (ing. mirrors) bulunması,
- Benzer haberlerin bulunması vb.
2. İşbirliği filtreleri (ing.
Collaborative Filtering)
- Benzer müşterilerin bulunması,
- Benzer ürünlerin bulunması vb.
Bu problemlerin birbirine
benzemesi nasıl olabilir? Anahtar kavram, benzerliklerin ele alınış tarzı ile
ilişkilidir. Elimizdeki problemi, kümelerin kesişimi olarak ele almanın yöntemini,
yukarıdaki örneklerden birbirine benzeyen
dokümanları bulma problemine uygulayarak göstereceğiz.
Herhangi şeylerin tekrarsız
olarak bir arada bulunabildiği yapı olarak kümeyi tanımlayalım. Dokümanı bir
küme olarak göstermek için dokümanda geçen kelimeleri, birer eleman olarak bu
kümeye dahil edelim. Bu durumda, her bir doküman bir
küme ile temsil edilmiş olur ve dokümanların birbirine benzerliğini kümeler
teorisinin temel işlemleri olan kesişim
ve birleşim ile ifade edelim. Kesişim
iki kümenin ortak elemanlarını bulma, birleşim
ise iki kümenin bütün elemanlarını tekrarlar olmaksızın bir kümede toplama
işlemidir.
Tanım : Benzerliği, A ve B ismindeki iki
kümenin kesişiminin, aynı kümelerin birleşimine oranı
olarak tanımlayalım. | A | ile A kümesinin eleman sayısını gösterelim.
Bu durumda
Benzerlik(A, B)
= |A ∩ B| / |A U B|
A ve B aynı kümeler ise benzerlik değeri 1.0, kesişimleri olmayan ve sembol
olarak Ø ile gösterilen iki küme ise benzerlik değeri 0.0 olur. Hemen fark edilebileceği
üzere, bu yaklaşımın önemli bir zayıflığı vardır.
Şimdi bunu 17 Nisan tarihli bir gazete haberinden [4]
aldığımız ve Merkez Bankası Başkanı Erdem
Başçı ya ait olduğu söylenen şu cümleye uygulayalım.
1.cümle
“ … gelişmekte olan
ülkelerde tasarrufların düştüğünü, borçlanmanın arttığını, özellikle gelişmekte
olan 5 büyük ülkede cari açık verildiğini söyledi.”
Yöntemdeki zayıflığı göstermek için, bu cümleyi biraz
farklılaştıralım.
2.cümle
“ … gelişmekte
olan ülkelerde tasarrufların arttığını, borçlanmanın düştüğünü,
özellikle gelişmekte olan 5 büyük ülkede cari fazla verildiğini
söyledi.”
Bu cümlelerden oluşan dokümanlarımızda tekrarlanan
kelimeleri attığımızda elimize geçen kümeler,
A = { gelişmekte, olan, ülkelerde, tasarrufların, düştüğünü,
borçlanmanın, arttığını, özellikle, 5, büyük, ülkede, cari, açık, verildiğini, söyledi }
B = { gelişmekte, olan,
ülkelerde, tasarrufların, arttığını, borçlanmanın, düştüğünü, özellikle, 5,
büyük, ülkede, cari, fazla,
verildiğini, söyledi }
Benzerlik(A,
B) = 14 / 16 = 0,88
Birbirine benzer gibi görünen,
fakat anlam olarak farklılık taşıyan birinci ve ikinci cümlenin
değerlendirilmesi için 0,88 değerini beklediğimizden yüksek bir benzerlik oranı
olarak değerlendirebiliriz. Sıkıntı, kümenin elemanlarını oluşturan kelimelerin
sırasının kaybedilmesi ile oluşuyor. Bu zayıflığın giderilmesi için öne çıkan
yöntem, kümenin elemanları içine bu sıralamanın katılmasını sağlayan özel bir
tekniğe dayanıyor.
Shingling
Bir metin içinde geçen
karakterlerin, her bir alt grup kendinden önceki alt gruptan bir veya daha
fazla karakter veya kelime bulunduracak şekilde bölümlendirilmesine shingling adı verilmektedir. Bu şekilde ortaya çıkan
her bir alt grup hesaplamalı linguistik de n-gram [2], büyük veri literatüründe ise shingle olarak isimlendirilir. Shingle
kelimesinin, yapılarda çatı katlarına uygulanan bir kaplama tekniğinden [3]
esinlenilerek, bu tekniğe verildiğini düşünenlere katılmamak elde değil.
|
Bu tekniğe göre, her bir shingle için bir boyut ve mehter alayının ilerlerken iki
adım ileri, bir adım geri gitmesine benzer olarak, her ileri gidişte kaç adım
geri gelineceği belirleniyor. Boy için karakter bazlı
gidilebileceği gibi, kelime bazlı da gidilebilir. Kelime bazlı işleyişe örnek
olarak, k = 2 shingle boyu ve 1 de geri gelme sayısı olmak üzere,
yukarıdaki kümeleri şu şekilde ifade edebiliriz.
A kümesi
|
B kümesi
|
“
… gelişmekte olan ülkelerde tasarrufların düştüğünü,
borçlanmanın arttığını, özellikle gelişmekte olan 5 büyük ülkede cari açık
verildiğini söyledi.”
|
“
… gelişmekte olan ülkelerde tasarrufların arttığını,
borçlanmanın düştüğünü, özellikle gelişmekte olan 5 büyük ülkede cari fazla
verildiğini söyledi.”
|
gelişmekte olan
olan ülkelerde
ülkelerde tasarrufların
tasarrufların
düştüğünü
düştüğünü
borçlanmanın
borçlanmanın
arttığını
arttığını
özellikle
özellikle gelişmekte
olan 5
5 büyük
büyük ülkede
ülkede cari
cari açık
açık verildiğini
verildiğini söyledi
|
gelişmekte olan
olan ülkelerde
ülkelerde tasarrufların
tasarrufların arttığını
arttığını borçlanmanın
borçlanmanın düştüğünü
düştüğünü özellikle
özellikle gelişmekte
olan 5
5
büyük
büyük ülkede
ülkede cari
cari fazla
fazla verildiğini
verildiğini söyledi
|
6 farklı shingle, toplam 15
|
6 farklı shingle, toplam 15
|
Benzerlik = 9 / 21 = 0,43
|
şeklinde
küme elemanları haline getirilir. Bu iki cümlenin birbirine benzerliği ilk
yöntem ile bulunan 0,88 e göre gerçeğe
daha uygun olarak 0,43 e düşer.
Bu işlemden sonra, elemanları 2
kelimeden oluşan katarları içeren ve her biri bir dokümana karşılık gelen
kümeler ortaya çıkmış olur. Bu şekilde tanımlanmış olan benzerlik ölçüsüne, ilk
ortaya atan kişi olan Paul Jaccard’dan dolayı Jaccard Indeksi ismi
verilmiştir [5].
Benzer
“Benzerlik Problemleri”
- “benzer müşterilerin bulunması” problemi; müşteriler kümeleri, müşterinin araştırılan davranışını ifade edenler (örnek: satın aldıkları ürünler) bu kümelerin elemanları olarak modellenebilir. Bu durumda yüksek Jaccard indeksine sahip olan müşterileri, birbirine benzer zevkleri, alışkanlıkları olan müşteriler olarak ele alabiliriz.
- “Benzer ürünlerin bulunması” problemi; ürünler kümeleri,
müşteriler bu kümelerin elemanlarını ifade edecek şekilde kurgulanabilir.
Buradan yola çıkılarak, iki ürün, satın alan müşterileri ifade eden küme
elemanlarının karşılaştırılması sonucu, yüksek Jaccard
indeksine sahip iseler benzer ürün veya ilişkili ürünler olarak
nitelendirilebilirler.
Her problemde hesaplanan değerin değerlendirilmesinde
kullanılacak eşik değeri, probleme özgü olarak belirlenmelidir.
Bellek kullanımı
Shingling
işlemi doğruluğu arttırmakta fakat bir maliyet çıkarmaktadır. İşlem sonrası her
bir doküman bellekte çok daha fazla yer tutar ve işleme zamanı da şüphesiz buna
bağlı olarak artar.
Kümeleri temsil eden veri
yapılarının, bellekte kaplayacağı alanın büyüklüğünün, doküman sayısına ve
dokümanların boyutuna bağlı olacağı açıktır. Her bir küme, N dokümandaki karakter sayısı, k
ise shingle sayısı olmak üzere N – ( k – 1 ) adet küme elemanı içerir. Örnek olarak, yaklaşık her birinin
ortalama 3000 karakter içermesi ve k = 5 seçilmesi durumunda 3000 - ( 5 – 1 ) = 2996 tane elemanı
olan küme karşılık gelir. Küme sayısının artması bellek kullanımını ciddi bir
miktarda arttıracaktır.
Shingle
seçerken karakter değilde, kelime üzerinden gidilecek
olunursa, her bir küme elemanının ortalama 30 byte lık bir alan kapladığı varsayımı altında, 100.000 doküman/küme
olduğu bir durumda 100.000 x 2996 x 30 = 8.4 GB bir
alan sadece küme elemanları için kullanılması gerekmektedir.
Alt Problem
: Kullanılan bellek miktarının çokluğu
Doküman sayısının dolayısı ile
karşılık gelen küme ve içindeki elemanların sayılarının artması ile bu rakamın
çok üzerine çıkılacağı açıktır. Bu nedenle, kümeleri hem yer probleminin önüne
geçmek, hem de sonuçta her bir kümenin diğerleri ile karşılaştırılması
sırasında gerekecek işlem zamanını azaltmak için, akıllıca bir çözüm bulmak
zorunluluğu ortadadır. Bu çözüm paralel işlem yapma olanağı da vermelidir ki,
kısa zamanda sonuca ulaşmak mümkün olsun.
Her bir küme elemanının daha
küçük bir alanda gösterimini sağlamak için, yazılım algoritmalarında çokça
kullanılan Hashing fonksiyonlarından [6] faydalanmak uygun
bir çözümdür. Bu sayede değişik boyutlarda, yerine göre onlarca byte olan her bir elemanı, bellekte sabit bir alan kaplayan
bir sayıya çevirmek mümkündür. Bu işlem ile tekrarlardan da kurtulmak
kolaylaşmış olmaktadır. Aynı eleman hep aynı hash
değerini alacaktır.
Bunun için her bir elemana hashing fonksiyonu uygulanarak bir makine komutu ile
işlenebilen hale getirmek faydalıdır. Bu algoritmanın üzerinde çalışacağı
makinanın 32 bit veya 64 bit olmasına göre 4 veya 8 byte
lık bir gösterim alanı anlamına gelmektedir. Bu
şekilde iki elemanın karşılaştırılması işlemi, uzun ve karmaşık katar
fonksiyonları kullanmak yerine, tek bir sayı karşılaştırma işlemi ile
yapılabilir hale gelir.
Kümelerin Benzerliğinin Korunduğu
Özetler
Hashing
fonksiyonları kullanarak elemanların kapladığı alanı küçültmek faydalıdır ama
büyük veri ile çalışıyorsanız, bu bile yeterli gelmeyebilir. Bu durumda
karşılaştırma için kullandığımız kümeleri daha da küçük bir alan kaplayacak
şekilde bir gösterim yolu bulabilir miyiz?
Matris Gösterimi
Bellekte kullanılan alan optimizasyonu için matrislerden yararlanacağız. Sütunları
kümeler, satırları ise evrensel küme elemanları olan bir matris kurgulayalım.
Evrensel küme bütün kümeleri içinde barındıran küme olarak tanımlansın. Buradan
itibaren hesaplamaları ve gösterimleri yer kısıtımızı
da gözeterek kolaylık açısından şöyle gösterelim. Dokümanların shingling yapılmış ve karşılık gelen elemanlarına hash fonksiyonu uygulanmış hallerini a, b, c, d, e ile gösterelim.
Evrensel Küme E ={a,b,c,d,e}
Alt kümeler, yani
dokümanlarımız;
S1={a,d}
S2={c}
S3={b,d,e}
S4={a,c,d}
İki boyutlu matrisler genel
olarak dokümanlarda sıkça kullandığımız tablolara benzerler, üst satırdakiler
matris sütun indeksi, sol tarafta bulunan sütundakiler ise satır indeksi olarak
ele alınırlar. Her hangi bir eleman örnek olarak (1,2) yani ilk satırın ikinci
elemanı olarak gösterilebilir. Buna göre yukarıdaki kümeler matris olarak,
aşağıdaki matris ile gösterilebilir ve bu matriste (1,2) elemanı (a, S2) elemanı anlamına
gelir ve değeri 0 dır.
S1
|
S2
|
S3
|
S4
|
|
a
|
1
|
0
|
0
|
1
|
b
|
0
|
0
|
1
|
0
|
c
|
0
|
1
|
0
|
1
|
d
|
1
|
0
|
1
|
1
|
e
|
0
|
0
|
1
|
0
|
Bu matris, sıfırdan farklı elemanlarının sayısının,
elemanların sayısının yarısından çok olması nedeni ile literatürde
seyrek (ing. Spare) matris
olarak isimlendirilir. Seyrek matrisler, hem bellekten kazanmak hem de işlemler
sırasında avantaj sağladığı için, bellekte tutulurken matris yapısında değil, sadece
sıfırdan farklı elemanların dikkate alındığı tuple
yapısında tutulur. Tuple değerlerin sırasının önemli
olduğu bir çeşit liste yapısıdır. Yukarıdaki matrisin ilk satırı şu şekilde gösterilebilir.
( ((a,S1),
1), ((a,S4), 1) ) veya (a,((S1,
1), (S4, 1)) )
Minhashing
Yukarıdaki matris üzerinden Jaccard Benzerlik fonksiyonu ile kümelerin ikili
benzerlikleri kolayca hesaplanabilir. Fakat eleman sayısı arttıkça bellek
ihtiyacı da artar. Amacımız belleği en az kullanarak bu hesabı yapmak olunca,
şu ipucu ile bir yöntem geliştirebiliriz. Matristeki her bir kolona yani kümeye
uygulanabilen öyle bir h fonksiyonu
bulalım ki bu amacımıza ulaşabilelim.
Bunun için bu fonksiyon iki
özelliği gerçeklesin.
- Bellekte tutulabilecek şekilde her bir S için küçük bir imza yaratabilelim.
- Benzerlik(Si, Sj) ile, h(Si) ve h(Sj) imzalarının benzerliği eşit olsun.
Bu iki koşulu birleştirelim ve
öyle bir h fonksiyonu bulalım ki,
- Benzerlik(Si, Sj) yüksek ise, yüksek olasılıkla h(Si) = h(Sj) olsun.
- Benzerlik(Si, Sj) düşük ise, yüksek olasılıkla h(Si) ≠ h(Sj) olsun.
Bu durumda hash
fonksiyonu kullanarak dokümanları her biri bir sayıya karşılık gelen kovalara
koyalım ve birbirine benzer doküman ikililerinin çoğunlukla aynı kovalara
konmasını bekleyelim.
Bunu sağlayan bir hash fonksiyonu Minhash olarak
bilinir ve aşağıdaki şekilde tanımlanır.
Minhash Fonksiyonu
Tanım : π, E kümesi üzerinde alınan herhangi bir permütasyon olsun. Yukarıdaki matriste S kümesinin bu permütasyon sırasına göre
1 değerini aldığı ilk elemanın sıra değeri bu kümenin minhash
değeri olarak nitelendirilir ve matematiksel olarak
hπ(S) = min π(S)
olarak
gösterilir. Bu şekilde söylenince karışık gelmiş olabilir, bunu daha anlaşılır
bir şekilde ifade edelim.
Açıklaması
:
Minhash
işlemi, yukarıdaki matris üzerinden gidecek olursak, ilk kolondaki elemanların
herhangi bir permütasyonunun [7] alınması ile başlar.
Permütasyon almayı, konu bağlamında kısaca, kümenin
elemanlarını bir torbada toplayıp her defasında bir adet elemanı rastgele
torbadan çekmek ve bunu iadesiz olarak bütün elemanlar bitene kadar yapmak, bu
işlem sırasında çekme sırasını not almak olarak tarif edebiliriz. Bu şekilde
torbada eleman kalmayınca olası permütasyonlardan biri
yani π alınmış
olur. İstendiği sayıda permütasyon için işlem
tekrarlanır.
Permütasyon alındıktan sonra, permütasyon sırasına göre yani torbadan çekme sırasına göre
her bir kolonda ilk 1 değerine karşılık gelen eleman, o kolonun Minhash değeri olarak isimlendirilir.
Örnek olarak, E kümesinin bir permütasyonu
yani dizilişi π = { b, e, a, d, c }
olarak alınabilir. h
minhash fonksiyonunu göstermek üzere h(S1) → a değerine karşılık
gelen sıra yani h(S1)=3 olur. Burada yapılan, sırası ile b değeri, e değeri, ve a değerinin S1
kolonunda 1 e karşılık gelip gelmemesine bakmak, b ve e için 0 olduğundan
geçmek, a için 1 olduğundan orada
durmaktır. Benzer şekilde h(S2)=5
e karşılık gelir.
Tabii burada bütün elemanların
tutulması ve gerekirse her birine bakılması gerektiği görülmektedir. Acaba
benzerlik değerini belli bir hata payını göze alarak sadece elemanların
bazılarına bakarak bulabilir miyiz? Bu şekilde hem işlem sayısı açısından, hem
de kullanılan bellek miktarı açısından önemli bir kazanım sağlamamız mümkün
olabilecektir.
MinHash İmzaları
Yukarıdaki şekilde bir
matrisimiz olsun ve M olarak
isimlendirelim. Kümeleri daha az bellek birimini kaplayacak şekilde temsil
etmek için, M nin
satırlarının n tane permütasyonunu üretelim. Duruma
göre, 100 veya yüzlerce sayıda üretilebilir. Bu permütasyonlar
ile belirlenen minhash fonksiyonlarını h1, h2, … ,
hn ile gösterelim. Bu durumda S sütununun
minhash imzasını [ h1(S), h2(S), … , hn(S)
] vektörü ile gösterebiliriz. M matrisinin ilgili kolonunun minhash
imzası ile oluşturulan her bir vektörü, M matrisinde kendi sütununun
bulunduğu yere koyarak imzalardan oluşan bir M matrisi elde ederiz. Dikkat
edilirse burada imza matrisi, M ile
aynı sayıda kolondan oluşuyor ama satır sayısı n ile sınırlıdır. Bu şekilde çok
sayıda elemanı olan bir dokümanı yani kümeyi az sayıda eleman ile temsil etmiş
oluruz. Dolayısı ile imza matrisimiz, asıl M matrisi ile karşılaştırıldığında
oldukça küçük bir alanı kaplar.
Minhash İmzalarının Bulunması
Yukarıda anlatılan algoritma
ile Minhash imzaları hesaplansa da, çok büyük M
matrisleri için yine de uygulanabilir değildir. Bu nedenle pratikte
uygulanabilir bir algoritmaya ihtiyaç vardır. Rastgele permütasyonun
etkisini öyle bir hash fonksiyonu seçerek simüle edebiliriz ki, her bir satır numarasına karşılık
satır sayısı kadar hash kovası içinden bir kova denk
gelsin. Bu aşamada dikkat edilecek nokta, klasik Hash
fonksiyonlarının aynı kovada birden fazla eleman düşürmesi normal ve beklenen
özelliği olmasına karşın, burada seçeceğimiz hash
fonksiyonlarının her bir kovaya mümkün olduğunca tek eleman düşecek şekilde
seçilmesidir.
Bu nedenle satırların n defa rasgele permütasyonunu
almak yerine, n tane rasgele seçilmiş hash fonksiyonu
h1, h2, … , hn
yi ilgili satırlar üzerinde hesaplıyoruz. Örnek
olarak x + 1 mod 5 yukarıdaki matris
için bu şekilde bir hash fonksiyonudur.
Satır numarası
|
H1 = x + 1 mod
5
|
H2 = 3 x + 1 mod 5
|
0
|
1
|
1
|
1
|
2
|
4
|
2
|
3
|
2
|
3
|
4
|
0
|
4
|
0
|
3
|
Bu hash
fonksiyonlarını kullanarak M nin imzası olan göreceli
küçük matrisi elde edebiliriz. Başlangıç olarak sütunlar kümeleri, satırlar
seçtiğimiz fonksiyonları göstersin. Matrisin her bir elemanının başlangıç
değeri olabilecek en büyük değer olarak ∞ yani sonsuz seçilir.
S1
|
S2
|
S3
|
S4
|
|
h1
|
∞
|
∞
|
∞
|
∞
|
h2
|
∞
|
∞
|
∞
|
∞
|
Algoritma her bir r satırı için şu şekildedir.
- Her bir hash fonksiyonu için h1(r), h2(r), … , hn(r) hesaplanır.
- Her bir S kolonu için şu işlemler yapılır;
- r satırındaki S kolonuna karşılık gelen değer 0 ise herhangi bir şey yapılmaz.
- r satırındaki S kolonuna karşılık gelen değer 1 ise, sırasıyla i=1,2,…,n değerleri için Benzerlik(i,S) değeri min( Benzerlik(i,S) nin o anki değeri, hi(r) )
Bu algoritma kullanılarak imzayı elde edelim.
Öncelikli olarak h1(0) = 1 ve h2(0)
= 1 olduğu görülür. 0 satırındaki değerlere baktığımızda sadece S1
ve S4 e karşılık gelen değerler 1, o halde bu değerlerde değişiklik
olabilir.
Min(∞, h1(0) = 1) = 1 ve Min(∞, h2(0) = 1) = 1
S1
|
S2
|
S3
|
S4
|
|
h1
|
1
|
∞
|
∞
|
1
|
h2
|
1
|
∞
|
∞
|
1
|
İkinci satır yani r=1 için h1(1) = 2 ve h2(1)
= 4 olduğu görülür. 1 satırındaki değerlere baktığımızda sadece S3 e
karşılık gelen değer 1, o halde bu sütundaki değerlerde değişiklik olabilir.
Min(∞, h1(1) = 2) = 2 ve Min(∞, h2(1) = 4) = 4
S1
|
S2
|
S3
|
S4
|
|
h1
|
1
|
∞
|
2
|
1
|
h2
|
1
|
∞
|
4
|
1
|
Bu işlemleri bu şekilde devam ettirdiğimizde üç adım
sonra şu matris elde edilir.
S1
|
S2
|
S3
|
S4
|
|
h1
|
1
|
3
|
0
|
1
|
h2
|
0
|
2
|
0
|
0
|
Bu imza matrisinden kümelerin Jaccard Benzerlikleri hesaplanabilir. İlk bakışta
görüleceği üzere S1 ve S4 kolonları aynıdır yani
Benzerlik(S1, S4) = 1.0 dir. İlk matrise baktığımızda Jaccard
benzerliğinin 2/3 olduğunu görüyoruz. Buradan, gerçek benzerlik 2/3 e yaklaşım
için 2 hash fonksiyonunun az kaldığını, fonksiyon
sayılarını arttırdığımızda gerçeğe daha fazla yaklaşacağımızı söyleyebiliriz.
Öte yandan Jaccard Benzerlik kestirimi imza
matrisinden Benzerlik(S1, S2) = 0 dır ve bu gerçek benzerliktir.
Yerel Duyarlı Hashing (LHS)
Belki garip gelecek ama şu ana
kadar yaptığımız tüm bu işlem ve çözümler, büyük veri ile çalışırken bazı dokümanların
ikili benzerliklerini hesaplamak için yetersiz kalabilir. Bunun nedeni,
dokümanların ikili karşılaştırmalarının sayısının çok fazla olabilmesidir. Örnek
olarak 1.000.000 dokümanı karşılaştırmak isteyelim. Bu üstel gösterimle 106
edecektir. İmzaların 250 tane olduğunu düşünürsek, her bir dokümanın imzası
için 1000 byte kullanılır. Bu durumda ikili kombinasyonlarını yani 106 C 2 yi hesaplarsak yaklaşık
1012/2 =
5 x 1011
ikili
eder. İkili karşılaştırmaların her birinin tahmini 1 mikro saniyede yapıldığını
kabul etsek, saniyede 1.000.000 yani 106 karşılaştırma yapılabilir.
Bu şartlarda tüm hesaplamaları yapmak 6 gün sürebilir.
Yapılacak işi azaltmadan,
paralelliği kullanarak hesaplama zamanını azaltabiliriz fakat istediğimizi yine
de elde edememe durumu olabilir. Bu hesaplamayı daha kısa zamanda yapmak için,
benzerlikleri her bir ikili için değil de sadece belli bir eşik değerini geçen
ikililer için hesaplayamaz mıyız? Evet, bu yönteme Yerele Duyarlı Hashing (ing. Locality
Sensitive Hashing – LSH)
denmektedir.
Bunun için yaptığımız hash işleminin tekrarlı olarak farklı fonksiyonlarla
yapılması, bu tekrarlar sonucunda aynı hash kovasına
en az bir kere girenlerin benzer olabileceklerine, girmeyenlerin ise
benzemediklerine hükmedebiliriz. Tabii bu yöntem ile belli bir hata yapmayı da
kabul etmiş oluyoruz. Yanlış Pozitif hatalar, aynı kovaya girip de
benzemeyenler, gereksiz işlem yapmamıza neden olurlar. Doğru Negatifler ise
aynı kovaya girmemelerine rağmen benzer olanlardır. Bu algoritma detayı için [1] e bakılabilir.
Sonuç
Görüldüğü üzere benzer öğeleri bulma probleminin basit
bir çözümü yok. Fakat bu kategorideki mevcut problemleri ve çözüm yöntemlerini
anlamak, eldeki probleme özgü sıkıntı noktalarını tespit etmek için ciddi bir olanak
sunuyor. Bu şekilde hali hazırda bu algoritmaları kullanan kütüphane veya
ürünleri kendi problemimizi çözmek için kullanırken, arka plandaki işleyişin
farkında olmanın bize getireceği avantajlardan yararlanabiliriz. Ayrıca, kendi problemlerine
özgü çözüm geliştirmek isteyen geliştiricilerin, probleme özel kendi algoritmalarını
geliştirmeleri gerektiği durumlarda da faydalı olacaktır.
Not: Bu yazım ilk olarak 7 Mayıs 2014 tarihinde www.devveri.com da yayımlanmıştır.
Kaynaklar
[1] http://infolab.stanford.edu/~ullman/mmds.html
Yorumlar