Büyük Veri İçerisinde Benzer Öğeleri Bulmak
Benzer Öğeleri Bulmak
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
Kümelere dönüştürme işlemi yapılabilen bu kategorideki problemler de ikiye ayrılmaktadır. Bunlar;
- Metin olarak birbirine benzeyen dokümanların bulunması
- Web’de birbirine benzeyen sayfaları bulma,
- İzinsiz kopyaların bulunması,
- Aynaların (ing. mirrors) bulunması,
- Benzer haberlerin bulunması vb.
- İş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 olanolan ülkelerdeülkelerde tasarruflarıntasarrufları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 olanolan ülkelerdeülkelerde tasarruflarıntasarrufları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.
Kaynaklar
[1] http://infolab.stanford.edu/~ullman/mmds.html
[2] http://en.wikipedia.org/wiki/N-gram
[3] http://www.wikihow.com/Lay-Shingles
[4] http://www.sabah.com.tr/Ekonomi/2014/04/17/erdem-bascidan-istifa-iddiasina-aciklama
[5] http://en.wikipedia.org/wiki/Jaccard_index
[6] Hashing, indexing ve Bloom Filtreleme
[7] http://tr.wikipedia.org/wiki/Perm%C3%BCtasyon
Büyük Veri İçindeki Nadir Görülen Olayların Keşfedilmesi Cloudera Apache Hadoop Geliştirici eğitimini başarıyla gerçekleştirdi