MapReduce - Algoritmo

O algoritmo MapReduce contém duas tarefas importantes, ou seja, Mapear e Reduzir.

  • A tarefa do mapa é feita por meio da classe Mapper
  • A tarefa de redução é feita por meio da Classe Redutor.

A classe Mapper pega a entrada, cria tokens, mapeia e classifica. A saída da classe Mapper é usada como entrada pela classe Reducer, que por sua vez pesquisa pares correspondentes e os reduz.

MapReduce implementa vários algoritmos matemáticos para dividir uma tarefa em pequenas partes e atribuí-las a vários sistemas. Em termos técnicos, o algoritmo MapReduce ajuda a enviar as tarefas Map & Reduce para os servidores apropriados em um cluster.

Esses algoritmos matemáticos podem incluir o seguinte -

  • Sorting
  • Searching
  • Indexing
  • TF-IDF

Ordenação

A classificação é um dos algoritmos MapReduce básicos para processar e analisar dados. MapReduce implementa algoritmo de classificação para classificar automaticamente os pares de valores-chave de saída do mapeador por suas chaves.

  • Os métodos de classificação são implementados na própria classe do mapeador.

  • Na fase de ordem aleatória e classificação, depois de tokenizar os valores na classe do mapeador, o Context classe (classe definida pelo usuário) coleta as chaves de valor correspondentes como uma coleção.

  • Para coletar pares de valores-chave semelhantes (chaves intermediárias), a classe Mapper tem a ajuda de RawComparator classe para classificar os pares de valor-chave.

  • O conjunto de pares de valores-chave intermediários para um determinado Redutor é classificado automaticamente pelo Hadoop para formar valores-chave (K2, {V2, V2, ...}) antes de serem apresentados ao Redutor.

Procurando

A pesquisa desempenha um papel importante no algoritmo MapReduce. Auxilia na fase combinadora (opcional) e na fase Redutor. Vamos tentar entender como Searching funciona com a ajuda de um exemplo.

Exemplo

O exemplo a seguir mostra como MapReduce emprega o algoritmo de pesquisa para descobrir os detalhes do funcionário que recebe o maior salário em um determinado conjunto de dados de funcionários.

  • Vamos supor que temos dados de funcionários em quatro arquivos diferentes - A, B, C e D. Suponhamos também que haja registros de funcionários duplicados em todos os quatro arquivos devido à importação repetida de dados de funcionários de todas as tabelas do banco de dados. Veja a ilustração a seguir.

  • The Map phaseprocessa cada arquivo de entrada e fornece os dados do funcionário em pares de valores-chave (<k, v>: <nome emp, salário>). Veja a ilustração a seguir.

  • The combiner phase(técnica de pesquisa) aceitará a entrada da fase Mapa como um par de valores-chave com o nome do funcionário e o salário. Usando a técnica de pesquisa, o combinador irá verificar todo o salário do funcionário para encontrar o funcionário com maior salário em cada arquivo. Veja o seguinte trecho.

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

O resultado esperado é o seguinte -

<satish, 26.000>

<gopal, 50000>

<kiran, 45000>

<manisha, 45000>

  • Reducer phase- De cada arquivo, você encontrará o funcionário com maior salário. Para evitar redundância, verifique todos os pares <k, v> e elimine entradas duplicadas, se houver. O mesmo algoritmo é usado entre os quatro pares <k, v>, que vêm de quatro arquivos de entrada. O resultado final deve ser o seguinte -

<gopal, 50000>

Indexando

Normalmente, a indexação é usada para apontar para um dado específico e seu endereço. Ele executa a indexação de lote nos arquivos de entrada para um mapeador específico.

A técnica de indexação normalmente usada no MapReduce é conhecida como inverted index.Motores de busca como Google e Bing usam técnicas de indexação invertida. Vamos tentar entender como a indexação funciona com a ajuda de um exemplo simples.

Exemplo

O texto a seguir é a entrada para a indexação invertida. Aqui, T [0], T [1] e t [2] são os nomes dos arquivos e seu conteúdo está entre aspas duplas.

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

Depois de aplicar o algoritmo de indexação, obtemos a seguinte saída -

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

Aqui, "a": {2} implica que o termo "a" aparece no arquivo T [2]. Da mesma forma, "é": {0, 1, 2} implica que o termo "é" aparece nos arquivos T [0], T [1] e T [2].

TF-IDF

TF-IDF é um algoritmo de processamento de texto abreviação de Term Frequency - Inverse Document Frequency. É um dos algoritmos comuns de análise da web. Aqui, o termo 'frequência' se refere ao número de vezes que um termo aparece em um documento.

Frequência de termo (TF)

Ele mede a frequência com que um determinado termo ocorre em um documento. É calculado pelo número de vezes que uma palavra aparece em um documento dividido pelo número total de palavras nesse documento.

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

Frequência inversa do documento (IDF)

Ele mede a importância de um termo. É calculado pelo número de documentos na base de dados de texto dividido pelo número de documentos onde um termo específico aparece.

Ao calcular TF, todos os termos são considerados igualmente importantes. Isso significa que TF conta a frequência do termo para palavras normais como "é", "a", "o que", etc. Portanto, precisamos saber os termos frequentes enquanto aumentamos os raros, calculando o seguinte -

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

O algoritmo é explicado a seguir com a ajuda de um pequeno exemplo.

Exemplo

Considere um documento contendo 1000 palavras, em que a palavra hiveaparece 50 vezes. O TF parahive é então (50/1000) = 0,05.

Agora, suponha que temos 10 milhões de documentos e a palavra hiveaparece em 1000 deles. Então, o IDF é calculado como log (10.000.000 / 1.000) = 4.

O peso TF-IDF é o produto dessas quantidades - 0,05 × 4 = 0,20.