descargar - Mapper y Reducer for K significan algoritmo en Hadoop en Java

mapreduce definition

Question

Estoy tratando de implementar K means en hadoop-1.0.1 en lenguaje java . Estoy frustrado ahora. Aunque obtuve un enlace github de la implementación completa de k means pero como novato en Hadoop , quiero aprenderlo sin copiar el código de otros. Tengo conocimiento básico del map y reduce función disponible en hadoop . ¿Alguien puede darme la idea de implementar k means mapper y clase reducer ? ¿Requiere iteración?

Answer 1

Ok, le doy una oportunidad para decirte lo que pensé al implementar k-means en MapReduce. Esta implementación difiere de la de Mahout, principalmente porque muestra cómo el algoritmo podría funcionar en una configuración distribuida (y no para el uso de producción real). También supongo que realmente sabes cómo funciona k-means.

Habiendo dicho eso, tenemos que dividir todo el algoritmo en tres etapas principales:

1. Nivel de trabajo
2. Nivel de mapa
3. Reducir el nivel

El nivel de trabajo

El nivel de trabajo es bastante simple, es escribir la entrada (Clave = la clase llamada ClusterCenter y Valor = la clase llamada VectorWritable ), manejar la iteración con el trabajo de Hadoop y leer el resultado de todo el trabajo.

VectorWritable es una implementación serializable de un vector, en este caso de mi propia biblioteca matemática, pero en realidad nada más que una simple matriz doble.

ClusterCenter es principalmente VectorWritable , pero con funciones de conveniencia que un centro generalmente necesita (promediando, por ejemplo).

En k-means, tienes algunos conjuntos de semillas de k-vectores que son tus centros iniciales y algunos vectores de entrada que quieres agrupar. Eso es exactamente lo mismo en MapReduce, pero los estoy escribiendo en dos archivos diferentes. El primer archivo solo contiene los vectores y algún centro de clave ficticia y el otro archivo contiene los centros iniciales reales (es decir, cen.seq ).

Después de todo lo que se escribe en el disco, puede comenzar su primer trabajo. Por supuesto, esto primero lanzará un Mapper que es el siguiente tema.

El nivel del mapa

En MapReduce siempre es inteligente saber qué entra y qué sale (en términos de objetos). Por lo tanto, desde el nivel de trabajo, sabemos que tenemos ClusterCenter y VectorWritable como entrada, mientras que ClusterCenter es actualmente simplemente un muñeco. Por supuesto, queremos tener lo mismo que salida, porque la etapa de mapa es el famoso paso de asignación de k-medias normales.

Está leyendo el archivo de centros reales que creó en el nivel de trabajo en la memoria para comparar los vectores de entrada y los centros. Por lo tanto, tiene esta métrica de distancia definida, en el asignador está codificada en la distancia de ManhattanDistance . Para ser un poco más específico, obtienes una parte de tu entrada en el escenario del mapa y luego puedes iterar sobre cada "par de valores clave" de entrada (es un par o tupla que consta de clave y valor) en comparación con cada uno de los centros . Aquí está rastreando qué centro es el más cercano y luego lo asigna al centro escribiendo el objeto ClusterCenter más ClusterCenter junto con el vector de entrada mismo en el disco.

Su salida es entonces: n-vectores junto con su centro asignado (como la clave). Hadoop ahora está clasificando y agrupando por tu clave, por lo que obtienes cada vector asignado para un solo centro en la tarea de reducción.

El nivel de reducción

Como se ClusterCenter anteriormente, tendrá un ClusterCenter y su VectorWritable asignado en la etapa de reducción. Este es el paso de actualización habitual que tiene en k-means normal. Entonces simplemente itera sobre todos los vectores, los suma y los promedia.

Ahora tiene una nueva "media" que puede comparar con la media que le asignaron antes. Aquí puede medir la diferencia entre los dos centros, lo que nos dice cuánto se movió el centro. Idealmente, no se habría movido ni habría converged .

El contador en Hadoop se utiliza para rastrear esta convergencia, el nombre es un poco engañoso porque en realidad rastrea cuántos centros no han convergido a un punto final, pero espero que puedas vivir con él.

Básicamente, ahora está escribiendo el nuevo centro y todos los vectores en el disco para la próxima iteración. Además, en el paso de limpieza, está escribiendo todos los nuevos centros reunidos en la ruta utilizada en el paso del mapa, por lo que la nueva iteración tiene los nuevos vectores.

Ahora, de nuevo en la etapa de trabajo, el trabajo de MapReduce debe hacerse ahora. Ahora estamos inspeccionando el contador de ese trabajo para obtener la cantidad de centros que aún no han convergido. Este contador se usa en el ciclo while para determinar si el algoritmo completo puede finalizar o no. De lo contrario, regrese nuevamente al párrafo del Nivel del mapa , pero use la salida del trabajo anterior como entrada.

En realidad, este fue todo el VooDoo.

Por razones obvias, esto no debería usarse en producción, porque su rendimiento es horrible. Mejor utiliza la versión más afinada de Mahout. Pero para fines educativos este algoritmo está bien;)

Si tiene más preguntas, no dude en escribirme un correo o un comentario.