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

Présentation :

Nous avons vu que l’algorihme 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 voluminineuses. Afn 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éequents 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 donnees 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éparement.

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 noeuds de noeuds préfixé par l’élément représenté.

Un noeud de l’arbre est composé par :

  • Le nom de l’item (nom-item). Il s’agit de l’item que représente le noeud.
  • Le nombre d’occurrence (count) de transaction où figure la portion de chemin jusqu’à ce noeud.
  • Un lien vers le noeud suivant dans l’arbre (node-link). Il s’agit d’un lien inter-noeud 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 noeud.

– 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 noeuds ayant ce même nom-item.

L’avantage de cette représentation des données est qu’il suffit de suivre les liens inter-noeuds 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 noeud racine de l’arbre {null} est d’abord crée. Durant ce même parcours, une branche sera créee 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 dun FP-tree construit

Exemple dun 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

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 noeud 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 strcuture 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

54 Responses to “L’algorithme FP-Growth – Les bases (1/3)”

  1. Han O'nime says:

    Merci pour l’ensemble de ces 3 articles, claire et précis!

    Concernant votre dernier paragraphe, je suis d’accord que pour une base de données volumineuse, la mémoire centrale sera très sollicitée. Mais ne pensez-vous que FP-growth en parrallèle (http://infolab.stanford.edu/~echang/recsys08-69.pdf), ou FP-growth avec les technologies du BiG Data (HDFS & MapReduce) pourraient résoudre ce problème?

    Merci d’avance pour votre réponse!

    PS: je suis étonné que vous ayez pris comme référence l’article publié en 2000 alors que les mêmes auteurs ont publié un autre article plus récent en 2004. Mais il reprend en grande partie l’article de 2000.
    http://ece.ut.ac.ir/dbrg/seminars/AdvancedDB/Spring%202010/sobhan%20moosavi%20nejad/resources/Mining%20frequent%20patterns%20without%20candidate%20generation.pdf

    • Lors d’une distribution d’un traitement, on vise toujours à repartir la charge et les ressources utilisées / nécessaires pour ce traitement. Donc par principe chacun des noeuds de la distribution, sera sollcité en fonction du volume des données qu’il a à traiter.

      MapReduce, produit beaucoup de données intermédiaires et pour peu que le modèle de données en entrée soit un peu complexe on va vite vers des saturations de la mémoire centrale. J’ai eu des cas où je devais faire appel à des bases NoSql pour stocker ces données intermédiaires.

      D’ailleurs j’ai travaillé sur un algorithme qui permettait de prévoir une distribution optimale des des données, un travail future serait d’intégrer la dimension de complexité des données afin de prévoir des éventuels dépassement de la mémoire centrale.

      Concernant la référence, effectivement j’ai cité la version publiée en 2000, car mon intension était de montrer l’évolution en décrivant d’abord les bases puis montrer les améliorations.

Leave a Reply