Dissertations / Theses: 'Analyse statistique de graphes'

1

Guillaume, Jean-Loup. "Analyse statistique et modélisation des grands réseaux d'interactions." Phd thesis, Université Paris-Diderot - Paris VII, 2004. http://tel.archives-ouvertes.fr/tel-00011377.

Full text

Abstract:

L'étude des grands réseaux d'interactions, ou réseaux rencontrés dans des contextes pratiques, vise à expliquer les interactions entre les différents individus d'un réseau par l'étude des grandes lois le gouvernant et à comprendre les divers phénomènes pouvant se produire sur ces réseaux. Cette thèse, divisée en trois parties, est consacrée à l'étude de ces réseaux.
La première partie est centrée sur l'analyse des réseaux et fait un point critique sur les réseaux étudiés et les paramètres introduits pour mieux comprendre leur structure. Un certain nombre de ces paramètres sont partagés par la majorité des réseaux étudiés et justifient l'étude de ceux-ci de manière globale.
La seconde partie qui constitue le coeur de cette thèse s'attache à la modélisation des grands réseaux d'interactions, c'est-à-dire la construction de graphes artificiels semblables à ceux rencontrés en pratique. Ceci passe tout d'abord par la présentation des modèles existants puis par l'introduction d'un modèle basé sur certaines propriétés non triviales qui est suffisamment simple pour que l'on puisse l'étudier formellement ses propriétés et malgré tout réaliste.
Enfin, la troisième partie est purement méthodologique. Elle permet de présenter la mise en pratique des parties précédentes et l'apport qui en découle en se basant sur trois cas particuliers : une étude des échanges dans un réseau pair-à-pair, une étude de la robustesse des réseaux aux pannes et aux attaques et enfin un ensemble de simulations visant à estimer la qualité des cartes de l'Internet actuellement utilisées.
Cette thèse met en lumière la nécessité de poursuivre les travaux sur les grands réseaux d'interactions et pointe plusieurs pistes prometteuses, notamment sur l'étude plus fine des réseaux, que ce soit de manière pondérée ou dynamique. Mais aussi sur la nécessité d'étudier de nombreux problèmes liés à la métrologie des réseaux pour réussir à capturer leur structure de manière plus précise.

APA, Harvard, Vancouver, ISO, and other styles

2

Zreik, Rawya. "Analyse statistique des réseaux et applications aux sciences humaines." Thesis, Paris 1, 2016. http://www.theses.fr/2016PA01E061/document.

Full text

Abstract:

Depuis les travaux précurseurs de Moreno (1934), l’analyse des réseaux est devenue une discipline forte, qui ne se limite plus à la sociologie et qui est à présent appliquée à des domaines très variés tels que la biologie, la géographie ou l’histoire. L’intérêt croissant pour l’analyse des réseaux s’explique d’une part par la forte présence de ce type de données dans le monde numérique d’aujourd’hui et, d’autre part, par les progrès récents dans la modélisation et le traitement de ces données. En effet, informaticiens et statisticiens ont porté leurs efforts depuis plus d’une dizaine d’années sur ces données de type réseau en proposant des nombreuses techniques permettant leur analyse. Parmi ces techniques on note les méthodes de clustering qui permettent en particulier de découvrir une structure en groupes cachés dans le réseau. De nombreux facteurs peuvent exercer une influence sur la structure d’un réseau ou rendre les analyses plus faciles à comprendre. Parmi ceux-ci, on trouve deux facteurs importants: le facteur du temps, et le contexte du réseau. Le premier implique l’évolution des connexions entre les nœuds au cours du temps. Le contexte du réseau peut alors être caractérisé par différents types d’informations, par exemple des messages texte (courrier électronique, tweets, Facebook, messages, etc.) échangés entre des nœuds, des informations catégoriques sur les nœuds (âge, sexe, passe-temps, Les fréquences d’interaction (par exemple, le nombre de courriels envoyés ou les commentaires affichés), et ainsi de suite. La prise en considération de ces facteurs nous permet de capturer de plus en plus d’informations complexes et cachées à partir des données. L’objectif de ma thèse été de définir des nouveaux modèles de graphes aléatoires qui prennent en compte les deux facteurs mentionnés ci-dessus, afin de développer l’analyse de la structure du réseau et permettre l’extraction de l’information cachée à partir des données. Ces modèles visent à regrouper les sommets d’un réseau en fonction de leurs profils de connexion et structures de réseau, qui sont statiques ou évoluant dynamiquement au cours du temps. Le point de départ de ces travaux est le modèle de bloc stochastique (SBM). Il s’agit d’un modèle de mélange pour les graphiques qui ont été initialement développés en sciences sociales. Il suppose que les sommets d’un réseau sont répartis sur différentes classes, de sorte que la probabilité d’une arête entre deux sommets ne dépend que des classes auxquelles ils appartiennent
Over the last two decades, network structure analysis has experienced rapid growth with its construction and its intervention in many fields, such as: communication networks, financial transaction networks, gene regulatory networks, disease transmission networks, mobile telephone networks. Social networks are now commonly used to represent the interactions between groups of people; for instance, ourselves, our professional colleagues, our friends and family, are often part of online networks, such as Facebook, Twitter, email. In a network, many factors can exert influence or make analyses easier to understand. Among these, we find two important ones: the time factor, and the network context. The former involves the evolution of connections between nodes over time. The network context can then be characterized by different types of information such as text messages (email, tweets, Facebook, posts, etc.) exchanged between nodes, categorical information on the nodes (age, gender, hobbies, status, etc.), interaction frequencies (e.g., number of emails sent or comments posted), and so on. Taking into consideration these factors can lead to the capture of increasingly complex and hidden information from the data. The aim of this thesis is to define new models for graphs which take into consideration the two factors mentioned above, in order to develop the analysis of network structure and allow extraction of the hidden information from the data. These models aim at clustering the vertices of a network depending on their connection profiles and network structures, which are either static or dynamically evolving. The starting point of this work is the stochastic block model, or SBM. This is a mixture model for graphs which was originally developed in social sciences. It assumes that the vertices of a network are spread over different classes, so that the probability of an edge between two vertices only depends on the classes they belong to

APA, Harvard, Vancouver, ISO, and other styles

3

Stoica, Alina-Mihaela. "Analyse de la structure locale des grands réseaux sociaux." Paris 7, 2010. http://www.theses.fr/2010PA077190.

Full text

Abstract:

Le principal but de notre recherche a été de caractériser les individus connectés dans un réseau social en analysant la structure locale du réseau. Pour cela, nous avons proposé une méthode qui décrit la façon dont un nœud (correspondant à un individu) est intégré dans le réseau. Notre méthode est liée à l'analyse de réseaux égocentrés en sociologie et à l'approche locale dans l'étude des grands graphes de terrain. Elle peut être appliquée à des petits réseaux, à des fractions de réseaux et aussi à des grands réseaux, grâce à sa petite complexité. Nous avons appliqué la méthode proposée à deux grands réseaux sociaux, un modélisant des activités en ligne sur MySpace, l'autre modélisant des communications par téléphone mobile. Dans le premier cas nous nous sommes intéressés à l'analyse de la popularité enligne des artistes sur MySpace. Dans le deuxième cas, nous avons proposé et avons utilisé une méthode pour regrouper les nœuds qui sont connectés au réseau de façon similaire. Nous avons constaté que la distribution des utilisateurs de téléphone mobile dans des groupes était corrélée à d'autres caractéristiques des individus (intensité de communication et âge). Bien que dans cette thèse nous ayons appliqué les deux méthodes seulement aux réseaux sociaux, elles peuvent être appliquées de la même manière à tout autre graphe, peu importe son origine
The main goal of our research was to characterize the individuals connected in a social network by analyzing the local structure of the network. For that, we proposed a method that describes the way a node (corresponding to an individual) is embedded in the network. Our method is related to the analysis of egocentred networks in sociology and to the local approach in the study of complex networks. It can be applied to small networks, to fractions of networks and also to large networks, due to its small complexity. We applied the proposed method to two large social networks, one modeling online activity on MySpace, the other one modeling mobile phone communications. In the first case we were interested in analyzing the online popularity of artists on MySpace. In the second case, we proposed and used a method for clustering nodes that are connected in a similar way to the network. We found that the distribution of mobile phone users into clusters was correlated to other characteristics of the individuals (i. E. Communication intensity and age). Although in this thesis we applied the two methods only to social networks, they can be applied in the same way to any other graph, no matter its origin

APA, Harvard, Vancouver, ISO, and other styles

4

Dumoncel, Franck. "Géographie et graphes : une interaction pour exprimer des requëtes spatiales guidée par des adjacences conceptuelles." Caen, 2006. http://www.theses.fr/2006CAEN2007.

Full text

Abstract:

L'accès à l'information géographique sous forme électronique s'ouvre de plus en plus au grand public. Des interfaces intuitives ne nécessitant pas ou peu d'apprentissage apparaissent alors dans le domaine. Néanmoins, lorsqu’il s’agit de spécifier plus finement l’information recherchée, le pouvoir expressif de ces interfaces est limité. Le projet Antéserveur Géographique propose un environnement complet pour permettre d’exprimer une requête de manière bi-modale (schéma + étiquette textuelle). Dans la première partie du manuscrit nous mettons en avant deux qualités de la modalité schématique : apprentissage réduit et pouvoir expressif riche. En contre partie, nous voyons les problèmes d’ambiguïtés dus aux différents sens qu’une telle modalité peut véhiculer. La seconde partie évoque le fonctionnement multimodal de notre interface et notamment la complémentarité du texte et du schéma pour lever les ambiguïtés grâce à une interaction contrôlée, celle-ci reposant sur un mécanisme appelé glissement de sens. Le mode textuel et les glissements de sens nécessitent une analyse spatiale adaptée du schéma. Nous abordons alors le domaine de l’analyse spatiale qualitative, au cœur de ce travail de recherche, dans lequel une utilisation récurrente par centre d’intérêt du modèle 9-intersections de M. J. EGENHOFFER est proposée. Grâce à cette méthode, nous disposons d’un modèle d’analyse spatiale unique permettant de relever différentes contraintes relevées jusqu’ici par des modèles distincts et sans lien. C’est cette unité qui nous permet de mettre en œuvre notre mécanisme de glissement de sens. Enfin, nous présentons brièvement notre réalisation informatique.

APA, Harvard, Vancouver, ISO, and other styles

5

Hollocou, Alexandre. "Nouvelles approches pour le partitionnement de grands graphes." Thesis, Paris Sciences et Lettres (ComUE), 2018. http://www.theses.fr/2018PSLEE063.

Full text

Abstract:

Les graphes sont omniprésents dans de nombreux domaines de recherche, allant de la biologie à la sociologie. Un graphe est une structure mathématique très simple constituée d’un ensemble d’éléments, appelés nœuds, reliés entre eux par des liens, appelés arêtes. Malgré cette simplicité, les graphes sont capables de représenter des systèmes extrêmement complexes, comme les interactions entre protéines ou les collaborations scientifiques. Le partitionnement ou clustering de graphe est un problème central en analyse de graphe dont l’objectif est d’identifier des groupes de nœuds densément interconnectés et peu connectés avec le reste du graphe. Ces groupes de nœuds, appelés clusters, sont fondamentaux pour une compréhension fine de la structure des graphes. Il n’existe pas de définition universelle de ce qu’est un bon cluster, et différentes approches peuvent s’avérer mieux adaptées dans différentes situations. Alors que les méthodes classiques s’attachent à trouver des partitions des nœuds de graphe, c’est-à-dire à colorer ces nœuds de manière à ce qu’un nœud donné n’ait qu’une et une seule couleur, des approches plus élaborées se révèlent nécessaires pour modéliser la structure complexe des graphes que l’on rencontre en situation réelle. En particulier, dans de nombreux cas, il est nécessaire de considérer qu’un nœud donné peut appartenir à plus d’un cluster. Par ailleurs, de nombreux systèmes que l’on rencontre en pratique présentent une structure multi-échelle pour laquelle il est nécessaire de partir à la recherche de hiérarchies de clusters plutôt que d’effectuer un partitionnement à plat. De plus, les graphes que l’on rencontre en pratique évoluent souvent avec le temps et sont trop massifs pour être traités en un seul lot. Pour ces raisons, il est souvent nécessaire d’adopter des approches dites de streaming qui traitent les arêtes au fil de l’eau. Enfin, dans de nombreuses applications, traiter des graphes entiers n’est pas nécessaire ou est trop coûteux, et il est plus approprié de retrouver des clusters locaux dans un voisinage de nœuds d’intérêt plutôt que de colorer tous les nœuds. Dans ce travail, nous étudions des approches alternatives de partitionnement de graphe et mettons au point de nouveaux algorithmes afin de résoudre les différents problèmes évoqués ci-dessus
Graphs are ubiquitous in many fields of research ranging from sociology to biology. A graph is a very simple mathematical structure that consists of a set of elements, called nodes, connected to each other by edges. It is yet able to represent complex systems such as protein-protein interaction or scientific collaborations. Graph clustering is a central problem in the analysis of graphs whose objective is to identify dense groups of nodes that are sparsely connected to the rest of the graph. These groups of nodes, called clusters, are fundamental to an in-depth understanding of graph structures. There is no universal definition of what a good cluster is, and different approaches might be best suited for different applications. Whereas most of classic methods focus on finding node partitions, i.e. on coloring graph nodes so that each node has one and only one color, more elaborate approaches are often necessary to model the complex structure of real-life graphs and to address sophisticated applications. In particular, in many cases, we must consider that a given node can belong to more than one cluster. Besides, many real-world systems exhibit multi-scale structures and one much seek for hierarchies of clusters rather than flat clusterings. Furthermore, graphs often evolve over time and are too massive to be handled in one batch so that one must be able to process stream of edges. Finally, in many applications, processing entire graphs is irrelevant or expensive, and it can be more appropriate to recover local clusters in the neighborhood of nodes of interest rather than color all graph nodes. In this work, we study alternative approaches and design novel algorithms to tackle these different problems. The novel methods that we propose to address these different problems are mostly inspired by variants of modularity, a classic measure that accesses the quality of a node partition, and by random walks, stochastic processes whose properties are closely related to the graph structure. We provide analyses that give theoretical guarantees for the different proposed techniques, and endeavour to evaluate these algorithms on real-world datasets and use cases

APA, Harvard, Vancouver, ISO, and other styles

6

Bonis, Thomas. "Algorithmes d'apprentissage statistique pour l'analyse géométrique et topologique de données." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLS459/document.

Full text

Abstract:

Dans cette thèse, on s'intéresse à des algorithmes d'analyse de données utilisant des marches aléatoires sur des graphes de voisinage, ou graphes géométriques aléatoires, construits à partir des données. On sait que les marches aléatoires sur ces graphes sont des approximations d'objets continus appelés processus de diffusion. Dans un premier temps, nous utilisons ce résultat pour proposer un nouvel algorithme de partitionnement de données flou de type recherche de modes. Dans cet algorithme, on définit les paquets en utilisant les propriétés d'un certain processus de diffusion que l'on approche par une marche aléatoire sur un graphe de voisinage. Après avoir prouvé la convergence de notre algorithme, nous étudions ses performances empiriques sur plusieurs jeux de données. Nous nous intéressons ensuite à la convergence des mesures stationnaires des marches aléatoires sur des graphes géométriques aléatoires vers la mesure stationnaire du processus de diffusion limite. En utilisant une approche basée sur la méthode de Stein, nous arrivons à quantifier cette convergence. Notre résultat s'applique en fait dans un cadre plus général que les marches aléatoires sur les graphes de voisinage et nous l'utilisons pour prouver d'autres résultats : par exemple, nous arrivons à obtenir des vitesses de convergence pour le théorème central limite. Dans la dernière partie de cette thèse, nous utilisons un concept de topologie algébrique appelé homologie persistante afin d'améliorer l'étape de "pooling" dans l'approche "sac-de-mots" pour la reconnaissance de formes 3D
In this thesis, we study data analysis algorithms using random walks on neighborhood graphs, or random geometric graphs. It is known random walks on such graphs approximate continuous objects called diffusion processes. In the first part of this thesis, we use this approximation result to propose a new soft clustering algorithm based on the mode seeking framework. For our algorithm, we want to define clusters using the properties of a diffusion process. Since we do not have access to this continuous process, our algorithm uses a random walk on a random geometric graph instead. After proving the consistency of our algorithm, we evaluate its efficiency on both real and synthetic data. We then deal tackle the issue of the convergence of invariant measures of random walks on random geometric graphs. As these random walks converge to a diffusion process, we can expect their invariant measures to converge to the invariant measure of this diffusion process. Using an approach based on Stein's method, we manage to obtain quantitfy this convergence. Moreover, the method we use is more general and can be used to obtain other results such as convergence rates for the Central Limit Theorem. In the last part of this thesis, we use the concept of persistent homology, a concept of algebraic topology, to improve the pooling step of the bag-of-words approach for 3D shapes

APA, Harvard, Vancouver, ISO, and other styles

7

Colin, Igor. "Adaptation des méthodes d’apprentissage aux U-statistiques." Thesis, Paris, ENST, 2016. http://www.theses.fr/2016ENST0070/document.

Full text

Abstract:

L’explosion récente des volumes de données disponibles a fait de la complexité algorithmique un élément central des méthodes d’apprentissage automatique. Les algorithmes d’optimisation stochastique ainsi que les méthodes distribuées et décentralisées ont été largement développés durant les dix dernières années. Ces méthodes ont permis de faciliter le passage à l’échelle pour optimiser des risques empiriques dont la formulation est séparable en les observations associées. Pourtant, dans de nombreux problèmes d’apprentissage statistique, l’estimation précise du risque s’effectue à l’aide de U-statistiques, des fonctions des données prenant la forme de moyennes sur des d-uplets. Nous nous intéressons tout d’abord au problème de l’échantillonnage pour la minimisation du risque empirique. Nous montrons que le risque peut être remplacé par un estimateur de Monte-Carlo, intitulé U-statistique incomplète, basé sur seulement O(n) termes et permettant de conserver un taux d’apprentissage du même ordre. Nous établissons des bornes sur l’erreur d’approximation du U-processus et les simulations numériques mettent en évidence l’avantage d’une telle technique d’échantillonnage. Nous portons par la suite notre attention sur l’estimation décentralisée, où les observations sont désormais distribuées sur un réseau connexe. Nous élaborons des algorithmes dits gossip, dans des cadres synchrones et asynchrones, qui diffusent les observations tout en maintenant des estimateurs locaux de la U-statistique à estimer. Nous démontrons la convergence de ces algorithmes avec des dépendances explicites en les données et la topologie du réseau. Enfin, nous traitons de l’optimisation décentralisée de fonctions dépendant de paires d’observations. De même que pour l’estimation, nos méthodes sont basées sur la concomitance de la propagation des observations et l’optimisation local du risque. Notre analyse théorique souligne que ces méthodes conservent une vitesse de convergence du même ordre que dans le cas centralisé. Les expériences numériques confirment l’intérêt pratique de notre approche
With the increasing availability of large amounts of data, computational complexity has become a keystone of many machine learning algorithms. Stochastic optimization algorithms and distributed/decentralized methods have been widely studied over the last decade and provide increased scalability for optimizing an empirical risk that is separable in the data sample. Yet, in a wide range of statistical learning problems, the risk is accurately estimated by U-statistics, i.e., functionals of the training data with low variance that take the form of averages over d-tuples. We first tackle the problem of sampling for the empirical risk minimization problem. We show that empirical risks can be replaced by drastically computationally simpler Monte-Carlo estimates based on O(n) terms only, usually referred to as incomplete U-statistics, without damaging the learning rate. We establish uniform deviation results and numerical examples show that such approach surpasses more naive subsampling techniques. We then focus on the decentralized estimation topic, where the data sample is distributed over a connected network. We introduce new synchronous and asynchronous randomized gossip algorithms which simultaneously propagate data across the network and maintain local estimates of the U-statistic of interest. We establish convergence rate bounds with explicit data and network dependent terms. Finally, we deal with the decentralized optimization of functions that depend on pairs of observations. Similarly to the estimation case, we introduce a method based on concurrent local updates and data propagation. Our theoretical analysis reveals that the proposed algorithms preserve the convergence rate of centralized dual averaging up to an additive bias term. Our simulations illustrate the practical interest of our approach

APA, Harvard, Vancouver, ISO, and other styles

8

Laporte, Quentin. "Étude morpho-statistique des réseaux sociaux. Application aux collaborations inter-organisationnelles." Electronic Thesis or Diss., Université de Lorraine, 2021. http://www.theses.fr/2021LORR0007.

Full text

Abstract:

Les applications collaboratives décentralisées permettent de répondre aux problèmes de confidentialité, de disponibilité et de sécurité inhérents aux plateformes collaboratives centralisées. Elles reposent sur un paradigme de communication pair-à-pair selon lequel tous les utilisateurs sont directement connectés les uns aux autres. Les collaborations ayant tendance à s'élargir et dépasser les frontières des organisations, il est nécessaire de garantir aux utilisateurs le contrôle sur leurs données tout en assurant la disponibilité de la collaboration. Pour ce faire, il est possible d'utiliser comme topologie le réseau social qui s'est tissé entre les collaborateurs. Le manque d'information sur ce maillage de confiance nous amène à développer une approche pour étudier ses propriétés morphologiques. Dans cette thèse, nous développons et mettons en œuvre une approche permettant d'étudier la structure sociale des interactions dans le cadre de collaborations inter-organisationnelles. Nous proposons une approche stochastique qui s'inspire des Exponential Random Graph Models (ERGM) et des modèles spatiaux. Nous définissons un formalisme qui met en avant la structure des interactions et intègre la dimension organisationnelle. Nous proposons d'utiliser une méthode d'inférence bayésienne, ABC Shdadow, pour contourner les difficultés liées à l'estimation de ce modèle. Cette approche est mise en œuvre sur un exemple réel : les collaborations initiées par les chercheurs d'un laboratoire. Elle permet notamment de montrer la faible propension, pour un chercheur, à tisser des liens avec d'autres laboratoires. Nous montrons que cette approche peut être appliquée à d'autres types d'interactions sociales, comme les interactions entre les enfants d'une école primaire. Enfin, nous présentons une stratégie de parallélisation de l'échantillonneur de Gibbs visant à traiter des graphes de plus grande taille dans un temps raisonnable
Decentralised collaborative applications address privacy, availability and security issues related to centralised collaborative platforms. Such applications are based on a peer-to-peer communication paradigm according to which all users are directly connected to one another. Collaborations tend to widen and spread beyond the borders of organisations. Under these circumstances, it is necessary to guarantee to users the control over their data, while keeping collaboration available. To that end, the social network that has built between collaborators may be used as topology. Lack of information on this trusted network leads us to develop an approach to study its morphological properties. In this thesis, we develop and implement an approach to study the social structure of interactions in the context of inter-organisational collaborations. We propose a stochastic approach based on Exponential Random Graph Models (ERGM) and spatial models. We define a formalism that highlights the structure of interactions and integrates the organisational dimension. We propose to use a Bayesian inference method, ABC Shadow, to overcome the issues related to the parameters estimation. This approach is applied to a real case study: the collaborations initiated by researchers in a laboratory. In particular, it highlights the low tendency for a researcher to create collaborative links with other laboratories. We show that this approach can be applied to other kinds of social interactions, such as interactions between pupils of a primary school. Finally, we present a parallelisation strategy of the Gibbs sampler aimed at processing larger graphs in a reasonable time

APA, Harvard, Vancouver, ISO, and other styles

9

Bera, Roderic. "L'Adjacence relative. Une Etude contextuelle de l'influence de l'environnement spatial dans l'appréhension de la notion de proximité." Rennes 1, 2004. https://hal.archives-ouvertes.fr/tel-01276691.

Full text

Abstract:

En information géographique, la notion de relation spatiale est primordiale, puisqu'elle conditionne la compréhension des interactions entre entités spatiales. Il est courant de décrire une scène par l'utilisation de grandeurs géomètriques (relation de distance, relations cardinales). Ceci permet de quantifier la relation d'une entité à une autre. Cependant, une telle approche ne prend pas en compte l'environnement spatial, dans la mesure où des entités tierces ne peuvent exercer une influence médiatrice. De plus, si la géométrie mesure, elle ne dit rien sur la nature d'une relation. L'approche topologique en revanche, si elle permet la description qualitative des relations ne permet pas de quantifier les relations spatiales. Elle a cependant l'avantage de faciliter la prise en compte du contexte spatial. Après avoir précisé les notions d'entités et de relations, nous prenons donc la topologie comme point de de départ pour l'étude et l'analyse de l'influence de l'environnement spatial dans la relation entre deux entitées données. Etudiant plus particulièrement la relation d'adjacence dans une partition spatiale, nous proposons un opérateur de proximité(l'adjacence relative) intégrant l'influence du contexte spatial avec une intensité modulable. Il est ensuite possible d'enrichir cet opérateur par l'intégration de grandeurs géomètriques et/ou attributaires (distance entre deux entités, superficie, ou encore périmètre). De plus, comme l'approche topologique permet une représentation sous forme de graphe relationnel, il est possible d'appliquer l'adjacence relative dans toute situation modélisable par un tel graphe(nous étudipons plus particulièrement les relations de voisinage entre territoires ainsi que les réseaux urbains). De ce point de vue, l'adjacence reletive émerge comme un nouvel outil d'analyse en syntaxe spatiale. Cependant, il reste difficile de représenter sur un même graphe des relations hétérogènes (c'est-à-dire principalement entre entités appartenant à des thématiques différentes). Nous explorons donc aussi cette voie dans le cas de l'interaction entre les entités de deux couches thématiqiues.

APA, Harvard, Vancouver, ISO, and other styles

10

Meot, Alain. "Explicitation de contraintes de voisinage en analyse multivariée : applications dans le cadre de problématiques agronomiques." Lyon 1, 1992. http://www.theses.fr/1992LYO10241.

Full text

Abstract:

Nous proposons dans ce memoire une solution simple a l'etude du lien entre une information multivariee et l'existence de proximites, generalement temporelles ou spatiales, entre les individus etudies. Le premier chapitre consiste en une revue non exhaustive des solutions proposees dans la litterature pour incorporer au cours d'une ordination une information spatiale. Dans un second chapitre nous examinons le cas ou, sur un ensemble d'individus, est definie une relation de voisinage notee sous la forme d'un graphe symetrique non value. Sont introduits dans la decomposition de la variance a partir du graphe deux operateurs, appeles operateurs de voisinage, dont les vecteurs propres possedent des proprietes extremales d'autocorrelation. Ces proprietes suggerent d'utiliser ces vecteurs propres en tant que variables instrumentales plutot que sur la base de leur definition de la variance comme le fait lebart (1969) pour les analyses locales. Les acp resultantes sont appelees analyses en composantes de voisinage (acv). Au cours du troisieme chapitre nous proposons deux illustrations pedagogiques de la demarche proposee. L'influence de proximites temporelles entre individus est en premier lieu illustree a partir de courbes de production annuelle de mandariniers. L'aspect spatial est ensuite aborde au travers de la description d'une grille de denombrement definie par l'observation de vaches paturant librement sur une grande parcelle. Le quatrieme chapitre est l'aboutissement d'une recherche pluridisciplinaire au sujet des pratiques d'organisation d'un territoire pature par un eleveur d'ovins. L'ordination sert a representer les trajectoires vegetales multivariees des divers elements spatiaux composant le territoire. Autour de cette description viennent s'agencer d'autres elements explicatifs du fonctionnement technique de cette exploitation. Les methodes proposees dans le second chapitre servent a entrer plus finement dans le jeu de donnees descriptif des trajectoires vegetales

APA, Harvard, Vancouver, ISO, and other styles

11

Maignant, Elodie. "Plongements barycentriques pour l'apprentissage géométrique de variétés : application aux formes et graphes." Electronic Thesis or Diss., Université Côte d'Azur, 2023. http://www.theses.fr/2023COAZ4096.

Full text

Abstract:

Une image obtenue par IRM, c'est plus de 60 000 pixels. La plus grosse protéine connue chez l'être humain est constituée d'environ 30 000 acides aminés. On parle de données en grande dimension. En réalité, la plupart des données en grande dimension ne le sont qu'en apparence. Par exemple, de toutes les images que l'on pourrait générer aléatoirement en coloriant 256 x 256 pixels, seule une infime proportion ressemblerait à l'image IRM d'un cerveau humain. C'est ce qu'on appelle la dimension intrinsèque des données. En grande dimension, apprentissage rime donc souvent avec réduction de dimension. Il existe de nombreuses méthodes de réduction de dimension, les plus récentes pouvant être classées selon deux approches.Une première approche, connue sous le nom d'apprentissage de variétés (manifold learning) ou réduction de dimension non linéaire, part du constat que certaines lois physiques derrière les données que l'on observe ne sont pas linéaires. Ainsi, espérer expliquer la dimension intrinsèque des données par un modèle linéaire est donc parfois irréaliste. Au lieu de cela, les méthodes qui relèvent du manifold learning supposent un modèle localement linéaire.D'autre part, avec l'émergence du domaine de l'analyse statistique de formes, il y eu une prise de conscience que de nombreuses données sont naturellement invariantes à certaines symétries (rotations, permutations, reparamétrisations...), invariances qui se reflètent directement sur la dimension intrinsèque des données. Ces invariances, la géométrie euclidienne ne peut pas les retranscrire fidèlement. Ainsi, on observe un intérêt croissant pour la modélisation des données par des structures plus fines telles que les variétés riemanniennes. Une deuxième approche en réduction de dimension consiste donc à généraliser les méthodes existantes à des données à valeurs dans des espaces non-euclidiens. On parle alors d'apprentissage géométrique. Jusqu'à présent, la plupart des travaux en apprentissage géométrique se sont focalisés sur l'analyse en composantes principales.Dans la perspective de proposer une approche qui combine à la fois apprentissage géométrique et manifold learning, nous nous sommes intéressés à la méthode appelée locally linear embedding, qui a la particularité de reposer sur la notion de barycentre, notion a priori définie dans les espaces euclidiens mais qui se généralise aux variétés riemanniennes. C'est d'ailleurs sur cette même notion que repose une autre méthode appelée barycentric subspace analysis, et qui fait justement partie des méthodes qui généralisent l'analyse en composantes principales aux variétés riemanniennes. Ici, nous introduisons la notion nouvelle de plongement barycentrique, qui regroupe les deux méthodes. Essentiellement, cette notion englobe un ensemble de méthodes dont la structure rappelle celle des méthodes de réduction de dimension linéaires et non linéaires, mais où le modèle (localement) linéaire est remplacé par un modèle barycentrique -- affine.Le cœur de notre travail consiste en l'analyse de ces méthodes, tant sur le plan théorique que pratique. Du côté des applications, nous nous intéressons à deux exemples importants en apprentissage géométrique : les formes et les graphes. En particulier, on démontre que par rapport aux méthodes standard de réduction de dimension en analyse statistique des graphes, les plongements barycentriques se distinguent par leur meilleure interprétabilité. En plus des questions pratiques liées à l'implémentation, chacun de ces exemples soulève ses propres questions théoriques, principalement autour de la géométrie des espaces quotients. Parallèlement, nous nous attachons à caractériser géométriquement les plongements localement barycentriques, qui généralisent la projection calculée par locally linear embedding. Enfin, de nouveaux algorithmes d'apprentissage géométrique, novateurs dans leur approche, complètent ce travail
An MRI image has over 60,000 pixels. The largest known human protein consists of around 30,000 amino acids. We call such data high-dimensional. In practice, most high-dimensional data is high-dimensional only artificially. For example, of all the images that could be randomly generated by coloring 256 x 256 pixels, only a very small subset would resemble an MRI image of a human brain. This is known as the intrinsic dimension of such data. Therefore, learning high-dimensional data is often synonymous with dimensionality reduction. There are numerous methods for reducing the dimension of a dataset, the most recent of which can be classified according to two approaches.A first approach known as manifold learning or non-linear dimensionality reduction is based on the observation that some of the physical laws behind the data we observe are non-linear. In this case, trying to explain the intrinsic dimension of a dataset with a linear model is sometimes unrealistic. Instead, manifold learning methods assume a locally linear model.Moreover, with the emergence of statistical shape analysis, there has been a growing awareness that many types of data are naturally invariant to certain symmetries (rotations, reparametrizations, permutations...). Such properties are directly mirrored in the intrinsic dimension of such data. These invariances cannot be faithfully transcribed by Euclidean geometry. There is therefore a growing interest in modeling such data using finer structures such as Riemannian manifolds. A second recent approach to dimension reduction consists then in generalizing existing methods to non-Euclidean data. This is known as geometric learning.In order to combine both geometric learning and manifold learning, we investigated the method called locally linear embedding, which has the specificity of being based on the notion of barycenter, a notion a priori defined in Euclidean spaces but which generalizes to Riemannian manifolds. In fact, the method called barycentric subspace analysis, which is one of those generalizing principal component analysis to Riemannian manifolds, is based on this notion as well. Here we rephrase both methods under the new notion of barycentric embeddings. Essentially, barycentric embeddings inherit the structure of most linear and non-linear dimension reduction methods, but rely on a (locally) barycentric -- affine -- model rather than a linear one.The core of our work lies in the analysis of these methods, both on a theoretical and practical level. In particular, we address the application of barycentric embeddings to two important examples in geometric learning: shapes and graphs. In addition to practical implementation issues, each of these examples raises its own theoretical questions, mostly related to the geometry of quotient spaces. In particular, we highlight that compared to standard dimension reduction methods in graph analysis, barycentric embeddings stand out for their better interpretability. In parallel with these examples, we characterize the geometry of locally barycentric embeddings, which generalize the projection computed by locally linear embedding. Finally, algorithms for geometric manifold learning, novel in their approach, complete this work

APA, Harvard, Vancouver, ISO, and other styles

12

Kokonendji, Célestin Clotaire. "Familles exponentielles naturelles réelles de fonction variance en R Q/ par Célestin Clotaire Kokonendji." Toulouse 3, 1993. http://www.theses.fr/1993TOU30092.

Full text

Abstract:

L'etude des familles exponentielles naturelles (f. E. N. ) reelles par leur fonction variance conduit naturellement a l'introduction de la classe de grand-babel qui generalise les classes fondamentales de morris et de mora. La premiere partie de cette these est consacree a une construction des elements d'une sous-classe de grand-babel dite de seshadri par l'action de la transformation de lindsay sur les elements de mora. (l'idee d'etudier cette action revient a v. Seshadri, et il est donc cosignataire de cette partie). Le resultat essentiel est de montrer que les lois de mora sont doublement indefiniment divisibles. La deuxieme partie fait une classification complete des f. E. N. De seshadri, caracterise sa fermeture et en donne des interpretations probabilistes. La troisieme partie plus generalement, etudie les f. E. N. De grand-babel. Elle donne d'abord des exemples et des techniques de construction probabiliste. Le resultat principal est une quasi-caracterisation en termes de familles des lois a priori conjuguees au sens bayesien. Cela est precede de considerations geometriques

APA, Harvard, Vancouver, ISO, and other styles

13

Dasse-Hartaut, Sandrine. "Combinatoire des tableaux escalier." Paris 7, 2014. http://www.theses.fr/2014PA077070.

Full text

Abstract:

Les tableaux escalier sont des objets combinatoires définis par S. Corteel et L. Williams, qui généralisent les tableaux de permutations et les tableaux alternatifs. Ils ont été utilisés pour donner une formule combinatoire pour les moments des polynômes d'Askey-Wilson. Les tableaux escalier sont également liés au processus d'exclusion asymétrique sur un réseau unidimensionnel avec bords ouverts, l'ASEP, un modèle de physique statistique important et sujet de nombreuses études, et ont permis de donner une formule combinatoire pour en exprimer la probabilité stationnaire. On montre ici différentes approches des tableaux escalier : une approche probabiliste permet d'en déduire des propriétés exactes et asymptotiques, une approche bijective permet de découvrir des propriétés de sous-ensembles de ces tableaux, via les tree-like tableaux ou des tables d'inversion. Enfin, une chaîne de Marov sur un sous-ensemble des tableaux escalier confirme intuitivement les formules obtenues par le calcul de la probabilité stationnaire du PASEP
A relatively new combinatorial structure, called staircase tableaux, was introduced in recent work of S. Corteel and L. Williams. Staircase tableaux are a generalisation of permutation tableaux and alternative tableaux. Their study gave a combinatorial formula for the moments of Askey-Wilson polynomials. Staircase tableaux are also related to the asymmetric exclusion process on a one-dimensional lattice with open boundaries (ASEP), an important and heavily studied particle model in statistical mechanics. The study of the generating function of the staircase tableau has given a combinatorial formula for the steady state probability of the ASEP. We use differents approaches to study the staircase tableaux : with a probabilistic approach, we prove the asymptotic normality of some parameters of the staircase tableaux ; with bijective combinatorics, we get the properties of some subsets of staircase tableaux, using for example tree-like tableaux or permutations. Finally, a Markov chain on a subset of staircase tableaux confirms intuitively the formula for the steady state probability without using the matrix ansatz

APA, Harvard, Vancouver, ISO, and other styles

14

Lagesse, Claire. "Lire les lignes de la ville : méthodologie de caractérisation des graphes spatiaux." Sorbonne Paris Cité, 2015. http://www.theses.fr/2015USPCC162.

Full text

Abstract:

La ville regroupe une grande diversité de composants et d'interactions. Parmi sa pluralité, nous choisissons un élément qui structure son développement et son usage : le réseau de ses rues. À partir de sa représentation sous forme de graphe, nous construisons un objet, la voie, qui se révèle être multi-échelle, rendant son analyse robuste au découpage du réseau. Nous étudions plusieurs indicateurs et nous établissons une grammaire de caractérisations non-redondantes des graphes spatiaux. La voie montre ainsi des propriétés spatiales particulières, rendant équivalentes certaines analyses globales à d'autres locales. L'application de cette méthodologie nous permet de mettre en évidence les propriétés particulières partagées par des graphes viaires de différents continents, et celles qui se retrouvent également dans d'autres réseaux spatiaux (biologiques, etc). Dans une approche diachronique, nous construisons une méthodologie de différentiation temporelle, permettant de quantifier les changements de proximité topologique entre les éléments du graphe. Cela nous permet d'avoir une première appréhension de la cinématique de croissance des réseaux étudiés. Cette recherche se termine par l'intégration de l'objet voie et de ses indicateurs dans une approche qualitative. Nous montrons ainsi comment l'analyse de villes, à travers les propriétés topologiques et topographiques de leurs réseaux viaires, permet de retrouver une partie des contextes historiques et géographiques de leur construction. La mise en perspective de ces travaux, par une synthèse des échanges pluridisciplinaires qui les ont entourés, révèle le potentiel de leurs applications et les pistes de recherches offertes
Cities arise from a large set of interactions and components. Amid this diversity, we chose an object which orchestrates the development and use of an urban area : the road network. From its representation with a graph we can build a geographical object called the way, which is multi-scale, making its analysis robust against zoning. We evaluate several indicators, and identify those that give the most relevant and non-redundant information. The way, appears to have unique spatial properties, revealing parallels between global and local analyses. With this methodology, we demonstrate how different road graphs, from various places in the world, show similar properties, and how some of those properties are also present in other networks (biological, hydrographical, etc). After considering the static properties of networks, we analyze how global characterization evolves through time. We define a model of temporal differentiation, where the change in accessibility of each object is highlighted. It is thus possible to have a first estimation of the growth kinematic of the road networks studied. This work culminates with the integration of the way and its associated indicators into a qualitative approach. We show how such analysis, based on the topological and topographical properties of their road networks, allows us to trace back some aspects of the historical and geographical contexts of city formation. Multidisciplinary discussions are synthesized to reveal research applications and future work

APA, Harvard, Vancouver, ISO, and other styles

15

Iacopini, Matteo. "Essays on econometric modelling of temporal networks." Thesis, Paris 1, 2018. http://www.theses.fr/2018PA01E058/document.

Full text

Abstract:

La théorie des graphes a longtemps été étudiée en mathématiques et en probabilité en tant qu’outil pour décrire la dépendance entre les nœuds. Cependant, ce n’est que récemment qu’elle a été mise en œuvre sur des données, donnant naissance à l’analyse statistique des réseaux réels.La topologie des réseaux économiques et financiers est remarquablement complexe: elle n’est généralement pas observée, et elle nécessite ainsi des procédures inférentielles adéquates pour son estimation, d’ailleurs non seulement les nœuds, mais la structure de la dépendance elle-même évolue dans le temps. Des outils statistiques et économétriques pour modéliser la dynamique de changement de la structure du réseau font défaut, malgré leurs besoins croissants dans plusieurs domaines de recherche. En même temps, avec le début de l’ère des “Big data”, la taille des ensembles de données disponibles devient de plus en plus élevée et leur structure interne devient de plus en plus complexe, entravant les processus inférentiels traditionnels dans plusieurs cas. Cette thèse a pour but de contribuer à ce nouveau champ littéraire qui associe probabilités, économie, physique et sociologie en proposant de nouvelles méthodologies statistiques et économétriques pour l’étude de l’évolution temporelle des structures en réseau de moyenne et haute dimension
Graph theory has long been studied in mathematics and probability as a tool for describing dependence between nodes. However, only recently it has been implemented on data, giving birth to the statistical analysis of real networks.The topology of economic and financial networks is remarkably complex: it is generally unobserved, thus requiring adequate inferential procedures for it estimation, moreover not only the nodes, but the structure of dependence itself evolves over time. Statistical and econometric tools for modelling the dynamics of change of the network structure are lacking, despite their increasing requirement in several fields of research. At the same time, with the beginning of the era of “Big data” the size of available datasets is becoming increasingly high and their internal structure is growing in complexity, hampering traditional inferential processes in multiple cases.This thesis aims at contributing to this newborn field of literature which joins probability, economics, physics and sociology by proposing novel statistical and econometric methodologies for the study of the temporal evolution of network structures of medium-high dimension

APA, Harvard, Vancouver, ISO, and other styles

16

Jmel, Saïd. "Applications des modèles graphiques au choix de variables et à l'analyse des interactions dans une table de contingence multiple." Toulouse 3, 1992. http://www.theses.fr/1992TOU30091.

Full text

Abstract:

On presente quelques aspects de l'apport des modeles graphiques en analyse des donnees multidimensionnelles. Deux sujets ont ete abordes. Le premier concerne la selection des variables. On propose une nouvelle methode basee sur un type particulier de modeles graphiques. On donne deux applications de cette methode: la premiere en analyse en composantes principales et la seconde en analyse loglineaire. Le second sujet traite de la modelisation des interactions dans une table de contingence multiple. On montre comment l'analyse factorielle des correspondances et les modeles d'association ligne colonne de goodman peuvent sous certaines contraintes prendre en consideration la structure du graphe d'interactions ou le graphe d'independance conditionnelle associe a cette table. En complement, on suggere quelques techniques d'analyse des donnees susceptibles d'aider a la construction de tels graphes

APA, Harvard, Vancouver, ISO, and other styles

17

Kadavankandy, Arun. "L’analyse spectrale des graphes aléatoires et son application au groupement et l’échantillonnage." Thesis, Université Côte d'Azur (ComUE), 2017. http://www.theses.fr/2017AZUR4059/document.

Full text

Abstract:

Dans cette thèse, nous étudions les graphes aléatoires en utilisant des outils de la théorie des matrices aléatoires et l’analyse probabilistique afin de résoudre des problèmes clefs dans le domaine des réseaux complexes et Big Data. Le premier problème qu’on considère est de détecter un sous graphe Erdős–Rényi G(m,p) plante dans un graphe Erdős–Rényi G(n,q). Nous dérivons les distributions d’une statistique basée sur les propriétés spectrales d’une matrice définie du graphe. Ensuite, nous considérons le problème de la récupération des sommets du sous graphe en présence de l’information supplémentaire. Pour cela nous utilisons l’algorithme «Belief Propagation». Le BP sans informations supplémentaires ne réussit à la récupération qu’avec un SNR effectif lambda au-delà d’un seuil. Nous prouvons qu’en présence des informations supplémentaires, ce seuil disparaît et le BP réussi pour n’importe quel lambda. Finalement, nous dérivons des expressions asymptotiques pour PageRank sur une classe de graphes aléatoires non dirigés appelés « fast expanders », en utilisant des techniques théoriques à la matrice aléatoire. Nous montrons que PageRank peut être approché pour les grandes tailles du graphe comme une combinaison convexe du vecteur de dégré normalisé et le vecteur de personnalisation du PageRank, lorsque le vecteur de personnalisation est suffisamment délocalisé. Par la suite, nous caractérisons les formes asymptotiques de PageRank sur le Stochastic Block Model (SBM) et montrons qu’il contient un terme de correction qui est fonction de la structure de la communauté
In this thesis, we study random graphs using tools from Random Matrix Theory and probability to tackle key problems in complex networks and Big Data. First we study graph anomaly detection. Consider an Erdős-Rényi (ER) graph with edge probability q and size n containing a planted subgraph of size m and probability p. We derive a statistical test based on the eigenvalue and eigenvector properties of a suitably defined matrix to detect the planted subgraph. We analyze the distribution of the derived test statistic using Random Matrix Theoretic techniques. Next, we consider subgraph recovery in this model in the presence of side-information. We analyse the effect of side-information on the detectability threshold of Belief Propagation (BP) applied to the above problem. We show that BP correctly recovers the subgraph even with noisy side-information for any positive value of an effective SNR parameter. This is in contrast to BP without side-information which requires the SNR to be above a certain threshold. Finally, we study the asymptotic behaviour of PageRank on a class of undirected random graphs called fast expanders, using Random Matrix Theoretic techniques. We show that PageRank can be approximated for large graph sizes as a convex combination of the normalized degree vector and the personalization vector of the PageRank, when the personalization vector is sufficiently delocalized. Subsequently, we characterize asymptotic PageRank on Stochastic Block Model (SBM) graphs, and show that it contains a correction term that is a function of the community structure

APA, Harvard, Vancouver, ISO, and other styles

18

Martinet, Lucie. "Réseaux dynamiques de terrain : caractérisation et propriétés de diffusion en milieu hospitalier." Thesis, Lyon, École normale supérieure, 2015. http://www.theses.fr/2015ENSL1010/document.

Full text

Abstract:

Durant cette thèse, nous nous sommes intéressés aux outils permettant d'extraire les propriétés structurelles et temporelles de réseaux dynamiques ainsi que les caractéristiques de certains scénarios de diffusion pouvant s'opérer sur ces réseaux. Nous avons travaillé sur un jeu de données spécifiques, issu du projet MOSAR, qui comporte entre autre le réseau de proximité des personnes au cours du temps durant 6 mois à l'hôpital de Berk-sur-mer. Ce réseau est particulier dans le sens où il est constitué de trois dimensions: temporelle, structurelle par la répartition des personnes en services et fonctionnelle car chaque personne appartient à une catégorie socio-professionnelle. Pour chacune des dimensions, nous avons utilisé des outils existants en physique statistique ainsi qu'en théorie des graphes pour extraire des informations permettant de décrire certaines propriétés du réseau. Cela nous a permis de souligner le caractère très structuré de la répartition des contacts qui suit la répartition en services et mis en évidence les accointances entre certaines catégories professionnelles. Concernant la partie temporelle, nous avons mis en avant l'évolution périodique circadienne et hebdomadaire ainsi que les différences fondamentales entre l'évolution des interactions des patients et celle des personnels. Nous avons aussi présenté des outils permettant de comparer l'activité entre deux périodes données et de quantifier la similarité de ces périodes. Nous avons ensuite utilisé la technique de simulation pour extraire des propriétés de diffusion de ce réseau afin de donner quelques indices pour établir une politique de prévention
In this thesis, we focus on tools whose aim is to extract structural and temporal properties of dynamic networks as well as diffusion characteristics which can occur on these networks. We work on specific data, from the European MOSAR project, including the network of individuals proximity from time to time during 6 months at the Brek-sur-Mer Hospital. The studied network is notable because of its three dimensions constitution : the structural one induced by the distribution of individuals into distinct services, the functional dimension due to the partition of individual into groups of socio-professional categories and the temporal dimension.For each dimension, we used tools well known from the areas of statistical physics as well as graphs theory in order to extract information which enable to describe the network properties. These methods underline the specific structure of the contacts distribution which follows the individuals distribution into services. We also highlight strong links within specific socio-professional categories. Regarding the temporal part, we extract circadian and weekly patterns and quantify the similarities of these activities. We also notice distinct behaviour within patients and staff evolution. In addition, we present tools to compare the network activity within two given periods. To finish, we use simulations techniques to extract diffusion properties of the network to find some clues in order to establish a prevention policy

APA, Harvard, Vancouver, ISO, and other styles

19

Blazere, Melanie. "Inférence statistique en grande dimension pour des modèles structurels. Modèles linéaires généralisés parcimonieux, méthode PLS et polynômes orthogonaux et détection de communautés dans des graphes." Thesis, Toulouse, INSA, 2015. http://www.theses.fr/2015ISAT0018/document.

Full text

Abstract:

Cette thèse s'inscrit dans le cadre de l'analyse statistique de données en grande dimension. Nous avons en effet aujourd'hui accès à un nombre toujours plus important d'information. L'enjeu majeur repose alors sur notre capacité à explorer de vastes quantités de données et à en inférer notamment les structures de dépendance. L'objet de cette thèse est d'étudier et d'apporter des garanties théoriques à certaines méthodes d'estimation de structures de dépendance de données en grande dimension.La première partie de la thèse est consacrée à l'étude de modèles parcimonieux et aux méthodes de type Lasso. Après avoir présenté les résultats importants sur ce sujet dans le chapitre 1, nous généralisons le cas gaussien à des modèles exponentiels généraux. La contribution majeure à cette partie est présentée dans le chapitre 2 et consiste en l'établissement d'inégalités oracles pour une procédure Group Lasso appliquée aux modèles linéaires généralisés. Ces résultats montrent les bonnes performances de cet estimateur sous certaines conditions sur le modèle et sont illustrés dans le cas du modèle Poissonien. Dans la deuxième partie de la thèse, nous revenons au modèle de régression linéaire, toujours en grande dimension mais l'hypothèse de parcimonie est cette fois remplacée par l'existence d'une structure de faible dimension sous-jacente aux données. Nous nous penchons dans cette partie plus particulièrement sur la méthode PLS qui cherche à trouver une décomposition optimale des prédicteurs étant donné un vecteur réponse. Nous rappelons les fondements de la méthode dans le chapitre 3. La contribution majeure à cette partie consiste en l'établissement pour la PLS d'une expression analytique explicite de la structure de dépendance liant les prédicteurs à la réponse. Les deux chapitres suivants illustrent la puissance de cette formule aux travers de nouveaux résultats théoriques sur la PLS . Dans une troisième et dernière partie, nous nous intéressons à la modélisation de structures au travers de graphes et plus particulièrement à la détection de communautés. Après avoir dressé un état de l'art du sujet, nous portons notre attention sur une méthode en particulier connue sous le nom de spectral clustering et qui permet de partitionner les noeuds d'un graphe en se basant sur une matrice de similarité. Nous proposons dans cette thèse une adaptation de cette méthode basée sur l'utilisation d'une pénalité de type l1. Nous illustrons notre méthode sur des simulations
This thesis falls within the context of high-dimensional data analysis. Nowadays we have access to an increasing amount of information. The major challenge relies on our ability to explore a huge amount of data and to infer their dependency structures.The purpose of this thesis is to study and provide theoretical guarantees to some specific methods that aim at estimating dependency structures for high-dimensional data. The first part of the thesis is devoted to the study of sparse models through Lasso-type methods. In Chapter 1, we present the main results on this topic and then we generalize the Gaussian case to any distribution from the exponential family. The major contribution to this field is presented in Chapter 2 and consists in oracle inequalities for a Group Lasso procedure applied to generalized linear models. These results show that this estimator achieves good performances under some specific conditions on the model. We illustrate this part by considering the case of the Poisson model. The second part concerns linear regression in high dimension but the sparsity assumptions is replaced by a low dimensional structure underlying the data. We focus in particular on the PLS method that attempts to find an optimal decomposition of the predictors given a response. We recall the main idea in Chapter 3. The major contribution to this part consists in a new explicit analytical expression of the dependency structure that links the predictors to the response. The next two chapters illustrate the power of this formula by emphasising new theoretical results for PLS. The third and last part is dedicated to graphs modelling and especially to community detection. After presenting the main trends on this topic, we draw our attention to Spectral Clustering that allows to cluster nodes of a graph with respect to a similarity matrix. In this thesis, we suggest an alternative to this method by considering a $l_1$ penalty. We illustrate this method through simulations

APA, Harvard, Vancouver, ISO, and other styles

20

Manouvrier, Jean-François. "Méthode de décomposition pour résoudre des problèmes combinatoires sur les graphes." Compiègne, 1998. http://www.theses.fr/1998COMP1152.

Full text

Abstract:

Les travaux de cette thèse utilisent une méthode de décomposition pour résoudre des problèmes combinatoires NP-difficiles énoncés sous la forme de problèmes de graphes. Parmi les méthodes exactes existantes, les méthodes utilisant une décomposition-arbre du graphe permettent de résoudre certains problèmes NP-difficiles en temps polynomial pour un graphe de largeur-arbre inferieur à K. K est une constante fixée en fonction du problème et des capacités de la machine utilisée. Nous nommons ces méthodes de programmation dynamique : méthodes de décomposition. Dans cette thèse, nous utilisons une décomposition-chemin du graphe, basée sur une numérotation linéaire des sommets du graphe, pour résoudre certains problèmes NP-difficiles. Les problèmes que nous avons ainsi traites sont les problèmes de la fiabilité des réseaux (fiabilité tous-terminaux et fiabilité 2-arête-connexe tous-terminaux), le problème du voyageur de commerce et le problème de l'arbre de Steiner minimal. Pour chacun de ces problèmes, nous étudions les autres méthodes existantes, nous démontrons que la méthode de décomposition peut être appliquée, en modélisant des classes d'équivalences regroupant des solutions partielles, et nous analysons l'implémentation de ces méthodes. Une des difficultés essentielles de l'implémentation des programmes de décomposition consiste à gérer efficacement en mémoire les classes. Pour la fiabilité 2-arête-connexe tous-terminaux, la structure des classes nous a contraints à introduire un concept de forêts fictives et à développer un algorithme énumérant ces forêts. Nous obtenons ainsi des algorithmes de décomposition résolvant ces problèmes, dont les complexités en temps sont linéaires en fonction de la taille du graphe pour des graphes de largeur-chemin bornée.

APA, Harvard, Vancouver, ISO, and other styles

21

Tremblay, Nicolas. "Réseaux et signal : des outils de traitement du signal pour l'analyse des réseaux." Thesis, Lyon, École normale supérieure, 2014. http://www.theses.fr/2014ENSL0938/document.

Full text

Abstract:

Cette thèse propose de nouveaux outils adaptés à l'analyse des réseaux : sociaux, de transport, de neurones, de protéines, de télécommunications... Ces réseaux, avec l'essor de certaines technologies électroniques, informatiques et mobiles, sont de plus en plus mesurables et mesurés ; la demande d'outils d'analyse assez génériques pour s'appliquer à ces réseaux de natures différentes, assez puissants pour gérer leur grande taille et assez pertinents pour en extraire l'information utile, augmente en conséquence. Pour répondre à cette demande, une grande communauté de chercheurs de différents horizons scientifiques concentre ses efforts sur l'analyse des graphes, des outils mathématiques modélisant la structure relationnelle des objets d'un réseau. Parmi les directions de recherche envisagées, le traitement du signal sur graphe apporte un éclairage prometteur sur la question : le signal n'est plus défini comme en traitement du signal classique sur une topologie régulière à n dimensions, mais sur une topologie particulière définie par le graphe. Appliquer ces idées nouvelles aux problématiques concrètes d'analyse d'un réseau, c'est ouvrir la voie à une analyse solidement fondée sur la théorie du signal. C'est précisément autour de cette frontière entre traitement du signal et science des réseaux que s'articule cette thèse, comme l'illustrent ses deux principales contributions. D'abord, une version multiéchelle de détection de communautés dans un réseau est introduite, basée sur la définition récente des ondelettes sur graphe. Puis, inspirée du concept classique de bootstrap, une méthode de rééchantillonnage de graphes est proposée à des fins d'estimation statistique
This thesis describes new tools specifically designed for the analysis of networks such as social, transportation, neuronal, protein, communication networks... These networks, along with the rapid expansion of electronic, IT and mobile technologies are increasingly monitored and measured. Adapted tools of analysis are therefore very much in demand, which need to be universal, powerful, and precise enough to be able to extract useful information from very different possibly large networks. To this end, a large community of researchers from various disciplines have concentrated their efforts on the analysis of graphs, well define mathematical tools modeling the interconnected structure of networks. Among all the considered directions of research, graph signal processing brings a new and promising vision : a signal is no longer defined on a regular n-dimensional topology, but on a particular topology defined by the graph. To apply these new ideas on the practical problems of network analysis paves the way to an analysis firmly rooted in signal processing theory. It is precisely this frontier between signal processing and network science that we explore throughout this thesis, as shown by two of its major contributions. Firstly, a multiscale version of community detection in networks is proposed, based on the recent definition of graph wavelets. Then, a network-adapted bootstrap method is introduced, that enables statistical estimation based on carefully designed graph resampling schemes

APA, Harvard, Vancouver, ISO, and other styles

22

Gaillard, Pierre. "Apprentissage statistique de la connexité d'un nuage de points par modèle génératif : application à l'analyse exploratoire et la classification semi-supervisée." Compiègne, 2008. http://www.theses.fr/2008COMP1767.

Full text

Abstract:

Dans cette thèse, nous présentons un modèle statistique permettant d'extraire la connexité des variétés structurantes d'un ensemble de points. Ce modèle combine des approches statistiques et géométriques en définissant un modèle de mélange gaussien construit à partir d'un graphe. A partir de ce graphe génératif, nous proposons et évaluons des méthodes d'analyses exploratoires et de classification non-supervisée et semi-supervisée
In this work, we propose a statistical model to learn the connectedness of a set of points. This model combine geometrical and statistical approaches by defining a mixture model based on a graph. From this generative graph, we propose and evaluate methods and algorithms to analyse the set of points and to realize semi-supervised learning

APA, Harvard, Vancouver, ISO, and other styles

23

Frindel, Carole. "Imagerie par résonance magnétique du tenseur de diffusion (IRM-TD) en imagerie cardiaque humaine : traitements et premi`eres interprétations." Phd thesis, INSA de Lyon, 2009. http://tel.archives-ouvertes.fr/tel-00473031.

Full text

Abstract:

Cette thèse a pour cadre l'étude de l'organisation spatiale des fibres du muscle cardiaque à partir de séries d'images tridimensionnelles acquises par IRM du Tenseur de Diffusion (IRMTD). Cette organisation constitue une propriété fondamentale du coeur sous-tendant la fonction contractile. Néanmoins elle est très complexe à obtenir au vu des difficultés inhérentes au mouvements cardiaque et respiratoire. Notre objectif consiste à développer de nouvelles approches, basées sur la prise en compte du mouvement du coeur et de la sensibilité au bruit de l'acquisition, pour l'estimation, l'analyse et la visualisation des fibres du myocarde. Dans ce cadre, mes travaux se déclinent selon trois axes principaux. Le premier compare, dans le contexte d'études cliniques ex vivo, les principales approches de régularisation opérant soit sur les images pondérées en diffusion soit sur les champs de tenseurs de diffusion. Les différences sont suffisamment faibles pour conclure que la qualité de nos données IRMTD est suffisante pour considérer toutes les méthodes de régularisation comme équivalentes. Partant de ce constat, une méthode de régularisation simple et rapide apparaî satisfaisante. Le second concerne la mise en place d'une méthode de tractographie spécialement conçue pour la spécificité cardiaque. Celle-ci est guidée par une fonctionnelle de coût globale qui permet l'estimation automatique des fibres cardiaques en une seule fois pour l'ensemble des données, et ce sans l'utilisation de points d'initialisation. Le dernier axe consiste en la distinction d'une population de fibres cardiaques en sous-groupes. Celle-ci s'appuie sur la comparaison de méthodes de classification de type géométrique et de type topologique exploitant toutes trois modes différents de représentation des fibres. Les résultats établissent que la classification pourrait permettre l'identification automatique de régions spécialisées dans le myocarde, ce qui pourrait grandement faciliter l'analyse et la comparaison des données IRMTD cardiaques pour la conception de thérapies patient-spécifiques.

APA, Harvard, Vancouver, ISO, and other styles

24

Heymann, Sébastien. "Analyse exploratoire de flots de liens pour la détection d'événements." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2013. http://tel.archives-ouvertes.fr/tel-00994766.

Full text

Abstract:

Un flot de liens représente une trace de l'activité d'un système complexe au cours du temps, où un lien apparaît lorsque deux entités du système entrent en interaction ; l'ensemble des entités et des liens forme un graphe. Ces traces constituent depuis quelques années des jeux de données stratégiques dans l'analyse de l'activité de systèmes complexes à grande échelle, impliquant des millions d'entités : réseaux de téléphone mobiles, réseaux sociaux, ou encore Internet. Cette thèse porte sur l'analyse exploratoire des flots de liens, en particulier sur la caractérisation de leur dynamique et l'identification d'anomalies au cours du temps (événements). Nous proposons un cadre exploratoire sans hypothèse sur les données, faisant appel à l'analyse statistique et à la visualisation. Les événements détectés sont statistiquement significatifs et nous proposons une méthode pour valider leur pertinence. Nous illustrons enfin notre méthodologie sur l'évolution du réseau social en ligne Github, où des centaines de milliers de développeurs collaborent sur des projets de logiciel.

APA, Harvard, Vancouver, ISO, and other styles

25

Munch, Mélanie. "Améliorer le raisonnement dans l'incertain en combinant les modèles relationnels probabilistes et la connaissance experte." Thesis, université Paris-Saclay, 2020. http://www.theses.fr/2020UPASB011.

Full text

Abstract:

Cette thèse se concentre sur l'intégration des connaissances d'experts pour améliorer le raisonnement dans l'incertitude. Notre objectif est de guider l'apprentissage des relations probabilistes avec les connaissances d'experts pour des domaines décrits par les ontologies.Pour ce faire, nous proposons de coupler des bases de connaissances (BC) et une extension orientée objet des réseaux bayésiens, les modèles relationnels probabilistes (PRM). Notre objectif est de compléter l'apprentissage statistique par des connaissances expertes afin d'apprendre un modèle aussi proche que possible de la réalité et de l'analyser quantitativement (avec des relations probabilistes) et qualitativement (avec la découverte causale). Nous avons développé trois algorithmes à travers trois approches distinctes, dont les principales différences résident dans leur automatisation et l'intégration (ou non) de la supervision d'experts humains.L'originalité de notre travail est la combinaison de deux philosophies opposées : alors que l'approche bayésienne privilégie l'analyse statistique des données fournies pour raisonner avec, l'approche ontologique est basée sur la modélisation de la connaissance experte pour représenter un domaine. La combinaison de la force des deux permet d'améliorer à la fois le raisonnement dans l'incertitude et la connaissance experte
This thesis focuses on integrating expert knowledge to enhance reasoning under uncertainty. Our goal is to guide the probabilistic relations’ learning with expert knowledge for domains described by ontologies.To do so we propose to couple knowledge bases (KBs) and an oriented-object extension of Bayesian networks, the probabilistic relational models (PRMs). Our aim is to complement the statistical learning with expert knowledge in order to learn a model as close as possible to the reality and analyze it quantitatively (with probabilistic relations) and qualitatively (with causal discovery). We developped three algorithms throught three distinct approaches, whose main differences lie in their automatisation and the integration (or not) of human expert supervision.The originality of our work is the combination of two broadly opposed philosophies: while the Bayesian approach favors the statistical analysis of the given data in order to reason with it, the ontological approach is based on the modelization of expert knowledge to represent a domain. Combining the strenght of the two allows to improve both the reasoning under uncertainty and the expert knowledge

APA, Harvard, Vancouver, ISO, and other styles

26

Mahmoudi, Saïd. "Indexation de formes planes : application à la reconnaissance multi-vues de modèles 3D." Lille 1, 2003. https://pepite-depot.univ-lille.fr/RESTREINT/Th_Num/2003/50376-2003-291.pdf.

Full text

Abstract:

Cette thèse s'inscrit dans le domaine de l'indexation et de la reconnaissance des formes planes dans une base constituée d'objets contours, et son application dans l'indexation multi-vues des objets tridimensionnels. Notre approche permet de reconnaître les objets 3D à partir d'une requête qui peut être une forme 2D ou une vue arbitraire d'un objet tridimensionnel. Un des problèmes fondamentaux de l'indexation d'images par la forme réside dans le choix d'une description invariante de celle-ci. Pour cela, nous proposons l'utilisation du descripteur CSS, qui s'appuie sur une analyse multi-échelle du contour. Nous proposons une organisation de l'index extrait à partir du CSS par une structure d'arbre dite M-tree, qui est totalement paramétrisée par une fonction de distance et qui permet aussi en sauvegardant les distances intermédiaires d'améliorer considérablement les temps de calculs. Nous avons aussi introduit une technique probabiliste bayésienne de recherche de ressemblance entre formes. L'application proposée représente une nouvelle méthode d'indexation de modèles 3D. Cette méthode consiste à caractériser les objets 3D par un ensemble de sept vues caractéristiques (trois principales et quatre secondaires). Les angles de prise de vues principales sont choisis par le biais d'une analyse d'information présente sous forme de nuage de points sur l'objet 3D. Les vues secondaires sont déduites à partir des vues principales. L'index du modèle 3D est calculé à partir des index correspondants aux sept vues qui le caractérisent. De ce fait, nous utilisons l'approche de reconnaissance de formes proposée pour le procédé de reconnaissance des vues. Une méthode de vote bayésienne est proposée pour la sélection des objets 3D similaires à la requête.

APA, Harvard, Vancouver, ISO, and other styles

27

Monnin, Pierre. "Matching and mining in knowledge graphs of the Web of data : Applications in pharmacogenomics." Electronic Thesis or Diss., Université de Lorraine, 2020. http://www.theses.fr/2020LORR0212.

Full text

Abstract:

Dans le Web des données, des graphes de connaissances de plus en plus nombreux sont simultanément publiés, édités, et utilisés par des agents humains et logiciels. Cette large adoption rend essentielles les tâches d'appariement et de fouille. L'appariement identifie des unités de connaissances équivalentes, plus spécifiques ou similaires au sein et entre graphes de connaissances. Cette tâche est cruciale car la publication et l'édition parallèles peuvent mener à des graphes de connaissances co-existants et complémentaires. Cependant, l'hétérogénéité inhérente aux graphes de connaissances (e.g., granularité, vocabulaires, ou complétude) rend cette tâche difficile. Motivés par une application en pharmacogénomique, nous proposons deux approches pour apparier des relations n-aires représentées au sein de graphes de connaissances : une méthode symbolique à base de règles et une méthode numérique basée sur le plongement de graphe. Nous les expérimentons sur PGxLOD, un graphe de connaissances que nous avons construit de manière semi-automatique en intégrant des relations pharmacogénomiques de trois sources du domaine. La tâche de fouille permet quant à elle de découvrir de nouvelles unités de connaissances à partir des graphes de connaissances. Leur taille croissante et leur nature combinatoire entraînent des problèmes de passage à l'échelle que nous étudions dans le cadre de la fouille de patrons de chemins. Nous proposons également l'annotation de concepts, une méthode d'amélioration des graphes de connaissances qui étend l'Analyse Formelle de Concepts, un cadre mathématique groupant des entités en fonction de leurs attributs communs. Au cours de tous nos travaux, nous nous sommes particulièrement intéressés à tirer parti des connaissances de domaines formalisées au sein d'ontologies qui peuvent être associées aux graphes de connaissances. Nous montrons notamment que, lorsqu'elles sont prises en compte, ces connaissances permettent de réduire l'impact des problèmes d'hétérogénéité et de passage à l'échelle dans les tâches d'appariement et de fouille
In the Web of data, an increasing number of knowledge graphs are concurrently published, edited, and accessed by human and software agents. Their wide adoption makes key the two tasks of matching and mining. First, matching consists in identifying equivalent, more specific, or somewhat similar units within and across knowledge graphs. This task is crucial since concurrent publication and edition may result in coexisting and complementary knowledge graphs. However, this task is challenging because of the inherent heterogeneity of knowledge graphs, e.g., in terms of granularities, vocabularies, and completeness. Motivated by an application in pharmacogenomics, we propose two approaches to match n-ary relationships represented in knowledge graphs: a symbolic rule-based approach and a numeric approach using graph embedding. We experiment on PGxLOD, a knowledge graph that we semi-automatically built by integrating pharmacogenomic relationships from three distinct sources of this domain. Second, mining consists in discovering new and useful knowledge units from knowledge graphs. Their increasing size and combinatorial nature entail scalability issues, which we address in the mining of path patterns. We also propose Concept Annotation, a refinement approach extending Formal Concept Analysis, a mathematical framework that groups entities based on their common attributes. Throughout all our works, we particularly focus on taking advantage of domain knowledge in the form of ontologies that can be associated with knowledge graphs. We show that, when considered, such domain knowledge alleviates heterogeneity and scalability issues in matching and mining approaches

APA, Harvard, Vancouver, ISO, and other styles

28

Guigourès, Romain. "Utilisation des modèles de co-clustering pour l'analyse exploratoire des données." Phd thesis, Université Panthéon-Sorbonne - Paris I, 2013. http://tel.archives-ouvertes.fr/tel-00935278.

Full text

Abstract:

Le co-clustering est une technique de classification consistant à réaliser une partition simultanée des lignes et des colonnes d'une matrice de données. Parmi les approches existantes, MODL permet de traiter des données volumineuses et de réaliser une partition de plusieurs variables, continues ou nominales. Nous utilisons cette approche comme référence dans l'ensemble des travaux de la thèse et montrons la diversité des problèmes de data mining pouvant être traités, comme le partitionnement de graphes, de graphes temporels ou encore le clustering de courbes. L'approche MODL permet d'obtenir des résultats fins sur des données volumineuses, ce qui les rend difficilement interprétables. Des outils d'analyse exploratoire sont alors nécessaires pour les exploiter. Afin de guider l'utilisateur dans l'interprétation de tels résultats, nous définissons plusieurs outils consistant à simplifier des résultats fins afin d'en avoir une interprétation globale, à détecter les clusters remarquables, à déterminer les valeurs représentatives de leurs clusters et enfin à visualiser les résultats. Les comportements asymptotiques de ces outils d'analyse exploratoire sont étudiés afin de faire le lien avec les approches existantes. Enfin une application sur des comptes-rendus d'appels de l'opérateur Orange, collectés en Côte d'Ivoire, montre l'intérêt de l'approche et des outils d'analyse exploratoire dans un contexte industriel.

APA, Harvard, Vancouver, ISO, and other styles

29

Coupechoux, Emilie. "Analyse de grands graphes aléatoires." Paris 7, 2012. http://www.theses.fr/2012PA077184.

Full text

Abstract:

Plusieurs types de réseaux du monde réel peuvent être représentés par des graphes. Comme il s'agit de réseaux de très grande taille, leur topologie détaillée est généralement inconnue, et nous les modélisons par de grands graphes aléatoires ayant les mêmes propriétés statistiques locales que celles des réseaux observés. Un exemple de telle propriété est la présence de regroupements dans les réseaux réels : si deux individus ont un ami en commun, ils ont également tendance à être amis entre eux. Etudier des modèles de graphes aléatoires qui soient à la fois appropriés et faciles à aborder d'un point de vue mathématique représente un challenge, c'est pourquoi nous considérons plusieurs modèles de graphes aléatoires possédant ces propriétés. La propagation d'épidémies dans les graphes aléatoires peut être utilisée pour modéliser plusieurs types de phénomènes présents dans les réseaux réels, comme la propagation de maladies, ou la diffusion d'une nouvelle technologie. Le modèle épidémique que nous considérons dépend du phénomène que nous voulons représenter :. Un individu peut contracter une maladie par un simple contact avec un de ses amis (ces contacts étant indépendants),. Mais une nouvelle technologie est susceptible d'être adoptée par un individu lorsque beaucoup de ses amis ont déjà la technologie en question. Nous étudions essentiellement ces deux différents cas de figure. Dans chaque cas, nous cherchons à savoir si une faible proportion de la population initialement atteinte (ou ayant la technologie en question) peut propager l'épidémie à une grande partie de la population
Several kinds of real-world networks can be represented by graphs. Since such networks are very large, their detailed topology is generally unknown, and we model them by large random graphs having the same local statistical properties as the observed networks. An example of such properties is the fact that real-world networks are often highly clustered : if two individuals have a friend in common, they are likely to also be each other's friends. Studying random graph models that are both appropriate and tractable from a mathematical point of view is challenging, that is why we consider several clustered random graph models. The spread of epidemics in random graphs can be used to model several kinds of phenomena in real-world networks, as the spread of diseases, or the diffusion of a new technology. The epidemic model we consider depends on the phenomenon we wish to represent :. An individual can contract a disease by a single contact with any of his friends (such contacts being independent),. But a new technology is likely to be adopted by an individual if many of his friends already have the technology in question. We essentially study these two cases. In each case, one wants to know if a small proportion of the population initially infected (or having the technology in question) can propagate the epidemic to a large part of the population

APA, Harvard, Vancouver, ISO, and other styles

30

Lumbreras, Alberto. "Automatic role detection in online forums." Thesis, Lyon, 2016. http://www.theses.fr/2016LYSE2111/document.

Full text

Abstract:

Nous traitons dans cette thèse le problème de la détection des rôles des utilisateurs sur des forums de discussion en ligne. On peut détenir un rôle comme l'ensemble des comportements propres d'une personne ou d'une position. Sur les forums de discussion, les comportements sont surtout observés à travers des conversations. Pour autant, nous centrons notre attention sur la manière dont les utilisateurs dialoguent. Nous proposons trois méthodes pour détecter des groupes d'utilisateurs où les utilisateurs d'un même groupe dialoguent de façon similaire.Notre première méthode se base sur les structures des conversations dans lesquelles les utilisateurs participent. Nous appliquons des notions de voisinage différentes (radiusbased, order-based, and time-based) applicables aux commentaires qui sont représentés par des noeuds sur un arbre. Nous comparons les motifs de conversation qu'ils permettent de détecter ainsi que les groupes d'utilisateurs associés à des motifs similaires. Notre deuxième méthode se base sur des modèles stochastiques de croissance appliqués aux fils de discussion. Nous proposons une méthode pour trouver des groupes d'utilisateurs qui ont tendance à répondre au même type de commentaire. Nous montrons que, bien qu'il y ait des groupes d'utilisateurs avec des motifs de réponse similaires, il n'y a pas d'évidence forte qui confirme que ces comportements présentent des propriétés prédictives quant aux comportements futurs {sauf pour quelques groupes avec des comportements extrêmes. Avec notre troisième méthode nous intégrons les types de données utilisés dans les deux méthodes précédentes (feature-based et behavioral ou functional-based) et nous montrons que le modèle trouve des groupes en ayant besoin de moins d'observations. L'hypothèse du modèle est que les utilisateurs qui ont des caractéristiques similaires ont aussi des comportements similaires
This thesis addresses the problem of detecting user roles in online discussion forums. A role may be defined as the set of behaviors characteristic of a person or a position. In discussion forums, behaviors are primarily observed through conversations. Hence, we focus our attention on how users discuss. We propose three methods to detect groups of users with similar conversational behaviors.Our first method for the detection of roles is based on conversational structures. Weapply different notions of neighborhood for posts in tree graphs (radius-based, order-based, and time-based) and compare the conversational patterns that they detect as well as the clusters of users with similar conversational patterns.Our second method is based on stochastic models of growth for conversation threads.Building upon these models we propose a method to find groups of users that tend to reply to the same type of posts. We show that, while there are clusters of users with similar replying patterns, there is no strong evidence that these behaviors are predictive of future behaviors |except for some groups of users with extreme behaviors.In out last method, we integrate the type of data used in the two previous methods(feature-based and behavioral or functional-based) and show that we can find clusters using fewer examples. The model exploits the idea that users with similar features have similar behaviors

APA, Harvard, Vancouver, ISO, and other styles

31

Corneli, Marco. "Dynamic stochastic block models, clustering and segmentation in dynamic graphs." Thesis, Paris 1, 2017. http://www.theses.fr/2017PA01E012/document.

Full text

Abstract:

Cette thèse porte sur l’analyse de graphes dynamiques, définis en temps discret ou continu. Nous introduisons une nouvelle extension dynamique du modèle a blocs stochastiques (SBM), appelée dSBM, qui utilise des processus de Poisson non homogènes pour modéliser les interactions parmi les paires de nœuds d’un graphe dynamique. Les fonctions d’intensité des processus ne dépendent que des classes des nœuds comme dans SBM. De plus, ces fonctions d’intensité ont des propriétés de régularité sur des intervalles temporels qui sont à estimer, et à l’intérieur desquels les processus de Poisson redeviennent homogènes. Un récent algorithme d’estimation pour SBM, qui repose sur la maximisation d’un critère exact (ICL exacte) est ici adopté pour estimer les paramètres de dSBM et sélectionner simultanément le modèle optimal. Ensuite, un algorithme exact pour la détection de rupture dans les séries temporelles, la méthode «pruned exact linear time» (PELT), est étendu pour faire de la détection de rupture dans des données de graphe dynamique selon le modèle dSBM. Enfin, le modèle dSBM est étendu ultérieurement pour faire de l’analyse de réseau textuel dynamique. Les réseaux sociaux sont un exemple de réseaux textuels: les acteurs s’échangent des documents (posts, tweets, etc.) dont le contenu textuel peut être utilisé pour faire de la classification et détecter la structure temporelle du graphe dynamique. Le modèle que nous introduisons est appelé «dynamic stochastic topic block model» (dSTBM)
This thesis focuses on the statistical analysis of dynamic graphs, both defined in discrete or continuous time. We introduce a new extension of the stochastic block model (SBM) for dynamic graphs. The proposed approach, called dSBM, adopts non homogeneous Poisson processes to model the interaction times between pairs of nodes in dynamic graphs, either in discrete or continuous time. The intensity functions of the processes only depend on the node clusters, in a block modelling perspective. Moreover, all the intensity functions share some regularity properties on hidden time intervals that need to be estimated. A recent estimation algorithm for SBM, based on the greedy maximization of an exact criterion (exact ICL) is adopted for inference and model selection in dSBM. Moreover, an exact algorithm for change point detection in time series, the "pruned exact linear time" (PELT) method is extended to deal with dynamic graph data modelled via dSBM. The approach we propose can be used for change point analysis in graph data. Finally, a further extension of dSBM is developed to analyse dynamic net- works with textual edges (like social networks, for instance). In this context, the graph edges are associated with documents exchanged between the corresponding vertices. The textual content of the documents can provide additional information about the dynamic graph topological structure. The new model we propose is called "dynamic stochastic topic block model" (dSTBM).Graphs are mathematical structures very suitable to model interactions between objects or actors of interest. Several real networks such as communication networks, financial transaction networks, mobile telephone networks and social networks (Facebook, Linkedin, etc.) can be modelled via graphs. When observing a network, the time variable comes into play in two different ways: we can study the time dates at which the interactions occur and/or the interaction time spans. This thesis only focuses on the first time dimension and each interaction is assumed to be instantaneous, for simplicity. Hence, the network evolution is given by the interaction time dates only. In this framework, graphs can be used in two different ways to model networks. Discrete time […] Continuous time […]. In this thesis both these perspectives are adopted, alternatively. We consider new unsupervised methods to cluster the vertices of a graph into groups of homogeneous connection profiles. In this manuscript, the node groups are assumed to be time invariant to avoid possible identifiability issues. Moreover, the approaches that we propose aim to detect structural changes in the way the node clusters interact with each other. The building block of this thesis is the stochastic block model (SBM), a probabilistic approach initially used in social sciences. The standard SBM assumes that the nodes of a graph belong to hidden (disjoint) clusters and that the probability of observing an edge between two nodes only depends on their clusters. Since no further assumption is made on the connection probabilities, SBM is a very flexible model able to detect different network topologies (hubs, stars, communities, etc.)

APA, Harvard, Vancouver, ISO, and other styles

32

Venant, Fabienne. "Représentation et calcul dynamique du sens : exploration du lexique adjectival du français." Phd thesis, Ecole des Hautes Etudes en Sciences Sociales (EHESS), 2006. http://tel.archives-ouvertes.fr/tel-00067902.

Full text

Abstract:

Ce travail de thèse présente un modèle de construction du sens d'un genre nouveau, défini dans le cadre des mathématiques du continu. Le langage y est vu comme un système morphodynamique, obéissant aux principes de base de la Gestalttheorie. Les unités linguistiques découpent leur sens dans un espace sémantique possédant une structure de variété différentiable. Nous avons implémenté ce modèle et l'avons testé sur le lexique adjectival français. Une méthode de construction automatique des espaces sémantiques, reposant sur l'analyse d'un graphe de synonymie, permet d'explorer le lexique adjectival dans son ensemble, ou de construire des espaces locaux. Les espaces sémantiques locaux servent de base à une méthode dynamique de calcul du sens, permettant de prendre en compte les différents facteurs de polysémie adjectivale. L'utilisation des espaces sémantiques globaux ouvre de belles perspectives, tant dans le domaine du calcul du sens que celui de l'exploration de graphes petit monde.

APA, Harvard, Vancouver, ISO, and other styles

33

Hamidouche, Mounia. "Analyse spectrale de graphes géométriques aléatoires." Thesis, Université Côte d'Azur, 2020. http://www.theses.fr/2020COAZ4019.

Full text

Abstract:

Nous étudions le graphe géométrique aléatoire (GGA) afin d'aborder des problèmes clés dans les réseaux complexes. Un GAA est construit en distribuant uniformément n nœuds sur un tore de dimension d et en connectant deux nœuds si leur distance ne dépasse pas un seuil. Trois régimes pour GGA présentent un intérêt particulier. Le régime de connectivité dans lequel le degré moyen d'un nœud a_n croît de manière logarithmique avec n ou plus vite. Le régime dense dans lequel a_n est linéaire avec n. Le régime thermodynamique dans lequel a_n est une constante. On étudie le spectre du Laplacien normalisé (LN) et régularisé du GGA dans les trois régimes. Lorsque d est fixe et n tend vers l'infini, on prouve que la distribution spectrale limite (DSL) du LN converge vers la distribution de Dirac concentrée en 1 dans le régime de connectivité. Dans le régime thermodynamique, on propose une approximation pour DSL du LN régularisé et on fournit une borne d'erreur sur l'approximation. On montre que DSL du LN régularisé d'un GGA est approximée par DSL d'un graphe géométrique déterministe (GGD). On étudie DSL de la matrice d'adjacence d'un GGA dans le régime de connectivité. Sous des conditions sur a_n, on montre que DSL de la matrice d'adjacence du GGD est une bonne approximation du GGA pour n large. On détermine la dimension spectrale (DS) qui caractérise la distribution du temps de retour d'une marche aléatoire sur le GGA. On montre que DS dépend de la densité spectrale de LN au voisinage des valeurs propres minimales. On prouve que la densité spectrale au voisinage de la valeur minimale suit une loi de puissance et que DS du GGA est approximé par d dans le régime thermodynamique
We study random geometric graphs (RGGs) to address key problems in complex networks. An RGG is constructed by uniformly distributing n nodes on a torus of dimension d and connecting two nodes if their distance does not exceed a certain threshold. Three regimes for RGGs are of particular interest. The connectivity regime in which the average vertex degree a_n grows logarithmically with n or faster. The dense regime in which a_n is linear with n. The thermodynamic regime in which a_n is a constant. We study the spectrum of RGGs normalized Laplacian (LN) and its regularized version in the three regimes. When d is fixed and n tends to infinity we prove that the limiting spectral distribution (LSD) of LN converges to Dirac distribution at 1 in the connectivity regime. In the thermodynamic regime we propose an approximation for LSD of the regularized NL and we provide an error bound on the approximation. We show that LSD of the regularized LN of an RGG is approximated by LSD of the regularized LN of a deterministic geometric graph (DGG). We study LSD of RGGs adjacency matrix in the connectivity regime. Under some conditions on a_n we show that LSD of DGGs adjacency matrix is a good approximation for LSD of RGGs for n large. We determine the spectral dimension (SD) that characterizes the return time distribution of a random walk on RGGs. We show that SD depends on the eigenvalue density (ED) of the RGG normalized Laplacian in the neighborhood of the minimum eigenvalues. Based on the analytical eigenvalues of the normalized Laplacian we show that ED in a neighborhood of the minimum value follows a power-law tail and we approximate SD of RGGs by d in the thermodynamic regime

APA, Harvard, Vancouver, ISO, and other styles

34

Bourien, Jérôme. "Analyse de distributions spatio-temporelles de transitoires dans des signaux vectoriels. Application à la détection-classification d'activités paroxystiques intercritiques dans des observations EEG." Phd thesis, Université Rennes 1, 2003. http://tel.archives-ouvertes.fr/tel-00007178.

Full text

Abstract:

Les signaux électroencéphalographiques enregistrés chez les patients épileptiques reflètent, en dehors des périodes correspondant aux crises d'épilepsie, des signaux transitoires appelés "activités épileptiformes" (AE). L'analyse des AE peut contribuer à l'étude des épilepsies partielles pharmaco-résistantes. Une méthode de caractérisation de la dynamique spatio-temporelle des AE dans des signaux EEG de profondeur est présentée dans ce document. La méthode est constituée de quatre étapes:

1. Détection des AE monovoie. La méthode de détection, qui repose sur une approche heuristique, utilise un banc de filtres en ondelettes pour réhausser la composante pointue des AE (généralement appelée "spike" dans la littérature). La valeur moyenne des statistiques obtenues en sortie de chaque filtre est ensuite analysée avec un algorithme de Page-Hinkley dans le but de détecter des changements abrupts correspondant aux spikes.

2. Fusion des AE. Cette procédure recherche des co-occurrences entre AE monovoie à l'aide d'une fenêtre glissante puis forme des AE multivoies.

3. Extraction des sous-ensembles de voies fréquement et significativement activées lors des AE multivoies (appelés "ensembles d'activation").

4. Evaluation de l'éxistence d'un ordre d'activation temporel reproductible (éventuellement partiel) au sein de chaque ensemble d'activation.

Les méthodes proposées dans chacune des étapes ont tout d'abord été évaluées à l'aide de signaux simulés (étape 1) ou à l'aide de models Markoviens (étapes 2-4). Les résultats montrent que la méthode complète est robuste aux effets des fausses-alarmes. Cette méthode a ensuite été appliquée à des signaux enregistrés chez 8 patients (chacun contenant plusieurs centaines d'AE). Les résultats indiquent une grande reproductibilité des distributions spatio-temporelles des AE et ont permis l'identification de réseaux anatomo-fonctionnels spécifiques.

APA, Harvard, Vancouver, ISO, and other styles

35

Panafieu, Elie de. "Combinatoire analytique des graphes, hypergraphes et graphes inhomogènes." Paris 7, 2014. http://www.theses.fr/2014PA077167.

Full text

Abstract:

Nous étudions deux modèles qui généralisent la notion de graphe : les hypergraphes non-uniformes et les graphes inhomogènes. Ces modèles sont proches de ceux définis par Darling et Norris (2004) et Sôderberg (2002). Nous étudions leur énumération et leur structure typique avant et autour de la naissance de la composante géante. Nous montrons que les graphes inhomogènes sont un cadre idéal pour la modélisation de nombreux problèmes de satisfaction de contraintes (CSP) de complexité polynomiale, tels que la 2-colorabilité, la satisfaisabilité de formules 2- Xor et de formules 2-Xor quantifiées. Nous relions la probabilité de satisfaisabilité de ces problèmes à l'énumération des graphes inhomogènes. En application, plusieurs résultats de transition de phase anciens et nouveaux reçoivent une preuve dans un cadre unifié. Enfin, nous proposons une nouvelle preuve simple du nombre de multigraphes connexes possédant un nombre d'arêtes proportionnel au nombre de sommets, Ce résultat a été obtenu dans le cadre des graphes simples par Bender, Canfield et McKay (1990). L'outil principale de cette thèse est la combinatoire analytique, telle que définie par Flajolet et Sedgewick dans leur livre (2009)
We investigate two graph-like models: the non-uniform hypergraphs and the inhomogeneous graphs. They are close to the models defined by Darling and Norris (2004) and Sôderberg (2002). We enumerate them and derive structure information before and near the birth of the giant component. The inhomogeneous graph model proves to be a convenient framework for the modeling of several tractable constraint satisfaction problems (CSP), such as the 2-colorability problem, the satisfiability of 2-Xor formulas and of quantified 2-Xor formulas. We link the probability of satisfiability of those problems to the enumeration of inhomogeneous graphs. As an application, proofs of old and new phase transition results are derived in a unified framework. Finally, we derive a new simple proof for the asymptotic number of connected multigraphs with a number of edges proportional to the number of vertices. This result was first derived for simple graphs by Bender, Canfield and McKay (1990). The main tool of this thesis is analytic combinatorics, as defined by Flajolet and Sedgewick in their book (2009)

APA, Harvard, Vancouver, ISO, and other styles

36

Zaylaa, Amira. "Analyse et extraction de paramètres de complexité de signaux biomédicaux." Thesis, Tours, 2014. http://www.theses.fr/2014TOUR3315/document.

Full text

Abstract:

L'analyse de séries temporelles biomédicales chaotiques tirées de systèmes dynamiques non-linéaires est toujours un challenge difficile à relever puisque dans certains cas bien spécifiques les techniques existantes basées sur les multi-fractales, les entropies et les graphes de récurrence échouent. Pour contourner les limitations des invariants précédents, de nouveaux descripteurs peuvent être proposés. Dans ce travail de recherche nos contributions ont porté à la fois sur l’amélioration d’indicateurs multifractaux (basés sur une fonction de structure) et entropiques (approchées) mais aussi sur des indicateurs de récurrences (non biaisés). Ces différents indicateurs ont été développés avec pour objectif majeur d’améliorer la discrimination entre des signaux de complexité différente ou d’améliorer la détection de transitions ou de changements de régime du système étudié. Ces changements agissant directement sur l’irrégularité du signal, des mouvements browniens fractionnaires et des signaux tirés du système du Lorenz ont été testés. Ces nouveaux descripteurs ont aussi été validés pour discriminer des fœtus en souffrance de fœtus sains durant le troisième trimestre de grossesse. Des mesures statistiques telles que l’erreur relative, l’écart type, la spécificité, la sensibilité ou la précision ont été utilisées pour évaluer les performances de la détection ou de la classification. Le fort potentiel de ces nouveaux invariants nous laisse penser qu’ils pourraient constituer une forte valeur ajoutée dans l’aide au diagnostic s’ils étaient implémentés dans des logiciels de post-traitement ou dans des dispositifs biomédicaux. Enfin, bien que ces différentes méthodes aient été validées exclusivement sur des signaux fœtaux, une future étude incluant des signaux tirés d’autres systèmes dynamiques nonlinéaires sera réalisée pour confirmer leurs bonnes performances
The analysis of biomedical time series derived from nonlinear dynamic systems is challenging due to the chaotic nature of these time series. Only few classical parameters can be detected by clinicians to opt the state of patients and fetuses. Though there exist valuable complexity invariants such as multi-fractal parameters, entropies and recurrence plot, they were unsatisfactory in certain cases. To overcome this limitation, we propose in this dissertation new entropy invariants, we contributed to multi-fractal analysis and we developed signal-based (unbiased) recurrence plots based on the dynamic transitions of time series. Principally, we aim to improve the discrimination between healthy and distressed biomedical systems, particularly fetuses by processing the time series using our techniques. These techniques were either validated on Lorenz system, logistic maps or fractional Brownian motions modeling chaotic and random time series. Then the techniques were applied to real fetus heart rate signals recorded in the third trimester of pregnancy. Statistical measures comprising the relative errors, standard deviation, sensitivity, specificity, precision or accuracy were employed to evaluate the performance of detection. Elevated discernment outcomes were realized by the high-order entropy invariants. Multi-fractal analysis using a structure function enhances the detection of medical fetal states. Unbiased cross-determinism invariant amended the discrimination process. The significance of our techniques lies behind their post-processing codes which could build up cutting-edge portable machines offering advanced discrimination and detection of Intrauterine Growth Restriction prior to fetal death. This work was devoted to Fetal Heart Rates but time series generated by alternative nonlinear dynamic systems should be further considered

APA, Harvard, Vancouver, ISO, and other styles

37

Dao, Ngoc Bich. "Réduction de dimension de sac de mots visuels grâce à l’analyse formelle de concepts." Thesis, La Rochelle, 2017. http://www.theses.fr/2017LAROS010/document.

Full text

Abstract:

La réduction des informations redondantes et/ou non-pertinentes dans la description de données est une étape importante dans plusieurs domaines scientifiques comme les statistiques, la vision par ordinateur, la fouille de données ou l’apprentissage automatique. Dans ce manuscrit, nous abordons la réduction de la taille des signatures des images par une méthode issue de l’Analyse Formelle de Concepts (AFC), qui repose sur la structure du treillis des concepts et la théorie des treillis. Les modèles de sac de mots visuels consistent à décrire une image sous forme d’un ensemble de mots visuels obtenus par clustering. La réduction de la taille des signatures des images consiste donc à sélectionner certains de ces mots visuels. Dans cette thèse, nous proposons deux algorithmes de sélection d’attributs (mots visuels) qui sont utilisables pour l’apprentissage supervisé ou non. Le premier algorithme, RedAttSansPerte, ne retient que les attributs qui correspondent aux irréductibles du treillis. En effet, le théorème fondamental de la théorie des treillis garantit que la structure du treillis des concepts est maintenue en ne conservant que les irréductibles. Notre algorithme utilise un graphe d’attributs, le graphe de précédence, où deux attributs sont en relation lorsque les ensembles d’objets à qui ils appartiennent sont inclus l’un dans l’autre. Nous montrons par des expérimentations que la réduction par l’algorithme RedAttsSansPerte permet de diminuer le nombre d’attributs tout en conservant de bonnes performances de classification. Le deuxième algorithme, RedAttsFloue, est une extension de l’algorithme RedAttsSansPerte. Il repose sur une version approximative du graphe de précédence. Il s’agit de supprimer les attributs selon le même principe que l’algorithme précédent, mais en utilisant ce graphe flou. Un seuil de flexibilité élevé du graphe flou entraîne mécaniquement une perte d’information et de ce fait une baisse de performance de la classification. Nous montrons par des expérimentations que la réduction par l’algorithme RedAttsFloue permet de diminuer davantage l’ensemble des attributs sans diminuer de manière significative les performances de classification
In several scientific fields such as statistics, computer vision and machine learning, redundant and/or irrelevant information reduction in the data description (dimension reduction) is an important step. This process contains two different categories : feature extraction and feature selection, of which feature selection in unsupervised learning is hitherto an open question. In this manuscript, we discussed about feature selection on image datasets using the Formal Concept Analysis (FCA), with focus on lattice structure and lattice theory. The images in a dataset were described as a set of visual words by the bag of visual words model. Two algorithms were proposed in this thesis to select relevant features and they can be used in both unsupervised learning and supervised learning. The first algorithm was the RedAttSansPerte, which based on lattice structure and lattice theory, to ensure its ability to remove redundant features using the precedence graph. The formal definition of precedence graph was given in this thesis. We also demonstrated their properties and the relationship between this graph and the AC-poset. Results from experiments indicated that the RedAttsSansPerte algorithm reduced the size of feature set while maintaining their performance against the evaluation by classification. Secondly, the RedAttsFloue algorithm, an extension of the RedAttsSansPerte algorithm, was also proposed. This extension used the fuzzy precedence graph. The formal definition and the properties of this graph were demonstrated in this manuscript. The RedAttsFloue algorithm removed redundant and irrelevant features while retaining relevant information according to the flexibility threshold of the fuzzy precedence graph. The quality of relevant information was evaluated by the classification. The RedAttsFloue algorithm is suggested to be more robust than the RedAttsSansPerte algorithm in terms of reduction

APA, Harvard, Vancouver, ISO, and other styles

38

Kassel, Adrien. "Laplaciens des graphes sur les surfaces et applications à la physique statistique." Thesis, Paris 11, 2013. http://www.theses.fr/2013PA112101.

Full text

Abstract:

Nous étudions le déterminant du laplacien sur les fibrés vectoriels sur les graphes et l'utilisons, en lien avec des techniques d'analyse complexe discrète, pour comprendre des modèles de physique statistique. Nous calculons certaines constantes de réseaux, construisons des limites d'échelles d'excursions de la marche aléatoire à boucles effacées sur les surfaces, et étudions certains champs gaussiens et processus déterminantaux
We study the determinant of the Laplacian on vector bundles on graphs and use it, combined with discrete complex analysis, to study models of statistical physics. We compute exact lattice constants, construct scaling limits for excursions of the loop-erased random walk on surfaces, and study some Gaussian fields and determinantal processes

APA, Harvard, Vancouver, ISO, and other styles

39

Calandriello, Daniele. "Efficient sequential learning in structured and constrained environments." Thesis, Lille 1, 2017. http://www.theses.fr/2017LIL10216/document.

Full text

Abstract:

L'avantage principal des méthodes d'apprentissage non-paramétriques réside dans le fait que la nombre de degrés de libertés du modèle appris s'adapte automatiquement au nombre d'échantillons. Ces méthodes sont cependant limitées par le "fléau de la kernelisation": apprendre le modèle requière dans un premier temps de construire une matrice de similitude entre tous les échantillons. La complexité est alors quadratique en temps et espace, ce qui s'avère rapidement trop coûteux pour les jeux de données de grande dimension. Cependant, la dimension "effective" d'un jeu de donnée est bien souvent beaucoup plus petite que le nombre d'échantillons lui-même. Il est alors possible de substituer le jeu de donnée réel par un jeu de données de taille réduite (appelé "dictionnaire") composé exclusivement d'échantillons informatifs. Malheureusement, les méthodes avec garanties théoriques utilisant des dictionnaires comme "Ridge Leverage Score" (RLS) ont aussi une complexité quadratique. Dans cette thèse nous présentons une nouvelle méthode d'échantillonage RLS qui met à jour le dictionnaire séquentiellement en ne comparant chaque nouvel échantillon qu'avec le dictionnaire actuel, et non avec l'ensemble des échantillons passés. Nous montrons que la taille de tous les dictionnaires ainsi construits est de l'ordre de la dimension effective du jeu de données final, garantissant ainsi une complexité en temps et espace à chaque étape indépendante du nombre total d'échantillons. Cette méthode présente l’avantage de pouvoir être parallélisée. Enfin, nous montrons que de nombreux problèmes d'apprentissage non-paramétriques peuvent être résolus de manière approchée grâce à notre méthode
The main advantage of non-parametric models is that the accuracy of the model (degrees of freedom) adapts to the number of samples. The main drawback is the so-called "curse of kernelization": to learn the model we must first compute a similarity matrix among all samples, which requires quadratic space and time and is unfeasible for large datasets. Nonetheless the underlying effective dimension (effective d.o.f.) of the dataset is often much smaller than its size, and we can replace the dataset with a subset (dictionary) of highly informative samples. Unfortunately, fast data-oblivious selection methods (e.g., uniform sampling) almost always discard useful information, while data-adaptive methods that provably construct an accurate dictionary, such as ridge leverage score (RLS) sampling, have a quadratic time/space cost. In this thesis we introduce a new single-pass streaming RLS sampling approach that sequentially construct the dictionary, where each step compares a new sample only with the current intermediate dictionary and not all past samples. We prove that the size of all intermediate dictionaries scales only with the effective dimension of the dataset, and therefore guarantee a per-step time and space complexity independent from the number of samples. This reduces the overall time required to construct provably accurate dictionaries from quadratic to near-linear, or even logarithmic when parallelized. Finally, for many non-parametric learning problems (e.g., K-PCA, graph SSL, online kernel learning) we we show that we can can use the generated dictionaries to compute approximate solutions in near-linear that are both provably accurate and empirically competitive

APA, Harvard, Vancouver, ISO, and other styles

40

Wehbe, Diala. "Simulations and applications of large-scale k-determinantal point processes." Thesis, Lille 1, 2019. http://www.theses.fr/2019LIL1I012/document.

Full text

Abstract:

Avec la croissance exponentielle de la quantité de données, l’échantillonnage est une méthode pertinente pour étudier les populations. Parfois, nous avons besoin d’échantillonner un grand nombre d’objets d’une part pour exclure la possibilité d’un manque d’informations clés et d’autre part pour générer des résultats plus précis. Le problème réside dans le fait que l’échantillonnage d’un trop grand nombre d’individus peut constituer une perte de temps.Dans cette thèse, notre objectif est de chercher à établir des ponts entre la statistique et le k-processus ponctuel déterminantal(k-DPP) qui est défini via un noyau. Nous proposons trois projets complémentaires pour l’échantillonnage de grands ensembles de données en nous basant sur les k-DPPs. Le but est de sélectionner des ensembles variés qui couvrent un ensemble d’objets beaucoup plus grand en temps polynomial. Cela peut être réalisé en construisant différentes chaînes de Markov où les k-DPPs sont les lois stationnaires.Le premier projet consiste à appliquer les processus déterminantaux à la sélection d’espèces diverses dans un ensemble d’espèces décrites par un arbre phylogénétique. En définissant le noyau du k-DPP comme un noyau d’intersection, les résultats fournissent une borne polynomiale sur le temps de mélange qui dépend de la hauteur de l’arbre phylogénétique.Le second projet vise à utiliser le k-DPP dans un problème d’échantillonnage de sommets sur un graphe connecté de grande taille. La pseudo-inverse de la matrice Laplacienne normalisée est choisie d’étudier la vitesse de convergence de la chaîne de Markov créée pour l’échantillonnage de la loi stationnaire k-DPP. Le temps de mélange résultant est borné sous certaines conditions sur les valeurs propres de la matrice Laplacienne.Le troisième sujet porte sur l’utilisation des k-DPPs dans la planification d’expérience avec comme objets d’étude plus spécifiques les hypercubes latins d’ordre n et de dimension d. La clé est de trouver un noyau positif qui préserve le contrainte de ce plan c’est-à-dire qui préserve le fait que chaque point se trouve exactement une fois dans chaque hyperplan. Ensuite, en créant une nouvelle chaîne de Markov dont le n-DPP est sa loi stationnaire, nous déterminons le nombre d’étapes nécessaires pour construire un hypercube latin d’ordre n selon le n-DPP
With the exponentially growing amount of data, sampling remains the most relevant method to learn about populations. Sometimes, larger sample size is needed to generate more precise results and to exclude the possibility of missing key information. The problem lies in the fact that sampling large number may be a principal reason of wasting time.In this thesis, our aim is to build bridges between applications of statistics and k-Determinantal Point Process(k-DPP) which is defined through a matrix kernel. We have proposed different applications for sampling large data sets basing on k-DPP, which is a conditional DPP that models only sets of cardinality k. The goal is to select diverse sets that cover a much greater set of objects in polynomial time. This can be achieved by constructing different Markov chains which have the k-DPPs as their stationary distribution.The first application consists in sampling a subset of species in a phylogenetic tree by avoiding redundancy. By defining the k-DPP via an intersection kernel, the results provide a fast mixing sampler for k-DPP, for which a polynomial bound on the mixing time is presented and depends on the height of the phylogenetic tree.The second application aims to clarify how k-DPPs offer a powerful approach to find a diverse subset of nodes in large connected graph which authorizes getting an outline of different types of information related to the ground set. A polynomial bound on the mixing time of the proposed Markov chain is given where the kernel used here is the Moore-Penrose pseudo-inverse of the normalized Laplacian matrix. The resulting mixing time is attained under certain conditions on the eigenvalues of the Laplacian matrix. The third one purposes to use the fixed cardinality DPP in experimental designs as a tool to study a Latin Hypercube Sampling(LHS) of order n. The key is to propose a DPP kernel that establishes the negative correlations between the selected points and preserve the constraint of the design which is strictly confirmed by the occurrence of each point exactly once in each hyperplane. Then by creating a new Markov chain which has n-DPP as its stationary distribution, we determine the number of steps required to build a LHS with accordance to n-DPP

APA, Harvard, Vancouver, ISO, and other styles

41

Jourdan-Marias, Astrid. "Analyse statistique et échantillonage d'expériences simulées." Pau, 2000. http://www.theses.fr/2000PAUU1014.

Full text

Abstract:

De nombreux phénomènes physiques sont étudiés à l'aide de simulateurs très complexes et coûteux. Bien souvent, l'utilisateur souhaite alors disposer d'un modèle simple et rapide afin de résumer la réponse du simulateur. Il est alors nécessaire de construire un prédicteur de la réponse du code informatique à partir d'un petit nombre de simulations, que l'on appelle encore expérience simulées. A l'heure actuelle il existe 2 principales approches statistiques des expériences simulées, l'une est basée sur un modèle spatial adapté du modèle géo-statistique de krigeage, et l'autre est basée sur des techniques d'échantillonage. Chacune d'elle présente des avantages mais aussi des inconvénients. Ce travail propose une nouvelle approche statistique plus performante des exprériences simulées qui intègre les points forts des 2 approches existantes, i, e. . .

APA, Harvard, Vancouver, ISO, and other styles

42

Mahé, Cédric. "Analyse statistique de delais d'evenement correles." Paris 7, 1998. http://www.theses.fr/1998PA077254.

Full text

Abstract:

Les delais d'evenement correles sont frequemment observes dans les etudes longitudinales lorsque plus d'un evenement peut survenir chez un individu ou lorsqu'un evenement survient chez des individus regroupes en cluster. La prise en compte de la dependance entre les delais d'evenements de la meme unite statistique (l'individu ou le cluster) est necessaire pour une estimation precise et non biaisee de l'effet des covariables sur le risque d'evenement. Pour les evenements non ordonnes, un modele combinant deux generalisations multivariees du modele de cox a ete developpe afin d'estimer un effet moyen des covariables sur le risque d'evenement ainsi que la force de correlation au sein de l'unite statistique. Ce modele a ensuite ete applique a une etude de cohorte expose-non expose. Pour les evenements ordonnes (recurrents), l'apport des methodes qui prennent en compte la correlation des delais a ete presente de facon didactique. D'autre part, dans le cadre des approches multivariees, le choix de la mesure de reponse adequate a ete discute selon la structure des donnees. L'extension de ces methodes a un critere de jugement combinant les deux types d'evenements ordonnes et non ordonnes necessite des developpements ulterieurs.

APA, Harvard, Vancouver, ISO, and other styles

43

Godard, Emmanuel. "Réécritures de graphes et algorithmique distribuée." Bordeaux 1, 2002. http://www.theses.fr/2002BOR12518.

Full text

Abstract:

Un système distribué peut être représenté par un graphe étiqueté : les sommets correspondent aux processeurs, les arêtes aux liens de communication et les étiquettes associées aux sommets codent les états des processeurs. Un algorithme distribué est alors décrit par un système de règles de transition locale où l'étiquette suivante d'un sommet est fonction de son étiquette actuelle et de celles de ses voisins (réétiquetage local). Les réétiquetages opérant sur des voisinages disjoints se déroulent en parallèle, de manière asynchrone. Dans ce cadre, on étudie la réalisabilité et non-réalisabilité des tâches distribuées. Nous illustrerons notre méthode en nous intéressant en particulier à certains problèmes spécifiques aux systèmes distribués (élection d'un noeud, reconnaissance de certaines propriétés topologiques du graphe sous-jacent au réseau, calcul de métriques du réseau comme par exemple la taille ou le diamètre). Dans tous ces cas, on présente une caractérisation complète de ce qui est réalisable par calcul distribué en fonction de la topologie du graphe sous-jacent mais également du degré de connaissance qu'a le réseau sur lui-même ("connaissance structurelle"). Ces conditions nécessaires et suffisantes sont principalement exprimées en termes de fermetures par s̀̀imilarités'' des familles de réseaux considérées. Ces s̀̀imilarités'' sont décrites de manière combinatoire à l'aide de morphismes de graphes particuliers : les revêtements et les quasi-revêtements. Les preuves des conditions nécessaires emploient des techniques de simulation à base de revêtements et quasi-revêtements. Les algorithmes distribués présentés pour les preuves des conditions suffisantes se fondent essentiellement sur un algorithme de cartographie du réseau sous-jacent. Celui-ci est construit à partir des extensions d'un algorithme d'énumération de A. Mazurkiewicz et d'un algorithme de détection des propriétés stables de Shy, Szymanski et Prywes.

APA, Harvard, Vancouver, ISO, and other styles

44

Cigana, John. "Analyse statistique de sensibilité du modèle SANCHO." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk2/ftp01/MQ38667.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Célimène, Fred. "Analyse statistique et économétrique des DOM-TOM." Paris 10, 1985. http://www.theses.fr/1985PA100002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Olivier, Adelaïde. "Analyse statistique des modèles de croissance-fragmentation." Thesis, Paris 9, 2015. http://www.theses.fr/2015PA090047/document.

Full text

Abstract:

Cette étude théorique est pensée en lien étroit avec un champ d'application : il s'agit de modéliser la croissance d'une population de cellules qui se divisent selon un taux de division inconnu, fonction d’une variable dite structurante – l’âge et la taille des cellules étant les deux exemples paradigmatiques étudiés. Le champ mathématique afférent se situe à l'interface de la statistique des processus, de l’estimation non-paramétrique et de l’analyse des équations aux dérivées partielles. Les trois objectifs de ce travail sont les suivants : reconstruire le taux de division (fonction de l’âge ou de la taille) pour différents schémas d’observation (en temps généalogique ou en temps continu) ; étudier la transmission d'un trait biologique général d'une cellule à une autre et étudier le trait d’une cellule typique ; comparer la croissance de différentes populations de cellules à travers le paramètre de Malthus (après introduction de variabilité dans le taux de croissance par exemple)
This work is concerned with growth-fragmentation models, implemented for investigating the growth of a population of cells which divide according to an unknown splitting rate, depending on a structuring variable – age and size being the two paradigmatic examples. The mathematical framework includes statistics of processes, nonparametric estimations and analysis of partial differential equations. The three objectives of this work are the following : get a nonparametric estimate of the division rate (as a function of age or size) for different observation schemes (genealogical or continuous) ; to study the transmission of a biological feature from one cell to an other and study the feature of one typical cell ; to compare different populations of cells through their Malthus parameter, which governs the global growth (when introducing variability in the growth rate among cells for instance)

APA, Harvard, Vancouver, ISO, and other styles

47

Goulard, Michel. "Champs spatiaux et statistique multidimensionnelle." Grenoble 2 : ANRT, 1988. http://catalogue.bnf.fr/ark:/12148/cb376138909.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Mostefaoui, Mustapha. "Analyse des propriétés temporelles des graphes d'événements valués continus." Nantes, 2001. http://www.theses.fr/2001NANT2100.

Full text

Abstract:

Les réseaux de Petri (RdP) sont un formalisme puissant de modélisation et d'évaluation des systèmes dynamiques complexes. Une classe particulière des RdP, que sont les graphes d'événements valués (GdEV) fortement connexes, permet plus particulièrement d'analyser les systèmes cycliques sans conflit structurel. Lorsque la notion de flux apparaît (système fluide, structure à haut débit, etc. ) il est possible d'utiliser un modèle GdEV continu (GdEVC). Le plus souvent, les méthodes d'analyse des propriétés temporelles des RdP continus se basent sur le développement du graphe d'évolution qui représente la dynamique du système. . .

APA, Harvard, Vancouver, ISO, and other styles

49

Albano, Alice. "Dynamique des graphes de terrain : analyse en temps intrinsèque." Thesis, Paris 6, 2014. http://www.theses.fr/2014PA066260/document.

Full text

Abstract:

Nous sommes entourés par une multitude de réseaux d'interactions, issus de contextes très différents. Ces réseaux peuvent être modélisés par des graphes, appelés graphes de terrain. Ils possèdent une structure en communautés, c'est-à-dire en groupes de nœuds très liés entre eux, et peu liés avec les autres. Un phénomène que l'on étudie sur les graphes dans de nombreux contextes est la diffusion. La propagation d'une maladie en est un exemple. Ces phénomènes dépendent d'un paramètre important, mais souvent peu étudié : l'échelle de temps selon laquelle on les observe. Selon l'échelle choisie, la dynamique du graphe peut varier de manière très importante.Dans cette thèse, nous proposons d'étudier des processus dynamiques en utilisant une échelle de temps adaptée. Nous considérons une notion de temps relatif, que nous appelons le temps intrinsèque, par opposition au temps "classique", que nous appelons temps extrinsèque. Nous étudions en premier lieu des phénomènes de diffusion selon une échelle de temps intrinsèque, et nous comparons les résultats obtenus avec une échelle extrinsèque. Ceci nous permet de mettre en évidence le fait qu'un même phénomène observé dans deux échelles de temps différentes puisse présenter un comportement très différent. Nous analysons ensuite la pertinence de l'utilisation du temps intrinsèque pour la détection de communautés dynamiques. Les communautés obtenues selon les échelles de temps extrinsèques et intrinsèques nous montrent qu'une échelle intrinsèque permet la détection de communautés beaucoup plus significatives et détaillées que l'échelle extrinsèque
We are surrounded by a multitude of interaction networks from different contexts. These networks can be modeled as graphs, called complex networks. They have a community structure, i.e. groups of nodes closely related to each other and less connected with the rest of the graph. An other phenomenon studied in complex networks in many contexts is diffusion. The spread of a disease is an example of diffusion. These phenomena are dynamic and depend on an important parameter, which is often little studied: the time scale in which they are observed. According to the chosen scale, the graph dynamics can vary significantly. In this thesis, we propose to study dynamic processes using a suitable time scale. We consider a notion of relative time which we call intrinsic time, opposed to "traditional" time, which we call extrinsic time. We first study diffusion phenomena using intrinsic time, and we compare our results with an extrinsic time scale. This allows us to highlight the fact that the same phenomenon observed at two different time scales can have a very different behavior. We then analyze the relevance of the use of intrinsic time scale for detecting dynamic communities. Comparing communities obtained according extrinsic and intrinsic scales shows that the intrinsic time scale allows a more significant detection than extrinsic time scale

APA, Harvard, Vancouver, ISO, and other styles

50

Rivoire, Olivier. "Phases vitreuses, optimisation et grandes déviations." Phd thesis, Université Paris Sud - Paris XI, 2005. http://tel.archives-ouvertes.fr/tel-00009956.

Full text

Abstract:

Les problèmes d'optimisation combinatoires définis sur graphes aléatoires sont au coeur de la théorie de la complexité algorithmique. Ils sont également étroitement liés à une formulation champ moyen, dite approximation de Bethe, de modèles sur réseau de verres de spins et verres structuraux. Cette thèse s'appuie sur ce parallèle pour appliquer à des problèmes d'optimisation une approche issue de la physique statistique des systèmes désordonnés, la méthode de la cavité. Etant donné un ensemble d'entrées (instances) d'un problème d'optimisation, cette méthode permet de déterminer les propriétés des solutions des instances typiques, ainsi que celles des instances atypiques, dont les probabilités sont exponentiellement petites (grandes déviations sur la structure externe). Pour une instance donnée, la méthode de la cavité donne également accès à la thermodynamique des différentes solutions admissibles (grandes déviations sur la structure interne). D'un point de vue physique, de nombreux problèmes algorithmiquement difficiles se révèlent ainsi posséder une phase de type verre. Cette thèse est composée de trois parties destinées à exposer les principes, applications et limitations de la méthode de la cavité. La première partie rappelle, dans la perspective des grandes déviations, les liens entre physique statistique et optimisation combinatoire. La deuxième partie aborde les modèles définis sur graphes aléatoires et, pour différents ensembles de graphes, analyse les propriétés typiques et atypiques de ces modèles. La troisième partie est consacrée aux grandes déviations sur le "désordre interne", constitué par les solutions et quasi-solutions d'une instance donnée. Une attention particulière est dévolue au traitement des phases vitreuses où l'ensemble des solutions est fragmenté en un nombre exponentiel d'amas disjoints (structure dite à un pas de brisure de symétrie des répliques); il est montré comment la méthode de la cavité fournit dans de tels cas une description fine des propriétés géométriques de l'espace des solutions.

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Analyse statistique de graphes'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles