El algoritmo de Reglas de Asociacion encuentra todos los conjuntos de elementos (itemsets) que poseen un soporte mayor que el minimo, luego utiliza los itemsets mas grandes para generar las reglas deseadas que tengan una confianza mayor a la minima. El concepto de “lift” de una regla es la tasa de soporte observada sobre la esperada si X e Y fueran independientes. Uno de los ejemplos mas ampliamente utilizados para la utilizacion de reglas de asociacion es para el analisis de Market Basket.
Ejemplo:
Algoritmo AIS
- Los conjuntos de elementos (itemset) encontrados se generan y cuentan en tiempo real mientras se lee la base de datos.
- Para cada nueva transaccion, se determina cual de los principales (mayores) conjuntos anteriormente generados ya contienen a esta transaccion.
- Los conjuntos candidatos se generan extendiendo a los principales conjuntos utilizando los elementos de esa transaccion.
La desventaja del algoritmo AIS es que termina generando y contando innecesariamente demasiados conjuntos candidatos que terminan siendo demasiado pequeños.
Algoritmo SETM
- Los conjuntos de elementos se generan en el momento mientras se procesa la base de datos, pero se cuentan al finalizar la pasada.
- Los nuevos conjuntos se generan de igual forma que el algoritmo AIS, pero el TID de la transaccion generada se guarda junto con el conjunto candidato en una estructura secuencial.
- Al finalizar la pasada de la base de datos, se sumariza esta estructura secuencial para obtener el valor de soporte para cada conjunto candidato.
El algoritmo SETM tiene la misma desventaja que el AIS. Pero suma una desventaja mas que es que para cada conjunto candidato, hay tantas entradas como su valor de soporte.
Algoritmo Apriori
- Se generan conjuntos candidatos utilizando solo los conjuntos principales de las pasadas previas, sin considerar las transacciones en la base de datos.
- Estos conjuntos grandes de los pases previos se unen consigo mismos para generar conjuntos con un tamaño por lo menos 1 mayor.
- Cada conjunto generado que tiene un subconjunto insuficientemente grande, se elimina. Los conjuntos que quedan se convierten en candidatos.
El algoritmo Apriori toma ventaja del hecho de que cualquier subconjunto de un conjunto frecuente, es si mismo a la vez un conjunto frecuente. El algoritmo puede, entonces, reducir el numero de candidatos a considerar al explorar solamente los conjuntos cuyo valor de soporte sea mayor que el valor minimo de soporte. Todos los conjuntos poco frecuentes se pueden eliminar si contienen un subconjunto poco frecuente.
Algoritmo AprioriTID
- La base de datos no se utiliza para contar el soporte de los conjuntos candidatos luego de la primer pasada.
- Los conjuntos candidatos se generan igual que con el algoritmo Apriori
- Se genera un conjunto C’ del cual cada miembro tiene el TID de cada transaccion y de los conjuntos principales presentes en esa transaccion. Este conjunto C’ se utiliza para contar el soporte de cada conjunto candidato.
La ventaja es que la cantidad de entradas en C’ puede ser menor que la cantidad de transacciones en la base de datos, especialmente cuanto mas avanza el procesamiento.
Algoritmo AprioriHibrido
Apriori es mejor que AprioriTID al inicio. Sin embargo AprioriTID es mas eficiente que Apriori hacia el final. Por lo tanto se puede diseñar un algoritmo hibrido que utilice Apriori en los inicios y luego cambie a AprioriTID cuando se espere que el conjunto C’ ya pueda caber en la memoria.