MapReduce - Algoritmo
El algoritmo MapReduce contiene dos tareas importantes, a saber, Map y Reduce.
- La tarea del mapa se realiza mediante Mapper Class
- La tarea de reducción se realiza mediante Reducer Class.
La clase Mapper toma la entrada, la tokeniza, la mapea y la ordena. La salida de la clase Mapper es utilizada como entrada por la clase Reducer, que a su vez busca pares coincidentes y los reduce.
MapReduce implementa varios algoritmos matemáticos para dividir una tarea en partes pequeñas y asignarlas a múltiples sistemas. En términos técnicos, el algoritmo MapReduce ayuda a enviar las tareas de Map & Reduce a los servidores apropiados en un clúster.
Estos algoritmos matemáticos pueden incluir lo siguiente:
- Sorting
- Searching
- Indexing
- TF-IDF
Clasificación
La clasificación es uno de los algoritmos básicos de MapReduce para procesar y analizar datos. MapReduce implementa un algoritmo de clasificación para clasificar automáticamente los pares clave-valor de salida del asignador por sus claves.
Los métodos de ordenación se implementan en la propia clase del asignador.
En la fase Shuffle and Sort, después de tokenizar los valores en la clase del asignador, el Context class (clase definida por el usuario) recopila las claves de valor coincidente como una colección.
Para recopilar pares clave-valor similares (claves intermedias), la clase Mapper toma la ayuda de RawComparator class para ordenar los pares clave-valor.
Hadoop clasifica automáticamente el conjunto de pares clave-valor intermedios para un reductor determinado para formar pares clave-valor (K2, {V2, V2,…}) antes de que se presenten al reductor.
buscando
La búsqueda juega un papel importante en el algoritmo MapReduce. Ayuda en la fase combinadora (opcional) y en la fase reductora. Intentemos comprender cómo funciona la búsqueda con la ayuda de un ejemplo.
Ejemplo
El siguiente ejemplo muestra cómo MapReduce emplea el algoritmo de búsqueda para averiguar los detalles del empleado que recibe el salario más alto en un conjunto de datos de empleado determinado.
Supongamos que tenemos datos de empleados en cuatro archivos diferentes: A, B, C y D. Supongamos también que hay registros de empleados duplicados en los cuatro archivos debido a la importación repetida de datos de empleados de todas las tablas de la base de datos. Vea la siguiente ilustración.
The Map phaseprocesa cada archivo de entrada y proporciona los datos de los empleados en pares clave-valor (<k, v>: <nombre de empresa, salario>). Vea la siguiente ilustración.
The combiner phase(técnica de búsqueda) aceptará la entrada de la fase Mapa como un par clave-valor con el nombre y el salario del empleado. Usando la técnica de búsqueda, el combinador verificará todo el salario del empleado para encontrar el empleado con el salario más alto en cada archivo. Vea el siguiente fragmento.
<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;
}El resultado esperado es el siguiente:
|
Reducer phase- Forma cada archivo, encontrarás el empleado con el salario más alto. Para evitar la redundancia, verifique todos los pares <k, v> y elimine las entradas duplicadas, si las hubiera. El mismo algoritmo se usa entre los cuatro pares <k, v>, que provienen de cuatro archivos de entrada. El resultado final debería ser el siguiente:
<gopal, 50000>Indexación
Normalmente, la indexación se utiliza para señalar un dato en particular y su dirección. Realiza una indexación por lotes en los archivos de entrada para un asignador en particular.
La técnica de indexación que se utiliza normalmente en MapReduce se conoce como inverted index.Los motores de búsqueda como Google y Bing utilizan la técnica de indexación invertida. Intentemos comprender cómo funciona la indexación con la ayuda de un ejemplo sencillo.
Ejemplo
El siguiente texto es la entrada para la indexación invertida. Aquí T [0], T [1] y t [2] son los nombres de los archivos y su contenido está entre comillas dobles.
T[0] = "it is what it is"
T[1] = "what is it"
T[2] = "it is a banana"Después de aplicar el algoritmo de indexación, obtenemos el siguiente resultado:
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}Aquí "a": {2} implica que el término "a" aparece en el archivo T [2]. De manera similar, "es": {0, 1, 2} implica que el término "es" aparece en los archivos T [0], T [1] y T [2].
TF-IDF
TF-IDF es un algoritmo de procesamiento de texto que es la abreviatura de Term Frequency - Inverse Document Frequency. Es uno de los algoritmos de análisis web habituales. Aquí, el término "frecuencia" se refiere al número de veces que aparece un término en un documento.
Frecuencia de término (TF)
Mide la frecuencia con la que aparece un término en particular en un documento. Se calcula dividiendo el número de veces que aparece una palabra en un documento entre el número total de palabras de ese documento.
TF(the) = (Number of times term the ‘the’ appears in a document) / (Total number of terms in the document)Frecuencia de documento inversa (IDF)
Mide la importancia de un término. Se calcula dividiendo el número de documentos en la base de datos de texto entre el número de documentos donde aparece un término específico.
Al calcular TF, todos los términos se consideran igualmente importantes. Eso significa que TF cuenta la frecuencia del término para palabras normales como "es", "a", "qué", etc. Por lo tanto, necesitamos conocer los términos frecuentes mientras ampliamos los raros, calculando lo siguiente:
IDF(the) = log_e(Total number of documents / Number of documents with term ‘the’ in it).El algoritmo se explica a continuación con la ayuda de un pequeño ejemplo.
Ejemplo
Considere un documento que contiene 1000 palabras, donde la palabra hiveaparece 50 veces. El TF parahive es entonces (50/1000) = 0,05.
Ahora, suponga que tenemos 10 millones de documentos y la palabra hiveaparece en 1000 de estos. Luego, la IDF se calcula como log (10,000,000 / 1,000) = 4.
El peso de TF-IDF es el producto de estas cantidades: 0,05 × 4 = 0,20.