Cuando MapReduce no es la solución ¿qué hacemos?

MapReduce es una técnica mediante la que grandes volúmenes de datos se separan en subconjuntos más pequeños para su análisis simultáneo en diferentes servidores, para, posteriormente, recoger y agregar los resultados de todos los sub-procesos para producir la respuesta final. Con esta arquitectura distribuida, si utilizamos 100 servidores, podremos procesar un conjunto de datos 100 veces más rápido que con una arquitectura tradicional no distribuida.

MapReduce funciona muy bien en contextos en los que las variables son tratadas una a una. Por ejemplo, queremos analizar un terabyte de datos de texto para determinar la frecuencia de todas las palabras clave que se encuentran en el texto. Con esta arquitectura es posible dividir el archivo en “n” más pequeños (siendo “n” el número de servidores de que disponemos) y elaborar “n” tablas de frecuencia de las palabras clave. Una vez finalizado este proceso reintegramos las “n” tablas en una única con todas las frecuencias agregadas

Sin embargo, cuando se necesita procesar conjuntos de datos en forma de matriz (relación 2 por 2, 3 por 3, etc.) MapReduce no ofrece ninguna ventaja comparativa sobre las arquitecturas no distribuidas. En estos casos debemos poner nuestra vista en soluciones más sofisticadas.

El Problema

Digamos que tenemos un conjunto de datos que consta de “N” observaciones y “K” variables, donde el conjunto de las variables k ({k1, k2,…, k10.000}) representan diferentes índices o cotizaciones y el conjunto de las observaciones ({arriba, abajo}) representan señales de precios de acciones medido en N tiempos diferentes.

Si queremos encontrar correlaciones muy altas con ventanas de tiempo para poder obtener un beneficio, por ejemplo si: Google es arriba hasta hoy o Facebook es abajo hasta mañana; tendremos que calcular diez mil veces las correlaciones FormulaKpara resolver este problema. En este escenario no se pueden desagregar las 10.000 Ks de cotización en 1.000 grupos, cada uno con 10 símbolos de cotización, para a continuación utilizar MapReduce. La gran mayoría de las correlaciones que hay que calcular implicará un conjunto de Ks de cotización en un árbol y parte de este conjunto de Ks en otro árbol. La aplicación de MapReduce para efectuar los cálculos es inútil en este caso. El mismo problema surge si se en lugar de una “correlación” queremos calcular cualquier otra función, digamos , calculada en dos variables, en lugar de en una.

Las Soluciones

1) Muestreo

En lugar de calcular todas las correlaciones cruzadas, sólo calcular una fracción de ellos. Seleccionamos m pares de variables aleatorias y calcular las correlaciones para estos pares m solamenteFormulaM

Una estrategia inteligente consiste en comenzar con una fracción muy pequeña de todos los posibles pares y aumentar el número de pares hasta el más alto (el más significativo) en el que las correlaciones apenas crece más. O se puede usar un enfoque simulado “precocinado” en el que decidir que variables agregar, para formar nuevas parejas, después de establecer  correlaciones tras el proceso de, digamos, 1.000 pares de variables seleccionadas al azar.

 

2) Data Binning

Si se puede hacer bins (trozos) de las variables en n elementos que tengan sentido, siendo n un valor pequeño (digamos = 5), entonces podremos pre-calcular todas las correlaciones posibles y guardarlas en una tabla de búsqueda. En nuestro problema tenemos varibales (arriba o abajo) en lugar de mediciones reales y continuas, como los deltas de los precios.

Con n = 5, hay más de 512 pares potenciales de valor. Un ejemplo de estos pares es {(arriba, arriba, abajo, arriba, abajo), (arriba, arriba, arriba, abajo, abajo)} donde los 5 primeros valores corresponden a una determinada población, y los últimos 5 valores a otro stock. Por tanto, es fácil de calcular previamente las 512 correlaciones. Todavía tendremos que buscar todos los pares de
FormulaK

poblaciones para resolver el problema, pero ahora es mucho más rápido: para cada par a tenemos una correlación, sin tener que realizar un cálculo, accediendo a un valor en una tabla hash o una matriz con 512 células.

Tenga en cuenta que con las variables binarias, la fórmula matemática para la correlación se simplifica significativamente. Utilizar la fórmula simplificada en todos los pares sera más rápido que utilizar las tablas de búsqueda para acceder a 512 correlaciones precalculadas. Sin embargo, el principio funciona independientemente de si usted calcula una simple correlación o una función más compleja.

 

3) La clásica reducción de datos

Las técnicas tradicionales de reducción también se pueden utilizar, hacia delante o hacia atrás, por etapas,  agregando o quitando una o dos variables a la vez, siempre que la variable agregada o eliminada se selección para maximizar la entropía resultante.

En pocas palabras, si usted tiene dos subconjuntos de datos del mismo conjunto de datos grande, un conjunto A con 100 variables (que pesa 1,23 GB cuando se comprime) y un conjunto B con 500 variables que incluyen las variables del conjunto A (que pesa 1,25 GB cuando se comprime), se puede decir que el extra de 400 variables (símbolos de acciones, por ejemplo) en el conjunto B no aportan ningún valor predictivo adicional y puede ser ignorada. O en otras palabras, la mejora obtenida con el conjunto B es tan pequeño que es probablemente menor que el ruido inherente a estas señales de precios de acciones.

 

4) La óptima

Una solución interesante consiste en utilizar una combinación de las tres estrategias anteriores. Siempre teniendo cuidado de asegurarnos que las altas correlaciones encontradas no son un efecto causado por la “maldición del BigData“.

Otro ejemplo donde MapReduce no es de utilidad: la construcción de una taxonomía de KeyWords

Queremos determinar la frecuencia de un KeyWords dentro de un “par de KeyWords” (Un “KeyWords” es un conjunto de palabras clave que se encuentran en una misma página web o cerca las unas de la otras en una misma página web. Un KeyWords, como norma general, está compuesto por más de una palabra pero casi nunca por más de tres). Mediante un webCrawler, hacemos una ingesta completa del contenido de texto que tiene una web concreta, una noticia, un muro en Facebook y un time line en Twitter. Una vez con toda la data calculamos las frecuencias para cada KeyWords por cada “par de KeyWords”. Con todas las frecuencias, crearemos una tabla (que normalmente contiene muchos millones de KeyWords, incluso después de la limpieza de los mismos), donde cada entrada es un par de KeyWords y tres números. Por ejemplo: A=”California seguro”, B=”seguro de hogar”, x=543, y=998 y z=11; donde:

  • x es el número de veces que aparece la KeyWords A en todas las páginas.
  • y es el número de veces que aparece la KeyWords B en todas las páginas.
  • z es el número de veces en que A y B se encuentran en la misma página.

Esta tabla de frecuencias de KeyWords se puede construir de una manera fácil y eficiente con MapReduce. Tenga en cuenta que la gran mayoría de las palabras clave A y B no forman un “par de KeyWords”, ya que z representa menos del 1% del total de respuestas. Así que si consideramos estas entradas como nulas y hacemos caso omiso de ellas, tendremos una base de “par de KeyWords” muy manejable que contendrá poco más de 50 millones de entradas.

Pero para crear una taxonomía, que desea poner estas KeyWords en grupos similares, podríamos calcular una disparidad d (A, B) entre los KeyWords A y B; en nuestro caso

Cuanto más alto sea el resultado de d (A, B), la disparidad entre A y B es más estrecha. Ahora bien, el gran problema es realizar el clustering – cualquier tipo de agrupamiento, por ejemplo, jerárquico – en el “par de KeyWords” de base, utilizando cualquier tipo de disparidad. Este problema, al igual que el problema de la correlación, no se puede dividir en sub-problemas, seguido de una etapa fusión, utilizando MapReduce.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s