Kitabı oku: «Innovando la educación en la tecnología», sayfa 20

Generación de reglas de asociación para productos de retail utilizando el algoritmo FP-Growth paralelo

Renato Pérez-Gómez

renato08lasalle13@gmail.com / Universidad de Lima, Perú

Recepción: 19-6-2019 / Aceptación: 8-8-2019

RESUMEN. Las organizaciones minoristas actuales tienen varias sucursales conectadas bajo el mismo sistema de gestión distribuido. Estos sistemas almacenan y registran la información de todas las transacciones dadas en las tiendas. Paralelamente, con el rápido crecimiento e implementación de las tecnologías de la información e Internet, la cantidad de datos generados en cada transacción o venta realizada es sustancial. Las técnicas de minería de datos tienen como objetivo identificar patrones y tendencias en una gran recopilación de datos. Su uso tiene un atractivo para los minoristas, ya que quieren convertir la gran cantidad de datos que tienen en información y conocimiento útiles. Una aplicación de minería de datos que atrae a los minoristas es el descubrimiento de reglas de asociación. El descubrimiento de estas reglas es la base de muchas decisiones comerciales, como el diseño de la canasta de productos, la elección de la estrategia de promoción y la combinación de productos. La intención de la investigación es la aplicación de las técnicas y metodologías de aprendizaje de asociación de reglas para la realidad de un comercio minorista con sucursales ubicadas en Lima. El conjunto de datos utilizado en esta investigación corresponderá a las transacciones realizadas con el tiempo para productos de consumo masivo.

PALABRAS CLAVE: minería de datos, análisis de la cesta de la compra, análisis de reglas de asociación, conjuntos de elementos frecuentes, FP-Growth, computación paralela

Generation of Association Rules for Retail Products Using the Parallel FP-Growth Algorithm

ABSTRACT. Retail organizations today have several branches connected under the same distributed management system. These systems store and record the information of all transactions taken place in stores. In parallel, with the rapid growth and implementation of information technologies and the Internet, the amount of data generated in each transaction or sale is substantial. The data mining techniques are aimed at identifying patterns and trends in a large data collection. The use of these techniques is attractive for retailers, as they want to convert the large amount of data they have into useful information and knowledge. A data mining application that attracts retailers is the discovery of association rules. The discovery of these rules is the basis of many commercial decisions, such as the design of the product basket, the choice of the promotion strategy and the combination of products. This research aims to apply learning techniques and methodologies of association rules for a retailer with branches located in Lima. The data set used in this research will match the transactions made over time for mass consumption products.

KEYWORDS: data mining, market basket analysis, association rule analysis, frequent itemsets, FP-growth, parallel computing

1. INTRODUCCIÓN

Con la tendencia, en los últimos años, de registrar y almacenar todo dato posible relacionado a los procesos operativos de la organización, la cantidad de data generada es abundante. Respecto a la industria del retail, gran parte de la data generada proviene de los miles de transacciones efectuadas en cada una de las sucursales. Los grandes representantes del sector a nivel mundial han identificado el gran potencial en minar la información oculta dentro de estos conjuntos de datos. Sin embargo, la aplicación de las técnicas de minería de datos no es el estándar en la mayoría de las organizaciones. La mayor aplicación de la minería de datos en el sector retail es la minería de reglas de asociación. Esta práctica supone un atractivo para las organizaciones debido a que tiene la intención de convertir la gran cantidad de datos que poseen en información útil y conocimiento. El descubrimiento de estas reglas es la base de muchas decisiones comerciales, como el diseño de la cesta de productos, la elección de la estrategia de promoción y la combinación de productos. Para la minería de reglas de asociación normalmente se hace uso del algoritmo Apriori. No obstante, en el desarrollo del algoritmo no estuvo pensado para manejar grandes volúmenes de datos por lo que en la actualidad es costoso, tanto computacional como en memoria. Existen otras alternativas óptimas respecto al manejo de memoria y que requieren de menos capacidad computacional; el algoritmo FP-Growth demuestra tener mejores resultados en rendimiento. Este algoritmo busca resolver las desventajas que posee el algoritmo clásico. Ya que este consiste en dos pasos para la generación de las reglas de asociación, es menos costoso en tiempo y en recursos. Si a este algoritmo se le suma la capacidad de procesar información en paralelo, el tiempo necesario para la ejecución del algoritmo será reducido drásticamente. Para lograr esto, en esta investigación, se hizo uso del framework Apache Spark y de su implementación del algoritmo FP-Growth.

2. ESTADO DEL ARTE

Los algoritmos existentes para la minería de reglas de asociación funcionan en datos estáticos, (Kaur y Kang, 2016). Estos encuentran las mejores reglas de asociación en base a métricas como soporte, confianza, elevación, etc. Sin embargo, para la próxima vez que se realiza la extracción de datos, estos algoritmos no capturan automáticamente los cambios en los datos. Por ello se usa algún otro algoritmo de comparación para rastrear el cambio en los datos. Este último, se utiliza para comprender la dinámica del proceso de generación de datos mediante la examinación de los cambios que se han producido en los patrones descubiertos. Se concluye que la minería periódica es un nuevo enfoque en la minería de datos que adquiere importancia. Este campo está evolucionando debido a las necesidades en diferentes aplicaciones y limitaciones de la minería de datos. Esto aumentaría el poder de las técnicas existentes de extracción de datos.

Según Di Fatta (2019), podría decirse que algunos factores limitantes han impedido una adopción más generalizada de ARM (association rule mining). En primer lugar, el descubrimiento de patrones interesantes a partir de datos requiere algoritmos combinatorios complejos y, a menudo, se benefician de la computación de alto rendimiento. Para problemas del mundo real, el espacio de búsqueda puede ser prohibitivamente grande. En segundo lugar, no es raro que incluso para un conjunto de datos de entrada relativamente pequeño, el conjunto de patrones descubiertos sea muy grande, incluso más grande que el conjunto de datos de entrada. En este caso, ARM es solo un primer paso en flujos de trabajo de datos más complejos que incluyen otras técnicas de extracción de datos. Por estas razones, un enfoque multidisciplinario que combina la experiencia tanto de la informática como del dominio de la aplicación específica es a menudo crítico.

En la investigación realizada por Griva, Bardaki, Pramatari y Papakiriakopoulos (2018) se propone un enfoque de análisis de negocios que extrae segmentos de visitas de clientes a partir de datos de venta. Se caracteriza por visita al cliente según las categorías de productos comprados en la canasta e identifica la intención de compra o la misión detrás de la visita. Además, se sugiere un enfoque de selección de funciones semisupervisadas que utiliza la taxonomía del producto como entrada y sugiere categorías personalizadas como salida. Este enfoque se utiliza para equilibrar el árbol de taxonomía del producto que tiene un efecto significativo en los resultados de la extracción de datos. En general, el resultado de esta investigación permite observar el comportamiento de compra de los clientes desde un punto de vista alternativo, no como sus necesidades e intenciones generales de compra, sino que se centran en sus requisitos y motivos por cada viaje o visita de compras.

Referente a Bhandari, Gupta y Das (2015), identifican la principal limitación de Apriori como el costo de tiempo para mantener un gran número de conjuntos candidatos con conjuntos de elementos frecuentes, soporte mínimo o conjuntos de elementos grandes. Por lo que proponen modificar el algoritmo para generar un FP-Tree en lugar de iterar el dataset una gran cantidad de veces. Con el algoritmo de Apriori se escaneó la base de datos dos veces, pero evidenciaron una mejora al usar el algoritmo paralelo y el concepto de partición. Presentan una fórmula matemática para seleccionar el clúster, ya que hay muchos clústeres. El resultado, un híbrido de Apriori con generación de FP-Tree. Concluyen, así, que el espacio de memoria se reduce drásticamente cuando se realiza una gran cantidad de transacciones desde los data-warehouse y al reducir el tiempo consumido en el escaneo de transacciones y también al reducir el número de transacciones a escanear.

En Galarreta Vásquez (2016) se identifican reglas de asociación entre categorías de productos de electrodomésticos de un retail. Para la prueba utilizaron data histórica de diez años para tres tiendas. El modelo se construyó con el software RapidMiner conectado a una BD en SQL Server. Eligió el algoritmo FP-Growth al ser más eficiente que Apriori e hizo uso de la totalidad de registros disponibles en la BD. Lo productos presentaban la siguiente jerarquía: familia, subfamilia, marca y es oferta. La data fue filtrada por oferta para dividir los productos en campañas promocionales, ya que podían alterar el resultado. La BD fue transformada para generar una matriz, la cual, luego, fue procesada por el algoritmo. La matriz almacenó la información cruzada de todo cliente que compró en el local y todas las subfamilias de productos. Si un cliente compró, por lo menos una vez un producto de la subfamilia, entonces fue registrado como TRUE, sea contrario como FALSE. Se concluyó que los productos con bajo precio incentivan la compra de productos con mayor precio.

Respecto a Xue, Wang, Liu y Li (2010), diseñan un modelo de minería de reglas de asociación para una venta de libros online. Para esto tienen 623 registros en la BD, los cuales fueron separados en 4 tablas. Definieron los parámetros soporte y confianza con 2 % y 60 %, respectivamente. Para la minería crearon una librería basada en ASP.NET. Luego, con un experimento analizaron los hábitos de compra de los clientes al encontrar asociaciones entre los artículos de pedido en la base de datos. La información obtenida del resultado del ejercicio concluyó que se lleva un aumento de las ventas al ayudar a los retailers a realizar una comercialización selectiva y planificar el espacio de la librería.

En Chunhua y Dongjun (2008) se presentan dos modelos de minería capaces de adaptarse a dos tipos de organización. Los autores plantean que existen dos tipos de organizaciones, aunque todas adoptan el enfoque de minería distribuida y el mismo patrón de toma de decisiones. En general, la carga de comunicación y la frecuencia de comunicación son los dos factores que afectan la eficiencia de la minería de datos. Se puede analizar un sistema de gestión distribuido desde tres aspectos: 1) cantidad de la tienda de sucursales; 2) el ancho de banda de comunicación; 3) entre las características del conjunto de datos local, las características incluyen si es denso o escaso, las cantidades de datos de transacciones, etc. Se definen dos tipos de organizaciones de retail. El primer tipo corresponde a las organizaciones que tienen varias sucursales y el bando de ancho de comunicación es largo (gran escala), mientras que la data de transacción de cada sucursal es pequeña. El segundo tipo, tienen pocas sucursales y comunicación pequeña, mientras que la data de transacción es grande (pequeña escala).