FP-Growth (croissance d'arbre de motifs fréquents)
- Introduite par
- Jiawei Han, Jian Pei & Yiwen Yin
- Année
- 2000
- Type
- Frequent-itemset mining algorithm
- Famille
- Pattern mining
Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais
À quoi sert-elle ?
FP-Growth, introduit par Jiawei Han, Jian Pei et Yiwen Yin en 2000, extrait les itemsets fréquents des données transactionnelles sans générer d'ensembles candidats, l'étape coûteuse qui ralentit l'algorithme classique Apriori.
Il compresse la base de données en un arbre de motifs fréquents (FP-tree) en deux balayages, puis génère récursivement des motifs fréquents à partir de cette structure, ce qui le rend considérablement plus rapide qu'Apriori sur de grands jeux de données denses.
L’intuition derrière la méthode
Apriori trouve les itemsets fréquents en générant et testant répétitivement des combinaisons candidates — un processus coûteux et gourmand en balayages qui explose sur des données denses. FP-Growth emprunte une voie différente : il comprime toute la base de données transactionnelle dans un arbre compact où les préfixes partagés sont stockés une seule fois, de sorte que les motifs communs se chevauchent et se compressent. Ensuite, au lieu de générer des candidats, il lit les motifs fréquents directement à partir de l'arbre en suivant les chemins qui mènent à chaque élément et en extrayant récursivement des arbres 'conditionnels' plus petits. Deux passages sur les données et une structure de données astucieuse remplacent les nombreux passages et l'explosion combinatoire des candidats d'Apriori.
Histoire
Han, Pei et Yin ont présenté FP-Growth à la SIGMOD 2000 comme une alternative sans génération de candidats à Apriori, avec un traitement élargi dans leur article de 2004 sur Data Mining and Knowledge Discovery. L'idée de l'arbre de motifs fréquents — compresser les transactions dans une structure de préfixes partagée et l'extraire récursivement — est devenue une technique fondamentale dans l'extraction de motifs, aux côtés d'Apriori (basé sur les candidats) et d'ECLAT (format vertical). Il reste un extracteur d'itemsets standard et performant dans les bibliothèques d'exploration de données.
Quand l’utiliser
Utilisez FP-Growth pour extraire les itemsets fréquents (et, en aval, les règles d'association) des données transactionnelles — analyse de panier d'achat, exploration de l'usage web et des flux de clics, recommandation, et co-occurrence en bioinformatique — en particulier sur des jeux de données volumineux ou denses où la génération de candidats d'Apriori est trop lente. Il ne nécessite que deux balayages de base de données et surpasse généralement Apriori. Ses coûts : le FP-tree doit tenir en mémoire (une limitation pour des données très volumineuses ou extrêmement éparses, où l'arbre se compresse mal), la récursion peut être complexe à implémenter, et comme toute extraction basée sur le support, il est sensible au seuil de support minimum (trop bas fait exploser la sortie, trop haut manque des motifs). ECLAT (intersection de tidsets verticaux) est une alternative ; pour les règles elles-mêmes, associez-le à la génération de règles d'association.
Limites et points d’attention
- Le FP-tree doit tenir en mémoire ; les jeux de données très volumineux peuvent ne pas le permettre.
- Sur des données éparses, l'arbre se compresse mal, érodant l'avantage.
- La construction récursive d'arbres conditionnels est comparativement complexe à implémenter.
- Sensible au seuil de support minimum, comme toute extraction d'itemsets fréquents.
Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.
Points forts
- Pas de génération de candidats — beaucoup plus rapide qu'Apriori sur des données volumineuses/denses.
- Seulement deux balayages de base de données, quelle que soit la longueur du motif.
- Le FP-tree compresse la structure partagée, économisant mémoire et temps sur les données denses.
- S'adapte aux longs motifs fréquents qui submergent les méthodes basées sur les candidats.
Applications
- Analyse de panier d'achat et extraction de règles d'association dans le commerce de détail.
- Extraction de motifs d'usage web et de flux de clics.
- Recommandation à partir d'éléments co-occurrents fréquents.
- Co-occurrence et découverte de motifs en bioinformatique.
- Toute tâche d'extraction d'itemsets fréquents à grande échelle où Apriori est trop lent.
Comment ça marche
Comment ça marche
Un premier balayage de la base de données compte le support de chaque élément et écarte ceux dont le support est inférieur au seuil minimum. Les éléments fréquents survivants sont triés par fréquence décroissante — cet ordre permet aux transactions de partager des préfixes d'arbre et maintient le FP-tree compact.
Formule
\text{scan DB: keep items with support} \ge \text{minsup, sort by frequency}Un second balayage insère chaque transaction (ses éléments fréquents, dans l'ordre trié) dans le FP-tree, incrémentant les compteurs le long des chemins de préfixes partagés et ajoutant de nouvelles branches si nécessaire. Une table d'en-tête relie toutes les occurrences de chaque élément, de sorte que l'arbre représente de manière compacte la structure fréquente de l'ensemble des données.
Formule
\text{second scan: insert each transaction's frequent items into the FP-tree}Pour chaque élément fréquent (traité du moins fréquent au plus fréquent), l'algorithme rassemble sa base de motifs conditionnels — l'ensemble des chemins de préfixes dans l'arbre qui co-apparaissent avec cet élément, chacun pondéré par son compteur. Cela capture le contexte dans lequel l'élément apparaît fréquemment.
Formule
\text{for each item: collect its conditional pattern base (prefix paths)}À partir de chaque base de motifs conditionnels, un FP-tree conditionnel plus petit est construit et extrait récursivement, générant des itemsets fréquents plus longs en ajoutant l'élément aux motifs trouvés dans son arbre conditionnel. La récursion se termine sur des arbres à chemin unique, dont les combinaisons d'itemsets sont énumérées directement — produisant tous les itemsets fréquents sans génération de candidats.
Formule
\text{build conditional FP-trees recursively to grow frequent patterns}Pièges courants
- Définir un support minimum trop bas, produisant une explosion d'itemsets.
- Supposer qu'il surpasse toujours Apriori — sur des données petites ou éparses, le gain est modeste.
- Oublier que les itemsets fréquents ne sont pas des règles ; la génération de règles est une étape distincte.
- Négliger les limites de mémoire lorsque le FP-tree ne peut pas être conservé en RAM.
Questions fréquentes
Comment FP-Growth est-il plus rapide qu'Apriori ?
Apriori génère et teste répétitivement des itemsets candidats, balayant la base de données de nombreuses fois. FP-Growth évite entièrement la génération de candidats : il compresse les données dans un FP-tree en deux balayages et extrait récursivement les motifs à partir de celui-ci. Cela élimine l'explosion combinatoire des candidats, offrant des gains de vitesse importants sur les données denses.
Qu'est-ce que le FP-tree ?
Un arbre de préfixes compressé des éléments fréquents de la base de données. Les transactions partageant un préfixe partagent un chemin, avec des compteurs de nœuds enregistrant le support, et une table d'en-tête relie les occurrences de chaque élément. Il stocke la structure fréquente de l'ensemble des données de manière compacte afin que les motifs puissent être lus sans re-balayage des données.
Comment FP-Growth se compare-t-il à ECLAT et aux règles d'association ?
FP-Growth, ECLAT et Apriori trouvent tous des itemsets fréquents ; ECLAT utilise une approche d'intersection de tidsets verticaux au lieu d'un arbre. Trouver des itemsets fréquents n'est que la première étape — les règles d'association (avec confiance/lift) sont générées à partir de ces itemsets dans une étape séparée.
Méthodes associées
Sources
Han, J., Pei, J., & Yin, Y. (2000). Mining frequent patterns without candidate generation. ACM SIGMOD Record, 29(2), 1–12.
Ouvrir la référence DOICopié.Han, J., Pei, J., Yin, Y., & Mao, R. (2004). Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1), 53–87.
Ouvrir la référence DOICopié.