L’algorithme FP-Growth – Les bases (1/3)

Nous avons vu que l’algorithme Apriori effectue plusieurs passes (scans) de la base de données. Ceci peut être très pénalisant lorsqu’il s’agit de données volumineuses.

Afin d’éviter les parcours répétés de la base de données, Han et al. [1] ont proposé  une méthode différente des approches par niveaux permettant d’extraire des itemsets fréquents sans génération de candidats.
Cette méthode s’appelle FP-growth (Frequent Pattern growth). Elle consiste d’abord à compresser la base de données en une structure compacte appelée FP-tree (Frequent Pattern tree), puis à diviser la base de données ainsi compressée en sous projections de la base de données appelées bases conditionnelles.
Chacune de ces projections est associée à un item fréquent. L’extraction des itemsets fréquents se fera sur chacune des projections séparément.

L’algorithme FP-growth apporte ainsi une solution au problème de la fouille de motifs fréquents dans une grande base de données transactionnelle. En stockant l’ensemble des éléments fréquents de la base de transactions dans une structure compacte, on supprimer la nécessité de devoir scanner de façon répétée la base de transactions. De plus, en triant les éléments dans la structure compacte, on accélère la recherche des motifs.

Structure d’un FP-tree :

Deux éléments essentiels constituent la structure d’un FP-tree. Ainsi les deux éléments qui composent cette structure sont :

1. Une structure sous forme d’un arbre avec une racine étiquetée ‘null’.
2. Un index (une table des pointeurs des items fréquents).

– L’arbre quant à lui est composé, comme indiqué, d’une racine ‘null’ et d’un ensemble de nœuds de nœuds préfixé par l’élément représenté.

Un nœud de l’arbre est composé par :

• Le nom de l’item (nom-item). Il s’agit de l’item que représente le nœud.
• Le nombre d’occurrence (count) de transaction où figure la portion de chemin jusqu’à ce nœud.
• Un lien vers le nœud suivant dans l’arbre (node-link). Il s’agit d’un lien inter-nœud vers les autres occurrences du même élément (ayant le m^me nom-item) figurant dans d’autres séquences de transactions. Cette valeur prend la valeur null s’il n’y a pas un tel nœud.

– L’Index est une table d’en-tête qui contient la liste des items fréquents et qui pointe sur la première occurrence de chaque élément. Chaque entrée dans cette table contient :

• Le nom de l’élément (nom-item).
• Le pointeur tête de la séquence des nœuds ayant ce même nom-item.

L’avantage de cette représentation des données est qu’il suffit de suivre les liens inter-nœuds pour connaître toutes les associations fréquentes où figure l’élément fréquent.

Construction d’un FP-Tree :

La construction du FP-tree nécessite deux parcours de la base des transactions (T) et se fait de la manière suivante :

1. On effectue un premier parcours de la base T pour déterminer les items fréquents en fonction du support minimum fourni.  Ces items seront triés par la suite par ordre décroissant de support dans une liste (L). Les items ainsi triés seront traités dans cet ordre.
2. Un second parcours de T est alors effectué. Chaque transaction est alors triée selon l’ordre des items dans L. Le nœud racine de l’arbre {null} est d’abord crée. Durant ce même parcours, une branche sera créée pour chaque transaction, mais des transactions ayant un même préfixe partageront le même début d’une branche de l’arbre, ainsi deux transactions identiques seront représentées par une seule et même branche.

La raison pour laquelle les items sont traités du plus fréquent au moins fréquent est que les items fréquents seront proches de la racine et seront mieux partagés par les transactions. Ceci fait du FP-tree une bonne structure compacte pour représenter les bases transactionnelles.

Exemple d’un FP-tree construit à partir d’une base de transactions

Récapitulatif de l’algorithme FP-tree :

Les différentes étapes de l’algorithme Fp-growth peuvent être résumées comme indiqué dans cette illustration.

Algorithme FP-growth

Avantages et inconvénients :

L’avantage majeur de l’algorithme est qu’il ne fait que deux balayages de la base des transactions. Le premier balayage étant pour trouver les k-itemset puis trier le résultat pour construire la liste des items fréquents dans T en ordre de fréquence. Le deuxième balayage ayant pour but la construction de la structure FP-tree. Aussi il peut être qualifié de :

• Complet :
  • puisqu’il contient toutes les informations sur les éléments fréquents
  • à chaque éléments fréquent correspond un chemin dans l’arbre.

• Concis :
  • puisqu’il ne contient que les éléments fréquents. les items sont classés en ordre de fréquence décroissante.
  • Plus un item est fréquent, plus il sera utilisé par les itemsets fréquent. Par conséquent son nœud sera utilisé souvent.

Néanmoins, malgré sa structure compacte, cela ne garantit pas, dans le cas ou la base de transactions est trop volumineuse, que toute la structure du FP-tree tiendra en mémoire centrale. De plus la construction de la structure FP-tree peut s’avérer longue et pourrait consommer beaucoup de ressources système.

Lire la suite de cet article:
L’algorithme FP-Growth – Construction du FP-tree (2/3)

[1] Han, J., Pei, J., Yin, Y., (2000). Mining Frequent Patterns without Candidate Generation. Proc. 2000 ACMSIGMOD Int. Conf. on Management of Data (SIGMOD’00), Dallas, TX