Condensed representations of frequent sets : application to descriptive pattern discovery
Institution:
Lyon, INSADisciplines:
Directors:
Abstract EN:
Interesting pattern discovery has recently seen an impressive progress, due to an increasing pressure from owners of large data sets and to the response of scientists by numerous theoretical and practical results. The most of data sets addressed in the beginning of the surge were sales data and the interesting patterns were in form of association rules. Very efficient solutions to this practical problem were elaborated, the root of them was the so-called APRIORI algorithm. Then, the owners of other types of data wondered if these basic methods could help them. Unfortunately, their data were different. Often, these applications could not take advantage of APRIORI. The research following the elaboration of the basic solution addressed the important application areas, where the basic solution could not be used. We addressed the problems with mining frequent patterns in different applicative contexts, especially the problems related to the large number of interesting frequent patterns present in data that are not similar to the sales data. Our methods mine a collection of patterns that may be quite different from the target pattern collection, and hopefully much more efficient to be mined in some types of data. Moreover, that different pattern collection must allow a subsequent "regeneration" of the target collection in a very efficient manner. Since the intermediate representation will be often smaller than the target collection, we call it a condensed representation. We obtained a significant improvement of the performances. The use of condensed representations is relatively novel in the field. Then new major condensed representations of simple frequent patterns are proposed, the algorithms to mine them and derive the target pattern collections. We show the practical advantages of the proposed condensed representations over the past methods, and provide an abstract view of the proposed representations in the unified structure for condensed representations.
Abstract FR:
L'extraction de motifs intéressants a connu récemment un développement impressionnant dû à une pression accrue des propriétaires de données sous-exploitées et à la réponse des chercheurs par de nombreux résultats théoriques et pratiques. A l'origine, les données analysées provenaient du domaine de la vente et les motifs intéressants se présentaient sous forme de règles d'association. Des solutions performantes à ce problème pratique ont été élaborées (ex. APRIORI). Puis, les propriétaires d'autres types de données se sont interrogés sur l'utilité de ces premières solutions pour analyser leurs données. Malheureusement, ces données étaient différentes. Souvent, dans ces cas-là, APRIORI était inefficace voire intractable. Nous avons étudié les problèmes liés à l'extraction de motifs intéressants dans des collections de données d'origine différentes, en particulier les problèmes liés au grand nombre de motifs valides dans les données non similaires aux données de ventes. Nos méthodes extraient une collection de motifs qui peut être différente de la collection cible de motifs, en estimant qu'elle sera plus efficace à calculer dans certains types de données. De plus, cette collection, différente de la collection cible de motifs, doit permettre une régénération efficace de la collection cible. Comme la représentation intermédiaire est souvent beaucoup plus petite que la collection cible, nous la désignons sous le terme représentation condensée. Nous avons obtenu des améliorations significatives des performances. L'utilisation de représentations condensées est relativement novatrice dans le domaine. La contribution principale de cette thèse est la proposition de nouvelles représentations condensées pour des motifs élémentaires, ainsi que les algorithmes pour extraire ces représentations condensées et régénérer, à partir d'elles, les collections de motifs cibles. Nous montrons les avantages de ces représentations condensées par rapport aux méthodes existantes.