Aprendizaje de reglas de asociación

El soporte es un indicador de con qué frecuencia aparece el conjunto de elementos en el conjunto de datos:

${\displaystyle {\text{support}}(A)=P(A)={\frac {({\text{number of transactions containing }}A)}{\text{ (total number of transactions)}}}}$

El soporte de una regla se define como:

${\displaystyle {\text{support}}(A\Rightarrow B)=P(A\cup B)={\frac {({\text{number of transactions containing }}A{\text{ and }}B)}{\text{ (total number of transactions)}}}}$

donde A y B son conjuntos de elementos separados que ocurren al mismo tiempo en una transacción. ^{[ 12 ]}

Utilizando la Tabla 2 como ejemplo, el conjunto de elementos${\displaystyle X=\{\mathrm {beer,diapers} \}}$tiene un soporte de 1/5=0,2 ya que ocurre en el 20% de todas las transacciones (1 de cada 5 transacciones). El argumento de soporte de X es un conjunto de precondiciones y, por lo tanto, se vuelve más restrictivo a medida que crece (en lugar de más inclusivo). ^{[ 13 ]}

Además, el conjunto de elementos${\displaystyle Y=\{\mathrm {milk,bread,butter} \}}$tiene un soporte de 1/5=0,2 ya que aparece en el 20% de todas las transacciones.

Al utilizar antecedentes y consecuentes, un analista de datos puede determinar la probabilidad de que varios artículos se compren juntos en comparación con el conjunto de datos completo. Por ejemplo, la Tabla 2 muestra que si se compra leche, entonces se compra pan tiene una probabilidad de 0,4 o 40%. Esto se debe a que en 2 de cada 5 transacciones, se compran tanto leche como pan. En conjuntos de datos pequeños como este ejemplo, es más difícil observar una correlación fuerte cuando hay pocas muestras, pero cuando el conjunto de datos crece, la probabilidad puede utilizarse para encontrar correlaciones entre dos o más productos en el ejemplo del supermercado.

Los umbrales mínimos de soporte son útiles para determinar qué conjuntos de elementos son preferidos o interesantes.

Si establecemos el umbral de soporte en ≥0,4 en la Tabla 3, entonces el${\displaystyle \{\mathrm {milk} \}\Rightarrow \{\mathrm {eggs} \}}$Se eliminaría ya que no cumplía con el umbral mínimo de 0,4. El umbral mínimo se utiliza para eliminar muestras cuando no hay suficiente respaldo o confianza para considerar la muestra como importante o interesante en el conjunto de datos.

Otra forma de encontrar muestras interesantes es calcular el valor de (soporte) × (confianza); esto permite al analista de datos identificar las muestras donde el soporte y la confianza son lo suficientemente altos como para destacarlas en el conjunto de datos e impulsar una revisión más detallada de la muestra para obtener más información sobre la conexión entre los elementos.

El soporte puede ser útil para encontrar la conexión entre productos en comparación con el conjunto de datos completo, mientras que la confianza analiza la conexión entre uno o más elementos y otro elemento. A continuación, se muestra una tabla que compara el soporte y el soporte multiplicado por la confianza, utilizando la información de la Tabla 4 para obtener los valores de confianza.

El soporte de X con respecto a T se define como la proporción de transacciones en el conjunto de datos que contiene el conjunto de ítems X. Denotando una transacción por${\displaystyle (i,t)}$donde i es el identificador único de la transacción y t es su conjunto de elementos, el soporte se puede escribir como:

${\displaystyle \mathrm {support\,of\,X} ={\frac {|\{(i,t)\in T:X\subseteq t\}|}{|T|}}}$

Esta notación se puede usar al definir conjuntos de datos más complejos, donde los elementos y los conjuntos de elementos pueden no ser tan sencillos como en nuestro ejemplo del supermercado. Otros ejemplos donde se puede usar esta notación son la búsqueda de grupos de mutaciones genéticas que actúan colectivamente para causar una enfermedad, la investigación del número de suscriptores que responden a ofertas de actualización y el descubrimiento de qué productos en una farmacia nunca se compran juntos. ^{[ 12 ]}

La confianza es el porcentaje de todas las transacciones que satisfacen ^X que también satisfacen Y. ^{[ 14} ]

Con respecto a T , el valor de confianza de una regla de asociación, a menudo denotado como${\displaystyle X\Rightarrow Y}$, es la proporción de transacciones que contienen tanto X como Y con respecto a la cantidad total de valores X presentes, donde X es el antecedente e Y es el consecuente.

La confianza también puede interpretarse como una estimación de la probabilidad condicional.${\displaystyle P(E_{Y}|E_{X})}$, la probabilidad de encontrar el lado derecho de la regla en transacciones bajo la condición de que estas transacciones también contengan el lado izquierdo. ^{[ 13 ] [ 15 ]}

Se suele representar de la siguiente manera:

${\displaystyle \mathrm {conf} (X\Rightarrow Y)=P(Y|X)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)}}={\frac {{\text{number of transactions containing }}X{\text{ and }}Y}{{\text{number of transactions containing }}X}}}$

La ecuación ilustra que la confianza se puede calcular calculando la coocurrencia de transacciones X e Y dentro del conjunto de datos en proporción a las transacciones que contienen solo X. Esto significa que el número de transacciones en X e Y se divide entre las que contienen solo X.

Por ejemplo, la Tabla 2 muestra la regla${\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \}}$que tiene confianza en${\displaystyle {\frac {1/5}{1/5}}={\frac {0.2}{0.2}}=1.0}$En el conjunto de datos, que indica que cada vez que un cliente compra mantequilla y pan, también compra leche. Este ejemplo en particular demuestra que la regla es correcta el 100% de las veces para transacciones que contienen tanto mantequilla como pan. La regla${\displaystyle \{\mathrm {fruit} \}\Rightarrow \{\mathrm {eggs} \}}$Sin embargo, tiene confianza en${\displaystyle {\frac {2/5}{3/5}}={\frac {0.4}{0.6}}=0.67}$Esto sugiere que se compran huevos el 67% de las veces que se compra fruta. En este conjunto de datos en particular, se compró fruta un total de 3 veces, y en dos de esas ocasiones se compraron huevos.

Para conjuntos de datos más grandes, un umbral mínimo, o un porcentaje de corte, para la confianza puede ser útil para determinar las relaciones entre los elementos. Al aplicar este método a algunos de los datos de la Tabla 2, se elimina la información que no cumple con los requisitos. La Tabla 4 muestra ejemplos de reglas de asociación donde el umbral mínimo de confianza es 0,5 (50%). Cualquier dato que no tenga una confianza de al menos 0,5 se omite. Generar umbrales permite que la asociación entre elementos se fortalezca a medida que se investigan más los datos, al enfatizar aquellos que coocurren con mayor frecuencia. La tabla utiliza la información de confianza de la Tabla 3 para implementar la columna Soporte × Confianza, donde se resalta la relación entre elementos a través de su confianza y soporte, en lugar de solo un concepto. Clasificar las reglas por Soporte × Confianza multiplica la confianza de una regla particular por su soporte y se implementa a menudo para una comprensión más profunda de la relación entre los elementos.

En general, utilizar la confianza en la minería de reglas de asociación es una excelente manera de comprender las relaciones entre los datos. Su mayor beneficio radica en resaltar la relación entre elementos específicos dentro del conjunto, ya que compara las coocurrencias de elementos con la ocurrencia total del antecedente en la regla específica. Sin embargo, la confianza no es el método óptimo para todos los conceptos en la minería de reglas de asociación. Su desventaja es que no ofrece múltiples perspectivas diferentes sobre las asociaciones. A diferencia del soporte, por ejemplo, la confianza no proporciona la perspectiva de las relaciones entre ciertos elementos en comparación con el conjunto de datos completo; así, mientras que "leche" y "pan", por ejemplo, pueden aparecer el 100% de las veces para la confianza, solo tienen un soporte de 0,4 (40%). Por ello, es importante considerar otros puntos de vista, como el Soporte × Confianza, en lugar de depender exclusivamente de un solo concepto para definir las relaciones.

La elevación de una regla se define como:

${\displaystyle \mathrm {lift} (X\Rightarrow Y)={\frac {\mathrm {supp} (X\cup Y)}{\mathrm {supp} (X)\times \mathrm {supp} (Y)}}}$

o la relación entre el apoyo observado y el esperado si X e Y fueran independientes .

Por ejemplo, la regla${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$tiene un ascensor de${\displaystyle {\frac {0.2}{0.4\times 0.4}}=1.25}$.

Si la regla tuviera un valor de elevación de 1, implicaría que la probabilidad de ocurrencia del antecedente y la del consecuente son independientes entre sí. Cuando dos eventos son independientes entre sí, no se puede derivar ninguna regla que los involucre.

Si el valor de elevación es > 1, eso nos permite saber hasta qué punto esos dos sucesos dependen uno del otro, y hace que esas reglas sean potencialmente útiles para predecir el consecuente en futuros conjuntos de datos.

Si el coeficiente de elevación es < 1, significa que los elementos son sustituibles entre sí. Esto implica que la presencia de un elemento tiene un efecto negativo sobre la presencia de otro, y viceversa.

El valor del lift radica en que considera tanto el soporte de la regla como el conjunto de datos general. ^{[ 13 ]}

La convicción de una regla se define como${\displaystyle \mathrm {conv} (X\Rightarrow Y)={\frac {1-\mathrm {supp} (Y)}{1-\mathrm {conf} (X\Rightarrow Y)}}}$. ^{[ 16 ]}

Por ejemplo, la regla${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$tiene una convicción de${\displaystyle {\frac {1-0.4}{1-0.5}}=1.2}$y puede interpretarse como la razón entre la frecuencia esperada de que X ocurra sin Y (es decir, la frecuencia con la que la regla hace una predicción incorrecta) si X e Y fueran independientes, dividida por la frecuencia observada de predicciones incorrectas. En este ejemplo, el valor de convicción de 1,2 muestra que la regla${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$Sería incorrecto un 20% más a menudo (1,2 veces más a menudo) si la asociación entre X e Y fuera puramente aleatoria.

Además de la confianza, se han propuesto otras medidas de interés para las reglas. Algunas medidas populares son:

• Con plena confianza ^{[ 17 ]}
• Fuerza colectiva ^{[ 18 ]}
• Apalancamiento ^{[ 19 ]}

^{Tan et al. [ 20 ]} y Hahsler ^{[ 21 ]} presentan y comparan varias medidas adicionales. La búsqueda de técnicas que puedan modelar el conocimiento previo del usuario (y el uso de estos modelos como medidas de interés) es actualmente una tendencia de investigación activa denominada "Interés Subjetivo".

El algoritmo Apriori fue presentado por R. Agrawal y R. Srikant en 1994 para la minería de conjuntos de elementos frecuentes y el aprendizaje de reglas de asociación. Su funcionamiento consiste en identificar los elementos individuales frecuentes en la base de datos y extenderlos a conjuntos de elementos cada vez mayores, siempre que estos conjuntos aparezcan con suficiente frecuencia. El nombre del algoritmo es Apriori porque utiliza el conocimiento previo de las propiedades de los conjuntos de elementos frecuentes.

Descripción general: Apriori utiliza un enfoque "de abajo hacia arriba", donde los subconjuntos frecuentes se extienden un elemento a la vez (un paso conocido como generación de candidatos ), y los grupos de candidatos se prueban con los datos. El algoritmo termina cuando no se encuentran más extensiones exitosas. Apriori utiliza una búsqueda en anchura y una estructura de árbol hash para contar eficientemente los conjuntos de elementos candidatos. Genera conjuntos de elementos candidatos de longitud a partir de conjuntos de elementos de longitud . Luego poda los candidatos que tienen un subpatrón poco frecuente. Según el lema de cierre descendente, el conjunto candidato contiene todos los conjuntos de elementos frecuentes de longitud . Después de eso, escanea la base de datos de transacciones para determinar los conjuntos de elementos frecuentes entre los candidatos.

Ejemplo: Supongamos que cada fila es una muestra de cáncer con una determinada combinación de mutaciones, identificadas por un carácter del alfabeto. Por ejemplo, una fila podría tener {a, c}, lo que significa que está afectada por las mutaciones 'a' y 'c'.

Ahora generaremos el conjunto de elementos frecuentes contando la cantidad de ocurrencias de cada carácter. Esto también se conoce como calcular los valores de soporte. Luego, reduciremos el conjunto de elementos seleccionando un umbral de soporte mínimo. Para esta pasada del algoritmo, elegiremos 3.

Dado que todos los valores de soporte son tres o superiores, no se realiza ninguna poda. El conjunto de elementos frecuentes es {a}, {b}, {c} y {d}. A continuación, repetiremos el proceso contando pares de mutaciones en el conjunto de entrada.

Ahora estableceremos nuestro valor mínimo de soporte en 4, de modo que solo quedarán {a, d} después de la poda. Luego, utilizaremos el conjunto de elementos frecuentes para crear combinaciones de tríos. Repetiremos el proceso contando las ocurrencias de tríos de mutaciones en el conjunto de entrada.

Dado que solo tenemos un elemento, el siguiente conjunto de combinaciones de cuartetos está vacío, por lo que el algoritmo se detendrá.

Ventajas y limitaciones:

Apriori tiene algunas limitaciones. La generación de candidatos puede resultar en conjuntos de candidatos grandes. Por ejemplo, un conjunto frecuente de 1 elemento con una frecuencia de 10^4 generará un conjunto de candidatos de 2 elementos con una frecuencia de 10^7. El algoritmo también necesita escanear la base de datos con frecuencia, específicamente n+1 escaneos, donde n es la longitud del patrón más largo. Apriori es más lento que el algoritmo Eclat. Sin embargo, Apriori tiene un buen rendimiento en comparación con Eclat cuando el conjunto de datos es grande. Esto se debe a que en el algoritmo Eclat, si el conjunto de datos es demasiado grande, las listas de identificadores de patrones (tid) se vuelven demasiado grandes para la memoria. FP-growth supera a Apriori y Eclat. Esto se debe a que el algoritmo FP-growth no tiene generación de candidatos ni prueba, utiliza una estructura de datos compacta y solo tiene un escaneo de la base de datos. ^{[ 27 ]}

Eclat ^{[ 11 ]} (también conocido como ECLAT, que significa Transformación de Clase de Equivalencia) es un algoritmo de retroceso que recorre el grafo reticular de conjuntos de ítems frecuentes mediante una búsqueda en profundidad (DFS). Mientras que la búsqueda en amplitud (BFS) utilizada en el algoritmo Apriori termina comprobando cada subconjunto de un conjunto de ítems antes de comprobarlo, la búsqueda en profundidad comprueba conjuntos de ítems más grandes y puede ahorrar en la comprobación del soporte de algunos de sus subconjuntos gracias a la propiedad de cierre descendente. Además, casi con toda seguridad utilizará menos memoria, ya que la complejidad espacial de la búsqueda en profundidad es menor que la de la búsqueda en amplitud.

Para ilustrar esto, supongamos que existe un conjunto de elementos frecuentes {a, b, c}. Un DFS puede verificar los nodos en la red de conjuntos de elementos frecuentes en el siguiente orden: {a} → {a, b} → {a, b, c}, en cuyo punto se sabe que {b}, {c}, {a, c}, {b, c} satisfacen la restricción de soporte por la propiedad de cierre descendente. Un BFS exploraría cada subconjunto de {a, b, c} antes de verificarlo finalmente. A medida que aumenta el tamaño de un conjunto de elementos, el número de sus subconjuntos experimenta una explosión combinatoria .

Es adecuado tanto para la ejecución secuencial como paralela con propiedades que mejoran la localidad. ^{[ 28 ] [ 29 ]}

FP significa patrón frecuente. ^{[ 30 ]}

En la primera pasada, el algoritmo cuenta las ocurrencias de elementos (pares atributo-valor) en el conjunto de datos de transacciones y almacena estos recuentos en una "tabla de encabezado". En la segunda pasada, construye la estructura del árbol FP insertando transacciones en un trie .

Los elementos de cada transacción deben ordenarse en orden descendente según su frecuencia en el conjunto de datos antes de insertarlos, para que el árbol se procese rápidamente. Los elementos de cada transacción que no cumplen con el requisito mínimo de soporte se descartan. Si varias transacciones comparten los elementos más frecuentes, el árbol FP proporciona una alta compresión cerca de la raíz del árbol.

El procesamiento recursivo de esta versión comprimida del conjunto de datos principal genera directamente conjuntos de elementos frecuentes, en lugar de generar elementos candidatos y probarlos contra toda la base de datos (como en el algoritmo apriori).

El crecimiento comienza desde la parte inferior de la tabla de encabezado, es decir, el elemento con el soporte más pequeño, al encontrar todas las transacciones ordenadas que terminan en ese elemento. Llame a este elemento${\displaystyle I}$.

Se crea un nuevo árbol condicional que es el árbol FP original proyectado sobre${\displaystyle I}$. Los soportes de todos los nodos en el árbol proyectado se vuelven a contar, obteniendo cada nodo la suma de los recuentos de sus hijos. Los nodos (y por lo tanto subárboles) que no cumplen con el soporte mínimo se podan. El crecimiento recursivo termina cuando ningún elemento individual condicionado a${\displaystyle I}$cumplir con el umbral mínimo de soporte. Las rutas resultantes desde la raíz hasta${\displaystyle I}$serán conjuntos de elementos frecuentes. Después de este paso, el procesamiento continúa con el siguiente elemento de encabezado menos compatible del árbol FP original.

Una vez que el proceso recursivo se haya completado, se habrán encontrado todos los conjuntos de elementos frecuentes y comenzará la creación de reglas de asociación. ^{[ 31 ]}

• Bibliografía anotada sobre reglas de asociación archivada el 19 de febrero de 2017 en Wayback Machine por M. Hahsler