Bonsoir,
Je pense avoir compris l'algo mais j'arrive pas a comprendre les exemples de pseudocode que je trouve.
En gros : On construit l'arbre et on a un index des items classés en ordre décroissant (nombre de fois qu'on les comptes dans la base des transactions).
On commence par le plus petit de ces items et on trouve les chemins qui mènent a lui. Pour parvenir a cet item on doit passer par des noeuds qui ont tous un poids , on assigne a tous les noeuds de ce chemin le plu petit poids qu'on trouve parmi ces noeuds.
On se retrouve avec pleins de chemins qui sont appelés des "Conditional Pattern Base" de cet item choisi , de ceux ci on choppe les Conditional FP tree. Ceux ci sont construit en regardant quel chemin sont pris au moins autant que le nombre support chosi au début.
Ici si j'ai bien compris on se retrouve donc avec seulement un chemin avec une branche ? Une fois qu'on a ca on essaie toutes les combinaisons et on a les "frequent patterns" et c'est terminé.

Je pense que je capte pas encore tout mais que j'y suis presque puisque dans le pseudo code ca parle de quand on a un seul chemin.
Voici le pseudocode que j'essaie de comprendre :

Tu cherches a faire quoi exactement?

Le 16 mai 2017 à 04:56:13 Godrik a écrit :
Tu cherches a faire quoi exactement?

A implementer cet algo, mais d'abord comprendre mieux l'image.
J'ai suivi cette explication (et d'autres sites) http://blog.khaledtannir.net/2012/07/lalgorithme-fp-growth-les-bases-13/ que j'ai trouver clair (sauf vers la fin du 3ieme article).

D'accord, tu cherches a resoudre le probleme "frequent itemset mining".

Quel est ton probleme ?

Le papier dans sigmod est beaucoup plus clair que le blog:

https://www.cs.sfu.ca/~jpei/publications/sigmod00.pdf

Le 16 mai 2017 à 21:20:51 Godrik a écrit :
Le papier dans sigmod est beaucoup plus clair que le blog:

https://www.cs.sfu.ca/~jpjpei/publications/sigmod00.pdf

Oui j'ai survolé celui ci http://www.philippe-fournier-viger.com/spmf/fpgrowth_04.pdf et c'etait plus clair et détaillé aussi.
Je pense avoir mieux compris.J'ai essayé de coder quelquechose mais je bloque a comment representer l'arbre. Je tente ca en python et j'aimerai faire l'arbre moi meme.
Pour moi y'a l'id, l'id du parent, l'item, le compteur qui compte pour chaque noeud.

Et je m'embrouille avec la recursion.
arbre (premier item et reste de la transaction, noeud ):
si l'item n'est pas la alors on crée le noeud
sinon on incremente son compteur
si le reste de la transaction n'est pas vide
arbre( premier item du reste de la transaction et le reste, noeud+1)

Mais ca pars en couille dans mon code et avec mon modele d'arbre qui est :

tree = { parent_id : [[id, letter, count],[id, letter, count]] ,
etc
}

Une fois qu'on a les groupes d'items fréquents comment efficacement en déduire les regles d'association. Je sais que la regle "si ce sous ensemble d'items n'est pas fréquent alors un ensemble plus grand contenant ce sous ensemble ne le sera pas non plus". Donc ca élimine pleins de combinaisons.

Ah en fait c'est simple non ?
On a tous les frequents itemsets, de ceux ci on peux faire tout pleins de combinaisons possibles, et on a la regle : si un ensemble I est frequent alors tout sous ensemble de celui ci est frequent. Donc on sait automatiquement que toutes les combinaisons possibles seront aussi frequentes. Donc tout est a tester ? Mais ca fais un nombre immense de regles pour chaque itemset non ?
Faux faire entrer en jeu la confiance d'une regle et faire un meme type de raisonnement que les regles que j'ai citer c'est ca ?

On a nos frequent itemsets,dans chacun de ceux ci on test toutes les regles possibles comme dans cette image : http://3.bp.blogspot.com/-vadPCNKhYCw/Ttu0gP_u3sI/AAAAAAAAAqc/ykf_6O-dVMg/s1600/Screen+shot+2011-12-04+at+2.57.39+PM.png On a la regle que si : S -> I-S (ou I c'est l'itemset et S un sous ensemble de I) n'est pas fréquent alors aucune des sous regles ne l'est non plus. On peux donc enlever des regles a tester (en gris).
J'ai du mal a trouver un moyen de faire ceci parce que je ne veux pas que les noeuds blancs retombent sur les regles enlévés (grises).
J'ai aussi l'impression de me parler tout seul De l'aide svp ^^

Je ne comprends pas bien tes question, c'est pour ca que je ne repondais pas. (Et je suis noye dnas l'administraton en ce moment.)

J'ai l'impression que tu confonds plusieurs algo, non?

L'enumeration des frequent itemset a partir du fp-TREE est donne en algo 2 de https://www.cs.sfu.ca/~jpei/publications/sigmod00.pdf

Le 22 mai 2017 à 14:56:03 Godrik a écrit :
Je ne comprends pas bien tes question, c'est pour ca que je ne repondais pas. (Et je suis noye dnas l'administraton en ce moment.)

J'ai l'impression que tu confonds plusieurs algo, non?

L'enumeration des frequent itemset a partir du fp-TREE est donne en algo 2 de https://www.cs.sfu.ca/~jpjpei/publications/sigmod00.pdf

Réponds pas si t'es occupé tkt pas ^^
Non je pense pas que je confonds ,une fois qu'on a les frequent itemsets faux aussi generer les regles d'ou ma question.
Quand je dis les regles c'est du genre si achete couche alors achete biere. couche => biere.