Distributed processing using cosine similarity for mapping Big Data in Hadoop A. F. Rojas, N. Y. Gelvez

Abstract— The analysis of big data is an issue that has become very important in recent years. The use of algorithms for processing big data that have generated as a result valuable information to organizations can be considered one of the biggest developments and most important lines of work today. This paper aims to show results in implementing cosine similarity for mapping big data in a flat database. For this purpose the information from movie ratings will be used, so it will result in a recommendation of a movie highly related to another. If the information used for testing is considered real, these results could be useful for the development of a recommendation system for products and services from an organization which has as well the records of their customers’ ratings.

Keywords— Big Data, Haddop, Cluster, Cosine similarity.

I. INTRODUCCIÓN

E

N este trabajo se encuentran los resultados y el análisis del uso de un sistema de recomendación que implementa el algoritmo de similitud de cosenos para correlacionar los registros de una base de datos plana. Los registros comprenden la información de cien mil películas de la base de datos MovieLens (https://movielens.org/), y representan lo que se puede entender por Big Data, de carácter abierto y libre distribución. Para el procesamiento de la información se hace necesario el uso de computación distribuida, debido al alto costo computacional. EMR (Elastic Map Reduce) es una solución de Amazon Web Services que provee un entorno de fácil uso para hacer computación distribuida en la nube. En conjunto, se tiene un entorno para la el procesamiento de datos de forma distribuida del cual se pretenden analizar el rendimiento y la confiabilidad, así mismo, de la correlación se pretende analizar los resultados y lo que puede significar para una organización esta información. II. BIG DATA

Actualmente las tecnologías son capaces de almacenar y procesar una cantidad de datos cada vez mayor de datos. Los datos de este tipo es lo que se conoce como “Big Data”. Big A. F. Rojas, Universidad Distrital Francisco José de Caldas (UDFJC), estudiante de pregrado en Ingeniería de Sistemas. Bogotá D.C, Colombia. [email protected] N. Y. Gelvez, Universidad Distrital Francisco José de Caldas (UDFJC), Ingeniera de Sistemas, Magister en Ciencias de la Información y comunicaciones con énfasis en Sistemas de Información. Bogotá D.C, Colombia. [email protected]

Data es el término para una colección de conjuntos de datos tan grande y compleja que se hace difícil de procesar con las herramientas tradicionales de procesamiento de datos. Big Data puede ser caracterizado por las tres V: volumen (grandes cantidades de datos), la variedad (incluye diferentes tipos de datos), y la velocidad (constantemente la acumulación de nuevos datos) [1]. Los datos se convierten en Big Data cuando su volumen, la velocidad, o la variedad superan las capacidades de los sistemas informáticos para almacenar, analizar y procesarlos. Recientemente, se ha ampliado la comprensión del Big Data añadiendo dos componentes V. De manera que se puede caracterizar al Big Data en cinco V: Volumen, Velocidad, Variedad, Veracidad, Valor [2]. Big Data no son sólo es gran cantidad de datos, en realidad es un nuevo concepto que proporciona una oportunidad para encontrar una nueva visión de los datos existentes. Hay muchas aplicaciones de Big Data: negocios, tecnología, telecomunicación, medicina, salud, servicios, bioinformática (genética), ciencia, comercio electrónico, finanzas, Internet (búsqueda de información, redes sociales), etc. Big Data puede provenir no sólo de los ordenadores, sino también desde miles de millones de teléfonos móviles, los mensajes de los medios sociales, diferentes sensores instalados en automóviles, medidores de servicios públicos, el transporte y muchos. En muchos casos, los datos están siendo generados más rápido de lo que pueden analizados. En el Big Data se puede incluir información estructurada y no estructurada. Los datos no estructurados son los datos que o bien no tienen una modelo de datos pre- definidos o no están organizados. Los datos estructurados son relativamente simples y fáciles de analizar, porque por lo general estos datos residen en bases de datos en forma de columnas y filas. El desafío para los científicos es desarrollar herramientas para transformar los datos no estructurados a estructurados. [3] Cuando se trata de grandes volúmenes de datos es un problema la agrupación de datos. A menudo, los conjuntos de datos, especialmente conjuntos de datos grandes, consisten en algunos grupos (clúster) y es necesario procesarlos al mismo tiempo. El método del Clúster ha sido aplicado a muchos problemas importantes [5] por el potencial de la computación distribuida, por ejemplo, a descubrir las tendencias de salud en los registros de pacientes, para eliminar entradas duplicadas en las listas de direcciones, para identificar nuevas clases de estrellas en datos astronómicos, para dividir los datos en grupos que son significativos, útiles, a agruparse millones de

documentos o páginas web. Para hacer frente a estas aplicaciones y muchos otros una variedad de algoritmos de agrupamiento se ha desarrollado. Existen algunas limitaciones en los métodos de Clustering existentes, la mayoría de los algoritmos requieren escanear el conjunto de datos varias veces, por lo que no son adecuados para ser procesados en un solo nodo. De manera que el Clúster de datos provee una solución más confiable y plausible para el procesamiento de grandes cantidades de datos. A. Haddop Cuando se trata de grandes datos, se trata de grandes desafíos tales como la velocidad de datos, volumen de datos y la variedad de datos. Tecnologías EDW y Hadoop puede útiles para gestionar estos desafíos. Hadoop es un framework de código abierto y es la fuente de una tecnología que precedió a casi todas las herramientas de almacenamiento de datos y análisis que han sido etiquetados como 'Big Data' (http://hadoop.apache.org). Con Hadoop es posible construir fácil, económica y efectivamente en escala muy grande un sistema de almacenamiento de datos y soluciones de procesamiento. El sistema de archivos Hadoop (HDFS) le permite enviar datos en Hadoop y luego trabaja con ellos simultáneamente en todos los discos y todos los servidores del Clúster. En el Clúster se tienen varios equipos, por lo que Hadoop proporciona un nuevo enfoque a la computación distribuida mediante la implementación de una idea llamada MapReduce (Mapeo Reducido). MapReduce es esencialmente una programación modelo para el procesamiento de grandes conjuntos de datos bajo un algoritmo paralelo distribuido que permite la separación, procesamiento y la agregación de grandes conjuntos de datos. A comparación con los tradicionales sistemas de gestión de bases de datos relacionales (RDBMS), Hadoop provee mejoras en tiempos de respuesta de consulta y la integridad con otros productos para el análisis de datos [7, 11]

B. Elastic Map Reduce Elastic Map Reduce (EMR) es un servicio web de Amazon Web Services (AWS) para el procesamiento rápido y rentable de grandes cantidades de datos. Simplifica el procesamiento de Big data, al proporcionar un framework de Hadoop auto gestionado que facilita la distribución y el procesamiento de grandes cantidades de datos entre instancias dinámicamente escalables llamado Elastic Cluster (EC2). EMR administra de manera segura y fiable sus casos de uso de Big Data, incluido el análisis de registros, la indexación web, el almacenamiento de datos, el aprendizaje automático, el análisis financiero, la simulación científica y la bioinformática. EMR Utiliza el procesamiento de Hadoop para hacer tareas como la indexación web, minería de datos, análisis de registros de archivos, aprendizaje automático, la simulación científica, y el almacenamiento de datos. [7]

Figura 2. Arquitectura EMR (http://www.slideshare.net/AmazonWebServices/clickstream-analyticsamazon-kinesis-and-apache-storm)

III. SIMILITUD DE COSENO

La similitud de coseno es una medida para la correlación de similitud. La similitud coseno mide de la similitud entre dos vectores en un espacio que posee un producto interior con el que se evalúa el valor del coseno del ángulo comprendido entre ellos. Esta función trigonométrica proporciona un valor igual a 1 si el ángulo comprendido es cero. Cualquier ángulo existente entre los vectores, el coseno arrojaría un valor inferior a uno. Si los vectores fuesen ortogonales el coseno se anularía, y si apuntasen en sentido contrario su valor sería -1. De esta forma, el valor de esta métrica se encuentra entre -1 y 1, es decir en el intervalo cerrado [-1,1]. Figura 1. Flujo de Información en un Clúster de Haddop (http://sentidoweb.com/2007/11/21/hadoop-plataforma-para-trabajar-congran-cantidad-de-datos.php) Figura 3. Fórmula para el cálculo del coseno para dos vectores con Sij características

Esta distancia se emplea frecuentemente en la búsqueda y recuperación de información representando las palabras (o documento) en un espacio vectorial. Una vez representados, los documentos y consultas como vectores, podemos medir su similitud. Una alternativa seria usar la distancia euclidiana, pero la variabilidad de largo entre documentos afectaría a la métrica. Lo más usado es usar el coseno del ángulo entre los vectores como medida de similitud. En minería de textos se aplica la similitud coseno con el objeto de establecer una métrica de semejanza entre textos. Se suele emplear como un indicador de cohesión de clústeres de textos. La complejidad de esta medida es cuadrática, lo cual la hace completamente aplicable a problemas del mundo real. La complejidad incluso puede ser transformada a lineal. [6]

Figura 4. Muestra del archivo de ratings

IV. APLICACION DE LA CORRELACION

En Big Data para realizar un análisis de la información se procede con los siguientes pasos: Pre-procesamiento de la información, distribución, procesamiento, resultados y análisis. (Este es un procedimiento normal y no implica el uso de una metodología estándar para el análisis de datos). El preprocesamiento de la información es la identificación de variables que son necesarias y que serán incluidas en el análisis, así como también el cotejamiento y la digitalización de la información que puede provenir de cualquier fuente, también limpiar los datos de registros incensarios, en la aplicación, esto se lleva a cabo en el mapeo. La distribución, es el establecimiento y distribución de la información en un clúster donde se pueda hacer computación distribuida, en este caso corresponde a las instancias de EMR. El procesamiento de la información es el núcleo de toda la operación, es este caso es la correlación por similitud de coseno. Al final están los resultados, que proveen información para que pueda ser analizada. En este trabajo no se tratan todos los pasos, pues se hace uso de una información recolectada externamente por la organización MovieLens. A. Pre-procesamiento de la información Los datos que serán usados para la aplicación corresponden a cien mil registros de películas cuya información se encuentra en formato digital en un documento de texto plano. Esto quiere decir que no es necesaria recabar, clasificar ni organizar la información. Lo que si es necesario es identificar las variables que se desean mapear, o más exactamente las variables que son necesarias para establecer una correlación. Si se considera que cada registro de la base de datos viene dado de la forma [identificación de usuario, identificación de película, rating, etiqueta de tiempo]. Al ejecutar el mapeo, los datos quedaran de la forma (clave: identificación de película, [ratings] ) descartando los otros datos pues no son importantes para la correlación. Previamente, se tomaran todos los nombres y las identificaciones da cada película de otro archivo, para luego ser usados posterior a la correlación para que los resultados sean más legibles. Esto último se incluye como otro paso de mapeo y solo influye en el tiempo de procesamiento. A continuación se muestra una parte del archivo que contiene los ratings de las películas y del otro que contiene los nombres. ( Ver Figura 4 y 5)

Figura 5. Muestra del archivo de nombres

B. Distribución y Procesamiento Para la distribución se hace preciso el uso del almacenamiento escalable en la nube de Amazon S3, otro de los servicios de AWS. En principio se suben los datos a la nube, luego se ejecuta el mapeo y la reducción en EMR, y después la respuesta se recibe en el ordenador local. Bien se podría almacenar la respuesta en el S3, pero es un procedimiento prescindible en este caso. Se debe recordar el objetivo de este trabajo es el análisis del rendimiento de la correlación en diferentes configuraciones de un clúster, luego el procedimiento del mapeo es el mismo para tordas las pruebas. Se realiza una prueba inicial, a manera de muestra de control en un maquina local de características depreciables. Luego se realiza el mismo procedimiento en un clúster sin esclavos, o una sola maquina EMR. Y luego consecutivamente se hace el mismo procedimiento con configuraciones más complejas de clúster así: una maquina maestra, una esclava. Una maquina maestra, dos esclavas. Y para finalizar una maquina maestra, tres esclavas. En todos los caos se sigue el mismo procedimiento paso a paso. Mapeo para la extracción de variables, reducir para agrupar las películas y su ratings por cada usuario, mapeo para relacionar pares de películas con pares de ratings, reducir mediante la ejecución de la correlación de similitud basada en coseno, mapeo para cambiar los identificadores de película por el nombre y finalmente reducir para generar un archivo de salida. A continuación se muestra un gráfico en donde se hace más claro todo el proceso. (Ver Figura 6)

clúster, cada una agregando un nodo más a la prueba de control. La identificación de cada paso es el mapeo (Paso 1), la correlación por similitud de coseno (Paso 2), y el la organización y muestra de los resultados (Paso 3). Todos los anteriores pasos corresponden a un proceso de MapReduce (Mapeo y Reducción, ver Tabla 1). TABLA I TIEMPO DE EJECUCION DE PASOS PARA CADA CONFIGURACION DE CLUSTER Paso (tiempo) \ Maquina Conf. Local Cluster

Figura 6. Pasos para en la prueba de la correlación

C. Resultados Para este trabajo se pueden clasificar los resultados en dos tipos: los resultados del procesamiento de los datos y las métricas de rendimiento de los clúster. Los resultados del procesamiento de los datos corresponden al resultado de la correlación de los registros de las películas y sus ratings. Lo que se pretende al usar la similitud de coseno, es proveer información que sea fácilmente legible y diga que tan relacionadas respecto al rating están unas películas de otras. Al final el resultado, es un conjunto de registros de la forma [nombre de película 1, [nombre de película 2, nivel de correlación, número de ratings]. El nombre de la película 1 y 2 es el filtro luego de fusionar el registro de nombres con el resultado de la correlación. El nivel de correlación es un número entre 0 y 1 que representa el porcentaje de correlación entre la película 1 y la 2. Y el número de ratings, corresponde a la cantidad de veces que fue calificada la película 2. De esta manera, se puede interpretar que la película que este más relacionada con otra es la que tenga mayor nivel de correlación y haya sido mayormente calificada. ( Ver Figura 7)

(1) Maquina de Control

(2) (3) Cluster con Cluster 1 esclavo con 2 esclavos

(4) Cluster con 3 esclavos

Paso 1

--

2 min

2 min

2 min

3 min

Paso 2

--

37 min

35 min

21 min

14 min

Paso 3

--

2 min

2 min

2 min

2 min

Total

50 -60 min

50 min

48 min

34 min

27 min

Además de la relación entre los pasos y el tiempo de procesamiento. AWS provee una sección de analíticas en donde se generan las siguientes graficas (Ver Figura 8 a 10). Que son la relación de consumo del sistema de almacenamiento HDFS del clúster respecto al tiempo, dado en bytes. Es importante el análisis de estos datos, ya que en un entorno de producción, la posibilidad de mejorar el rendimiento de un proceso puede es un procedimiento crítico.

Figura 8. Rendimiento del sistema de archivos HDFS para la máquina de control (1)

Figura 9. Rendimiento del sistema de archivos HDFS para el clúster (2)

Figura 7. Muestra del archivo de final de correlación

A continuación se presentan los resultados de las métricas correspondientes a las pruebas en cuatro configuraciones de

Figura 10. Rendimiento del sistema de archivos HDFS para el clúster (4)

V. ANALISIS

Los sistemas de recomendación de productos y servicios son un tema de principal interés en la web. La prueba de un algoritmo que pueda correlacionar ratings no solo de películas, sino de cualquier tipo de producto entonces se hace más relevante. De los resultados de la tabla 1, se puede concluir que el uso de computación distribuida reduce considerablemente el tiempo de procesamiento de la información en los procesos críticos. Sin embargo, y contrario al sentido común, agregar más nodos al clúster no hace que el tiempo de procesamiento se divida en el número de nodos del clúster respecto a una sola máquina. El tiempo si se ve reducido, pero no en proporción directa con el número de nodos del clúster. Respecto al rendimiento del sistema de archivos HDFS del clúster, se puede decir que al agregar mayor número de nodos la cantidad y la velocidad de los datos de entrar y salida se ve afectada dramáticamente. Se puede pasar del orden de los 6’000.000 de bytes de escritura (ver figura 8) en un clúster de una nodo, a los 250.000 bytes (ver figura 11) en un clúster de 4 nodos. Para mejorar el rendimiento al momento de procesar los datos se proponen cambios como: descartar los ratings malos antes de realizar la correlación, es decir, en el momento del mapeo. Cambiar el tipo correlación (Correlación de Pearson, Coeficiente de Jaccard, probabilidad condicional), aunque no es propósito de este trabajo, es una buena manera de mejorar el remiendo. Ajustar el umbral de la cantidad mínima de ratings o un ratings mínimo. Proponer otra similaridad para que pueda ser correlacionada también y tome en cuenta el número de ratings. Todo lo anterior, no es objeto de estudio en este trabajo, pero al ser factores que afectan directamente al rendimiento, vale la pena proponerlos.

REFERENCIAS [1] S. Schmidt, Data is exploding the 3V's of big data, Bussines, Computing World, 2012. [2] KY. Zhai, Y-S. Ong, and IW. Tsang, The Emerging “Big Dimensionality”. In Proceedinggs of the 22nd International on Wolrd Wid Web Companion. Computational. Intelligence Magazine IEEE, vol 9, no. 3, pp. 14-26, 2014 [3] Olga Kurasova, Virginijus Marcinkevicius, Viktor Medvedev, Aurimas Rapecka, and Pavel Stefanovic. Strategies for Big Data Clustering. Computational. IEEE 26th International Conference on Tools with Artificial Intelligence, 2014 [4] kannan Govindarajan1 , Thamarai Selvi Somasundaram1, Vivekanandan S Kumar, Kinshuk, Clustering in Big Data Learning Analytics, IEEE Fifth International Conference on Technology for Education, 2013 [5] A. McCallum, K. Nigam,and L. Ungar, ”Efficient clustering of high-dimensional data sets with application to reference matching”, in Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 169–178, 2000. [6] Felipe Bravo Marquez, Procesamiento de texto y modelo vectorial http://www.cs.waikato.ac.nz/~fjb11/clases/irintro.pdf [7] Elastic Map Reduce from Official AWS web https://aws.amazon.com/es/elasticmapreduce/ [8] MovieLes web, Base de datos para la recomendación de Películas , https://movielens.org/ [9] Frank Kane, Data Scientys, Taming Bid Data with MapReduce and Hadoop, Onlien Course, https://www.udemy.com/taming-big-data-withmapreduce-and-hadoop [10] A. Moreno, T.Redondo, Text Analytics: the convergence of Big Data and Artificial Intelligence, International Journal of Interactive Multimedia and Artificial Intelligence, 3(6), pp. 57-64, doi: 10.9781/ijimai.2016.369

Andrés Felipe Rojas Hernández., estudiante de Ingeniería de Sistemas de la Universidad Distrital Francisco José de Caldas ubicada en Bogotá, Colombia.

VI. CONCLUSIONES

La computación distribuida en la nube mediante clúster es una muy buena alternativa a la computación tradicional sobre todo cuando se pretenden procesar y analizar grandes cantidades de datos. Algunas compañías ofrecen servicios para la computación en la nube, el servicio de Elastic Map Reduce basado en Haddop es una herramienta muy fácil de usar, no necesita mantenimiento ni configuración, y aun así, tiene todo el potencial de procesamiento que cualquier otro entorno de computación distribuida, pero además tiene la capacidad de escalar según las necesidades de procesamiento. El uso de la correlación basada en similitud de coseno es un procedimiento que puede ser usado como base para un sistema de recomendación de productos, si bien no es la correlación más rápida, tiene buena fiabilidad y un rendimiento computacional aceptable. Por otro lado, si bien la computación distribuida en clúster es mejor en volumen, variedad y velocidad. No significa que el trabajo y tiempo de ejecución de los procesos escalen de manera lineal respeto al número de nodos del clúster. Es menester de quien realice el análisis determinar si por requerimientos computacionales requiere de un entorno distribuido o no.

Nancy Yaneth Gelvez García, Ingeniera de Sistemas, Magister en Ciencias de la Información y comunicaciones con énfasis en Sistemas de Información Universidad distrital. Líneas de investigación: virtualización, Big data, sistemas de información, redes de datos, radio cognitiva. Docente tiempo completo Universidad Distrital Francisco José de Caldas.