Ph.D Jérémy Sanhes
Contribution à la fouille de données spatio-temporelles : application à l'étude de l'érosion
Download Draft here
Defended on September 25th 2014 at Nouméa
Committee
Pr. Jérôme Aze, Université Montpellier 2, LIRMM
Dr. Frédéric Flouvat, PPME, Université de Nouvelle-Calédonie, co-directeur
Dr. Florence Le Ber, ENGEES, Université de Strasbourg
Dr. Nazha Selmaoui-Folcher, PPME, Université de Nouvelle-Calédonie, co-directrice
Dr. Maguelonne Teisseire, IRSTEA, UMR TETIS et LIRMM, rapporteur
Pr. Alexandre Termier, Université Rennes 1, IRISA, rapporteur
Résumé. Les événements spatio-temporels regroupent une large diversité de phénomènes comportant des caractéristiques propres. Par exemple, l’étude de flux migratoires se révèle ainsi très différente de l’étude de propagation de maladies. En effet, le domaine d’intérêt de la première porte sur le suivi des trajectoires, tandis que celui de la deuxième porte sur les facteurs de la propagation. De plus, chaque classe d’un problème spatio-temporel peut être abordée différemment, que l’on considère ou non un voisinage spatial, une caractérisation des objets d’étude unique ou multiple, ou bien une (in)dépendance entre les événements. Ainsi, les techniques de fouilles de données développées sont souvent restées spécifiques à une sous-classe de problème spatio-temporel, c’est-à-dire sous un ensemble restreint d’hypothèses. Or, pour réussir à dégager des connaissances nouvelles à partir de données, il est nécessaire d’élargir cet ensemble d’hypothèses, c’est-à-dire élargir le champs des possibles quant aux corrélations qu’il peut exister entre événements. Nous proposons donc une modélisation de ces phénomènes spatio-temporels permettant de prendre en compte plus de considérations que dans l’état de l’art. En outre, cette modélisation permet d’exprimer des événements qui existent dans les phénomènes d’érosion : un objet d’étude peut se diviser en plusieurs objets, ou fusionner avec d’autres objets pour n’en former qu’un seul. Plus précisément, nous modélisons les dynamiques spatio-temporelles sous la forme d’un unique graphe orienté, que la composante temporelle des problèmes rend acyclique, et dont les sommets sont attribués par plusieurs caractéristiques. La fouille de données dans un unique graphe est une opération non-triviale, que la pluralité des attributs rend encore plus complexe. Nous nous concentrons sur la recherche de chemins d’attributs dans un tel graphe, sous contraintes de fréquence minimale et de non-redondance d’information. Ces contraintes, bien que très utilisées dans la littérature pour les bases de données transactionnelles, ont peu ou pas été étudiées dans le cas d’un graphe unique. Conjointement à ces contraintes primitives, il est très souvent nécessaire de filtrer l’ensemble des motifs solution qui peuvent s’avérer trop nombreux et peu pertinents. Pour cela, les experts du domaine des données étudiées doivent être sollicités, afin d’exprimer les filtres pertinents sous forme de contraintes. Il est cependant difficile et fastidieux de traduire de façon complète la connaissance d’un domaine vers des contraintes. De plus, cette traduction est susceptible d’apporter son lot d’erreurs humaines. En partant de ce constat, nous proposons d’utiliser les connaissances expertes existant dans la littérature du domaine sous la forme de modèles mathématiques. Ces modèles présentent l’avantage d’être à la fois riches et synthétiques, et leur utilisation permet de réduire l’intervention humaine. Nous nous concentrons sur le cas des fonctions mathématiques donnant un résultat dans R, que nous pouvons alors utiliser comme mesure experte ; nous en dérivons ainsi des contraintes de seuil minimum. Nous mettons en évidence des propriétés sur cette contrainte permettant d’élaguer l’espace de recherche d’itemsets fréquents, et ainsi améliorer le passage à l’échelle de l’extraction. Enfin, nous appliquons les méthodes développées à l’étude de l’érosion en Nouvelle-Calédonie. À partir de sources d’information multiples (images satellite, modèles numériques de terrain, occupation des sols, pente, géologie) et hétérogènes (à valeur numérique, ou catégorielles), nous fouillons tantôt un ensemble de pixels pour un temps donné, tantôt un unique graphe acyclique attribué. Dans le premier cas, nous recherchons des caractéristiques communes aux pixels exprimant une forte érosion selon un modèle expert. Dans le deuxième cas, nous utilisons les résultats précédents pour rechercher des successions temporelles de caractéristiques menant à des zones présentant une forte ou faible érosion. Un prototype de visualiseur permet de retrouver et de mettre en évidence les occurrences de ces chemins. Les résultats obtenus confortent l’intérêt des approches proposées. Ils mettent notamment en avant des zones connues pour leur dynamique en matière d’érosion.
Abstract.
Spatio-temporal events denote a large range of phenomena with different
characteristics. For example, migration flows studies appear to be very
different from disease spread studies. Indeed, interestingness of the
first relies on tracking trajectories, whereas the second is about
finding the factors of spread. Moreover, each class of a
spatio-temporal problem can be tackled differently, depending on which
parameters are considered: the studied spatial neighbourhood, the
number of characteristics associated with the objects, or whether
events are supposed correlated or independent. As a result, data mining
techniques are often specific to a sub-class of spatio-temporal
problem, that is to say, to a limited set of hypothesis. In order to
bring out new knowledge from data, it seems to be necessary to enlarge
this set of hypothesis, that is to say, to widen the field of
possibilities regarding correlations that may exist between events. For
this, we propose a new model that allows to take into account more
considerations than existing studies. For example, this representation
allows to model the complex spatio-temporal dynamic of erosion
phenomenon: an object can be split up in several other objects, or can
merge with other objects into one. More precisely, we use a single
directed graph, that becomes acyclic thanks to the temporal component
of the problem, and that is attributed by several characteristics.
Mining a single graph is a nontrivial operation, and is even more
complex because of the plurality of the attributes. We focus here on
searching paths of attributes, under frequency and non-redundancy
constraints. Those constraints have been largely studied for
transactional databases, but have been less studied in the case of a
single graph (or even not studied at all). Conjointly to those
primitive constraints, it is often necessary to filter the set of found
patterns that can be too numerous and/or not relevant for experts. To
do so, we need to solicit experts on the domain of the studied data.
However, it is difficult to translate a wide knowledge of a given
domain into constraints. In addition, such translation could plausibly
bring some human mistakes. From this observation, we propose to use
existing expert knowledge that has been expressed in the form of
mathematical models and published in the litterature of the domain.
These models present the advantages of being both highly informative
and synthetic; their use avoids –or greatly reduce– human intervention.
We focus on the case where those models are mathematical functions of
several variables giving a result in R, that we can use as an expert
measure to define a minimum threshold-based constraint. We highlight
some of its theorical properties enabling search space pruning for
frequent itemsets mining. Finally, we apply the two mining methods to
the study of erosion in New-Caledonia. The studied data is
heterogeneous with numerical and categorical values coming from
multiple sources (e.g. from satellite images, digital elevation model,
land cover truth or geology). We elaborate two scenarii. In the first
one, we mine a set of pixels, that can be seen as a transactional
database. We seek properties on pixels expressing a high erosion risk
according to an expert model. In the second scenario, we mine a single
attributed acyclic graph: we exploit the previous results to seek
temporal series of characteristics leading to a high or low erosion
risk. A visualisation prototype allows to remap and highlight
occurrences of these paths. The results bear out the interest of
proposed approaches. In particular, they highlights areas that are
known for their erosive dynamic.
Publications