Fundamentos de Reglas de Asociación y Funcionamiento del Algoritmo Apriori

Métricas de Evaluación: Soporte y Confianza

• Confianza de una regla, confianza(B → C): es la proporción de transacciones en las cuales ocurre C dado que ocurrió B.
  Confianza(B → C) = Soporte(B, C) / Soporte(B).
• El soporte y la confianza miden, en conjunto, la importancia de una regla y, por ende, el grado de utilidad de la misma. De hecho, de todas las posibles reglas que se pueden extraer de una matriz de datos, solo se utilizan aquellas cuyo soporte y confianza superen ciertos valores mínimos.

Funcionamiento del Algoritmo Apriori

Dada una matriz de datos con n transacciones y p atributos, y suponiendo que el soporte mínimo es igual a M, y que la confianza mínima es igual a R, el procedimiento para extraer las reglas de asociación es el siguiente:

1. Obtener C₁, que es la lista de todos los atributos con soporte ≥ M.
2. L₁ = C₁.
3. i = 1.
4. Repetir hasta que (C_i = L_i = ∅) ó (i = p):
   • 4.1 i = i + 1.
   • 4.2 Obtener C_i combinando los itemsets de L_i-1. La unión de cada par de itemsets de L_i-1 genera un nuevo itemset. Si este nuevo itemset tiene un tamaño igual a i, entonces se incluye en C_i.
   • 4.3 Obtener L_i, que es un subconjunto de la lista C_i, de la cual se retienen solo a los itemsets cuyo soporte es ≥ M.
   Fin del repita hasta.
5. Cada elemento de L_i (i ≥ 2) genera varias reglas de asociación, pero solo se van a aceptar a aquellas que posean una confianza ≥ R.

Conceptos de Reglas de Asociación

Las reglas de asociación representan patrones o tendencias de comportamiento en matrices de datos compuestas únicamente por variables binarias. También pueden ser consideradas como medidas de la relación entre las variables de una matriz de datos (X), cuando esta está formada solo por variables dicotómicas.

Definiciones Fundamentales

• Sea A = {A₁, A₂, …, A_p} el conjunto de todos los posibles artículos (atributos).
• A todo subconjunto de A se le llama itemset.
• Sea T = {t₁, t₂, …, t_n} el conjunto de todas las transacciones almacenadas en la base de datos.
• Cada transacción en T contiene un identificador único y un subconjunto de elementos de A.
• Una regla de asociación se define formalmente como una implicación de la forma B → C, donde B y C son dos itemsets denominados el antecedente y el consecuente, respectivamente, de manera que B implica C. Estos itemsets deben cumplir las siguientes condiciones:
  • Esto significa, simplemente, que B y C son no vacíos, y que un mismo artículo (o atributo) no puede figurar simultáneamente en ambos itemsets.
• Soporte de un itemset X, soporte(X): es la proporción de las transacciones que contienen al itemset X. Suponiendo que K transacciones contienen al itemset X, entonces Soporte(X) = K/n.