Mining evolutions of complex spatial objects using a single-attributed Directed Acyclic Graph
- PDF / 2,630,585 Bytes
- 41 Pages / 439.37 x 666.142 pts Page_size
- 33 Downloads / 234 Views
Mining evolutions of complex spatial objects using a single-attributed Directed Acyclic Graph Frédéric Flouvat1 · Nazha Selmaoui-Folcher1 · Jérémy Sanhes1 · Chengcheng Mu1 · Claude Pasquier2 · Jean-François Boulicaut3 Received: 8 June 2018 / Accepted: 20 May 2020 © Springer-Verlag London Ltd., part of Springer Nature 2020
Abstract Directed acyclic graphs (DAGs) are used in many domains ranging from computer science to bioinformatics, including industry and geoscience. They enable to model complex evolutions where spatial objects (e.g., soil erosion) may move, (dis)appear, merge or split. We study a new graph-based representation, called attributed DAG (a-DAG). It enables to capture interactions between objects as well as information on objects (e.g., characteristics or events). In this paper, we focus on pattern mining in such data. Our patterns, called weighted paths, offer a good trade-off between expressiveness and complexity. Frequency and compactness constraints are used to filter out uninteresting patterns. These constraints lead to an exact condensed representation (without loss of information) in the single-graph setting. A depth-first search strategy and an optimized data structure are proposed to achieve the efficiency of weighted path discovery. It does a progressive extension of patterns based on database projections. Relevance, scalability and genericity are illustrated by means of qualitative and quantitative results when mining various real and synthetic datasets. In particular, we show how such an approach can be used to monitor soil erosion using remote sensing and geographical information system (GIS) data.
This research was supported by the Project FOSTER ANR-2010-COSI-012-01 funded by the French Ministry of Higher Education and Research.
B
Frédéric Flouvat [email protected] Nazha Selmaoui-Folcher [email protected] Claude Pasquier [email protected] Jean-François Boulicaut [email protected]
1
ISEA, University of New Caledonia, BP R4, 98851 Nouméa, New Caledonia
2
CNRS, I3S, Université Côte d’Azur, Nice, France
3
LIRIS UMR5205, CNRS, INSA de Lyon, 69621 Villeurbanne, France
123
F. Flouvat et al.
Keywords Graph mining · Spatiotemporal data · Attributed DAG · Weighted path · Environmental monitoring
1 Introduction Analysis and management of environmental risks are major issues in today’s world. These last years, a huge amount of data has been collected to monitor the environment. One of the main challenges with such data is to understand and predict dynamics of ecosystems affected by global climate change and local human activity. However, underlying phenomena and collected data are complex. A large number of spatial objects evolve over long periods of time. Moreover, each object may be related to several heterogeneous information (e.g., landcover, weather, soil type, topology) that may explain or influence their evolution. Objects may also move and change (as illustrated in Fig. 1). For example, soil erosion may grow, shrink, move,
Data Loading...
