{"id":347,"date":"2012-07-12T18:12:01","date_gmt":"2012-07-12T16:12:01","guid":{"rendered":"http:\/\/blog.khaledtannir.net\/?p=347"},"modified":"2012-07-12T18:12:01","modified_gmt":"2012-07-12T16:12:01","slug":"lalgorithme-fp-growth-les-bases-13","status":"publish","type":"post","link":"https:\/\/khaledtannir.net\/en\/2012\/07\/12\/lalgorithme-fp-growth-les-bases-13\/","title":{"rendered":"L’algorithme FP-Growth – Les bases (1\/3)"},"content":{"rendered":"

Nous avons vu que l\u2019algorithme Apriori<\/a> effectue plusieurs passes (scans) de la base de donn\u00e9es. Ceci peut \u00eatre tr\u00e8s p\u00e9nalisant lorsqu’il s’agit de donn\u00e9es volumineuses.<\/p>\n

<\/p>\n

Afin d’\u00e9viter les parcours r\u00e9p\u00e9t\u00e9s de la base de donn\u00e9es, Han et al.<\/em> [1]<\/span> ont propos\u00e9<\/span><\/span>\u00a0<\/span> une m\u00e9thode diff\u00e9rente des approches par niveaux permettant d’extraire des itemsets fr\u00e9quents sans g\u00e9n\u00e9ration de candidats.
\nCette m\u00e9thode s’appelle FP-growth<\/strong> <\/span><\/span>(Frequent<\/span> <\/em><\/span><\/span>Pattern growth<\/em><\/span>). Elle consiste d’abord \u00e0 compresser la base de donn\u00e9es en une structure compacte appel\u00e9e FP-tree<\/strong> <\/span><\/span>(Frequent Pattern tree<\/span><\/em>), puis \u00e0 diviser la base de donn\u00e9es ainsi <\/span><\/span>compress\u00e9e en sous projections de la base de donn\u00e9es appel\u00e9es bases conditionnelles<\/span><\/span>.<\/span><\/span>
\nChacune <\/span><\/span>de ces projections est associ\u00e9e \u00e0 un item fr\u00e9quent. L’extraction des itemsets fr\u00e9quents se fera sur chacune des projections s\u00e9par\u00e9ment.<\/p>\n

L’algorithme FP-growth\u00a0<\/strong>apporte ainsi une solution au probl\u00e8me de la fouille de motifs fr\u00e9quents dans une grande base de donn\u00e9es transactionnelle. En stockant l\u2019ensemble des \u00e9l\u00e9ments fr\u00e9quents de la base de transactions dans une structure compacte, on supprimer la n\u00e9cessit\u00e9 de devoir scanner de fa\u00e7on r\u00e9p\u00e9t\u00e9e la base de transactions. De plus, en triant les \u00e9l\u00e9ments dans la structure compacte, on acc\u00e9l\u00e8re la recherche des motifs.<\/p>\n

<\/h2>\n

Structure d’un FP-tree :<\/span><\/span><\/h2>\n

Deux \u00e9l\u00e9ments essentiels constituent la\u00a0structure d’un FP-tree. Ainsi les deux \u00e9l\u00e9ments qui composent cette structure sont :<\/span><\/span><\/p>\n

    \n
  1. Une structure sous forme d’un\u00a0arbre avec une racine \u00e9tiquet\u00e9e ‘null’<\/em><\/span>.<\/span><\/span><\/li>\n
  2. Un index (une table des pointeurs des items fr\u00e9quents).<\/span><\/span><\/li>\n<\/ol>\n

    – L’arbre quant \u00e0 lui\u00a0<\/span><\/span>est compos\u00e9, comme indiqu\u00e9, d’une racine ‘null’<\/span> et d’un ensemble de n\u0153uds<\/span><\/span> de n\u0153uds pr\u00e9fix\u00e9 par l\u2019\u00e9l\u00e9ment repr\u00e9sent\u00e9.<\/p>\n

    Un n\u0153ud de l’arbre est compos\u00e9 par :<\/p>\n