Menú

Algoritmo a priori en minería de datos: implementación con ejemplos

  • Principal
  • Otro
  • Algoritmo a priori en minería de datos: implementación con ejemplos

apriori algorithm data mining

Pruebe Nuestro Instrumento Para Eliminar Los Problemas

Tutorial en profundidad sobre el algoritmo a priori para descubrir conjuntos de elementos frecuentes en la minería de datos. Este tutorial explica los pasos a priori y cómo funciona:

En esto Serie de tutoriales de minería de datos , echamos un vistazo al Algoritmo de árbol de decisión en nuestro tutorial anterior.

Existen varios métodos para la minería de datos, como asociación, correlación, clasificación y agrupación.

qué máquinas virtuales de escritorio se ejecutan en el sistema operativo Windows

Este tutorial se centra principalmente en la minería mediante reglas de asociación. Mediante reglas de asociación, identificamos el conjunto de elementos o atributos que se encuentran juntos en una tabla.

Algoritmo a priori

Lo que vas a aprender:

¿Qué es un conjunto de elementos?

Un conjunto de elementos juntos se denomina conjunto de elementos. Si algún conjunto de elementos tiene k-elementos, se denomina k-conjunto de elementos. Un conjunto de elementos consta de dos o más elementos. Un conjunto de elementos que se produce con frecuencia se denomina conjunto de elementos frecuentes. Por lo tanto, la extracción frecuente de conjuntos de elementos es una técnica de extracción de datos para identificar los elementos que suelen aparecer juntos.

Por ejemplo , Bread and butter, Laptop y software antivirus, etc.

¿Qué es un conjunto de elementos frecuentes?

Un conjunto de elementos se denomina frecuente si satisface un valor de umbral mínimo de apoyo y confianza. El soporte muestra transacciones con artículos comprados juntos en una sola transacción. La confianza muestra las transacciones en las que los artículos se compran uno tras otro.

Para el método de extracción de conjuntos de elementos frecuentes, consideramos solo aquellas transacciones que cumplen con los requisitos de confianza y soporte de umbral mínimo. Los conocimientos de estos algoritmos de minería ofrecen muchos beneficios, reducción de costos y una ventaja competitiva mejorada.

Hay un tiempo de compensación necesario para extraer datos y el volumen de datos para la extracción frecuente. El algoritmo de minería frecuente es un algoritmo eficiente para minar los patrones ocultos de conjuntos de elementos en poco tiempo y con menos consumo de memoria.

Minería de patrones frecuente (FPM)

El algoritmo de minería de patrones frecuente es una de las técnicas más importantes de minería de datos para descubrir relaciones entre diferentes elementos en un conjunto de datos. Estas relaciones se representan en forma de reglas de asociación. Ayuda a encontrar las irregularidades en los datos.

FPM tiene muchas aplicaciones en el campo del análisis de datos, errores de software, marketing cruzado, análisis de campañas de venta, análisis de la cesta de la compra, etc.

Los conjuntos de elementos frecuentes descubiertos a través de Apriori tienen muchas aplicaciones en tareas de minería de datos. Tareas como encontrar patrones interesantes en la base de datos, descubrir la secuencia y la minería de reglas de asociación es la más importante de ellas.

Las reglas de asociación se aplican a los datos de transacciones del supermercado, es decir, para examinar el comportamiento del cliente en términos de los productos comprados. Las reglas de asociación describen la frecuencia con la que los artículos se compran juntos.

Reglas de asociación

La minería de reglas de asociación se define como:

“Sea I = {…} un conjunto de' n 'atributos binarios llamados elementos. Sea D = {….} Un conjunto de transacciones llamado base de datos. 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 X-> Y donde X, Y? Yo y X? Y = ?. El conjunto de elementos X e Y se denomina antecedente y consecuente de la regla, respectivamente '.

Las reglas de aprendizaje de asociación se utilizan para encontrar relaciones entre atributos en grandes bases de datos. Una regla de asociación, A => B, tendrá la forma 'para un conjunto de transacciones, algún valor del conjunto de elementos A determina los valores del conjunto de elementos B bajo la condición en la que se cumplen el soporte y la confianza mínimos'.

El apoyo y la confianza se pueden representar con el siguiente ejemplo:

|_+_|

La declaración anterior es un ejemplo de una regla de asociación. Esto significa que hay una transacción del 2% que compró pan y mantequilla juntos y hay un 60% de clientes que compraron pan y mantequilla.

El soporte y la confianza para el conjunto de elementos A y B se representan mediante fórmulas:

Fórmula de apoyo y confianza para el conjunto de elementos A y B

La minería de reglas de asociación consta de 2 pasos:

  1. Encuentra todos los conjuntos de elementos frecuentes.
  2. Genere reglas de asociación a partir de los conjuntos de elementos frecuentes anteriores.

¿Por qué la minería frecuente de conjuntos de elementos?

La minería frecuente de conjuntos de elementos o patrones se usa ampliamente debido a sus amplias aplicaciones en las reglas de asociación de minería, correlaciones y restricciones de patrones de gráficos que se basan en patrones frecuentes, patrones secuenciales y muchas otras tareas de minería de datos.

Algoritmo a priori - Algoritmos de patrones frecuentes

El algoritmo Apriori fue el primer algoritmo que se propuso para la minería frecuente de conjuntos de elementos. Posteriormente fue mejorado por R Agarwal y R Srikant y llegó a ser conocido como Apriori. Este algoritmo utiliza dos pasos 'unir' y 'podar' para reducir el espacio de búsqueda. Es un enfoque iterativo para descubrir los conjuntos de elementos más frecuentes.

Apriori dice:

La probabilidad de que el ítem I no sea frecuente es si:

  • PI)
  • P (I + A)
  • Si un conjunto de elementos tiene un valor menor que el soporte mínimo, todos sus superconjuntos también caerán por debajo del soporte mínimo y, por lo tanto, pueden ignorarse. Esta propiedad se llama propiedad Antimonotone.

Los pasos seguidos en el algoritmo Apriori de minería de datos son:

  1. Unirse paso : Este paso genera (K + 1) conjunto de elementos a partir de K-conjuntos de elementos uniendo cada elemento consigo mismo.
  2. Paso de poda : Este paso analiza el recuento de cada elemento de la base de datos. Si el artículo candidato no cumple con el soporte mínimo, entonces se considera poco frecuente y, por lo tanto, se elimina. Este paso se realiza para reducir el tamaño de los conjuntos de elementos candidatos.

Pasos a priori

El algoritmo a priori es una secuencia de pasos a seguir para encontrar el conjunto de elementos más frecuente en la base de datos dada. Esta técnica de minería de datos sigue los pasos de unión y poda de forma iterativa hasta que se logra el conjunto de elementos más frecuente. En el problema se da un umbral de soporte mínimo o lo asume el usuario.

#1) En la primera iteración del algoritmo, cada elemento se toma como candidato de 1 conjunto de elementos. El algoritmo contará las ocurrencias de cada elemento.

#2) Deje que haya un soporte mínimo, min_sup (por ejemplo, 2). Se determina el conjunto de conjuntos de 1 elementos cuya ocurrencia satisface el mínimo. Solo aquellos candidatos que cuentan más o igual que min_sup, se adelantan para la siguiente iteración y los demás se eliminan.

#3) A continuación, se descubren elementos frecuentes de 2 conjuntos de elementos con min_sup. Para ello, en el paso de unión, el conjunto de 2 elementos se genera formando un grupo de 2 combinando elementos consigo mismo.

#4) Los candidatos del conjunto de 2 elementos se podan utilizando el valor de umbral min-sup. Ahora la tabla tendrá 2 conjuntos de elementos con min-sup solamente.

#5) La siguiente iteración formará 3 conjuntos de elementos mediante el paso de unión y eliminación. Esta iteración seguirá la propiedad antimonotónica donde los subconjuntos de conjuntos de 3 elementos, es decir, los subconjuntos de conjuntos de 2 elementos de cada grupo caen en min_sup. Si todos los subconjuntos de conjuntos de 2 elementos son frecuentes, entonces el superconjunto será frecuente; de ​​lo contrario, se podará.

#6) El siguiente paso será hacer un conjunto de 4 elementos uniendo el conjunto de 3 elementos consigo mismo y podando si su subconjunto no cumple con los criterios min_sup. El algoritmo se detiene cuando se logra el conjunto de elementos más frecuente.

Pasos a priori

(imagen fuente )

Ejemplo de Apriori:Umbral de soporte = 50%, confianza = 60%

TABLA 1

TransacciónLista de artículos
T1I1, I2, I3
T2I2, I3, I4
T3I4, I5
T4I1, I2, I4
T5I1, I2, I3, I5
T6I1, I2, I3, I4

Solución:

Umbral de soporte = 50% => 0.5 * 6 = 3 => min_sup = 3

1. Recuento de cada artículo

TABLA 2

ArtículoContar
I14
I25
I34
I44
I52

2. Paso de poda: TABLA 2 muestra que el elemento I5 no cumple min_sup = 3, por lo que se elimina, solo I1, I2, I3, I4 cumplen con el recuento min_sup.

TABLA 3

ArtículoContar
I14
I25
I34
I44

3. Unirse al paso: Formulario de 2 elementos. Desde TABLA 1 averigüe las ocurrencias de 2-itemset.

TABLA 4

ArtículoContar
I1, I24
I1, I33
I1, I42
I2, I34
I2, I43
I3, I42

4. Paso de poda: TABLA -4 muestra que el conjunto de elementos {I1, I4} y {I3, I4} no cumple min_sup, por lo que se elimina.

TABLA 5

ArtículoContar
I1, I24
I1, I33
I2, I34
I2, I43

5. Paso de unión y poda: Formulario de 3 elementos. Desde el TABLA 1 averigüe las apariciones del conjunto de 3 elementos. Desde TABLA 5 , averigüe los subconjuntos de 2 elementos que admiten min_sup.

Podemos ver para el conjunto de elementos {I1, I2, I3} subconjuntos, {I1, I2}, {I1, I3}, {I2, I3} están ocurriendo en TABLA 5 por tanto, {I1, I2, I3} es frecuente.

Podemos ver para el conjunto de elementos {I1, I2, I4} subconjuntos, {I1, I2}, {I1, I4}, {I2, I4}, {I1, I4} no es frecuente, ya que no ocurre en TABLA 5 por tanto, {I1, I2, I4} no es frecuente, por lo que se elimina.

TABLA 6

Artículo
I1, I2, I3
I1, I2, I4
I1, I3, I4
I2, I3, I4

Solo {I1, I2, I3} es frecuente .

6. Genere reglas de asociación: A partir del conjunto de elementos frecuentes descubierto anteriormente, la asociación podría ser:

{I1, I2} => {I3}

Confianza = apoyo {I1, I2, I3} / apoyo {I1, I2} = (3/4) * 100 = 75%

{I1, I3} => {I2}

Confianza = apoyo {I1, I2, I3} / apoyo {I1, I3} = (3/3) * 100 = 100%

{I2, I3} => {I1}

Confianza = apoyo {I1, I2, I3} / apoyo {I2, I3} = (3/4) * 100 = 75%

{I1} => {I2, I3}

Confianza = apoyo {I1, I2, I3} / apoyo {I1} = (3/4) * 100 = 75%

{I2} => {I1, I3}

Confianza = apoyo {I1, I2, I3} / apoyo {I2 = (3/5) * 100 = 60%

{I3} => {I1, I2}

Confianza = apoyo {I1, I2, I3} / apoyo {I3} = (3/4) * 100 = 75%

Esto muestra que todas las reglas de asociación anteriores son sólidas si el umbral de confianza mínimo es del 60%.

¿Cuál es la fase de análisis en el sdlc?

El algoritmo a priori: pseudocódigo

C: conjunto de elementos candidatos de tamaño k

L: conjunto de artículos frecuentes de talla k

Psudocódigo

(imagen fuente )

Ventajas

  1. Algoritmo fácil de entender
  2. Los pasos de unión y eliminación son fáciles de implementar en grandes conjuntos de elementos en grandes bases de datos

Desventajas

  1. Requiere un alto cálculo si los conjuntos de elementos son muy grandes y el soporte mínimo se mantiene muy bajo.
  2. Es necesario escanear toda la base de datos.

Métodos para mejorar la eficiencia a priori

Hay muchos métodos disponibles para mejorar la eficiencia del algoritmo.

  1. Técnica basada en hash: Este método utiliza una estructura basada en hash llamada tabla hash para generar k-itemsets y su recuento correspondiente. Utiliza una función hash para generar la tabla.
  2. Reducción de transacciones: Este método reduce el número de transacciones que se escanean en iteraciones. Las transacciones que no contienen elementos frecuentes se marcan o eliminan.
  3. Fraccionamiento: Este método requiere solo dos escaneos de la base de datos para extraer los conjuntos de elementos frecuentes. Dice que para que cualquier conjunto de elementos sea potencialmente frecuente en la base de datos, debería ser frecuente en al menos una de las particiones de la base de datos.
  4. Muestreo: Este método selecciona una muestra aleatoria S de la base de datos D y luego busca un conjunto de elementos frecuentes en S. Es posible que se pierda un conjunto de elementos frecuentes global. Esto se puede reducir bajando min_sup.
  5. Recuento dinámico de conjuntos de elementos: Esta técnica puede agregar nuevos conjuntos de elementos candidatos en cualquier punto de inicio marcado de la base de datos durante el análisis de la base de datos.

Aplicaciones del algoritmo Apriori

Algunos campos donde se usa Apriori:

  1. En el campo de la educación: Extraer reglas de asociación en minería de datos de estudiantes admitidos a través de características y especialidades.
  2. En el campo médico: Por ejemplo, análisis de la base de datos del paciente.
  3. En silvicultura: Análisis de probabilidad e intensidad de incendios forestales con los datos de incendios forestales.
  4. Apriori es utilizado por muchas empresas como Amazon en el Sistema de recomendación y de Google para la función de autocompletar.

Conclusión

El algoritmo Apriori es un algoritmo eficiente que escanea la base de datos solo una vez.

Reduce considerablemente el tamaño de los conjuntos de elementos de la base de datos proporcionando un buen rendimiento. Por lo tanto, la minería de datos ayuda a los consumidores y las industrias a mejorar el proceso de toma de decisiones.

¡Consulte nuestro próximo tutorial para saber más sobre el algoritmo de crecimiento de patrones frecuentes!

PREV Tutorial | SIGUIENTE Tutorial

Lectura recomendada

^