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 bases de datos grandes. Su objetivo es identificar reglas sólidas descubiertas en bases de datos utilizando algunas medidas de interés. ^[1] En cualquier transacción dada con una variedad de elementos, las reglas de asociación tienen como objetivo descubrir las reglas que determinan cómo o por qué se conectan ciertos elementos.

Basándose en el concepto de reglas fuertes, 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 punto de venta (POS) en 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 de hamburguesa. Dicha información se puede utilizar como base para tomar decisiones sobre actividades de marketing como, por ejemplo, precios promocionales o ubicaciones de productos . ${\displaystyle \{\mathrm {onions,potatoes} \}\Rightarrow \{\mathrm {burger} \}}$

Además del ejemplo anterior del análisis de la cesta de la compra , las reglas de asociación se emplean hoy en día en muchas áreas de aplicación, entre ellas la minería de datos de uso web , la detección de intrusiones , la producción continua y la bioinformática . A diferencia de la minería de datos de secuencias , el aprendizaje de reglas de asociación normalmente no tiene en cuenta 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, y muchas de las reglas son difíciles de entender. ^[3]

Definición

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 ubican en la parte blanca izquierda del círculo, mientras que las que contienen Y se colorean en rojo y a la derecha. Cualquier transacción que contenga tanto X como Y se ubica en el medio y se colorea de rosa. Se pueden utilizar múltiples conceptos para representar la información de este gráfico. Por ejemplo, si se toman todas las transacciones en la sección rosa y se dividen por la cantidad total de transacciones (transacciones que contienen X (blanco) + transacciones que contienen Y (rojo)), el resultado se conocería como el soporte. Un ejemplo de obtención del resultado de un método conocido como la confianza, se pueden tomar todas las transacciones en el 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, 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] una regla se define solo entre un conjunto y un solo elemento, por ejemplo . ${\displaystyle X\Rightarrow i_{j}}$ ${\displaystyle i_{j}\in I}$

Cada regla está compuesta por dos conjuntos diferentes de elementos, también conocidos como conjuntos de elementos , X e Y , donde X se llama antecedente o lado izquierdo (LHS) e Y consecuente o 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 ocurre en un conjunto de datos, entonces Y también lo hará. ${\displaystyle X\Rightarrow Y}$

Proceso

Las reglas de asociación se crean buscando datos de patrones frecuentes de si-entonces y utilizando un criterio determinado en Soporte y Confianza para definir cuáles son las relaciones más importantes. El soporte es la evidencia de la frecuencia con la que aparece un elemento en los datos proporcionados, ya que la confianza se define por la cantidad de veces que se encuentran verdaderas las declaraciones si-entonces. 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. La Elevación mostrará cuántas veces se espera que se encuentre verdadera la declaración si-entonces.

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

Existen muchas técnicas de minería de datos diferentes que se pueden utilizar para encontrar determinados análisis y resultados; por ejemplo, existe el análisis de clasificación, el análisis de agrupamiento y el análisis de regresión. ^[4] La técnica que se debe utilizar depende de lo que se esté buscando con los datos. Las reglas de asociación se utilizan principalmente para encontrar análisis y una predicción del comportamiento del cliente. En el caso del análisis de clasificación, lo más probable es que se utilice para cuestionar, tomar decisiones y predecir el comportamiento. ^[5] El análisis de agrupamiento se utiliza principalmente cuando no se hacen suposiciones sobre las posibles relaciones dentro de los datos. ^[5] El análisis de regresión se utiliza cuando se desea predecir el valor de una variable dependiente continua a partir de una serie de variables independientes. ^[5]

Beneficios

Existen muchos beneficios en el uso de reglas de asociación, como la búsqueda de patrones que ayuden a comprender las correlaciones y coocurrencias entre conjuntos de datos. Un buen ejemplo del mundo real que utiliza reglas de asociación sería la medicina. La medicina utiliza reglas de asociación para ayudar a diagnosticar a los pacientes. Al diagnosticar a los pacientes, hay muchas variables a considerar, ya que muchas enfermedades comparten síntomas similares. Con el uso de las reglas de asociación, los médicos pueden determinar la probabilidad condicional de una enfermedad comparando las relaciones de síntomas de casos anteriores. ^[6]

Desventajas

Sin embargo, las reglas de asociación también conllevan muchas desventajas diferentes, como encontrar los parámetros y los umbrales 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 se consideren relevantes, pero también podría hacer que el algoritmo tenga un bajo rendimiento. A veces, los algoritmos implementados contendrán demasiadas variables y parámetros. Para alguien que no tenga un buen concepto de minería de datos, esto podría hacer que tenga problemas para comprenderlo. ^[7]

Umbrales

Conjunto de elementos frecuente en red, donde el color del cuadro indica cuántas transacciones contienen la combinación de elementos. Nótese 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} puede tener como máximo elementos. Esto se denomina propiedad de cierre descendente . ^[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 de soporte mínimo 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 soporte es del 30%, el umbral de confianza es del 50%.

La tabla de la izquierda contiene los datos originales sin organizar y la tabla de la derecha está organizada por umbrales. En este caso, el elemento C es mejor que los umbrales de apoyo y confianza, por lo que ocupa el primer lugar. El elemento A ocupa el segundo lugar porque sus valores de umbral son exactos. El elemento D ha alcanzado el umbral de apoyo, pero no el de confianza. El elemento B no ha alcanzado el umbral de apoyo ni el de confianza, por lo que ocupa el último lugar.

Encontrar todos los conjuntos de elementos frecuentes en una base de datos no es una tarea fácil, ya que implica recorrer todos los datos para encontrar todas las posibles combinaciones de elementos de todos los conjuntos de elementos posibles. El conjunto de conjuntos de elementos posibles es el conjunto potencia 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 potencia crecerá exponencialmente en el número de elementos n que estén dentro del conjunto potencia I . Es posible una búsqueda eficiente utilizando la propiedad de cierre hacia abajo del soporte ^{[2] [8]} (también llamada antimonotonía ^[9] ). Esto garantizaría que un conjunto de elementos frecuente y todos sus subconjuntos también sean frecuentes y, por lo tanto, no tendrán conjuntos de elementos infrecuentes como subconjunto de un conjunto de elementos frecuente. 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 artículos 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 diversas medidas de significación e interés. Las restricciones 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 dada. ${\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 requerida ]} 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 el conjunto de elementos aparece 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)}}}}$

Si tomamos como ejemplo la Tabla 2, el conjunto de elementos tiene un apoyo de 1/5=0,2, ya que se da en el 20% de todas las transacciones (1 de cada 5 transacciones). El argumento de apoyo 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] ${\displaystyle X=\{\mathrm {beer,diapers} \}}$

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

Al utilizar antecedentes y consecuentes, un minero de datos puede determinar el respaldo de la compra de varios artículos 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 y tiene un respaldo de 0,4 o 40 %. Esto se debe a que en 2 de cada 5 transacciones, se compra leche y 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 se hace más grande, el respaldo se puede utilizar para encontrar la correlación entre dos o más productos en el ejemplo del supermercado.

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

Si fijamos el umbral de apoyo en ≥0,4 en la Tabla 3, se eliminaría porque no alcanza el umbral mínimo de 0,4. El umbral mínimo se utiliza para eliminar muestras en las que no hay un apoyo o una confianza lo suficientemente fuertes como para considerar que la muestra es 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 (soporte)×(confianza); esto permite a un minero de datos ver las muestras en las que el soporte y la confianza son lo suficientemente altos como para ser resaltados en el conjunto de datos y provocar 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 útil 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 el soporte y el 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. Denotando una transacción por 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 para definir conjuntos de datos más complejos en los que los artículos y los conjuntos de artículos pueden no ser tan fáciles como en nuestro ejemplo del supermercado anterior. Otros ejemplos en los que se puede utilizar el soporte son para encontrar grupos de mutaciones genéticas que trabajan en conjunto para causar una enfermedad, investigar la cantidad de suscriptores que responden a ofertas de actualización y descubrir qué productos de 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 denotado como , es la relación entre las transacciones que contienen tanto X como Y y la cantidad total de valores X presentes, donde X es el antecedente e Y es el consecuente. ${\displaystyle X\Rightarrow Y}$

La confianza también puede interpretarse 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 así:

${\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 las transacciones X e Y dentro del conjunto de datos en relación con las transacciones que contienen solo X. Esto significa que la cantidad de transacciones en X e Y se divide por las que solo contienen 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 en particular demuestra que la regla es correcta el 100% del tiempo 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 compra fruta. Dentro de este conjunto de datos en particular, la fruta se compra un total de 3 veces, y dos de esas veces 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}$

En el caso de conjuntos de datos más grandes, puede resultar útil establecer un umbral mínimo o un porcentaje de corte para la confianza a fin de 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 en los que el umbral mínimo de confianza es 0,5 (50 %). Se omiten todos los datos que no tienen una confianza de al menos 0,5. La generación de umbrales permite que la asociación entre los elementos se fortalezca a medida que se investigan más los datos, haciendo hincapié en aquellos que ocurren de manera simultánea con mayor frecuencia. La tabla utiliza la información de confianza de la Tabla 3 para implementar la columna Apoyo × Confianza, en la que se destaca la relación entre los elementos a través de su confianza y apoyo, en lugar de solo un concepto. La clasificación de las reglas por Apoyo × Confianza multiplica la confianza de una regla en particular con respecto a su apoyo y, a menudo, se implementa para una comprensión más profunda de la relación entre los elementos.

En general, el uso de la confianza en la minería de reglas de asociación es una excelente manera de generar conciencia sobre las relaciones entre los datos. Su mayor beneficio es destacar 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 cada concepto en la minería de reglas de asociación. La desventaja de su uso es que no ofrece múltiples perspectivas de diferencia 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 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 soporte de 0,4 (40%). Por eso es importante observar otros puntos de vista, como Soporte × Confianza, en lugar de confiar únicamente en un concepto incesantemente para definir las relaciones.

Elevar

El levantamiento de una norma 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 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 un valor 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 el que esas dos ocurrencias dependen una de la otra, y hace que esas reglas sean potencialmente útiles para predecir el consecuente en futuros conjuntos de datos.

Si el valor de elevación es < 1, esto nos permite saber que los elementos son sustitutos 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 . ^[16] ${\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 razó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 dividida 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:

• Confianza total ^[17]
• Fuerza colectiva ^[18]
• Apalancamiento ^[19]

^{Tan et al. [20]} y Hahsler ^[21] presentan y comparan varias medidas más. Buscar técnicas que puedan modelar lo que el usuario ha sabido (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ó en particular gracias al artículo de 1993 de Agrawal et al. ^[2] , que ha obtenido más de 23.790 citas según Google Scholar, a abril de 2021, y es, por tanto, uno de los artículos más citados en el campo de la minería de datos. Sin embargo, lo que ahora se denomina "reglas de asociación" ya se introdujo en el artículo de 1966 ^[22] sobre GUHA, un método general de minería de datos desarrollado por Petr Hájek et al. ^[23].

Un uso temprano (alrededor de 1989) del soporte mínimo y la confianza 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 o 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 asociaciones posibles para buscar conjuntos de elementos que parecen estar asociados, existe un gran riesgo de encontrar muchas asociaciones espurias. Se trata de conjuntos de elementos que aparecen juntos con una frecuencia inesperada en los datos, pero solo lo hacen por casualidad. Por ejemplo, supongamos que estamos considerando un conjunto de 10 000 elementos y buscamos reglas que contengan dos elementos en el lado izquierdo y un elemento en el lado derecho. Hay aproximadamente 1 000 000 000 000 de tales reglas. 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 suponemos 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 espurias 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. Es necesario realizar otro paso después para generar reglas a partir de los conjuntos de elementos frecuentes que se encuentran en una base de datos.

Algoritmo a priori

Apriori fue desarrollado 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. Procede mediante la identificación de los elementos individuales frecuentes en la base de datos y su extensión a conjuntos de elementos cada vez más grandes, siempre que dichos conjuntos de elementos aparezcan con la suficiente frecuencia. El nombre del algoritmo es Apriori porque utiliza el conocimiento previo de las propiedades de los conjuntos de elementos frecuentes.

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 extienden un elemento a la vez (un paso conocido como generación de candidatos ) y los grupos de candidatos se prueban contra 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, elimina los candidatos que tienen un subpatrón poco frecuente. De acuerdo con el lema de cierre descendente, el conjunto de candidatos contiene todos los conjuntos de elementos frecuentes de longitud . Después de eso, escanea la base de datos de transacciones para determinar 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 etiquetadas con un carácter del alfabeto. Por ejemplo, una fila podría tener {a, c}, lo que significa que está afectada por la mutación "a" y la mutación "c".

Ahora generaremos el conjunto de elementos frecuentes contando la cantidad de ocurrencias de cada carácter. 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 estableceremos nuestro valor de soporte mínimo en 4, de modo que solo quede {a, d} después de la poda. Ahora utilizaremos el conjunto de elementos frecuentes para crear combinaciones de tripletes. Luego repetiremos el proceso contando las ocurrencias 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 como resultado conjuntos de candidatos grandes. Por ejemplo, un conjunto de 1 elemento frecuente de 10^4 generará un conjunto de 2 elementos candidatos de 10^7. El algoritmo también necesita escanear la base de datos con frecuencia, para ser específico, 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 funciona bien 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 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 de candidatos ni prueba, usa una estructura de datos compacta y solo tiene un escaneo de la base de datos. ^[27]

Algoritmo Eclat

Eclat ^[11] (alt. ECLAT, significa Equivalence Class Transformation) es un algoritmo de retroceso que recorre el gráfico reticular de conjuntos de elementos frecuentes en un estilo 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 propiedad de cierre hacia abajo. Además, casi con certeza utilizará menos memoria ya que DFS tiene una complejidad de espacio menor que BFS.

Para ilustrar esto, supongamos que hay un conjunto de elementos frecuentes {a, b, c}. Un DFS puede comprobar 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 hacia abajo. BFS exploraría cada subconjunto de {a, b, c} antes de comprobarlo 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 tanto para ejecución secuencial como paralela con propiedades de mejora de localidad. ^{[28] [29]}

Algoritmo de crecimiento de FP

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 de frecuencia en el conjunto de datos antes de insertarse para que el árbol pueda procesarse rápidamente. Los elementos de cada transacción que no cumplan con el requisito de compatibilidad mínima 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 genera conjuntos de elementos frecuentes directamente, en lugar de generar elementos candidatos y probarlos en 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 menor soporte, al buscar 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 . Se vuelven a contar los soportes de todos los nodos en el árbol proyectado y cada nodo obtiene la suma de los recuentos de sus hijos. Los nodos (y, por lo tanto, los subárboles) que no cumplen con el soporte mínimo se podan. El crecimiento recursivo finaliza cuando ningún elemento individual condicional a cumple con el umbral de soporte mínimo. 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 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

ASOCIACIÓN

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

Búsqueda en 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 el 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 en el popular sistema de descubrimiento de asociaciones Magnum Opus.

Ciencia

Una historia famosa sobre la extracción 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 también tienden a comprar cerveza. Esta anécdota se hizo popular como un ejemplo de cómo se pueden encontrar reglas de asociación inesperadas a partir de datos cotidianos. Hay diversas opiniones sobre qué parte de la historia es cierta. ^[36] Daniel Powers dice: ^[36]

En 1992, Thomas Blischok, gerente 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 farmacias Osco. Se desarrollaron consultas a bases de datos para identificar afinidades. El análisis "descubrió que entre las 5:00 y las 7:00 p. m. los consumidores compraban cerveza y pañales". Los gerentes de Osco NO explotaron la relación entre la cerveza y los pañales moviendo los productos más cerca 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 en las que cada elemento puede tener varias relaciones. Estas relaciones indican relaciones indirectas entre las entidades. Considere la siguiente MRAR en la que el primer elemento consta de tres relaciones vive en , cerca y húmedo : “Aquellos que viven en un lugar cercano a una ciudad con un tipo de clima húmedo y también son menores de 20 años , su estado de salud es bueno”. Estas reglas de asociación se pueden extraer de datos RDBMS o de datos de la web semántica. ^[37] ${\displaystyle \implies }$

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

El aprendizaje de clases ponderadas es otra forma de aprendizaje asociativo en el que se pueden asignar pesos a las clases para centrarse en un tema particular de preocupación para el consumidor de los resultados de minería de datos.

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

El descubrimiento de patrones k-óptimos 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 de conjuntos de elementos frecuentes aproximados es una versión relajada de la minería de conjuntos de elementos frecuentes que permite que algunos de los elementos en algunas de las filas sean 0. ^[41]

Reglas de asociación generalizadas: taxonomía jerárquica (jerarquía de conceptos)

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

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

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

La agrupación de subespacios , un tipo específico de agrupación de datos de alta dimensión , se basa también en muchas variantes en la propiedad de cierre hacia abajo 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]

Véase 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 fuertes , en Piatetsky-Shapiro, Gregory; y Frawley, William J.; eds., Descubrimiento de conocimiento en bases de datos , AAAI/MIT Press, Cambridge, MA.
2. Agrawal, R.; Imieliński, T.; Swami, A. (1993). "Extracción de reglas de asociación entre conjuntos de elementos en bases de datos de gran tamaño". Actas de la conferencia internacional ACM SIGMOD de 1993 sobre gestión de datos - SIGMOD '93 . p. 207. CiteSeerX  10.1.1.40.6984 . doi :10.1145/170035.170072. ISBN 978-0897915922.S2CID 490415  .
3. Garcia, Enrique (2007). "Inconvenientes y soluciones de la aplicación de minería de reglas de asociación en sistemas de gestión del aprendizaje" (PDF) . Sci2s . Archivado (PDF) desde el original el 23 de diciembre de 2009.
4. "Técnicas de minería de datos: las 5 principales a tener en cuenta". Precisamente . 2021-11-08 . Consultado el 2021-12-10 .
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 (Association Rule Mining)?". SearchBusinessAnalytics . Consultado el 10 de diciembre de 2021 .
7. "Desventajas y soluciones de la aplicación de la minería de reglas de asociación en sistemas de gestión del aprendizaje". ResearchGate . Consultado el 10 de diciembre de 2021 .
8. Tan, 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.S2CID1080975  .​
10. Agrawal, Rakesh; y Srikant, Ramakrishnan; Algoritmos rápidos para extraer reglas de asociación en bases de datos grandes Archivado el 25 de febrero de 2015 en Wayback Machine , en Bocca, Jorge B.; Jarke, Matthias; y Zaniolo, Carlo; editores, Actas de la 20.ª Conferencia Internacional sobre Bases de Datos Muy Grandes (VLDB), Santiago de Chile, septiembre de 1994 , páginas 487-499
11. Zaki, MJ (2000). "Algoritmos escalables para minería de asociaciones". IEEE Transactions on Knowledge and Data Engineering . 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). Descubrimiento de conocimiento en datos. doi :10.1002/9781118874059. ISBN 9781118874059.
13. Hahsler, Michael (2005). "Introducción a arules – Un entorno computacional para extraer reglas de asociación y conjuntos de elementos frecuentes" (PDF) . Journal of Statistical Software . doi : 10.18637/jss.v014.i15 . Archivado desde el original (PDF) el 2019-04-30 . Consultado el 2016-03-18 .
14. Wong, Pak (1999). "Visualización de reglas de asociación para minería de texto" (PDF) . Laboratorio de redes neuronales artificiales de la 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 --- una revisión general y 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). "Conteo dinámico de conjuntos de elementos y reglas de implicación para datos de cestas 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.S2CID15385590  .​
17. Omiecinski, ER (2003). "Medidas de interés alternativas para asociaciones mineras en bases de datos". IEEE Transactions on Knowledge and Data Engineering . 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 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 fuertes , Knowledge Discovery in Databases, 1991, págs. 229-248
20. Tan, Pang-Ning; Kumar, Vipin; Srivastava, Jaideep (2004). "Selección de la medida objetiva correcta 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". Computing . 1 (4): 293–308. doi :10.1007/BF02345483. S2CID  10511114.
23. Hájek, Petr; Rauch, Jan; 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 clase en 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). "Descubrimiento de 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}}: Requiere citar revista |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 conocimiento . 1 (4): 343–373. doi :10.1023/A:1009773317876. S2CID  10038675.
30. Han (2000). "Extracción 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.S2CID6059661  .​
31. Witten, Frank, Hall: Herramientas y técnicas prácticas de aprendizaje automático para minería de datos, 3.ª 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: Un algoritmo admisible eficiente para búsqueda desordenada , Journal of Artificial Intelligence Research 3, Menlo Park, CA: AAAI Press, pp. 431-465 acceso en línea
34. Bayardo, Roberto J. Jr.; Agrawal, Rakesh; Gunopulos, Dimitrios (2000). "Minería de reglas basada en restricciones en bases de datos grandes y densas". Minería de datos y descubrimiento de conocimiento . 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. "Noticias DSS: Vol. 3, No. 23".
37. Ramezani, Reza, Mohamad Saraee y Mohammad Ali Nematbakhsh; MRAR: Minería de reglas de asociación de múltiples relaciones , Journal of Computing and Security, 1, n.º 2 (2014)
38. GI Webb y S. Butler y D. Newlands (2003). On Detecting Differences Between Groups (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". Computer . 36 (11): 22–29. doi :10.1109/MC.2003.1244531.
40. Wong, AKC; Yang Wang (1997). "Descubrimiento de patrones de orden superior a partir de datos de valor discreto". IEEE Transactions on Knowledge and Data Engineering . 9 (6): 877–893. CiteSeerX 10.1.1.189.1704 . doi :10.1109/69.649314. 
41. Liu, Jinze; Paulsen, Susan; Sun, Xing; Wang, Wei; Nobel, Andrew; Prins, Jan (2006). "Extracción de conjuntos de elementos frecuentes aproximados en presencia de ruido: algoritmo y análisis". Actas de la Conferencia internacional SIAM de 2006 sobre extracción 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 la minería de 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. King, RD; Srinivasan, A.; Dehaspe, L. (febrero de 2001). "Warmr: una herramienta de minería de datos para datos químicos". J Comput Aided Mol Des . 15 (2): 173–81. Bibcode :2001JCAMD..15..173K. doi :10.1023/A:1008171016861. PMID  11272703. S2CID  3055046.

Bibliografías

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