Modelo de Reglas de Asociación

Las reglas de asociación introducen incertidumbre (probabilidades) a las reglas de los Sistemas Basados en Reglas.

Las asociaciones son relaciones de co-ocurrencia entre elementos:

$\underset{(X)}{\mathrm{Queso}}⟶\underset{(Y)}{\mathrm{Cerveza}}[\text{Soporte}10\%,\text{Confianza}80\%]$

Donde:

• El soporte representa el porcentaje de transacciones en $T$ que contienen $X\cup Y$. Mide la frecuencia de la regla.
• La confianza representa el porcentaje de transacciones en $T$ que contienen $X$ e $Y$. Mide la predictibilidad de la regla.

El conteo de soporte de $X$ es $X.count$.

$$\text{Soporte}=\frac{X\cup Y).count}{n}\text{Confianza}=\frac{(X\cup Y).count}{X.count}=Pr(Y|X)$$

El objetivo es, dado un conjunto de transacciones $T$, encontrar todas las reglas de asociación en en $T$ cuyos valores de soporte y confianza sean iguales o mayores a los establecidos por el usuario.

El problema está en encontrar todas las reglas. Existen varios algoritmos para esto, y todos dan el mismo conjunto de reglas.

Algoritmo A Priori

Este algoritmo trabaja en dos pasos:

1. Crear el conjunto de items frecuentes, es decir filtrados por soporte mínimo.
2. Generar todas las reglas de asociación confiables, es decir filtradas por la confianza mínima.

Se asume que los items en $I$ están ordenados lexicográficamente. La propiedad de cierre hacia abajo (downward closure) dice que, si un itemset contiene soporte mínimo, entonces todos sus subconjuntos no vacíos también lo contienen. Esto poda un gran número de itemsets y hace eficiente al algoritmo.

El algoritmo puede funcionar con mucha cantidad de datos ya que solamente tiene en cuenta $k$ items en cada pasada (lo que se conoce como level-wise search).

$$\begin{array}{rl}& \text{Algorithm Apriori}(T)\\ & C_1\leftarrow \text{init-pass}(T);\\ & F_1\leftarrow \{f\mid f\in C_1,f.count/n\ge minsup\};\\ & \text{for }(k=2;F_{k-1}\ne \varnothing ;k++)\text{do}\\ & C_k\leftarrow \text{candidate-gen}(F_{k-1});\\ & \text{for each transaction}t\in T\text{do}\\ & \text{for each candidate}c\in C_k\text{do}\\ & \text{if }c\text{is contained in }t\text{then}\\ & c.count++;\text{// conteo de soporte}\\ & \text{endfor}\\ & \text{endfor}\\ & F_k\leftarrow \{c\in C_k\mid c.count/n\ge minsup\}\text{// filtrar por soporte mıˊnimo}\\ & \text{endfor}\\ & \text{return }F\leftarrow {\bigcup }_k{F}_k\end{array}$$ $$\begin{array}{rl}& \text{Function }\text{candidate-gen}(F_{k-1})\\ & C_k\leftarrow \varnothing \\ & \text{forall }{f}_1,f_2\in F_{k-1}\text{do}\text{// pares de itemsets frecuentes}\\ & \text{with }{f}_1=\{i_1,\dots ,i_{k-2},i_{k-1}\}\text{// que solo difieren en el uˊltimo item}\\ & \text{and }{f}_2=\{i_1,\dots ,i_{k-2},i_{k-1}^{\prime }\}\\ & \text{and }{i}_{k-1}<i_{k-1}^{\prime }\text{do}\text{// en orden lexicograˊfico}\\ & c\leftarrow \{i_1,\dots ,i_{k-1},i_{k-1}^{\prime }\};\text{// unir los dos itemsets}\\ & C_k\leftarrow C_k\cup \{c\};\text{// agregar el nuevo candidato}\\ & \text{for each }(k-1)\text{-subset }s\text{ of }c\text{do}\\ & \text{if }(s\notin F_{k-1})\text{then}\\ & \text{delete }c\text{ from }{C}_k;\text{// filtrar por cierre hacia abajo}\\ & \text{endfor}\\ & \text{endfor}\\ & \text{return }{C}_k\end{array}$$

Una vez generado el conjunto $F$ de todos los itemsets frecuentes filtrados por soporte mínimo, se generan todas las reglas de asociación confiables (filtradas por la confianza mínima).

$$\begin{array}{rl}& \text{Algorithm }\text{genRules}(F)\\ & \text{for each frequent }k\text{-itemset }{f}_k\in F,k\ge 2\text{do}\\ & \text{output every 1-item consequent rule of }{f}_k\\ & \text{with confidence }\ge minconf\text{// filtrar por confianza mıˊnima}\\ & \text{and support }\leftarrow f_k.count/n\\ & H_1\leftarrow \{\text{consequents of all 1-item consequent rules derived from }{f}_k\text{ above}\};\\ & \text{ap-genRules}(f_k,H_1);\\ & \text{endfor}\end{array}$$ $$\begin{array}{rl}& \text{Procedure }\text{ap-genRules}(f_k,H_m)//H_m\text{ es el conjunto de consecuentes de }m\text{-items}\\ & \text{if }(k>m+1)\wedge (H_m\ne \varnothing )\text{then}\\ & H_{m+1}\leftarrow \text{candidate-gen}(H_m);\\ & \text{for each }{h}_{m+1}\in H_{m+1}\text{do}\\ & conf\leftarrow f_k.count/(f_k-h_{m+1}).count;\\ & \text{if }(conf\ge minconf)\text{then}\text{// filtrar por confianza mıˊnima}\\ & \text{output the rule }(f_k-h_{m+1})\to h_{m+1}\\ & \text{with confidence }=conf\\ & \text{and support }=f_k.count/n\\ & \text{else}\\ & \text{delete }{h}_{m+1}\text{ from }{H}_{m+1};\\ & \text{endif}\\ & \text{endfor}\\ & ap\text{-}genRules(f_k,H_{m+1});\\ & \text{endif}\end{array}$$