Doküman Benzerliği (Shingling, Minhashing ve LSH)

Doküman benzerliği bulurken uygulanacak farklı yöntemler mevcut. Bu yöntemlere örnek olarak Shingling, Minhashing ve LSH verilebilir. Benzerliği bulurken bu metodları hangi sıra ile ve ne amaçla kullanabileceğimiz aşağıdaki resimde belirtilmiştir.

Resim: Courdera - Mining Massive Datasets .

Shingling:

Doküman belirlenen sayı adedince shingle şeklinde bölünür. Buna k-sjingle denilir. Mantık n-gramlardaki gibidir.  Ki doküman arasındaki farkı incelerken dokümanlardaki farklı olan ve aynı olan shingle sayıları göz önünde bulundurulur.

Örn:

Doküman = kakules

k=2

2-shingles = {ka,ak,ku,ul,le,es}

Shingle'lar çok uzun olduklarında 4 byte yer kaplayacaklşekilde sıkıştırma yapılır. Sıkıştırılmış nesnelere "token" adı verilir. Dokümanlar arasındaki karşılaştırmalar token'lar ile yapılır.

Minhashing:

• Jaccard Similarity: 1. dokümanda  6 ikinci dokümanda 8 shingle var ise ve bunlardan 3 tanesi ortak ise jaccard smilarity 3/11 'dir. Bunun için doküman shingle larından oluşan bir matrix oluşturulur. Bu matrixde iki dokumanda da geçen (1,1) doküman sayısı/herhangi birinde 1 değeri olanların toplamı(1,0 yada 0,1) olarak hesaplanır.

Minhashig 'de hash fonksiyonu hesaplanırken Matrix üzerinde satırlar random olarak dağıtılır ve hangi sırayı hangi satırın doldurduğuna bakılarak bir hash matrix oluşturulur. (1. satırdan başlanarak doldurma işlemi yapılır.) Col/Col 'da kolonlardaki benzerlik Sig/Sig de signature matrixdeki benzerlik bulunur.

Resim: Courdera - Mining Massive Datasets .

Bu yöntemi büyük veri setlerinde uygulamak zordur. Bunun için hash metodları ile hashmatrix oluşturulur. Hash matrix oluşturulurken:

• Hash metodu değere göre hesaplanır.
• Ana matriste kolon için değeri 1 ise :
• Hash metodunun sonucu hash matrisdeki kolondaki değerden küçük ise, hash matrisindeki değer hash metodundaki ile güncellenir.
• Değil ise aynen bir sonraki adıma yansıtılır.

Resim: Courdera - Mining Massive Datasets .

Son çıkan matristeki değerlerin aynı olmasına göre kolonların benzerlikleri bulunur.

LSH- Locality Sensitive Hashing:

Tüm bu işlemlerden sonra büyük veriler ile çalışırken elimizde çok sayıda imza olşacaktır ve bunların karşılaştırılması da uzun zaman alıcaktır. Bu işlem süresini kısaltmak için imzalar üzerinde tekrar bir hash işlemler dizisi gerçekleştirilir ve çıkan sonuçlara göre kutularda duruplanır. Ortak bir kutuya bir kez girenler benzer olarak kabul edilir ve bu imzaya sahip belgelerde benzer olarak oylanır.