Sequential Pattern Generalization for Mining Multi-source Data
Généralisation de motifs séquentiels pour la fouille de données multi-sources
Résumé
Huge amounts of digital data have been created across years due to the increasing digitization in our everyday life. As a consequence, fast data collection and storage tools have been developed and data can be collected in huge volumes for various research and business purposes. The collected data can come from multiple data sources and can be of heterogeneous kinds thus forming heterogeneous multi-source datasets, and they can be analyzed to extract valuable information. Data mining is an important task in discovering interesting information from datasets. Different approaches in this domain have been proposed, among which pattern mining is the most important one. Pattern mining, including sequential pattern mining, discovers statistically relevant patterns (or sequential patterns) among data. The challenges of this domain include discovering important patterns with a limited complexity and by avoiding redundancy among the resulting patterns. Multi-source data could represent descriptive and sequential data, making the mining process complex. There could be problems of data similarity on one source level which leads to a limited number of extracted patterns. The aim of the thesis is to mine multi-source data to obtain valuable information and compensate the loss of patterns due to the problem of similarity with a limited complexity and by avoiding pattern redundancy. Many approaches have been proposed to mine multi-source data. These approaches either integrate multi-source data and perform a single mining process which increases the complexity and generates a redundant set of sequential patterns, or they mine sources separately and integrate the results which could lead to a loss of patterns. We propose G_SPM, a general sequential pattern mining algorithm that takes advantage of multi-source data to mine general patterns which compensates the loss of patterns caused by the problem of data similarity. These rich patterns contain various kinds of information and have higher data coverage than traditional patterns. G_SPM adopts a selective mining strategy of data sources where a main source is first mined, and other sources are mined only when similarity among patterns is detected, which limits the complexity and avoids pattern redundancy. The experimental results confirm that G_SPM succeeds in mining general patterns with a limited complexity. In addition, it outperforms traditional approaches in terms of runtime and pattern redundancy.
La digitalisation de notre monde est souvent associée à une production de grandes quantités de données. Ainsi, des outils de collecte et de stockage de données ont dû être développés, à des fins d’exploitation en recherche ou dans l’industrie. Les données collectées peuvent provenir de plusieurs sources, formant ainsi de gros corpus de données hétérogènes. Ces corpus peuvent être analysés pour extraire de l’information. C’est l’objet de la fouille de données, qui fait l’objet d’un intérêt grandissant depuis de nombreuses années. Différentes approches de fouille de données ont été proposées, parmi lesquelles la très populaire fouille de motifs. La fouille de motifs, qui inclut la fouille de motifs séquentiels, vise à extraire des motifs ordonnés fréquents dans les données.Dans le cadre de sources de données multiples, les données peuvent représenter des points de vue différents sur le phénomène représenté. Par ailleurs, la présence de similarité entre certains éléments de données est une caractéristique classique, qui mène à la perte d’information lors du processus de fouille. L’objectif de cette thèse est de concevoir un algorithme de fouille des motifs dans des données multi-source dans le but d’extraire une information pertinente tout en compensant la perte de motifs due à la similarité entre éléments et en limitant la redondance entre motifs. Plusieurs approches ont été proposées dans la littérature. Certaines fusionnent l’ensemble des sources dans un seul ensemble de données et exploitent un algorithme classique de fouille de motifs, ce qui mène à un algorithme complexe qui extrait un grand nombre de motifs redondants. D’autres fouillent les sources séparément ce qui peut mener à une perte potentielle de motifs. Nous proposons G_SPM, un algorithme de fouille de motifs séquentiels qui tire avantage des multiples sources de données à disposition dans le but de pallier le problème de la similarité entre éléments, en formant des motifs généraux. G_SPM adopte une stratégie de fouille sélective de sources, ce qui lui permet d’avoir une complexité limitée. Par ailleurs, G_SPM fouille dans un premier temps une unique source de données, celle qui lui permet d’avoir des motifs séquentiels les plus précis possibles. Les expérimentations menées confirment que G_SPM identifie des motifs généraux avec un temps d’exécution limité, il permet donc de gérer la similarité entre les éléments en compensant l’éclatement des occurrences sur plusieurs motifs.
Fichier principal
DDOC_T_2020_0204_BU_DAHER.pdf (1.23 Mo)
Télécharger le fichier
DDOC_T_2020_0204_BU_DAHER_RESUME.pdf (56.93 Ko)
Télécharger le fichier
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|