Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Avec l’informatisation accrue de toutes les sphères d’activités de la société, nous assistons de nos jours à une explosion de la quantité de données électroniques existantes. C’est pourquoi, nous devons avoir recours à des outils automatiques qui sont à même d’analyser automatiquement les données et de ne nous fournir que l’information pertinente et résumée par rapport à ce qui est recherché. Les techniques de forage de données sont généralement utilisées à cette fin. Cependant, ces dernières nécessitent généralement un temps de calcul considérable afin d’analyser un large volume de données. Par ailleurs, si les données sont géographiquement distribuées, les regrouper sur un même site pour y créer un modèle (un classificateur par exemple) peut s’avérer très coûteux. Pour résoudre ce problème, nous proposons de construire plusieurs modèles, et plus précisément plusieurs classificateurs, soit un classificateur par site. Ensuite, les règles constituant ces classificateurs sont regroupées puis filtrées en se basant sur certaines mesures statistiques et une validation effectuée à partir de très petits échantillons provenant de chacun des sites. Le modèle résultant, appelé méta-classificateur, est, d’une part, un outil de prédiction pour toute nouvelle instance et, d’autre part, une vue abstraite de tout l’ensemble de données. Nous basons notre approche de filtrage de règles de classification sur une mesure de confiance associée à chaque règle qui est calculée statistiquement et validée en utilisant les échantillons recueillis. Nous avons considéré plusieurs techniques de validation tel qu’il sera présenté dans cette thèse. / With the pervasive use of computers in all spheres of activity in our society, we are faced nowadays with the explosion of electronic data. This is why we need automatic tools that are able to automatically analyze the data in order to provide us with relevant and summarized information with respect to some query. For this task, data mining techniques are generally used. However, these techniques require considerable computing time in order to analyze a huge volume of data. Moreover, if the data is geographically distributed, gathering it on the same site in order to create a model (a classifier for instance) could be time consuming. To solve this problem, we propose to build several models, that is one classifier by site. Then, rules constituting these classifiers are aggregated and filtered based on some statistical measures, and a validation process is carried out on samples from each site. The resulting model, called a metaclassifier is, on one hand, a prediction tool for any new (unseen) instance and, on the other hand, an abstract view of the whole data set. We base our rule filtering approach on a confidence measure associated with each rule, which is computed statistically and then validated using the data samples (one from each site). We considered several validation techniques such as will be discussed in this thesis.

Le recours aux données géographiques issues des macro-observatoires s’impose comme la solution incontournable pour les agences de développement et bailleurs de fonds internationaux en quête de données structurées et facilement accessibles. Ces données sont pourtant conçues selon une vision globalisante qui ne reflète pas ou pas suffisamment les contextes spécifiques locaux sur lesquels ces acteurs doivent intervenir. Dans les pays du Sud en particulier, les savoirs géographiques locaux constituent le plus souvent la seule source de données terrain disponible. Mais leur fiabilité et leur utilité sont souvent questionnées, en comparaison des données statistiques ou cartographiques des macro-observatoires. En effet, ils ne sont que peu ou pas formalisés. Ils nécessitent des processus de collecte de terrain complexes à mettre en œuvre. Leur interprétation est souvent difficile, en particulier pour les acteurs occidentaux. Ce travail de recherche a pour objectif la conception d’un cadre d’intégration des savoirs géographiques locaux dans les macro-observatoires. Il repose concrètement sur l’observation, l’analyse et la mise en relief des points communs et des différences des deux types de savoirs géographiques, à partir du cas de la région de DIANA à Madagascar; et plus précisément des savoirs locaux issues d’une démarche de Zonage À Dire d’Acteurs (ZADA) et des données globales de l’observatoire « Harvest Choice » de l’International Food Policy Research Institute (IFPRI). Mots-clés : Macro-observatoires, données locales, données globales, infrastructure de données spatiales, intégration des données, connaissances locales, connaissances experts, SIG.

L'objectif de ce mémoire est d'introduire le lecteur à la compression de données générale et sans perte et de présenter deux nouvelles techniques que nous avons développées et implantées afin de contribuer au domaine. La première technique que nous avons développée est le recyclage de bits et elle a pour objectif de réduire la taille des fichiers compressés en profitant du fait que plusieurs techniques de compression de données ont la particularité de pouvoir produire plusieurs fichiers compressés différents à partir d'un même document original. La multiplicité des encodages possibles pour un même fichier compressé cause de la redondance. Nous allons démontrer qu'il est possible d'utiliser cette redondance pour diminuer la taille des fichiers compressés. La deuxième technique que nous avons développée est en fait une méthode qui repose sur l'énumération des sous-chaînes d'un fichier à compresser. La méthode est inspirée de la famille des méthodes PPM (prediction by partial matching). Nous allons montrer comment la méthode fonctionne sur un fichier à compresser et nous allons analyser les résultats que nous avons obtenus empiriquement.

Les nouvelles technologies «omiques» à haut débit, incluant la génomique, l'épigénomique, la transcriptomique, la protéomique, la métabolomique ou encore la métagénomique, ont connues ces dernières années un développement considérable. Indépendamment, chaque technologie omique est une source d'information incontournable pour l'étude du génome humain, de l'épigénome, du transcriptome, du protéome, du métabolome, et également de son microbiote permettant ainsi d'identifier des biomarqueurs responsables de maladies, de déterminer des cibles thérapeutiques, d'établir des diagnostics préventifs et d'accroître les connaissances du vivant. La réduction des coûts et la facilité d'acquisition des données multi-omiques à permis de proposer de nouveaux plans expérimentaux de type série temporelle où le même échantillon biologique est séquencé, mesuré et quantifié à plusieurs temps de mesures. Grâce à l'étude combinée des technologies omiques et des séries temporelles, il est possible de capturer les changements d'expressions qui s'opèrent dans un système dynamique pour chaque molécule et avoir une vision globale des interactions multi-omiques, inaccessibles par une approche simple standard. Cependant le traitement de cette somme de connaissances multi-omiques fait face à de nouveaux défis : l'évolution constante des technologies, le volume des données produites, leur hétérogénéité, la variété des données omiques et l'interprétabilité des résultats d'intégration nécessitent de nouvelles méthodes d'analyses et des outils innovants, capables d'identifier les éléments utiles à travers cette multitude d'informations. Dans cette perspective, nous proposons plusieurs outils et méthodes pour faire face aux challenges liés à l'intégration et l'interprétation de ces données multi-omiques particulières. Enfin, l'intégration de données multi-omiques longitudinales offre des perspectives dans des domaines tels que la médecine de précision ou pour des applications environnementales et industrielles. La démocratisation des analyses multi-omiques et la mise en place de méthodes d'intégration et d'interprétation innovantes permettront assurément d'obtenir une meilleure compréhension des écosystèmes biologiques. / New high-throughput «omics» technologies, including genomics, epigenomics, transcriptomics, proteomics, metabolomics and metagenomics, have expanded considerably in recent years. Independently, each omics technology is an essential source of knowledge for the study of the human genome, epigenome, transcriptome, proteome, metabolome, and also its microbiota, thus making it possible to identify biomarkers leading to diseases, to identify therapeutic targets, to establish preventive diagnoses and to increase knowledge of living organisms. Cost reduction and ease of multi-omics data acquisition resulted in new experimental designs based on time series in which the same biological sample is sequenced, measured and quantified at several measurement times. Thanks to the combined study of omics technologies and time series, it is possible to capture the changes in expression that take place in a dynamic system for each molecule and get a comprehensive view of the multi-omics interactions, which was inaccessible with a simple standard omics approach. However, dealing with this amount of multi-omics data faces new challenges: continuous technological evolution, large volumes of produced data, heterogeneity, variety of omics data and interpretation of integration results require new analysis methods and innovative tools, capable of identifying useful elements through this multitude of information. In this perspective, we propose several tools and methods to face the challenges related to the integration and interpretation of these particular multi-omics data. Finally, integration of longidinal multi-omics data offers prospects in fields such as precision medicine or for environmental and industrial applications. Democratisation of multi-omics analyses and the implementation of innovative integration and interpretation methods will definitely lead to a deeper understanding of eco-systems biology.

Ce mémoire présente deux projets de développement portant sur des algorithmes et des outils logiciels offrant des solutions pratiques à des problématiques courantes rencontrées en réadaptation. Le premier développement présenté est un algorithme de correspondance de séquence qui s'intègre à des interfaces de contrôle couramment utilisées en pratique. L'implémentation de cet algorithme offre une solution flexible pouvant s'adapter à n'importe quel utilisateur de technologies d'assistances. Le contrôle de tels appareils représente un défi de taille puisqu'ils ont, la plupart du temps, une dimensionnalité élevée (c-à-d. plusieurs degrés de liberté, modes ou commandes) et sont maniés à l'aide d'interfaces basées sur de capteurs de faible dimensionnalité offrant donc très peu de commandes physiques distinctes pour l'utilisateur. L'algorithme proposé se base donc sur de la reconnaissance de courts signaux temporels ayant la possibilité d'être agencés en séquences. L'éventail de combinaisons possibles augmente ainsi la dimensionnalité de l'interface. Deux applications de l'algorithme sont développées et testées. La première avec une interface de contrôle par le souffle pour un bras robotisé et la seconde pour une interface de gestes de la main pour le contrôle du clavier-souris d'un ordinateur. Le second développement présenté dans ce mémoire porte plutôt sur la collecte et l'analyse de données en réadaptation. Que ce soit en milieux cliniques, au laboratoires ou au domicile, nombreuses sont les situations où l'on souhaite récolter des données. La solution pour cette problématique se présente sous la forme d'un écosystème d'applications connectées incluant serveur et applications web, mobiles et embarquée. Ces outils logiciels sont développés sur mesure et offrent un procédé unique, peu coûteux, léger et rapide pour la collecte, la visualisation et la récupération de données. Ce manuscrit détaille une première version en décrivant l'architecture employée, les technologies utilisées et les raisons qui ont mené à ces choix tout en guidant les futures itérations. / This Master's thesis presents two development projects about algorithms and software tools providing practical solutions to commonly faced situations in rehabilitation context. The first project is the development of a sequence matching algorithm that can be integrated to the most commonly used control interfaces. The implementation of this algorithm provides a flexible solution that can be adapted to any assistive technology user. The control of such devices represents a challenge since their dimensionality is high (i.e., many degrees of freedom, modes, commands) and they are controlled with interfaces based on low-dimensionality sensors. Thus, the number of actual physical commands that the user can perform is low. The proposed algorithm is based on short time signals that can be organized into sequences. The multiple possible combinations then contribute to increasing the dimensionality of the interface. Two applications of the algorithm have been developed and tested. The first is a sip-and-puff control interface for a robotic assistive arm and the second is a hand gesture interface for the control of a computer's mouse and keyboard. The second project presented in this document addresses the issue of collecting and analyzing data. In a rehabilitation's clinical or laboratory environment, or at home, there are many situations that require gathering data. The proposed solution to this issue is a connected applications ecosystem that includes a web server and mobile, web and embedded applications. This custom-made software offers a unique, inexpensive, lightweight and fast workflow to visualize and retrieve data. The following document describes a first version by elaborating on the architecture, the technologies used, the reasons for those choices, and guide the next iterations.

Pas toutes les techniques de compression des données adoptent le principe de dictionnaire pour représenter ses mots de code. Le dictionnaire est un ensemble de mots de code associés aux symboles sources lors de l’opération d’encodage. La correspondance entre le mot de code et le symbole source dépend de l’algorithme de compression adopté. Généralement, chaque algorithme construit son dictionnaire selon un ensemble de propriétés. Parmi ces propriétés nous avons celle de préfixe. Elle est primordiale pour les codes de type fixe à variable (FV) tels que l’algorithme de Huffman et celui de Shannon-Fano. Par contre, la propriété préfixe est optionnelle pour les codes de longueur variable à fixe (VF). Donc cela peut causer le but de pouvoir construire un dictionnaire plus performant, comme le cas des codes quasi-instantanés. Dans cette optique, Yamamoto et Yokoo ont éliminé cette condition pour créer un dictionnaire meilleur que celui de Tunstall. Les dictionnaires proposés par Yamamoto et Yokoo sont appelés les codes VF quasi-instantanés ou en anglais almost instantaneous VF codes. En s’appuyant sur leurs contributions, nous avons déduit que leur technique peut fournir dans certains cas des codes variables à fixes sous-optimaux, d’où notre suggestion de correctifs à leurs algorithmes pour en améliorer l’efficacité. Aussi nous proposons un autre mécanisme pour construire des codes VF en utilisant le principe de la programmation dynamique. / Various techniques of data compression use a dictionary to represent their codewords. A dictionary is a set of codewords associated with the source symbols during the encoding operation. The correspondence between the codeword and the symbol source depends on the compression algorithm. Usually, the prefix property is key for the fixed-to-variable type codes FV as demonstrated in the Huffman and the Shannon-Fano algorithms. However, such a property may be eliminated for fixed-length codes in order to build a more efficient dictionary. In this context, Yamamoto and Yokoo excluded this condition to create a dictionary better than Tunstall. This new dictionary is called instantaneous variable-to-fixed code. Based on their contributions, we have deduced that their technique can provide, in some cases, suboptimal variable-to-fixed codes. Hence, we suggested to improve their algorithms. Also, we proposed another mechanism for building optimal AIVF codes by adopting the principle of dynamic programming.

Des systèmes informationnels de santé (SIS) ont été mis en place au cours des 20 dernières années pour soutenir les processus de soins, les tâches administratives et les activités de recherche ainsi que pour assurer la gestion raisonnée des établissements de santé. Un entrepôt de données (ED) doit être créé à partir de nombreuses sources de données hétérogènes afin de rendre les données exploitables d’une façon uniforme au sein des SIS. La temporalisation de cet entrepôt est rapidement devenue un enjeu crucial afin de garder les traces de l’évolution des données et d’améliorer la prise de décision clinique. L’entrepôt de données temporalisé (EDT) requiert l’application de règles systématiques afin de garantir l’intégrité et la qualité des données. Générer le schéma temporel d’un EDT est une tâche complexe. Plusieurs questions se posent dès lors, dont celles-ci : (a) Quel modèle temporel est le mieux adapté à l’automatisation de la construction d’un EDT (plus particulièrement dans le domaine de la santé)? (b) Quelles propriétés peut-on garantir formellement, suite à cette construction? D’une part, le volume du schéma de données nécessite d’importantes ressources humaines et financières, et d’autre part, plusieurs modèles temporels existent, mais ils ne sont pas formalisés ou non généraux. Les concepteurs s’en remettent donc le plus souvent à des règles de pratiques variées, floues, incomplètes et non validées. Dans ce travail, un cadre de référence permettant de formaliser, de généraliser et d’opérationnaliser des modèles temporels est défini. Deux modèles : BCDM et TRM sont présentés selon le cadre de référence avec leurs contraintes d’intégrité, leurs algorithmes de construction et une liste des prolongements requis. Il en résulte qu’il est désormais possible de s’affranchir des règles de pratique imprécises et de temporaliser un entrepôt en se fondant sur une méthode rigoureuse aux propriétés démontrables basées sur des critères fondamentaux (théorie relationnelle), des critères de conception reconnus et explicites (normalisation).

Les réseaux des capteurs sans fil sont considérés comme une alternative aux réseaux câblés afin de permettre l'installation dans des zones peu accessibles. Par conséquent, de nouveaux protocoles ont été conçus pour supporter le manque des ressources qui est spécifique à ce type de réseau. La communication entre les nœuds est réalisée par des protocoles spécifiques pour la gestion efficace de l'énergie. La gestion des données collectées par ces nœuds doit être également prise en compte car la communication entre les nœuds engendre un coût non négligeable en termes d'énergie. De plus, l'installation de ce type de réseau dans des régions lointaines facilite les attaques sur la structure des réseaux ainsi que sur les données collectées. Les mesures de sécurité envisagées amènent des coûts d'énergie supplémentaires. Un aspect souvent négligé concerne le cas où un nœud ne peut pas communiquer avec la station de base (sink node) qui collectionne et traite les données. Cependant, les nœuds continuent à accumuler des informations en suivant les plans de collection. Si la situation continue, l'espace de mémoire (storage) diminue à un point où la collection de nouvelles données n'est plus possible.Nous proposons des mécanismes pour la réduction contrôlée de données en considérant leur priorité relative. Les données sont divisées dans des unités auxquelles un niveau d'importance est alloué, en fonction des considérations d'utilité et de missions qui les utilisent. Nous proposons un ensemble de primitives (opérations) qui permettent la réduction d'espace de stockage nécessaire, tout en préservant un niveau raisonnable de résolution des informations collectées. Pour les larges réseaux à multiple nœuds, nous proposons des mécanismes pour le partage de données (data load sharing) ainsi que la redondance. Des algorithmes ont été proposés pour évaluer l'efficacité de ces techniques de gestion de données vis-à-vis de l'énergie nécessaire pour transférer les données.A travers des simulations, nous avons validé le fait que les résultats sont très utiles dans les cas à mémoire limitée (wireless nades) et pour les communications intermittentes.

Cette thèse présente une étude approfondie de la protection cryptographique des bases de données. Elle aborde tous les aspects de ce domaine : la législation l'encadrant, les produits commerciaux et " open-source " offrant ce type de service, et les travaux effectués par les communautés de cryptographie et de base de données. Cette étude se focalise notamment sur les systèmes d'information qui contiennent des données hautement sensibles. Dans ce contexte, nous avons étudié la sécurité de plusieurs propositions. En particulier, nous avons effectué une cryptanalyse de l'algorithme de chiffrement Fast Comparison Encryption (FCE) proposé par Ge et Zdonik en 2007, ainsi que d'une variante suggérée par les auteurs en réaction à notre première cryptanalyse. Ces deux attaques ont l'avantage d'être pratiques, c'est-à-dire qu'elles s'exécutent en temps raisonnable sur un PC standard. Ces travaux nous ont également conduit à proposer des façons sûres de protéger les bases de données en utilisant des algorithmes dont la sécurité a été éprouvée par la communauté cryptographique. Cela permet d'avoir des solutions robustes, à défaut d'être parfaites, pour protéger des données sensibles.