Est-FPGrowth toujours considéré comme « l'état de l'art » dans fréquente extraction de motifs?

Question

Pour autant que je sais le développement d'algorithmes pour résoudre le problème des mines Motif fréquent (FPM), la route des améliorations ont des points de contrôle principaux. Tout d'abord, l'algorithme Apriori a été proposé en 1993, par Agrawal et al. , ainsi que la formalisation du problème. L'algorithme a pu strip-off certains ensembles des ensembles de 2^n - 1 (de PowerSet) en utilisant un treillis pour maintenir les données. Un inconvénient de cette approche était la nécessité de relire la base de données pour calculer la fréquence de chaque ensemble élargi.

Plus tard, l'année 1997, Zaki et al. proposé l'algorithme Eclat , qui inséré la fréquence résultante de chaque jeu à l'intérieur du réseau . Cela a été fait en ajoutant à chaque nœud du réseau, l'ensemble des transactions ids qui avaient les éléments de la racine au nœud appelé. La principale contribution est que l'on n'a pas à relire l'ensemble des données de connaître la fréquence de chaque jeu, mais la mémoire nécessaire pour maintenir une telle structure de données construite peut dépasser la taille de l'ensemble de données lui-même.

En 2000, Han et al proposé un algorithme nommé FPGrowth , ainsi que d'une structure de données préfixe arbre nommé FPTree. L'algorithme a pu fournir une compression de données importantes, tout en accordant également ce serait cédé (sans génération de itemset candidat) ne itemsets fréquents. Cela a été fait principalement par le tri des éléments de chaque transaction par ordre décroissant, de sorte que les éléments les plus fréquents sont ceux qui ont le moins de répétitions dans la structure de données d'arbre. Étant donné que la fréquence descend seulement en traversant l'arbre en profondeur, l'algorithme est capable de strip-off itemsets non fréquents.

Modifier :

Pour autant que je sache, cela peut être considéré comme un état de l'art algorithme, mais je voudrais savoir sur les autres solutions proposées. Quels sont les autres algorithmes pour FPM sont considérés comme « l'état de l'art »? Quel est le l'intuition / principale contribution de ces algorithmes?

L'algorithme est FPGrowth toujours considéré comme « état de l'art » dans fréquente extraction de motifs? Sinon, quel algorithme (s) peut extraire de itemsets fréquents grands ensembles de données plus efficacement?

Answer 1

Etat de l'art comme: utilisé dans la pratique ou travaillé en théorie

APRIORI est utilisé partout, sauf dans le développement de nouveaux algorithmes fréquents itemset. Il est facile à mettre en œuvre et facile à réutiliser dans des domaines très différents. Vous trouverez des centaines d'implémentations APRIORI de qualité variable. Et il est facile de se tromper APRIORI, en fait.

FPgrowth est beaucoup plus difficile à mettre en œuvre, mais aussi beaucoup plus intéressant. Donc, d'un point de vue académique, tout le monde essaie d'améliorer FPgrowth -. Le travail se base sur APRIORI acceptée sera très difficile maintenant

Si vous avez une bonne mise en œuvre, chaque algorithme a il est bon et ce qui est mauvais situations à mon avis. Une bonne mise en œuvre APRIORI sera uniquement besoin de scanner la base de données k pour trouver toutes les fois itemsets fréquents de longueur k . En particulier si vos données se insère dans la mémoire principale est ce pas cher. Que peut tuer APRIORI est trop 2-itemsets fréquents (en particulier lorsque vous ne pas utiliser de techniques d'accélération et similaires, etc. Trie). Il fonctionne mieux sur les grandes données avec un faible nombre de motifs fréquents.

Éclat fonctionne sur des colonnes; mais il a besoin de lire chaque colonne beaucoup plus souvent. Il y a quelques travaux sur diffsets pour réduire ce travail. Si vos données ne rentre pas dans la mémoire principale, souffre probablement Éclat plus de Apriori. En profondeur allant d'abord, il sera également en mesure de retourner un premier résultat intéressant beaucoup plus tôt que Apriori, et vous pouvez utiliser ces résultats pour ajuster les paramètres; vous avez donc besoin de moins d'itérations pour trouver de bons paramètres. Mais par la conception, il ne peut pas exploiter la taille aussi nettement que Apriori a fait.

FPGrowth comprime le jeu de données dans l'arbre. Cela fonctionne mieux quand vous avez beaucoup d'enregistrements en double. Vous pourriez probablement récolter des gains de tout à fait pour Apriori et Éclat aussi si vous pouvez pré-trier vos données et les doublons de fusion dans des vecteurs pondérés. FPGrowth fait cela à un niveau extrême. L'inconvénient est que la mise en œuvre est beaucoup plus difficile; et une fois que cet arbre ne rentre pas dans la mémoire plus il devient un gâchis à mettre en œuvre.

En ce qui concerne les résultats de la performance et de référence - ne leur fait pas confiance. Il y a tellement de choses à mettre en œuvre de manière incorrecte. Essayez 10 implémentations différentes, et vous obtenez 10 résultats très différents de performance. En particulier pour APRIORI, j'ai l'impression que la plupart des implémentations sont brisées dans le sens de manquer quelques-unes des principales contributions de APRIORI ... et de ceux qui ont droit ces pièces, la qualité des optimisations varie beaucoup.

Il y a papeier même sur la façon de mettre en œuvre ces algorithmes efficacement:

  

efficace de Implémentations Apriori et Eclat. Christian Borgelt
Atelier de Frequent Ensemble d'Implémentations Mining (FIMI 2003, Melbourne, FL, USA).

Vous pouvez également lire ces enquêtes sur ce domaine:

•   

  Goethals, Bart. « Enquête sur l'exploitation minière de modèle fréquemment. » Univ. d'Helsinki (2003).

•   

  Ferenc Bodon, Enquête sur itemset Mining fréquente, Rapport technique, Budapest University of Technology et économique, 2006,

•   

  Frequent Item Set Mining Christian BORGELT Wiley Avis interdisciplinaires: Data Mining et Knowledge Discovery 2 (6): 437-456. 2012

Answer 2

La plupart du récent modèle fréquent approche que je l'ai vu dans la littérature sont basées sur l'optimisation FPGrowth. Je dois admettre, je ne l'ai pas vu beaucoup de développements dans la littérature en FPM dans de nombreuses années.

moments forts de nombreux Cette Wikibook les variantes sur FPGrowth qui sont hors il.