MapReduce - алгоритм

Алгоритм MapReduce содержит две важные задачи, а именно Map и Reduce.

Задача карты выполняется с помощью класса Mapper.
Задача сокращения выполняется с помощью класса Reducer.

Класс Mapper принимает ввод, токенизирует его, сопоставляет и сортирует. Выходные данные класса Mapper используются в качестве входных данных для класса Reducer, который, в свою очередь, ищет подходящие пары и сокращает их.

MapReduce реализует различные математические алгоритмы для разделения задачи на небольшие части и назначения их нескольким системам. С технической точки зрения алгоритм MapReduce помогает отправлять задачи Map & Reduce на соответствующие серверы в кластере.

Эти математические алгоритмы могут включать в себя следующее:

Sorting
Searching
Indexing
TF-IDF

Сортировка

Сортировка - один из основных алгоритмов MapReduce для обработки и анализа данных. MapReduce реализует алгоритм сортировки для автоматической сортировки выходных пар ключ-значение из сопоставителя по их ключам.

Методы сортировки реализованы в самом классе mapper.
На этапе перемешивания и сортировки после токенизации значений в классе сопоставления Context class (определяемый пользователем класс) собирает соответствующие ключи в виде коллекции.
Чтобы собрать похожие пары ключ-значение (промежуточные ключи), класс Mapper использует RawComparator класс для сортировки пар ключ-значение.
Набор промежуточных пар "ключ-значение" для данного редуктора автоматически сортируется Hadoop для формирования ключей и значений (K2, {V2, V2,…}), прежде чем они будут представлены редуктору.

Поиск

Поиск играет важную роль в алгоритме MapReduce. Это помогает на этапе объединения (опция) и на этапе восстановления. Попробуем разобраться, как работает Searching, на примере.

пример

В следующем примере показано, как MapReduce использует алгоритм поиска, чтобы узнать подробности о сотруднике, получающем самую высокую зарплату в данном наборе данных о сотрудниках.

Допустим, у нас есть данные о сотрудниках в четырех разных файлах - A, B, C и D. Предположим также, что во всех четырех файлах есть повторяющиеся записи о сотрудниках из-за многократного импорта данных о сотрудниках из всех таблиц базы данных. См. Следующую иллюстрацию.

The Map phaseобрабатывает каждый входной файл и предоставляет данные о сотрудниках в виде пар ключ-значение (<k, v>: <emp name, salary>). См. Следующую иллюстрацию.

The combiner phase(метод поиска) примет входные данные с этапа сопоставления в виде пары ключ-значение с именем сотрудника и зарплатой. Используя технику поиска, объединитель проверит всю заработную плату сотрудников, чтобы найти самого высокооплачиваемого сотрудника в каждом файле. См. Следующий фрагмент.

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

Ожидаемый результат выглядит следующим образом -

<сатиш, 26000>

<гопал, 50000>

<киран, 45000>

<маниша, 45000>

Reducer phase- Сформируйте каждый файл, вы найдете самого высокооплачиваемого сотрудника. Чтобы избежать избыточности, проверьте все пары <k, v> и удалите повторяющиеся записи, если таковые имеются. Тот же алгоритм используется между четырьмя парами <k, v>, которые поступают из четырех входных файлов. Окончательный результат должен быть следующим -

<gopal, 50000>

Индексирование

Обычно индексация используется для указания на определенные данные и их адрес. Он выполняет пакетную индексацию входных файлов для конкретного Mapper.

Техника индексации, которая обычно используется в MapReduce, известна как inverted index.Поисковые системы, такие как Google и Bing, используют метод перевернутой индексации. Попробуем разобраться, как работает индексация, на простом примере.

пример

Следующий текст является вводом для инвертированной индексации. Здесь T [0], T [1] и t [2] - имена файлов, а их содержимое заключено в двойные кавычки.

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

После применения алгоритма индексирования мы получаем следующий результат -

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

Здесь "a": {2} означает, что термин "a" появляется в файле T [2]. Аналогично, «is»: {0, 1, 2} подразумевает, что термин «is» встречается в файлах T [0], T [1] и T [2].

TF-IDF

TF-IDF - это алгоритм обработки текста, который является сокращением от Term Frequency - Inverse Document Frequency. Это один из распространенных алгоритмов веб-анализа. Здесь термин «частота» относится к тому, сколько раз термин встречается в документе.

Частота сроков (TF)

Он измеряет, как часто в документе встречается конкретный термин. Он рассчитывается как количество раз, когда слово появляется в документе, деленное на общее количество слов в этом документе.

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

Обратная частота документов (IDF)

Он измеряет важность термина. Он рассчитывается путем деления количества документов в текстовой базе данных на количество документов, в которых встречается конкретный термин.

При вычислении TF все термины считаются одинаково важными. Это означает, что TF считает частоту термина для обычных слов, таких как «есть», «а», «что» и т. Д. Таким образом, нам нужно знать часто встречающиеся термины, увеличивая масштаб редких, вычисляя следующее:

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

Алгоритм поясняется ниже на небольшом примере.

пример

Рассмотрим документ, содержащий 1000 слов, в которых слово hiveпоявляется 50 раз. TF дляhive тогда (50/1000) = 0,05.

Теперь предположим, что у нас есть 10 миллионов документов и слово hiveпоявляется в 1000 из них. Тогда IDF рассчитывается как log (10,000,000 / 1,000) = 4.

Вес TF-IDF является произведением этих величин - 0,05 × 4 = 0,20.