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

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 Frequent 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 nœud racine null associé à un ensemble de nœuds. Ces nœuds sont eux mêmes composés par :

• Le nom de l’élément.
• Le nombre d’occurrence dans la base de transactions.
• La portion du chemin (composée de tous les éléments rencontrés de la racine jusqu’au nœud concerné).
• Un lien inter-nœud vers les autres occurrences 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-nœuds, 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 occurrences.
3. Définir la priorité des éléments, puis trier les items en fonction de leur priorité.
4. Création du nœud racine.
5. Insertion des nœuds enfants.
6. Validation.

 

Etape 1:

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

 

 

 

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 de la base de transactions ayant un support inférieur à 3 occurrences 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’occurrence respectif.

 

 

 

La table ainsi obtenue constitue la table des entêtes (Headers Table) appelée aussi la table des pointeurs. Maintenant que nous avons déterminé 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’occurrences. Ce tri s’effectue en ordre décroissant, l’élément ayant comptabilisé le plus grand nombre d’occurrences est placé en tête et l’élément ayant comptabilisé le moins d’occurrences est placé en queue. Ce traitement sera effectué pour chacune des lignes de transactions contenues dans la base des transactions.

 

 

 

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’insertion des différents nœuds.

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’existence d’un nœud correspondant, s’il n’existe pas, le nœud est créé, dans le cas contraire le nombre d’occurrence 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’existence d’un nœud 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 nœud correspondant est inséré à partir de l’élément racine de l’arbre. Le nœud  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 poursuit de même avec les éléments suivants (c, a, m, p). Ainsi on obtient la structure illustrée par cette figure.

 

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’occurrences est incrémenté de 1.
La transaction contient l’élément f, l’arbre aussi. Par conséquent le nombre d’occurrence de f passe à 2 (1 + 1). Il en est de même pour les éléments c, et a. Nous arrivons à l’élément b. Il n’existe pas d’éléments b correspondant, donc un nouveau nœud est créé à partir de notre position actuelle, c.à.d le nœud 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é. Concernant l’élément m restant, étant donné qu’il n’existe pas de nœud correspondant à partir de notre position (nœud b) un nouveau nœud 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 nœud m déjà existant. Ceci est illustré par la figure ci-dessous.

 

 

 

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.

 

 

 

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 nœuds de l’arbre avec les informations de la table des entêtes.
Pour cela, il faut compter, et additionner si besoin, toutes les occurrences 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.

Conclusion :

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 exhaustive 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.

20 mai 2020