In this paper, we present a knowledge discovery process applied to hydrological data. To achieve this objective, we combine successive methods to extract knowledge on data collected at stations located along several rivers. Firstly, data is pre processed in order to obtain di erent spatial proximities. Later, we apply two algorithms to extract spatiotemporal patterns and compare them. Such elements can be used to assess spatialized indicators to assist the interpretation of ecological and rivers monitoring pressure data.
In response to the rapidly rising and widespread use of database technology
including heterogeneous, geo-referenced and multidimensional data -, there is
a growing interest in developing new techniques for extracting knowledge from
data. These techniques are the subject of the emerging eld of Knowledge
Discovery in Databases (KDD). The KDD process is de ned as the multi-steps
process of discovering valid, novel, and potentially useful knowledge from large
databases [
The KDD process can be very complex and the steps may change signi
cantly depending on data origin. For instance, when data are geo-referenced,
KDD process is considerably limited because spatial information is not easy
to discern and can provide additional information. Currently, research in
geographic knowledge discovery (i.e., KDD on spatial databases) is very active [
In this context, this paper focus on the impact of spatial components of data on the KDD process. For this, we propose a KDD process including two steps: rst, we pre process the data in order to divide the space using two original spatialization approaches. Finally, we apply two di erent data mining techniques enabling to extract two semantically di erent kinds of spatiotemporal patterns. These techniques have been compared and di erences were widely discussed in this paper.
This paper shows the current state of a PhD thesis, which focus on understand and modelize spatiotemporal phenomena. This thesis is under direction of Prof. Maguelonne Teisseire, Prof. Nazha Selmaoui-Folcher, Prof. Sandra Bringay and Prof. Frederic Flouvat.
The water system, structuring landscapes and ecosystems of metropolitan France, covers more than 500000 km. divided into 6 water supply agencies containing several watersheds1. This structure is a fragile environment subject to the presence of many economic activities and usages that have increased the vulnerability of the water resources including rivers, canals, lakes, etc. In this context, river pollution is a phenomenon that is observed by measuring physicochemical and biological indicators for water quality. These indicators, which evolve over time and depend explicitly on the location of sampling stations strategically located along several rivers.
Two types of data are available: (1) static informations related to the station itself, e.g., its location (coordinates x, y), its reference code, etc., and; (2) dynamic informations which correspond to data measured by the station, e.g., the Standardized Global Biological Index (ibgn), Biological Diatom Index (ibd), the taxonomic variety (taxovar), the sh index ( shindex), etc.
This manuscript is organized as follows: In Section 2, we present our motivation and a detailed overview of the related work. Then, in Section 3, we describe our generic knowledge discovery process. Later, we apply our proposition on dataset and some patters obtained are shown. This paper ends with our conclusions and some perspectives. 2
Knowledge discovery in databases (KDD ) is a dynamic research eld. In [
In addition, the advent of GIS (Geographical Information Systems)
technology and the availability of large volume of spatiotemporal data has increased
1 In the context of surface water, a watershed is a geographic area bounded
peripherally by a water parting and draining to a common outlet: a point on a larger stream
or river, a lake, etc.
the need for e ective and e cient methods to extract unknown and unexpected
information. Unfortunately, in many situations, a simple data mining method
will often be limited in its ability to retrieve informative knowledge from
complex spatiotemporal databases [
Pre-processing and transformation steps (or more simply pre-processing)
are directly related to the data mining step because these steps have an
important impact on mining results. In [
Referring to data mining, several solutions are proposed in the literature
to extract knowledge in a spatiotemporal database. Early works addressed the
spatial and temporal dimensions separately. In [
Spatiotemporal database
Space division
Patterns extraction Watercourse ∊-neighborhood
Spatially Sequential Pattern Spatio-sequential Pattern
To our knowledge, no works have tried to mine sequential patterns at different spatial granularity levels and then combine their results to obtain more informative and general spatial patterns. In fact, the goal of spatial data mining is to discover spatial patterns and to suggest hypotheses about potential generators of this kind of patterns. This task is not straightforward and requires us to challenge the classical KDD process. In this paper we focus on spatial patterns from the perspective of space division using di erent levels of spatial granularities. This task was performed to deduce more general patterns by averaging attributes of spatial objects grouped into homogeneous areas. This rst pre-processing step was combined, in the one hand, with a classical algorithm of sequential pattern mining and, in the other hand, with a new method for extracting spatiotemporal patterns (i.e., sequences of spatial sets of events). This second data mining approach allow us to deal with the developments and interactions between the study area and its immediate environment.
Several phenomena can be studied using our KDD approach, e.g., the soil erosion, the epidemic surveillance, the river pollution, and many others. In this paper, we have applied our method on data of river pollution, but our approach has been tested also on dengue epidemiological monitoring data collected in New Caledonia. 3
Our approach is divided into three steps: (1) spatial decomposition and aggregation, and; (2) spatiotemporal patterns mining using two approaches. This general process is illustrated in Figure 1.
Spatial decomposition and aggregation are pre-processing steps in which spatial data is mapped to sequences according to di erent spatial relationships (e.g., station proximity, watercourse). Thanks to this transformation, the spatial features of data are integrated into the KDD process.
The resulting spatial sequences are used as an input of the data mining
step, which is composed of two methods. The rst one extracts spatially
frequent sequences using a classical sequential patterns mining algorithm (see, [
Data at our disposal is associated to biological indicators collected by
monitoring stations strategically positioned along several watersheds. This heterogeneous
data is also geo-referenced and temporally variable, thus making them di cult
to explore globally. Moreover, several implicit spatial relationship between
studied objects may be considered. For instance, a monitoring station is located in
upstream (or downstream) along to a speci c watercourse, and it is also located
in an agricultural zone. It is therefore necessary to perform pre-processing that
takes into account di erent spatial proximities (e.g., grouping stations according
to their distance, according to their agricultural zone, etc.). In this work, we
do not study the evolution of events for each station independently, this kind
of approaches are widely studied, e.g., see [
{ A watercourse approach: for a given watercourse, two stations X and Y located on this watercourse are considered to be neighbors. For instance, in Figure 2, stations W , X, Y and Z belong to the same watercourse, moreover, these stations are considered as a single area and their data are combined. An example of incident that can be study thanks to this approach is: a fuel out ow from a boat at station X will impact on measures of station X and later on measures on stations Y and Z located on downstream of station X. { The -neighborhood approach: the space is divided into areas grouping stations by exploiting the Lambert coordinates. In each of these areas, stations covering an area of km2 are grouped, even if these stations belong to different watercourses. For instance in Figure 3, stations W , X and Y are considered as a single area, even if they are not on the same watercourse. An example of phenomenon that can be study based on this approach is: pesticide use in a crop eld located between stations X and Y can impact on measures of stations located on rivers around this crop eld even if stations are not positioned in the same river.
Thanks to these two spatial division methods, we are able to group the stations within areas and thus to aggregate data in order to build spatial sequences, i.e., sequences containing spatial characteristics of data. Nevertheless, if we cannot perceive the "spatialization" in sequences, this feature can be evinced in patterns obtained as discussed in Section 4.1.
W
X
Y
Z !
W ! X
Y
In this section, we present two data mining methods. The rst one is a classical
algorithm ([
Sequential patterns mining: Consider the spatiotemporal database DB, illustrated in Table 1, which groups all records made by stations dispersed along several rivers (e.g. in Table 1, item A could be "good biological indicator IBGN").
Each tuple T is a transaction and consists of a triplet (id-station, id-date, itemset): the id of the station, the date of record as well as all current quality status of the river.
Let I = fi1; i2; : : : ; img the set of items (quality status). An itemset is a nonempty set of items denoted by (i1; i2; : : : ; ik) where ij is an item. A sequence S is an non-empty ordered list, of itemsets denoted by < IS1; IS2; : : : ; ISp > where ISj is an itemset.
A n-sequence is a sequence of n-itemsets. For example, consider quality status A; B; C; D and E recorded by the station Station1 according to the sequence S =< (A; E)(B; C)(D)(E) >, as shown in the Table 1. This means quality status A and E were recorded together by Station1, i.e., at the same time. Then, Station1 recorded B and C, the last items in the sequence were recorded later and separately, by the same station. In this example, S is a 4-sequence.
A sequence < IS1; IS2; : : : ; ISp > is a subsequence of another sequence < IS10; IS20; : : : ; ISm0 > if there exist integers k1 < : : : < kj < : : : < kp such as IS1 ISk01 ; IS2 ISk02 ; : : : ; ISp ISk0p . For example, the sequence S0 =< (B)(E) > is a subsequence of S because (B) (B; C) and (E) (E). However, < (B)(C) > is not a subsequence of S because the two itemsets (B) and (C) are not included in two itemsets of S. All quality status recorded by the same station are grouped and sorted by date. It is called the data sequence of the station.
A station supports a sequence S if S is included in his data sequence (S is a subsequence of the station data sequence). The support of a sequence S is calculated as the percentage of stations that support S.
Let minsupp be a minimum support set by the user, a sequence that satis es the minimum support (i.e., whose support is greater than minsupp) is a frequent sequence called a sequential pattern.
The interpretation of this rst type of patterns is strongly due to how we
preprocess data to be mined. Indeed, the main challenge of spatially frequent
sequences is to capture the spatial characteristics of data grouping stations
using di erent topologies before to data mining step. For more information,
see [
Afterwards, we present a second type of patterns whose semantics takes into account the spatial relationships (e.g., neighborhood) between stations. Spatio-sequential patterns mining: On the spatiotemporal database illustrated in Table 1, we de ne a neighborhood relationship between stations (or a set of stations), which is denoted by Neighbor, as: n Neighbor(Stationi; Stationj) = true if Stationi and Stationj are close by
Neighbor(Stationi; Stationj) = false otherwise
We de ne the In relationship between stations and itemsets which describes the occurrence of itemset IS in station S at time t in the database DB: In(IS; S; t) is true if is is present in DB for station S at time t. In our example, consider the itemset IS = (A; E) then In(IS; Station1; 2012=01=12) is true (see Table 1).
Spatial itemset. Let ISi and ISj be two itemsets, we say that ISi and ISj are spatially close if and only if In(ISi; Stationi; t) ^ In(ISj ; Stationj ; t) ^ N eighbor(Stationi; Stationj ) is true.
A pair of itemsets ISi and ISj that are spatially close, is called a spatial itemset and denoted by IST = ISi ISj .
To facilitate notations, we introduce a group operator for itemsets to be assigned by the operator (near ), denoted by []. The symbol represents the absence of itemsets in a zone. Figure 4 shows the three types of spatial itemsets that we can build with the proposed notations. The dotted lines represent spatial neighborhood relationship.
We now de ne the notion of zones evolution according to their spatial neighborhood relationship.
Spatial Sequence. A spatial sequence or simply S2 is an ordered list of spatial itemsets, denoted by s = hIST1 IST2 : : : ISTm i where ISTi , ISTi+1 satisfy the constraint of temporal sequentiality . A S2 s = h(AB)( [B; C])(P [Q; R])i is illustrated in Figure 5, where the arrows represent the temporal dynamics and the dotted lines represent the environment.
A (a)
D
The main challenge involved in the spatio-sequential patterns mining
problem is to study the evolution of characteristics/events in monitoring
stations taking into account immediate surrounding areas (for more information,
see [
More formally: Let minsupp be a minimum threshold set by the user, a spatial sequence S2 satisfying ST P i(S2) minsupp. These frequent sequences are called spatio-sequential patterns or simply S2P.
It is important to notice that both data mining methods - spatially sequential patterns and spatio-sequential patterns - can be used with any spatialization approach. For instance, monitoring station located on watercourses can be grouped by district in order to study the impact of river pollution between neighboring districts. 4
In this section, we present a qualitative evaluation by giving some examples of spatiotemporal patterns extracted by the two data mining methods. Later, these two kinds of patterns are compared semantically.
Spatially sequential patters: Table 2 shows some spatial sequential patterns extracted from RM water supply agency dataset using the -neighborhood spatialization approach. We can notice that we obtain a sequence of itemsets or set of items (events), which characterizes the evolution of a set of stations - covering 10 km2 - over time. For instance, the spatially frequent sequence h(ibd:>16.010)(ibd:(12.990;16.010] taxovar:(19.500;31.500])i can be interpreted as: frequently, a high value of IBD has been register before an decrement of IDB indicator associated to a mean value of taxonomic variety. Spatio-sequential patters: Table 3 shows some spatio-sequential patterns (S2P) extracted from RMC dataset using the watercourse spatialization approach. We may con rm that we obtain a sequence of itemsets (i.e., a set of items or events), which characterizes the evolution of a zone and its near surrounding over time. We should remember that a zone group a set of stations placed in a speci c watercourse and stations located in close watercourses compose its near surrounding.
For instance, in Table 3, the second S2P h( [ibd:<=13.325; taxovar:<=15.500; ibgn:<=4.500])i means that: often, a low values of IBD, taxonomic variety and IBGN indicators appear together, subsequently, we can assume that the water quality is seriously a ected in some watercourses belonging the RM water supply agency. Moreover, the third S2P h(ibd:>21.216)( taxovar:(17.500;29.500]) (ibd:(13.985;21.216])i can be interpreted by: In 30% of areas, a high value of IBD appear before the occurrence of a means value of taxovar in a neighbor watercourse followed by a decrement of IBD indicator. 4.1
Discusion: Spatially sequential patterns vs Spatio-sequential patterns In this data mining process, we have focused on the extraction of spatiotemporal patterns. In this context, we have proposed two methods allowing us include spatial characteristics into the obtained patterns. These two techniques di er substantially in the process and the results are semantically di erent. The rst one uses a widely used sequential pattern mining algorithm whereas the other uses a new method called spatio-sequential pattern mining. These two techniques have been performed on a real database that have been pre processed in order to divide the space into homogeneous zones following two pollution hypotheses (see Section 3.1).
The rst kind of patterns represents the evolution of a set of characteristics - biological indicators - belonging to a set of monitoring stations grouped using di erent spatial proximities. It is important to notice that, by applying the same algorithm on the same database for the same minimal support but with the two spatial division methods, we obtain two di erent sets of spatially sequential patterns. This di erence is re ected not only in the number of extracted patterns but also in their constitution themselves. To know which spatialization approach is more interesting for experts, we can apply a post processing techniques like a clustering (e.g., k-means) combined to statistical measure (e.g., sum of square for errors).
The second kind of patterns also represents changes in zones over time, nevertheless, it includes additional information, i.e., events appeared in neighboring areas. In this kind of extracted patterns, we can directly perceive the spatial relationships between neighboring areas thanks to spatial operator (close to). The extraction of this additional information impacts directly in the performance of our algorithm since the search space increases with the number of neighbors to be evaluated. In contrast, this additional information can be crucial in decisions concerning the preservation and restoration of rivers and their surrounding environments.
It is important to notice that, the rst kind of patterns are included in the second one. Indeed, the spatio-sequential pattern mining is an extension of the spatially sequential patterns mining taking into account the neighboring areas.
These two proposed approaches are generic. Indeed, we have also applied to our approaches to other real datasets, e.g., some results for epidemic monitoring of dengue fever and a visualization prototype are available on http: //datamining.univ-nc.nc/. 5
In this paper we have presented the rst steps of a data mining project on hydrological data. In particular, we applied two algorithms for spatiotemporal pattern extraction according to two spatialization approaches. Moreover, a detailed comparison between these two data mining techniques has been included in this work. We highlighted the problems that are posed depending on choices made in terms of spatialization and their in uence on the number of extracted patterns. This work has been conducted blind, i.e., without the intervention of data specialists. The results underline the di culties involved in pre-processing search data without a thorough knowledge of the study area in question.
The perspectives of this work are numerous. First, regarding the data processed, additional elements on water pressures are currently in acquisition phase. Indeed, the exact determination of the condition of the watercourse requires other indicators that are absent from the data presently studied. Then, for the extraction phase, we would like to compare di erent data mining techniques in terms of obtained patterns. In addition, a huge number of patterns have been extracted. Currently, we have proposed a new quality measure called the least temporal contradiction to lter the most relevant patterns. This measure allow us to estimate how many times a rule is veri ed vs how many times it is disabled. A pattern that is most frequently tested as disabled is a priori irrelevant. This measure is being adapted to spatio-sequential patterns.
We also have proposed a visualization prototype, which is available on http: //datamining.univ-nc.nc/ and allow us to visualize a spatial dynamic of spatio-sequential patterns extracted on dengue fever dataset.