ECLAT : Extraction de sous-ensembles d'items fréquents
- Introduite par
- Mohammed J. Zaki
- Année
- 2000
- Type
- Frequent-itemset mining algorithm (vertical format)
- Famille
- Pattern mining
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
ECLAT, introduit par Mohammed Zaki en 2000, extrait les sous-ensembles d'items fréquents à l'aide d'une représentation verticale des données : au lieu de parcourir les transactions, il stocke pour chaque item l'ensemble des identifiants de transaction (un tidset) qui le contiennent, et calcule le support de tout sous-ensemble d'items en intersectant les tidsets.
Cette approche par parcours en profondeur, basée sur l'intersection, est rapide et économe en mémoire, une alternative aux parcours horizontaux d'Apriori et à l'arbre de FP-Growth.
L’intuition derrière la méthode
La plupart des extracteurs de sous-ensembles d'items pensent ligne par ligne : quels items sont dans chaque transaction ? ECLAT retourne la table sur le côté. Pour chaque item, il conserve une liste des transactions qui le contiennent. Désormais, le support d'une paire d'items est simplement la taille du chevauchement de leurs deux listes — une simple intersection d'ensembles — et vous ne parcourez jamais à nouveau la base de données. Pour trouver des sous-ensembles d'items plus longs, intersectez les listes des plus courts. En parcourant ainsi en profondeur et en élaguant dès qu'une intersection devient trop petite, on énumère efficacement tous les sous-ensembles d'items fréquents.
Histoire
Mohammed Zaki a introduit ECLAT et le paradigme d'extraction verticale dans des travaux culminant avec son article de 2000 dans IEEE TKDE sur l'extraction d'associations évolutive, le raffinant plus tard avec les diffsets (dECLAT). Il a rejoint Apriori (1994, génération de candidats horizontale) et FP-Growth (2000, basé sur un arbre) comme l'une des trois familles canoniques d'algorithmes d'extraction de sous-ensembles d'items fréquents, chacune échangeant différemment parcours, mémoire et densité des données. ECLAT reste une option standard dans les boîtes à outils d'exploration de données.
Quand l’utiliser
Utilisez ECLAT pour l'extraction de sous-ensembles d'items fréquents lorsqu'une approche verticale basée sur l'intersection convient aux données — elle est souvent très rapide sur des jeux de données denses et évite les parcours répétés de la base de données, ce qui en fait une alternative solide à Apriori et une concurrente de FP-Growth. Elle excelle lorsque les tidsets sont de taille modérée et tiennent en mémoire, et la variante diffset gère bien les données denses. Ses coûts : les tidsets pour les items fréquents peuvent être volumineux et gourmands en mémoire sur de grands jeux de données épars, les intersections intermédiaires ajoutent une surcharge, et comme toute extraction basée sur le support, elle est sensible au seuil de support minimum. Comme toujours, les sous-ensembles d'items fréquents ne sont que la première étape ; les règles d'association avec confiance/lift sont générées ensuite. Choisissez parmi ECLAT, FP-Growth et Apriori en fonction de la densité des données et de la mémoire.
Limites et points d’attention
- Les tidsets pour les items fréquents peuvent être volumineux, coûtant de la mémoire sur de grands jeux de données.
- Les résultats d'intersection intermédiaires ajoutent une surcharge de mémoire/temps.
- Moins intuitif que les représentations horizontales (Apriori).
- Sensible au seuil de support minimum, comme toute extraction de sous-ensembles d'items.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Support calculé par des intersections rapides de tidsets — pas de parcours répétés de la base de données.
- Recherche en profondeur avec des classes d'équivalence de préfixes réutilisant le travail et localisant la mémoire.
- Souvent très efficace sur les jeux de données denses, compétitif avec FP-Growth.
- L'optimisation diffset réduit davantage la mémoire et le coût d'intersection.
Applications
- Extraction d'associations du panier d'achats et de la vente au détail.
- Analyse de co-occurrence Web et de flux de clics.
- Découverte de co-occurrences fréquentes en bio-informatique.
- Toute tâche d'extraction de sous-ensembles d'items favorisant une approche verticale basée sur l'intersection.
- Jeux de données transactionnels denses où ECLAT avec diffsets excelle.
Comment ça marche
Comment ça marche
La base de données est transformée une seule fois en format vertical : chaque item est associé à son tidset, l'ensemble des identifiants de transaction dans lesquels il apparaît. C'est la structure de données clé — tout le travail ultérieur consiste en opérations sur les ensembles de tidsets, et non en passages sur les transactions originales.
Formule
\text{for each item } i:\ t(i) = \{ \text{transaction ids containing } i \}Le support d'un sous-ensemble d'items est la cardinalité de l'intersection de ses tidsets d'items — le nombre de transactions les contenant tous. Le comptage devient une intersection, ce qui est rapide, et les items uniques fréquents (ceux dont le tidset est suffisamment grand) amorcent la recherche.
Formule
\text{support}(X) = | \textstyle\bigcap_{i\in X} t(i) |Les sous-ensembles d'items sont étendus en intersectant les tidsets : le tidset de X ∪ {y} est l'intersection des tidsets de X et de {y}. ECLAT explore le treillis des sous-ensembles d'items en profondeur au sein de classes d'équivalence (sous-ensembles d'items partageant un préfixe), de sorte que les intersections sont réutilisées et la recherche reste locale.
Formule
t(X\cup Y) = t(X) \cap t(Y)\ \text{(intersect to extend itemsets)}Une extension n'est conservée que si son tidset (et donc son support) atteint le seuil de support minimum ; sinon, cette branche est élaguée (anti-monotonie : aucun sur-ensemble ne peut être fréquent). Les diffsets — ne stockant que les différences entre les tidsets — sont une optimisation courante qui réduit davantage la mémoire et le coût d'intersection.
Formule
\text{keep extensions with } \text{support} \ge \text{minsup}Pièges courants
- Extraction de très grandes données éparses où les tidsets font exploser la mémoire — envisagez les diffsets ou FP-Growth.
- Définir un support minimum trop bas et produire un nombre ingérable de sous-ensembles d'items.
- Confondre les sous-ensembles d'items fréquents avec les règles d'association (les règles sont une étape distincte).
- Ignorer la variante diffset sur des données denses où elle aide considérablement.
Questions fréquentes
Comment ECLAT diffère-t-il d'Apriori et de FP-Growth ?
Tous les trois trouvent des sous-ensembles d'items fréquents. Apriori utilise un format horizontal avec génération de candidats et de nombreux parcours ; FP-Growth compresse les données dans un arbre et extrait récursivement ; ECLAT utilise un format vertical de tidsets et calcule le support en intersectant les listes d'identifiants de transaction en profondeur. ECLAT et FP-Growth évitent les parcours répétés d'Apriori.
Qu'est-ce qu'un tidset ?
Un tidset (ensemble d'identifiants de transaction) est la liste des transactions qui contiennent un item ou un sous-ensemble d'items donné. ECLAT les stocke verticalement et calcule le support d'un sous-ensemble d'items comme la taille de l'intersection de ses tidsets d'items, transformant le comptage en intersection d'ensembles.
Que sont les diffsets ?
Les diffsets stockent uniquement la différence entre le tidset d'un sous-ensemble d'items et celui de son parent, plutôt que le tidset complet. Sur des données denses, cela réduit considérablement la mémoire et le coût d'intersection, donnant au variant dECLAT un avantage d'efficacité substantiel.
Méthodes associées
Sources
Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.
Ouvrir la référence DOICopié.