L’algorithme
FP Growth
Omar Talbi – Slim Yaich
01 Notion FP Growth
Etude comparative
02 entre FP Growth et A 03 Application de l’
priori Algorithme FP Growth
04 Conclusion
Notion de FP Growth
Algorithme Principe Structure
● C’est un algorithme ● Même principe que ● Structure
de génération des l’algorithme a priori sauf
cet algorithme a le rôle
arborescente
règles d’association
de résoudre les (FP-Tree)
inconvénients de
l’algorithme a priori.
A priori vs FP Growth
A priori FP Growth
● Le nombre d’accés aux bases de Vs ● Nombre d’accès au base des
données est lente . données est égale à 2
● Le nombre des items sets ● Génère les itemset fréquents sans
candidats augmente en fonction de utilisation des itemset candidate
la taille de base de données
Phase 1 : Construction de FP Tree
• Le 1er Scan de la base de donnée pour extraire les item sets fréquents En utilisent le paramètre
Min Support Count = 2
Nombre A B C D E F
des
Tickets
T1 1 1 0 0 1 0
T2 0 1 0 1 0 0
T3 0 1 1 0 0 0
T4 1 1 0 1 0 0
T5 1 0 1 0 0 0
T6 0 1 1 0 0 0
T7 1 0 1 0 0 0
T8 1 1 1 0 1 0
T9 1 1 1 0 0 1
Application de l’algorithme : FP Growth
Nombre des Tickets Produits
T1 A,B,E
T2 B,D
T3 B,C
T4 A,B,D
T5 A,C
T6 B,C
T7 A,C
T8 A,B,C,E
T9 A,B,C, F
Application de l’algorithme : FP Growth
Nombre des Tickets Produits
T1 A,B,E
T2 B,D
T3 B,C
T4 A,B,D
T5 A,C
T6 B,C
T7 A,C
T8 A,B,C,E
T9 A,B,C, F
Application de l’algorithme : FP Growth
Produits Support
A 6 >= 2 : Fréquent
B 7 >= 2 : Fréquent
C 6 >= 2 : Fréquent
D 2 >= 2 : Fréquent
E 2 >= 2 : Fréquent
F 6 < 2 : Non Fréquent
Application de l’algorithme : FP Growth
Produits Support
B 7
A 6
C 6
D 2
E 2
Application de l’algorithme : FP Growth
Tn Produits Produits Selon poids
plus fort
T1 A,B,E
T2 B,D
T3 B,C
T4 A,B,D
T5 A,C
T6 B,C
T7 A,C
T8 A,B,C,E
T9 A,B,C, F
Application de l’algorithme : FP Growth
Tn Produits Produits Selon poids
plus fort
T1 A,B,E B, A, E
T2 B,D B, D
T3 B,C B, C
T4 A,B,D B, A, D
T5 A,C A, C
T6 B,C B, C
T7 A,C A, C
T8 A,B,C,E B, A, C, E
T9 A,B,C, F B, A, C
Construction de l’arbre FP-Tree
Conclusion :
➔ Même si on utilise ces deux algorithmes différents : on trouve les mêmes
règles d’association à la fin
TD
