Algorithmes pour la découverte de motifs profitables

"La fouille de données est un domaine important de l'informatique portant sur la découverte d'informations nouvelles, inattendues et utiles dans des bases de données. Un problème important est la découverte des motifs fréquents, qui consistent à découvrir des itemsets (ensemble d'articles) achetés fréquemment dans des transactions de consommateurs. Les algorithmes classiques pour ce problème souffrent toutefois d'une limite importante : ils ne considèrent pas la quantité des articles (items) dans les transactions et leur profit unitaire. Par conséquent, ces algorithmes peuvent découvrir de nombreux motifs fréquents qui rapportent un faible profit et ignorer les motifs rares générant un profit élevé. Pour pallier cette limite, la découverte de motifs profitables (générant un haut profit) a émergé comme un problème important. Néanmois, les algorithmes actuels souffrent de limites importantes. Tout d'abord, plusieurs de ces algorithmes ne considèrent pas l'ordonnancement des achats et la confiance, c'est-à-dire la propabilité qu'un client achète un produit sachant ses achats antérieurs, ce qui est désirable par exemple, pour la recommandation de produits. De plus, ces algorithmes sont généralement très demandant en termes de mémoire et temps d'exécution. Dans cette thèse, nous proposons deux algorithmes efficients pour la découverte des motifs profitables, afin de pallier ces limites. Le premier, HUSRM, est conçu pour être appliqué à des bases de données séquences de transactions. Il vise la découverte de règles séquentielles de la X Y indiquant que l'achat de certains articles X implique l'achat d'autres articles Y avec une certaine confiance, et rapporte un profit élevé. Des résultats expérimentaux sur plusieurs jeux de données montrent que HUSRM est 25 fois plus rapide et consomme 50% moins de mémoire qu'une version sans optimisations. Le second, EFIM, est appliqué à des bases de données de transactions sans ordre temporel. Il vise à réduire la consommation en mémoire et temps d'exécution pour la découverte des itemsets profitables. EFIM introduit plusieurs nouvelles stratégies pour élaguer l'espace de recherche et réduire la complexité du problème. Une étude expérimentale approfondie montre que EFIM est jusqu'à 7000 fois plus rapide et consomme moins de mémoire que plusieurs algorithmes de la littérature."--Résumé.

Name thesis:degree_name

Maîtrise ès sciences (informatique)

Level thesis:degree_level

2e cycle

Discipline thesis:degree_discipline

Faculté des sciences

Grantor dc:publisher

Université de Moncton

Year dc:date.issued

2015

Author dc:creator

• Zida, Souleymane

Advisor dc:contributor.advisor

• Fournier-Viger, Philippe

• Exploration de données (Informatique)
• Algorithmes
• Extraction de règles d'association
• Traitement séquentiel (Informatique)
• Systèmes experts (Informatique)
• Commerce électronique

Statement dc:rights

• Author

Language dc:language.iso

iso639-2b, fre

Identifier

oclc: 946589262

Dc Identifier Other

umir:1799

OAI identifier oai:identifier

oai:umoncton.scholaris.ca:20.500.14658/6520