Saltar al contenido
Volver a los resultados

Minería de conjuntos de ítems frecuentes ECLAT

Propuesto por
Mohammed J. Zaki
Año
2000
Tipo
Frequent-itemset mining algorithm (vertical format)
Familia
Pattern mining

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

ECLAT, introducido por Mohammed Zaki en 2000, extrae conjuntos de ítems frecuentes utilizando una representación de datos vertical: en lugar de escanear transacciones, almacena para cada ítem el conjunto de ID de transacción (un tidset) que lo contienen, y calcula el soporte de cualquier conjunto de ítems intersecando tidsets.

Este enfoque de búsqueda en profundidad basado en intersecciones es rápido y eficiente en memoria, una alternativa a los escaneos horizontales de Apriori y al árbol de FP-Growth.

La intuición detrás del método

La mayoría de los mineros de conjuntos de ítems piensan fila por fila: ¿qué ítems hay en cada transacción? ECLAT invierte la tabla. Para cada ítem, mantiene una lista de las transacciones que lo contienen. Ahora, el soporte de un par de ítems es simplemente el tamaño de la superposición de sus dos listas —una simple intersección de conjuntos— y nunca se vuelve a escanear la base de datos. Para encontrar conjuntos de ítems frecuentes más largos, se intersecan las listas de los más cortos. Recorrer esto en profundidad y podar cada vez que una intersección se vuelve demasiado pequeña enumera eficientemente todos los conjuntos de ítems frecuentes.

Historia

Mohammed Zaki introdujo ECLAT y el paradigma de minería vertical en un trabajo que culminó en su artículo de 2000 en IEEE TKDE sobre minería de asociación escalable, refinándolo posteriormente con diffsets (dECLAT). Se unió a Apriori (1994, generación de candidatos horizontal) y FP-Growth (2000, basado en árboles) como una de las tres familias canónicas de algoritmos de conjuntos de ítems frecuentes, cada una con diferentes compensaciones entre escaneos, memoria y densidad de datos. ECLAT sigue siendo una opción estándar en los kits de herramientas de minería de datos.

Cuándo usarlo

Utilice ECLAT para la minería de conjuntos de ítems frecuentes cuando un enfoque vertical basado en intersecciones se adapte a los datos; a menudo es muy rápido en conjuntos de datos densos y evita escaneos repetidos de la base de datos, lo que lo convierte en una alternativa sólida a Apriori y un par a FP-Growth. Destaca cuando los tidsets son de tamaño moderado y caben en la memoria, y la variante diffset maneja bien los datos densos. Sus costos: los tidsets para ítems frecuentes pueden ser grandes y consumir mucha memoria en grandes conjuntos de datos dispersos, las intersecciones intermedias añaden sobrecarga, y como toda minería basada en soporte, es sensible al umbral de soporte mínimo. Como siempre, los conjuntos de ítems frecuentes son solo la primera etapa; las reglas de asociación con confianza/lift se generan después. Elija entre ECLAT, FP-Growth y Apriori según la densidad de los datos y la memoria.

Limitaciones y consideraciones

  • Los tidsets para ítems frecuentes pueden ser grandes, lo que consume memoria en grandes conjuntos de datos.
  • Los resultados de intersección intermedios añaden sobrecarga de memoria/tiempo.
  • Menos intuitivo que las representaciones horizontales (Apriori).
  • Sensible al umbral de soporte mínimo, como toda minería de conjuntos de ítems.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • Soporte calculado mediante intersecciones rápidas de tidsets; no hay escaneos repetidos de la base de datos.
  • La búsqueda en profundidad con clases de equivalencia de prefijo reutiliza el trabajo y localiza la memoria.
  • A menudo muy eficiente en conjuntos de datos densos, competitivo con FP-Growth.
  • La optimización diffset reduce aún más la memoria y el costo de intersección.

Aplicaciones

  • Minería de asociación de cestas de mercado y minorista.
  • Análisis de co-ocurrencia web y de flujos de clics.
  • Descubrimiento de co-ocurrencias frecuentes en bioinformática.
  • Cualquier tarea de conjuntos de ítems frecuentes que favorezca un enfoque vertical basado en intersecciones.
  • Conjuntos de datos transaccionales densos donde diffset ECLAT sobresale.

Cómo funciona

Cómo funciona

1

La base de datos se transforma una vez a formato vertical: cada ítem se mapea a su tidset, el conjunto de ID de transacción en las que aparece. Esta es la estructura de datos clave; todo el trabajo subsiguiente son operaciones de conjuntos sobre tidsets, no pasadas sobre las transacciones originales.

Fórmula
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}
2

El soporte de un conjunto de ítems es la cardinalidad de la intersección de los tidsets de sus ítems —el número de transacciones que los contienen a todos. Contar se convierte en intersecar, lo cual es rápido, y los ítems individuales frecuentes (aquellos cuyo tidset es lo suficientemente grande) inician la búsqueda.

Fórmula
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |
3

Los conjuntos de ítems se extienden intersecando tidsets: el tidset de X ∪ {y} es la intersección de los tidsets de X y {y}. ECLAT explora la red de conjuntos de ítems en profundidad dentro de clases de equivalencia (conjuntos de ítems que comparten un prefijo), por lo que las intersecciones se reutilizan y la búsqueda se mantiene local.

Fórmula
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}
4

Una extensión se mantiene solo si su tidset (y por lo tanto su soporte) cumple el umbral de soporte mínimo; de lo contrario, esa rama se poda (antimonotonicidad: ningún superconjunto puede ser frecuente). Los diffsets —que almacenan solo las diferencias entre tidsets— son una optimización común que reduce aún más la memoria y el costo de intersección.

Fórmula
\text{keep extensions with } \text{support} \ge \text{minsup}

Errores comunes

  • Minería de datos dispersos muy grandes donde los tidsets agotan la memoria; considere diffsets o FP-Growth.
  • Establecer un soporte mínimo demasiado bajo y producir un número inmanejable de conjuntos de ítems.
  • Confundir conjuntos de ítems frecuentes con reglas de asociación (las reglas son un paso separado).
  • Ignorar la variante diffset en datos densos donde ayuda enormemente.

Preguntas frecuentes

¿En qué se diferencia ECLAT de Apriori y FP-Growth?

Los tres encuentran conjuntos de ítems frecuentes. Apriori utiliza un formato horizontal con generación de candidatos y muchos escaneos; FP-Growth comprime los datos en un árbol y mina recursivamente; ECLAT utiliza un formato tidset vertical y calcula el soporte intersecando listas de ID de transacción en profundidad. ECLAT y FP-Growth evitan los escaneos repetidos de Apriori.

¿Qué es un tidset?

Un tidset (conjunto de ID de transacción) es la lista de transacciones que contienen un ítem o conjunto de ítems dado. ECLAT los almacena verticalmente y calcula el soporte de un conjunto de ítems como el tamaño de la intersección de los tidsets de sus ítems, convirtiendo el conteo en una intersección de conjuntos.

¿Qué son los diffsets?

Los diffsets almacenan solo la diferencia entre el tidset de un conjunto de ítems y el de su padre, en lugar del tidset completo. En datos densos, esto reduce drásticamente la memoria y el costo de intersección, otorgando a la variante dECLAT una ventaja sustancial en eficiencia.

Métodos relacionados

Fuentes

  1. Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.

    Abrir referencia DOI
    Copiado.