MapReduce - Algoritma

MapReduce algoritması, Map ve Reduce olmak üzere iki önemli görev içerir.

Harita görevi Mapper Class aracılığıyla yapılır
İndirgeme görevi Redüktör Sınıfı ile yapılır.

Mapper sınıfı girdiyi alır, jetonlaştırır, eşler ve sıralar. Mapper sınıfının çıktısı, karşılık gelen çiftleri arayan ve onları azaltan Reducer sınıfı tarafından girdi olarak kullanılır.

MapReduce, bir görevi küçük parçalara ayırmak ve bunları birden çok sisteme atamak için çeşitli matematiksel algoritmalar uygular. Teknik terimlerle, MapReduce algoritması, Harita ve Azaltma görevlerinin bir kümedeki uygun sunuculara gönderilmesine yardımcı olur.

Bu matematiksel algoritmalar şunları içerebilir:

Sorting
Searching
Indexing
TF-IDF

Sıralama

Sıralama, verileri işlemek ve analiz etmek için temel MapReduce algoritmalarından biridir. MapReduce, eşleştiriciden çıktı anahtar-değer çiftlerini anahtarlarına göre otomatik olarak sıralamak için sıralama algoritması uygular.

Sıralama yöntemleri, mapper sınıfının kendisinde uygulanır.
Shuffle and Sort aşamasında, mapper sınıfındaki değerleri tokenize ettikten sonra, Context class (kullanıcı tanımlı sınıf), eşleşen değerli anahtarları bir koleksiyon olarak toplar.
Benzer anahtar-değer çiftlerini (ara anahtarlar) toplamak için Mapper sınıfı şunlardan yardım alır: RawComparator anahtar / değer çiftlerini sıralamak için sınıf.
Belirli bir İndirgeyici için ara anahtar / değer çifti kümesi, Düşürücüye sunulmadan önce anahtar / değer çiftleri (K2, {V2, V2,…}) oluşturmak için otomatik olarak Hadoop tarafından sıralanır.

Aranıyor

Arama, MapReduce algoritmasında önemli bir rol oynar. Birleştirici aşamasında (isteğe bağlı) ve Redüktör aşamasında yardımcı olur. Bir örnek yardımıyla Aramanın nasıl çalıştığını anlamaya çalışalım.

Misal

Aşağıdaki örnek, MapReduce'un belirli bir çalışan veri kümesinde en yüksek maaşı alan çalışanın ayrıntılarını bulmak için Arama algoritmasını nasıl kullandığını gösterir.

Çalışan verilerinin A, B, C ve D olmak üzere dört farklı dosyada olduğunu varsayalım. Çalışan verilerini tüm veritabanı tablolarından tekrar tekrar içe aktardığımız için dört dosyanın hepsinde de yinelenen çalışan kayıtları olduğunu varsayalım. Aşağıdaki resme bakın.

The Map phaseher girdi dosyasını işler ve çalışan verilerini anahtar-değer çiftleri halinde sağlar (<k, v>: <emp adı, maaş>). Aşağıdaki resme bakın.

The combiner phase(arama tekniği), Harita aşamasından gelen girdiyi, çalışan adı ve maaşıyla birlikte bir anahtar-değer çifti olarak kabul edecektir. Arama tekniğini kullanarak birleştirici, her dosyadaki en yüksek maaşlı çalışanı bulmak için tüm çalışan maaşını kontrol edecektir. Aşağıdaki parçaya bakın.

<k: employee name, v: salary>
Max= the salary of an first employee. Treated as max salary

if(v(second employee).salary > Max){
   Max = v(salary);
}

else{
   Continue checking;
}

Beklenen sonuç aşağıdaki gibidir -

<satish, 26000>

<gopal, 50000>

<kiran, 45000>

<manisha, 45000>

Reducer phase- Her dosyayı oluşturun, en yüksek maaşlı çalışanı bulacaksınız. Fazlalıktan kaçınmak için, tüm <k, v> çiftlerini kontrol edin ve varsa yinelenen girişleri eleyin. Aynı algoritma, dört girdi dosyasından gelen dört <k, v> çifti arasında kullanılır. Nihai çıktı aşağıdaki gibi olmalıdır -

<gopal, 50000>

Endeksleme

Normalde indeksleme, belirli bir veriyi ve adresini göstermek için kullanılır. Belirli bir Eşleştirici için girdi dosyaları üzerinde toplu indeksleme gerçekleştirir.

Normalde MapReduce'da kullanılan indeksleme tekniği olarak bilinir inverted index.Google ve Bing gibi arama motorları ters indeksleme tekniğini kullanır. Basit bir örnek yardımıyla İndekslemenin nasıl çalıştığını anlamaya çalışalım.

Misal

Aşağıdaki metin, tersine çevrilmiş indeksleme için girdidir. Burada T [0], T [1] ve t [2] dosya adlarıdır ve içerikleri çift tırnak içindedir.

T[0] = "it is what it is"
T[1] = "what is it"
T[2] = "it is a banana"

İndeksleme algoritmasını uyguladıktan sonra aşağıdaki çıktıyı alıyoruz -

"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}

Burada "a": {2} "a" teriminin T [2] dosyasında göründüğünü belirtir. Benzer şekilde, "eşittir": {0, 1, 2} "eşittir" teriminin T [0], T [1] ve T [2] dosyalarında göründüğünü belirtir.

TF-IDF

TF-IDF, Terim Frekansı - Ters Belge Frekansı'nın kısaltması olan bir metin işleme algoritmasıdır. Yaygın web analiz algoritmalarından biridir. Burada, 'sıklık' terimi, bir terimin bir belgede kaç kez göründüğünü ifade eder.

Dönem Frekansı (TF)

Bir belgede belirli bir terimin ne sıklıkla geçtiğini ölçer. Bir kelimenin bir belgedeki görünme sayısının o belgedeki toplam kelime sayısına bölünmesiyle hesaplanır.

TF(the) = (Number of times term the ‘the’ appears in a document) / (Total number of terms in the document)

Ters Belge Frekansı (IDF)

Bir terimin önemini ölçer. Metin veritabanındaki belge sayısının belirli bir terimin göründüğü belge sayısına bölünmesiyle hesaplanır.

TF'yi hesaplarken, tüm terimler eşit derecede önemli kabul edilir. Bu, TF'nin "eşittir", "a", "ne" gibi normal kelimeler için terim sıklığını saydığı anlamına gelir. Bu nedenle, aşağıdakileri hesaplayarak nadir terimleri ölçeklendirirken sık kullanılan terimleri bilmemiz gerekir -

IDF(the) = log_e(Total number of documents / Number of documents with term ‘the’ in it).

Algoritma aşağıda küçük bir örnek yardımıyla açıklanmıştır.

Misal

1000 kelimelik bir belge düşünün, burada kelime hive50 kez görünür. TF içinhive (50/1000) = 0,05 olur.

Şimdi, 10 milyon belgemiz olduğunu ve hivebunların 1000'inde görünür. Daha sonra IDF, log (10.000.000 / 1.000) = 4 olarak hesaplanır.

TF-IDF ağırlığı, bu miktarların ürünüdür - 0.05 × 4 = 0.20.