Algoritmo a priori – Part 1

Requisito previo: conjunto de elementos frecuentes en el conjunto de datos (minería de reglas de asociación) R. Agrawal y R. Srikant proporcionan un algoritmo a priori en 1994 para encontrar conjuntos de elementos frecuentes en un conjunto de datos para la regla de asociación booleana
. El nombre del algoritmo es A priori porque utiliza el conocimiento previo de las propiedades frecuentes del conjunto de elementos. Aplicamos un enfoque iterativo o una búsqueda por niveles en la que se utilizan conjuntos de elementos k frecuentes para encontrar conjuntos de elementos k+1.

Para mejorar la eficiencia de la generación nivelada de conjuntos de elementos frecuentes, se usa una propiedad importante llamada propiedad Apriori que ayuda a reducir el espacio de búsqueda.

Propiedad a priori:
todos los subconjuntos no vacíos del conjunto de elementos frecuentes deben ser frecuentes. El concepto clave del algoritmo Apriori es su anti-monotonicidad de la medida de soporte. A priori supone que

Todos los subconjuntos de un conjunto de elementos frecuentes deben ser frecuentes (propiedad a priori).
Si un conjunto de elementos es infrecuente, todos sus superconjuntos serán infrecuentes.

Antes de comenzar a comprender el algoritmo, revise algunas definiciones que se explican en mi publicación anterior.
Considere el siguiente conjunto de datos y encontraremos conjuntos de elementos frecuentes y generaremos reglas de asociación para ellos.

el recuento mínimo de soporte es 2
la confianza mínima es 60%

Paso 1: K = 1
(I) Cree una tabla que contenga el recuento de soporte de cada elemento presente en el conjunto de datos: llamado C1 (conjunto de candidatos)

(II) compare el recuento de soporte del elemento del conjunto de candidatos con el recuento de soporte mínimo (aquí min_support=2 si support_count de los elementos del conjunto de candidatos es menor que min_support, elimine esos elementos). Esto nos da el conjunto de elementos L1.

Paso-2: K=2

• Genere el conjunto de candidatos C2 utilizando L1 (esto se denomina paso de unión). La condición de unir L _k-1 y L _k-1 es que debe tener (K-2) elementos en común.
• Verifique que todos los subconjuntos de un conjunto de elementos sean frecuentes o no y, si no son frecuentes, elimine ese conjunto de elementos. (Ejemplo de subconjunto de {I1, I2} son {I1}, {I2} son frecuentes. Verifique cada conjunto de elementos)
• Ahora encuentre el recuento de soporte de estos conjuntos de elementos buscando en el conjunto de datos.


(II) compare el recuento de soporte del candidato (C2) con el recuento de soporte mínimo (aquí min_support=2 si support_count del elemento del conjunto de candidatos es menor que min_support, luego elimine esos elementos) esto nos da el conjunto de elementos L2.



Paso 3:

• Genere el conjunto de candidatos C3 utilizando L2 (paso de unión). La condición de unir L _k-1 y L _k-1 es que debe tener (K-2) elementos en común. Así que aquí, para L2, el primer elemento debe coincidir.
  Entonces, el conjunto de elementos generado al unirse a L2 es {I1, I2, I3}{I1, I2, I5}{I1, I3, i5}{I2, I3, I4}{I2, I4, I5}{I2, I3, I5}
• Verifique si todos los subconjuntos de estos conjuntos de elementos son frecuentes o no y, de lo contrario, elimine ese conjunto de elementos. (Aquí, el subconjunto de {I1, I2, I3} son {I1, I2}, {I2, I3}, {I1, I3} que son frecuentes. Para {I2, I3, I4}, el subconjunto {I3, I4} no es frecuente, así que elimínelo. Del mismo modo, verifique cada conjunto de elementos)
• encuentre el recuento de soporte de estos conjuntos de elementos restantes buscando en el conjunto de datos.


(II) Compare el recuento de soporte del candidato (C3) con el recuento de soporte mínimo (aquí min_support=2 si support_count del elemento del conjunto de candidatos es menor que min_support, luego elimine esos elementos) esto nos da el conjunto de elementos L3.



Paso 4:

• Genere el conjunto de candidatos C4 usando L3 (paso de unión). La condición de unir L _k-1 y L _k-1 (K=4) es que tengan (K-2) elementos en común. Así que aquí, para L3, los primeros 2 elementos (artículos) deben coincidir.
• Compruebe que todos los subconjuntos de estos conjuntos de elementos sean frecuentes o no (aquí, el conjunto de elementos formado al unir L3 es {I1, I2, I3, I5}, por lo que su subconjunto contiene {I1, I3, I5}, que no es frecuente). Así que no hay elementos en C4
• Nos detenemos aquí porque no se encuentran más conjuntos de elementos frecuentes

Por lo tanto, hemos descubierto todos los conjuntos de elementos frecuentes. Ahora entra en escena la generación de una regla de asociación fuerte. Para eso necesitamos calcular la confianza de cada regla.

Confianza:
una confianza del 60 % significa que el 60 % de los clientes que compraron leche y pan también compraron mantequilla.

Confidence(A->B)=Support_count(A∪B)/Support_count(A)

Así que aquí, tomando un ejemplo de cualquier conjunto de elementos frecuentes, mostraremos la generación de reglas.
Conjunto de elementos {I1, I2, I3} //desde L3
SO las reglas pueden ser
[I1^I2]=>[I3] //confianza = sup(I1^I2^I3)/sup(I1^I2) = 2/4* 100=50%
[I1^I3]=>[I2] //confianza = sup(I1^I2^I3)/sup(I1^I3) = 2/4*100=50%
[I2^I3]=>[ I1] //confianza = sup(I1^I2^I3)/sup(I2^I3) = 2/4*100=50%
[I1]=>[I2^I3] //confianza = sup(I1^I2^ I3)/sup(I1) = 2/6*100=33%
[I2]=>[I1^I3] //confianza = sup(I1^I2^I3)/sup(I2) = 2/7*100= 28%
[I3]=>[I1^I2] //confianza = sup(I1^I2^I3)/sup(I3) = 2/6*100=33%

Entonces, si la confianza mínima es del 50%, las primeras 3 reglas pueden considerarse como reglas de asociación sólidas.

Limitaciones del algoritmo a priori
El algoritmo a priori puede ser lento. La principal limitación es el tiempo requerido para mantener una gran cantidad de conjuntos de candidatos con conjuntos de elementos muy frecuentes, soporte mínimo bajo o conjuntos de elementos grandes, es decir, no es un enfoque eficiente para una gran cantidad de conjuntos de datos. Por ejemplo, si hay 10 ^ 4 de conjuntos frecuentes de 1 elemento, debe generar más de 10 ^ 7 candidatos en 2 longitudes que, a su vez, se probarán y acumularán. Además, para detectar un patrón frecuente en el tamaño 100, es decir, v1, v2… v100, tiene que generar 2^100 conjuntos de elementos candidatos que generan costosas pérdidas de tiempo en la generación de candidatos. Por lo tanto, buscará muchos conjuntos de conjuntos de elementos candidatos, también escaneará la base de datos muchas veces repetidamente para encontrar conjuntos de elementos candidatos. A priori será muy bajo e ineficaz cuando la capacidad de la memoria sea limitada con un gran número de transacciones. [Fuente :https://arxiv.org/pdf/1403.3948.pdf ]