Case-Based Reasoning for Eliciting the Evolution of
Geospatial Objects
Joice Mota†, Gilberto Camara*†, Maria Isabel Escada†, Olga Bittencourt †, Leila
Fonseca, and Lúbia Vinhas†
1
INPE – National Institute for Space Research,
Av dos Astronautas 1758,
12227-001 São José dos Campos, Brazil
{joice, gilberto, isabel, olga, leila, lubia} @dpi.inpe.br
Abstract. This paper proposes an automated approach for describing how
geospatial objects evolve. We consider geospatial objects whose boundaries and
properties change in the time, and refer to them as evolving objects. Our
approach is to provide a set of rules that describe how objects change, referred
to as rule-based evolution. We consider the case where we have a series of
snapshots, each of which contains the status of the objects at a given time.
Given this data, we would like to extract the rules that describe how these
objects changed. We use the technique of case-based reasoning (CBR) to
extract the rules of object evolution, given a few representatives examples. The
resulting rules are used to elicit the full history of all changes in these objects.
This allows finding out how objects evolved, recovering their history. As an
example of our proposed approach, we include a case study of how
deforestation evolves in Brazilian Amazonia Tropical Forest.
Keywords: Spatio-temporal data, evolving objects, Case-Based Reasoning.
1 Introduction
The computational modelling of geospatial information continues to be, after decades
of research, a challenging problem which defies a definitive solution. Since computer
models assign human-conceived geographical entities to data types, matching
geospatial data to types and classes has been the focus of intense research. Recently,
there has been much interest on modelling and representation of geospatial objects
whose properties change [1-5]. Such interest has a strong practical motivation. A new
generation of mobile devices has enabled new forms of communication and spatial
information processing. Remote sensing data is becoming widespread, and more and
more images are available to describe changes in the landscape. As new data sources
grow, we are overwhelmed with streams of data that provide information about
change.
Mota, Câmara, Escada et al.
Representing change in a GIS is not only an issue of handling time-varying data. It
also concerns how objects gain or lose their identity, how their properties change,
what changes happen simultaneously, and what causes change. We consider that
finding a unique comprehensive theory for spatio-temporal data types and operators is
arguably an unsolvable problem. This irremovable complexity is a direct outcome of
the ambiguities for defining ‘time’. Time can be viewed as an independent entity of
the universe, a dimension in which events occur in sequence. That is the view
subscribed by Newton and used in the tradition of experimental physics. A second
view is to consider time as an intellectual construct within which humans sequence
and compare events. This second view is the tradition of Leibniz and Kant. These
two opposing views lead to the controversy in the philosophy of time over whether
extension in time is analogous to extension in space, the so-called 3D/4D controversy
[6]. For a further philosophical discussion of spatio-temporal concepts, see [1] [3] [4].
Therefore, we need practical solutions that handle specific problems. We need first to
find out the needs and constrains of the application domain and then choose a suitable
approach, from the many available scientific proposals.
As Goodchild et al.[5] point out, the distinction between geospatial entities as
continuous fields or discrete objects also applies in the temporal domain. In this
paper, we deal with computational models for time-varying discrete geospatial
entities. We refer to those as geospatial objects and distinguish two broad categories.
The first category concerns objects whose position and extent change continuously,
referred to as moving objects. The second type concerns objects bound to specific
locations, but whose geometry, topology and properties change but at least part of its
position is not altered. We refer to these as evolving objects, which arise in urban
cadastre and in land cover change. For an alternative characterization of spatiotemporal objects, see Goodchild et al.[5].
This paper describes a computational model for evolving objects, which tracks
changes that occurred during an object’s lifetime. The proposed model aims to answer
questions such as “What changes took place for each object?”, “When did these
changes occur?”, and “How did the changes take place?”. We aim to extract the
history of an object from its creation to its disappearance, including references to
other objects involved. Eliciting the history of each object helps us to understand the
underlying causes of change. To be able to record the complete history of each
object, we need a model that uses previous cases as well as knowledge elicited from
an expert as the main sources of knowledge used to solve new problems. This leads to
the subject of this paper. We propose a computational method that contains a set of
rules that describe how geospatial objects evolve, based on a sample of existing cases.
These rules arise from knowledge about the application domain. Using these rules, we
can extract a detailed history of the objects and track their evolution. Our proposal
applies the Case-Based Reasoning (CBR) technique to set up the evolutionary rules,
defining a set of types for objects and a set of constraints applicable on those types.
In what follows, we review previous work on section 2 and describe our proposal
in Section 3. In section 4, we describe an experiment where we applied our method to
a spatio-temporal study of deforestation evolution. This paper builds on previous
work by the authors [7-9]
CBR for Object Evolution
2 Challenges in describing how spatial objects evolve
In this section, we consider previous work on models for evolving objects and
introduce the challenges in describing how these objects change. Evolving objects are
typical of cadastral and land change applications. Computational models for
describing such objects are also referred to as lifeline models. Lifeline models use
three ideas: identity, life, and genealogy. Identity is the characteristic that
distinguishes each object during all its life. Life is the time period from the object’s
creation until its elimination. Genealogy implies managing the changes that an object
has during its life. Hornsby and Egenhofer [10] stress the need to preserve an object’s
identity when its geometry, topology, or attributes change, a view supported by
Grenon and Smith [3]. Consider the case of parcels in an urban cadastre. A parcel can
change its owner, be merged with another, or split into two. A possible approach is to
describe an object’s history based on operations such as creation, splitting and
merging [10, 11]. However, these authors do not consider the problem of extracting
the evolution rules from the objects themselves. They also only consider objects of a
single type. In this paper, we consider objects of different types and we provide ways
to extract their evolution rules.
Fig. 1 – Example of object evolution
To take a simple motivational example, consider Figure 1, where there are three
objects: S1 of type ‘Street’ and P1 and P2 of type ‘Parcel’. Given the geometries of
these objects at times T1 and T2, how can we find out how these objects evolved? To
model this example, we need to consider different rules for spatial operations.
Consider the case of the ‘merge’ geometric operation, which joins the geometries of
two objects. When the objects have different types, merging two objects can produce
different results. When the object types are ‘Street’ and ‘Parcel’, there should be
different rules for the result of the merging two objects. One possible set of rules is:
(a) “merging two Parcels results in a Parcel”; (b) “merging a Street with a Parcel
results in expanding the Street”.
As a second example, consider how the internal and external borders of Brazil
changed, as shown in Figure 2. Each polygon in Figure 2 is a Brazilian state. The
Mota, Câmara, Escada et al.
Brazilian borders have changed significantly since the 18th Century, both because of
internal division (creation of new states from existing ones) and inclusion of external
areas (through international treaties). Suppose we want to devise a procedure that,
given the snapshots shown in Figure 2, tries to extract the history of Brazil´s internal
and external borders. Such a method would have to distinguish at least three data
types (‘Country’, ‘State’, ‘ExternalArea’) and would need a set of type-dependent
rules for object merging and splitting. As a first guess, this set would have these rules:
R1. Splitting an existing State produces two States: a new State and the existing
State with a smaller area.
R2. An existing State can be converted into a new State with the same borders.
R3. Merging a State with an existing State produces a State with lager area. The
new area is assigned to an existing State.
R4. Merging a Country with an External Area produces a Country with larger
area. The new area is assigned to an existing State.
R5. Splitting a State from a Country produces a Country with smaller area and a
new part of the External Area.
Fig. 2 – Evolution of internal and external borders of Brazil from 1709 to 1990.
These rules are not the only possible set. They may be able to rebuild a believable
history of the Brazilian states, but may fail to be historically accurate. Given a set of
snapshots which show that state of spatial objects in different times, we are not
always able to remake their precise history. However, often the snapshots are all we
have, and we need to devise ways to make a likely guess about the objects’ evolution.
These examples and similar cases lead us to propose the idea of rule-based
evolution of typed geospatial objects. Our view of types comes from Computer
Science, where types are tools for expressing abstractions in a computer language
CBR for Object Evolution
[12]. On a theoretical level, a type is a set of elements in a mathematical domain that
satisfy certain restrictions. A typed object is an object whose evolution is subject to
constraints that are specific to its type. Thus, in the Brazilian borders example, objects
of type ‘Country’ and those of type ‘State’ use different rules to describe their
evolution. Models where objects have different types and evolution cases are richer
and more powerful than typeless ones.
3. Extracting the Evolution Rules using Case-Based Reasoning
In this section, we describe the use of Case-Based Reasoning (CBR) to extract the
evolution rules for a set of geospatial objects. CBR is a method for problem solving
that relies on previously used solutions to solve similar problems [13]. In contrast to
techniques that rely solely on general knowledge of a problem domain, CBR is able
to use the specific knowledge of previously experienced, concrete problems [14]. This
is a recurring technique in human-problem solving. To solve a new problem, we recall
how we handled a similar one in the past and try to reuse it. A new problem is solved
by finding a similar past case and reusing it in the new problem. CBR is an
incremental technique, since experience learned in a case is applied for solving future
problems.
Traditional rule-based inferences have no memory of previous cases, and use the
same set of rules for solving all problems. Instead of doing inferences using a large
group of rules, a CBR-based software keeps track of previous cases. When confronted
with a new problem, it tries to adapt rules that were useful in similar cases, thus
increasing continually its knowledge base [14]. The similarity between two problems
can often ensure the interpretation adopted for a previous case can also adopted for
the new one.
There are two types of CBR implementations: automatic procedures and
information recovery methods [13]. Automatic systems solve the problem in an
autonomous way and provide methods to evaluate the results of their decisions.
Information recovery methods use human experts to set up the problem-solving rules
based on well-known examples. These rules are then used to perform the desired task.
The current work uses a CBR software of the second type. Following [14], our
proposed CBR technique has the following main steps: 1) Select a set of exemplary
cases in the database; 2) Use these cases to set up a set of evolution rules with the
help of a domain expert; 3) Test the proposed solution and, if necessary, revise it; and
4) Store the experience represented in the current set of rules for future reuse. The
steps to model and to represent how spatio-temporal objects evolve (shown in Figure
3) are:
1.
Retrieval of snapshots of the area that contains a set of geospatial objects
whose history we want to describe.
2.
Select a subset of this data that allows the human expert to find out the
different types of geospatial objects and set up their evolution rules.
Mota, Câmara, Escada et al.
3.
Represent these evolution rules using CBR.
4.
Recover all objects from the database and compute their history based on
the evolution rules.
Fig. 3. General view of CBR method for eliciting geospatial objects evolution.
The domain expert defines two types of rules for defining the objects’ evolution:
description rules and evolution rules. The description rules define the types of
geospatial objects. The progression rules define how objects evolve under spatial
operations such as ‘split’ and ‘merge’. The expert defines the description rules
considering the objects’ properties and their spatial relationships, including
topological predicates such as ‘cross’, ‘close to’ and ‘touch’. Consider Figure 4,
where some prototypical land change objects are portrayed. Figure 4(a) shows three
objects at time T1. At time T2, three new objects appear as shown in Figure 4(b).
After application of the description and progression rules described below, the
resulting objects are shown in Figure 4(c).
In this case, the description rules define the existence of three types of objects:
Large Geometric (LG), Linear (LI8) and Small Geometric (SG), according to the
following rules:
DR1. An object with perimeter/area ratio smaller than 50 is a Linear object.
DR2. An object with perimeter/area ratio greater than 50 and whose area is less
than 10 hectares is a Small Geometric object.
DR3. An object with perimeter/area ratio greater than 50 and whose area is more
than 10 hectares is a Large Geometric object.
These rules allow us to identify the objects in Figure 4, as shown in the labels
assigned to each object. For this case, a possible set of evolution rules would be:
ER1. A Small Geometric object that touches a Large Geometric object is merged
with the Large Geometric object.
ER2. Two adjacent Small Geometric objects are merged.
ER3. Two Linear objects that are adjacent are not merged.
CBR for Object Evolution
Fig. 4 – Evolution of prototypical land change objects: (a) Time T1; (b) Time T2 before
application of evolution rules; (c) Time T2 after application of evolution rules.
Applying these rules, the Small Geometric objects shown in Figure 4(b) are
merged with the adjacent Large Geometric objects, thus resulting in a spatial
expansion of the latter objects. This example shows the need for a software
organization that is able to represent the description and evolution rules and apply
them to extract the history of a set of objects. We describe this organization is in the
next section.
4. CBR-based Geospatial Object History Extractor
This section describes the architecture of the geospatial history extractor that uses
CBR (Case-based reasoning). A CBR software stores knowledge as a set of cases.
Each case contains data about a specific episode, with its description and the context
it can be used [15]. The contents of each case include a set of rules set up by the
domain expert. Among the several existent techniques for knowledge acquisition for
CBR [16], we used unstructured interviews, where the information is obtained
through direct conversation with the specialist. In these interviews, he gives his
perspective of the problem, and a computer specialist records these cases. The expert
elicits the knowledge domain in two steps. First, he describes the objects in their
environment (description rules). Second, he analyses thes outcome of spatial
operations between the objects (evolution rules). After the expert produces the rules,
the CBR software stores a set of rules for each case, as shown in Figure 5.
Mota, Câmara, Escada et al.
Fig. 5 – Example of case construction based on expert rules
The knowledge base consists of a series of cases, indexed by the object´s attributes.
Based on the problem´s description, the indexes point out which attributes should be
compared, finding out the case that can be useful for the solution. Each attribute
receives a weight according to their degree of importance in the solution of the case.
In our model, we built the indexes using an explanation-based technique, where the
specialist points out which attributes are relevant for the solution of the problem[17].
Figure 5 shows the indexes for the cases that described the problem described in
Figure 4. The indexes for the description rules are area and perimeter/area ratio; the
indexes for evolution cases are the object types and their spatial relationship.
CBR for Object Evolution
After creating and indexing the knowledge base, we can then create the history of
all objects. Each object is considered to be a new problem and processed separately in
two phases (see Figure 6). Processing starts by taking the objects from the Geospatial
Objects Database that contains snapshots of the geospatial objects at different
moments. For the example shown in Figure 2 (evolution of Brazil´s borders), the
database would contain six snapshots for the years 1709, 1789, 1822, 1889, 1943 and
1990. The CBR system starts at the earliest snapshot. For each object in each
snapshot, the CBR tries to find out its type based on the Description Cases Database
that contains a set of cases, defined by a domain expert. The CBR system measures
the similarity between each case stored in the database and the new object, according
to their attribute values. Expressed as a real number between 0.0 (no similarity) and 1
(equality), similarity is calculated for each case in the database according to the
attribute values. The software recovers the best match, shows it to the expert for
confirmation, and stores the confirmed solutions in the Typed Geospatial Objects
Database. After processing all the information from the first snapshot, the software
recovers all objects from the next snapshot in the Geospatial Objects Database. It
describes them according to the rules of the Description Cases Database and stores
them in the Typed Geospatial Objects Database.
Fig. 6. CBR System Architecture for Geospatial Object History Extraction
The second phase of the CBR-based software takes the objects from two
consecutive snapshot of the Typed Geospatial Objects Database to describe their
evolution. It compares the objects from the two consecutive snapshots according to
the rules of the Evolution Cases Database. These rules consider the objects’ spatial
relationships to find out if two objects should be merged or if an object should be split
Mota, Câmara, Escada et al.
and then joined with another. The software creates the history of each object and
stores it in History Objects Database. Thus, the method has the following steps,
considering the snapshots are stored in increasing temporal order, taking time as a
sequence T={1, …, n}:
1.
Let T = 1.
2.
Take the objects from time T from the Geospatial Objects Database.
Describe these objects according to the Description Cases Database.
Store the results in the Typed Geospatial Objects Database.
3.
Take the objects from time T+1 from the Geospatial Objects Database.
Describe these objects according to the Description Cases Database.
Store the results in the Typed Geospatial Objects Database.
4.
Compare the objects of times T and T+1 using the Evolution Cases
Database. Evolve the objects if possible. Store the results in a History
Objects Database.
5.
If there are further snapshots in the Geospatial Objects Database, make T
= T+1 and go to step 2 above. Otherwise, exit the program.
To better explain the possible uses of the proposed technique, we present a case
study using real data in the next section.
5. Land change objects in Brazilian Amazonia: a case study
This section presents a case study about extraction of the history of geospatial objects
associated to deforestation areas in the Brazilian Amazonia rainforest. It motivation is
the surveying work carried out by the National Institute for Space Research (INPE).
Using remote sensing images, INPE provides yearly assessments of the deforestation
in Amazonia region that are considered to be precise by the international community.
INPE’s measures show that close to 250,000 km2 of forest were cut in Amazonia from
1995 to 2007 [18]. Given the extent of deforestation in Amazonia, it is important to
figure out the agents of deforestation. We need to assess the role and the spatial
organization of the different agents involved in land change. Our idea is to associate
each land change patch, detected in a remote sensing image to one of the agents of
change. Extensive fieldwork points out the different agents involved in land use
change (small-scale farmers, large plantations, cattle ranchers) can be distinguished
by their different spatial patterns of land use [19] [20]. These patterns evolve in time;
new small settlements emerge and large farms increase their agricultural area at the
expense of the forest. Farmers also buy land from small settlers to increase their
property for large-scale agriculture and extensive cattle ranching. Therefore, our CBR
technique will aim to distinguish land change objects based on their shapes and spatial
arrangements.
For our case study, we selected a government-planned rural settlement called Vale
do Anari, located in Rondônia State, Brazilian Amazonia Tropical Forest. This
settlement was established by INCRA (Colonization and Land Reform National
CBR for Object Evolution
Institute) in 1982, with lots size of around 50 ha (see Figure 8). The choice considered
two reasons: one of the authors has done extensive fieldwork on the area [21, 22], and
this area had already been studied in a previous work [9]. In this previous work, Silva
et al [9] used a decision-tree classifier to describe shapes found in land use maps
extracted from remote sensing images. They then associated these shape descriptions
to the different types of social agents involved in land use change.
Fig. 8. Location of the study area. The Brazilian Amazonia is on the left, and the Vale do Anari
area in the state of Rondônia is on the right. Light-coloured areas point to deforestation.
Silva et al.´s work did not find out how individual objects evolved, but presented
his results simply comparing the overall types of objects found in each snapshot.
Since his work found good descriptive rules for the different object types, it motivated
the authors to use the CBR technique for eliciting the history of the objects in the
Vale do Anari region. In our study, we distinguish three types of land change objects:
Small Lot (LOTS), Along Road Occupation (AR) and Concentration Areas (CON).
The characteristics of those objects are:
• Small Lot: Small settlement household colonists living on subsistence agriculture
or small cattle ranching. Their spatial patterns show up as linear patterns following
planned roads built during earlier stages of colonization.
• Along Road Occupation: Small household colonists associated to settlement
schemes living on subsistence agriculture or small cattle ranching. Their spatial
patterns show up as irregular clearings near roads, following parcels defined by
the planned settlement.
• Concentration: Medium to large farmers, associated to cattle ranches larger than 50
ha. This pattern results from selling several 50 ha lots to a farmer aiming to enlarge
his property. Their spatial patterns are regular ones, close to roads or population
nucleus.
Mota, Câmara, Escada et al.
To describe these object types, we use both, their geometric attributes and their
spatial relations, as shown in Table 2. We define a linear shape as an object with
perimeter/area ratio greater than 50. An irregular shape is an object with a
perimeter/area ratio smaller than 10 and an area smaller than 50 ha. A regularly
shaped object is one with a perimeter/area ratio smaller than 50 and an area greater
than 50 ha. The spatial relation used to distinguish this object type is its adjacency to
roads. This rule considers that early settlers in the region occupied and cleared their
lots preferably close to the roads, ensuring accessibility to urban nucleus and services.
Table 2. Description of deforestation objects
Example
Geometry
Spatial relation
Object Type
Linear shape
Touches the road
Along road
occupation
Linear shape
Doesn´t touch the
road
Small lot
Irregular shape
Touches the road
Along road
occupation
Irregular shape
Doesn’t touch the
road
Small lot
Geometric
shape
Indifferent
Concentration
Thus, the Description Rules (DR) for deforestation objects are:
DR1. “A geometric spatial pattern is an object of type land concentration”.
DR2. “An irregularly shaped pattern that touches a road is an object of type along
road occupation”.
DR3. “An irregular spatial pattern doesn’t touch a road is an object of type small
lot”.
CBR for Object Evolution
DR4. “A linear spatial pattern that touches a road is an object of type along road
occupation”.
DR5. “A linear spatial pattern that doesn’t touch a road is an object of type small
lot”.
A subset of the deforestation objects in the Vale do Anari is shown in Figure 9.
The sequence starts with objects representing 1982-1985 deforestation on its right
side. The next set of deforestation objects represents new deforested areas detected
during the 1985-1988 period and so forth. These three year snapshots show how
deforestation occurred; the objects’ labelling was confirmed by experts on
deforestation domain. On the left side of Figure 9 the deforestation objects detected in
the intervals of three years are shown and linked to an attribute table by an
identification number.
After setting up the definition rules, the next step is defining the evolution rules
that will make up the history of the object. These rules depend on the object´s type as
well as its adjacency relation with the other objects. An object of type along road
occupation does not evolve, since it signals the start of the occupation. When objects
of type small lot touch each other, they are merged creating a new small lot. When an
object of the concentration type touches an object of types concentration or small lot,
they are merged and the result is a new concentration. A small lot object type with
area greater than 50 ha represents the results of small lots objects that evolved along
time. If a concentration object type touches a small lot object with area greater than
50 ha it doesn´t evolve. The evolution rules for typed deforestation objects are:
ER1 – “Two adjacent land concentration objects are merged and the new object is
a land concentration”.
ER2 – “An object of type along road occupation is not merged with other objects”.
ER3 – “Two adjacent small lot objects are merged and the new object produced is
a small lot”.
ER4 – “A small lot with area < 50 ha adjacent to a land concentration object is
merged with it and the result is a land concentration object”.
ER5 – “A small lot with area >= 50ha and adjacent to a land concentration object
is not merged with other object.”
Mota, Câmara, Escada et al.
Fig. 9. Sequence of deforestation objects
The CBR software builds the Description Cases Database using the description
rules and the Evolution Cases Database using the evolution rules. After creating these
databases, it considers all deforestation objects using the procedure described in
Section 4 above. For each new object, it looks for a similar case in Description Cases
Database to define its type. The next step is to apply the evolution rules. Given an
object´s type and spatial arrangements, the CBR software looks for similar cases in
CBR for Object Evolution
the Evolution Cases Database. Based on these cases, it finds out the history of each
object, which is stored for later retrieval. For each object, the history database keeps
track of its evolution, including the originating objects (if the new objects results from
a merge operation). The results produced by the CBR for a sample of the
deforestation objects are presented in Figure 10.
Figure 10. Example of the history of deforestation objects.
Mota, Câmara, Escada et al.
The report of the object’s history shows how deforestation objects evolved. Until
1991, no objects evolved due to rule ER2: “An object of type along road occupation is
not merged with other objects”. In 1991, the object 478 merged with the object 341
following rule ER3 (“Two adjacent small lot objects are merged and the new object is
a small lot”) and the result is the object 1. Also in 1991, object 497 merges with
object 42 according to rule ER4 (“A small lot with area < 50 ha adjacent to a land
concentration object is merged with it and the result is a land concentration object”),
creating object 2. In 1994, land concentration object 486 appears and merges with
objects 345 and 43 following rule ER4, creating object 4. In the same year, object 2
merges with object 507 again following rule ER4, creating object 5. In 1994 object 5
merges with object 4 following rule ER1 (“Two adjacent land concentration objects
are merged and the new object is a land concentration”), creating object 6. Object 6
is again expanded, producing object 7 when merges with object 1. In 1997, object 7
merges with objects 725, creating object 8. Then it merges with object 783, creating
object 9, and finally merges with object 799, producing object 10. The CBR software
was thus able to show how land concentration occurred in the region, pointing out the
government plan for settling many colonists in the area has been largely frustrated
[21]. The process of land concentration in the Vale do Anari settlement described by
the CBR software matches what was noted in the interviews performed during
fieldwork [21].
6. Conclusions
In this paper, we deal with evolving objects. We are interested in cases where the
simple rules of merging and splitting are not enough to describe their evolution, since
such evolution depends on the object´s types. We propose a method that uses previous
cases as well as knowledge elicited from a specialist as the main sources of
knowledge used to solve new problems. A contribution of our research is the
definition a case-based reasoning (CBR) method to describe the object´s type and find
out how geospatial objects evolve. Experimental results for the Brazilian Amazonia
Tropical Forest corroborate the effectiveness of our proposal. The approach of using
typed geospatial objects and evolution rules contributes to solve the problem of
automatically modelling and describing the history of evolving geospatial objects.
Use of the CBR software for describing object evolution follows form the work of
Silva et al. [9] that developed a method for distinguishing patterns of land use change
based on their shapes in static timestamps. Their work did not discuss how spatial
patterns evolve in time. The current work addresses the problem of tracking changes
during an object’s lifetime, based on type-specific evolution rules. In our experiments
using case-based reasoning (CBR), we were able to obtain the rules for object
evolution and to describe how geospatial objects evolve. The CBR technique proved
to be a simple and useful approach to set up the rules for land change trajectories.
In our application domain, CBR presented a satisfactory result, since the
knowledge base had only a few cases, which were presented to the expert in an
organized way. When there are many data types and different cases, the knowledge
base should be generated carefully to avoid conflicting and inconsistent
CBR for Object Evolution
interpretations. Additionally, despite advanced techniques for case indexing and
retrieval (neural networks, genetic algorithms), a knowledge base with many cases
can have a slow and bad performance. In such cases, the CBR software needs to
include adaptation and learning techniques, which also detect inconsistencies in the
rules. In this case, the rules would be changed according to the expert´s reaction to
examples being presented to him. Adaptation and learning are complex and errorprone techniques that, if not done properly, may result in further inconsistencies in the
knowledge base. Therefore, many CBR softwares do not provide an adaptation and
learning facility. They simply recover the most similar case and make the solution
available for the specialist to determine if it solves his matching problem.
Our experience shows that CBR-based techniques are useful and simple to set up
for recovering the history of evolving geospatial objects when there are few types and
clear-cut rules for object description and evolution. When there are many types and
the evolution rules are complex, the CBR software needs to be carefully designed, and
should include a learning phase and techniques for detecting inconsistencies and
conflicts. In our work, we consider the CBR software we designed in promising
enough; so we plan to extend these CBR techniques for improving the study of land
cover change evolution in the Brazilian Amazonia region.
Acknowlegments. Gilberto Camara’s work is partly funded by CNPq (grants PQ –
300557/19996-5 and 550250/2005-0) and FAPESP (grant 04/11012-0). Olga
Bittencourt’s work is funded by CAPES.
References
1. Frank, A.: Ontology for Spatio-temporal Databases. In: Koubarakis, M., Sellis, T. (eds.):
Spatio-Temporal Databases: The Chorochronos Approach. Springer, Berlin (2003) 9-78
2. Worboys, M.: Event-oriented approaches to geographic phenomena. International Journal
of Geographical Information Science 19 (2005) 1-28
3. Grenon, P., Smith, B.: SNAP and SPAN: Towards Dynamic Spatial Ontology. Spatial
Cognition & Computation 4 (2003) 69-104
4. Galton, A.: Fields and Objects in Space, Time, and Space-time. Spatial Cognition and
Computation 4 (2004) 39-68
5. Goodchild, M.F., Yuan, M., Cova, T.J.: Towards a general theory of geographic
representation in GIS. International Journal of Geographical Information Science 21 (2007)
239–260
6. Markosian, N.: Time. In: Zalta, E.N. (ed.): The Stanford Encyclopedia of Philosophy
(Winter 2008)
7. Bittencourt, O., Câmara, G., Vinhas, L., Mota, J.S.: Rule-based evolution of typed
spatiotemporal objects. In: VIII Brazilian Symposium in Geoinformatics, GeoInfo2007,
Campos do Jordão, Brazil (2007)
8. Mota, J.S., Câmara, G., Fonseca, L.M.G., Escada, M.I.S., Bittencourt, O.: Applying casebased reasoning in the evolution of deforestation patterns in the Brazilian Amazonia. .
Proceedings of the 2008 ACM Symposium on Applied Computing (Fortaleza, Ceara,
Brazil, March 16 - 20, 2008). SAC '08. , ACM, New York, NY (2008) 1683-1687
Mota, Câmara, Escada et al.
9. Silva, M.P.S., Câmara, G., Escada, M.I., Souza, R.C.M.: Remote Sensing Image Mining:
Detecting Agents of Land Use Change in Tropical Forest Areas. International Journal of
Remote Sensing 29 (2008) 4803-4822
10. Hornsby, K., Egenhofer, M.: Identity-Based Change: A Foundation for Spatio-Temporal
Knowledge Representation. International Journal of Geographical Information Science 14
(2000) 207-224
11. Medak, D.: Lifestyles. In: Frank, A.U., Raper, J., & Cheylan, J.-P. (ed.): Life and Motion of
Socio-Economic Units. ESF Series. Taylor & Francis, London (2001)
12. Cardelli, L., Wegner, P.: On Understanding Type, Data Abstraction, and Polymorphism.
ACM Computing Surveys 17 (1985) 471-552
13. Kolodner, J.: Case-based reasoning. Morgan Kaufmann Publishers Inc. San Francisco, CA,
USA (1993)
14. Aamodt, A., Plaza, E.: Case-based reasoning: foundational issues, methodological
variations and system approaches. AI Communications 7(1) (1994) 39–59
15. Wangenheim, C.G., Wangenheim, A.: Raciocínio Baseado em Casos, Barueri: São Paulo.
(2003)
16. Motoda, H., Mizoguchi, R., Boose, J., Gaines, B.: Knowledge Acquisition for KnowledgeBased Systems. IEEE Expert: Intelligent Systems and Their Applications 6 (1991) 53-64
17. Lorenzi, F., Abel, M.: Aplicando raciocínio baseado em casos na investigação de
irregularidades nas internações hospitalares (Applying CBR for investigating problems in
hospitals). Brazilian Computer Congress, Itajaí, SC. (2002) 13
18. INPE: Monitoramento da Floresta Amazônica Brasileira por Satélite (Monitoring the
Brazilian Amazon Forest by Satellite). National Institute for Space Research, Sao José dos
Campos (2008)
19. Lambin, E.F., Geist, H.J., Lepers, E.: Dynamics of land-use and land-cover change in
Tropical Regions. Annual Review of Environment and Resources 28 (2003) 205-241
20. Silva, M.P.S., Câmara, G., Escada, M.I.S., Souza, R.C.M.: Remote Sensing Image Mining:
Detecting Agents of Land Use Change in Tropical Forest Areas. International Journal of
Remote Sensing 29 (2008) 4803-4822.
21. Escada, M.I.: Evolução de Padrões da Terra na Região Centro-Norte de Rondônia
(Evolution of Land Use Patterns in the Center-North Region of Rondônia). PhD Thesis in
Remote Sensing. Instituto Nacional de Pesquisas Espaciais, São José dos Campos (2003)
164 p.
22. Soler, L., Escada, M., Verburg, P.: Quantifying deforestation and secondary forest
determinants for different spatial extents in an Amazonian colonization frontier (Rondonia).
Applied Geography 29 (2009) 182-193