MapReduce - algorytm

Algorytm MapReduce zawiera dwa ważne zadania, a mianowicie Mapowanie i Zmniejszanie.

• Zadanie mapy jest realizowane za pomocą klasy Mapper
• Zadanie redukcji jest realizowane za pomocą klasy reduktora.

Klasa Mapper pobiera dane wejściowe, tokenizuje je, mapuje i sortuje. Dane wyjściowe klasy Mapper są używane jako dane wejściowe przez klasę Reducer, która z kolei wyszukuje pasujące pary i redukuje je.

MapReduce implementuje różne algorytmy matematyczne, aby podzielić zadanie na małe części i przypisać je do wielu systemów. Pod względem technicznym algorytm MapReduce pomaga w wysyłaniu zadań Map & Reduce do odpowiednich serwerów w klastrze.

Te algorytmy matematyczne mogą obejmować:

• Sorting
• Searching
• Indexing
• TF-IDF

Sortowanie

Sortowanie jest jednym z podstawowych algorytmów MapReduce do przetwarzania i analizy danych. MapReduce implementuje algorytm sortowania, aby automatycznie sortować wyjściowe pary klucz-wartość z programu odwzorowującego według ich kluczy.

• Metody sortowania są zaimplementowane w samej klasie mappera.

• W fazie Shuffle and Sort, po tokenizowaniu wartości w klasie mappera, plik Context class (klasa zdefiniowana przez użytkownika) zbiera pasujące klucze o wartościach jako kolekcję.

• Aby zebrać podobne pary klucz-wartość (klucze pośrednie), klasa Mapper korzysta z pomocy RawComparator klasy, aby posortować pary klucz-wartość.

• Zestaw pośrednich par klucz-wartość dla danego Reducera jest automatycznie sortowany przez Hadoop w celu utworzenia par klucz-wartość (K2, {V2, V2,…}), zanim zostaną przedstawione Reducerowi.

Badawczy

Wyszukiwanie odgrywa ważną rolę w algorytmie MapReduce. Pomaga w fazie sumatora (opcjonalnie) oraz w fazie reduktora. Spróbujmy zrozumieć, jak działa wyszukiwanie, na przykładzie.

Przykład

Poniższy przykład pokazuje, jak MapReduce wykorzystuje algorytm wyszukiwania, aby poznać szczegóły pracownika, który pobiera najwyższe wynagrodzenie w danym zbiorze danych pracowników.

• Załóżmy, że mamy dane pracowników w czterech różnych plikach - A, B, C i D. Załóżmy również, że we wszystkich czterech plikach znajdują się zduplikowane rekordy pracowników z powodu wielokrotnego importowania danych pracowników ze wszystkich tabel bazy danych. Zobacz poniższą ilustrację.

• The Map phaseprzetwarza każdy plik wejściowy i dostarcza dane pracowników w parach klucz-wartość (<k, v>: <imię i nazwisko, wynagrodzenie>). Zobacz poniższą ilustrację.

• The combiner phase(technika wyszukiwania) zaakceptuje dane wejściowe z fazy mapy jako parę klucz-wartość z nazwiskiem pracownika i jego wynagrodzeniem. Korzystając z techniki wyszukiwania, sumator sprawdzi wszystkie pensje pracowników, aby znaleźć najwyżej opłacanego pracownika w każdym pliku. Zobacz poniższy fragment.

<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;
}

Oczekiwany wynik jest następujący -

<satish, 26000> <gopal, 50000> <kiran, 45000> <manisha, 45000>

• Reducer phase- W każdym pliku znajdziesz najwyżej opłacanego pracownika. Aby uniknąć nadmiarowości, sprawdź wszystkie pary <k, v> i wyeliminuj zduplikowane wpisy, jeśli występują. Ten sam algorytm jest używany między czterema parami <k, v>, które pochodzą z czterech plików wejściowych. Ostateczny wynik powinien wyglądać następująco -

<gopal, 50000>

Indeksowanie

Zwykle indeksowanie służy do wskazywania określonych danych i ich adresu. Wykonuje indeksowanie wsadowe plików wejściowych dla określonego programu Mapper.

Technika indeksowania, która jest zwykle używana w MapReduce, jest znana jako inverted index.Wyszukiwarki takie jak Google i Bing używają techniki indeksowania odwróconego. Spróbujmy zrozumieć, jak działa indeksowanie, korzystając z prostego przykładu.

Przykład

Poniższy tekst stanowi dane wejściowe dla odwróconego indeksowania. Tutaj T [0], T [1] it [2] to nazwy plików, a ich zawartość jest w cudzysłowie.

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

Po zastosowaniu algorytmu indeksowania otrzymujemy następujący wynik -

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

Tutaj „a”: {2} oznacza, że ​​termin „a” pojawia się w pliku T [2]. Podobnie „jest”: {0, 1, 2} oznacza, że ​​termin „jest” pojawia się w plikach T [0], T [1] i T [2].

TF-IDF

TF-IDF to algorytm przetwarzania tekstu, który jest skrótem od Term Frequency - Inverse Document Frequency. Jest to jeden z powszechnych algorytmów analizy sieci. W tym przypadku termin „częstotliwość” odnosi się do tego, ile razy termin pojawia się w dokumencie.

Termin Częstotliwość (TF)

Mierzy częstotliwość występowania określonego terminu w dokumencie. Oblicza się, ile razy słowo pojawia się w dokumencie, podzielone przez całkowitą liczbę słów w tym dokumencie.

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

Odwrotna częstotliwość dokumentu (IDF)

Mierzy znaczenie terminu. Oblicza się go przez liczbę dokumentów w tekstowej bazie danych podzieloną przez liczbę dokumentów, w których występuje określony termin.

Podczas obliczania TF wszystkie terminy są uważane za równie ważne. Oznacza to, że TF zlicza częstotliwość terminów dla normalnych słów, takich jak „jest”, „a”, „co” itp. Dlatego musimy znać częste terminy podczas skalowania w górę rzadkich, obliczając następujące -

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

Algorytm jest wyjaśniony poniżej za pomocą małego przykładu.

Przykład

Rozważmy dokument zawierający 1000 słów, w tym słowo hivepojawia się 50 razy. TF dlahive jest wtedy (50/1000) = 0,05.

Teraz załóżmy, że mamy 10 milionów dokumentów i słowo hivepojawia się w 1000 z nich. Następnie IDF jest obliczany jako log (10 000 000/1 000) = 4.

Iloczynem tych wielkości jest waga TF-IDF - 0,05 × 4 = 0,20.