Association rule learning

Method for discovering interesting relations between variables in databases

Association rule learning is a rule-based machine learning method for discovering interesting relations between variables in large databases. It is intended to identify strong rules discovered in databases using some measures of interestingness.^[1] In any given transaction with a variety of items, association rules are meant to discover the rules that determine how or why certain items are connected.

Based on the concept of strong rules, Rakesh Agrawal, Tomasz Imieliński and Arun Swami^[2] introduced association rules for discovering regularities between products in large-scale transaction data recorded by point-of-sale (POS) systems in supermarkets. For example, the rule ${\displaystyle \{\mathrm {onions,potatoes} \}\Rightarrow \{\mathrm {burger} \}}$ found in the sales data of a supermarket would indicate that if a customer buys onions and potatoes together, they are likely to also buy hamburger meat. Such information can be used as the basis for decisions about marketing activities such as, e.g., promotional pricing or product placements.

In addition to the above example from market basket analysis, association rules are employed today in many application areas including Web usage mining, intrusion detection, continuous production, and bioinformatics. In contrast with sequence mining, association rule learning typically does not consider the order of items either within a transaction or across transactions.

The association rule algorithm itself consists of various parameters that can make it difficult for those without some expertise in data mining to execute, with many rules that are arduous to understand.^[3]

Definition

A Venn Diagram to show the associations between itemsets X and Y of a dataset. All transactions that contain item X are located in the white, left portion of the circle, while those containing Y are colored red and on the right. Any transaction containing both X and Y are located in the middle and are colored pink. Multiple concepts can be used to depict information from this graph. For example, if one takes all of the transactions in the pink section and divided them by the total amount of transactions (transactions containing X (white) + transactions containing Y(red)), the output would be known as the support. An instance of getting the result of a method known as the confidence, one can take all of the transactions in the middle (pink) and divide them by all transactions that contain Y (red and pink). In this case, Y is the antecedent and X is the consequent.

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 Incremento 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 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. ^[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 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. ^[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.

The Support Threshold is 30%, Confidence Threshold is 50%

The Table on the left is the original unorganized data and the table on the right is organized by the thresholds. In this case Item C is better than the thresholds for both Support and Confidence which is why it is first. Item A is second because its threshold values are spot on. Item D has met the threshold for Support but not Confidence. Item B has not met the threshold for either Support or Confidence and that is why it is last.

To find all the frequent itemsets in a database is not an easy task since it involves going through all the data to find all possible item combinations from all possible itemsets. The set of possible itemsets is the power set over I and has size ${\displaystyle 2^{n}-1}$ , of course this means to exclude the empty set which is not considered to be a valid itemset. However, the size of the power set will grow exponentially in the number of item n that is within the power set I. An efficient search is possible by using the downward-closure property of support^[2][8] (also called anti-monotonicity^[9]). This would guarantee that a frequent itemset and all its subsets are also frequent and thus will have no infrequent itemsets as a subset of a frequent itemset. Exploiting this property, efficient algorithms (e.g., Apriori^[10] and Eclat^[11]) can find all frequent itemsets.

Useful Concepts

To illustrate the concepts, we use a small example from the supermarket domain. Table 2 shows a small database containing the items where, in each entry, the value 1 means the presence of the item in the corresponding transaction, and the value 0 represents the absence of an item in that transaction. The set of items is ${\displaystyle I=\{\mathrm {milk,bread,butter,beer,diapers,eggs,fruit} \}}$.

An example rule for the supermarket could be ${\displaystyle \{\mathrm {butter,bread} \}\Rightarrow \{\mathrm {milk} \}}$ meaning that if butter and bread are bought, customers also buy milk.

In order to select interesting rules from the set of all possible rules, constraints on various measures of significance and interest are used. The best-known constraints are minimum thresholds on support and confidence.

Let ${\displaystyle X,Y}$ be itemsets, ${\displaystyle X\Rightarrow Y}$ an association rule and T a set of transactions of a given database.

Note: this example is extremely small. In practical applications, a rule needs a support of several hundred transactions before it can be considered statistically significant,^{[citation needed]} and datasets often contain thousands or millions of transactions.

Support

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 tanto X como Y con respecto a 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 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\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 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.

If the lift is > 1, that lets us know the degree to which those two occurrences are dependent on one another, and makes those rules potentially useful for predicting the consequent in future data sets.

If the lift is < 1, that lets us know the items are substitute to each other. This means that presence of one item has negative effect on presence of other item and vice versa.

The value of lift is that it considers both the support of the rule and the overall data set.^[13]

Conviction

The conviction of a rule is defined as ${\displaystyle \mathrm {conv} (X\Rightarrow Y)={\frac {1-\mathrm {supp} (Y)}{1-\mathrm {conf} (X\Rightarrow Y)}}}$.^[16]

For example, the rule ${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$ has a conviction of ${\displaystyle {\frac {1-0.4}{1-0.5}}=1.2}$, and can be interpreted as the ratio of the expected frequency that X occurs without Y (that is to say, the frequency that the rule makes an incorrect prediction) if X and Y were independent divided by the observed frequency of incorrect predictions. In this example, the conviction value of 1.2 shows that the rule ${\displaystyle \{\mathrm {milk,bread} \}\Rightarrow \{\mathrm {butter} \}}$ would be incorrect 20% more often (1.2 times as often) if the association between X and Y was purely random chance.

Alternative measures of interestingness

In addition to confidence, other measures of interestingness for rules have been proposed. Some popular measures are:

• All-confidence^[17]
• Collective strength^[18]
• Leverage^[19]

Several more measures are presented and compared by Tan et al.^[20] and by Hahsler.^[21] Looking for techniques that can model what the user has known (and using these models as interestingness measures) is currently an active research trend under the name of "Subjective Interestingness."

History

The concept of association rules was popularized particularly due to the 1993 article of Agrawal et al.,^[2] which has acquired more than 23,790 citations according to Google Scholar, as of April 2021, and is thus one of the most cited papers in the Data Mining field. However, what is now called "association rules" is introduced already in the 1966 paper^[22] on GUHA, a general data mining method developed by Petr Hájek et al.^[23]

An early (circa 1989) use of minimum support and confidence to find all association rules is the Feature Based Modeling framework, which found all rules with ${\displaystyle \mathrm {supp} (X)}$ and ${\displaystyle \mathrm {conf} (X\Rightarrow Y)}$ greater than user defined constraints.^[24]

Statistically sound associations

One limitation of the standard approach to discovering associations is that by searching massive numbers of possible associations to look for collections of items that appear to be associated, there is a large risk of finding many spurious associations. These are collections of items that co-occur with unexpected frequency in the data, but only do so by chance. For example, suppose we are considering a collection of 10,000 items and looking for rules containing two items in the left-hand-side and 1 item in the right-hand-side. There are approximately 1,000,000,000,000 such rules. If we apply a statistical test for independence with a significance level of 0.05 it means there is only a 5% chance of accepting a rule if there is no association. If we assume there are no associations, we should nonetheless expect to find 50,000,000,000 rules. Statistically sound association discovery^[25][26] controls this risk, in most cases reducing the risk of finding any spurious associations to a user-specified significance level.

Algorithms

Many algorithms for generating association rules have been proposed.

Some well-known algorithms are Apriori, Eclat and FP-Growth, but they only do half the job, since they are algorithms for mining frequent itemsets. Another step needs to be done after to generate rules from frequent itemsets found in a database.

Apriori algorithm

Apriori is given by R. Agrawal and R. Srikant in 1994 for frequent item set mining and association rule learning. It proceeds by identifying the frequent individual items in the database and extending them to larger and larger item sets as long as those item sets appear sufficiently often. The name of the algorithm is Apriori because it uses prior knowledge of frequent itemset properties.

The control flow diagram for the Apriori algorithm

Overview: Apriori uses a "bottom up" approach, where frequent subsets are extended one item at a time (a step known as candidate generation), and groups of candidates are tested against the data. The algorithm terminates when no further successful extensions are found. Apriori uses breadth-first search and a Hash tree structure to count candidate item sets efficiently. It generates candidate item sets of length  from item sets of length . Then it prunes the candidates which have an infrequent sub pattern. According to the downward closure lemma, the candidate set contains all frequent -length item sets. After that, it scans the transaction database to determine frequent item sets among the candidates.

Example: Assume that each row is a cancer sample with a certain combination of mutations labeled by a character in the alphabet. For example a row could have {a, c} which means it is affected by mutation 'a' and mutation '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 reticular 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 en . 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 respaldadas.

búsqueda OPUS

OPUS is an efficient algorithm for rule discovery that, in contrast to most alternatives, does not require either monotone or anti-monotone constraints such as minimum support.^[33] Initially used to find rules for a fixed consequent^[33][34] it has subsequently been extended to find rules with any item as a consequent.^[35] OPUS search is the core technology in the popular Magnum Opus association discovery system.

Lore

A famous story about association rule mining is the "beer and diaper" story. A purported survey of behavior of supermarket shoppers discovered that customers (presumably young men) who buy diapers tend also to buy beer. This anecdote became popular as an example of how unexpected association rules might be found from everyday data. There are varying opinions as to how much of the story is true.^[36] Daniel Powers says:^[36]

In 1992, Thomas Blischok, manager of a retail consulting group at Teradata, and his staff prepared an analysis of 1.2 million market baskets from about 25 Osco Drug stores. Database queries were developed to identify affinities. The analysis "did discover that between 5:00 and 7:00 p.m. that consumers bought beer and diapers". Osco managers did NOT exploit the beer and diapers relationship by moving the products closer together on the shelves.

Other types of association rule mining

Multi-Relation Association Rules (MRAR): These are association rules where each item may have several relations. These relations indicate indirect relationships between the entities. Consider the following MRAR where the first item consists of three relations live in, nearby and humid: “Those who live in a place which is nearby a city with humid climate type and also are younger than 20 ${\displaystyle \implies }$ their health condition is good”. Such association rules can be extracted from RDBMS data or semantic web data.^[37]

Contrast set learning is a form of associative learning. Contrast set learners use rules that differ meaningfully in their distribution across subsets.^[38][39]

Weighted class learning is another form of associative learning where weights may be assigned to classes to give focus to a particular issue of concern for the consumer of the data mining results.

High-order pattern discovery facilitates the capture of high-order (polythetic) patterns or event associations that are intrinsic to complex real-world data.^[40]

K-optimal pattern discovery provides an alternative to the standard approach to association rule learning which requires that each pattern appear frequently in the data.

Approximate Frequent Itemset mining is a relaxed version of Frequent Itemset mining that allows some of the items in some of the rows to be 0.^[41]

Generalized Association Rules hierarchical taxonomy (concept hierarchy)

Quantitative Association Rules categorical and quantitative data

Interval Data Association Rules e.g. partition the age into 5-year-increment ranged

Sequential pattern mining discovers subsequences that are common to more than minsup (minimum support threshold) sequences in a sequence database, where minsup is set by the user. A sequence is an ordered list of transactions.^[42]

Subspace Clustering, a specific type of clustering high-dimensional data, is in many variants also based on the downward-closure property for specific clustering models.^[43]

Warmr, shipped as part of the ACE data mining suite, allows association rule learning for first order relational rules.^[44]

See also

• Sequence mining
• Production system (computer science)
• Learning classifier system
• Rule-based machine learning

References

1. Piatetsky-Shapiro, Gregory (1991), Discovery, analysis, and presentation of strong rules, in Piatetsky-Shapiro, Gregory; and Frawley, William J.; eds., Knowledge Discovery in Databases, AAAI/MIT Press, Cambridge, MA.
2. Agrawal, R.; Imieliński, T.; Swami, A. (1993). "Mining association rules between sets of items in large databases". Proceedings of the 1993 ACM SIGMOD international conference on Management of data - SIGMOD '93. p. 207. CiteSeerX 10.1.1.40.6984. doi:10.1145/170035.170072. ISBN 978-0897915922. S2CID 490415.
3. Garcia, Enrique (2007). "Drawbacks and solutions of applying association rule mining in learning management systems" (PDF). Sci2s. Archived (PDF) from the original on 2009-12-23.
4. "Data Mining Techniques: Top 5 to Consider". Precisely. 2021-11-08. Retrieved 2021-12-10.
5. "16 Data Mining Techniques: The Complete List - Talend". Talend - A Leader in Data Integration & Data Integrity. Retrieved 2021-12-10.
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 conocimiento 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