Search

DBpedia, which encode the knowledge of Wikipedia, has become a reference for the web of data. Resources can be indexed by manually-defined categories which are not accessible by a machine.In this article, we intend to give a classificatory role to the categories (including access and use by a machine) by means of data mining techniques such as association rules and redescription mining. We compare these approaches on a dataset from DBpedia and we present our results., Le web des données s'appuie sur un ensemble de triplets codés avec RDF. Ces triplets représentent des relations entre les ressources qu'il faut pouvoir exploiter, notamment pour la recherche d'informations et autres traitements automatiques. DBpédia, qui encode les connaissances de Wikipédia, est devenue une base de référence pour le web des données. Les ressources peuvent y être répertoriées par des catégories définies manuellement, dont la sémantique n'est pas directement accessible par des machines. Dans cet article, nous proposons de donner un rôle classificatoire aux catégories (afin de permettre aux machines d'accèder et d'exploiter leur sémantique) au moyen de méthodes de fouille de données, à savoir la recherche de règles d'associations et de motifs apparentés. Nous présentons une étude comparative de ces variantes sur une partie de DB-pédia et discutons le potentiel des différentes approches.

As organisms are adapted to their environments, assemblages of taxa can be used to describe environments in the present and in the past. Here, we use a data mining method, namely redescription mining, to discover and analyze patterns of association between large herbivorous mammals and their environments via their functional traits. We focus on functional properties of animal teeth, characterized using a recently developed dental trait scoring scheme. The teeth of herbivorous mammals serve as an interface to obtain energy from food, and are therefore expected to match the types of plant food available in their environment. Hence, dental traits are expected to carry a signal of environmental conditions. We analyze a global compilation of occurrences of large herbivorous mammals and of bioclimatic conditions. We identify common patterns of association between dental traits distributions and bioclimatic conditions and discuss their implications. Each pattern can be considered as a computational biome. Our analysis distinguishes three global zones, which we refer to as the boreal-temperate moist zone, the tropical moist zone and the tropical-subtropical dry zone. The boreal-temperate moist zone is mainly characterized by seasonal cold temperatures, a lack of hypsodonty and a high share of species with obtuse lophs. The tropical moist zone is mainly characterized by high temperatures, high isothermality, abundant precipitation and a high share of species with acute rather than obtuse lophs. Finally, the tropical dry zone is mainly characterized by a high seasonality of temperatures and precipitation, as well as high hypsodonty and horizodonty. We find that the dental traits signature of African rain forests is quite different from the signature of climatically similar sites in North America and Asia, where hypsodont species and species with obtuse lophs are mostly absent. In terms of climate and dental signatures, the African seasonal tropics share many similarities with Central-South Asian sites. Interestingly, the Tibetan plateau is covered both by redescriptions from the tropical-subtropical dry group and by redescriptions from the boreal-temperate moist group, suggesting a combination of features from both zones in its dental traits and climate.

International audience; In many real-world data analysis tasks, we have different types of data over the same objects or entities, perhaps because the data originate from distinct sources or are based on different terminologies. In order to understand such data, an intuitive approach is to identify thecorrespondences that exist between these different aspects. This isthe motivating principle behind redescription mining, a data analysistask that aims at finding distinct commoncharacterizations of the same objects.This paper provides a short overview of redescription mining; what it is and how it is connected to other data analysis methods; the basic principles behind current algorithms for redescription mining; and examples and applications of redescription mining for real-world data analysis problems.

Advancements in mobile technology and computing have fostered the collection of a large number of civic datasets that capture the pulse of urban life. Furthermore, the open government and data initiative has led many local authorities to make these datasets publicly available, hoping to drive innovation that will further improve the quality of life for the city dwellers. In this paper, we develop a novel application that utilizes crime data to provide safe urban navigation. Given a model that allows us to estimate the relative probability of a crime on any road segment, we define two variants of the SafePaths problem where the goal is to find a short and low-risk path between a source and a destination locations. Since both the length and the risk of the path are equally important and they cannot be combined into a single objective, we approach the urban-navigation problemas a biobjective shortest path problem. Our algorithms aim to output a small set of paths that provide tradeoffs between distance and safety. While the solution space of such biobjective problems can be exponentially large, we design efficient algorithms that effectively exploit its structure and geometry. We enhance these algorithms with early-stopping criteria, which in practice lead to four times shorter running times with minimal sacrifices in the information content they provide to the user. In addition, using crime data from Chicago and Philadelphia we develop the required risk model for their street urban networks. Our experiments with this data demonstrate the efficacy of our algorithms and their practical applicability.

In scientific investigations data oftentimes have different nature. For instance, they might originate from distinct sources or be cast over separate terminologies. In order to gain insight into the phenomenon of interest, a natural task is to identify the correspondences that exist between these different aspects. This is the motivating idea of redescription mining, the data analysis task studied in this thesis. Redescription mining aims to find distinct common characterizations of the same objects and, vice versa, to identify sets of objects that admit multiple shared descriptions. A practical example in biology consists in finding geographical areas that admit two characterizations, one in terms of their climatic profile and one in terms of the occupying species. Discovering such redescriptions can contribute to better our understanding of the influence of climate over species distribution. Besides biology, applications of redescription mining can be envisaged in medicine or sociology, among other fields. Previously, redescription mining was restricted to propositional queries over Boolean attributes. However, many conditions, like aforementioned climate, cannot be expressed naturally in this limited formalism. In this thesis, we consider more general query languages and propose algorithms to find the corresponding redescriptions, making the task relevant to a broader range of domains and problems. Specifically, we start by extending redescription mining to non-Boolean attributes. In other words, we propose an algorithm to handle nominal and real-valued attributes natively. We then extend redescription mining to the relational setting, where the aim is to find corresponding connection patterns that relate almost the same object tuples in a network. We also study approaches for selecting high quality redescriptions to be output by the mining process. The first approach relies on an interface for mining and visualizing redescriptions interactively and allows the analyst to tailor the selection of results to meet his needs. The second approach, rooted in information theory, is a compression-based method for mining small sets of associations from two-view datasets. In summary, we take redescription mining outside the Boolean world and show its potential as a powerful exploratory method relevant in a broad range of domains., Lors de l'analyse scientifique d'un phénomène, les données disponibles sont souvent de différentes natures. Entre autres, elles peuvent provenir de différentes sources ou utiliser différentes terminologies. Découvrir des correspondances entre ces différents aspects fournit un moyen naturel de mieux comprendre le phénomène à l'étude. C'est l'idée directrice de la fouille de redescriptions (redescription mining), la méthode d'analyse de données étudiée dans cette thèse. La fouille de redescriptions a pour but de trouver diverses manières de décrire les même choses et vice versa, de trouver des choses qui ont plusieurs descriptions en commun. Un exemple en biologie consiste à déterminer des zones géographiques qui peuvent être caractérisées de deux manières, en terme de leurs conditions climatiques d'une part, et en terme des espèces animales qui y vivent d'autre part. Les régions européennes de la Scandinavie et de la Baltique, par exemple, ont des conditions de températures et de précipitations similaires et l'élan est une espèce commune aux deux régions. Identifier de telles redescriptions peut potentiellement aider à élucider l'influence du climat sur la distribution des espèces animales. Pour prendre un autre exemple, la fouille de redescriptions pourrait être appliquée en médecine, pour mettre en relation les antécédents des patients, leurs symptômes et leur diagnostic, dans le but d'améliorer notre compréhension des maladies. Auparavant, la fouille de redescriptions n'utilisait que des requêtes propositionnelles à variables booléennes. Cependant, de nombreuses conditions, telles que le climat cité ci-dessus, ne peuvent être exprimées dans ce formalisme restreint. Dans cette thèse, nous proposons un algorithme pour construire directement des redescriptions avec des variables réelles. Nous introduisons ensuite des redescriptions mettant en jeu des liens entre les objets, c'est à dire basées sur des requêtes relationnelles. Nous étudions aussi des approches pour sélectionner des redescriptions de qualité, soit en utilisant une interface permettant la fouille et la visualisation interactives des redescriptions, soit via une méthode sans paramètres motivée par des principes de la théorie de l'information. En résumé, nous étendons la fouille de redescriptions hors du monde booléen et montrons qu'elle constitue une méthode d'exploration de données puissante et pertinente dans une large variété de domaines.

International audience; We present a method for visual and interactive geospatial redescription mining. The goal of geospatial redescription mining is to characterize geospatial areas using two different descriptions, such as their bioclimatic features and fauna. Indeed, one application of geospatial redescription mining is finding bioclimatic niches, i.e. explaining the distribution of species using their bioclimatic envelope.Allowing users to find the geospatial redescriptions in an interactive way, and to see the results in clear visualizations, is fundamental for the applicability of the method. We present several goals we think a good interactive and visual redescription mining method should fulfil, and we explain how our proposed method achieves (most of) them. Finally, we also discuss some open problems in interactive redescription mining.

In scientific investigations data oftentimes have different nature. For instance, they might originate from distinct sources or be cast over separate terminologies. In order to gain insight into the phenomenon of interest, a natural task is to identify the correspondences that exist between these different aspects. This is the motivating idea of redescription mining, the data analysis task studied in this thesis. Redescription mining aims to find distinct common characterizations of the same objects and, vice versa, to identify sets of objects that admit multiple shared descriptions. A practical example in biology consists in finding geographical areas that admit two characterizations, one in terms of their climatic profile and one in terms of the occupying species. Discovering such redescriptions can contribute to better our understanding of the influence of climate over species distribution. Besides biology, applications of redescription mining can be envisaged in medicine or sociology, among other fields. Previously, redescription mining was restricted to propositional queries over Boolean attributes. However, many conditions, like aforementioned climate, cannot be expressed naturally in this limited formalism. In this thesis, we consider more general query languages and propose algorithms to find the corresponding redescriptions, making the task relevant to a broader range of domains and problems. Specifically, we start by extending redescription mining to non-Boolean attributes. In other words, we propose an algorithm to handle nominal and real-valued attributes natively. We then extend redescription mining to the relational setting, where the aim is to find corresponding connection patterns that relate almost the same object tuples in a network. We also study approaches for selecting high quality redescriptions to be output by the mining process. The first approach relies on an interface for mining and visualizing redescriptions interactively and allows the analyst to tailor the selection of results to meet his needs. The second approach, rooted in information theory, is a compression-based method for mining small sets of associations from two-view datasets. In summary, we take redescription mining outside the Boolean world and show its potential as a powerful exploratory method relevant in a broad range of domains. Tieteellinen tutkimusaineisto kootaan usein eri termistöä käyttävistä lähteistä. Näiden erilaisten näkökulmienvälisten vastaavuuksien ja yhteyksien tunnistaminen on luonnollinen tapa lähestyä tutkittavaa ilmiötä. Väitöskirjassa tarkastellaan juuri tähän pyrkivää data-analyysimenetelmää, jälleenkuvausten louhintaa (redescription mining). Jälleenkuvausten tavoitteena on yhtäältä kuvata samaa asiaa vaihoehtoisilla tavoilla ja toisaalta tunnistaa sellaiset asiat, joilla on useita eri kuvauksia. Jälleenkuvausten louhinnalla on mahdollisia sovelluksia mm. biologiassa, lääketieteessä ja sosiologiassa. Biologiassa voidaan esimerkiksi etsiä sellaisia maantieteellisiä alueita, joita voidaan luonnehtia kahdella vaihtoehtoisella tavalla: joko kuvaamalla alueen ilmasto tai kuvaamalla alueella elävät lajit. Esimerkiksi Skandinaviassa ja Baltiassa on ensinnäkin samankaltaiset lämpötila- ja sadeolosuhteet ja toisekseen hirvi on yhteinen laji molemmilla alueilla. Tällaisten jälleenkuvausten löytäminen voi auttaa ymmärtämään ilmaston vaikutuksia lajien levinneisyyteen. Lääketieteessä taas jälleenkuvauksilla voidaan löytää potilaiden taustatietojen sekä heidän oireidensa ja diagnoosiensa välisiä yhteyksiä, joiden avulla taas voidaan mahdollisesti paremmin ymmärtää itse sairauksia. Aiemmin jälleenkuvausten louhinnassa on rajoituttu tarkastelemaan totuusarvoisia muuttujia sekä propositionaalisia kuvauksia. Monia asioita, esimerkiksi ilmastotyyppiä, ei kuitenkaan voi luontevasti kuvata tällaisilla rajoittuneilla formalismeilla. Väitöskirjatyössä laajennetaankin jälleenkuvausten käytettävyyttä. Työssä esitetään ensimmäinen algoritmi jälleenkuvausten löytämiseen aineistoista, joissa attribuutit ovat reaalilukuarvoisia ja käsitellään ensimmäistä kertaa jälleenkuvausten etsintää relationaalisista aineistoista, joissa asiat viittaavat toisiinsa. Lisäksi väitöskirjassa tarkastellaan menetelmiä, joilla jälleenkuvausten joukosta voidaan valita kaikkein laadukkaimmat. Näihin menetelmiin kuuluvat sekä interaktiivinen käyttöliittymä jälleenkuvausten louhintaan ja visualisointiin, että informaatioteoriaan perustuvaa parametriton menetelmä parhaiden kuvausten valitsemiseksi. Kokonaisuutena väitöskirjatyössä siis laajennetaan jälleenkuvausten louhintaa totuusarvoisista muuttujista myös muunlaisten aineistojen käsittelyyn sekä osoitetaan menetelmän mahdollisuuksia monenlaisilla sovellusalueilla. Méthodes pour la fouille de redescriptions Lors de l'analyse scientifique d'un phénomène, les données disponibles sont souvent de différentes natures. Entre autres, elles peuvent provenir de différentes sources ou utiliser différentes terminologies. Découvrir des correspondances entre ces différents aspects fournit un moyen naturel de mieux comprendre le phénomène à l'étude. C'est l'idée directrice de la fouille de redescriptions (redescription mining), la méthode d'analyse de données étudiée dans cette thèse. La fouille de redescriptions a pour but de trouver diverses manières de décrire les même choses et vice versa, de trouver des choses qui ont plusieurs descriptions en commun. Un exemple en biologie consiste à déterminer des zones géographiques qui peuvent être caractérisées de deux manières, en terme de leurs conditions climatiques d'une part, et en terme des espèces animales qui y vivent d'autre part. Les régions européennes de la Scandinavie et de la Baltique, par exemple, ont des conditions de températures et de précipitations similaires et l'élan est une espèce commune aux deux régions. Identifier de telles redescriptions peut potentiellement aider à élucider l'influence du climat sur la distribution des espèces animales. Pour prendre un autre exemple, la fouille de redescriptions pourrait être appliquée en médecine, pour mettre en relation les antécédents des patients, leurs symptômes et leur diagnostic, dans le but d'améliorer notre compréhension des maladies. Auparavant, la fouille de redescriptions n'utilisait que des requêtes propositionnelles à variables booléennes. Cependant, de nombreuses conditions, telles que le climat cité ci-dessus, ne peuvent être exprimées dans ce formalisme restreint. Dans cette thèse, nous proposons un algorithme pour construire directement des redescriptions avec des variables réelles. Nous introduisons ensuite des redescriptions mettant en jeu des liens entre les objets, c'est à dire basées sur des requêtes relationnelles. Nous étudions aussi des approches pour sélectionner des redescriptions de qualité, soit en utilisant une interface permettant la fouille et la visualisation interactives des redescriptions, soit via une méthode sans paramètres motivée par des principes de la théorie de l'information. En résumé, nous étendons la fouille de redescriptions hors du monde booléen et montrons qu'elle constitue une méthode d'exploration de données puissante et pertinente dans une large variété de domaines.

International audience; Redescription mining is a powerful data analysis tool that is used to find multiple descriptions of the same entities. Consider geographical regions as an example. They can be characterized by the fauna that inhabits them on one hand and by their meteorological conditions on the other hand. Finding such redescriptors, a task known as niche-finding, is of much importance in biology. Current redescription mining methods cannot handle other than Boolean data. This restricts the range of possible applications or makes discretization a pre-requisite, entailing a possibly harmful loss of information. In niche-finding, while the fauna can be naturally represented using a Boolean presence/absence data, the weather cannot. In this paper, we extend redescription mining to categorical and real-valued data with possibly missing values using a surprisingly simple and efficient approach. We provide extensive experimental evaluation to study the behavior of the proposed algorithm. Furthermore, we show the statistical significance of our results using recent innovations on randomization methods.