L’algorithme FP-Growth – Construction du FP-tree (2/3)

 

Présentation:

Cet article est le deuxième article de la série concernant l’algorithme FP-Growth. Dans le premier article j’ai présenté l’algorithme, son fonctionnement global ainsi que ses avantages et inconvénients.

Dans cet article je vais introduire la construction d’une structure FP-tree. Pour rappel, l’algorithme FP-Growth utilise une structure de donnée appelée Frquent Pattern tree. Il permet de trouver les itemsets fréquents dans une base de transactions. Grace à la structure FP-tree on conserve l’ensemble des éléments fréquents de la base des transactions dans une structure compacte. Ainsi il n’est plus nécessaire de devoir parcourir la base de transactions. De plus, ces éléments se retrouvent triés ce qui accélère la recherche des règles d’association.

Un Frequent Pattern tree est composé d’un noeud racine null associé à un ensemble de noeuds. Ces noeuds sont eux mêmes composés par :

  • Le nom de l’élément.
  • Le nombre d’occurence dans la base de transactions.
  • La portion du chemin (composée de tous les éléments rencontrés de la racine jusqu’au noeud concerné).
  • Un lien inter-noeud vers les autres occurences du même éléments figurant dans d’autres séquences de transactions.

 

L’avantage de cette structure de données est, qu’en suivant les liens inter-noeuds, on peut facilement connaître toutes les associations fréquentes où figure l’élément fréquent.

 

Etapes de la construction du FP-tree :

La construction d’une structure FP-tree passe par 6 étapes principales. les étapes 1 à 5 prépare la structure et insère les éléments qui doivent s’y trouver. La  sixième étape consiste à valider les information insérées dans les étapes précédentes :

  1. Calculer le support minimum
  2. Parcours de la base des transactions pour trouver la somme totale des différentes occurences.
  3. Définir la priorité des éléments, puis trier les items en fonction de leur priorité.
  4. Création du noeud racine.
  5. Insertion des noeuds enfants.
  6. Validation.

 

Etape 1:

Considérons la base de transactions suivante. Supposons que le support minimum est défini à 50%.

 

Base des Transactions

Base des Transactions

 

Dans notre cas, pour obtenir un support de 50%, il faut le calculer  ainsi :

Support minimum = (50/100 * 5) = 2.5

50 étant le pourcentage minimum demandé, 5 étant le nombre total de transactions dans la base.

Si la valeur obtenue n’est pas entière, elle sera arrondie . (par exemple : ceiling(50/100 * 5) = 3

Le résultat obtenu, 3 dans notre cas, constitue le support minimum et par conséquent tous les items da la base de transactions ayant un suport inférieur à 3 occurences minimum sera ignoré.

Cette étape étant terminée, passons à l’étape suivante.

 

Etape 2 :

Dans cette étape nous allons parcourir la base de transactions afin de calculer les fréquences des éléments qui s’y trouvent. Par la suite, une fois les différentes fréquences obtenues, seuls les éléments dont la fréquence est supérieure au support minimum défini dans l’étape 1 seront retenus, les autres seront ignorés.  Dans notre cas, le tableau suivant représente les items retenus ainsi que leurs nombre d’occurence respectif.

Occurences des items

Occurences des items

La table ainsi obtenue constitue la table des entêtes (Headers Table) appellée aussi la table des pointeurs. Maintenant que nous avons determiné nos différents items, il faut les prioritiser. Cette tâche est réalisée dans la prochaine étape de la construction.

 

Etape 3 :

Cette étape consiste à ordonner les différents éléments en fonction de leur poids. Il s’agit de les trier en fonction de leur nombre d’occurences. Ce tri s’effectue en ordre décroissant, l’élément ayant comptabilisé le plus grand nombre d’occurences est placé en tête et l’élément ayant comptabilisé le moins d’occurences est placé en queue. Ce traitement sera effectué pour chacune des lignes de transactions contenues dans la base des transactions.

Items Fréquents Ordonnés

Items Fréquents Ordonnés

Dans notre cas, l’élément f ayant un support de 4 est placé en tête, l’élément p quant à lui a un support de 3 est par conséquent il se retrouve en dernière position.

A la fin de cette étape, on peut considérer que tout est prêt pour commencer la construction de la structure FP-tree avec la création et l’insértion des différents noeuds.

 

Etape 4 :

A partir du résultat obtenu lors de l’étape précédente, nous commençons la construction de la structure FP-tree. Tout d’abord l’élément ‘Racine’ de l’arbre est créé. Cet élément racine ne contiendra aucun élément. Il contiendra uniquement des liens vers ses éléments enfants.

On commence par parcourir chaque élément de la transaction (voir illustration plus loin). Puis pour chaque élément de la transaction on vérifie l’éxistance d’un noeud correspondant, s’il n’existe pas, le noeud est créé, dans le cas contraire le nombre d’occurence est incrémenté. Puis pour chaque élément créé on va établir un lien depuis la table des entêtes vers l’élément inséré dans l’arbre.

A ce stade l’arbre est encore vide, donc la procédure de vérification de l’exsitance d’un noeud en particulier indiquera qu’il n’existe pas et par conséquent il faudra le créer.

La première transaction est composée des éléments (f, c, a, m, p) triés par ordre décroissant en fonction de leur poids. L’élément f étant le premier de la liste, un noeud correspondant est inséré à partir de l’élément racine de l’arbre. Le noeud f contient le compte de 1 car c’est la première fois que l’on insère cet élément. Un lien est établi entre l’élément racine de l’arbre et l’élément f puis un autre lien est établi à partir de la table des entêtes. On porsuit de même avec les éléments suivants (c, a, m, p). Ainsi on obtient la structure illustrée par cette figure.

Insertion des éléments dans FP-tree

 

Etape 5 :

La construction se poursuit avec la deuxième transaction qui est composée des éléments (f, c, a, b, m). Cette fois-ci l’arbre contient des éléments et par conséquent pour chaque élément trouvé son nombre d’occurences est incrémenté de 1.

La transaction contient l’élément f, l’arbre aussi. Par conséquent le nombre d’occurence de f passe à 2 (1 + 1). Il en est de même pour les élémens c, et a. Nous arrivons à l’élément b. Il n’existe pas d’éléments b correspondant, donc un nouveau noeud est créé à partir de notre position actuelle, c.à.d le noeud a et un nouveau lien est créé à partir de a vers b puis un lien à partir de la table des entêtes vers le nouveau élément inséré. Concenrnat l’élément m restant, étant donné qu’il n’existe pas de noeud correspondant à partir de notre position (noeud b) un nouveau noeud est créé et initialisé avec une valeur de 1, puis en plus du lien créé à partir de l’élément b, un lien est créé à partir du noeud m déjà existant. Ceci est illustré par la figure ci-dessous.

 

Construction FP-tree à partir de la 2ème transaction

Construction FP-tree à partir de la 2ème transaction

 

A la fin du traitement de toutes les transactions de la base la structure finale de Fp-tree est illustrée par la figure suivante.

FP-tree - Etat final

Etat final de la structure FP-tree

 

Etape 6 :

Cette dernière étape consiste à valider les informations de l’arbre. Comment savoir si elles sont correctes ? La réponse à cette question est très simple, il suffit de comparer les informations obtenues à partir des différents noeuds de l’arbre avec les informations de la table des entêtes.

Pour cela, il faut compter, et additionner si besoin, toutes les occurences d’un éléments dans l’arbre et comparer le résultat obtenus à celui stocké dans la table des entêtes.

Ainsi après avoir compter tous les éléments de la structure, on obtient le résultat suivant :

(f:4, c:4, a:3, b:3, m:3, p:3) ce qui est conforme à la tables des entêtes.

 

Conculsion :

Dans cette article j’ai présenté la structure d’un FP-tree qui est une structure compacte utilisée pour représenter les itemsets fréquents en guise de leurs utilisations dans la génération de règles d’associations. Cette structure exaustive préserve toutes les informations des itemsets fréquents. Aussi, cette structure est compacte puisqu’elle ne génère aucun itemset qui ne soit pas fréquent et les classe en fonction de leur fréquence en ordre décroissant. Ainsi, la taille de FP-tree est directement liée au nombre maximal d’itemsets fréquents contenus dans la base de transactions.

 

L’article suivant présentera la technique d’identification itemsets fréquents à partir du FP-tree.

58 Responses to “L’algorithme FP-Growth – Construction du FP-tree (2/3)”

  1. supermec says:

    Super article! simple et bien fait! merci!!

Leave a Reply to supermec