Skip to content
Torna ai risultati

Estrazione di itemset frequenti ECLAT

Introdotto da
Mohammed J. Zaki
Anno
2000
Tipo
Frequent-itemset mining algorithm (vertical format)
Famiglia
Pattern mining

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

ECLAT, introdotto da Mohammed Zaki nel 2000, estrae itemset frequenti utilizzando una rappresentazione dati verticale: invece di scansionare le transazioni, memorizza per ogni elemento l'insieme degli ID delle transazioni (un tidset) che lo contengono, e calcola il supporto di qualsiasi itemset intersecando i tidset.

Questo approccio depth-first, basato sull'intersezione, è veloce ed efficiente in termini di memoria, un'alternativa alle scansioni orizzontali di Apriori e all'albero di FP-Growth.

L’intuizione alla base del metodo

La maggior parte degli algoritmi di estrazione di itemset opera riga per riga: quali elementi sono presenti in ciascuna transazione? ECLAT ribalta la prospettiva. Per ogni elemento mantiene un elenco delle transazioni che lo contengono. Ora il supporto di una coppia di elementi è semplicemente la dimensione dell'intersezione delle loro due liste — una semplice intersezione di insiemi — e non si scansiona mai nuovamente il database. Per trovare itemset frequenti più lunghi, si intersecano le liste di quelli più corti. Percorrere questo spazio in profondità (depth-first) e potare ogni volta che un'intersezione diventa troppo piccola permette di enumerare efficientemente tutti gli itemset frequenti.

Storia

Mohammed Zaki ha introdotto ECLAT e il paradigma di estrazione verticale in lavori culminati nel suo articolo del 2000 su IEEE TKDE sull'estrazione scalabile di associazioni, raffinandolo successivamente con i diffset (dECLAT). Si è affiancato ad Apriori (1994, generazione di candidati orizzontali) e FP-Growth (2000, basato su alberi) come una delle tre famiglie canoniche di algoritmi per itemset frequenti, ognuno con diversi compromessi tra scansioni, memoria e densità dei dati. ECLAT rimane un'opzione standard nei toolkit di data mining.

Quando usarlo

Utilizzare ECLAT per l'estrazione di itemset frequenti quando un approccio verticale basato sull'intersezione si adatta ai dati — è spesso molto veloce su dataset densi ed evita scansioni ripetute del database, rendendolo una valida alternativa ad Apriori e un pari a FP-Growth. Eccelle quando i tidset sono di dimensioni moderate e rientrano in memoria, e la variante diffset gestisce bene i dati densi. I suoi costi: i tidset per gli elementi frequenti possono essere grandi e richiedere molta memoria su grandi dataset sparsi, le intersezioni intermedie aggiungono overhead, e come tutta l'estrazione basata sul supporto è sensibile alla soglia di supporto minimo. Come sempre, gli itemset frequenti sono solo il primo stadio; le regole di associazione con confidenza/lift vengono generate successivamente. Scegliere tra ECLAT, FP-Growth e Apriori in base alla densità dei dati e alla memoria.

Limiti e considerazioni

  • I tidset per gli elementi frequenti possono essere grandi, con un costo di memoria su grandi dataset.
  • I risultati delle intersezioni intermedie aggiungono overhead di memoria/tempo.
  • Meno intuitivo delle rappresentazioni orizzontali (Apriori).
  • Sensibile alla soglia di supporto minimo, come tutta l'estrazione di itemset.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Supporto calcolato tramite veloci intersezioni di tidset — nessuna scansione ripetuta del database.
  • Ricerca in profondità (depth-first) con classi di equivalenza di prefisso riutilizza il lavoro e localizza la memoria.
  • Spesso molto efficiente su dataset densi, competitivo con FP-Growth.
  • L'ottimizzazione diffset riduce ulteriormente il costo di memoria e di intersezione.

Applicazioni

  • Estrazione di regole di associazione nel mercato di riferimento e nella vendita al dettaglio.
  • Analisi di co-occorrenza nel web e nei clickstream.
  • Scoperta di co-occorrenze frequenti in bioinformatica.
  • Qualsiasi compito di estrazione di itemset frequenti che favorisca un approccio verticale basato sull'intersezione.
  • Dataset transazionali densi dove ECLAT con diffset eccelle.

Come funziona

Come funziona

1

Il database viene trasformato una sola volta in formato verticale: ogni elemento mappa al suo tidset, l'insieme degli ID delle transazioni in cui appare. Questa è la struttura dati chiave — tutto il lavoro successivo consiste in operazioni sugli insiemi di tidset, non in passaggi attraverso le transazioni originali.

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

Il supporto di un itemset è la cardinalità dell'intersezione dei tidset dei suoi elementi — il numero di transazioni che li contengono tutti. Il conteggio diventa un'intersezione, che è veloce, e gli elementi singoli frequenti (quelli il cui tidset è sufficientemente grande) avviano la ricerca.

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

Gli itemset vengono estesi intersecando i tidset: il tidset di X ∪ {y} è l'intersezione dei tidset di X e {y}. ECLAT esplora il reticolo degli itemset in profondità (depth-first) all'interno di classi di equivalenza (itemset che condividono un prefisso), quindi le intersezioni vengono riutilizzate e la ricerca rimane locale.

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

Un'estensione viene mantenuta solo se il suo tidset (e quindi il supporto) soddisfa la soglia di supporto minimo; altrimenti quel ramo viene potato (anti-monotonia: nessun soprainsieme può essere frequente). I diffset — che memorizzano solo le differenze tra i tidset — sono un'ottimizzazione comune che riduce ulteriormente la memoria e il costo dell'intersezione.

Formula
\text{keep extensions with } \text{support} \ge \text{minsup}

Errori comuni

  • Estrazione di dati sparsi molto grandi dove i tidset fanno esplodere la memoria — considerare diffset o FP-Growth.
  • Impostare il supporto minimo troppo basso e produrre un numero ingestibile di itemset.
  • Confondere itemset frequenti con regole di associazione (le regole sono un passaggio separato).
  • Ignorare la variante diffset su dati densi dove aiuta notevolmente.

Domande frequenti

In che modo ECLAT differisce da Apriori e FP-Growth?

Tutti e tre trovano itemset frequenti. Apriori utilizza un formato orizzontale con generazione di candidati e molte scansioni; FP-Growth comprime i dati in un albero ed estrae ricorsivamente; ECLAT utilizza un formato verticale di tidset e calcola il supporto intersecando le liste di ID transazione in profondità (depth-first). ECLAT e FP-Growth evitano le scansioni ripetute di Apriori.

Cos'è un tidset?

Un tidset (insieme di ID transazione) è l'elenco delle transazioni che contengono un dato elemento o itemset. ECLAT li memorizza verticalmente e calcola il supporto di un itemset come la dimensione dell'intersezione dei tidset dei suoi elementi, trasformando il conteggio in intersezione di insiemi.

Cosa sono i diffset?

I diffset memorizzano solo la differenza tra il tidset di un itemset e quello del suo genitore, anziché il tidset completo. Su dati densi ciò riduce drasticamente la memoria e il costo dell'intersezione, conferendo alla variante dECLAT un notevole vantaggio in termini di efficienza.

Metodi correlati

Fonti

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

    Apri il riferimento DOI
    Copiato.