Conceptos básicos

En análisis de reglas de asociación (Association Rules) y de conjuntos de objetos frecuentes (Frequent Itemset Analysis) tenemos distintos conceptos relevantes. Tomemos como ejemplo los datos de compras en un supermercado.

Ojo que una regla de asociación no es una implicancia lógica. Es decir, no necesariamente existe una relación de causalidad entre \(X\) e \(Y\), sino que de co-ocurrencia.

Existen distintas medidas de interés sobre itemsets y reglas. Entre las más importantes, están support, confidence, y lift:

\[\sigma(X) = \text{# de veces que aparece }X \text{ en el dataset}\] \[\text{support}(X \rightarrow Y) = \frac{\sigma(X \cup Y)}{N}\] \[\text{confidence}(X \rightarrow Y) = \frac{\text{support}(X\rightarrow Y)}{\text{support}(X)} = \frac{\sigma(X \cup Y)}{\sigma(X)}\] \[\text{lift}(X\rightarrow Y) = \frac{\text{confidence}(X\rightarrow Y)}{\text{support}(Y)}\]

Donde \(N\) es la cantidad de transacciones (el tamaño del dataset).

Si el dataset es muy grande, es posible interpretar estas medidas de interés como probabilidades:

\[\text{support}(X \rightarrow Y) = P(X, Y)\] \[\text{confidence}(X \rightarrow Y) = P(Y|X)\] \[\text{lift}(X\rightarrow Y) = \frac{P(X, Y)}{P(X)P(Y)}\]

Donde \(P(X)\) es la probabilidad de \(X\), \(P(X, Y)\) es la probabilidad de \(X\) e \(Y\), y \(P(Y|X)\) es la probabilidad de \(Y\) dado \(X\).

Usualmente, el objetivo es encontrar reglas de asociación interesantes a partir del dataset de transacciones. Para esto, uno define umbrales (thresholds) de soporte, confianza, lift, etc. y trata de generar reglas cuya medida de interés sea \(\geq\) cada uno de estos umbrales. Por ejemplo, podemos buscar reglas con minSup = 0.05 y minConf = 0.1.

Reglas de asociación en R

Partimos cargando las librerías arules y arulesViz, y el dataset de compras de supermercado:

# En R instale las librerías `arules` y `arulesViz`

# arules:
# install.packages('arules')

# Esta es opcional:
# install.packages('arulesViz')

library("tidyverse")
library("arules")
data(Groceries)
# ahora Groceries está disponible como una variable en el entorno de R

Para observar las primeras 6 transacciones, usamos el comando inspect sobre head:

inspect(head(Groceries))
##     items                     
## [1] {citrus fruit,            
##      semi-finished bread,     
##      margarine,               
##      ready soups}             
## [2] {tropical fruit,          
##      yogurt,                  
##      coffee}                  
## [3] {whole milk}              
## [4] {pip fruit,               
##      yogurt,                  
##      cream cheese ,           
##      meat spreads}            
## [5] {other vegetables,        
##      whole milk,              
##      condensed milk,          
##      long life bakery product}
## [6] {whole milk,              
##      butter,                  
##      yogurt,                  
##      rice,                    
##      abrasive cleaner}
summary(Groceries)
## transactions as itemMatrix in sparse format with
##  9835 rows (elements/itemsets/transactions) and
##  169 columns (items) and a density of 0.02609146 
## 
## most frequent items:
##       whole milk other vegetables       rolls/buns             soda 
##             2513             1903             1809             1715 
##           yogurt          (Other) 
##             1372            34055 
## 
## element (itemset/transaction) length distribution:
## sizes
##    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15 
## 2159 1643 1299 1005  855  645  545  438  350  246  182  117   78   77   55 
##   16   17   18   19   20   21   22   23   24   26   27   28   29   32 
##   46   29   14   14    9   11    4    6    1    1    1    1    3    1 
## 
##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##   1.000   2.000   3.000   4.409   6.000  32.000 
## 
## includes extended item information - examples:
##        labels  level2           level1
## 1 frankfurter sausage meat and sausage
## 2     sausage sausage meat and sausage
## 3  liver loaf sausage meat and sausage

Con el algoritmo eclat determinamos los itemsets más frecuentes:

# usamos soporte mínimo 0.07
frequentItems <- eclat(Groceries, parameter = list(supp = 0.07))
## Eclat
## 
## parameter specification:
##  tidLists support minlen maxlen            target   ext
##     FALSE    0.07      1     10 frequent itemsets FALSE
## 
## algorithmic control:
##  sparse sort verbose
##       7   -2    TRUE
## 
## Absolute minimum support count: 688 
## 
## create itemset ... 
## set transactions ...[169 item(s), 9835 transaction(s)] done [0.00s].
## sorting and recoding items ... [18 item(s)] done [0.00s].
## creating sparse bit matrix ... [18 row(s), 9835 column(s)] done [0.00s].
## writing  ... [19 set(s)] done [0.00s].
## Creating S4 object  ... done [0.00s].
items.sorted <- sort(frequentItems, by="support")
inspect(items.sorted)
##      items                         support    count
## [1]  {whole milk}                  0.25551601 2513 
## [2]  {other vegetables}            0.19349263 1903 
## [3]  {rolls/buns}                  0.18393493 1809 
## [4]  {soda}                        0.17437722 1715 
## [5]  {yogurt}                      0.13950178 1372 
## [6]  {bottled water}               0.11052364 1087 
## [7]  {root vegetables}             0.10899847 1072 
## [8]  {tropical fruit}              0.10493137 1032 
## [9]  {shopping bags}               0.09852567  969 
## [10] {sausage}                     0.09395018  924 
## [11] {pastry}                      0.08896797  875 
## [12] {citrus fruit}                0.08276563  814 
## [13] {bottled beer}                0.08052872  792 
## [14] {newspapers}                  0.07981698  785 
## [15] {canned beer}                 0.07768175  764 
## [16] {pip fruit}                   0.07564820  744 
## [17] {other vegetables,whole milk} 0.07483477  736 
## [18] {fruit/vegetable juice}       0.07229283  711 
## [19] {whipped/sour cream}          0.07168277  705

Veamos estos datos en un gráfico de barras, convirtiendo el objeto items.sorted en un data.frame o tibble:

df <- as(items.sorted, "data.frame")
as.tibble(df) %>%
  ggplot(mapping = aes(x = reorder(items, support), y = support)) + geom_bar(stat = "identity") + coord_flip()

arules ya dispone de algunos métodos que hacen lo mismo:

itemFrequencyPlot(Groceries, topN=10, type="absolute", main="Item Frequency")

Para generar reglas de asociación usamos el algoritmo Apriori implementado en la librería arules:

rules <- apriori(Groceries, parameter=list(support=0.001, confidence=0.5))
## Apriori
## 
## Parameter specification:
##  confidence minval smax arem  aval originalSupport maxtime support minlen
##         0.5    0.1    1 none FALSE            TRUE       5   0.001      1
##  maxlen target   ext
##      10  rules FALSE
## 
## Algorithmic control:
##  filter tree heap memopt load sort verbose
##     0.1 TRUE TRUE  FALSE TRUE    2    TRUE
## 
## Absolute minimum support count: 9 
## 
## set item appearances ...[0 item(s)] done [0.00s].
## set transactions ...[169 item(s), 9835 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 done [0.01s].
## writing ... [5668 rule(s)] done [0.00s].
## creating S4 object  ... done [0.00s].
inspect(head(sort(rules, by="lift"), 3))
##     lhs                             rhs              support    
## [1] {Instant food products,soda} => {hamburger meat} 0.001220132
## [2] {soda,popcorn}               => {salty snack}    0.001220132
## [3] {flour,baking powder}        => {sugar}          0.001016777
##     confidence lift     count
## [1] 0.6315789  18.99565 12   
## [2] 0.6315789  16.69779 12   
## [3] 0.5555556  16.40807 10

Podemos observar que la regla con mayor lift (cuyas asociaciones son más fuertes) es aquella que dice: cada vez que se compran productos de comida rápida y soda, entonces se compra también carne para hamburguesas. Note, sin embargo, que esto se produce sólo en un 0.1% de todas las transacciones del dataset (support).

Es claro que no es viable analizar manualmente las 5668 reglas generadas. Para esto, usamos métodos de visualización provistos por arulesViz:

library("arulesViz")
plot(rules)

De no estar disponible arulesViz, también podemos hacer gráficos similares usando lo que ya hemos visto:

df <- as(rules, 'data.frame')
tbl <- as.tibble(df)

tbl %>%
  ggplot(mapping = aes(x = support, y = confidence, color = lift, size = count)) + geom_jitter(alpha = 0.5)

tbl %>% filter(support > 0.02)
## Warning: package 'bindrcpp' was built under R version 3.4.4
tbl %>% filter(confidence == 1)

Con este gráfico es posible observar que las reglas más interesantes (basadas en el lift) tienen bajo soporte.

Otra forma de visualizar las reglas de asociación es usando un gráfico de matriz agrupada. Éste muestra en una matriz un círculo indicando algunas medidas de interés; en las columnas se muestra el lado derecho de una regla, mientras que en las filas se muestra el lado izquierdo. Los itemsets mostrados corresponden a los grupos de itemsets más similares entre sí.

Acá se usa como medida de similitud la distancia de Jaccard para comparar la cantidad de elementos en común entre dos itemsets. La distancia de Jaccard entre dos conjuntos \(X\) e \(Y\) se define de la siguiente forma:

\[d(X, Y) = \frac{|X \cap Y|}{|X \cup Y|}\]

plot(rules, method="grouped")

El color de cada círculo representa el lift, mientras que el tamaño representa el support. Es posible observar que la regla más fuerte que vimos recién se muestra en la esquina superior izquierda.

Otra forma de visualizar es usando grafos (redes de conexiones entre nodos o vértices mediante arcos o aristas). Usualmente, los vértices representan items o itemsets, y las aristas representan relaciones entre las reglas. La desventaja de este tipo de visualización es que se satura fácilmente con muchos datos (clutter). Para los siguientes gráficos vamos a usar las 10 reglas con mayor lift. Para conjuntos de reglas más grandes, es necesario usar herramientas interactivas, que permitan inspeccionar ciertas zonas del grafo, filtrar, etc. (como Gephi).

subrules <- head(sort(rules, by="lift"), 20)
plot(subrules, method="graph", engine = "htmlwidget")

Con ggplot y dplyr podemos buscar los patrones que queramos, como por ejemplo, ¿cuáles itemsets “predicen” mejor la compra de mantequilla (butter)?

tbl
# lhs: "left hand side"
# rhs: "right hand side"
# lhs => rhs

tbl %>%
  separate(rules, into = c("lhs", "rhs"), sep = " => ") %>%
  filter(rhs == "{butter}") %>%
  ggplot(aes(x = reorder(lhs, confidence), y = confidence, fill = support)) + geom_bar(stat = "identity") + coord_flip() +
  labs(x = "LHS", y = "Confidence", title = "Itemsets que predicen {butter}")

Laboratorio

Pregunta 1

Explique con sus palabras qué significa que la regla {rice, sugar} => {whole milk} tenga un confidence de 1. Explique con sus palabras qué significa que la regla {Instant food products, soda} => {hamburger meat} tenga un lift de 18.

Pregunta 2

Considere las siguientes transacciones:

{audifonos, smartphone}
{audifonos, smartphone}
...
{audifonos, smartphone}
{smartphone}
{smartphone}
.. 
{smartphone}

Donde la cantidad de transacciones {audifonos, smartphone} es igual a la cantidad de {smartphone}, es decir, ambas tienen el mismo support. De este dataset podemos inferir dos reglas:

{audifonos} => {smartphone}
{smartphone} => {audifonos}

Suponga que las transacciones corresponden a ventas en una tienda y que queremos determinar reglas de asociación para recomendar productos. Para esto, responda:

  1. ¿Cuál es el confidence de cada una de las reglas?
  2. ¿Cuál es el lift de cada una de las reglas?
  3. ¿Cuál de las dos reglas considera que es más útil para usar en una recomendación?

Pregunta 3

Describa tres observaciones sobre las reglas obtenidas con el dataset Groceries. Puede usar los gráficos que vimos más arriba, o generar gráficos nuevos modificando el código de este notebook.

Preguntas bonus

Pregunta 1

¿Cuántos itemsets del siguiente dataset tienen support \(\geq 0.5\)? Si exigimos como minimum support \(0.9\), ¿cuáles reglas de asociación tienen confidence 1?

Utilice la siguiente propiedad de los itemsets, llamada la monotonicidad de los itemsets (o también llamado principio Apriori) para contar y generar reglas rápidamente: Si un itemset es frecuente, entonces todos los subconjuntos de este itemset también son frecuentes.

{1}
{1, 2}
{1, 2, 3}
{1, 2, 3, 4}
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5, 6}
{1, 2, 3, 4, 5, 6, 7}
{1, 2, 3, 4, 5, 6, 7, 8}
{1, 2, 3, 4, 5, 6, 7, 8, 9}
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Pregunta 2

El coseno de dos vectores \(x\) e \(y\) se define como

\[\cos(x,y) = \frac{x \cdot y}{||x|| \cdot ||y||}\]

Donde \(x = (x_1, x_2, \ldots, x_d)\) e \(y = (y_1, y_2, \ldots, y_d)\), \(x\cdot y = \sum_{i=1}^d x_iy_i\), y \(||x|| = \sqrt{\sum_{i=1}^d x_i^2}\). En dos dimensiones (es decir, \(x = (x_1, x_2)\) y \(y=(y_1, y_2)\)), puede pensar en el coseno como el cálculo del coseno del ángulo de los dos lados de un tríangulo.

Adaptando esta fórmula a las reglas de asociación de la forma \(X\rightarrow Y\), tenemos que para \(x_i\) (siendo \(x_i\) la componente \(i\)-ésima del vector \(x\) en el ejemplo anterior), \(x_i = 1\) si es que la transacción \(t_i\) contiene a \(X\), y \(0\) si no. Lo mismo para \(y_i\) e \(Y\).

Expresado de otra forma:

\[\cos(X \rightarrow Y) = \frac{\text{support}(X\rightarrow Y)}{\sqrt{\text{support}(X)\text{support}(Y)}}\]

Describa en palabras qué significa esta fórmula para una regla cualquiera \(X \rightarrow Y\). ¿Qué valores toma el coseno de una regla?

Referencias

  1. Data Mining Algorithms In R/Frequent Pattern Mining/The Apriori Algorithm. https://en.wikibooks.org/wiki/Data_Mining_Algorithms_In_R/Frequent_Pattern_Mining/The_Apriori_Algorithm
  2. Tan, Steinbach, Kumar, Introduction to Data Mining, chapter 6: Association Analysis: Basic Concepts and Algorithms. http://www-users.cs.umn.edu/~kumar/dmbook/ch6.pdf
  3. Yanchang Zhao, Association Rule Mining with R. http://www.rdatamining.com/docs/association-rule-mining-with-r
  4. Michael Hahsler, A Probabilistic Comparison of Commonly Used Interest Measures for Association Rules, 2015. http://michael.hahsler.net/research/association_rules/measures.html
  5. Michael Hahsler, Sudheer Chelluboina, Visualizing Association Rules: Introduction to the R-extension Package arulesViz. https://cran.r-project.org/web/packages/arulesViz/vignettes/arulesViz.pdf
  6. Merceron, Yacef, Interestingness Measures for Association Rules in Educational Data. http://www.educationaldatamining.org/EDM2008/uploads/proc/6_Yacef_18.pdf
  7. Leskovec, Rajaraman, Ullman, Mining of Massive Datasets. http://infolab.stanford.edu/~ullman/mmds/ch6.pdf