Spelling suggestions: "subject:"fouille dess données"" "subject:"fouille deus données""
81 |
Problématique des entrepôts de données textuelles : dr Warehouse et la recherche translationnelle sur les maladies rares / Textual data Warehouse challenge : Dr. Warehouse and translational research on rare diseasesGarcelon, Nicolas 29 November 2017 (has links)
La réutilisation des données de soins pour la recherche s’est largement répandue avec le développement d’entrepôts de données cliniques. Ces entrepôts de données sont modélisés pour intégrer et explorer des données structurées liées à des thesaurus. Ces données proviennent principalement d’automates (biologie, génétique, cardiologie, etc) mais aussi de formulaires de données structurées saisies manuellement. La production de soins est aussi largement pourvoyeuse de données textuelles provenant des comptes rendus hospitaliers (hospitalisation, opératoire, imagerie, anatomopathologie etc.), des zones de texte libre dans les formulaires électroniques. Cette masse de données, peu ou pas utilisée par les entrepôts classiques, est une source d’information indispensable dans le contexte des maladies rares. En effet, le texte libre permet de décrire le tableau clinique d’un patient avec davantage de précisions et en exprimant l’absence de signes et l’incertitude. Particulièrement pour les patients encore non diagnostiqués, le médecin décrit l’histoire médicale du patient en dehors de tout cadre nosologique. Cette richesse d’information fait du texte clinique une source précieuse pour la recherche translationnelle. Cela nécessite toutefois des algorithmes et des outils adaptés pour en permettre une réutilisation optimisée par les médecins et les chercheurs. Nous présentons dans cette thèse l'entrepôt de données centré sur le document clinique, que nous avons modélisé, implémenté et évalué. À travers trois cas d’usage pour la recherche translationnelle dans le contexte des maladies rares, nous avons tenté d’adresser les problématiques inhérentes aux données textuelles: (i) le recrutement de patients à travers un moteur de recherche adapté aux données textuelles (traitement de la négation et des antécédents familiaux), (ii) le phénotypage automatisé à partir des données textuelles et (iii) l’aide au diagnostic par similarité entre patients basés sur le phénotypage. Nous avons pu évaluer ces méthodes sur l’entrepôt de données de Necker-Enfants Malades créé et alimenté pendant cette thèse, intégrant environ 490 000 patients et 4 millions de comptes rendus. Ces méthodes et algorithmes ont été intégrés dans le logiciel Dr Warehouse développé pendant la thèse et diffusé en Open source depuis septembre 2017. / The repurposing of clinical data for research has become widespread with the development of clinical data warehouses. These data warehouses are modeled to integrate and explore structured data related to thesauri. These data come mainly from machine (biology, genetics, cardiology, etc.) but also from manual data input forms. The production of care is also largely providing textual data from hospital reports (hospitalization, surgery, imaging, anatomopathologic etc.), free text areas in electronic forms. This mass of data, little used by conventional warehouses, is an indispensable source of information in the context of rare diseases. Indeed, the free text makes it possible to describe the clinical picture of a patient with more precision and expressing the absence of signs and uncertainty. Particularly for patients still undiagnosed, the doctor describes the patient's medical history outside any nosological framework. This wealth of information makes clinical text a valuable source for translational research. However, this requires appropriate algorithms and tools to enable optimized re-use by doctors and researchers. We present in this thesis the data warehouse centered on the clinical document, which we have modeled, implemented and evaluated. In three cases of use for translational research in the context of rare diseases, we attempted to address the problems inherent in textual data: (i) recruitment of patients through a search engine adapted to textual (data negation and family history detection), (ii) automated phenotyping from textual data, and (iii) diagnosis by similarity between patients based on phenotyping. We were able to evaluate these methods on the data warehouse of Necker-Enfants Malades created and fed during this thesis, integrating about 490,000 patients and 4 million reports. These methods and algorithms were integrated into the software Dr Warehouse developed during the thesis and distributed in Open source since September 2017.
|
82 |
Routine activity extraction from local alignments in mobile phone context data / Une approche d'alignement à la problématique de la détection des activités habituellesMoritz, Rick Patrick Constantin 05 February 2014 (has links)
L'homme, de manière générale apprécie ses habitudes. Nous proposons une méthodologie d'identification des activités de routine depuis des régularités extraites des données de contexte, acquises sur téléphone portable. Notre choix algorithmique se base sur l'algorithme d'alignement proposé par Lecroq et al. L'algorithme cherche à aligner des séquences de n-uplets de données du contexte. Les séquences algorithmiques correspondent aux traces d'utilisation régulières. Notre contribution technique consiste à l'amélioration de l'algorithme afin qu'il puisse exploiter la nature séquentielle des données se basant sur une approche d'optimisation locale. Les deux apports rendent la solution adaptée aux données dont la volumétrie compatibles avec les données de contexte.Afin d'évaluer notre approche, nous présentons un générateur de données simulées et une campagne d'acquisition de données réelles. Ces données sont utilisées pour valider notre approche. / Humans are creatures of habit, often developing a routine for their day-to-day life. We propose a way to identify routine as regularities extracted from the context data of mobile phones. We choose Lecroq et al.'s existing state of the art algorithm as basis for a set of modifications that render it suitable for the task. Our approach searches alignments in sequences of n-tuples of context data, which correspond to the user traces of routine activity. Our key enhancements to this algorithm are exploiting the sequential nature of the data an early maximisation approach. We develop a generator of context-like data to allow us to evaluate our approach. Additionally, we collect and manually annotate a mobile phone context dataset to facilitate the evaluation of our algorithm. The results allow us to validate the concept of our approach.
|
83 |
Système d'information décisionnel sur les interactions environnement-santé : cas de la Fièvre de la Vallée du Rift au Ferlo (Sénégal) / Decision-making system on environment and health interactions : case of the Rift Valley Fever in Ferlo (Senegal)Bouba, Fanta 25 September 2015 (has links)
Notre recherche se situe dans le cadre du projet QWECI (Quantifying Weather and Climate Impacts on Health in Developing Countries, UE FP7) en partenariat avec l’UCAD, le CSE et l’IPD, autour de la thématique environnement-santé avec comme cas pratique les maladies à vecteurs au Sénégal et plus particulièrement la Fièvre de la Vallée du Rift (FVR). La santé des populations humaines et animales est souvent fortement influencée par l’environnement. D’ailleurs, la recherche sur les facteurs de propagation des maladies à transmission vectorielle, telle que la FVR, prend en compte cette problématique dans sa dimension aussi bien physique que socio-économique. Apparue en 1912-1913 au Kenya, la FVR est une anthropo-zoonose virale répandue dans les régions tropicales qui concerne principalement les animaux mais dont les hommes peuvent aussi être touchés. Au Sénégal, la zone à risque concerne en majorité la vallée du fleuve Sénégal et la zone sylvo-pastorale du Ferlo. Bien que de climat sahélien, le Ferlo regorge de nombreuses mares qui sont des sources d’approvisionnement en eau pour les hommes et le bétail mais également les gîtes larvaires pour les vecteurs potentiels de la FVR. La maîtrise de la FVR, carrefour de trois (03) grands systèmes (agro-écologique, pathogène, économique/sanitaire/social), implique nécessairement la prise en compte de plusieurs paramètres si l’on veut d’abord comprendre les mécanismes d’émergence mais aussi envisager le travail de modélisation du risque. Notre travail porte sur le processus décisionnel pour quantifier l’utilisation de données sanitaires et environnementales dans l’évaluation de leur impact pour le suivi de la FVR. Les équipes de recherche impliquées produisent des données lors de leurs enquêtes de terrains et des analyses de laboratoire. Ce flot de données croissant devrait être stocké et préparé à des études corrélées grâce aux nouvelles techniques de stockage que sont les entrepôts de données. A propos de l’analyse des données, il ne suffit pas de s’appuyer seulement sur les techniques classiques telles que les statistiques. En effet, la valeur ajoutée de contribution sur la question s’oriente vers une analyse prédictive combinant à la fois les techniques agrégées de stockage et des outils de traitement. Ainsi, pour la découverte d’informations, nouvelles et pertinentes à priori non évidentes, il est nécessaire de s’orienter vers la fouille de données. Par ailleurs, l’évolution de la maladie étant fortement liée à la dynamique spatio-temporelle environnementale des différents acteurs (vecteurs, virus et hôtes), cause pour laquelle nous nous appuyons sur les motifs spatio-temporels pour identifier et mesurer certaines interactions entre les paramètres environnementaux et les acteurs impliqués. Grâce au processus décisionnel, les résultats qui en découlent sont multiples :i. suivant la formalisation de la modélisation multidimensionnelle, nous avons construit un entrepôt de données intégré qui regroupe l’ensemble des objets qui participent à la gestion du risque sanitaire – ce modèle peut être généralisé aux maladies à vecteurs ;ii. malgré une très grande variété de moustiques, les Culex de type neavei et les Aedes de type ochraceus et vexans sont les vecteurs potentiels de la FVR les plus présents dans la zone d’étude et ce, durant la saison des pluies, période la plus sujette à des cas suspects ; la période à risque reste quand même le mois d’octobre ;iii. les mares analysées ont quasiment le même comportement, mais des variations significatives subsistent par endroits.Ce travail de recherche démontre une fois de plus l’intérêt pour la mise en évidence des relations entre les données environnementales et la FVR à partir de méthodes de fouille de données, pour la surveillance spatio-temporelle du risque d’émergence. / Our research is in part of the QWeCI european project (Quantifying Weather and Climate Impacts on Health in Developing Countries, EU FP7) in partnership with UCAD, the CSE and the IPD, around the theme of environmental health with the practical case on vector-borne diseases in Senegal and particularly the Valley Fever (RVF). The health of human and animal populations is often strongly influenced by the environment. Moreover, research on spread factors of vector-borne diseases such as RVF, considers this issue in its dimension both physical and socio-economic. Appeared in 1912-1913 in Kenya, RVF is a widespread viral anthropo-zoonosis in tropical regions which concerns animals but men can also be affected. In Senegal, the risk area concerns mainly the Senegal River Valley and the forestry-pastoral areas Ferlo. With a Sahelian climate, the Ferlo has several ponds that are sources of water supply for humans and livestock but also breeding sites for potential vectors of RVF. The controlling of the RVF, which is crossroads of three (03) large systems (agro-ecological, pathogen, economic/health/social), necessarily entails consideration of several parameters if one wants to first understand the mechanisms emergence but also consider the work on risk modeling. Our work focuses on the decision making process for quantify the use of health data and environmental data in the impact assessment for the monitoring of RVF. Research teams involved produce data during their investigations periods and laboratory analyzes. The growing flood of data should be stored and prepared for correlated studies with new storage techniques such as datawarehouses. About the data analysis, it is not enough to rely only on conventional techniques such as statistics. Indeed, the contribution on the issue is moving towards a predictive analysis combining both aggregate storage techniques and processing tools. Thus, to discover information, it is necessary to move towards datamining. Furthermore, the evolution of the disease is strongly linked to environmental spatio-temporal dynamics of different actors (vectors, viruses, and hosts), cause for which we rely on spatio-temporal patterns to identify and measure interactions between environmental parameters and the actors involved. With the decision-making process, we have obtained many results :i. following the formalization of multidimensional modeling, we have built an integrated datawarehouse that includes all the objects that are involved in managing the health risk - this model can be generalized to others vector-borne diseases;ii. despite a very wide variety of mosquitoes, Culex neavei, Aedes ochraceus and Aedes vexans are potential vectors of FVR. They are most present in the study area and, during the rainy season period which is most prone to suspected cases; the risk period still remains the month of October;iii. the analyzed ponds have almost the same behavior, but significant variations exist in some points.This research shows once again the interest in the discovery of relationships between environmental data and the FVR with datamining methods for the spatio-temporal monitoring of the risk of emergence.
|
84 |
Mining user similarity in online social networks : analysis,modeling and applications / Fouille de similarité de l'utilisateur dans les réseaux sociaux : analyse, modélisation et applicationsHan, Xiao 21 May 2015 (has links)
Réseaux sociaux (RS) (par exemple, Facebook, Twitter et LinkedIn) ont gagné en popularité écrasante et accumulé des données numériques massives sur la société humaine. Ces données massives, représentant de l’information personnelle et sociale des individus, nous offrent des possibilités sans précédent pour étudier, analyser et modéliser la structure de réseau complexe, les relations humaines, les gens similitude, etc. Pendant ce temps, les RS ont déclenché un grand nombre d’applications et de services qui rentables chercher à maintenir des liens de vibrer et l’expérience des utilisateurs d’avance. Dans ce contexte, comment concevoir ces applications et les services, en particulier comment extraire et d’exploiter des fonctionnalités sociales efficaces à partir des données massives disponibles pour améliorer les applications et les services, a reçu beaucoup d’attention. Cette thèse, visant à améliorer les applications et les services sociaux, étudie trois questions essentielles et pratiques RS: (1) Comment pouvons-nous explorer les amis potentiels pour un utilisateur d’établir et d’élargir ses liens sociaux? (2) comment pouvons-nous découvrir un contenu intéressant pour un utilisateur pour satisfaire ses goûts personnels? (3) comment pouvons-nous informer un utilisateur du risque d’exposition de son information privée pour préserver sa vie privée? S’appuyant sur les idées sur la similarité de personnes dans les sciences sociales, cette thèse étudie les effets et les applications de l’utilisateur similitude dans les RS pour résoudre les problèmes mentionnés ci-dessus. Plus précisément, les sociologues suggèrent que la similitude engendre connexion et induit principe homophilie que les gens similaires (par exemple, même âge, l’éducation ou la profession) sont plus susceptibles de communiquer, de confiance et de partager l’information avec l’autre que ceux dissemblables. Inspiré par ces résultats, cette thèse étudie le principe de similitude répandue dans RS en termes de savoir si les utilisateurs similaires seraient proches dans leurs relations sociales, similaire dans leurs intérêts, ou approximative dans leur géo distance, en se appuyant sur 500K profils d’utilisateurs recueillies auprès de Facebook; il explore en outre des solutions pour exploiter efficacement le principe de similitude observée pour concevoir les quatre applications et des services sociaux suivantes: • Effets de Similarité de L’utilisateur sur Lien Prévision pour les Nouveaux Utilisateurs : nous analysons la prédiction de liaison pour les nouveaux utilisateurs qui n’ont pas créé de lien. Basé sur l’information limitée obtenu lors de votre inscription la procédure de nouveaux utilisateurs, ainsi que les attributs et les liens des utilisateurs existants dans un RS, nous étudions la façon dont beaucoup de similitude entre deux utilisateurs affecterait la probabilité qu’ils se lient d’amitié. En conséquence, nous proposons un modèle de prédiction de liaison efficace pour les nouveaux utilisateurs. • Similarité Minière de L’utilisateur pour la Découverte de Contenu en Réseaux P2P Sociale : nous examinons comment similarité et connaissances des participants dans RS pourraient bénéficier leur découverte de contenu dans les réseaux P2P. Nous construisons un modèle de réseau P2P sociale où chaque pair attribue plus de poids à ses amis dans RS qui ont similarité supérieur et plus de connaissances. Utilisation de marche aléatoire avec la méthode de redémarrage, nous présentons un nouveau contenu algorithme de découverte le dessus du modèle de réseau P2P sociale proposé. • Inspection intérêt similarité - Prédiction et Application : nous présentons des études empiriques détaillées sur les intérêts similitude et de révéler que les gens sont susceptibles de présenter des goûts similaires s’ils ont des informations démographiques similaires (par exemple, âge, lieu), ou s’elles sont amis. Par conséquent, étant donné un nouvel utilisateur dont les intérêts (...) / Online Social Networks (OSNs) (e.g., Facebook, Twitter and LinkedIn) have gained overwhelming popularity and accumulated massive digital data about human society. These massive data, representing individuals' personal and social information, provide us with unprecedented opportunities to study, analyze and model the complex network structure, human connections, people similarity, etc. Meanwhile, OSNs have triggered a large number of profitable applications and services which seek to maintain vibrate connections and advance users' experience. In this context, how to devise such applications and services, especially how to extract and exploit effective social features from the massive available data to enhance the applications and services, has received much attention. This dissertation, aiming to enhance the social applications and services, investigates three critical and practical issues in OSNs: (1) How can we explore potential friends for a user to establish and enlarge her social connections? (2) How can we discover interesting content for a user to satisfy her personal tastes? (3) How can we inform a user the exposure risk of her private information to preserve her privacy? Drawing on the insights about people's similarity in social science, this dissertation studies the widespread similarity principle in OSN in terms of whether similar users would be close in their social relationships, similar in their interests, or approximate in their geo-distance, relying on 500K user profiles collected from Facebook; it further explores solutions to effectively leverage the observed similarity principle to address the aforementioned practical issues
|
85 |
Empreintes audio et stratégies d'indexation associées pour l'identification audio à grande échelle / Audio-fingerprints and associated indexing strategies for the purpose of large-scale audio-identificationFenet, Sébastien 23 September 2013 (has links)
Dans cet ouvrage, nous définissons précisément ce qu’est l’identification audio à grande échelle. En particulier, nous faisons une distinction entre l’identification exacte, destinée à rapprocher deux extraits sonores provenant d’un même enregistrement, et l’identification approchée, qui gère également la similarité musicale entre les signaux. A la lumière de ces définitions, nous concevons et examinons plusieurs modèles d’empreinte audio et évaluons leurs performances, tant en identification exacte qu’en identificationapprochée. / N this work we give a precise definition of large scale audio identification. In particular, we make a distinction between exact and approximate matching. In the first case, the goal is to match two signals coming from one same recording with different post-processings. In the second case, the goal is to match two signals that are musically similar. In light of these definitions, we conceive and evaluate different audio-fingerprint models.
|
86 |
Découverte de collections homogènes de sous-graphes denses par des méthodes de fouille de données sous contraintesMougel, Pierre-Nicolas 14 September 2012 (has links) (PDF)
Ce travail de thèse concerne la fouille de données sur des graphes attribués. Il s'agit de graphes dans lesquels des propriétés, encodées sous forme d'attributs, sont associées à chaque sommet. Notre objectif est la découverte, dans ce type de données, de sous-graphes organisés en plusieurs groupes de sommets fortement connectés et homogènes au regard des attributs. Plus précisément, nous définissons l'extraction sous contraintes d'ensembles de sous-graphes densément connectés et tels que les sommets partagent suffisamment d'attributs. Pour cela nous proposons deux familles de motifs originales ainsi que les algorithmes justes et complets permettant leur extraction efficace sous contraintes. La première famille, nommée Ensembles Maximaux de Cliques Homogènes, correspond à des motifs satisfaisant des contraintes concernant le nombre de sous-graphes denses, la taille de ces sous-graphes et le nombre d'attributs partagés. La seconde famille, nommée Collections Homogènes de k-cliques Percolées emploie quant à elle une notion de densité plus relaxée permettant d'adapter la méthode aux données avec des valeurs manquantes. Ces deux méthodes sont appliquées à l'analyse de deux types de réseaux, les réseaux de coopérations entre chercheurs et les réseaux d'interactions de protéines. Les motifs obtenus mettent en évidence des structures utiles dans un processus de prise de décision. Ainsi, dans un réseau de coopérations entre chercheurs, l'analyse de ces structures peut aider à la mise en place de collaborations scientifiques entre des groupes travaillant sur un même domaine. Dans le contexte d'un graphe de protéines, les structures exhibées permettent d'étudier les relations entre des modules de protéines intervenant dans des situations biologiques similaires. L'étude des performances en fonction de différentes caractéristiques de graphes attribués réels et synthétiques montre que les approches proposées sont utilisables sur de grands jeux de données.
|
87 |
Extraction de motifs dans la rédaction collaborative sur les WikisUwatowenimana, Jeanne d'Arc January 2008 (has links)
Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.
|
88 |
Conception d'heuristiques d'optimisation pour les problèmes de grande dimension : application à l'analyse de données de puces à ADN / Heuristics implementation for high-dimensional problem optimization : application in microarray data analysisGardeux, Vincent 30 November 2011 (has links)
Cette thèse expose la problématique récente concernant la résolution de problèmes de grande dimension. Nous présentons les méthodes permettant de les résoudre ainsi que leurs applications, notamment pour la sélection de variables dans le domaine de la fouille de données. Dans la première partie de cette thèse, nous exposons les enjeux de la résolution de problèmes de grande dimension. Nous nous intéressons principalement aux méthodes de recherche linéaire, que nous jugeons particulièrement adaptées pour la résolution de tels problèmes. Nous présentons ensuite les méthodes que nous avons développées, basées sur ce principe : CUS, EUS et EM323. Nous soulignons en particulier la très grande vitesse de convergence de CUS et EUS, ainsi que leur simplicité de mise en oeuvre. La méthode EM323 est issue d'une hybridation entre la méthode EUS et un algorithme d'optimisation unidimensionnel développé par F. Glover : l'algorithme 3-2-3. Nous montrons que ce dernier algorithme obtient des résultats d'une plus grande précision, notamment pour les problèmes non séparables, qui sont le point faible des méthodes issues de la recherche linéaire. Dans une deuxième partie, nous nous intéressons aux problèmes de fouille de données, et plus particulièrement l'analyse de données de puces à ADN. Le but est de classer ces données et de prédire le comportement de nouveaux exemples. Dans un premier temps, une collaboration avec l'hôpital Tenon nous permet d'analyser des données privées concernant le cancer du sein. Nous développons alors une méthode exacte, nommée delta-test, enrichie par la suite d'une méthode permettant la sélection automatique du nombre de variables. Dans un deuxième temps, nous développons une méthode heuristique de sélection de variables, nommée ABEUS, basée sur l'optimisation des performances du classifieur DLDA. Les résultats obtenus sur des données publiques montrent que nos méthodes permettent de sélectionner des sous-ensembles de variables de taille très faible,ce qui est un critère important permettant d'éviter le sur-apprentissage / This PhD thesis explains the recent issue concerning the resolution of high-dimensional problems. We present methods designed to solve them, and their applications for feature selection problems, in the data mining field. In the first part of this thesis, we introduce the stakes of solving high-dimensional problems. We mainly investigate line search methods, because we consider them to be particularly suitable for solving such problems. Then, we present the methods we developed, based on this principle : CUS, EUS and EM323. We emphasize, in particular, the very high convergence speed of CUS and EUS, and their simplicity of implementation. The EM323 method is based on an hybridization between EUS and a one-dimensional optimization algorithm developed by F. Glover : the 3-2-3 algorithm. We show that the results of EM323 are more accurate, especially for non-separable problems, which are the weakness of line search based methods. In the second part, we focus on data mining problems, and especially those concerning microarray data analysis. The objectives are to classify data and to predict the behavior of new samples. A collaboration with the Tenon Hospital in Paris allows us to analyze their private breast cancer data. To this end, we develop an exact method, called delta-test, enhanced by a method designed to automatically select the optimal number of variables. In a second time, we develop an heuristic, named ABEUS, based on the optimization of the DLDA classifier performances. The results obtained from publicly available data show that our methods manage to select very small subsets of variables, which is an important criterion to avoid overfitting
|
89 |
Ballstering : un algorithme de clustering dédié à de grands échantillons / Ballstering : a clustering algorithm for large datasetsCourjault-Rade, Vincent 17 April 2018 (has links)
Ballstering appartient à la famille des méthodes de machine learning qui ont pour but de regrouper en classes les éléments formant la base de données étudiée et ce sans connaissance au préalable des classes qu'elle contient. Ce type de méthodes, dont le représentant le plus connu est k-means, se rassemblent sous le terme de "partitionnement de données" ou "clustering". Récemment un algorithme de partitionnement "Fast Density Peak Clustering" (FDPC) paru dans le journal Science a suscité un intérêt certain au sein de la communauté scientifique pour son aspect innovant et son efficacité sur des données distribuées en groupes non-concentriques. Seulement cet algorithme présente une complexité telle qu'il ne peut être aisément appliqué à des données volumineuses. De plus nous avons pu identifier plusieurs faiblesses pouvant nuire très fortement à la qualité de ses résultats, dont en particulier la présence d'un paramètre général dc difficile à choisir et ayant malheureusement un impact non-négligeable. Compte tenu de ces limites, nous avons repris l'idée principale de FDPC sous un nouvel angle puis apporté successivement des modifications en vue d'améliorer ses points faibles. Modifications sur modifications ont finalement donné naissance à un algorithme bien distinct que nous avons nommé Ballstering. Le fruit de ces 3 années de thèse se résume principalement en la conception de ce dernier, un algorithme de partitionnement dérivé de FDPC spécialement conçu pour être efficient sur de grands volumes de données. Tout comme son précurseur, Ballstering fonctionne en deux phases: une phase d'estimation de densité suivie d'une phase de partitionnement. Son élaboration est principalement fondée sur la construction d'une sous-procédure permettant d'effectuer la première phase de FDPC avec une complexité nettement amoindrie tout évitant le choix de dc qui devient dynamique, déterminé suivant la densité locale. Nous appelons ICMDW cette sous-procédure qui représente une partie conséquente de nos contributions. Nous avons également remanié certaines des définitions au cœur de FDPC et revu entièrement la phase 2 en s'appuyant sur la structure arborescente des résultats fournis par ICDMW pour finalement produire un algorithme outrepassant toutes les limitations que nous avons identifié chez FDPC. / Ballstering belongs to the machine learning methods that aim to group in classes a set of objects that form the studied dataset, without any knowledge of true classes within it. This type of methods, of which k-means is one of the most famous representative, are named clustering methods. Recently, a new clustering algorithm "Fast Density Peak Clustering" (FDPC) has aroused great interest from the scientific community for its innovating aspect and its efficiency on non-concentric distributions. However this algorithm showed a such complexity that it can't be applied with ease on large datasets. Moreover, we have identified several weaknesses that impact the quality results and the presence of a general parameter dc difficult to choose while having a significant impact on the results. In view of those limitations, we reworked the principal idea of FDPC in a new light and modified it successively to finally create a distinct algorithm that we called Ballstering. The work carried out during those three years can be summarised by the conception of this clustering algorithm especially designed to be effective on large datasets. As its Precursor, Ballstering works in two phases: An estimation density phase followed by a clustering step. Its conception is mainly based on a procedure that handle the first step with a lower complexity while avoiding at the same time the difficult choice of dc, which becomes automatically defined according to local density. We name ICMDW this procedure which represent a consistent part of our contributions. We also overhauled cores definitions of FDPC and entirely reworked the second phase (relying on the graph structure of ICMDW's intermediate results), to finally produce an algorithm that overcome all the limitations that we have identified.
|
90 |
Sélection de variables pour l’analyse des données semi-supervisées dans les systèmes d’Information décisionnels / Feature selection for semi-supervised data analysis in decisional information systemsHindawi, Mohammed 21 February 2013 (has links)
La sélection de variables est une tâche primordiale en fouille de données et apprentissage automatique. Il s’agit d’une problématique très bien connue par les deux communautés dans les contextes, supervisé et non-supervisé. Le contexte semi-supervisé est relativement récent et les travaux sont embryonnaires. Récemment, l’apprentissage automatique a bien été développé à partir des données partiellement labélisées. La sélection de variables est donc devenue plus importante dans le contexte semi-supervisé et plus adaptée aux applications réelles, où l’étiquetage des données est devenu plus couteux et difficile à obtenir. Dans cette thèse, nous présentons une étude centrée sur l’état de l’art du domaine de la sélection de variable en s’appuyant sur les méthodes qui opèrent en mode semi-supervisé par rapport à celles des deux contextes, supervisé et non-supervisé. Il s’agit de montrer le bon compromis entre la structure géométrique de la partie non labélisée des données et l’information supervisée de leur partie labélisée. Nous nous sommes particulièrement intéressés au «small labeled-sample problem» où l’écart est très important entre les deux parties qui constituent les données. Pour la sélection de variables dans ce contexte semi-supervisé, nous proposons deux familles d’approches en deux grandes parties. La première famille est de type «Filtre» avec une série d’algorithmes qui évaluent la pertinence d’une variable par une fonction de score. Dans notre cas, cette fonction est basée sur la théorie spectrale de graphe et l’intégration de contraintes qui peuvent être extraites à partir des données en question. La deuxième famille d’approches est de type «Embedded» où la sélection de variable est intrinsèquement liée à un modèle d’apprentissage. Pour ce faire, nous proposons des algorithmes à base de pondération de variables dans un paradigme de classification automatique sous contraintes. Deux visions sont développées à cet effet, (1) une vision globale en se basant sur la satisfaction relaxée des contraintes intégrées directement dans la fonction objective du modèle proposé ; et (2) une deuxième vision, qui est locale et basée sur le contrôle stricte de violation de ces dites contraintes. Les deux approches évaluent la pertinence des variables par des poids appris en cours de la construction du modèle de classification. En outre de cette tâche principale de sélection de variables, nous nous intéressons au traitement de la redondance. Pour traiter ce problème, nous proposons une méthode originale combinant l’information mutuelle et un algorithme de recherche d’arbre couvrant construit à partir de variables pertinentes en vue de l’optimisation de leur nombre au final. Finalement, toutes les approches développées dans le cadre de cette thèse sont étudiées en termes de leur complexité algorithmique d’une part et sont validés sur des données de très grande dimension face et des méthodes connues dans la littérature d’autre part. / Feature selection is an important task in data mining and machine learning processes. This task is well known in both supervised and unsupervised contexts. The semi-supervised feature selection is still under development and far from being mature. In general, machine learning has been well developed in order to deal with partially-labeled data. Thus, feature selection has obtained special importance in the semi-supervised context. It became more adapted with the real world applications where labeling process is costly to obtain. In this thesis, we present a literature review on semi-supervised feature selection, with regard to supervised and unsupervised contexts. The goal is to show the importance of compromising between the structure from unlabeled part of data, and the background information from their labeled part. In particular, we are interested in the so-called «small labeled-sample problem» where the difference between both data parts is very important. In order to deal with the problem of semi-supervised feature selection, we propose two groups of approaches. The first group is of «Filter» type, in which, we propose some algorithms which evaluate the relevance of features by a scoring function. In our case, this function is based on spectral-graph theory and the integration of pairwise constraints which can be extracted from the data in hand. The second group of methods is of «Embedded» type, where feature selection becomes an internal function integrated in the learning process. In order to realize embedded feature selection, we propose algorithms based on feature weighting. The proposed methods rely on constrained clustering. In this sense, we propose two visions, (1) a global vision, based on relaxed satisfaction of pairwise constraints. This is done by integrating the constraints in the objective function of the proposed clustering model; and (2) a second vision, which is local and based on strict control of constraint violation. Both approaches evaluate the relevance of features by weights which are learned during the construction of the clustering model. In addition to the main task which is feature selection, we are interested in redundancy elimination. In order to tackle this problem, we propose a novel algorithm based on combining the mutual information with maximum spanning tree-based algorithm. We construct this tree from the relevant features in order to optimize the number of these selected features at the end. Finally, all proposed methods in this thesis are analyzed and their complexities are studied. Furthermore, they are validated on high-dimensional data versus other representative methods in the literature.
|
Page generated in 0.0736 seconds