Aprendizaje de reglas de asociación

Método para descubrir relaciones interesantes entre variables en bases de datos.

El aprendizaje de reglas de asociación es un método de aprendizaje automático basado en reglas para descubrir relaciones interesantes entre variables en grandes bases de datos. Su objetivo es identificar reglas sólidas descubiertas en bases de datos utilizando algunas medidas de interés. ^[1] En cualquier transacción determinada con una variedad de artículos, las reglas de asociación están destinadas a descubrir las reglas que determinan cómo o por qué ciertos artículos están conectados.

Basándose en el concepto de reglas estrictas, Rakesh Agrawal , Tomasz Imieliński y Arun Swami ^[2] introdujeron reglas de asociación para descubrir regularidades entre productos en datos de transacciones a gran escala registrados por sistemas de puntos de venta (POS) en los supermercados. Por ejemplo, la regla encontrada en los datos de ventas de un supermercado indicaría que si un cliente compra cebollas y patatas juntas, es probable que también compre carne para hamburguesas. Dicha información puede usarse como base para decisiones sobre actividades de marketing como, por ejemplo, fijación de precios promocionales o colocación de productos . ${\displaystyle \{\mathrm {onions,potatoes} \}\Rightarrow \{\mathrm {burger} \}}$

Además del ejemplo anterior del análisis de la cesta de la compra , hoy en día se emplean reglas de asociación en muchas áreas de aplicaciones, incluida la minería de uso web , la detección de intrusos , la producción continua y la bioinformática . A diferencia de la minería de secuencias , el aprendizaje de reglas de asociación normalmente no considera el orden de los elementos ni dentro de una transacción ni entre transacciones.

El algoritmo de reglas de asociación en sí consta de varios parámetros que pueden dificultar su ejecución para quienes no tienen cierta experiencia en minería de datos, con muchas reglas que son difíciles de entender. ^[3]

Definición

Un diagrama de Venn para mostrar las asociaciones entre los conjuntos de elementos X e Y de un conjunto de datos. Todas las transacciones que contienen el elemento X se encuentran en la parte blanca izquierda del círculo, mientras que las que contienen Y están coloreadas en rojo y en la derecha. Cualquier transacción que contenga X e Y se ubica en el medio y es de color rosa. Se pueden utilizar varios conceptos para representar la información de este gráfico. Por ejemplo, si uno toma todas las transacciones en la sección rosa y las divide por la cantidad total de transacciones (transacciones que contienen X (blanco) + transacciones que contienen Y (rojo)), el resultado se conocería como soporte. En un ejemplo de obtención del resultado de un método conocido como confianza, se pueden tomar todas las transacciones del medio (rosa) y dividirlas por todas las transacciones que contienen Y (rojo y rosa). En este caso, Y es el antecedente y X es el consecuente.

Siguiendo la definición original de Agrawal, Imieliński y Swami ^[2], el problema de la minería de reglas de asociación se define como:

Sea un conjunto de n atributos binarios llamados elementos . ${\displaystyle I=\{i_{1},i_{2},\ldots ,i_{n}\}}$

Sea un conjunto de transacciones llamado base de datos . ${\displaystyle D=\{t_{1},t_{2},\ldots ,t_{m}\}}$

Cada transacción en D tiene un ID de transacción único y contiene un subconjunto de los elementos en I.

Una regla se define como una implicación de la forma:

${\displaystyle X\Rightarrow Y}$, dónde . ${\displaystyle X,Y\subseteq I}$

En Agrawal, Imieliński, Swami ^[2] se define una regla solo entre un conjunto y un solo elemento, por . ${\displaystyle X\Rightarrow i_{j}}$ ${\displaystyle i_{j}\in I}$

Cada regla está compuesta por dos conjuntos diferentes de ítems, también conocidos como conjuntos de ítems , X e Y , donde X se llama antecedente o del lado izquierdo (LHS) e Y consecuente o del lado derecho (RHS). El antecedente es el elemento que se puede encontrar en los datos, mientras que el consecuente es el elemento que se encuentra cuando se combina con el antecedente. La declaración a menudo se lee como si X entonces Y , donde el antecedente ( X ) es el si y el consecuente ( Y ) es el entonces . Esto simplemente implica que, en teoría, siempre que X ocurra en un conjunto de datos, Y también ocurrirá. ${\displaystyle X\Rightarrow Y}$

Proceso

Las reglas de asociación se crean buscando datos en busca de patrones frecuentes si-entonces y utilizando un determinado criterio en Apoyo y Confianza para definir cuáles son las relaciones más importantes. El respaldo es la evidencia de la frecuencia con la que aparece un elemento en los datos proporcionados, ya que la confianza se define por cuántas veces las afirmaciones si-entonces se consideran verdaderas. Sin embargo, hay un tercer criterio que se puede utilizar, se llama Elevación y se puede utilizar para comparar la Confianza esperada y la Confianza real. Lift mostrará cuántas veces se espera que la afirmación si-entonces sea verdadera.

Las reglas de asociación se crean para calcular a partir de conjuntos de elementos, que se crean a partir de dos o más elementos. Si las reglas se construyeran a partir del análisis de todos los conjuntos de elementos posibles de los datos, entonces habría tantas reglas que no tendrían ningún significado. Es por eso que las reglas de asociación generalmente se crean a partir de reglas que están bien representadas por los datos.

Existen muchas técnicas diferentes de minería de datos que puede utilizar para encontrar determinados análisis y resultados; por ejemplo, análisis de clasificación, análisis de agrupación y análisis de regresión. ^[4] La técnica que debes utilizar depende de lo que estés buscando con tus datos. Las reglas de asociación se utilizan principalmente para encontrar análisis y predecir el comportamiento del cliente. Para el análisis de clasificación, lo más probable es que se utilice para cuestionar, tomar decisiones y predecir comportamientos. ^[5] El análisis de agrupamiento se utiliza principalmente cuando no se hacen suposiciones sobre las relaciones probables dentro de los datos. ^[5] El análisis de regresión se utiliza cuando se desea predecir el valor de un dependiente continuo a partir de varias variables independientes. ^[5]

Beneficios

Existen muchos beneficios al utilizar reglas de asociación, como encontrar el patrón que ayude a comprender las correlaciones y coocurrencias entre conjuntos de datos. Un muy buen ejemplo del mundo real que utiliza reglas de Asociación sería la medicina. La medicina utiliza reglas de la Asociación para ayudar a diagnosticar a los pacientes. Al diagnosticar a los pacientes hay muchas variables a considerar, ya que muchas enfermedades compartirán síntomas similares. Con el uso de las reglas de la Asociación, los médicos pueden determinar la probabilidad condicional de una enfermedad comparando las relaciones entre síntomas de casos pasados. ^[6]

Desventajas

Sin embargo, las reglas de asociación también conllevan muchos inconvenientes diferentes, como encontrar los parámetros y la configuración de umbral adecuados para el algoritmo de minería. Pero también existe la desventaja de tener una gran cantidad de reglas descubiertas. La razón es que esto no garantiza que las reglas sean relevantes, pero también podría causar que el algoritmo tenga un bajo rendimiento. A veces, los algoritmos implementados contendrán demasiadas variables y parámetros. Para alguien que no tiene un buen concepto de minería de datos, esto podría causarle problemas para entenderlo. ^[7]

Umbrales

Enrejado de conjunto de elementos frecuentes, donde el color del cuadro indica cuántas transacciones contienen la combinación de elementos. Tenga en cuenta que los niveles inferiores de la red pueden contener como máximo el número mínimo de elementos de sus padres; por ejemplo, {ac} solo puede tener como máximo elementos. Esto se llama propiedad de cierre a la baja . ^[2] ${\displaystyle \min(a,c)}$

Al utilizar reglas de Asociación, lo más probable es que solo utilice Soporte y Confianza. Sin embargo, esto significa que debe satisfacer un soporte mínimo especificado por el usuario y una confianza mínima especificada por el usuario al mismo tiempo. Por lo general, la generación de reglas de asociación se divide en dos pasos diferentes que deben aplicarse:

1. Un umbral mínimo de soporte para encontrar todos los conjuntos de elementos frecuentes que se encuentran en la base de datos.
2. Un umbral de confianza mínimo para los conjuntos de elementos frecuentes que se encuentran para crear reglas.

El umbral de apoyo es del 30%, el umbral de confianza es del 50%

La tabla de la izquierda son los datos originales no organizados y la tabla de la derecha está organizada por umbrales. En este caso, el Ítem C es mejor que los umbrales tanto de Apoyo como de Confianza, por lo que ocupa el primer lugar. El elemento A ocupa el segundo lugar porque sus valores umbral son acertados. El elemento D ha alcanzado el umbral de apoyo pero no de confianza. El ítem B no ha alcanzado el umbral ni de Apoyo ni de Confianza y es por eso que está último.

Encontrar todos los conjuntos de elementos frecuentes en una base de datos no es una tarea fácil, ya que implica revisar todos los datos para encontrar todas las combinaciones posibles de elementos de todos los conjuntos de elementos posibles. El conjunto de conjuntos de elementos posibles es la potencia establecida sobre I y tiene tamaño ; por supuesto, esto significa excluir el conjunto vacío que no se considera un conjunto de elementos válido. Sin embargo, el tamaño del conjunto de potencias crecerá exponencialmente en el número de elementos n que estén dentro del conjunto de potencias I. Es posible una búsqueda eficiente utilizando la propiedad de cierre descendente del soporte ^{[2] [8]} (también llamada antimonotonicidad ^[9] ). Esto garantizaría que un conjunto de elementos frecuentes y todos sus subconjuntos también lo sean y, por lo tanto, no habrá conjuntos de elementos infrecuentes como subconjunto de un conjunto de elementos frecuentes. Al explotar esta propiedad, los algoritmos eficientes (por ejemplo, Apriori ^[10] y Eclat ^[11] ) pueden encontrar todos los conjuntos de elementos frecuentes. ${\displaystyle 2^{n}-1}$

Conceptos útiles

Para ilustrar los conceptos, utilizamos un pequeño ejemplo del ámbito de los supermercados. La Tabla 2 muestra una pequeña base de datos que contiene los artículos donde, en cada entrada, el valor 1 significa la presencia del artículo en la transacción correspondiente y el valor 0 representa la ausencia de un artículo en esa transacción. El conjunto de elementos es . ${\displaystyle I=\{\mathrm {milk,bread,butter,beer,diapers,eggs,fruit} \}}$

Un ejemplo de regla para el supermercado podría ser que si se compra mantequilla y pan, los clientes también compren leche. ${\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \}}$

Para seleccionar reglas interesantes del conjunto de todas las reglas posibles, se utilizan restricciones sobre varias medidas de significancia e interés. Las limitaciones más conocidas son los umbrales mínimos de apoyo y confianza.

Sean conjuntos de elementos, una regla de asociación y T un conjunto de transacciones de una base de datos determinada. ${\displaystyle X,Y}$ ${\displaystyle X\Rightarrow Y}$

Nota: este ejemplo es extremadamente pequeño. En aplicaciones prácticas, una regla necesita el respaldo de varios cientos de transacciones antes de que pueda considerarse estadísticamente significativa ^{[ cita necesaria ]} y los conjuntos de datos a menudo contienen miles o millones de transacciones.

Apoyo

El soporte es una indicación de la frecuencia con la que aparece el conjunto de elementos en el conjunto de datos.

En nuestro ejemplo, puede ser más fácil explicar el soporte escribiendo ^[12] donde A y B son conjuntos de elementos separados que ocurren al mismo tiempo en una transacción. ${\displaystyle {\text{support}}=P(A\cap B)={\frac {({\text{number of transactions containing }}A{\text{ and }}B)}{\text{ (total number of transactions)}}}}$

Usando la Tabla 2 como ejemplo, el conjunto de elementos 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 apoyo a X es un conjunto de condiciones previas y, por tanto, se vuelve más restrictivo a medida que crece (en lugar de más inclusivo). ^[13] ${\displaystyle X=\{\mathrm {beer,diapers} \}}$

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

Cuando se utilizan antecedentes y consecuentes, permite al minero de datos determinar el soporte de varios artículos que se compran juntos en comparación con el conjunto de datos completo. Por ejemplo, el Cuadro 2 muestra que si se compra leche, entonces se compra pan tiene un apoyo del 0,4 o 40%. Esto porque en 2 de cada 5 de las transacciones se compra tanto leche como pan. En conjuntos de datos más pequeños como este ejemplo, es más difícil ver una correlación fuerte cuando hay pocas muestras, pero cuando el conjunto de datos crece, se puede utilizar el apoyo para encontrar una correlación 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 se eliminaría ya que no cumplió con el umbral mínimo de 0,4. El umbral mínimo se utiliza para eliminar muestras donde no hay un apoyo o confianza lo suficientemente fuerte como para considerar la muestra como importante o interesante en el conjunto de datos. ${\displaystyle \{\mathrm {milk} \}\Rightarrow \{\mathrm {eggs} \}}$

Otra forma de encontrar muestras interesantes es encontrar el valor de (apoyo)×(confianza); esto permite que un minero de datos vea las muestras donde el apoyo y la confianza son lo suficientemente altos como para resaltarse en el conjunto de datos y solicitar una mirada más cercana a la muestra para encontrar más información sobre la conexión entre los elementos.

El soporte puede ser beneficioso para encontrar la conexión entre productos en comparación con todo el conjunto de datos, 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 muestra la comparación y el contraste entre soporte y soporte × confianza, utilizando la información de la Tabla 4 para derivar 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 elementos X. Al denotar una transacción donde i es el identificador único de la transacción y t es su conjunto de elementos, el soporte puede escribirse como: ${\displaystyle (i,t)}$

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

Esta notación se puede utilizar al definir conjuntos de datos más complicados donde los artículos y los conjuntos de artículos pueden no ser tan fáciles como en nuestro ejemplo de supermercado anterior. Otros ejemplos de dónde se puede utilizar el apoyo es encontrar grupos de mutaciones genéticas que trabajen colectivamente para causar una enfermedad, investigar la cantidad de suscriptores que responden a ofertas de actualización y descubrir qué productos en una farmacia nunca se compran juntos. ^[12]

Confianza

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

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

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

Comúnmente se representa como:

${\displaystyle \mathrm {conf} (X\Rightarrow Y)=P(Y|X)={\frac {\mathrm {supp} (X\cap 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 las 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 tanto en X como en Y se divide por aquellas solo en X.

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

Para conjuntos de datos más grandes, un umbral mínimo o un límite porcentual de confianza puede resultar útil para determinar las relaciones entre 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%). Se omite cualquier dato que no tenga una confianza de al menos 0,5. La generación de umbrales permite que la asociación entre elementos se fortalezca a medida que los datos se investigan más a fondo enfatizando aquellos que más coexisten. La tabla utiliza la información de confianza de la Tabla 3 para implementar la columna Apoyo × Confianza, donde se resalta la relación entre los elementos a través de su confianza y apoyo, en lugar de solo un concepto. Clasificar las reglas por Soporte × Confianza multiplica la confianza de una regla particular en su soporte y, a menudo, se implementa 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 generar conciencia sobre las relaciones de datos. Su mayor beneficio es resaltar la relación entre elementos particulares entre sí 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. La desventaja de usarlo es que no ofrece múltiples perspectivas diferentes sobre las asociaciones. A diferencia del apoyo, por ejemplo, la confianza no proporciona la perspectiva de las relaciones entre ciertos elementos en comparación con todo el conjunto de datos, por lo que, si bien la leche y el pan, por ejemplo, pueden aparecer el 100% del tiempo para la confianza, solo tiene un apoyo de 0,4. (40%). Por eso es importante mirar otros puntos de vista, como Apoyo × Confianza, en lugar de confiar únicamente en un concepto incesantemente para definir las relaciones.

Elevar

La elevación de una regla se define como:

${\displaystyle \mathrm {lift} (X\Rightarrow Y)={\frac {\mathrm {supp} (X\cap 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 tiene una elevación de . ${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$ ${\displaystyle {\frac {0.2}{0.4\times 0.4}}=1.25}$

Si la regla tuviera una 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 establecer ninguna regla que involucre a esos dos eventos.

Si la elevación es > 1, eso nos permite saber el grado en que esas dos ocurrencias dependen entre sí y hace que esas reglas sean potencialmente útiles para predecir el consecuente en futuros conjuntos de datos.

Si el incremento es <1, eso nos permite saber que los elementos se sustituyen entre sí. Esto significa que la presencia de un elemento tiene un efecto negativo sobre la presencia de otro elemento y viceversa.

El valor de la elevación es que considera tanto el soporte de la regla como el conjunto de datos general. ^[13]

Convicción

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

Por ejemplo, la regla tiene una convicción de , y puede interpretarse como la relación de 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 dividido por la frecuencia observada de predicciones incorrectas. En este ejemplo, el valor de convicción de 1,2 muestra que la regla sería incorrecta un 20% más a menudo (1,2 veces más a menudo) si la asociación entre X e Y fuera puramente aleatoria. ${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$ ${\displaystyle {\frac {1-0.4}{1-0.5}}=1.2}$ ${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$

Medidas alternativas de interés.

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

• Toda confianza ^[17]
• Fuerza colectiva ^[18]
• Apalancamiento ^[19]

Tan et al. presentan y comparan varias medidas más. ^[20] y por Hahsler. ^[21] Buscar técnicas que puedan modelar lo que el usuario ha conocido (y usar estos modelos como medidas de interés) es actualmente una tendencia de investigación activa bajo el nombre de "Interés subjetivo".

Historia

El concepto de reglas de asociación se popularizó especialmente gracias al artículo de 1993 de Agrawal et al., ^[2] que ha obtenido más de 23.790 citas según Google Scholar, hasta abril de 2021, y es, por tanto, uno de los artículos más citados en el Campo de minería de datos. Sin embargo, lo que ahora se llama "reglas de asociación" ya se introdujo en el artículo de 1966 ^[22] sobre GUHA, un método general de extracción de datos desarrollado por Petr Hájek et al. ^[23]

Un uso temprano (alrededor de 1989) de soporte y confianza mínimos para encontrar todas las reglas de asociación es el marco de modelado basado en características, que encontró todas las reglas con restricciones definidas por el usuario y mayores que ellas. ^[24] ${\displaystyle \mathrm {supp} (X)}$ ${\displaystyle \mathrm {conf} (X\Rightarrow Y)}$

Asociaciones estadísticamente sólidas

Una limitación del enfoque estándar para descubrir asociaciones es que al buscar cantidades masivas de posibles asociaciones para buscar colecciones de elementos que parecen estar asociados, existe un gran riesgo de encontrar muchas asociaciones falsas. Se trata de conjuntos de elementos que coexisten con una frecuencia inesperada en los datos, pero sólo lo hacen por casualidad. Por ejemplo, supongamos que estamos considerando una colección de 10.000 elementos y buscamos reglas que contengan dos elementos en el lado izquierdo y 1 elemento en el lado derecho. Existen aproximadamente 1.000.000.000.000 de reglas de este tipo. Si aplicamos una prueba estadística de independencia con un nivel de significancia de 0,05 significa que solo hay un 5% de posibilidades de aceptar una regla si no hay asociación. Si asumimos que no hay asociaciones, deberíamos esperar encontrar 50.000.000.000 de reglas. El descubrimiento de asociaciones estadísticamente sólidas ^{[25] [26]} controla este riesgo, reduciendo en la mayoría de los casos el riesgo de encontrar asociaciones falsas a un nivel de significancia especificado por el usuario.

Algoritmos

Se han propuesto muchos algoritmos para generar reglas de asociación.

Algunos algoritmos conocidos son Apriori , Eclat y FP-Growth, pero solo hacen la mitad del trabajo, ya que son algoritmos para extraer conjuntos de elementos frecuentes. Después es necesario realizar otro paso para generar reglas a partir de conjuntos de elementos frecuentes que se encuentran en una base de datos.

Algoritmo a priori

Apriori es proporcionado por R. Agrawal y R. Srikant en 1994 para el aprendizaje frecuente de reglas de asociación y minería de conjuntos de elementos. Procede identificando los elementos individuales frecuentes en la base de datos y extendiéndolos a conjuntos de elementos cada vez más grandes, siempre que esos conjuntos de elementos aparezcan con suficiente frecuencia. El nombre del algoritmo es Apriori porque utiliza conocimiento previo de las propiedades frecuentes de los conjuntos de elementos.

El diagrama de flujo de control para el algoritmo Apriori.

Descripción general: Apriori utiliza un enfoque "de abajo hacia arriba", donde los subconjuntos frecuentes se amplían 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 finaliza cuando no se encuentran más extensiones exitosas. Apriori utiliza una búsqueda en amplitud y una estructura de árbol Hash para contar conjuntos de elementos candidatos de manera eficiente. 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 de longitud frecuente. Después de eso, escanea la base de datos de transacciones para determinar conjuntos de artículos frecuentes entre los candidatos.

Ejemplo: supongamos que cada fila es una muestra de cáncer con una determinada combinación de mutaciones etiquetadas por un carácter del alfabeto. Por ejemplo, una fila podría tener {a, c}, lo que significa que se ve afectada por la mutación 'a' y la mutación 'c'.

Ahora generaremos el conjunto de elementos frecuentes contando el número de apariciones de cada personaje. Esto también se conoce como encontrar los valores de soporte. Luego podaremos el conjunto de elementos eligiendo un umbral de soporte mínimo. Para esta pasada del algoritmo elegiremos 3.

Dado que todos los valores de soporte son tres o más, no hay poda. El conjunto de elementos frecuentes es {a}, {b}, {c} y {d}. Después de esto repetiremos el proceso contando pares de mutaciones en el conjunto de entrada.

Ahora haremos que nuestro valor de soporte mínimo sea 4, de modo que solo quede {a, d} después de la poda. Ahora usaremos el conjunto de elementos frecuentes para hacer combinaciones de trillizos. Luego repetiremos el proceso contando las apariciones de tripletes de mutaciones en el conjunto de entrada.

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

Ventajas y limitaciones:

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

Algoritmo de Éclat

Eclat ^[11] (alt. ECLAT, significa Equivalence Class Transformation) es un algoritmo de retroceso que atraviesa el gráfico de celosía de conjuntos de elementos frecuentes en forma de búsqueda en profundidad (DFS). Mientras que el recorrido de búsqueda en amplitud (BFS) utilizado en el algoritmo Apriori terminará verificando cada subconjunto de un conjunto de elementos antes de verificarlo, el recorrido DFS verifica conjuntos de elementos más grandes y puede ahorrar en la verificación del soporte de algunos de sus subconjuntos en virtud de la búsqueda descendente. -propiedad más cercana. Además, es casi seguro que utilizará menos memoria ya que DFS tiene una complejidad de espacio menor que BFS.

Para ilustrar esto, supongamos que haya 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}, momento en el que se sabe que {b}, {c}, { a, c}, {b, c} satisfacen la restricción de soporte mediante la propiedad de cierre descendente. 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 sufre una explosión combinatoria .

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

Algoritmo de crecimiento de FP

FP significa patrón frecuente. ^[30]

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

Los elementos de cada transacción deben ordenarse en orden descendente de su frecuencia en el conjunto de datos antes de insertarse para que el árbol pueda procesarse rápidamente. Los artículos de cada transacción que no cumplan con el requisito mínimo de soporte se descartan. Si muchas 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 aumenta los conjuntos de elementos frecuentes directamente, en lugar de generar elementos candidatos y probarlos con toda la base de datos (como en el algoritmo a priori).

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 artículo . ${\displaystyle I}$

Se crea un nuevo árbol condicional que es el árbol FP original proyectado . Los soportes de todos los nodos en el árbol proyectado se vuelven a contar y cada nodo obtiene la suma de los recuentos de sus hijos. Los nodos (y por tanto los subárboles) que no cumplen con el soporte mínimo se podan. El crecimiento recursivo finaliza cuando ningún elemento individual condicionado cumple el umbral mínimo de soporte. Las rutas resultantes desde la raíz hasta 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. ${\displaystyle I}$ ${\displaystyle I}$ ${\displaystyle I}$

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

Otros

ASOC

El procedimiento ASSOC ^[32] es un método GUHA que busca reglas de asociación generalizadas utilizando operaciones rápidas de cadenas de bits . Las reglas de asociación extraídas por este método son más generales que las obtenidas a priori; por ejemplo, los "elementos" pueden conectarse tanto con conjunciones como con disyunciones y la relación entre antecedente y consecuente de la regla no se limita a establecer un mínimo de apoyo y confianza como en a priori: se puede utilizar una combinación arbitraria de medidas de interés respaldado.

búsqueda OPUS

OPUS es un algoritmo eficiente para el descubrimiento de reglas que, a diferencia de la mayoría de las alternativas, no requiere restricciones monótonas o antimonótonas, como un soporte mínimo. ^[33] Inicialmente utilizado para encontrar reglas para un consecuente fijo ^{[33] [34]} posteriormente se ha ampliado para encontrar reglas con cualquier elemento como consecuente. ^[35] La búsqueda OPUS es la tecnología central del popular sistema de descubrimiento de asociaciones Magnum Opus.

Ciencia

Una historia famosa sobre la minería de reglas de asociación es la historia de "la cerveza y el pañal". Una supuesta encuesta sobre el comportamiento de los compradores de supermercados descubrió que los clientes (presumiblemente hombres jóvenes) que compran pañales tienden también a comprar cerveza. Esta anécdota se hizo popular como ejemplo de cómo se pueden encontrar reglas de asociación inesperadas a partir de datos cotidianos. Hay diferentes opiniones sobre qué parte de la historia es cierta. ^[36] Daniel Powers dice: ^[36]

En 1992, Thomas Blischok, director de un grupo de consultoría minorista en Teradata , y su personal prepararon un análisis de 1,2 millones de cestas de la compra de unas 25 tiendas Osco Drug. Se desarrollaron consultas a bases de datos para identificar afinidades. El análisis "sí descubrió que entre las 17.00 y las 19.00 horas los consumidores compraban cerveza y pañales". Los gerentes de Osco NO explotaron la relación entre la cerveza y los pañales acercando los productos en los estantes.

Otros tipos de minería de reglas de asociación

Reglas de asociación de relaciones múltiples (MRAR) : son reglas de asociación donde cada elemento puede tener varias relaciones. Estas relaciones indican relaciones indirectas entre las entidades. Considere el siguiente MRAR donde el primer ítem consta de tres relaciones que viven en , cercano y húmedo : “Quienes viven en un lugar cercano a una ciudad con tipo de clima húmedo y además son menores de 20 años su estado de salud es bueno”. Estas reglas de asociación se pueden extraer de datos RDBMS o datos de la web semántica. ^[37] ${\displaystyle \implies }$

El aprendizaje de conjuntos de contrastes es una forma de aprendizaje asociativo. Los alumnos de conjuntos de contraste utilizan reglas que difieren significativamente en su distribución entre los subconjuntos. ^{[38] [39]}

El aprendizaje de clases ponderado es otra forma de aprendizaje asociativo en el que se pueden asignar ponderaciones a las clases para centrarse en un tema particular de interés para el consumidor de los resultados de la minería de datos.

El descubrimiento de patrones de alto orden facilita la captura de patrones de alto orden (politéticos) o asociaciones de eventos que son intrínsecos a datos complejos del mundo real.^[40]

El descubrimiento de patrones K-óptimo proporciona una alternativa al enfoque estándar para el aprendizaje de reglas de asociación que requiere que cada patrón aparezca con frecuencia en los datos.

La minería aproximada de conjuntos de elementos frecuentes es una versión relajada de la minería de conjuntos de elementos frecuentes que permite que algunos de los elementos en algunas filas sean 0. ^[41]

Taxonomía jerárquica de reglas de asociación generalizadas (jerarquía de conceptos)

Reglas de asociación cuantitativa datos categóricos y cuantitativos

Reglas de asociación de datos de intervalo , por ejemplo, dividir la edad en un intervalo de incrementos de 5 años

La minería de patrones secuenciales descubre subsecuencias que son comunes a más de secuencias minsup (umbral mínimo de soporte) en una base de datos de secuencias, donde el usuario establece minsup. Una secuencia es una lista ordenada de transacciones. ^[42]

La agrupación subespacial , un tipo específico de agrupación de datos de alta dimensión , en muchas variantes también se basa en la propiedad de cierre descendente para modelos de agrupación específicos. ^[43]

Warmr , incluido como parte de la suite de minería de datos ACE, permite el aprendizaje de reglas de asociación para reglas relacionales de primer orden. ^[44]

Ver también

• Minería de secuencias
• Sistema de producción (informática)
• Sistema clasificador de aprendizaje.
• Aprendizaje automático basado en reglas

Referencias

1. Piatetsky-Shapiro, Gregory (1991), Descubrimiento, análisis y presentación de reglas estrictas , en Piatetsky-Shapiro, Gregory; y Frawley, William J.; eds., Descubrimiento de conocimientos en bases de datos , AAAI/MIT Press, Cambridge, MA.
2. , R.; Imieliński, T.; Swami, A. (1993). "Reglas de asociación minera entre conjuntos de elementos en grandes bases de datos". Actas de la conferencia internacional ACM SIGMOD de 1993 sobre gestión de datos: SIGMOD '93 . pag. 207. CiteSeerX  10.1.1.40.6984 . doi :10.1145/170035.170072. ISBN 978-0897915922. S2CID  490415.
3. García, Enrique (2007). "Inconvenientes y soluciones de la aplicación de la minería de reglas de asociación en sistemas de gestión del aprendizaje" (PDF) . Ciencia2 . Archivado (PDF) desde el original el 23 de diciembre de 2009.
4. "Técnicas de minería de datos: las cinco principales a considerar". Precisamente . 2021-11-08 . Consultado el 10 de diciembre de 2021 .
5. "16 técnicas de minería de datos: la lista completa - Talend". Talend: líder en integración e integridad de datos . Consultado el 10 de diciembre de 2021 .
6. "¿Qué son las reglas de asociación en la minería de datos (minería de reglas de asociación)?". BúsquedaBusinessAnalytics . Consultado el 10 de diciembre de 2021 .
7. "Inconvenientes y soluciones de la aplicación de la minería de reglas de asociación en sistemas de gestión del aprendizaje". Puerta de la investigación . Consultado el 10 de diciembre de 2021 .
8. Bronceado, Pang-Ning; Michael, Steinbach; Kumar, VIPIN (2005). "Capítulo 6. Análisis de asociación: conceptos básicos y algoritmos" (PDF) . Introducción a la Minería de Datos . Addison-Wesley . ISBN 978-0-321-32136-7.
9. Jian Pei; Jiawei Han; Lakshmanan, LVS (2001). "Extracción de conjuntos de elementos frecuentes con restricciones convertibles". Actas de la 17ª Conferencia Internacional sobre Ingeniería de Datos . págs. 433–442. CiteSeerX 10.1.1.205.2150 . doi :10.1109/ICDE.2001.914856. ISBN  978-0-7695-1001-9. S2CID  1080975.
10. Agrawal, Rakesh; y Srikant, Ramakrishnan; Algoritmos rápidos para reglas de asociaciones mineras en grandes bases de datos Archivado el 25 de febrero de 2015 en Wayback Machine , en Bocca, Jorge B.; Jarke, Matías; y Zaniolo, Carlo; editores, Actas de la XX Conferencia Internacional sobre Bases de Datos Muy Grandes (VLDB), Santiago, Chile, septiembre de 1994 , páginas 487-499
11. Zaki, MJ (2000). "Algoritmos escalables para minería asociativa". Transacciones IEEE sobre conocimiento e ingeniería de datos . 12 (3): 372–390. CiteSeerX 10.1.1.79.9448 . doi : 10.1109/69.846291. 
12. Larose, Daniel T.; Larose, Chantal D. (23 de junio de 2014). Descubriendo el conocimiento en los datos. doi :10.1002/9781118874059. ISBN 9781118874059.
13. Hahsler, Michael (2005). "Introducción a las reglas: un entorno computacional para reglas de asociaciones mineras y conjuntos de elementos frecuentes" (PDF) . Revista de software estadístico . doi : 10.18637/jss.v014.i15 . Archivado desde el original (PDF) el 30 de abril de 2019 . Consultado el 18 de marzo de 2016 .
14. Wong, Pak (1999). "Visualización de reglas de asociación para minería de textos" (PDF) . Laboratorio de Redes Neuronales Artificiales de BSTU . Archivado (PDF) desde el original el 29 de noviembre de 2021.
15. Hipp, J.; Güntzer, U.; Nakhaeizadeh, G. (2000). "Algoritmos para la minería de reglas de asociación: un estudio general y una comparación". Boletín de exploraciones de ACM SIGKDD . 2 : 58–64. CiteSeerX 10.1.1.38.5305 . doi :10.1145/360402.360421. S2CID  9248096. 
16. Brin, Sergey; Motwani, Rajeev; Ullman, Jeffrey D.; Tsur, Shalom (1997). "Recuento dinámico de conjuntos de artículos y reglas de implicación para datos de la cesta de la compra". Actas de la conferencia internacional ACM SIGMOD de 1997 sobre gestión de datos: SIGMOD '97 . págs. 255–264. CiteSeerX 10.1.1.41.6476 . doi :10.1145/253260.253325. ISBN  978-0897919111. S2CID  15385590.
17. Omiecinski, ER (2003). “Medidas alternativas de interés para las asociaciones mineras en bases de datos”. Transacciones IEEE sobre conocimiento e ingeniería de datos . 15 : 57–69. CiteSeerX 10.1.1.329.5344 . doi :10.1109/TKDE.2003.1161582. S2CID  18364249. 
18. Aggarwal, Charu C.; Yu, Philip S. (1998). "Un nuevo marco para la generación de conjuntos de elementos". Actas del decimoséptimo simposio ACM SIGACT-SIGMOD-SIGART sobre principios de los sistemas de bases de datos - PODS '98 . págs. 18-24. CiteSeerX 10.1.1.24.714 . doi :10.1145/275487.275490. ISBN  978-0897919968. S2CID  11934586.
19. Piatetsky-Shapiro, Gregory; Descubrimiento, análisis y presentación de reglas sólidas , Descubrimiento de conocimientos en bases de datos, 1991, págs. 229-248
20. Bronceado, Pang-Ning; Kumar, VIPIN; Srivastava, Jaideep (2004). "Seleccionar la medida objetiva adecuada para el análisis de asociación". Sistemas de información . 29 (4): 293–313. CiteSeerX 10.1.1.331.4740 . doi :10.1016/S0306-4379(03)00072-3. 
21. Michael Hahsler (2015). Una comparación probabilística de medidas de interés comúnmente utilizadas para reglas de asociación. https://mhahsler.github.io/arules/docs/measures
22. Hájek, P.; Havel, I.; Chytil, M. (1966). "El método GUHA de determinación automática de hipótesis". Informática . 1 (4): 293–308. doi :10.1007/BF02345483. S2CID  10511114.
23. Hájek, Petr; Rauch, enero; Coufal, David; Feglar, Tomáš (2004). "El Método GUHA, Preprocesamiento y Minería de Datos". Soporte de bases de datos para aplicaciones de minería de datos . Apuntes de conferencias sobre informática. vol. 2682, págs. 135-153. doi :10.1007/978-3-540-44497-8_7. ISBN 978-3-540-22479-2.
24. Webb, Geoffrey (1989). "Un enfoque de aprendizaje automático para el modelado de estudiantes". Actas de la Tercera Conferencia Conjunta Australiana sobre Inteligencia Artificial (AI 89) : 195–205.
25. Webb, Geoffrey I. (2007). "Descubriendo patrones significativos". Aprendizaje automático . 68 : 1–33. doi : 10.1007/s10994-007-5006-x .
26. Gionis, Arístides; Mannila, Heikki; Mielikäinen, Taneli; Tsaparas, Panayiotis (2007). "Evaluación de los resultados de la minería de datos mediante aleatorización de intercambio". Transacciones ACM sobre descubrimiento de conocimiento a partir de datos . 1 (3): 14–es. CiteSeerX 10.1.1.141.2607 . doi :10.1145/1297332.1297338. S2CID  52305658. 
27. Heaton, Jeff (30 de enero de 2017). "Comparación de características de conjuntos de datos que favorecen los algoritmos de minería de conjuntos de elementos frecuentes Apriori, Eclat o FP-Growth". arXiv : 1701.09042 [cs.DB].
28. Zaki, Mohammed Javeed; Parthasarathy, Srinivasan; Ogihara, Mitsunori; Li, Wei (1997). "Nuevos algoritmos para el descubrimiento rápido de reglas de asociación": 283–286. CiteSeerX 10.1.1.42.3283 . hdl :1802/501.  {{cite journal}}: Citar diario requiere |journal=( ayuda )
29. Zaki, Mohammed J.; Parthasarathy, Srinivasan; Ogihara, Mitsunori; Li, Wei (1997). "Algoritmos paralelos para el descubrimiento de reglas de asociación". Minería de datos y descubrimiento de conocimientos . 1 (4): 343–373. doi :10.1023/A:1009773317876. S2CID  10038675.
30. Han (2000). "Minería de patrones frecuentes sin generación de candidatos". Actas de la conferencia internacional ACM SIGMOD de 2000 sobre gestión de datos . vol. SIGMOD '00. págs. 1–12. CiteSeerX 10.1.1.40.4436 . doi :10.1145/342009.335372. ISBN  978-1581132175. S2CID  6059661.
31. Witten, Frank, Hall: Herramientas y técnicas prácticas de aprendizaje automático de minería de datos, tercera edición ^{[ página necesaria ]}
32. Hájek, Petr; Havránek, Tomáš (1978). Mecanizar la formación de hipótesis: fundamentos matemáticos para una teoría general. Springer-Verlag. ISBN 978-3-540-08738-0.
33. Webb, Geoffrey I. (1995); OPUS: An Efficient Admissible Algorithm for Unordered Search , Journal of Artificial Intelligence Research 3, Menlo Park, CA: AAAI Press, págs. 431-465, acceso en línea
34. Bayardo, Roberto J. Jr.; Agrawal, Rakesh; Gunópulos, Dimitrios (2000). "Minería de reglas basada en restricciones en bases de datos grandes y densas". Minería de datos y descubrimiento de conocimientos . 4 (2): 217–240. doi :10.1023/A:1009895914772. S2CID  5120441.
35. Webb, Geoffrey I. (2000). "Búsqueda eficiente de reglas de asociación". Actas de la sexta conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos - KDD '00 . págs. 99-107. CiteSeerX 10.1.1.33.1309 . doi :10.1145/347090.347112. ISBN  978-1581132335. S2CID  5444097.
36. "DSS News: Vol. 3, No. 23".
37. Ramezani, Reza, Mohamad Saraee y Mohammad Ali Nematbakhsh; MRAR: Reglas de la Asociación Minera de Relación Múltiple , Journal of Computing and Security, 1, no. 2 (2014)
38. GI Webb, S. Butler y D. Newlands (2003). Sobre la detección de diferencias entre grupos. KDD'03 Actas de la Novena Conferencia Internacional ACM SIGKDD sobre Descubrimiento de Conocimiento y Minería de Datos.
39. Menzies, T.; Ying Hu (2003). "Prácticas informáticas: minería de datos para personas muy ocupadas". Computadora . 36 (11): 22-29. doi :10.1109/MC.2003.1244531.
40. Wong, AKC; Yang Wang (1997). "Descubrimiento de patrones de alto orden a partir de datos de valores discretos". Transacciones IEEE sobre conocimiento e ingeniería de datos . 9 (6): 877–893. CiteSeerX 10.1.1.189.1704 . doi : 10.1109/69.649314. 
41. Liu, Jinze; Paulsen, Susan; Sol, Xing; Wang, Wei; Nobel, Andrés; Prins, enero (2006). "Minería de conjuntos de elementos frecuentes aproximados en presencia de ruido: algoritmo y análisis". Actas de la Conferencia Internacional SIAM de 2006 sobre Minería de Datos . págs. 407–418. CiteSeerX 10.1.1.215.3599 . doi :10.1137/1.9781611972764.36. ISBN  978-0-89871-611-5.
42. Zaki, Mohammed J. (2001); SPADE: Un algoritmo eficiente para extraer secuencias frecuentes , Machine Learning Journal, 42, págs. 31–60
43. Zimek, Arturo; Asentimiento, Ira; Vreeken, Jilles (2014). Minería de patrones frecuentes . págs. 403–423. doi :10.1007/978-3-319-07821-2_16. ISBN 978-3-319-07820-5.
44. Rey, RD; Srinivasan, A.; Dehaspe, L. (febrero de 2001). "Warmr: una herramienta de minería de datos para datos químicos". J Mol Des asistido por computadora . 15 (2): 173–81. Código Bib : 2001JCAMD..15..173K. doi :10.1023/A:1008171016861. PMID  11272703. S2CID  3055046.

Bibliografías

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