L’algorithme FP-Growth – Identification des motifs fréquents (3/3)

 

Cet article constitue la troisième et dernière partie de la série consacrée à l’algorithme FP-Growth. Dans l’article précédent  j’ai introduit la construction d’une structure FP-tree, structure utilisée par l’algorithme FP-Growth pour stocker les informations concernant tous les motifs (itemsets) fréquents dans une base de transactions.

Dans cet article je vais présenter la manière dont sont identifiés les itemsets fréquents de la base de transactions à partir de la structure FP-tree construite à la suite du parcours des éléments de la bases de transactions. Le but étant de générer à partir de ces ensembles d’itemsets fréquents les règles d’associations.

Fonctionnement :

Pour expliquer comment sont identifiés les itemsets fréquents je vais me baser sur le même exemple de l’article précédent. A la fin de la deuxième étape de la construction du FP-tree nous avons pu définir la table des entêtes (Headers Table). Cette table, tout comme le FP-tree obtenu à la fin de la phase de construction, vont nous servir à identifier les itemssets fréquents.

 

 

Rappelons que, dans notre exemple le support minimum à été défini à 3, et que la table des entêtes a été triée en fonction du poids (nombre d’occurrences) de chaque élément. De même, seuls les éléments ayant un support > 3 ont été retenus lors de la préparation de la table des entêtes.
Lors de la construction du FP-tree, des liens ont été créés entre les nœuds et la table des entêtes afin de faciliter la navigation. Par conséquent tous les nœuds a_i peuvent être atteints en suivant la chaîne des pointeurs des champs nœud-lien en commençant par celui de la table des pointeurs correspondant à l’item fréquent a_i.
Egalement, tous les motifs contenant ai doivent être un sous-ensemble d’un chemin partant d la racine et contenant a_i.

Identifier les motifs fréquent contenant p :

Pour identifier les motifs fréquents contenant l’élément p, la table des entêtes est parcourue de bas en haut ; commençant par l’élément p de la table et se terminant par  l’élément c (le dernier élément f est ignoré).
A partir de la table des pointeurs, on parcours le FP-tree en suivants les pointeurs pour l’item fréquent p. Puis, nous créons tous les chemin à partir de la racine et se terminant par p pour former la base des motifs p-conditionnés. Ceci constitue l’ensemble des préfixes de p.

 

 

 

 

L’élément p peut être atteint en suivant deux chemins à partir de la racine : (élément : occurrence)

• (f:4, c:3, a:3, m:2, p:2)
• (c:1, b:1, p:1)

Les transactions contenant ‘p’ doivent avoir le nombre d’occurrence de p, par conséquent nous obtenons :

• (f:2, c:2, a:2, m:2, p:2)
• (c:1, b:1, p:1)

Etant donné que ‘p’ fait parti de ces transactions, nous pouvons l’ignorer et nos chemins, appelés Motif de Base Conditionné (Conditional Pattern Base, CPB) deviennent :

• (f:2, c:2, a:2, m:2)
• (c:1, b:1)

Un Chemin de Base Conditionné contient toutes les transactions dans lesquelles un élément occurre. Pour trouver tous les motifs fréquents contenant un élément (en l’occurrence ‘p’)n nous avons besoin de trouver tous les motifs fréquents dans le CPB puis leur ajouter l’élément. Ceci peut être fait avec la construction d’un nouveau FP-tree pour le CPB.

Pour terminer l’identification des motifs fréquents contenant p, on va, pour chaque motif dans la base des motifs p-conditionnés, puis évaluer le nombre de chaque item et construire le FP-tree correspondant à partir de cette base des motifs.

(f:2, c:2, a:2, m:2), (c:1, b:1) => (c:3)

Seul l’élément c est fréquent ça c’est le seul élément qui un nombre d’occurrences supérieur au support minimum. Là aussi, il  faut éliminer tous les éléments dont le support est inférieur au support minimum et les prioriser comme décrit précédemment. La valeur de l’occurrence du motif fréquent à identifier est extraite de la valeur du support obtenu par le sous-arbre. Par conséquent le motif fréquent contenant p est:

(p:3, cp:3)

Identifier les motifs fréquent contenant m :

Pour identifier les motifs fréquents contenant l’élément m, il suffit de suivre la même procédure de l’identification de l’élément p.
L’élément m peut être atteint en suivant deux chemins à partir de la racine, l’identification des chemins m-conditionnés nous donne :

• (f:4, c:3, a:3, m:2, p:2) => (f:2, c:2, a:2)
• (f:4, c:3, a:3, b:1, m:1) => (f:1, c:1, a:1, b:1)

Il faut noter que seuls les préfixes (tous ce qui est avant ‘m’) sont pris en considération. C’est un moyen systématique pour éviter de (re)considérer l’élément ‘p’.
L’élément b n’étant pas fréquent, il sera retiré. Par conséquent le FP-tree m-conditionné devient :

(f:3, c:3, a:3)

Les motifs fréquents identifiés reliés à l’élément m sont :

m, fm, cm, am, fcm, fam, cam, fcam

Concernant les autres éléments de la table des entêtes, la procédure est la même. Le tableau suivant récapitule les résultats obtenus.

 

 

Ainsi nous voilà arriver au terme de cet article, j’espère qu’il vous sera utile dans la compréhension de l’algorithme FP-Growth et n’hésitez pas à me faire part de vos commentaires et observations.

20 mai 2020