Spelling suggestions: "subject:"fouille dde données"" "subject:"fouille dee données""
151 |
Pattern mining rock: more, faster, betterTermier, Alexandre 08 July 2013 (has links) (PDF)
Le pattern mining est un domaine du data mining dont le but est l'extraction de régularité dans les données. Ce document présente nos contributions au domaine selon 3 axes : 1. Le domaine du pattern mining est jeune et il y existe encore beaucoup de types de régularités qu'un analyste serait intéressé de découvrir mais qui ne sont pas encore gérées. Nous avons contribué à deux nouveaux types de patterns: les patterns graduels et les patterns périodiques avec "ruptures". Nous avons aussi proposé ParaMiner, un algorithme original pour le pattern mining générique, qui permet à des analystes de spécifier directement le type de patterns qui les intéressent. 2. Le pattern mining demande beaucoup de ressources de calcul. Pour réduire le temps de calcul, nous avons étudié comment exploiter le parallélisme des processeurs multicoeurs. Nos résultats montrent que des techniques classiques en pattern mining sont mal adaptées au parallélisme, et nous avons proposé des solutions. 3. Notre objectif à long terme est de rendre le pattern mining plus facile à utiliser par les analystes. Il y a beaucoup à faire dans ce but, actuellement les analystes doivent travailler sur de longues listes de millions de patterns. Nous présentons nos premiers résultats, dans le contexte de la fouille de traces d'exécution de processeurs.
|
152 |
Une Approche Hybride de Simulation-Optimisation Basée sur la fouille de Données pour les problèmes d'ordonnancementShahzad, Atif 16 March 2011 (has links) (PDF)
Une approche hybride basée sur la fouille de données pour découvrir de nouvelles règles de priorité pour le problème l'ordonnancement job-shop est présentée. Cette approche est basée sur la recherche de connaissances supposées être intégrés dans les solutions efficaces fournies par un module d'optimisation préalablement mis en oeuvre et utilisant la recherche tabou. L'objectif est de découvrir les principes directeurs de l'ordonnancement à l'aide de la fouille de données et donc d'obtenir un ensemble de règles capables d'obtenir des solutions efficaces pour un problème d'ordonnancement. Une structure basée sur fouille de données est présentée et mise en œuvre pour un problème de job shop avec comme objectifs le retard maximum et le retard moyen. Les résultats obtenus sont très prometteurs.
|
153 |
Extraction de motifs spatio-temporels dans des séries d'images de télédétection : application à des données optiques et radar / Spatio-temporal pattern extraction from remote sensing image series : application on optical and radar dataJulea, Andreea Maria 20 September 2011 (has links)
Les Séries Temporelles d'Images Satellitaires (STIS), visant la même scène en évolution, sont très intéressantes parce qu'elles acquièrent conjointement des informations temporelles et spatiales. L'extraction de ces informations pour aider les experts dans l'interprétation des données satellitaires devient une nécessité impérieuse. Dans ce mémoire, nous exposons comment on peut adapter l'extraction de motifs séquentiels fréquents à ce contexte spatio-temporel dans le but d'identifier des ensembles de pixels connexes qui partagent la même évolution temporelle. La démarche originale est basée sur la conjonction de la contrainte de support avec différentes contraintes de connexité qui peuvent filtrer ou élaguer l'espace de recherche pour obtenir efficacement des motifs séquentiels fréquents groupés (MSFG) avec signification pour l'utilisateur. La méthode d'extraction proposée est non supervisée et basée sur le niveau pixel. Pour vérifier la généricité du concept de MSFG et la capacité de la méthode proposée d'offrir des résultats intéressants à partir des SITS, sont réalisées des expérimentations sur des données réelles optiques et radar. / The Satellite Image Time Series (SITS), aiming the same scene in evolution, are of high interest as they capture both spatial and temporal information. The extraction of this infor- mation to help the experts interpreting the satellite data becomes a stringent necessity. In this work, we expound how to adapt frequent sequential patterns extraction to this spatiotemporal context in order to identify sets of connected pixels sharing a same temporal evolution. The original approach is based on the conjunction of support constraint with different constraints based on pixel connectivity that can filter or prune the search space in order to efficiently ob- tain Grouped Frequent Sequential (GFS) patterns that are meaningful to the end user. The proposed extraction method is unsupervised and pixel level based. To verify the generality of GFS-pattern concept and the proposed method capability to offer interesting results from SITS, real data experiments on optical and radar data are presented.
|
154 |
Enhancing supervised learning with complex aggregate features and context sensitivity / Amélioration de l'apprentissage supervisé par l'utilisation d'agrégats complexes et la prise en compte du contexteCharnay, Clément 30 June 2016 (has links)
Dans cette thèse, nous étudions l'adaptation de modèles en apprentissage supervisé. Nous adaptons des algorithmes d'apprentissage existants à une représentation relationnelle. Puis, nous adaptons des modèles de prédiction aux changements de contexte.En représentation relationnelle, les données sont modélisées par plusieurs entités liées par des relations. Nous tirons parti de ces relations avec des agrégats complexes. Nous proposons des heuristiques d'optimisation stochastique pour inclure des agrégats complexes dans des arbres de décisions relationnels et des forêts, et les évaluons sur des jeux de données réelles.Nous adaptons des modèles de prédiction à deux types de changements de contexte. Nous proposons une optimisation de seuils sur des modèles à scores pour s'adapter à un changement de coûts. Puis, nous utilisons des transformations affines pour adapter les attributs numériques à un changement de distribution. Enfin, nous étendons ces transformations aux agrégats complexes. / In this thesis, we study model adaptation in supervised learning. Firstly, we adapt existing learning algorithms to the relational representation of data. Secondly, we adapt learned prediction models to context change.In the relational setting, data is modeled by multiples entities linked with relationships. We handle these relationships using complex aggregate features. We propose stochastic optimization heuristics to include complex aggregates in relational decision trees and Random Forests, and assess their predictive performance on real-world datasets.We adapt prediction models to two kinds of context change. Firstly, we propose an algorithm to tune thresholds on pairwise scoring models to adapt to a change of misclassification costs. Secondly, we reframe numerical attributes with affine transformations to adapt to a change of attribute distribution between a learning and a deployment context. Finally, we extend these transformations to complex aggregates.
|
155 |
Contribution des techniques de fusion et de classification des images au processus d'aide à la reconnaissance des cibles radar non coopératives / The contribution of fusion and classification techniques for non-cooperative target recognitionJdey Aloui, Imen 23 January 2014 (has links)
La reconnaissance automatique de cibles non coopératives est d’une grande importance dans divers domaines. C’est le cas pour les applications en environnement incertain aérien et maritime. Il s’avère donc nécessaire d’introduire des méthodes originales pour le traitement et l’identification des cibles radar. C’est dans ce contexte que s’inscrit notre travail. La méthodologie proposée est fondée sur le processus d’extraction de connaissance à partir de données (ECD) pour l’élaboration d’une chaine complète de reconnaissance à partir des images radar en essayant d’optimiser chaque étape de cette chaine de traitement. Les expérimentations réalisées pour constituer une base de données d’images ISAR ont été effectuées dans la chambre anéchoïque de l’ENSTA de Bretagne. Ce dispositif de mesures utilisé a l’avantage de disposer d’une maîtrise de la qualité des données représentants les entrées dans le processus de reconnaissance (ECD). Nous avons ainsi étudié les étapes composites de ce processus de l’acquisition jusqu’à l’interprétation et l’évaluation de résultats de reconnaissance. En particulier, nous nous sommes concentrés sur l’étape centrale dédiée à la fouille de données considérée comme le cœur du processus développé. Cette étape est composée de deux phases principales : une porte sur la classification et l’autre sur la fusion des résultats des classifieurs, cette dernière est nommée fusion décisionnelle. Dans ce cadre, nous avons montré que cette dernière phase joue un rôle important dans l’amélioration des résultats pour la prise de décision tout en prenant en compte les imperfections liées aux données radar, notamment l’incertitude et l’imprécision. Les résultats obtenus en utilisant d’une part les différentes techniques de classification (kppv, SVM et PMC), et d’autre part celles de de fusion décisionnelle (Bayes, vote, théorie de croyance, fusion floue) font l’objet d’une étude analytique et comparative en termes de performances. / The automatic recognition of non-cooperative targets is very important in various fields. This is the case for applications in aviation and maritime uncertain environment. Therefore, it’s necessary to introduce innovative methods for radar targets treatment and identification.The proposed methodology is based on the Knowledge Discovery from Data process (KDD) for a complete chain development of radar images recognition by trying to optimize every step of the processing chain.The experimental system used is based on an ISAR image acquisition system in the anechoic chamber of ENSTA Bretagne. This system has allowed controlling the quality of the entries in the recognition process (KDD). We studied the stages of the composite system from acquisition to interpretation and evaluation of results. We focused on the center stage; data mining considered as the heart of the system. This step is composed of two main phases: classification and the results of classifiers combination called decisional fusion. We have shown that this last phase improves results for decision making by taking into account the imperfections related to radar data, including uncertainty and imprecision.The results across different classification techniques as a first step (kNN, SVM and MCP) and decision fusion in a second time (Bayes, majority vote, belief theory, fuzzy fusion) are subject of an analytical and comparative study in terms of performance.
|
156 |
Contributions to decision tree based learning / Contributions à l’apprentissage de l’arbre des décisionsQureshi, Taimur 08 July 2010 (has links)
Advances in data collection methods, storage and processing technology are providing a unique challenge and opportunity for automated data learning techniques which aim at producing high-level information, or models, from data. A Typical knowledge discovery process consists of data selection, data preparation, data transformation, data mining and interpretation/validation of the results. Thus, we develop automatic learning techniques which contribute to the data preparation, transformation and mining tasks of knowledge discovery. In doing so, we try to improve the prediction accuracy of the overall learning process. Our work focuses on decision tree based learning and thus, we introduce various preprocessing and transformation techniques such as discretization, fuzzy partitioning and dimensionality reduction to improve this type of learning. However, these techniques can be used in other learning methods e.g. discretization can also be used for naive-bayes classifiers. The data preparation step represents almost 80 percent of the problem and is both time consuming and critical for the quality of modeling. Discretization of continuous features is an important problem that has effects on accuracy, complexity, variance and understandability of the induction models. In this thesis, we propose and develop resampling based aggregation techniques that improve the quality of discretization. Later, we validate by comparing with other discretization techniques and with an optimal partitioning method on 10 benchmark data sets.The second part of our thesis concerns with automatic fuzzy partitioning for soft decision tree induction. Soft or fuzzy decision tree is an extension of the classical crisp tree induction such that fuzzy logic is embedded into the induction process with the effect of more accurate models and reduced variance, but still interpretable and autonomous. We modify the above resampling based partitioning method to generate fuzzy partitions. In addition we propose, develop and validate another fuzzy partitioning method that improves the accuracy of the decision tree.Finally, we adopt a topological learning scheme and perform non-linear dimensionality reduction. We modify an existing manifold learning based technique and see whether it can enhance the predictive power and interpretability of classification. / La recherche avancée dans les méthodes d'acquisition de données ainsi que les méthodes de stockage et les technologies d'apprentissage, s'attaquent défi d'automatiser de manière systématique les techniques d'apprentissage de données en vue d'extraire des connaissances valides et utilisables.La procédure de découverte de connaissances s'effectue selon les étapes suivants: la sélection des données, la préparation de ces données, leurs transformation, le fouille de données et finalement l'interprétation et validation des résultats trouvés. Dans ce travail de thèse, nous avons développé des techniques qui contribuent à la préparation et la transformation des données ainsi qu'a des méthodes de fouille des données pour extraire les connaissances. A travers ces travaux, on a essayé d'améliorer l'exactitude de la prédiction durant tout le processus d'apprentissage. Les travaux de cette thèse se basent sur les arbres de décision. On a alors introduit plusieurs approches de prétraitement et des techniques de transformation; comme le discrétisation, le partitionnement flou et la réduction des dimensions afin d'améliorer les performances des arbres de décision. Cependant, ces techniques peuvent être utilisées dans d'autres méthodes d'apprentissage comme la discrétisation qui peut être utilisées pour la classification bayesienne.Dans le processus de fouille de données, la phase de préparation de données occupe généralement 80 percent du temps. En autre, elle est critique pour la qualité de la modélisation. La discrétisation des attributs continus demeure ainsi un problème très important qui affecte la précision, la complexité, la variance et la compréhension des modèles d'induction. Dans cette thèse, nous avons proposes et développé des techniques qui ce basent sur le ré-échantillonnage. Nous avons également étudié d'autres alternatives comme le partitionnement flou pour une induction floue des arbres de décision. Ainsi la logique floue est incorporée dans le processus d'induction pour augmenter la précision des modèles et réduire la variance, en maintenant l'interprétabilité.Finalement, nous adoptons un schéma d'apprentissage topologique qui vise à effectuer une réduction de dimensions non-linéaire. Nous modifions une technique d'apprentissage à base de variété topologiques `manifolds' pour savoir si on peut augmenter la précision et l'interprétabilité de la classification.
|
157 |
Diffusion de l’information dans les médias sociaux : modélisation et analyse / Information diffusion in social media : modeling and analysisGuille, Adrien 25 November 2014 (has links)
Les médias sociaux ont largement modifié la manière dont nous produisons, diffusons et consommons l'information et sont de fait devenus des vecteurs d'information importants. L’objectif de cette thèse est d’aider à la compréhension du phénomène de diffusion de l’information dans les médias sociaux, en fournissant des moyens d’analyse et de modélisation.Premièrement, nous proposons MABED, une méthode statistique pour détecter automatiquement les évènements importants qui suscitent l'intérêt des utilisateurs des médias sociaux à partir du flux de messages qu'ils publient, dont l'originalité est d'exploiter la fréquence des interactions sociales entre utilisateurs, en plus du contenu textuel des messages. Cette méthode diffère par ailleurs de celles existantes en ce qu'elle estime dynamiquement la durée de chaque évènement, plutôt que de supposer une durée commune et fixée à l'avance pour tous les évènements. Deuxièmement, nous proposons T-BASIC, un modèle probabiliste basé sur la structure de réseau sous-jacente aux médias sociaux pour prédire la diffusion de l'information, plus précisément l'évolution du volume d'utilisateurs relayant une information donnée au fil du temps. Contrairement aux modèles similaires également basés sur la structure du réseau, la probabilité qu'une information donnée se diffuse entre deux utilisateurs n'est pas constante mais dépendante du temps. Nous décrivons aussi une procédure pour l'inférence des paramètres latents du modèle, dont l'originalité est de formuler les paramètres comme des fonctions de caractéristiques observables des utilisateurs. Troisièmement, nous proposons SONDY, un logiciel libre et extensible implémentant des méthodes tirées de la littérature pour la fouille et l'analyse des données issues des médias sociaux. Le logiciel manipule deux types de données : les messages publiés par les utilisateurs, et la structure du réseau social interconnectant ces derniers. Contrairement aux logiciels académiques existants qui se concentrent soit sur l'analyse des messages, soit sur l'analyse du réseau, SONDY permet d'analyser ces deux types de données conjointement en permettant l'analyse de l'influence par rapport aux évènements détectés. Les expérimentations menées à l'aide de divers jeux de données collectés sur le média social Twitter démontrent la pertinence de nos propositions et mettent en lumière des propriétés qui nous aident à mieux comprendre les mécanismes régissant la diffusion de l'information. Premièrement, en comparant les performances de MABED avec celles de méthodes récentes tirées de la littérature, nous montrons que la prise en compte des interactions sociales entre utilisateurs conduit à une détection plus précise des évènements importants, avec une robustesse accrue en présence de contenu bruité. Nous montrons également que MABED facilite l'interprétation des évènements détectés en fournissant des descriptions claires et précises, tant sur le plan sémantique que temporel. Deuxièmement, nous montrons la validité de la procédure proposée pour estimer les probabilités de diffusion sur lesquelles repose le modèle T-BASIC, en illustrant le pouvoir prédictif des caractéristiques des utilisateurs sélectionnées et en comparant les performances de la méthode d'estimation proposée avec celles de méthodes tirées de la littérature. Nous montrons aussi l'intérêt d'avoir des probabilités non constantes, ce qui permet de prendre en compte dans T-BASIC la fluctuation du niveau de réceptivité des utilisateurs des médias sociaux au fil du temps. Enfin, nous montrons comment, et dans quelle mesure, les caractéristiques sociales, thématiques et temporelles des utilisateurs affectent la diffusion de l'information. Troisièmement, nous illustrons à l'aide de divers scénarios l'utilité du logiciel SONDY, autant pour des non-experts, grâce à son interface utilisateur avancée et des visualisations adaptées, que pour des chercheurs du domaine, grâce à son interface de programmation. / Social media have greatly modified the way we produce, diffuse and consume information, and have become powerful information vectors. The goal of this thesis is to help in the understanding of the information diffusion phenomenon in social media by providing means of modeling and analysis.First, we propose MABED (Mention-Anomaly-Based Event Detection), a statistical method for automatically detecting events that most interest social media users from the stream of messages they publish. In contrast with existing methods, it doesn't only focus on the textual content of messages but also leverages the frequency of social interactions that occur between users. MABED also differs from the literature in that it dynamically estimates the period of time during which each event is discussed rather than assuming a predefined fixed duration for all events. Secondly, we propose T-BASIC (Time-Based ASynchronous Independent Cascades), a probabilistic model based on the network structure underlying social media for predicting information diffusion, more specifically the evolution of the number of users that relay a given piece of information through time. In contrast with similar models that are also based on the network structure, the probability that a piece of information propagate from one user to another isn't fixed but depends on time. We also describe a procedure for inferring the latent parameters of that model, which we formulate as functions of observable characteristics of social media users. Thirdly, we propose SONDY (SOcial Network DYnamics), a free and extensible software that implements state-of-the-art methods for mining data generated by social media, i.e. the messages published by users and the structure of the social network that interconnects them. As opposed to existing academic tools that either focus on analyzing messages or analyzing the network, SONDY permits the joint analysis of these two types of data through the analysis of influence with respect to each detected event.The experiments, conducted on data collected on Twitter, demonstrate the relevance of our proposals and shed light on some properties that give us a better understanding of the mechanisms underlying information diffusion. First, we compare the performance of MABED against those of methods from the literature and find that taking into account the frequency of social interactions between users leads to more accurate event detection and improved robustness in presence of noisy content. We also show that MABED helps with the interpretation of detected events by providing clearer textual description and more precise temporal descriptions. Secondly, we demonstrate the relevancy of the procedure we propose for estimating the pairwise diffusion probabilities on which T-BASIC relies. For that, we illustrate the predictive power of users' characteristics, and compare the performance of the method we propose to estimate the diffusion probabilities against those of state-of-the-art methods. We show the importance of having non-constant diffusion probabilities, which allows incorporating the variation of users' level of receptivity through time into T-BASIC. We also study how -- and in which proportion -- the social, topical and temporal characteristics of users impact information diffusion. Thirdly, we illustrate with various scenarios the usefulness of SONDY, both for non-experts -- thanks to its advanced user interface and adapted visualizations -- and for researchers -- thanks to its application programming interface.
|
158 |
Confiance et risque pour engager un échange en milieu hostile / Trust and risk to exchange into hostil environmentLegrand, Véronique 19 June 2013 (has links)
De nos jours, l’échange électronique est le seul média qui offre l’accès à l’information pour tous, partout et tout le temps, mais en même temps il s’est ouvert à de nouvelles formes de vulnérabilités. La régulation des systèmes numériques, en héritage de la régulation cybernétique, maintient les équilibres à l’aide d’une boucle de rétroaction négative. Ainsi, leurs sys-tèmes de défense, désignés sous le terme de zone démilitarisée (DMZ) suivent-ils une régulation cybernétique en émettant ce que l’on appelle des évènements de sécurité. De tels évènements sont issus de sondes de surveillance qui matérialisent la ligne de dé-fense du système régulé. Toutefois, de telles sondes sont des système-experts et ces évènements appris au préalable ne rendent pas toujours compte de la dynamique de l’environnement et plus encore de la psychologie des individus. Plus encore, la multi-plication des systèmes de surveillance a entrainé une production considérable de ces évènements rendant cet ensemble de plus en plus inefficace. Par ailleurs, les systèmes vivants obéissent à une régulation complexe, l’homéostasie, qui les guide dans l’incertain à l’aide de mécanismes de surveillance continue. La force de tels mécanismes repose sur la variété des points de vue qu’ils empruntent ce qui leur permet de conjuguer leurs connaissances préalables à leurs informations de contexte pour comprendre leur environnement et s’adapter. Dans notre thèse, nous proposons d’associer à chaque système communicant, un sys-tème de surveillance continue : Dangerousness Incident Management (DIM) qui rend compte des changements de l’environnement en collectant et analysant toutes les traces laissées par les activités des usagers ou systèmes, légitimes ou non ; de cette manière, un tel système accède à une information étendue et reste sensible à son contexte. Néan-moins, plusieurs difficultés surviennent liées à la compréhension des informations re-cueillies dont le sens est noyé dans une grande masse d’informations, elles sont deve-nues implicites. Notre contribution principale repose sur un mécanisme de fouille de données adapté aux informations implicites. Nous proposons une structure à fort pou-voir d’abstraction fondée sur le principe d’un treillis de concepts. À partir de ce modèle de référence adaptatif, il nous est possible de représenter tous les acteurs d’un échange afin de faire coopérer plusieurs points de vue et plusieurs systèmes, qu’ils soient hu-mains ou machine. Lorsque l’incertitude de ces situations persiste, nous proposons un mécanisme pour guider l’usager dans ses décisions fondé sur le risque et la confiance. Enfin, nous évaluons nos résultats en les comparant aux systèmes de références Com-mon Vulnerabilities and Exposures (CVE) proposés par le National Institute of Stan-dards and Technology (NIST). / Nowadays, the electronic form of exchanges offers a new media able to make easy all information access, ubiquitous access, everywhere and everytime. But, at the same time, such a media - new, opened and complex - introduces unknown threats and breaches. So, how can we start up trust exchanges? From the system theory point of view, the cybernetic regulation maintains the sys-tems equilibrium with negative feedback loops. In this way, the defense line is based on a set of defense components still named Demilitarized Zone (DMZ) in order to block flow, to control anomalies and give out alerts messages if deviances are detected. Nev-ertheless, most of these messages concern only anomalies of machines and very little of human. So, messages do not take into account neither psychological behavior nor the dynamic of the context. Furthermore, messages suffer of the "big data" problem and become confused due to too much velocity, volume and variety. Finally, we can limit this problem to the understanding difficulty during the access to the specific knowledge in connection with the message. For example, the identity theft with the XSS attack is an illustration of this unfriendly environment. On the contrary, the living sciences show that organisms follow a positive regulation by where each one itself adapts according to his complexity. For that, they deploy adapted and continuous environment monitoring process still named "homeostasis". During this cycle, inputs capture information, then outputs adjust in response corre-sponding actions : this is the feedback. The strength of such a mechanism lies on the information meaning and in particular on the clues they include. In fact, some of these information include clues by which organisms can explain situations. For example, the information « attention" alludes to dangerous situation. This faculty comes from ad-vanced knowledge having first explicit relationship with this information: this relation forms what we call the "cognitive loop". To illustrate this phenomenon, the cognitive sciences often evoke "a friend immediately recognized by her friend" despite he is swal-lowed up in the crowd. But, the cognitive loop should not be broken. Like the living beings functioning, our work propose a cognitive model named Diag-nostic And Incident Model (DIM). The main idea lies on the context-aware model in order to adapt itself like "homeostasis". DIM has been founded on the principle of the "cognitive loop" where the inputs are the "logs" of numerics systems. So, in order to make easier the comparison between contextual and known situation, we will design "logs" and advanced knowledge by a common model. DIM proposes a conceptual struc-ture to extract clues from massive and various "logs” issued from environment based on advanced knowledge acquisition. Then, we propose the cognitive structure will be applied to the anomaly detection, incident management and diagnosis process.
|
159 |
Graph mining for object tracking in videos / Fouille de graphes pour le suivi d’objets dans les vidéosDiot, Fabien 03 June 2014 (has links)
Détecter et suivre les objets principaux d’une vidéo est une étape nécessaire en vue d’en décrire le contenu pour, par exemple, permettre une indexation judicieuse des données multimédia par les moteurs de recherche. Les techniques de suivi d’objets actuelles souffrent de défauts majeurs. En effet, soit elles nécessitent que l’utilisateur désigne la cible a suivre, soit il est nécessaire d’utiliser un classifieur pré-entraîné à reconnaitre une classe spécifique d’objets, comme des humains ou des voitures. Puisque ces méthodes requièrent l’intervention de l’utilisateur ou une connaissance a priori du contenu traité, elles ne sont pas suffisamment génériques pour être appliquées aux vidéos amateurs telles qu’on peut en trouver sur YouTube. Pour résoudre ce problème, nous partons de l’hypothèse que, dans le cas de vidéos dont l’arrière-plan n’est pas fixe, celui-ci apparait moins souvent que les objets intéressants. De plus, dans une vidéo, la topologie des différents éléments visuels composant un objet est supposée consistante d’une image a l’autre. Nous représentons chaque image par un graphe plan modélisant sa topologie. Ensuite, nous recherchons des motifs apparaissant fréquemment dans la base de données de graphes plans ainsi créée pour représenter chaque vidéo. Cette approche nous permet de détecter et suivre les objets principaux d’une vidéo de manière non supervisée en nous basant uniquement sur la fréquence des motifs. Nos contributions sont donc réparties entre les domaines de la fouille de graphes et du suivi d’objets. Dans le premier domaine, notre première contribution est de présenter un algorithme de fouille de graphes plans efficace, appelé PLAGRAM. Cet algorithme exploite la planarité des graphes et une nouvelle stratégie d’extension des motifs. Nous introduisons ensuite des contraintes spatio-temporelles au processus de fouille afin d’exploiter le fait que, dans une vidéo, les objets se déplacent peu d’une image a l’autre. Ainsi, nous contraignons les occurrences d’un même motif a être proches dans l’espace et dans le temps en limitant le nombre d’images et la distance spatiale les séparant. Nous présentons deux nouveaux algorithmes, DYPLAGRAM qui utilise la contrainte temporelle pour limiter le nombre de motifs extraits, et DYPLAGRAM_ST qui extrait efficacement des motifs spatio-temporels fréquents depuis les bases de données représentant les vidéos. Dans le domaine du suivi d’objets, nos contributions consistent en deux approches utilisant les motifs spatio-temporels pour suivre les objets principaux dans les vidéos. La première est basée sur une recherche du chemin de poids minimum dans un graphe connectant les motifs spatio-temporels tandis que l’autre est basée sur une méthode de clustering permettant de regrouper les motifs pour suivre les objets plus longtemps. Nous présentons aussi deux applications industrielles de notre méthode / Detecting and following the main objects of a video is necessary to describe its content in order to, for example, allow for a relevant indexation of the multimedia content by the search engines. Current object tracking approaches either require the user to select the targets to follow, or rely on pre-trained classifiers to detect particular classes of objects such as pedestrians or car for example. Since those methods rely on user intervention or prior knowledge of the content to process, they cannot be applied automatically on amateur videos such as the ones found on YouTube. To solve this problem, we build upon the hypothesis that, in videos with a moving background, the main objects should appear more frequently than the background. Moreover, in a video, the topology of the visual elements composing an object is supposed consistent from one frame to another. We represent each image of the videos with plane graphs modeling their topology. Then, we search for substructures appearing frequently in the database of plane graphs thus created to represent each video. Our contributions cover both fields of graph mining and object tracking. In the first field, our first contribution is to present an efficient plane graph mining algorithm, named PLAGRAM. This algorithm exploits the planarity of the graphs and a new strategy to extend the patterns. The next contributions consist in the introduction of spatio-temporal constraints into the mining process to exploit the fact that, in a video, the motion of objects is small from on frame to another. Thus, we constrain the occurrences of a same pattern to be close in space and time by limiting the number of frames and the spatial distance separating them. We present two new algorithms, DYPLAGRAM which makes use of the temporal constraint to limit the number of extracted patterns, and DYPLAGRAM_ST which efficiently mines frequent spatio-temporal patterns from the datasets representing the videos. In the field of object tracking, our contributions consist in two approaches using the spatio-temporal patterns to track the main objects in videos. The first one is based on a search of the shortest path in a graph connecting the spatio-temporal patterns, while the second one uses a clustering approach to regroup them in order to follow the objects for a longer period of time. We also present two industrial applications of our method
|
160 |
Big data management for periodic wireless sensor networks / Gestion de données volumineuses dans les réseaux de capteurs périodiquesMedlej, Maguy 30 June 2014 (has links)
Les recherches présentées dans ce mémoire s’inscrivent dans le cadre des réseaux decapteurs périodiques. Elles portent sur l’étude et la mise en oeuvre d’algorithmes et de protocolesdistribués dédiés à la gestion de données volumineuses, en particulier : la collecte, l’agrégation etla fouille de données. L’approche de la collecte de données permet à chaque noeud d’adapter sontaux d’échantillonnage à l’évolution dynamique de l’environnement. Par ce modèle le suréchantillonnageest réduit et par conséquent la quantité d’énergie consommée. Elle est basée surl’étude de la dépendance de la variance de mesures captées pendant une même période voirpendant plusieurs périodes différentes. Ensuite, pour sauvegarder plus de l’énergie, un modèled’adpatation de vitesse de collecte de données est étudié. Ce modèle est basé sur les courbes debézier en tenant compte des exigences des applications. Dans un second lieu, nous étudions unetechnique pour la réduction de la taille de données massive qui est l’agrégation de données. Lebut est d’identifier tous les noeuds voisins qui génèrent des séries de données similaires. Cetteméthode est basée sur les fonctions de similarité entre les ensembles de mesures et un modèle defiltrage par fréquence. La troisième partie est consacrée à la fouille de données. Nous proposonsune adaptation de l’approche k-means clustering pour classifier les données en clusters similaires,d’une manière à l’appliquer juste sur les préfixes des séries de mesures au lieu de l’appliquer auxséries complètes. Enfin, toutes les approches proposées ont fait l’objet d’études de performancesapprofondies au travers de simulation (OMNeT++) et comparées aux approches existantes dans lalittérature. / This thesis proposes novel big data management techniques for periodic sensor networksembracing the limitations imposed by wsn and the nature of sensor data. First, we proposed anadaptive sampling approach for periodic data collection allowing each sensor node to adapt itssampling rates to the physical changing dynamics. It is based on the dependence of conditionalvariance of measurements over time. Then, we propose a multiple level activity model that usesbehavioral functions modeled by modified Bezier curves to define application classes and allowfor sampling adaptive rate. Moving forward, we shift gears to address the periodic dataaggregation on the level of sensor node data. For this purpose, we introduced two tree-based bilevelperiodic data aggregation techniques for periodic sensor networks. The first one look on aperiodic basis at each data measured at the first tier then, clean it periodically while conservingthe number of occurrences of each measure captured. Secondly, data aggregation is performedbetween groups of nodes on the level of the aggregator while preserving the quality of theinformation. We proposed a new data aggregation approach aiming to identify near duplicatenodes that generate similar sets of collected data in periodic applications. We suggested the prefixfiltering approach to optimize the computation of similarity values and we defined a new filteringtechnique based on the quality of information to overcome the data latency challenge. Last butnot least, we propose a new data mining method depending on the existing K-means clusteringalgorithm to mine the aggregated data and overcome the high computational cost. We developeda new multilevel optimized version of « k-means » based on prefix filtering technique. At the end,all the proposed approaches for data management in periodic sensor networks are validatedthrough simulation results based on real data generated by periodic wireless sensor network.
|
Page generated in 0.0716 seconds