Aprendizaje de reglas de asociación

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. En cualquier transacción determinada con una variedad de artículos, las reglas de asociación tienen como objetivo descubrir las reglas que determinan cómo o por qué se conectan ciertos artículos.

Basado en el concepto de reglas fuertes, Rakesh Agrawal, Tomasz Imieliński y Arun Swami presentaron reglas de asociación para descubrir regularidades entre productos en datos de transacción a gran escala registrados por sistemas de puntos de venta (POS) en supermercados. Por ejemplo, la regla ${displaystyle {mathrm {onions,potatoes} 'Rightarrow {mathrm {burger} {}}$ encontrado en los datos de venta de un supermercado indicaría que si un cliente compra cebollas y patatas juntas, es probable que también compre carne de hamburguesa. Esa información puede utilizarse como base para las decisiones sobre actividades de marketing como, por ejemplo, la fijación de precios promocionales o la colocación de productos.

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.

Definición

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

Vamos ${displaystyle Yo...$ ser un conjunto de n atributos binarios llamados Temas.

Vamos ${displaystyle D={t_{1},t_{2},ldotst_{m}}$ ser un conjunto de transacciones llamadas el base de datos.

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

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

${displaystyle XRightarrow Sí.$, donde ${displaystyle X,Ysubseteq Yo...$.

En Agrawal, Imieliński, Swami a Regla se define sólo entre un conjunto y un solo elemento, ${displaystyle XRightarrow I_{j}$ para ${displaystyle i_{j}in I}$.

Cada regla está compuesta por dos conjuntos diferentes de artículos, también conocido como ítems, X y Y, donde X se llama antecedentes o lado izquierdo (LHS) y Y consiguiente o lado derecho (RHS). El antecedente es ese elemento que se puede encontrar en los datos mientras que el consiguiente es el elemento encontrado cuando se combina con el antecedente. La declaración ${displaystyle XRightarrow Sí.$ a menudo se lee como si X entonces Y, donde el antecedente (X) es el si y el consiguienteY) es el entonces. Esto simplemente implica que, en teoría, cuando X ocurre en un conjunto de datos, entonces Y lo hará también.

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 mediante 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 extracción 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. 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. El análisis de agrupamiento se utiliza principalmente cuando no se hacen suposiciones sobre las relaciones probables dentro de los datos. El análisis de regresión se utiliza cuando se desea predecir el valor de un dependiente continuo a partir de varias variables independientes.

Beneficios

El uso de reglas de asociación tiene muchos beneficios, como encontrar el patrón que ayuda 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.

Desventajas

Sin embargo, las reglas de asociación también conllevan muchas desventajas 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.

Umbrales

Cuando utilices reglas de Asociación, lo más probable es que solo utilices 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 ítems frecuentes que están en la base de datos.
2. Un umbral mínimo de confianza a los ítems frecuentes encontrados 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 elemento B no ha alcanzado el umbral ni de Apoyo ni de Confianza y por eso ocupa el último lugar.

Encontrar todos los ítems frecuentes en una base de datos no es una tarea fácil ya que implica pasar por todos los datos para encontrar todas las combinaciones posibles de elementos de todos los ítems posibles. El conjunto de posibles ítems es el poder establecido sobre I y tiene tamaño ${displaystyle 2^{n}-1}$ por supuesto esto significa excluir el conjunto vacío que no se considera un ítem válido. Sin embargo, el tamaño del conjunto de potencia crecerá exponencialmente en el número de elementos n que está dentro del sistema de poder I. Una búsqueda eficiente es posible utilizando propiedad de cierre hacia abajo apoyo (también llamado anti-monotonicidad). Esto garantizaría que un ítem frecuente y todos sus subconjuntos también sean frecuentes y por lo tanto no tendrán ítems infrecuentes como subconjunto de un ítem frecuente. Explorar esta propiedad, algoritmos eficientes (por ejemplo, Apriori y Eclat) pueden encontrar todos los ítems frecuentes.

Conceptos útiles

Para ilustrar los conceptos, utilizamos un pequeño ejemplo del dominio del supermercado. En el cuadro 2 se muestra una pequeña base de datos que contiene los elementos donde, en cada entrada, el valor 1 significa la presencia del objeto 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} {}}$.

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

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

Vamos ${displaystyle X,Y}$ ser ítems, ${displaystyle XRightarrow Sí.$ una norma de asociación y T a set of transactions of a given database.

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, y los conjuntos de datos a menudo contienen miles o millones de transacciones.

Soporte

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 ${displaystyle {text{support}}=P(Acap B)={frac {text{number of transactions containing }}A{text{ and }}}B)}{text{ (total number of transactions)}}}}}}}}}}}}}}}} {text{f}}}}}}}$ donde A y B son conjuntos de elementos separados que ocurren al mismo tiempo en una transacción.

Utilizando el cuadro 2 como ejemplo, el ítem ${displaystyle X={mathrm {beer,diapers} {}}$ tiene un apoyo 1/5=0.2 ya que se produce en el 20% de todas las transacciones (1 de 5 transacciones). El argumento de apoyo a X es un conjunto de condiciones previas, y por lo tanto se vuelve más restrictivo a medida que crece (en lugar de más inclusivo).

Además, el ítem ${displaystyle Y={mathrm {milk,bread,butter} {}}$ tiene un apoyo 1/5=0.2 como aparece en el 20% de todas las transacciones también.

Cuando se utilizan antecedentes y consecuentes, permite que un minero de datos determine 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 fijamos el umbral de soporte a ≥0.4 en la tabla 3, entonces el ${displaystyle {mathrm {milk} 'Rightarrow {mathrm {eggs} {}}$ sería eliminado ya que no alcanzó el umbral mínimo de 0.4. El umbral mínimo se utiliza para eliminar muestras donde no hay un soporte suficientemente fuerte o confianza para considerar la muestra como importante o interesante en el conjunto de datos.

Otra manera de encontrar muestras interesantes es encontrar el valor de (apoyo)×(confianza); esto permite a un minero de datos ver las muestras donde el soporte y la confianza son lo suficientemente altos como para ser resaltado en el conjunto de datos e impulsar 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 apoyo de X con respecto a T se define como la proporción de transacciones en el conjunto de datos que contiene el ítem X. Denotar una transacción ${displaystyle (i,t)}$ Donde i es el identificador único de la transacción y t es su ítem, el soporte puede ser escrito como:

${displaystyle mathrm {support,of,X} ={frac {ы{(i,t)in T:Xsubseteq - ¿Qué?$

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.

Confianza

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

Con respecto a T, el valor de confianza de una regla de asociación, a menudo denotado como ${displaystyle XRightarrow Sí.$, es la relación de las transacciones que contienen ambas X y Y a la cantidad total de X valores presentes, donde X es el antecedente y Y es el consiguiente.

La confianza también se puede interpretar como una estimación de la probabilidad condicional ${displaystyle P(E_{Y}$, la probabilidad de encontrar el RHS de la regla en las transacciones con la condición de que estas transacciones también contengan el LHS.

Comúnmente se representa como:

${displaystyle mathrm {conf} (XRightarrow Y)=P(Y sometidaX)={frac {mathrm {supp} {cap Y)}{mathrm {supp}}={frac {text{number of transactions containing }}X{text{}}}}{text{}{}{number}{}{}{}{}{}{}{}{}{}{}{text{}{}{}{}{}{}{}{}{}{}{}{}{number}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{}{}{}$

La ecuación ilustra que la confianza se puede calcular calculando la coocurrencia de las transacciones X y Y dentro del conjunto de datos en proporción a transacciones que contienen solo X. Esto significa que el número de transacciones tanto en X como en Y se divide por aquellos que están justo en X.

Por ejemplo, el cuadro 2 muestra la regla ${displaystyle {mathrm {butter,bread} "Rightarrow"$ que tiene una confianza ${fnMicroc} {1/5}{1/5}={frac} {0.2}{0.2}=1.0}$ 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 al 100% del tiempo para las transacciones que contienen mantequilla y pan. La regla ${displaystyle {mathrm {fruit} 'Rightarrow {mathrm {eggs} }$, sin embargo, tiene una confianza ${fnMicroc} {2/5}{3/5}={frac {0.4}{0.6}=0,67} {0}} {0}} {0}} {0}} {0} {0}} {0}}}} {0} {0}}}} {0}}}}} {0}}}}}} {0}} {0}}} {0}}} {0}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {\\\\\\\\\\\\\\\\\\\\\\\\\\\\\f}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$. Esto sugiere que los huevos se compran 67% de las veces que se trae la fruta. Dentro de este conjunto de datos particular, la fruta se compra un total de 3 veces, con dos de esos tiempos consistentes en compras de huevo.

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.

Ascensor

La elevación de una regla se define como:

${displaystyle mathrm {lift} (XRightarrow Y)={frac {mathrm {supp} {cap Y)}{mathrm {supp} (X)times mathrm {supp}}}}}}}}}}}$

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

Por ejemplo, la regla ${displaystyle {mathrm {milk,bread} 'Rightarrow {mathrm {butter} {}}$ tiene un ascensor ${displaystyle {frac {0.2}{0.4times 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 el ascensor es > 1, que nos permite saber el grado en que esas dos ocurrencias dependen una de la otra, y hace que esas reglas sean potencialmente útiles para predecir el consecuente en conjuntos de datos futuros.

Si el ascensor es < 1, que 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 del incremento es que considera tanto el soporte de la regla como el conjunto de datos general.

Convicción

El convicción de una norma se define como ${displaystyle mathrm {conv} (XRightarrow Y)={frac {1-mathrm {supp} (Y)}{1-mathrm {conf} {XRightarrow Y)}}}}}$.

Por ejemplo, la regla ${displaystyle {mathrm {milk,bread} 'Rightarrow {mathrm {butter} {}}$ tiene una condena ${displaystyle {frac {1-0.4}{1-0.5}=1.2}$, y puede ser interpretado como la relación de la frecuencia esperada que X ocurre sin Y (es decir, la frecuencia que la regla hace una predicción incorrecta) si X y Y fueron independientes divididos por la frecuencia observada de predicciones incorrectas. En este ejemplo, el valor de convicción de 1.2 muestra que la regla ${displaystyle {mathrm {milk,bread} 'Rightarrow {mathrm {butter} {}}$ sería incorrecto 20% más a menudo (1.2 veces más a menudo) si la asociación entre X y Y era puramente aleatoria oportunidad.

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
• Fuerza colectiva
• Leverage

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

Historia

El concepto de reglas de asociación se popularizó especialmente gracias al artículo de 1993 de Agrawal et al., que ha obtenido más de 23.790 citas según Google Scholar, hasta abril de 2021, y por lo tanto es 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" se introduce ya en el artículo de 1966 sobre GUHA, un método general de extracción de datos desarrollado por Petr Hájek et al.

Un uso temprano (circa 1989) del apoyo mínimo y la confianza para encontrar todas las reglas de asociación es el marco de modelado basado en las características, que encontró todas las reglas con ${displaystyle mathrm {supp} (X)}$ y ${displaystyle mathrm {conf} (XRightarrow Y)}$ mayor que las limitaciones definidas por el usuario.

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 controla este riesgo y, en la mayoría de los casos, reduce el riesgo de encontrar cualquier asociación falsa 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.

Descripción general: Apriori utiliza una estrategia "de abajo hacia arriba" enfoque, 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 está afectada por la mutación 'a' y mutación 'c'.

Ahora generaremos el conjunto de elementos frecuentes contando el número de apariciones 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 haremos que nuestro valor mínimo de soporte 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:

A priori 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.

Algoritmo de Éclat

Eclat (alt. ECLAT, significa Transformación de clases de equivalencia) 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 tanto para ejecución secuencial como paralela con propiedades que mejoran la localidad.

Algoritmo de crecimiento FP

FP significa patrón frecuente.

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 encabezados". En el segundo paso, construye la estructura del árbol FP insertando transacciones en un intento.

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 encabezados es decir, el artículo con el apoyo más pequeño encontrando todas las transacciones ordenadas que terminan en ese artículo. Llame a este artículo ${displaystyle Yo...$.

Se crea un nuevo árbol condicional que es el árbol FP original proyectado sobre ${displaystyle Yo...$. Los soportes de todos los nodos en el árbol proyectado se recuento con cada nodo obteniendo la suma de sus hijos cuenta. Nodos (y por lo tanto subárboles) que no cumplen con el soporte mínimo son podados. El crecimiento recuperativo termina cuando no hay elementos individuales condicionados a ${displaystyle Yo...$ cumplir con el umbral mínimo de soporte. Los caminos resultantes de raíz a raíz ${displaystyle Yo...$ serán artículos frecuentes. Después de este paso, el procesamiento continúa con el siguiente elemento de cabecera menos soportado del árbol FP original.

Una vez completado el proceso recursivo, se han encontrado todos los conjuntos de elementos frecuentes, y comienza la creación de reglas de asociación.

Otros

ASOCIACIÓN

El procedimiento ASSOC es un método GUHA que mide para las reglas de asociación generalizada usando operaciones rápidas de bitstrings. Las reglas de asociación minadas por este método son más generales que las de los apriori, por ejemplo "temas" pueden conectarse tanto con la conjunción como con las disyunciones y la relación entre antecedente y consecuencia de la norma no se limita a establecer el mínimo apoyo y confianza como en apriori: puede utilizarse una combinación arbitraria de medidas de interés apoyadas.

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. Inicialmente utilizado para encontrar reglas para un consecuente fijo, posteriormente se ha ampliado para encontrar reglas con cualquier elemento como consecuente. La búsqueda OPUS es la tecnología central del popular sistema de descubrimiento de asociaciones Magnum Opus.

Conocimiento

Una historia famosa sobre la minería de reglas de asociación es la de "cerveza y pañal" historia. 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. Daniel Powers dice:

En 1992, Thomas Blischok, gerente de un grupo de consultoría minorista en Teradata, y su personal preparó un análisis de 1,2 millones de cestas de mercado de alrededor de 25 tiendas Osco Drug. Se elaboraron consultas de base de datos para identificar afinidades. El análisis "descubrió que entre las 5:00 y las 7:00 p.m. los consumidores compraron cerveza y pañales". Los gerentes de Osco no aprovecharon la relación de cerveza y pañales al acercar los productos en los estantes.

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

Reglas de asociación de relaciones múltiples (MRAR): Estas son reglas de asociación donde cada artículo puede tener varias relaciones. Estas relaciones indican relaciones indirectas entre las entidades. Considerar el siguiente MRAR donde el primer tema consta de tres relaciones vivir en, cerca y húmedo"Aquellos que vivir en un lugar que es cerca una ciudad con húmedo tipo climático y también son más joven 20 ${displaystyle implies }$ sus estado de salud es bueno”. Tales reglas de asociación pueden extraerse de los datos de RDBMS o datos de la web semánticos.

aprendizaje de conjuntos de contrastes es una forma de aprendizaje asociativo. Los aprendices de conjuntos de contraste utilizan reglas que difieren significativamente en su distribución entre los subconjuntos.

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.

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.

descubrimiento de patrones óptimos K 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.

conjunto de elementos frecuentes aproximado 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.

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

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

Reglas de asociación de datos de intervalo p. dividir la edad en incrementos de 5 años

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.

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.

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.