Frequent Itemset Mining Alghorithms
library(dplyr)
library(arules)
library(ggplot2)
library(plotly)
library(arulesViz)
library(plyr)
library(tidyverse)
library(readxl)
library(knitr)
library(lubridate)
library(plotly)Frequent Itemset Mining Alghorithms
Supongamos que un cliente nos brinda datos para todas las transacciones que consisten en artículos comprados en la tienda por varios clientes durante un período de tiempo y nos pide que usemos esos datos para ayudar a impulsar su negocio. El cliente usará sus hallazgos no solo para cambiar/actualizar/agregar artículos en el inventario, sino también para cambiar el diseño de la tienda física o más bien una tienda en línea.
Frequent Itemset Mining se utiliza cuando se desea encontrar una asociación entre diferentes objetos en un conjunto, encontrar patrones frecuentes en una base de datos de transacciones. Las aplicaciones de Frequent Itemset Mining se encuentran en marketing, análisis de datos basket (o análisis basket de mercado) en la venta minorista, agrupación y clasificación. Se puede llegar a concluir qué artículos compran los clientes juntos con frecuencia mediante la generación de un conjunto de reglas llamadas Reglas de asociación. En palabras simples, le da salida como reglas; en forma:
\[ \text{Articulo A } \Rightarrow \text{ Articulo B} \]
Los clientes pueden utilizar esas reglas para numerosas estrategias de marketing, por ejemplo:
- Cambiar el diseño de la tienda según las tendencias
- Análisis del comportamiento del cliente
- Diseño de catálogos
- Cross marketing en tiendas online
- ¿Cuáles son los artículos de tendencia que compran los clientes?
- Correos electrónicos personalizados con ventas complementarias
Consideremos el siguiente ejemplo.
| ID | Articulo |
|---|---|
| 1 | Pan, Leche |
| 2 | Pan, Pañales, Cerveza, Huevos |
| 3 | Leche, Pañales, Cerveza, Refrescos |
| 4 | Pan, Leche, Pañales, Cerveza |
| 5 | Pan, Leche, Refrescos, Pañales |
Un conjunto de artículos frecuentes es {Pañales, Cerveza}.
\[ \text{Pañales } \Rightarrow \text{ Cerveza} \]
El ejemplo anterior es un conjunto de datos de transacciones. Se puede ver las transacciones numeradas del 1 al 5. Cada transacción muestra los artículos comprados en esa transacción. Puedes ver que Pañal se compra con Cerveza en tres transacciones. Del mismo modo, el pan se compra con leche en tres transacciones, lo que las convierte en conjuntos de artículos frecuentes. Las reglas de asociación se dan de la siguiente forma:
\[ \text{Articulo A } \Rightarrow \text{ Articulo B}[\text{Support}, \text{ Confidence}] \]
Por ejemplo:
\[ \text{Computadora } \Rightarrow \text{ Anti-Virus}[\text{Support = 0.2}, \text{ Confidence=0.6}] \]
La regla anterior dice:
- El 20% de las transacciones muestra que el software antivirus se compra con la compra de una computadora
- El 60% de los clientes que compran software antivirus se adquiere con la compra de una computadora
Conceptos básicos de los Frequent Itemset Mining Alghorithms
Itemset: colección de uno o más elementos. K-item-set significa un conjunto de k elementos.
Support Count: frecuencia de aparición de un conjunto de elementos
Support (s): Fracción de transacciones que contienen el conjunto de elementos ‘X’
\[ \text{Support(X)} = \frac{\text{Frecuencia(X)}}{N} \]
Para una regla \(A \Rightarrow B\), el soporte viene dado por:
\[ \text{Support(A => B)} = \frac{\text{Frecuencia(A,B)}}{N} \]
- Confidence(c): Para una regla A => B, la confianza muestra el porcentaje en el que B se compra con A.
\[ \text{Confidence(A => B)} = \frac{\text{Frecuencia(A,B)}}{\text{Frecuencia(A)}} \]
El soporte y la confianza miden qué tan interesante es la regla. Está establecido por el soporte mínimo y los umbrales mínimos de confianza. Estos umbrales establecidos por el cliente ayudan a comparar la fuerza de la regla de acuerdo con su propia voluntad o la del cliente. Cuanto más cerca del umbral, más útil es la regla para el cliente.
- Lift: Lift da la correlación entre A y B en la regla A => B. La correlación muestra cómo un conjunto de elementos A afecta al conjunto de elementos B.
\[ \text{Lift(A => B)} = \frac{\text{Support}}{\text{Support(A)Support(B)}} \]
Si Lift = 1, entonces A y B son independientes y no se puede derivar ninguna regla de ellos.
Si Lift > 1, entonces A y B son dependientes entre sí, y el grado del cual viene dado por el valor de lift.
Si Lift < 1, entonces la presencia de A tendrá un efecto negativo en B.
Apriori.
Frequent Itemset Mining considera un enfoque de dos pasos:
Generación de conjuntos de elementos frecuentes: encuentre todos los conjuntos de elementos frecuentes con \(soporte\geq recuento\) predeterminado de \(min\_support\)
Generación de reglas: enumere todas las reglas de asociación de conjuntos de elementos frecuentes. Calcule el soporte y la confianza para todas las reglas. Elimine las reglas que no superen los umbrales \(min\_support\) y \(min\_confidence\).
La generación frecuente de conjuntos de elementos es el paso más costoso desde el punto de vista computacional porque requiere un análisis completo de la base de datos.
Entre los pasos anteriores, la generación de conjuntos de elementos frecuentes es la más costosa en términos de cálculo.
Anteriormente, ha visto el ejemplo de solo 5 transacciones, pero en el mundo real, los datos de transacciones para minoristas pueden exceder hasta GB y TB de datos para los cuales se necesita un algoritmo optimizado para eliminar conjuntos de elementos que no ayudarán en pasos posteriores.
Propiedad Apriori.
Si una celda dada no satisface el soporte mínimo, entonces ningún descendiente de la celda (es decir, una celda más especializada) tampoco satisfará el soporte mínimo. Es decir, cualquier subconjunto de un conjunto de elementos frecuentes también debe ser frecuente. En otras palabras, no se debe generar ni probar ningún subconjunto de un conjunto de elementos poco frecuente.
Conjunto de Artículos Lattice, es una representación gráfica del principio del algoritmo APRIORI. Consiste en el nodo de k-item-set y la relación de subconjuntos de ese k-item-set.
Se puede ver en la figura anterior que en la parte superior están todos los elementos en los datos de la transacción y luego comienza a moverse hacia abajo creando subconjuntos. Para \(d\) número de elementos, el tamaño se convertirá en \(2^d\). Esto muestra lo difícil que será generar un conjunto de elementos frecuentes al encontrar soporte para cada combinación.
Usando la propiedad apriori, si el conjunto de elementos \(\{a, b\}\) es poco frecuente, no es necesario tener en cuenta todos sus subconjuntos.
Uso de Software Estadístico
Para este ejemplo se trabajara con el siguiente conjunto de datos items.csv que contiene datos de transacciones.
Dado que el objetivo del presente trabajo, es mostrar el funcionamiento del software estadístico R, solo se han considerado los datos, respecto a las transacciones y artículos.
Librerías.
| Packcage | Descripción |
|---|---|
| arules | Proporciona la infraestructura para representar, manipular y analizar patrones y datos de transacciones (conjuntos de elementos frecuentes y reglas de asociación). |
| arulesViz | Extensión del paquete ‘arules’ con varias técnicas de visualización para reglas de asociación y conjuntos de elementos. El paquete también incluye varias visualizaciones interactivas para la exploración de reglas. |
Antes de aplicar los Frequent Itemset Mining Alghorithms, necesitamos convertir la base de datos en datos de tipo transacciones para que todos los artículos que se compran juntos en una factura estén en una fila.
Dependiendo de como se encuentren los datos originalmente serán necesarias diferentes técnicas para obtener el tipo de datos que buscamos, algunas funciones que puede ser utilez y facilitar este procedimiento son:
| Packcage | Función | Descripción |
|---|---|---|
| base | paste | Concatenar vectores después de convertirlos a carácter. |
| arules | read.transactions | Lee un archivo de datos de transacciones del disco y crea un objeto de tipo transacciones |
| methods | as | Coaccionar un objeto a una clase determinada |
A continuación Presentamos las primeras transacciones de nuestros datos.
Tr <- read.transactions(file = "Datos_Tienda.csv",
format = "single",
sep = ",",
header = TRUE,
cols = c("id_compra", "item"),
rm.duplicates = TRUE) items transactionID
[1] {Bolsas de Plastico,
Jugo de frutas y vegetales,
Leche entera,
Mantequilla,
Otros Vegetales,
Productos para el cuidados de mascotas,
Queso Crema,
Vinagre,
Yogurt} 2005Donde se observa que en esta transacción se compraron Bolsas de Plástico, Jugo de frutas y Vegetales, Leche entera, Mantequilla, Otros vegetales, Productos para el cuidado de mascotas, Queso Crema, Vinagre y Yogurt.
items transactionID
[1] {Bocadillos Salados,Productos de pasteleria} 2006 En cambio para esta transacción solo se compraron, Bocadillos Salados y Productos de pastelería.
itemFrequencyPlot, resulta útil visualizar los datos con los que se trabajan, resulta de interés estudiar con que frecuencia se compra cierto articulo, visualmente se tiene:
library(RColorBrewer)
itemFrequencyPlot(Tr,topN=20,type="absolute",col=brewer.pal(8,'Pastel2'), main="Absolute Item Frequency Plot")
Este gráfico muestra que Leche Entera y Otros Vegetales tiene el mayor numero de ventas.
Generación delas Reglas.
El siguiente paso es extraer las reglas utilizando el algoritmo APRIORI. La función apriori() es del paquete arules.
apriori() El algoritmo Apriori emplea una búsqueda por niveles para conjuntos de elementos frecuentes. La implementación utilizada de Apriori incluye algunas mejoras como, un árbol de prefijos y clasificación de elementos.
# Min Support as 0.001, confidence as 0.8.
association.rules <- apriori(Tr, parameter = list(supp=0.001, conf=0.8,maxlen=10))Apriori
Parameter specification:
confidence minval smax arem aval originalSupport maxtime support minlen
0.8 0.1 1 none FALSE TRUE 5 0.001 1
maxlen target ext
10 rules TRUE
Algorithmic control:
filter tree heap memopt load sort verbose
0.1 TRUE TRUE FALSE TRUE 2 TRUE
Absolute minimum support count: 2
set item appearances ...[0 item(s)] done [0.00s].
set transactions ...[165 item(s), 2306 transaction(s)] done [0.00s].
sorting and recoding items ... [157 item(s)] done [0.00s].
creating transaction tree ... done [0.00s].
checking subsets of size 1 2 3 4 5 6 7 8 done [0.01s].
writing ... [9395 rule(s)] done [0.00s].
creating S4 object ... done [0.00s].Apriori tomará Tr como el objeto de transacción en el que se aplicará la minería. El parámetro le permitirá establecer min_sup y min_confidence. Los valores predeterminados para el parámetro son soporte mínimo de 0.1, la confianza mínima de 0.8, máximo de 10 elementos (maxlen).
summary (association.rules) muestra lo siguiente:
set of 9395 rules
rule length distribution (lhs + rhs):sizes
2 3 4 5 6 7 8
1 603 3529 3549 1390 291 32
Min. 1st Qu. Median Mean 3rd Qu. Max.
2.000 4.000 5.000 4.716 5.000 8.000
summary of quality measures:
support confidence coverage lift
Min. :0.001301 Min. :0.8000 Min. :0.001301 Min. : 3.197
1st Qu.:0.001301 1st Qu.:1.0000 1st Qu.:0.001301 1st Qu.: 4.136
Median :0.001301 Median :1.0000 Median :0.001301 Median : 5.490
Mean :0.001463 Mean :0.9719 Mean :0.001530 Mean : 10.044
3rd Qu.:0.001735 3rd Qu.:1.0000 3rd Qu.:0.001735 3rd Qu.: 12.201
Max. :0.006938 Max. :1.0000 Max. :0.008673 Max. :192.167
count
Min. : 3.000
1st Qu.: 3.000
Median : 3.000
Mean : 3.373
3rd Qu.: 4.000
Max. :16.000
mining info:
data ntransactions support confidence
Tr 2306 0.001 0.8Especificación de parámetro: min_sup = 0.001 y min_confidence = 0.8 valores con 10 elementos como máximo de elementos en una regla.
Total number of rules: el conjunto de 9395 reglas
Número total de reglas: una longitud de 5 elementos tiene la mayor cantidad de reglas: 3549 y la longitud de 2 elementos tiene la menor cantidad de reglas: 1
Resumen de medidas de calidad: valores mínimos y máximos de soporte, confianza y elevación.
Información utilizada para crear reglas: los datos, el soporte y la confianza que proporcionamos al algoritmo.
Dado que hay 9395 reglas, se muestran a continuación solo las 10 principales:
lhs rhs support confidence coverage lift count
[1] {Frutas Congeladas} => {Otros Vegetales} 0.001300954 1 0.001300954 5.170404 3
[2] {Chocolate para cocinar,
Levadura} => {Mantequilla} 0.001300954 1 0.001300954 17.875969 3
[3] {Chocolate para cocinar,
Mantequilla} => {Levadura} 0.001300954 1 0.001300954 44.346154 3
[4] {Chocolate para cocinar,
Levadura} => {Otros Vegetales} 0.001300954 1 0.001300954 5.170404 3
[5] {Chocolate para cocinar,
Otros Vegetales} => {Levadura} 0.001300954 1 0.001300954 44.346154 3
[6] {Chocolate para cocinar,
Levadura} => {Leche entera} 0.001300954 1 0.001300954 3.996534 3
[7] {Chocolate para cocinar,
Leche entera} => {Levadura} 0.001300954 1 0.001300954 44.346154 3
[8] {Chocolate para cocinar,
Mantequilla} => {Otros Vegetales} 0.001300954 1 0.001300954 5.170404 3
[9] {Chocolate para cocinar,
Otros Vegetales} => {Mantequilla} 0.001300954 1 0.001300954 17.875969 3
[10] {Chocolate para cocinar,
Mantequilla} => {Leche entera} 0.001300954 1 0.001300954 3.996534 3El resultado anterior se puede interpretar de la siguiente manera:
El 100% de los clientes que compraron ‘Frutas Congeladas’ también compraron ‘Otros Vegetales’.
El 100% de los clientes que compraron ‘Chocolate para cocinar,Levadura’ también compraron ‘Mantequilla’.
Encontrar reglas relacionadas con elementos dados.
A veces, se desea trabajar en un producto específico. Si se desea averiguar qué causa la influencia en la compra del artículo X, puede usar la opción de apariencia en el comando apriori. La apariencia nos da opciones para establecer LHS (parte SI) y RHS (parte ENTONCES) de la regla.
Por ejemplo, para encontrar lo que compran los clientes antes de comprar ‘Refrescos’, se tiene
Apriori
Parameter specification:
confidence minval smax arem aval originalSupport maxtime support minlen
0.8 0.1 1 none FALSE TRUE 5 0.001 1
maxlen target ext
10 rules TRUE
Algorithmic control:
filter tree heap memopt load sort verbose
0.1 TRUE TRUE FALSE TRUE 2 TRUE
Absolute minimum support count: 2
set item appearances ...[1 item(s)] done [0.00s].
set transactions ...[165 item(s), 2306 transaction(s)] done [0.00s].
sorting and recoding items ... [157 item(s)] done [0.00s].
creating transaction tree ... done [0.00s].
checking subsets of size 1 2 3 4 5 6 7 8 done [0.01s].
writing ... [270 rule(s)] done [0.00s].
creating S4 object ... done [0.00s]. lhs rhs support confidence coverage lift count
[1] {Pan de Higado,
Productos de pasteleria} => {Refrescos} 0.001300954 1.0 0.001300954 5.375291 3
[2] {Cerveza Embotellada,
Leche Condensada} => {Refrescos} 0.001300954 1.0 0.001300954 5.375291 3
[3] {Agua Embotellada,
Leche Condensada} => {Refrescos} 0.001300954 1.0 0.001300954 5.375291 3
[4] {Servilletas,
Vinagre} => {Refrescos} 0.001300954 1.0 0.001300954 5.375291 3
[5] {Comida Instantanea,
Periodico} => {Refrescos} 0.001734605 0.8 0.002168257 4.300233 4
[6] {Chocolate de especialidad,
Productos Terminados} => {Refrescos} 0.001300954 1.0 0.001300954 5.375291 3El resultado anterior se puede interpretar de la siguiente manera:
[5] El 80% de los clientes que compraron ‘Comida Instantanea,Periodico’ también compraron ‘Refrescos’.
De manera similir para X como la causa, se tiene: Considerando ‘Frutas Congeladas’
Apriori
Parameter specification:
confidence minval smax arem aval originalSupport maxtime support minlen
0.8 0.1 1 none FALSE TRUE 5 0.001 1
maxlen target ext
10 rules TRUE
Algorithmic control:
filter tree heap memopt load sort verbose
0.1 TRUE TRUE FALSE TRUE 2 TRUE
Absolute minimum support count: 2
set item appearances ...[1 item(s)] done [0.00s].
set transactions ...[165 item(s), 2306 transaction(s)] done [0.00s].
sorting and recoding items ... [157 item(s)] done [0.00s].
creating transaction tree ... done [0.00s].
checking subsets of size 1 2 done [0.00s].
writing ... [1 rule(s)] done [0.00s].
creating S4 object ... done [0.00s]. lhs rhs support confidence coverage
[1] {Frutas Congeladas} => {Otros Vegetales} 0.001300954 1 0.001300954
lift count
[1] 5.170404 3 Visualización de reglas de asociación
Las técnicas basadas en gráficos visualizan reglas de asociación utilizando vértices y aristas donde los vértices se etiquetan con nombres de elementos y los conjuntos de elementos o reglas se representan como un segundo conjunto de vértices. Los elementos se conectan con conjuntos de elementos / reglas mediante flechas dirigidas. Las flechas que apuntan de los elementos a los vértices de las reglas indican los elementos LHS y una flecha de una regla a un elemento indica el RHS. El tamaño y el color de los vértices a menudo representan medidas de interés.
Los diagramas de gráficos son una excelente manera de visualizar reglas, pero tienden a congestionarse a medida que aumenta el número de reglas. Por lo tanto, es mejor visualizar una menor cantidad de reglas con visualizaciones basadas en gráficos.
Eclat ((Equivalence Class Transformation)
Este algoritmo utiliza operaciones de intersección simples para la agrupación de clases de equivalencia junto con un recorrido de Lettice ascendente.
Generación delas Reglas.
El siguiente paso es extraer las reglas utilizando el algoritmo APRIORI. La función eclat() es del paquete arules.
# Min Support as 0.001, confidence as 0.8.
eclat.rules <- apriori(Tr, parameter = list(supp=0.001, conf=0.8,maxlen=10))Apriori
Parameter specification:
confidence minval smax arem aval originalSupport maxtime support minlen
0.8 0.1 1 none FALSE TRUE 5 0.001 1
maxlen target ext
10 rules TRUE
Algorithmic control:
filter tree heap memopt load sort verbose
0.1 TRUE TRUE FALSE TRUE 2 TRUE
Absolute minimum support count: 2
set item appearances ...[0 item(s)] done [0.00s].
set transactions ...[165 item(s), 2306 transaction(s)] done [0.00s].
sorting and recoding items ... [157 item(s)] done [0.00s].
creating transaction tree ... done [0.00s].
checking subsets of size 1 2 3 4 5 6 7 8 done [0.01s].
writing ... [9395 rule(s)] done [0.00s].
creating S4 object ... done [0.00s].Eclat tomará Tr como el objeto de transacción en el que se aplicará la minería. El parámetro le permitirá establecer min_sup y min_confidence. Los valores predeterminados para el parámetro son soporte mínimo de 0.1, la confianza mínima de 0.8, máximo de 10 elementos (maxlen).
summary (eclat.rules) muestra lo siguiente:
set of 9395 rules
rule length distribution (lhs + rhs):sizes
2 3 4 5 6 7 8
1 603 3529 3549 1390 291 32
Min. 1st Qu. Median Mean 3rd Qu. Max.
2.000 4.000 5.000 4.716 5.000 8.000
summary of quality measures:
support confidence coverage lift
Min. :0.001301 Min. :0.8000 Min. :0.001301 Min. : 3.197
1st Qu.:0.001301 1st Qu.:1.0000 1st Qu.:0.001301 1st Qu.: 4.136
Median :0.001301 Median :1.0000 Median :0.001301 Median : 5.490
Mean :0.001463 Mean :0.9719 Mean :0.001530 Mean : 10.044
3rd Qu.:0.001735 3rd Qu.:1.0000 3rd Qu.:0.001735 3rd Qu.: 12.201
Max. :0.006938 Max. :1.0000 Max. :0.008673 Max. :192.167
count
Min. : 3.000
1st Qu.: 3.000
Median : 3.000
Mean : 3.373
3rd Qu.: 4.000
Max. :16.000
mining info:
data ntransactions support confidence
Tr 2306 0.001 0.8Especificación de parámetro: min_sup = 0.001 y min_confidence = 0.8 valores con 10 elementos como máximo de elementos en una regla.
Total number of rules: el conjunto de 9395 reglas
Número total de reglas: una longitud de 5 elementos tiene la mayor cantidad de reglas: 3549 y la longitud de 2 elementos tiene la menor cantidad de reglas: 1
Resumen de medidas de calidad: valores mínimos y máximos de soporte, confianza y elevación.
Información utilizada para crear reglas: los datos, el soporte y la confianza que proporcionamos al algoritmo.
Dado que hay 9395 reglas, se muestran a continuación solo las 10 principales:
lhs rhs support confidence coverage lift count
[1] {Frutas Congeladas} => {Otros Vegetales} 0.001300954 1 0.001300954 5.170404 3
[2] {Chocolate para cocinar,
Levadura} => {Mantequilla} 0.001300954 1 0.001300954 17.875969 3
[3] {Chocolate para cocinar,
Mantequilla} => {Levadura} 0.001300954 1 0.001300954 44.346154 3
[4] {Chocolate para cocinar,
Levadura} => {Otros Vegetales} 0.001300954 1 0.001300954 5.170404 3
[5] {Chocolate para cocinar,
Otros Vegetales} => {Levadura} 0.001300954 1 0.001300954 44.346154 3
[6] {Chocolate para cocinar,
Levadura} => {Leche entera} 0.001300954 1 0.001300954 3.996534 3
[7] {Chocolate para cocinar,
Leche entera} => {Levadura} 0.001300954 1 0.001300954 44.346154 3
[8] {Chocolate para cocinar,
Mantequilla} => {Otros Vegetales} 0.001300954 1 0.001300954 5.170404 3
[9] {Chocolate para cocinar,
Otros Vegetales} => {Mantequilla} 0.001300954 1 0.001300954 17.875969 3
[10] {Chocolate para cocinar,
Mantequilla} => {Leche entera} 0.001300954 1 0.001300954 3.996534 3El resultado anterior se puede interpretar de la siguiente manera:
El 100% de los clientes que compraron ‘Frutas Congeladas’ también compraron ‘Otros Vegetales’.
El 100% de los clientes que compraron ‘Chocolate para cocinar,Levadura’ también compraron ‘Mantequilla’.
Conclusiones
Al analizar los dos métodos tanto el Apriori como el Eclat, aunque sus estructuras son diferentes para generar reglas de asociación, se pudo observar que ambos métodos generaron exactamente las mismas reglas, dado el soporte mínimo y la confianza.
Finalmente, se podría utilizar cualquier de los métodos ya que tienen resultados similares, sin embargo el apriori es el mas utilizado al momento de establecer transacciones frecuentes y reglas de asociación.