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

Yazı tipi:

3. ANTECEDENTES

La minería de itemsets frecuentes dentro del dataset es el punto clave de la generación de reglas de asociación. Lo que se pretende con esta técnica es extraer los itemsets más frecuentes y grandes dentro de una gran lista de transacciones que contienen varios elementos cada uno. A continuación, una breve descripción de dos algoritmos para la minería de reglas de asociación.

3.1 Algoritmos de minería de asociación

La primera propuesta de solución presentada se dio en Agrawal, Imienlinski y Swami (1993), en donde se presenta el algoritmo Apriori. Durante veinte años, este algoritmo se presentó como la solución clásica en el área. Sin embargo, muchas otras soluciones han sido propuestas para obtención de las reglas de asociación para base de datos transaccionales. Las dos grandes desventajas que se pueden identificar de Apriori son el tiempo de ejecución que crece exponencialmente con la cantidad de registros y los requisitos computacionales para la generación de estas reglas. Ante estos puntos, se presenta el algoritmo FP-Growth como la alternativa ideal (Han, Pei y Yin, 2000).

3.2 FP-Growth

Es una mejora de Apriori diseñada para eliminar algunos de los cuellos de botella en este (Han et al., 2000). El algoritmo se diseñó teniendo en cuenta los beneficios de mapReduce, por lo que funciona bien con cualquier sistema distribuido centrado en mapReduce. FP-Growth simplifica todos los problemas presentes en Apriori mediante el uso de una estructura llamada FP-Tree. En un árbol FP, cada nodo representa un elemento y su recuento actual, y cada rama representa una asociación diferente.

El árbol FP se construye leyendo el conjunto de datos una transacción a la vez y asignando cada transacción a una ruta en el árbol de FP (Han, Kamber y Pei, 2011). Como diferentes transacciones pueden tener varios elementos en común, sus rutas pueden superponerse (Tan, Steinbach y Kumar, 2005). Cuanto más se superponen las rutas, más compresión se puede lograr utilizando la estructura del árbol de FP. Si el tamaño del árbol de FP es lo suficientemente pequeño como para caber en la memoria principal, esto permitirá extraer conjuntos de elementos frecuentes directamente de la estructura en la memoria en lugar de realizar pases repetidos sobre los datos almacenados en el disco.

Para minar el árbol FP se empieza desde cada patrón de longitud 1 (patrón sufijo inicial), se construye su base de patrón condicional (consiste en el set de rutas de prefijo en el árbol que concurre con el patrón sufijo), luego se construye su árbol FP (condicional), y se realiza la minería de forma recursiva en el árbol (Han et al., 2011). El crecimiento del patrón se logra mediante la concatenación del patrón sufijo con los patrones frecuentes generados a partir de un árbol FP condicional.

La mayor ventaja que se encuentra en FP-Growth es el hecho de que el algoritmo solo necesita leer el archivo dos veces, como se explica a continuación, quien lo lee una vez por cada iteración. Otra gran ventaja es que elimina la necesidad de calcular los pares que se van a contar, lo cual es muy pesado en el procesamiento, ya que utiliza el FP-Tree (Fournier-Viger et al., 2017). Esto lo hace O (n) que es mucho más rápido que Apriori. El algoritmo FP-Growth almacena en memoria una versión compacta de la base de datos.

4. METODOLOGÍA
4.1 Exploración de la data

Antes de entrar a detallar el modelo y su funcionamiento, es importante dedicar esfuerzos a entender la data con la que se está trabajando. El análisis exploratorio de datos se refiere al proceso crítico de realizar investigaciones iniciales sobre datos para descubrir patrones, detectar anomalías, probar hipótesis y verificar suposiciones con la ayuda de estadísticas de resumen y representaciones gráficas. Es una buena práctica comprender los datos primero y tratar de recopilar tantos conocimientos a partir de ellos.

Luego de haber realizado la limpieza necesaria al dataset para que este se encuentre listo y sea alimentado al modelo, se realiza un análisis exploratorio a la data. De esta manera, la información que se obtenga permitirá generar visión de negocio. Es decir, conocimiento sobre cuál es el comportamiento entre las entidades del caso de estudio. Para este caso en específico, sería la relación entre productos y departamentos o categorías, los diez productos con más órdenes, las horas o días de la semana con más órdenes, etcétera.

4.1.1 Distribución de productos por categoría

Esta observación permite entender cuáles son los productos que más espacio ocupan en estantes y a qué categoría pertenecen (véase la figura 1). El espacio en los estantes influye en la efectividad de ventas y marketing. Evidentemente, existe una diferencia en la visibilidad y atención recibida entre los estantes inferiores y los estantes superiores, por lo que se puede observar una diferencia significativa entre las ventas de los productos y marcas colocadas en dos estantes diferentes. Esta distribución es fundamental para que los retailers puedan establecer sus estrategias de negocio y marketing.

4.1.2 Productos más vendidos

Es importante también tener en cuenta cuáles son los productos que más ventas u órdenes registran ya que son estos los puntos clave para las estrategias de negocio que elaboren los retailers. En la figura 2 se pueden observar los diez productos más vendidos. Esto, junto con el análisis anterior, permite saber más si la distribución de ventas de la categoría depende de uno o un grupo selecto de productos o del conjunto total.

4.1.3 Número de productos por transacción u órdenes

De igual manera que las visualizaciones anteriores, otro aspecto importante a tomar en cuenta es la cantidad de productos que se registran por transacción u orden. Esto quiere decir, cuántos productos compra cada cliente. De esta forma, los retailers podrán crear ofertas personalizadas que logren atraer más a un cliente según esta métrica.

4.1.4 Cantidad de órdenes en el tiempo

Por último, esta visualización permite conocer las frecuencias de compra de los clientes. Qué días de la semana y a qué hora de dicho día se registran las mayores cantidades de transacciones. Con estos datos es posible determinar la probabilidad de que un cliente existente con un historial de compras adquiera un producto en un momento determinado. Esta información permite no solo dirigirse a los clientes que tienen más probabilidades de comprar algo, sino también adaptar la oferta a lo que es más probable que les atraiga.

4.2 Modelo y experimentación

Se tomó la decisión de desarrollar la propuesta de solución en el lenguaje Python. Este es el lenguaje más utilizado en el área de Data Science (por lo que tiene una excelente comunidad y extenso conjunto de librerías), es liviano y eficiente en la ejecución de código, pero también es multifuncional. De igual forma, se utilizó el framework de computación en clúster y de código abierto Apache Spark, este provee una interfaz para la programación con paralelización de la data implícita y tolerancia a fallos.

La legibilidad y la simplicidad inherentes de Python hacen que sea relativamente fácil de recopilar y la cantidad de bibliotecas analíticas dedicadas disponibles en la actualidad significa que se puedan encontrar paquetes ya adaptados a las necesidades del problema que se pueden descargar libremente. Esto se debe a que Python es un lenguaje de programación multiparadigma: una especie de navaja suiza para el mundo de la codificación. Es compatible con la programación orientada a objetos, la programación estructurada y los patrones de programación funcional, entre otros.

Apache Spark es un potente motor de código abierto que ofrece procesamiento de flujo en tiempo real, procesamiento interactivo, procesamiento de gráficos, procesamiento en memoria y procesamiento por lotes con una velocidad rápida, facilidad de uso e interfaz estándar. Dentro de los componentes existentes en el ecosistema de Spark, en esta propuesta de solución se utilizarán los módulos MLlib y SQL. Esta interfaz contiene implementaciones de algoritmos y modelos especializados de machine learning. En este módulo se encuentra la implementación del algoritmo FP-Growth.

Respecto al modelo planteado en este trabajo para la generación de reglas de asociación utilizando el algoritmo FP-Growth, lo primero que se realizó fue identificar los módulos necesarios para la solución. Estos son, un módulo para el preprocesamiento y exploración de la data y otro módulo para el algoritmo de generación de ítems frecuentes y generación de reglas de asociación. Lo que en el área de machine learning se conoce como pipelines. Esto se refiere a la estructura secuencial de pasos a seguir para la implementación del modelo, siendo la salida de cada paso la entada del siguiente.

El flujo de trabajo representativo de la propuesta de solución se puede observar en la figura 5. A partir de lo explicado en esta sección, se pueden abstraer cinco pasos críticos que contienen los procedimientos necesarios a llevar a cabo desde la lectura del dataset (input) hasta la generación de las reglas de asociación (output).

Antes de describir en qué consisten los pasos mencionados, es necesario entender la estructura del dataset que se posee, porque esta estructura define el enfoque a tomar para las acciones respectivas al preprocesamiento, a cómo realizar un análisis exploratorio y cómo leer esta data, y la estructura que este conjunto de datos debe tener para poder ser alimentado al modelo. El dataset en posesión es una fracción en dimensión de tiempo de los datos almacenados en una base de datos (BD) relacional para un retailer del sector autoservicio. El nombre del retailer permanecerá confidencial por mutuo acuerdo. Sin embargo, es posible detallar que esta fracción pertenece a registros correspondientes a la temporada verano. Este dato será clave en el apartado de resultados, ya que se da contexto al output del modelo. Al ser un reflejo de la BD, se tiene un archivo de tipo csv para cada entidad, en total cuatro: pasillos, categorías, órdenes y productos. Estas se relacionan a partir de identificadores (Id) únicos para cada registro de cada tabla, como una BD transaccional.

Para el módulo de preprocesamiento se eliminaron todos los registros NA, como primer paso. Después se procedió a determinar las variables o campos factores, que en este caso vendrían a ser ProductID y OrderId. Estas variables permiten la agrupación de los ítems por transacción. Esto quiere decir, si n número de ítems pertenecen a la misma transacción t, esto se traducirá a una lista de transacciones donde t contendrá los n ítems. Finalmente, ya que el modelo necesita una lista de tuplas compuestas del índice de la transacción y de la lista de ítems en esa transacción, se selecciona la lista de ítems producto de la agrupación realizada en el paso anterior. Asimismo, para la exploración de la data se utilizó el componente SQL de Spark. Este permite realizar consultas SQL a los dataframes de Spark, algo que facilita el tratamiento de la data ya que esta posee una estructura relacional. No se detallarán los resultados de la exploración de la data dado que eso fue realizado en el apartado 4.1.

Con respecto al módulo para la generación de los ítems frecuentes y las reglas de asociación, la implementación del algoritmo en Spark requiere de cuatro parámetros, los cuales son la columna en el dataset que contiene a la lista de ítems por transacción, el soporte mínimo, la confianza mínima y el número de particiones a realizar el paralelismo del procesamiento. La columna para evaluar es simplemente el nombre de la columna en el dataframe Spark que contiene la lista de ítems. El soporte y la confianza mínimos son valores que van en el rango de 0 a 1, y se expresan en porcentaje en el análisis. Los valores para estos dos parámetros dependen de las necesidades de la empresa y es ella la encargada de realizar el estudio correspondiente para establecer estos valores. Debido a que el análisis de las necesidades de la empresa es personalizado e implica muchos aspectos a considerar, este escapa del alcance de esta investigación. El número de particiones es necesario cuando se desea ejecutar el modelo creado en un clúster de computadoras. Puesto que en este trabajo todo procesamiento es ejecutado desde un solo ordenador, este parámetro no impacta en el desempeño real del modelo. Posteriormente, ya definidos los parámetros para el modelo, se pasa a realizar el ajuste de este con el conjunto de datos especificado. El resultado será el modelo adaptado a los valores dados a partir de la data alimentada. Una vez realizado esto, se pueden obtener los ítems frecuentes y reglas de asociación gracias a las funciones ya definidas en el framework de Apache Spark.

La abstracción de la lógica detrás de la generación de ítems frecuentes y reglas de asociación, se definen en los algoritmos find_frequent_patterns y generate_association_rules. La última es la que genera las reglas de asociación a partir de los patrones frecuentes encontrados. Respecto al algoritmo find_frequent_patterns, se instancia un objecto de clase árbol con los parámetros transacciones y umbral de soporte mínimo para filtrar los patrones frecuentes. Este objeto hará llamado a la función mine-tree, esta función actuará dependiendo de la condicional de si el árbol contiene un solo camino o rama que nace desde el nodo o contiene múltiples caminos o ramas. Si el árbol tiene un solo camino se generará la lista de patrones frecuentes. Si el árbol tiene muchos caminos se minarán estos subárboles y se tendrá una sublista de patrones por subárbol, estas sublistas luego serán insertadas en el diccionario principal de patrones, el cual tendrá aquellos patrones por subárbol que superen el mínimo de soporte establecido. Con respecto al manejo de la clase árbol, este se generará y trabajará de manera común, con recur-sividad. Respecto al algoritmo generate-association-rules, tomará el diccionario que generó find-frequent-patterns y lo iterará para generar un diccionario que tenga como clave al antecedente y como valores al consecuente y a la confianza. La confianza representa la probabilidad de que el consecuente se presente cuando exista el antecedente.

ALGORITHM 1: find-frequent-patterns (transacciones, soporte mínimo)

Tree <- Instanciar un objeto árbol con parámetros el dataset y el soporte mínimo deseado

IF tree tiene un solo camino:

Generar diccionario de patrones frecuentes

ELSE:

Generar sublista de patrones frecuentes por cada subárbol

Insertar sublista de patrones frecuentes en el diccionario principal de patrones frecuentes

Output <- diccionario de patrones frecuentes

End

ALGORITHM 2: generate-association-rules (patrones, confianza mínima)

FOR itemset IN patrones.clave:

soporte_superior <- patrones[itemset]

FOR index IN itemnset.longitud:

FOR antecedente IN itemset[i]:

IF antecedente se encuentra en patterns:

soporte_inferior <- patrones[antecedente]

confianza < - soporte_superior / soporte inferior

IF confianza >= confinaza_mínima:

Reglas[antecedente] = (consecuente, confianza)

Outpur <- Reglas

End

ALGORITHM 3: FP-Growth

Patrones <- find_frequent_patterns(dataset, soporte_min)

Reglas <- generate_association_rules(patrones, confianza_min)

Output <- Reglas

End

5. RESULTADOS Y DISCUSIÓN

El modelo se inicializó con los valores 0,01 para soporte mínimo y 0,1 para confianza. Los ítems frecuentes encontrados que sobrepasen el umbral de soporte están conformados por dos ítems. Esto quiere decir que no existen relaciones entre 3 ítems que pasen el 1 % del total de transacciones. En la figura 6 se puede apreciar los 16 primeros ítems frecuentes según su frecuencia. La relación más fuerte existente entre fresas orgánicas y bolsa de plátanos orgánicos. Existen un total de 131 209 transacciones, por lo que la relación descrita aparece el 2,34 % de veces.

Referente a las reglas de asociación, la relación más fuerte es entre palta Hass orgánica (antecedente) y bolsa de plátanos orgánicos (consecuente). Esta relación se refiere a la probabilidad de que ocurra el consecuente a partir del antecedente. Es decir, hay un 33,18 % de que la bolsa de plátanos orgánicos sea comprado cuando se compra palta Hass orgánica. A diferencia de los ítems frecuentes, este examina la relación pirobalística entre dos o más ítems, mientras que los ítems frecuentes es una descripción frecuencial de las apariciones conjuntas de los ítems. En la figura 7 se pueden apreciar las 20 reglas de asociación más fuertes según su confianza.

La aparición constante de productos de tipo fruta o verdura se debe a que la fracción del dataset utilizado corresponde a la temporada de verano, por lo que es comprensible este comportamiento. Esto indica que es importante realizar un análisis exploratorio previo a la data para entender, luego, los resultados obtenidos.

No se decidió por realizar más pruebas con diferentes parámetros porque estos dependen enteramente de las necesidades de negocio del retailer. Los resultados obtenidos de otra combinación de parámetros no son más ni menos correcta que la realizada en este trabajo. El punto clave para la obtención de los mejores resultados es dedicar el esfuerzo al entendimiento y tratamiento de la data de entrada y el estudio profundo de las necesidades de la organización.

Respecto al desempeño del modelo, se realizaron varias pruebas al tiempo de ejecución del modelo y sus componentes. Para esto se identificaron las partes que componen el modelo: el ajuste de la data al modelo (model fit), la generación de ítems frecuentes, la generación de reglas de asociación, la lectura o carga de la data, la preparación de la data para alimentar al modelo. En la tabla 1 se pueden observar los tiempos de ejecución para cada uno de estos componentes. El número de evaluaciones hace referencia a cuántas veces se ejecutará el componente correspondiente, mientras que las repeticiones significan cuántas veces esta evaluación será realizada. La salida de este ejercicio es el tiempo más bajo del total de repeticiones, mientras que el tiempo de ejecución es la división del tiempo total de repetición entre el número de evaluaciones. Es decir, para la primera fila, se ejecutó 5 veces el componente model fit con 10 evaluaciones cada una, el mínimo tiempo entre estas 5 repeticiones es el tiempo total de repetición (44,21 s), y este tiempo dividido entre el número de evaluaciones da el tiempo promedio (para uso referencial) de cada evaluación (4,42 s).

Es tentador calcular la media y la desviación estándar del vector resultado de las repeticiones. Sin embargo, esto no es muy útil. En un caso típico, el valor más bajo proporciona un límite inferior para la rapidez con la que la máquina pueda ejecutar el fragmento de código dado; los valores más altos en el vector de resultados generalmente no son causados por la variabilidad en la velocidad de Python, sino por otros procesos que interfieren con su precisión de tiempo. Por lo tanto, el mínimo del resultado es probablemente el único número que debería utilizarse como referencia al tiempo de ejecución del componente.

Si se separan los componentes por metodología, presentados en la tabla 1, en dos grupos, se tendría a model fit, freq ítems (ítems frecuentes) y ass rules (reglas de asociación) como un grupo y a load data y prepare data como otro. Este último es muy costoso en tiempo porque realiza la carga de la data (3 millones de registros para este trabajo) y las asociaciones necesarias. Para el primer grupo, es model fit el que toma mayor tiempo pues ajusta la data al modelo, el cual crea el árbol FP a partir de los parámetros establecidos, para posteriormente tanto freq ítems como ass rules realicen la minería de ese árbol. En este punto es donde se aprecian las ventajas de FP-Growth, ya que, una vez realizada la construcción del árbol, la minería de esta y la obtención de información como resultado toma milésimas de segundo para un conjunto de data real.

En cuanto al tiempo de ejecución variando la cantidad de registros a procesar, en las tablas 2 y 3 se pueden observar los resultados obtenidos. En la tabla 2 se realiza la misma dinámica que en la tabla 1. Se utilizó el módulo Timeit de Python para realizar la medición del tiempo. Como puede observarse, la diferencia de tiempo no es drástica entre las pruebas. Aunque el impacto de subir de 100 000 a 1 000 000 registros fue fuerte y el más notorio entre todos, el siguiente paso arriba (10 000 000) no tiene gran diferencia. La tabla 3 mide lo mismo, la diferencia radica que esta utiliza el módulo Time para medir el tiempo. Esa medición, a diferencia de la anterior, es afectada por los procesos que se ejecutan en segundo plano u otras tareas que el ordenador está realizando.