Pour autant que je connaisse le développement d'algorithmes pour résoudre le problème de FPM (Frequent Pattern Mining), la route des améliorations a quelques points de contrôle principaux. Premièrement, l' algorithme Apriori a été proposé en 1993 par Agrawal et al. , ainsi que la formalisation du problème. L'algorithme a été capable de bande hors des ensembles des 2^n - 1ensembles (PowerSet) en utilisant un treillis pour maintenir les données. Un inconvénient de l'approche était la nécessité de relire la base de données pour calculer la fréquence de chaque ensemble étendu.
Plus tard, en 1997, Zaki et al. a proposé l'algorithme Eclat , qui a inséré la fréquence résultante de chaque ensemble à l'intérieur du réseau. Cela a été fait en ajoutant, à chaque nœud du réseau, l'ensemble des identifiants de transaction qui avaient les éléments de la racine au nœud référencé. La principale contribution est qu'il n'est pas nécessaire de relire l'ensemble de données pour connaître la fréquence de chaque ensemble, mais la mémoire requise pour conserver une telle structure de données peut dépasser la taille de l'ensemble de données lui-même.
En 2000, Han et al. a proposé un algorithme nommé FPGrowth , ainsi qu'une structure de données d'arbre préfixe nommée FPTree. L'algorithme a été en mesure de fournir une compression de données significative, tout en garantissant que seuls des jeux d'éléments fréquents seraient générés (sans génération de jeu d'éléments candidat). Cela a été fait principalement en triant les éléments de chaque transaction dans l'ordre décroissant, de sorte que les éléments les plus fréquents sont ceux avec le moins de répétitions dans la structure de données de l'arborescence. Etant donné que la fréquence descend seulement en traversant l'arbre en profondeur, l'algorithme est capable de dénuder-off itemsets non fréquents.
Modifier :
Pour autant que je sache, cela peut être considéré comme un algorithme de pointe, mais j'aimerais connaître d'autres solutions proposées. Quels autres algorithmes pour FPM sont considérés comme "à la pointe de la technologie"? Quelle est l' intuition / contribution principale de ces algorithmes?
L'algorithme FPGrowth est-il toujours considéré comme «à la pointe de la technologie» dans le cadre de l'exploration fréquente de motifs? Sinon, quel (s) algorithme (s) peut (peuvent) extraire plus efficacement des ensembles d'éléments fréquents de grands ensembles de données?
Réponses:
État 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 d'ensemble d'éléments fréquents. Il est facile à mettre en œuvre et à 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 - obtenir un travail basé sur APRIORI sera désormais très difficile.
Si vous avez une bonne implémentation, chaque algorithme a ses bonnes et ses mauvaises situations à mon avis. Une bonne mise en œuvre APRIORI sera seulement besoin d'analyser la base de données k fois pour trouver tous les itemsets fréquents de longueur k . En particulier, si vos données s'insèrent dans la mémoire principale, cela n'est pas cher. Ce qui peut tuer APRIORI, c'est trop de jeux de 2 éléments fréquents (en particulier lorsque vous n'utilisez pas un Trie et des techniques d'accélération similaires, etc.). Il fonctionne mieux sur des données volumineuses avec un faible nombre d'ensembles d'éléments fréquents.
Eclat travaille sur les colonnes; mais il doit lire chaque colonne beaucoup plus souvent. Il y a du travail sur les diffsets pour réduire ce travail. Si vos données ne rentrent pas dans la mémoire principale, Eclat souffre probablement plus qu'Apriori. En allant d'abord en profondeur, il sera également en mesure de renvoyer un premier résultat intéressant beaucoup plus tôt qu'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 conception, il ne peut pas exploiter la taille aussi soigneusement qu'Apriori.
FPGrowth compresse l'ensemble de données dans l'arborescence. Cela fonctionne mieux lorsque vous avez de nombreux enregistrements en double. Vous pourriez probablement récolter également quelques gains pour Apriori et Eclat si vous pouvez trier vos données et fusionner les doublons en vecteurs pondérés. FPGrowth le fait à 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 plus dans la mémoire, il devient difficile à mettre en œuvre.
Quant aux résultats de performance et aux benchmarks - ne leur faites pas confiance. Il y a tellement de choses à implémenter incorrectement. Essayez 10 implémentations différentes et vous obtenez 10 résultats de performances très différents. En particulier pour APRIORI, j'ai l'impression que la plupart des implémentations sont cassées dans le sens de manquer certaines des principales contributions d'APRIORI ... et de celles qui ont ces bonnes parties, la qualité des optimisations varie beaucoup.
Il existe même des articles sur la façon de mettre en œuvre efficacement ces algorithmes:
Vous pouvez également vouloir lire ces sondages sur ce domaine:
la source
La plupart des approches récentes des modèles fréquents que j'ai vues dans la littérature sont basées sur l'optimisation de FPGrowth. Je dois admettre que je n'ai pas vu beaucoup de développements dans la littérature dans FPM depuis de nombreuses années.
Ce wikibook met en évidence de nombreuses variantes de FPGrowth qui existent.
la source