La syncope, dont l'origine peut ne pas être clairement définie, est considérée comme une pathologie fréquente. Dans ce cas et lorsque les épisodes sont répétés, le patient peut être amené à réaliser le test de la table d'inclinaison. Cet examen appelé tilt-test, est une méthode reconnue pour recréer les conditions dans lesquelles le patient ressent les symptômes de la syncope. Cependant, le principal problème de ce test est sa durée, qui peut atteindre une heure. Dès lors, pour des raisons de coût et de bien-être des patients, il paraît important de pouvoir réduire sa durée. C'est dans cet objectif que s'inscrivent les travaux réalisés dans le cadre de cette thèse, qui tentent de prédire l'apparition des symptômes liés à la syncope, et ce, le plus tôt possible. Durant nos recherches, deux axes sont ressortis naturellement : la fouille de données et le dé- veloppement de modèles capables de prédire le résultat du tilt-test. Ces deux axes partagent des méthodes issues de l'apprentissage articiel, qui permettent d'acquérir et d'extraire des connaissances à partir d'un ensemble d'observations signicatif. La littérature propose tout un ensemble de méthodes, qui nous ont permis de mettre en évidence certaines caractéristiques pertinentes, de manière à construire des modèles parcimonieux et robustes. Ces derniers ont permis d'obtenir des résultats intéressants pour la prédiction du résultat du tilt-test au terme notamment, des dix premières minutes de l'examen. Ces performances ont pu être considérablement améliorées par le développement de nouvelles techniques de fouille de données, permettant d'extraire très e- cacement de la connaissance. Les méthodes mises en place s'articulent autour de la sélection de variables et de l'interprétation de projections non linéaires. Ces méthodes, bien que développées autour de notre thématique, se sont montrées reproductibles lors de tests sur d'autres ensembles de données.

Une carte combinatoire est un modèle topologique qui permet de représenter les subdivisions de l'espace en cellules et les relations d'adjacences et d'incidences entre ces cellules en n dimensions. Cette structure de données est de plus en plus utilisée en traitement d'images, mais elle manque encore d'outils pour les analyser. Notre but est de définir de nouveaux outils pour les cartes combinatoires nD. Nous nous intéressons plus particulièrement à l'extraction de sous-cartes fréquentes dans une base de cartes. Nous proposons deux signatures qui sont également des formes canoniques de cartes combinatoires. Ces signatures ont chacune leurs avantages et leurs inconvénients. La première permet de décider de l'isomorphisme entre deux cartes en temps linéaire, en contrepartie le coût de stockage en mémoire est quadratique en la taille de la carte. La seconde signature a un coût de stockage en mémoire linéaire en la taille de la carte, cependant le temps de calcul de l'isomorphisme est quadratique. Elles sont utilisables à la fois pour des cartes connexes, non connexes, valuées ou non valuées. Ces signatures permettent de représenter une base de cartes combinatoires et de rechercher un élément de manière efficace. De plus, le temps de recherche ne dépend pas du nombre de cartes présent dans la base. Ensuite, nous formalisons le problème de recherche de sous-cartes fréquentes dans une base de cartes combinatoires nD. Nous implémentons deux algorithmes pour résoudre ce problème. Le premier algorithme extrait les sous-cartes fréquentes par une approche en largeur tandis que le second utilise une approche en profondeur. Nous comparons les performances de ces deux algorithmes sur des bases de cartes synthétiques. Enfin, nous proposons d'utiliser les motifs fréquents dans une application de classification d'images. Chaque image est décrite par une carte qui est transformée en un vecteur représentant le nombre d'occurrences des motifs fréquents. À partir de ces vecteurs, nous utilisons des techniques classiques de classification définies sur les espaces vectoriels. Nous proposons des expérimentations en classification supervisée et non supervisée sur deux bases d'images.

Dans la fouille de données multi-tables, les données sont représentées sous un format relationnel dans lequel les individus de la table cible sont potentiellement associés à plusieurs enregistrements dans des tables secondaires en relation un-à-plusieurs. Afin de prendre en compte les variables explicatives secondaires (appartenant aux tables secondaires), la plupart des approches existantes opèrent par mise à plat, obtenant ainsi une représentation attribut-valeur classique. Par conséquent, on perd la représentation initiale naturellement compacte mais également on risque d'introduire des biais statistiques. Dans cette thèse, nous nous intéressons à évaluer directement les variables secondaires vis-à-vis de la variable cible, dans un contexte de classification supervisée. Notre méthode consiste à proposer une famille de modèles non paramétriques pour l'estimation de la densité de probabilité conditionnelle des variables secondaires. Cette estimation permet de prendre en compte les variables secondaires dans un classifieur de type Bayésien Naïf. L'approche repose sur un prétraitement supervisé des variables secondaires, par discrétisation dans le cas numérique et par groupement de valeurs dans le cas catégoriel. Dans un premier temps, ce prétraitement est effectué de façon univariée, c'est-à-dire, en considérant une seule variable secondaire à la fois. Dans un second temps, nous proposons une approche de partitionnement multivarié basé sur des itemsets de variables secondaires, ce qui permet de prendre en compte les éventuelles corrélations qui peuvent exister entre variables secondaires. Des modèles en grilles de données sont utilisés pour obtenir des critères Bayésiens permettant d'évaluer les prétraitements considérés. Des algorithmes combinatoires sont proposés pour optimiser efficacement ces critères et obtenir les meilleurs modèles.Nous avons évalué notre approche sur des bases de données multi-tables synthétiques et réelles. Les résultats montrent que les critères d'évaluation ainsi que les algorithmes d'optimisation permettent de découvrir des variables secondaires pertinentes. De plus, le classifieur Bayésien Naïf exploitant les prétraitements effectués permet d'obtenir des taux de prédiction importants.

La génomique comparée est essentiellement une forme de fouille de données dans des grandes collections de relations n-aires. La croissance du nombre de génomes sequencés créé un stress sur la génomique comparée qui croit, au pire géométriquement, avec la croissance en données de séquence. Aujourd'hui même des laboratoires de taille modeste obtient, de façon routine, plusieurs génomes à la fois - et comme des grands consortia attend de pouvoir réaliser des analyses tout-contre-tout dans le cadre de ses stratégies multi-génomes. Afin d'adresser les besoins à tous niveaux il est nécessaire de repenser les cadres algorithmiques et les technologies de stockage de données utilisés pour la génomique comparée. Pour répondre à ces défis de mise à l'échelle, dans cette thèse nous développons des méthodes originales basées sur les technologies NoSQL et MapReduce. À partir d'une caractérisation des sorts de données utilisés en génomique comparée et d'une étude des utilisations typiques, nous définissons un formalisme pour le Big Data en génomique, l'implémentons dans la plateforme NoSQL Cassandra, et évaluons sa performance. Ensuite, à partir de deux analyses globales très différentes en génomique comparée, nous définissons deux stratégies pour adapter ces applications au paradigme MapReduce et dérivons de nouveaux algorithmes. Pour le premier, l'identification d'événements de fusion et de fission de gènes au sein d'une phylogénie, nous reformulons le problème sous forme d'un parcours en parallèle borné qui évite la latence d'algorithmes de graphe. Pour le second, le clustering consensus utilisé pour identifier des familles de protéines, nous définissons une procédure d'échantillonnage itérative qui converge rapidement vers le résultat global voulu. Pour chacun de ces deux algorithmes, nous l'implémentons dans la plateforme MapReduce Hadoop, et évaluons leurs performances. Cette performance est compétitive et passe à l'échelle beaucoup mieux que les algorithmes existants, mais exige un effort particulier (et futur) pour inventer les algorithmes spécifiques.

La découverte et l'interprétation de motifs et de règles sont deux tâches centrales en extraction de connaissances dans les bases de données. Cette thèse traite de l'extraction et des usages de motifs minimaux à la fois en fouille de données et dans le domaine des hypergraphes. D'une part, nous proposons une méthode efficace pour la découverte de motifs delta-libres dans les données larges, malgré les difficultés algorithmiques inhérentes à ce type de données. Cette méthode repose sur l'utilisation de l'extension des motifs et d'un nouveau critère d'élagage. D'autre part, nous nous intéressons à la qualité des règles d'associations et nous présentons un cadre générique qui permet de mieux comprendre les similarités et différences entre mesures. Il montre que de nombreuses mesures (appelées SBMs pour Simultaneously Bounded Measures) ont des comportements proches. Ce résultat permet de garantir des valeurs minimales pour toutes les SBMs et la production de règles de qualité par rapport à l'ensemble de ces mesures. Enfin, l'apport des méthodes de type <> pour d'autres domaines est mis en évidence. Nous montrons que notre approche de découverte de motifs dans les données larges est exploitable pour calculer efficacement les traverses minimales d'un hypergraphe, un problème réputé comme particulièrement difficile. Différentes applications, notamment en biologie, montrent l'intérêt pratique de nos méthodes.

L'étude et l'analyse des réseaux sociaux attirent l'attention d'une variété de sciences (psychologie, statistiques, sociologie). Parmi elles, le domaine de la fouille de données offre des outils pour extraire automatiquement des informations utiles sur les propriétés de ces réseaux. Plus précisément, la fouille de graphes répond au besoin de modéliser et d'étudier les réseaux sociaux en particulier dans le cas des grandes communautés que l'on trouve habituellement dans les médias en ligne oú la taille des réseaux sociaux est trop grande pour les méthodes manuelles. La modélisation générale d'un réseau social est basée sur des structures de graphes. Les sommets du graphe représentent les individus et les arêtes des actions différentes ou des types de liens sociaux entre les individus. Une communauté est définie comme un sous-graphe (d'un réseau social) et se caractérise par des liens denses. Plusieurs mesures ont été précédemment proposées pour l'évaluation des divers aspects de la qualité de ces communautés mais la plupart d'entre elles ignorent diverses propriétés des interactions entre individus (par exemple l'orientation de ces liens). Dans la recherche présentée ici, le concept de "k-core" est utilisé comme un moyen d'évaluer les communautés et d'en extraire des informations. La structure de "k-core" mesure la robustesse d'un réseau non orienté en utilisant la dégénérescence du graphe. En outre, des extensions du principe de dégénérescence sont introduites pour des réseaux dont les arêtes possèdent plus d'informations que celles non orientées. Le point de départ est l'exploration des attributs qui peuvent être extraits des graphes non orientés (réseaux sociaux). Sur ce point, la dégénérescence est utilisée pour évaluer les caractéristiques d'une collaboration entre individus et sur l'ensemble de la communauté - une propriété non capturée par les métriques sur les sommets individuels ou par les métriques d'évaluation communautaires traditionnelles. Ensuite, cette méthode est étendue aux graphes pondérés, orientés et signés afin d'offrir de nouvelles mesures d'évaluation pour les réseaux sociaux. Ces nouvelles fonctionnalités apportent des outils de mesure de la collaboration dans les réseaux sociaux oú l'on peut attribuer un poids ou un orientation à une interaction et fournir des moyens alternatifs pour capturer l'importance des individus au sein d'une communauté. Pour les graphes signés, l'extension de la dégénérescence permet de proposer des métriques supplémentaires qui peuvent être utilisées pour modéliser la confiance. De plus, nous introduisons une approche de partitionnement basée sur le traitement du graphe de manière hiérarchique, hiérarchie fournie par le principe de "core expansion sequence" qui partitionne le graphe en différents niveaux ordonnés conformément à la décomposition "k-core". Les modèles théoriques de graphes sont ensuite appliqués sur des graphes du monde réel pour examiner les tendances et les comportements. Les jeux de données explorés incluent des graphes de collaborations scientifiques et des graphes de citations (DBLP et ARXIV), une instance de graphe interne de Wikipédia et des réseaux basés sur la confiance entre les individus (par exemple Epinions et Slashdot). Les conclusions sur ces ensembles de données sont significatives et les modèles proposés offrent des résultats intuitifs.

Cette thèse est consacrée aux tests statistiques, visant à comparer un vecteur de données numériques, indicées par l'ensemble des gènes du génome humain, à un certain ensemble de gènes, connus pour être associés par exemple à un type donné de cancer. Parmi les méthodes existantes, le test Gene Set Enrichment Analysis est le plus utilisé. Néanmoins, il a deux inconvénients. D'une part, le calcul des p-valeurs est coûteux et peu précis. D'autre part, il déclare de nombreux résultats significatifs, dont une majorité n'ont pas de sens biologique. Ces deux problèmes sont traités, par l'introduction de deux procédures statistiques nouvelles, les tests de Kolmogorov-Smirnov pondéré et doublement pondéré. Ces deux tests ont été appliqués à des données simulées et réelles, et leurs résultats comparés aux procédures existantes. Notre conclusion est que, au-delà leurs avantages mathématiques et algorithmiques, les tests proposés pourraient se révéler, dans de nombreux cas, plus informatifs que le test GSEA classique, et traiter efficacement les deux problèmes qui ont motivé leur construction. / Our focus is on statistical testing methods, that compare a given vector of numeric values, indexed by all genes in the human genome, to a given set of genes, known to be associated to a particular type of cancer for instance. Among existing methods, Gene Set Enrichment Analysis is the most widely used. However it has several drawbacks. Firstly, the calculation of p-values is very much time consuming, and insufficiently precise. Secondly, like most other methods, it outputs a large number of significant results, the majority of which are not biologically meaningful. The two issues are addressed here, by two new statistical procedures, the Weighted and Doubly Weighted Kolmogorov-Smirnov tests. The two tests have been applied both to simulated and real data, and compared with other existing procedures. Our conclusion is that, beyond their mathematical and algorithmic advantages, the WKS and DWKS tests could be more informative in many cases, than the classical GSEA test and efficiently address the issues that have led to their construction.

Les mots constituent l'un des fondements des langues naturelles de type indo-européenne. Des corpus rédigés avec ces langues sont alors naturellement décrits avec des mots. Cependant, l'information qu'ils véhiculent seuls est assez réduite d'un point de vue sémantique. Il est en effet primordial de prendre en compte la complexité de ces langues comme par exemple leurs propriétés syntaxiques, lexicales et sémantiques. Nous proposons dans cette thèse de prendre en considération ces propriétés en décrivant un corpus par le biais d'informations syntaxiques permettant de découvrir des connaissances sémantiques. Nous présentons dans un premier temps un modèle de sélection de descripteurs SelDe. Ce dernier se fonde sur les objets issus des relations syntaxiques d'un corpus. Le modèle SelDe a été évalué pour des tâches de classification de données textuelles. Pour cela, nous présentons une approche d'expansion de corpus, nommée ExpLSA, dont l'objectif est de combiner les informations syntaxiques fournies par SelDe et la méthode numérique LSA. Le modèle SelDe, bien que fournissant des descripteurs de bonne qualité, ne peut être appliqué avec tous types de données textuelles. Ainsi, nous décrivons dans cette thèse un ensemble d'approches adaptées aux données textuelles dites complexes. Nous étudions la qualité de ces méthodes avec des données syntaxiquement mal formulées et orthographiées, des données bruitées ou incomplètes et finalement des données dépourvues de syntaxe. Finalement un autre modèle de sélection de descripteurs, nommé SelDeF, est proposé. Ce dernier permet de valider de manière automatique des relations syntaxiques dites “induites”. Notre approche consiste à combiner deux méthodes. Une première approche fondée sur des vecteurs sémantiques utilise les ressources d'un thésaurus. Une seconde s'appuie sur les connaissances du Web et des mesures statistiques afin de valider les relations syntaxiques. Nous avons expérimenté SelDeF pour une tâche de construction et d'enrichissement de classes conceptuelles. Les résultats expérimentaux montrent la qualité des approches de validation et reflètent ainsi la qualité des classes conceptuelles construites.

Les travaux présentés dans ce mémoire, ont été développés sur le thème de la découverte de motifs intéressants à travers la fouille de données et mis en oeuvre dans le cadre de la conception de systèmes d'information. Ils sont essentiellement consacrés aux problèmes soulevés par l'étape de fouille pour la découverte de modèles et de motifs fréquents. Ils sont à la fois d'ordre méthodologique et applicatif.

La découverte de motifs est une tâche centrale pour<br />l'extraction de connaissances dans les bases de données. Cette thèse<br />traite de l'extraction de motifs locaux sous contraintes. Nous<br />apportons un éclairage nouveau avec un cadre combinant des primitives<br />monotones pour définir des contraintes quelconques. La variété de ces<br />contraintes exprime avec précision l'archétype des motifs recherchés<br />par l'utilisateur au sein d'une base de données. Nous proposons alors<br />deux types d'approche d'extraction automatique et générique malgré les<br />difficultés algorithmiques inhérentes à cette tâche. Leurs efficacités<br />reposent principalement sur l'usage de conditions nécessaires pour<br />approximer les variations de la contrainte. D'une part, des méthodes<br />de relaxations permettent de ré-utiliser les nombreux algorithmes<br />usuels du domaines. D'autre part, nous réalisons des méthodes<br />d'extraction directes dédiées aux motifs ensemblistes pour les données<br />larges ou corrélées en exploitant des classes d'équivalences. Enfin,<br />l'utilisation de nos méthodes ont permi la découverte de phénomènes<br />locaux lors d'applications industrielles et médicales.