L'information occupe désormais une place centrale dans notre vie quotidienne, elle est à la fois omniprésente et facile d'accès. Pourtant, l'extraction de l'information à partir des données est un processus souvent inaccessible. En effet, même si les méthodes de fouilles de données sont maintenant accessibles à tous, les résultats de ces fouilles sont souvent complexes à obtenir et à exploiter pour l'utilisateur. La fouille de motifs combinée à l'utilisation de contraintes est une direction très prometteuse de la littérature pour à la fois améliorer l'efficience de la fouille et rendre ses résultats plus appréhendables par l'utilisateur. Cependant, la combinaison de contraintes désirée par l'utilisateur est souvent problématique car, elle n'est pas toujours adaptable aux caractéristiques des données fouillées tel que le bruit. Dans cette thèse, nous proposons deux nouvelles contraintes et un algorithme pour pallier ce problème. La contrainte de robustesse permet de fouiller des données bruitées en conservant la valeur ajoutée de la contrainte de contiguïté. La contrainte de clôture allégée améliore l'appréhendabilité de la fouille de motifs tout en étant plus résistante au bruit que la contrainte de clôture classique. L'algorithme C3Ro est un algorithme générique de fouille de motifs séquentiels intégrant de nombreuses contraintes, notamment les deux nouvelles contraintes que nous avons introduites, afin de proposer à l'utilisateur la fouille la plus efficiente possible tout en réduisant au maximum la taille de l'ensemble des motifs extraits. C3Ro rivalise avec les meilleurs algorithmes de fouille de motifs de la littérature en termes de temps d'exécution tout en consommant significativement moins de mémoire. C3Ro a été expérimenté dans le cadre de l’extraction de compétences présentes dans les offres d'emploi sur le Web / Information now occupies a central place in our daily lives, it is both ubiquitous and easy to access. Yet extracting information from data is often an inaccessible process. Indeed, even though data mining methods are now accessible to all, the results of these mining are often complex to obtain and exploit for the user. Pattern mining combined with the use of constraints is a very promising direction of the literature to both improve the efficiency of the mining and make its results more apprehensible to the user. However, the combination of constraints desired by the user is often problematic because it does not always fit with the characteristics of the searched data such as noise. In this thesis, we propose two new constraints and an algorithm to overcome this issue. The robustness constraint allows to mine noisy data while preserving the added value of the contiguity constraint. The extended closedness constraint improves the apprehensibility of the set of extracted patterns while being more noise-resistant than the conventional closedness constraint. The C3Ro algorithm is a generic sequential pattern mining algorithm that integrates many constraints, including the two new constraints that we have introduced, to provide the user the most efficient mining possible while reducing the size of the set of extracted patterns. C3Ro competes with the best pattern mining algorithms in the literature in terms of execution time while consuming significantly less memory. C3Ro has been experienced in extracting competencies from web-based job postings

Dans cette thèse, nous proposons une nouvelle approche WCUM (Web Content and Usage Mining based approach) permettant de relier l'analyse du contenu à l'analyse de l'usage d'un site Web afin de mieux comprendre le comportement général des visiteurs du site. Ce travail repose sur l'utilisation de l'algorithme CROKI2 de classification croisée implémenté selon deux stratégies d'optimisation différentes que nous comparons à travers des expérimentations sur des données générées artificiellement. Afin de pallier le problème de détermination du nombre de classes sur les lignes et les colonnes, nous proposons de généraliser certains indices proposés initialement pour évaluer les partitions obtenues par des algorithmes de classification simple, aux algorithmes de classification simultanée. Pour évaluer la performance de ces indices nous proposons un algorithme de génération de biclasses artificielles pour effectuer des simulations et valider les résultats. Des expérimentations sur des données artificielles ainsi qu'une application sur des données réelles ont été réalisées pour évaluer l'efficacité de l'approche proposée. / In this thesis, we propose a new approach WCUM (Web Content and Usage Mining based approach) for linking content analysis to usage analysis of a website to better understand the general behavior of the web site visitors. This work is based on the use of the block clustering algorithm CROKI2 implemented by two different strategies of optimization that we compared through experiments on artificially generated data. To mitigate the problem of determination of the number of clusters on rows and columns, we suggest to generalize the use of some indices originally proposed to evaluate the partitions obtained by clustering algorithms to evaluate bipartitions obtained by simultaneous clustering algorithms. To evaluate the performance of these indices on data with biclusters structure, we proposed an algorithm for generating artificial data to perform simulations and validate the results. Experiments on artificial data as well as on real data were realized to estimate the efficiency of the proposed approach.

Cette thèse se situe à l'interface de la statistique et de la fouille de données. Elle est composée de trois parties indépendantes. Dans la première, nous cherchons à estimer l'ordre (le nombre d'États cachés) d'un modèle de Markov caché dont la distribution d'émission appartient à la famille exponentielle. Nous nous plaçons dans le cas où aucune borne supérieure sur cet ordre n'est connue a priori. Nous définissons deux estimateurs pénalisés pour cet ordre, l'un basé sur le maximum de vraisemblance et l'autre sur une statistique de mélange bayésien. Nous montrons la consistance forte de ces estimateurs. Dans la deuxième partie, nous extrayons des motifs séquentiels dont la fréquence est exceptionnellement élevée par rapport à un modèle de Markov. L'approche consiste à dénombrer dynamiquement toutes les positions possibles d'un motif au sein d'une séquence. Puis la fréquence observée est comparée à la fréquence attendue à l'aide d'un test binomial. Une procédure est utilisée pour tenir compte des tests multiples. Des expérimentations sont menées sur des bases synthétiques et des séquences de protéines. Enfin, dans la troisième partie, nous nous intéressons au calcul de l'estimateur à noyau de la densité. Les observations sont regroupées dans des structures hiérarchiques d'arbres binaires. Les calculs sont réalisés sur les nœuds, plutôt que sur les points, pour une plus grande efficacité. Nous effectuons le calcul sur un Échantillon de points de chaque nœud, au lieu de sa totalité, en utilisant des inégalités de concentration non-paramétriques pour contrôler l'erreur. Puis, nous proposons un nouveau parcours de l'arbre pour effectuer ces échantillonnages sur un nombre réduit de nœuds. Nous testons notre approche sur des jeux de données synthétiques. / This Ph.D thesis lies at the interface of statistics and data mining. It contains three independent parts. In the first one, we aim at estimating the order (the number of hidden states) of a Hidden Markov Model, whose emission distribution belongs to the exponential family. We suppose that no upper bound is known on this order. We define two penalised estimators for this order, one based on the maximum likelihood, an the other on a bayesian mixture statistic. We prove that both estimators are strongly consistent. In the second part, we extract sequential patterns of exceptional frequency given a Markov model. We first dynamically enumerate all the possible occurences of a pattern in a sequence. Then, the observed frequency is compared to the expected frequency using a binomial test. Multiple testing is taken into account. Experiments are led on synthetic databases and protein sequences. Finally, in the third chapter, we are interested in kernel density estimation. The observations are gathered in hierarchical structures called binary trees. Computations are done on nodes of trees, rather than on raw observations, for greater efficiency. We only take into account samples on each node, instead of all the observations, using a non-parametric concentration inequality to control the error. We also propose to only browse some parts of the tree. We test our approach on synthetic datasets.

La classification de documents textuels est une tâche relativement ancienne. Très tôt, de nombreux documents de différentes natures ont été regroupés dans le but de centraliser la connaissance. Des systèmes de classement et d'indexation ont alors été créés. Ils permettent de trouver facilement des documents en fonction des besoins des lecteurs. Avec la multiplication du nombre de documents et l'apparition de l'informatique puis d'internet, la mise en œuvre de systèmes de classement des textes devient un enjeu crucial. Or, les données textuelles, de nature complexe et riche, sont difficiles à traiter de manière automatique. Dans un tel contexte, cette thèse propose une méthodologie originale pour organiser l'information textuelle de façon à faciliter son accès. Nos approches de classification automatique de textes mais aussi d'extraction d'informations sémantiques permettent de retrouver rapidement et avec pertinence une information recherchée.De manière plus précise, ce manuscrit présente de nouvelles formes de représentation des textes facilitant leur traitement pour des tâches de classification automatique. Une méthode de généralisation partielle des données textuelles (approche GenDesc) s'appuyant sur des critères statistiques et morpho-syntaxiques est proposée. Par ailleurs, cette thèse s'intéresse à la construction de syntagmes et à l'utilisation d'informations sémantiques pour améliorer la représentation des documents. Nous démontrerons à travers de nombreuses expérimentations la pertinence et la généricité de nos propositions qui permettent une amélioration des résultats de classification. Enfin, dans le contexte des réseaux sociaux en fort développement, une méthode de génération automatique de HashTags porteurs de sémantique est proposée. Notre approche s'appuie sur des mesures statistiques, des ressources sémantiques et l'utilisation d'informations syntaxiques. Les HashTags proposés peuvent alors être exploités pour des tâches de recherche d'information à partir de gros volumes de données. / We have work for a long time on the classification of text. Early on, many documents of different types were grouped in order to centralize knowledge. Classification and indexing systems were then created. They make it easy to find documents based on readers' needs. With the increasing number of documents and the appearance of computers and the internet, the implementation of text classification systems becomes a critical issue. However, textual data, complex and rich nature, are difficult to treat automatically. In this context, this thesis proposes an original methodology to organize and facilitate the access to textual information. Our automatic classification approache and our semantic information extraction enable us to find quickly a relevant information.Specifically, this manuscript presents new forms of text representation facilitating their processing for automatic classification. A partial generalization of textual data (GenDesc approach) based on statistical and morphosyntactic criteria is proposed. Moreover, this thesis focuses on the phrases construction and on the use of semantic information to improve the representation of documents. We will demonstrate through numerous experiments the relevance and genericity of our proposals improved they improve classification results.Finally, as social networks are in strong development, a method of automatic generation of semantic Hashtags is proposed. Our approach is based on statistical measures, semantic resources and the use of syntactic information. The generated Hashtags can then be exploited for information retrieval tasks from large volumes of data.

Le regroupement d'objets, dans un cadre non-supervisé, est une tâche importante et difficile en apprentissage. Ce processus intervient dans des contextes variés tels que la découverte de connaissances, la simplification dans le représentation ou la description d'un ensemble de données.<br /><br />Nous proposons, dans cette étude, l'algorithme de clustering PoBOC permettant de structurer un ensemble d'objets en classes non-disjointes. Nous utilisons cette méthode de clustering comme outil de traitement dans deux applications très différentes.<br /><br />- En apprentissage supervisé, l'organisation préalable des instances apporte une connaissance utile pour la tâche d'induction de règles propositionnelles et logiques.<br /><br />- En Recherche d'Information, les ambiguïtés et subtilités de la langue naturelle induisent naturellement des recouvrements entre thématiques.<br /><br />Dans ces deux domaines de recherche, l'intérêt d'organiser les objets en classes non-disjointes est confirmé par les études expérimentales adaptées.

Les outils de simulation ont déjà été éprouvés pour l'étude de nombreux phénomènes, mais simuler le comportement humain reste un défi à la fois pour l'informatique et les sciences humaines. Dans ce contexte, nous avons travaillé sur la simulation des comportements individuels et des interactions sociales dans les groupes d'individus pour observer l'émergence de phénomènes sociaux. À cette fin, nous avons mener un travail inter-disciplinaire mêlant des techniques d'intelligence artificielle, de systèmes multi-agents, de sciences humaines et de fouille de données spatio-temporelles. Cette thèse présente un nouveau modèle d'agent émotionnel : l'agent EFT (Emotion, Feeling, Temperament). Basée sur une architecture BDI, notre modèle intègre le modèle émotionnel OCC et le modèle comportemental PerformanSe. Nous présentons également une implémentation concrète de notre modèle : la simulation de personnes cérébrolésés sur une chaîne de conditionnement. Nous décrivons la modélisation des interactions de notre système grâce à AgentUML. Via des méthodes de fouille de données spatio-temporel, nous extrayons les informations pertinentes à partir des données issues de la simulation.

Nous nous intéressons au problème de la prédiction de l’occurrence d’une baisse de prix pour fournir un conseil à l’achat immédiat ou reporté d’un voyage sur un site web de comparaison des prix. La méthodologie proposée repose sur l’apprentissage statistique d’un modèle d’évolution du prix à partir de l’information conjointe d’attributs du voyage considéré et d’observations passées du prix et de la "popularité" celui-ci. L’originalité principale consiste à représenter l’évolution des prix par le processus ponctuel inhomogène des sauts de celui-ci. A partir d’une base de données constituée par liligo.com, nous mettons en oeuvre une méthode d’apprentissage d’un modèle d’évolution des prix. Ce modèle permet de fournir un prédicteur de l’occurrence d’une baisse du prix sur une période future donnée et donc de prodiguer un conseil d’achat ou d’attente au client. / The goal of this paper is to consider the design of decision-making tools in the context of varying travel prices from the customer’s perspective. Based on vast streams of heterogeneous historical data collected through the internet, we describe here two approaches to forecasting travel price changes at a given horizon, taking as input variables a list of descriptive characteristics of the flight, together with possible features of the past evolution of the related price series. Though heterogeneous in many respects ( e.g. sampling, scale), the collection of historical prices series is here represented in a unified manner, by marked point processes (MPP). State-of-the-art supervised learning algorithms, possibly combined with a preliminary clustering stage, grouping flights whose related price series exhibit similar behavior, can be next used in order to help the customer to decide when to purchase her/his ticket.

Les ressources d'information multilingues sur le Web sont devenues de plus en plus des objets d'études importantes pour différents domaines intervenant au traitement de l'information. Néanmoins, nous constatons que la structure des ressources multilingues est très peu explorée par rapport à l'abondance des méthodes de traitement automatique des langues naturelles. Dans cette thèse, nous abordons l'aspect multilinguisme dans un contexte de catégorisation des sites Web multilingues. Nous apportons quelques connaissances expérimentales portant sur la représentation de documents multilingues, la modélisation des données en une structure homogène, la qualité de la recherche d'information dans un contexte multilingues et enfin sur les notions de frontière et de centre de gravité pour départager des langues dominantes sans puiser dans des connaissances linguistiques.

Le déboggage des applications de streaming qui s'exécutent sur les systèmes embarqués multimédia est l'un des domaines les plus exigeants dans le développement de logiciel embarqué. Les nouvelles générations de materiel embarqué introduisent de nouvelles systèmes sur une puce, qui fait que les développeurs du logiciel doivent adapter leurs logiciels aux nouvelles platformes. Le logiciel embarqué doit non seulement fournir des résultats corrects mais aussi le faire en temps réel afin de respecter les propriétés de qualité de service (Quality-of-Service, QoS) du système. Lorsque les propriétés QoS ne sont pas respectées, des bugs temporels font leur apparition. Ces bugs se manifestent comme, par exemple, des glitches dans le flux vidéo ou des craquements dans le flux audio. Le déboggage temporel est en général difficile à effectuer car les bugs temporels n'ont pas souvent de rapport avec l'exactitude fonctionnelle du code des applications, ce qui rend les outils de débogage traditionels, comme GDB, peu utiles. Le non-respect des propriétés QoS peut provenir des interactions entre les applications, ou entre les applications et les processus systèmes. Par conséquent, le contexte d'exécution entier doit être pris en compte pour le déboggage temporel. Les avancements récents en collecte des traces d'exécution permettent aux développeurs de recueillir des traces et de les analyser après la fin d'exécution pour comprendre quelle activité système est responsable des bugs temporels. Cependant, les traces d'exécution ont une taille conséquente, ce qui demande aux devéloppeurs des connaissainces en analyse de données qu'ils n’ont souvent pas.Dans cette thèse, nous proposons SATM - une approche novatrice pour le déboggage temporel des applications de streaming. SATM repose sur la prémisse que les applications sont conçues avec le modèle dataflow, i.e. peuvent être représentées comme un graphe orienté où les données sont transmises entre des unités de calcul (fontions, modules, etc.) appelées "acteurs". Les acteurs doivent être exécutés de manière périodique afin de respecter les propriétés QoS représentées par les contraintes de temps-réél. Nous montrons qu'un acteur qui ne respecte pas de façon répétée sa période pendant l'exécution de l'application cause la violation des contraintes temps-reel de l'application. En pratique, SATM est un workflow d'analyse de données venant des traces d'exécution qui combine des mesures statistiques avec des algorithmes de fouille de données. SATM fournit une méthode automatique du débogage temporel des applications de streaming. Notre approche prend en entrée une trace d'exécution d'une application ayant une QoS basse ainsi qu'une liste de ses acteurs, et tout d'abord détecte des invocations des acteurs dans la trace. SATM découvre ensuite les périodes des acteurs ainsi que les séctions de la trace où la période n'a pas été respectée. Enfin, ces séctions sont analysées afin d'extraire des motifs de l'activité système qui différencient ces sections des autres séctions de la trace. De tels motifs peuvent donner des indices sur l'origine du problème temporel dans le systeme et sont rendus au devéloppeur. Plus précisément, nous représentons ces motifs comme des séquences contrastes minimales et nous étudions des différentes solutions pour fouiller ce type de motifs à partir des traces d'exécution.Enfin, nous montrons la capacité de SATM de détecter une perturbation temporelle injectée artificiellement dans un framework multimedia GStreamer, ainsi que des bugs temporels dans deux cas d'utilisation des applications de streaming industrielles provenant de la société STMicroelectronics. Nous fournissons également une analyse détaillée des algorithmes de fouille de motifs séquentiels appliqués sur les données venant des traces d'exécution, et nous expliquons pour quelle est la raison les algorithmes de pointe n'arrivent pas à fouiller les motifs séquentiels à partir des traces d'exécution de façon efficace. / Debugging streaming applications run on multimedia embedded systems found in modern consumer electronics (e.g. in set-top boxes, smartphones, etc) is one of the most challenging areas of embedded software development. With each generation of hardware, more powerful and complex Systems-on-Chip (SoC) are released, and developers constantly strive to adapt their applications to these new platforms. Embedded software must not only return correct results but also deliver these results on time in order to respect the Quality-of-Service (QoS) properties of the entire system. The non-respect of QoS properties lead to the appearance of temporal bugs which manifest themselves in multimedia embedded systems as, for example, glitches in the video or cracks in the sound. Temporal debugging proves to be tricky as temporal bugs are not related to the functional correctness of the code, thus making traditional GDB-like debuggers essentially useless. Violations of QoS properties can stem from complex interactions between a particular application and the system or other applications; the complete execution context must be, therefore, taken into account in order to perform temporal debugging. Recent advances in tracing technology allow software developers to capture a trace of the system's execution and to analyze it afterwards to understand which particular system activity is responsible for the violations of QoS properties. However, such traces have a large volume, and understanding them requires data analysis skills that are currently out of the scope of the developers' education.In this thesis, we propose SATM (Streaming Application Trace Miner) - a novel temporal debugging approach for embedded streaming applications. SATM is based on the premise that such applications are designed under the dataflow model of computation, i.e. as a directed graph where data flows between computational units called actors. In such setting, actors must be scheduled in a periodic way in order to meet QoS properties expressed as real-time constraints, e.g. displaying 30 video frames per second. We show that an actor which does not eventually respect its period at runtime causes the violation of the application’s real-time constraints. In practice, SATM is a data analysis workflow combining statistical measures and data mining algorithms. It provides an automatic solution to the problem of temporal debugging of streaming applications. Given an execution trace of a streaming application exhibiting low QoS as well as a list of its actors, SATM firstly determines exact actors’ invocations found in the trace. It then discovers the actors’ periods, as well as parts of the trace in which the periods are not respected. Those parts are further analyzed to extract patterns of system activity that differentiate them from other parts of the trace. Such patterns can give strong hints on the origin of the problem and are returned to the developer. More specifically, we represent those patterns as minimal contrast sequences and investigate various solutions to mine such sequences from execution trace data.Finally, we demonstrate SATM’s ability to detect both an artificial perturbation injected in an open source multimedia framework, as well as temporal bugs from two industrial use cases coming from STMicroelectronics. We also provide an extensive analysis of sequential pattern mining algorithms applied on execution trace data and explain why state-of-the-art algorithms fail to efficiently mine sequential patterns from real-world traces.

Les technologies de l'information et le succès des services associés (forums, sites spécialisés, etc) ont ouvert la voie à un mode d'expression massive d'opinions sur les sujets les plus variés (e-commerce, critiques artistiques, etc). Cette profusion d'opinions constitue un véritable eldorado pour l'internaute, mais peut rapidement le conduire à une situation d'indécision car,les avis déposés peuvent être fortement disparates voire contradictoires. Pour une gestion fiable et pertinente de l'information contenue dans ces avis, il est nécessaire de mettre en place des systèmes capables de traiter directement les opinions exprimées en langage naturel afin d'en contrôler la subjectivité et de gommer les effets de lissage des traitements statistiques. La plupart des systèmes dits de recommandation ne prennent pas en compte toute la richesse sémantique des critiques et leur associent souvent des systèmes d'évaluation qui nécessitent une implication conséquente et des compétences particulières chez l'internaute. Notre objectif est de minimiser l'intervention humaine dans le fonctionnement collaboratif des systèmes de recommandation en automatisant l'exploitation des données brutes que constituent les avis en langage naturel. Notre approche non supervisée de segmentation thématique extrait les sujets d'intérêt des critiques, puis notre technique d'analyse de sentiments calcule l'opinion exprimée sur ces critères. Ces méthodes d'extraction de connaissances combinées à des outils d'analyse multicritère adaptés à la fusion d'avis d'experts ouvrent la voie à des systèmes de recommandation pertinents, fiables et personnalisés.