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

 

Présentation :

Cet article constitue la troisième et dernière partie de la serie 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 à identifer les itemssets fréquents.

Occurences des items

Occurences des items

FP-tree - Etat final

Etat fina de la structure FP-tree

Rappelons que, dans notre exemple le support minimum à été défini à 3, et que la table des enêtes a été triée en fonction du poids (nombre d’occurences) 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 noeuds et la table des entêtes afin de faciliter la navigation. Par conséquent tous les noeuds ai peuvent être atteints en suivant la chaine des pointeurs des champs noeud-lien en commençant par celui de la table des pointeurs correspondant à l’item fréquent ai.

Egalement, tous les motifs contenant ai doivent être un sous-ensemble d’un chemin partant d la racine et contenant ai.

Identifier les motifs fréquent contenant p :

Pour identifer les motifs fréquents contenant l’élément p, la table des entêtes est parcourue de bas en haut ; commencant 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.

Motifs de base p-conditionné

Motifs de base p-conditionné

 

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

  • (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’occurence 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, appellé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 occure. Pour trouver tous les motifs fréquents contenant un élément (en l’occurence ‘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éaquents 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 ca c’est le seul élément qui un nombre d’occurences 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 prioritiser comme décrit précédemment. La valeur de l’occurence 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.

Tableau récapitulatif des base des motifs x-conditionnés

Tableau récapitulatif des base des motifs x-conditionnés

 

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

Leave a Reply