Spelling suggestions: "subject:"digraphes orientée."" "subject:"digraphes orienté.""
1 |
Définition et évaluation d'approches pour la validation des graphiques acycliques dirigés à partir de donnéesGadio, Souleymane 15 March 2024 (has links)
L’évaluation de relations causales à l’aide de données observationnelles est une pratique courante en épidémiologie. En présence de telles données, l’exposition d’intérêt est non randomisée et l’estimation des effets peut être biaisée par l’existence de variables confondantes. Les graphes acycliques dirigés (DAG) permettent de représenter les relations causales présumées entre les variables jugées pertinentes, ainsi que d’identifier les variables réellement confondantes, mais tracer un DAG peut être un défi majeur. Dans ce mémoire, nous avons étudié, développé et comparé différentes méthodes de validation des DAG. Un DAG est dit compatible avec les données si les indépendances statistiques sous-tendues par le DAG sont présentes dans les données. Nous avons considéré quatre méthodes statistiques paramétriques et deux non-paramétriques afin de tester l’ensemble de ces indépendances. À partir de données synthétiques simulées, nous avons évalué la capacité de ces tests à distinguer les DAG valides de ceux non valides. Plusieurs simulations variant en fonction de la taille d’échantillon, du nombre et du type de variables, ainsi que de la forme de leurs relations ont été réalisées. Par ailleurs, nous avons illustré l’application de nos tests pour valider un DAG concernant l’impact des nouveaux retards vaccinaux aux visites de vaccination sur le statut vaccinal. La performance des tests varie d’un scénario à l’autre. La majorité des tests rejettent plus souvent la validité des DAG pourtant valides dans certains scénarios que l’erreur de type I prévue de 5% à l’exception du test d’équations structurelles WLSMV (mean and variance adjusted weighted least squares) qui donne des résultats assez satisfaisant, notamment en absence de relations quadratiques dans la structure des données. Ce dernier test a toutefois une puissance relativement faible à détecter les DAG non valides dans certains cas. Par ailleurs, nos résultats illustrent que certains DAG non valides sont impossibles à discerner d’un DAG valide à partir des données observées. Les tests que nous avons explorés peuvent aider à discerner certains problèmes dans les DAG. Malgré leurs limites, ces tests sont des outils avec un potentiel important pour aider les épidémiologistes à valider leurs hypothèses lorsqu’ils utilisent des DAG. / Assessing causal relationships using observational data is common practice in epidemiology. In the presence of such data, the exposure of interest is non-randomized and the estimation of the effects may be biased by the existence of confounding variables. Directed acyclic graphs (DAGs) allow depicting the presumed causal relationships between variables deemed relevant, as well as identify truly confounding variables, but building a DAG can be a major challenge. In this thesis, we have developed and compared different DAG validation methods. A DAG is said to be compatible with the data if the statistical independencies underlying the DAG are present in the data. We consider three parametric and two nonparametric statistical methods in order to test all of these independencies. Using simulated synthetic data, we evaluate the ability of these tests to distinguish valid DAGs from those that are not valid. Several simulations varying according to the sample size, the number and type of variables, as well as the form of their relationships were performed. In addition, we illustrate the application of our tests to validate a DAG concerning the impact of new vaccine delays on vaccination visits at vaccination status. Tests’ performance vary from scenario to scenario. The majority of tests reject more often the validity of DAG yet valid in some scenarios than the type I error of 5% expected with the exception of the structural equation WLSMV (mean and variance adjusted weighted least squares) which gives fairly satisfactory results, especially in the absence of quadratic relationships in the data structure. However, this last test has a relatively low power to detect invalid DAGs in certain cases. Our results also illustrate that some invalid DAGs are impossible to discern from a valid DAG based on the observed data. The tests we have explored can help detect certain problems in DAGs. Despite their limitations, these tests are therefore tools with significant potential to help epidemiologists to validate their hypotheses when using DAGs.
|
2 |
La moyenne bayésienne pour les modèles basés sur les graphes acycliques orientésBouzite, Fatima Ezzahraa 01 March 2024 (has links)
Les méthodes d'inférence causale sont utiles pour répondre à plusieurs questions de recherche dans différents domaines, notamment en épidémiologie. Les graphes acycliques orientés sont des outils importants pour l'inférence causale. Entre autres, ils peuvent être utilisés pour identifier les variables confondantes utilisées dans l'ajustement de modèles statistiques afin d'estimer sans biais l'effet d'un traitement. Ces graphes sont construits à partir des connaissances du domaine d'application. Pourtant, ces connaissances sont parfois insuffisantes pour supposer que le graphe construit est correct. Souvent, un chercheur peut proposer divers graphiques correspondants à une même problématique. Dans ce projet, on développe une alternative au modèle moyen bayésien traditionnel qui se base sur un ensemble de graphes proposés par un utilisateur. Pour sa mise en œuvre, on estime d'abord la vraisemblance des données sous les modèles impliqués par chacun des graphes afin de déterminer la probabilité a posteriori de chaque graphe. On identifie, pour chaque graphe, un ensemble de covariables d'ajustement suffisant pour éviter le biais de confusion et on estime l'effet causal à partir d'approches appropriées en ajustant pour ces covariables. Finalement, l'effet causal global est estimé comme une moyenne pondérée des estimations correspondantes à chacun des graphes. La performance de cette approche est étudiée à l'aide d'une étude de simulation où le mécanisme de génération des données est inspiré de l'étude Study of Osteoporotic Fractures (SOF). Différents scénarios sont présentés selon les liens considérés entre les variables. L'étude de simulation démontre une bonne performance générale de notre méthode par comparaison au modèle moyen bayésien traditionnel. L'application de cette approche est illustrée à l'aide de données de l'étude SOF dont l'objectif est l'estimation de l'effet de l'activité physique sur le risque de fractures de la hanche. / Causal inference methods are useful for answering several research questions in different fields, including epidemiology. Directed acyclic graphs are important tools for causal inference. Among other things, they can be used to identify confounding variables used in fitting statistical models to unbiasedly estimate the effect of a treatment. These graphs are built from the knowledge of the domain of application. However, this knowledge is sometimes insufficient to assume that the constructed graph is correct. Often, a researcher can propose various graphs corresponding to the same problem. In this project, we develop an alternative to the traditional Bayesian model averaging which is based on a set of graphs proposed by a user. For its implementation, we first estimate the likelihood of the data under the models implied by each graph to determine the posterior probability of each graph. A set of adjustment covariates sufficient to control for confounding bias is identified for each graph and the causal effect is estimated using appropriate approaches by adjusting for these covariates. Finally, the overall causal effect is estimated as a weighted average of the graph-specific estimates. The performance of this approach is studied using a simulation study in which the data generation mechanism is inspired by the Study of Osteoporotic Fractures (SOF). Different scenarios varying in their relationships between the variables are presented. The simulation study shows a good overall performance of our method compared to the traditional Bayesian model averaging. The application of this approach is illustrated using data from the SOF, whose objective is to estimate the effect of physical activity on the risk of hip fractures.
|
3 |
Subdivisions de digraphes / Subdivisions of digraphsOliveira, Ana Karolinna Maia de 05 November 2014 (has links)
Dans ce travail, nous considérons le problème suivant : étant donné un graphe orienté D, contient-il une subdivision d’un digraphe fixé F ? Nous pensons qu’il existe une dichotomie entre les instances polynomiales et NP-complètes. Nous donnons plusieurs exemples pour les deux cas. En particulier, sauf pour cinq instances, nous sommes capable de classer tous les digraphes d’ordre 4. Alors que toutes les preuves NP-complétude sont faites par réduction de une version du problème 2-linkage en digraphes, nous utilisons différents outils algorithmiques pour prouver la solvabilité en temps polynomial de certains cas, certains d’entre eux impliquant des algorithmes relativement complexes. Les techniques varient des simples algorithmes de force brute, aux algorithmes basés sur des calculs maximale de flot, et aux décompositions en anses des digraphes fortement connexes, entre autres. Pour terminer, nous traitons le cas particulier où F étant une union disjointe de cycles dirigés. En particulier, nous montrons que les cycles dirigés de longueur au moins 3 possède la Propriété d’Erdos-Pósa : pour tout n, il existe un entier tn tel que pour tout digraphe D, soit D a n cycles dirigés disjoints de longueur au moins 3, soit il y a un ensemble T d’au plus tn sommets qui intersecte tous les cycles dirigés de longueur au moins 3. De ce résultat, nous déduisons que si F est l’union disjointe de cycles dirigés de longueur au plus 3, alors on peut décider en temps polynomial si un digraphe contient une subdivision de F. / In this work, we consider the following problem: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We believe that there is a dichotomy between NP-complete and polynomial-time solvable instances of this problem. We present many examples of both cases. In particular, except for five instances, we are able to classify all the digraphs F of order 4.While all NP-hardness proofs are made by reduction from some version of the 2-linkage problem in digraphs, we use different algorithmic tools for proving polynomial-time solvability of certain instances, some of them involving relatively complicated algorithms. The techniques vary from easy brute force algorithms, algorithms based on maximum-flow calculations, handle decompositions of strongly connected digraphs, among others. Finally, we treat the very special case of F being the disjoint union of directed cycles. In particular, we show that the directed cycles of length at least 3 have the Erdos-Pósa Property: for every n, there exists an integer tn such that for every digraph D, either D contains n disjoint directed cycles of length at least 3, or there is a set T of tn vertices that meets every directed cycle of length at least 3. From this result, we deduce that if F is the disjoint union of directed cycles of length at most 3, then one can decide in polynomial time if a digraph contains a subdivision of F.
|
4 |
Description algèbrique des graphes orientés pondérés et applicationsLeroux, Philippe 02 June 2003 (has links) (PDF)
Un des objectifs majeurs de cette thèse est la construction d'un formalisme algébrique englobant la notion de graphe orienté pondéré et celle de cogèbre coassociative. On montre la nécessité de travailler avec des cogèbres équipées de deux coproduits ou co-opérations. Ce faisant on retrouve la notion de digèbre associative introduite dix ans plus tôt par Jean-Louis Loday, notion motivée par la K-théorie, proposant ainsi un point de vue complémentaire à son formalisme. Le développement du formalisme algébrique introduit dans cette thèse propose aussi une extension de la notion de graphe orienté ainsi que l'utilisation de cogèbres équipées de plusieurs coproduits. La construction de graphes orientés sur des objets algébriques tels que les produits. La construction de graphes orientés sur des objets algébriques tels que les algèbres, bigèbres ou algèbres de Hopf motive ainsi la construction naturelle d'autres types d'algèbres tels que les trigèbres associatives, trigèbres cubiques, algèbres dendriformes, algèbres diptères et algèbres pré-dendriformes introduites par Jean-Louis Loday et Maria Ronco et re-découvertes par l'auteur. La construction de pavages ou de recouvrements coassociatifs de graphes orientés par des cogèbres coassociatives ou cogèbres codiptères permet la construction d'objets algèbriques plus généraux qu'on appelle variétés coassociatives. D'autres objectifs développés dans cette thèse sont liés à l'utilisation de grammaires coassociatives ou au formalisme de Quillen appliqué aux dérivées de type Leibniz-Ito, outils apparaissant en calculs stochastiques classique et quantique et reliés de très près au formalisme proposé par l'auteur.
|
5 |
A contribution to the theory of graph homomorphisms and colorings / Une contribution à la théorie d' homomorphisme et de coloration des graphesSen, Sagnik 04 February 2014 (has links)
Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes. / An oriented graph is a directed graph with no cycle of length at most two. A homomorphism of an oriented graph to another oriented graph is an arc preserving vertex mapping. To push a vertex is to switch the direction of the arcs incident to it. An orientable graph is an equivalence class of oriented graph with respect to the push operation. An orientable graph [−→G] admits a homomorphism to an orientable graph [−→H] if an element of [−→G] admits a homomorphism to an element of [−→H]. A signified graph (G, Σ) is a graph whose edges are assigned either a positive sign or a negative sign, while Σ denotes the set of edges with negative signs assigned to them. A homomorphism of a signified graph to another signified graph is a vertex mapping such that the image of a positive edge is a positive edge and the image of a negative edge is a negative edge. A signed graph [G, Σ] admits a homomorphism to a signed graph [H, Λ] if an element of [G, Σ] admits a homomorphism to an element of [H, Λ]. The oriented chromatic number of an oriented graph −→G is the minimum order of an oriented graph −→H such that −→G admits a homomorphism to −→H. A set R of vertices of an oriented graph −→G is an oriented relative clique if no two vertices of R can have the same image under any homomorphism. The oriented relative clique number of an oriented graph −→G is the maximum order of an oriented relative clique of −→G. An oriented clique or an oclique is an oriented graph whose oriented chromatic number is equal to its order. The oriented absolute clique number of an oriented graph −→G is the maximum order of an oclique contained in −→G as a subgraph. The chromatic number, the relative chromatic number and the absolute chromatic number for orientable graphs, signified graphs and signed graphs are defined similarly. In this thesis we study the chromatic number, the relative clique number and the absolute clique number of the above mentioned four types of graphs. We specifically study these three parameters for the family of outerplanar graphs, of outerplanar graphs with given girth, of planar graphs and of planar graphs with given girth. We also try to investigate the relation between the four types of graphs and prove some results regarding that. In this thesis, we provide tight bounds for the absolute clique number of these families in all these four settings. We provide improved bounds for relative clique numbers for the same. For some of the cases we manage to provide improved bounds for the chromatic number as well. One of the most difficult results that we prove here is that the oriented absolute clique number of the family of planar graphs is at most 15. This result settles a conjecture made by Klostermeyer and MacGillivray in 2003. Using the same technique we manage to prove similar results for orientable planar graphs and signified planar graphs. We also prove that the signed chromatic number of triangle-free planar graphs is at most 25 using the discharging method. This also implies that the signified chromatic number of trianglefree planar graphs is at most 50 improving the previous upper bound. We also study the 2-dipath and oriented L(p, q)-labeling (labeling with a condition for distance one and two) for several families of planar graphs. It was not known if the categorical product of orientable graphs and of signed graphs exists. We prove both the existence and also provide formulas to construct them. Finally, we propose some conjectures and mention some future directions of works to conclude the thesis.
|
6 |
Analyse des propriétés structurelles d'observabilité de l'état et de l'entrée inconnue des systèmes linéaires par approche graphiqueMartinez-Martinez, Sinuhé 27 May 2008 (has links) (PDF)
Le travail de thèse présenté dans ce document traite de l'analyse de différentes propriétés liées à l'observabilité des systèmes à entrée inconnue par approche graphique. La simplicité de mise en œuvre de l'approche graphique permet de se défaire des difficultés numériques inhérentes aux approches géométrique et algébrique. Ce constat a conduit ces dernières décennies, à une série d'études structurelles basées sur l'approche graphique. <br />Parmi les propriétés encore non abordées graphiquement, l'observabilité forte traduit l'observabilité des variables d'état d'un système pour toute valeur d'entrée ainsi que l'observabilité conjointe de l'état et de l'entrée. Ces propriétés plus fortes que l'observabilité simple et le diagnostic nous ont paru utiles et pertinentes à étudier. En effet, les outils d'analyse développés peuvent s'avérer importants dans le cadre de la synthèse d'observateurs ou d'estimateurs d'entrées utile à la synthèse de lois de commandes tolérantes aux défauts ou robustes aux perturbations, ou encore quand il s'agit de vérifier si la propriété d'observabilité d'un système n'est pas altérée lorsqu'il est soumis à des perturbations, voire à des défauts d'amplitude trop importante pour être négligés. <br />Le manuscrit est structuré en trois parties. Dans la première, nous avons abordé l'analyse de différentes propriétés d'observabilité. Plus précisément, nous avons tout d'abord donné des conditions nécessaires et suffisantes d'observabilité de l'entrée et de l'état d'un système. Des conditions nécessaires et suffisantes pour l'observabilité forte d'une partie donnée des composantes de l'entrée et de l'état ont ensuite été établies. Le dernier résultat de cette partie concerne l'observabilité forte de tout l'état d'un système à entrée inconnue. Des conditions nécessaires et suffisantes ont été démontrées. <br />La seconde partie de cette thèse a consisté à étudier le problème du placement des capteurs afin de recouvrer des propriétés d'observabilité forte lorsque les conditions de la première partie ne sont pas vérifiées. Deux cas ont été traités. Le premier concerne la propriété d'observabilité forte d'une partie donnée de l'état. La stratégie de placement de capteurs consiste alors en une condition nécessaire permettant d'imposer qu'au moins une sortie du système soit sensible à chacune des composantes de l'état devant être fortement observables, puis en un système de relations graphiques, utilisé comme condition suffisante à ce qu'une configuration de capteurs assure l'observabilité forte des composantes de l'état choisies. Le second problème de placement de capteurs a pour objectif de rendre observables toutes les composantes de l'état. Le problème a été traité en trois étapes. Pour chacune d'elles, des conditions nécessaires et suffisantes sur le placement de capteurs ont été trouvées. Le nombre minimal de capteurs nécessaire et suffisant a aussi été déterminé. Les conditions trouvées sont fondées essentiellement sur des algorithmes classiques de la théorie des graphes.<br />La troisième partie traite de l'implémentation des résultats établis dans une boîte à outils dédiée à l'analyse structurelle (lisa) des systèmes linéaires et bilinéaires structurés. En premier lieu, les motivations qui ont conduit à la conception de cette boîte à outils sont exposées. La structure de lisa est ensuite présentée. Elle repose entièrement sur des algorithmes de base tels que la détermination des ensembles de successeurs et de prédécesseurs, le calcul des tailles de lien et de couplages maximaux entre deux ensembles de sommets et la caractérisation des ensembles de sommets essentiels dans des liens de taille maximale ou encore des séparateurs d'entrée et de sortie. Tous ces algorithmes ont des ordres de complexité polynomiaux. Nous avons montré comment en associant certains algorithmes de base, nous sommes arrivés à analyser l'observabilité de l'état et de l'entrée et à établir des conditions de détection et de localisation de défauts. Enfin, il est présenté des fonctions pouvant être rajoutées à lisa concernant différentes propriétés structurelles pour en faire un outil d'analyse plus complet.
|
7 |
Des graphes orientés aux treillis complets : une nouvelle approche de l'ordre faible sur les goupes de Coxeter / From valued digraphs to complete lattices : a new approach of weak order on Coxeter groupsViard, François 26 November 2015 (has links)
L'ordre faible sur un groupe de Coxeter W est un ordre partiel sur les éléments de W, intervenant dans de nombreux domaines de la combinatoire algébrique. Dans cette thèse, on propose un nouveau modèle général pour l'étude de cet ordre ainsi que d'autres ensembles ordonnés affiliés, et on explore diverses conséquences aussi bien algébriques que combinatoires de cette construction. On commence, dans le chapitre 3, par étudier une version restreinte de ce modèle. Plus précisément, on explique comment on peut associer un ensemble ordonné (aussi appelé « poset » à tout graphe orienté, simple, acyclique et muni d'une valutation sur ses sommets (aussi appelé « graphe valué »). On montre ensuite que ces posets sont en général des semi-treillis inférieurs, des treillis quand le graphe est fini, et on donne une formule explicite pour les valeurs de leurs fonctions de Möbius. On prouve ensuite que l'ordre faible sur les groupes de Coxeter de type A, B et A, le « flag weak order », ainsi que le treillis des idéaux supérieurs et inférieurs de tout poset fini peuvent être décrit avec notre modèle. Cette description amène naturellement à associer une série quasi-symétrique à chaque élément de An et An et on montre que cette série est en fait la série de Stanley associée. On présente dans le chapitre 4 les résultats centraux de la thèse, en effet on y introduit la généralisation de la construction faite au chapitre précédent au cas de tout graphe valué, c'est-à-dire sans condition s'acyclicité et de simplicité. On s'affranchit également de certaines contraintes imposées par la définition du chapitre 3, ce qui nous permet d'associer à tout graphe valué un treillis complet, et non plus un semi-treillis. En particulier, les semi-treillis du chapitre 3 se retrouvent naturellement plongés dans un treillis complet. Ceci nous amène à nous intéresser à des conjectures de Dyer portant sur l'étude d'une extension de l'ordre faible sur tout groupe de Coxeter (entre autres, il est conjecturé que ces extensions sont des treillis complets). On construit alors, à l'aide de notre formalisme, des extensions de l'ordre faible ayant beaucoup des propriétés conjecturalement attachées aux extensions de Dyer, et contenant ces dernières comme sous-poset. On conjecture que l'une de ces extensions coïncide avec celle de Dyer, et on fournit des outils pour le tester. Finalement, on étudie diverses conséquences de notre théorie : la construction d'extensions des semi-treillis cambriens (fin du chapitre 4), la construction d'un nouveau modèle combinatoire pour le treillis de Tamari et m-Tamari (chapitre 5), et enfin on propose une application à la combinatoire des tableaux (chapitre 6) / Weak order on a Coxeter group W is a partial order on W appearing in many areas of algebraic combinatorics. In this thesis, we propose a new general model for the study of the weak order and other related partially ordered sets (also called “posets”) and we explore various algebraic and combinatorial consequences of this construction. We begin with studying a restricted version of this model in Chapter 3. More precisely, we explain how one can associate a poset to any simple acyclic digraph together with a valuation on its vertices (also called “valued digraph”). We then prove that these posets are complete meet semi-lattices in general, complete lattices when the underlying digraph is finite, and we give an explicit formula to compute the value of their Möbius functions. Then, we show that the weak order on Coxeter groups of type A, B and A, the flag weak order, and the up-set (resp. down-set) lattices of any finite poset can be described within this theory. This description naturally leads to associate a quasi-symmetric function to any element of An And An, and we demonstrate that this function is in fact the corresponding Stanley symmetric function. In Chapter 4 we introduce the main results of this thesis. Indeed, we introduce in this chapter the generalization of the construction made in Chapter 3 to the case of any valued digraph, that is without the simplicity and acyclicity condition. Furthermore, this new definition allows us to get rid of some constraints of the definition of Chapter 3, allowing us to associate a complete lattice to each valued digraph. In particular, the meet semi-lattices of Chapter 3 are naturally extended into complete lattices. This leads us to the study of some conjectures of Dyer about the properties of an extension of the weak order having a lot of the properties conjecturally attached to Dyer’s extensions, and we prove that each one of our extensions contains Dyer’s extension as a sub-poset. We make the conjecture that one of this extension coincide with the one of Dyer, and we provide tools in order to test this conjecture. Finally, we study various consequences of out theory : we provide extensions of Cambrian semi-lattices into complete lattices (end of Chapter 4), we construct a new combinatorial model for Tamari and m-Tamari lattices (Chapter 5), and we finish with an application to tableaux combinatorics (Chapter 6)
|
8 |
La visualisation d’information pour les données massives : une approche par l’abstraction de données / Information visualization for big data : a data abstraction approachSansen, Joris 04 July 2017 (has links)
L’évolution et la démocratisation des technologies ont engendré une véritable explosion de l’information et notre capacité à générer des données et le besoin de les analyser n’a jamais été aussi important. Pourtant, les problématiques soulevées par l’accumulation de données (stockage, temps de traitement, hétérogénéité, vitesse de captation/génération, etc. ) sont d’autant plus fortes que les données sont massives, complexes et variées. La représentation de l’information, de part sa capacité à synthétiser et à condenser des données, se constitue naturellement comme une approche pour les analyser mais ne résout pas pour autant ces problèmes. En effet, les techniques classiques de visualisation sont rarement adaptées pour gérer et traiter cette masse d’informations. De plus,les problèmes que soulèvent le stockage et le temps de traitement se répercutent sur le système d’analyse avec par exemple, la distanciation de plus en plus forte entre la donnée et l’utilisateur : le lieu où elle sera stockée et traitée et l’interface utilisateur servant à l’analyse. Dans cette thèse nous nous intéressons à ces problématiques et plus particulièrement à l’adaptation des techniques de visualisation d’informations pour les données massives. Pour cela, nous nous intéressons tout d’abord à l’information de relation entre éléments, comment est-elle véhiculée et comment améliorer cette transmission dans le contexte de données hiérarchisées. Ensuite, nous nous intéressons à des données multivariées,dont la complexité à un impact sur les calculs possibles. Enfin, nous présentons les approches mises en oeuvre pour rendre nos méthodes compatibles avec les données massives. / The evolution and spread of technologies have led to a real explosion of information and our capacity to generate data and our need to analyze them have never been this strong. Still, the problems raised by such accumulation (storage, computation delays, diversity, speed of gathering/generation, etc. ) is as strong as the data are big, complex and varied. Information visualization,by its ability to summarize and abridge data was naturally established as appropriate approach. However, it does not solve the problem raised by Big Data. Actually, classical visualization techniques are rarely designed to handle such mass of information. Moreover, the problems raised by data storage and computation time have repercussions on the analysis system. For example,the increasing distance between the data and the analyst : the place where the data is stored and the place where the user will perform the analyses arerarely close. In this thesis, we focused on these issues and more particularly on adapting the information visualization techniques for Big Data. First of all focus on relational data : how does the existence of a relation between entity istransmitted and how to improve this transmission for hierarchical data. Then,we focus on multi-variate data and how to handle their complexity for the required computations. Finally, we present the methods we designed to make our techniques compatible with Big Data.
|
9 |
Inférence de réseaux de régulation orientés pour les facteurs de transcription d'Arabidopsis thaliana et création de groupes de co-régulation / Inference of directed regulatory networks on the transcription factors of Arabidopsis thaliana and setting up of co-regulation groupsVasseur, Yann 08 December 2017 (has links)
Dans cette thèse, nous cherchons à caractériser les facteurs de transcription de la plante Arabidopsis thaliana, gènes importants pour la régulation de l'expression du génome. À l'aide de données d'expression, notre objectif biologique est de classer ces facteurs de transcription en groupes de gènes co-régulateurs et en groupes de gènes co-régulés. Nous procédons en deux phases pour y parvenir. La première phase consiste à construire un réseau de régulation entre les facteurs de transcription. La seconde phase consiste en la classification des facteurs de transcription selon les liens de régulation établis par ce réseau. D'un point de vue statistique, les facteurs de transcription sont les variables et les données d'expression sont les observations. Nous représentons le réseau à inférer par un graphe orienté dont les nœuds sont les variables. L'estimation de ses arêtes est vue comme un problème de sélection de variables en grande dimension avec un faible nombre d'unités statistiques. Nous traitons ce problème à l'aide de régressions linéaires pénalisées de type LASSO. Une approche préliminaire qui consiste à sélectionner un ensemble de variables du chemin de régularisation par le biais de critères de vraisemblance pénalisée s'avère être instable et fournit trop de variables explicatives. Pour contrecarrer cela, nous proposons et mettons en compétition deux procédures de sélection, adaptées au problème de la haute dimension et mêlant régression linéaire pénalisée et rééchantillonnage. L'estimation des différents paramètres de ces procédures a été effectuée dans le but d'obtenir des ensembles de variables stables. Nous évaluons la stabilité des résultats à l'aide de jeux de données simulés selon notre modèle graphique. Nous faisons appel ensuite à une méthode de classification non supervisée sur chacun des graphes orientés obtenus pour former des groupes de nœuds vus comme contrôleurs et des groupes de nœuds vus comme contrôlés. Pour évaluer la proximité entre les classifications doubles des nœuds obtenus sur différents graphes, nous avons développé un indice de comparaison de couples de partition dont nous éprouvons et promouvons la pertinence. D'un point de vue pratique, nous proposons une méthode de simulation en cascade, exigée par la complexité de notre modèle et inspirée du bootstrap paramétrique, pour simuler des jeux de données en accord avec notre modèle. Nous avons validé notre modèle en évaluant la proximité des classifications obtenues par application de la procédure statistique sur les données réelles et sur ces données simulées. / This thesis deals with the characterisation of key genes in gene expression regulation, called transcription factors, in the plant Arabidopsis thaliana. Using expression data, our biological goal is to cluster transcription factors in groups of co-regulator transcription factors, and in groups of co-regulated transcription factors. To do so, we propose a two-step procedure. First, we infer the network of regulation between transcription factors. Second, we cluster transcription factors based on their connexion patterns to other transcriptions factors.From a statistical point of view, the transcription factors are the variables and the samples are the observations. The regulatory network between the transcription factors is modelled using a directed graph, where variables are nodes. The estimation of the nodes can be interpreted as a problem of variables selection. To infer the network, we perform LASSO type penalised linear regression. A preliminary approach selects a set of variable along the regularisation path using penalised likelihood criterion. However, this approach is unstable and leads to select too many variables. To overcome this difficulty, we propose to put in competition two selection procedures, designed to deal with high dimension data and mixing linear penalised regression and subsampling. Parameters estimation of the two procedures are designed to lead to select stable set of variables. Stability of results is evaluated on simulated data under a graphical model. Subsequently, we use an unsupervised clustering method on each inferred oriented graph to detect groups of co-regulators and groups of co-regulated. To evaluate the proximity between the two classifications, we have developed an index of comparaison of pairs of partitions whose relevance is tested and promoted. From a practical point of view, we propose a cascade simulation method required to respect the model complexity and inspired from parametric bootstrap, to simulate data under our model. We have validated our model by inspecting the proximity between the two classifications on simulated and real data.
|
Page generated in 0.082 seconds