Regresión Lineal Simple MapReduce

Yo creo inmensamente que el Big Data aunque en mi país México es muy joven esta tecnología aún, en grandes potencias esta tecnología se utiliza para encontrar patrones en grandes volúmenes de información, hacer algoritmos predictivos, de clasificación, clusterización y más, creo inmensamente que esta tecnología será el futuro, junto con el Internet de las cosas y el cloud, hoy en día ya no es ningún impedimento hacer perdiciones de inmensos volúmenes de información y si saben programar bajo este framework, las posibilidades son inmensas, ya que puedes tratar cualquier tipo de información existente en el mundo lógico y darle algún sentido.

Empezaremos estudiando que es una regresión lineal y ajustar la mejor recta de acuerdo a nuestros datos el ejemplo más sencillo de predicción, pero también el más representativo para explicar toda la teoría del post anterior, una regresión lineal no representa rectas, más bien tiene el nombre por que los parámetros que se estiman son lineales, con este método podemos hacer estimaciones para datos que representen cualquier tipo de curva de forma polinomial.

La regresión lineal tiene años existiendo y fue gracias a Gauss que tenemos una estimación de este tipo, se puede realizar un ajuste lineal con Álgebra Lineal y no trabajando con una muestra lo cual lo hace más exacto, pero un poco más complejo de procesar, para este ejemplo trabajaremos con con una regresión lineal con dos parámetros a estimar de una forma probabilista.

El código para este ejemplo se podrá encontrar en el siguiente, con el cuál trabajaremos a lo largo de este post link:  https://github.com/NeoChoosenOne/Linearregression

Este problema surge al querer encontrar una función f  que se ajuste a un conjunto de puntos, a continuación plantearé el problema.

Para este post tomaremos el caso en que m=2 por lo tanto a lo que queremos llegar luciría de la siguiente forma.

Una vez planteado el problema y sabiendo a que queremos llegar, procederemos a resolver el problema.

Nosotros nos enfocaremos en el caso 1, en el caso en el que la función que queremos obtener tiene la forma de una recta, las funciones anteriores, son funciones lineales ya que los parámetros que desean calcular son lineales.

La ecuación del punto uno nos sirve para ajustar una recta a nuestros puntos que deseamos analizar.

Entonces empezamos suponiendo que tenemos una linea que ajusta nuestros puntos como la ecuación anterior, la ecuación anterior es de forma determinista, pero en realidad en el modelo anterior existen errores, ya que la ecuación anterior no ajustará todos los puntos de nuestro conjunto, a menos que en realidad este conjunto de puntos sea un conjunto que lleve una relación de crecimiento en forma de recta la función será exacta en todos los valores, de lo contrario debemos contemplar el siguiente modelo.

En el modelo anterior estamos asumiendo y aceptando que existe un error en nuestra función para cada punto de nuestro conjunto, el cuál convierte el modelo determinista a uno probabilista, este error tiene la siguiente propiedad.

Al final nuestra variable aleatoria de error, es una variable aleatoria que se distribuye normal y con media 0, esta es la famosa función de error de Gauss, como podemos ver, nuestro modelo esta contemplando el error en cada punto, entonces al final tendremos un error acumulado total donde es la suma de cada uno de los errores individuales por punto.

Si calculamos la esperanza de nuestro modelo anterior el que contempla el error tendremos una ecuación como la siguiente, donde la última ecuación son estimadores de los parámetros beta.

Podemos replantear este problema como la minimización del error total de nuestro modelo, el cuál se calcula como la diferencia entre el punto real y el punto estimado, el cual es el error entre ambos puntos el cual puede ser positivo o negativo, para trabajar con puros datos positivos y sin perdida de generalidad cada error se elevara al cuadrado y la suma de todos los errores al cuadrado, es el error total.

Nuestro objetivo es el de minimizar la función anterior o como se muestra en la siguiente imagen.

Entonces ahora nuestro objetivo es resolver el problema anterior, y para resolverlo como sabemos de cálculo, basta con calcular sus puntos críticos, con respecto a los dos parámetros desconocidos, pero no hace falta calcular si es un máximo o mínimo, ya que es una función estrictamente creciente y positiva, pero por que hago esta afirmación, muy simple, la ecuación anterior puede reescribirse como mostraré a continuación.

 

como podemos notar es una función cuadrática que tiene la siguiente forma.

Así que como podemos notar, no es necesario preocuparnos por si es un máximo o mínimo, ya que sabemos que tiene un punto critico y ese punto crítico es necesariamente un mínimo de nuestros datos. 

Una vez sabiendo que solo en realidad encontraremos el mínimo procederemos a calcularlo, el primer paso será calcular las derivadas parciales por parte de cada parámetro.

Entonces el problema se convierte en un sistema de ecuaciones de tamaño 2x2.

Cómo podemos ver en la imagen anterior tenemos el sistema de ecuaciones, no calcularé las derivadas paso por paso, ya que eso es algo que no debería ser muy complicado para el lector, pasando directamente al sistema de ecuaciones de forma más clara de la siguiente imagen:

Después procedemos a resolver el sistema de ecuaciones cosa que tampoco haré por que eso es algo que el lector puede hacer fácilmente,  terminando de resolver la ecuación llegamos al siguiente resultado.

Bueno estas son las ecuaciones para encontrar el valor de las estimaciones de nuestro modelo lineal, ahora procederé a mostrar por que es una paralelización trivial, para recordar que quiero decir con lo anterior bastará con recordar la definición del blog anterior.

Paralelización Trivial

Yo aseguré que se necesitaba lo anterior para garantizar una paralelización trivial, ahora provemos que para la regresión lineal los puntos anteriores se cumplen, tomando las siguientes ecuaciones para realizar nuestro calculo de la regresión lineal con el MapReduce.

Con las fórmulas anteriores podemos cubrir los 5 puntos de la definición 1.4, empezaremos definiendo a f de la siguiente manera.

Entonces cumple el ejemplo uno, por que con la definición anterior de la función en forma gráfica nos queda de la siguiente manera, supongamos que tenemos un archivo como el siguiente, que se divide en 3 bloques, entonces tendremos 3 maps que deben ser ejecutados, supongamos que tenemos 2 nodos para procesarlos, entonces ejecutaran 2 al mismo tiempo y el 3 será cuando uno de los dos se desocupe.

Ahora tomando los bloques y aplicándole la función anterior a cada uno de los bloques anteriores tenemos el siguiente resultado.

La función se ve implementada por el código de nuestro mapper y reducer, como se puede observar en el código implementamos un combiner que es el mismo código del reducer el cuál la información de la imagen anterior, lo dejara de la siguiente forma.

Esta sería la parte de sort & suffle quedando los datos como la parte anterior, y después ejecutará el código del reducer para cada nodo que tiene asignado un map, teniendo por salida después del paso del combinar la siguiente imagen.

Una vez que se ha realizado el mismo proceso en cada bloquesito en los nodos dispobibles de nuestro clúster, procedemos a la parte del reducer donde prácticamente el reducer tendrá solo una entrada como la siguiente.

 Que es la agrupación en un solo key de los 3 resultados anteriores, este elemento que pertenece al conjunto S es el único elemento que le llega al reducer, por lo tanto solo tendrá que sumar todos los elementos pertenecientes a esa llave para obtener las sumas totales de sumx, sumy, sumxy, sumxx y n con los que ya podemos calcular los parámetros betas. 

Como podemos ver los pasos anteriores se realizan en las 2 máquinas paralelamente y siempre un bloquesito lo mapeará a un elemento del conjunto S, también no importa en que orden se haga, ya que siempre dará el mismo resultado de acuerdo a nuestra función que definimos al inicio de este apartado cumpliendo la propiedad 3.

Para probar la propiedad dos basta con imaginar el caso en que en el conjunto B solo exista un elemento al cual le pertenecerá solo un elemento del conjunto S el cual tendrá la suma total smux, sumy, sumxy, sumxx, n, pero como pudimos ver en este ejemplo ese resultado se logra con los bloquesitos de tal manera que la propiedad 2 se cumple y más aún la 5, ya que no importa cuantos bloquesitos estén contentenidos en el conjunto B como todos son disjuntos el resultado siempre será el mismo sin importar el orden en que a estos se les aplique la función f.

Utilización de los Programas

Una vez probado que es una paralelización trivial, procederemos a la utilización de este programa, el programa necesita un archivo de texto plano con el siguiente formato.

Donde el elemento antes de la coma hace referencia a los puntos x y el siguiente a los puntos y, como necesitamos hacer pruebas y no bastará solo con 5 puntos, podrán descargar de aquí un dataset que no recuerdo de donde lo saque, pero puede ayudarnos para realizar un ejemplo con más sentido que solo andar poniendo números aleatorios el cuál se podrá descargar de el siguiente link: https://www.dropbox.com/s/0axlcuh41qibmkk/datos_ventas.txt?dl=0

Ahora del archivo del link anterior tiene varias columnas, tal vez lo volvamos a utilizar más adelante cuando ponga el ejemplo de regresión lineal múltiple, pero para este ejemplo tomaremos las columnas fecha y ventas, que son las variables más obvias para un ejemplo de este tipo, ya que la variable dependiente serán las ventas que dependen de una variable independiente, el tiempo.

El archivo luce algo como lo siguiente.

Cuenta con 8400 registros, pocos para ser honestos, pero estos procesos funcionan de la misma manera como para 1 registro que como para miles de millones de registros, obvio si se ejecuta para pocos registros, no se verá la optimización del tiempo ya que para pocos registros es más eficiente ejecutar el programa verticalmente, osea en una sola máquina, el programa MapReduce de transformación en el siguiente link: https://github.com/NeoChoosenOne/TransformationData

Así que se creará otro proceso MapReduce que tendrá por funcionalidad el agrupar el monto total de acuerdo a los meses de cada año, procederemos subiendo el archivo anterior a nuestro HDFS, cosa que ya no mostraré como por que esto se vio en posts anteriores, una vez que el archivo esta arriba, procedemos a correr el programa de la siguiente manera.

• hadoop jar transformation_month-0.0.1-SNAPSHOT.jar com.cbds.transformation_month.GroupByMonthYear /prueba /linearregression 

La carpeta donde se encuentra el archivo con la información se llama prueba y la carpeta donde estará el resultado se llamará linearregression.

Una vez que termine este Job en el Web Browser podremos ver las dos carpetas, la de input (prueba) y la de salida (linearregression).

Con el nuevo MapReduce nuestra información luciera de la siguiente forma.

Como podemos observar, la primera columna a lado de la coma, es un conjunto de datos totalmente ordenado y es monótono creciente. 

Una vez obtenido el formato y los datos de la manera que nos importa, procedemos a correr el programa de regresión lineal que se encontraba al inicio de este post de la siguiente manera.

• hadoop jar linear_regression-0.0.1-SNAPSHOT.jar com.cbds.linear_regression.LinearRegression /linearregression /output

El cual lucirá de la siguiente forma en consola.

Una vez finalizado este Job que calcula los parámetros de nuestro modelo de regresión lineal, podremos encontrar en la carpeta Output/ en el Web Browser la cuál contiene nuestros dos parámetros.

Dentro de este archivo se encuentra el part-r-00000 con los parámetros correspondientes de acuerdo a nuestros datos a lo largo de este post.

Procedemos a descargar el archivo el cual debe lucir de la siguiente manera.

El valor del lado izquierdo de la coma es el estimador beta cero y el del lado derecho es el estimador beta uno, con esto hemos terminado este ejemplo de MapReduce. 

Estos valores para nuestros estimadores son los que más se ajustan a nuestros datos para poder ajustar una recta a estos datos, las primeras dos gráficas se representan como serie de tiempo, mientras que en la última del lado derecho se muestra como es que se vería el espacio de los puntos.

Cabe mencionar que mientras más grande sea el conjunto de datos y si el modelo se presta para realizar un ajuste lineal, este será más preciso, aunque es un modelo estadístico que empieza asumiendo que se tiene un conjunto de puntos muestra y esto se debe a que gracias a la estadística podemos obtener resultados con un bajo grado de incertidumbre sin trabajar con los datos y esto se debe a que antes si teníamos miles de millones de registros o midiéndolos desde el punto de vista espacio petabytes de información, era imposible procesar esa información en un tiempo razonable, por eso es que se trabajaba con muestras, pero gracias a este tipo de procesamiento en paralelo ya no es un problema tomar nuestra muestra como el conjunto total de información, y es más aún, gracias al siguiente teorema podemos afirmar que nuestros resultados serán más exactos gracias a esta forma de procesamiento con hadoop.

Entonces mientras más datos usemos, la media de nuestros datos calculados con nuestra estimación más se aproximará a la media media real de los datos en otras palabras, la media maestral tiende a la media población donde cada Y son la cantidad de dinero que se genera al día y solo realizamos una transformación para que se midiera de acuerdo al año.