ML | Algoritmo ECLAT

Prerrequisitos: algoritmo a priori

El algoritmo ECLAT significa Equivalence Class Clustering y bottom-up Lattice Traversal . Es uno de los métodos populares de minería de reglas de asociación . Es una versión más eficiente y escalable del algoritmo Apriori. Mientras que el algoritmo Apriori funciona en un sentido horizontal imitando la búsqueda primero en amplitud de un gráfico, el algoritmo ECLAT funciona de manera vertical al igual que la búsqueda primero en profundidad de un gráfico. Este enfoque vertical del algoritmo ECLAT lo convierte en un algoritmo más rápido que el algoritmo Apriori.

¿Cómo funciona el algoritmo? :
La idea básica es utilizar las intersecciones de Transaction Id Sets(tidsets) para calcular el valor de soporte de un candidato y evitar la generación de subconjuntos que no existen en el árbol de prefijos. En la primera llamada de la función, todos los elementos individuales se utilizan junto con sus tidsets. Luego, la función se llama recursivamente y en cada llamada recursiva, cada par elemento-tidset se verifica y se combina con otros pares elemento-tidset. Este proceso continúa hasta que no se pueden combinar pares de elementos-conjuntos candidatos.

Entendamos ahora lo dicho anteriormente trabajando con un ejemplo:

Considere el siguiente registro de transacciones:-

Los datos anteriores son una array booleana en la que, para cada celda (i, j), el valor indica si el j-ésimo artículo está incluido en la i-ésima transacción o no. 1 significa verdadero mientras que 0 significa falso.

Ahora llamamos a la función por primera vez y organizamos cada elemento con su tidset de forma tabular:

k = 1, soporte mínimo = 2

Artículo	Tidset
Pan de molde	{T1, T4, T5, T7, T8, T9}
Manteca	{T1, T2, T3, T4, T6, T8, T9}
Leche	{T3, T5, T6, T7, T8, T9}
Coca	{T2, T4}
Mermelada	{T1, T8}

Ahora llamamos recursivamente a la función hasta que no se puedan combinar más pares de ítem-tidset:

k = 2

Artículo	Tidset
{Pan con mantequilla}	{T1, T4, T8, T9}
{Pan, Leche}	{T5, T7, T8, T9}
{Pan, Coca-Cola}	{T4}
{Pan, Mermelada}	{T1, T8}
{Suero de la leche}	{T3, T6, T8, T9}
{mantequilla, coca cola}	{T2, T4}
{mantequilla, mermelada}	{T1, T8}
{leche, mermelada}	{T8}

k = 3

Artículo	Tidset
{Pan, Mantequilla, Leche}	{T8, T9}
{Pan, mantequilla, mermelada}	{T1, T8}

k = 4

Artículo	Tidset
{Pan, Mantequilla, Leche, Mermelada}	{T8}

Nos detenemos en k = 4 porque no hay más pares de artículos y conjuntos para combinar.

Dado que el soporte mínimo = 2, concluimos las siguientes reglas del conjunto de datos dado:

Artículos comprados	Productos Recomendados
Pan de molde	Manteca
Pan de molde	Leche
Pan de molde	Mermelada
Manteca	Leche
Manteca	Coca
Manteca	Mermelada
Pan y mantequilla	Leche
Pan y mantequilla	Mermelada

Ventajas sobre el algoritmo a priori: –

1. Requisitos de memoria: dado que el algoritmo ECLAT utiliza un enfoque de búsqueda primero en profundidad, utiliza menos memoria que el algoritmo Apriori.
2. Velocidad: el algoritmo ECLAT suele ser más rápido que el algoritmo Apriori.
3. Número de cálculos: el algoritmo ECLAT no implica el escaneo repetido de los datos para calcular los valores de apoyo individuales.