AN ORDER-k VORONOI APPROACH TO GEOSPATIAL CONCEPT MANAGEMENT WITHIN CONCEPTUAL SPACES

Abstract

Representing concepts and their boundaries is a core task in concept management. We introduce a flexible framework for representing concept boundaries and tessellations through the complete higher order Voronoi diagrams within conceptual spaces. The framework provides different levels of concept granularity modelling vagueness and indeterminacy of concept boundaries, effectively supports complex concepts of multi-pieced regions with holes, and robustly supports concept learning and formation. We also outline a generic data structure that systematically supports our concept management framework. Experimental results demonstrate the robustness and flexibility of the proposed framework.

INTRODUCTION

Concept management is one of the core tasks in artificial intelligence. It involves concept representation, concept formation, concept learning, concept tessellation and categorization, and concept reasoning. In this series of tasks, representing concepts is an initial and central task since it greatly affects subsequent concept management processes. There exist three popular approaches for representing concepts: symbolic representation, conceptual representation, and associationistic representation (particularly connectionistic) (Gärdenfors 2000). Symbolic representation provides a high-level abstract representation while associationistic representation offers a low-level detailed representation. Conceptual representation is a midway representation bridging a gap between the too-coarse symbolic representation and the too fine-grained associationistic representation. It builds elementary properties and concepts from the associationistic representation, and feeds geometrically and topologically well-formed concepts to the symbolic representation.

Recently, the importance of conceptual representation has been emphasized and a geometry-equipped conceptual spaces approach has been widely explored (Chella, Frixione, and Gaglio 2001a; Gärdenfors and Williams 2001; Lagus, Airola, and Creutz 2002; Lee 2003, 2004; Lee and Williams 2003). It provides a robust framework for modelling properties and concepts that are core elements for concept management. In conceptual spaces, concept management is simplified by a tessellation of the space. The ordinary Voronoi diagram has been a widely adopted space tessellation method supporting both the nearest neighbor learning (well supported by the machine-learning community, Mitchell 1997) and the prototype learning (well supported by the cognitive science community, Gärdenfors 2000). Even though it provides a computationally sound data structure, its applicability is limited due to its rigidity and inflexibility. For instance, the ordinary Voronoi diagram does not systematically support complex concepts, indeterminacy of concepts, concept discovery, and concept kerneling.

In this article, we introduce a flexible space tessellation approach through the complete order-k Voronoi diagrams (OkVD) for systematic concept management within conceptual spaces. They extend the ordinary Voronoi diagram to a higher order in order to overcome its drawbacks. We propose a generic data structure to efficiently and effectively support the complete order-k Voronoi diagrams (from order-1 to order-(n − 1), where n is the number of objects). The proposed approach systematically support the following concept management capabilities:

	Modelling indeterminacy and fuzzy membership of concepts;
	Modelling complex concepts and properties with multi-pieced regions and holes;
	Modelling concepts and properties with a null region;
	Kerneling concepts and properties;
	Categorization and concept learning;
	Concept discovery and formulation;

CONCEPTUAL SPACES AND CONCEPT TESSELLATIONS

A conceptual space is seen as a collection of one or more domains and each domain consists of a number of quality dimensions. Objects are identified with multi-dimensional points (also called knoxel, Chella, Frixione, and Gaglio 2001a) within conceptual spaces, and quality dimensions represent “qualities” of an object. Each quality dimension is endowed with certain geometrical, topological, or ordering structures. A set of quality dimensions are integral and form a domain if an object cannot be assigned a value in one dimension without assigning values to others; otherwise they are separable. For instance, dimension hue, chromaticity, and brightness are integral and considered as a color domain. A set of integral dimensions are used to represent properties and a set of separable domains are used to represent concepts. A property is a region in a domain and a concept is a set of properties and their relationships within conceptual spaces. It is well known that similarity plays a key role in many cognitive tasks such as concept acquisition, formation, learning, and categorization. Conceptual spaces are geometric representations of concepts and similarity is measured by a distance metric. Similarity is measured by the Euclidean metric in intradomains while it is measured by the Manhattan metric in interdomains (Gärdenfors 2000). Recently, the conceptual spaces-based framework has been used in various applications including computer vision (Chella, Frixione, and Gaglio 2001a), cluster reasoning (Lee and Williams 2003), representing dynamic actions (Chella, Frixione, and Gaglio 2001b), and conceptual similarities of verbs (Lagus, Airola, and Creutz 2002). In addition, managing concepts and categories in data-rich environments has been studied (Gärdenfors and Williams 2001). Details of conceptual spaces can be found in Gärdenfors (2000).

In conceptual spaces, objects are represented by multi-dimensional points and a concept is formulated by a set of exemplars (previously categorized examples of objects in the concept). Therefore, representing a concept is equivalent to representing a set of exemplars. Representing a set of multi-dimensional points is typically achieved by the following two methods in conceptual spaces: a Voronoi diagram of individual (VoI) vs. a Voronoi diagram of prototype (VoP). Figure 1 depicts VoI and VoP tessellations of six examples, where three examples P ₁ = {p ₁, p ₂, p ₃} form a concept and the other three P ₂ = {p ₄, p ₅, p ₆} form another concept. Concept boundaries that distinguish these two concepts are shown as thick black polylines in this figure. In these two approaches, concepts are mutually exclusive and collectively exhaustive. These concept boundaries define regions of properties and concepts, and regionalize exemplars. They can be used for concept categorization, concept formation, and learning. Even though these two have been dominant approaches for concept tessellation and management within conceptual spaces, they suffer from several drawbacks. First, these two approaches are rigid-defining, crisp concept boundaries and regions; they are not able to represent indeterminacy of concept. Second, these two Voronoi approaches generate space tessellations that do not define any regions for a new concept; thus it is difficult for them to discover and formulate a new concept. They are able to support concept growth, but not well-suited for concept discovery and formation. Third, due to the simplicity employed in these two approaches, they do not support well for complex concepts with multi-pieced regions and null regions. Fourth, they themselves do not provide a systematic approach for concept kerneling. Table 1 summarizes concept management processes supported by VoI, VoP, and OkVD.

FIGURE 1 VoI and VoP tessellations of P = {p ₁, p ₂, p ₃, p ₄, p ₅, p ₆}: (a) VOI(P); (b) VOP(P) with prototypes in red squares.

TABLE 1 Comparison of VoI and VoP for Concept Management

Concept management capability	VoI	VoP	OkVD
Concept learning/categorization	Yes	Yes	Yes
Concept discovery/formation	No	No	Yes
Representation of multi-pieced regions	Yes	No	Yes
Representation of null regions	No	No	Yes
Representation of indeterminacy	No	No	Yes
Self-integrated concept kerneling	No	No	Yes

CONCEPT MANAGEMENT WITH THE COMPLETE ORDER-k VORONOI DIAGRAMS

Concept Boundaries and Tessellations

The ordinary Voronoi diagram tessellates the space in such a way that every location in the space is assigned to the closest generator. A set of locations closest to more than one generator formulates the ordinary Voronoi diagram consisting of Voronoi edges and vertices. Order-k Voronoi diagrams are natural and useful extensions of the ordinary Voronoi diagram to more than one generator (Okabe, Boots, Sugihara, and Chiu 2000). They provide tessellations where each region has the same k unordered closest sites for a given k. The order-k Voronoi diagram ^(k) is a set of all order-k Voronoi regions where the order-k Voronoi region for a random subset consisting of k points out of P, is defined as follows:

where, k generators are not ordered. The order-k Voronoi diagram ^(k) becomes the ordinary Voronoi diagram when k is 1 while it becomes the farthest point Voronoi diagram when k is n − 1.

When k generators are ordered, the diagram becomes the ordered order-k Voronoi diagram ^〈k〉. It is defined as , where the ordered order-k Voronoi region is defined as:

Figure 2 depicts the order-3 Voronoi diagram and ordered order-3 Voronoi diagram of P. A region in Figure 2(a) depicts an order-3 Voronoi region of P ₁ where all generators belong to the same concept. Thus, this region is indicative of the concept P ₁. Its neighboring regions (that share a Voronoi edge with ) are Voronoi regions of {p ₁, p ₂, p ₄}, {p ₁, p ₂, p ₆}, and {p ₂, p ₃, p ₆}. These neighboring regions have members that belong to different concepts. For instance, the Voronoi region of {p ₁, p ₂, p ₄} has members p ₁, p ₂ belonging to the concept P ₁ and a member p ₄ belonging to the concept P ₂. Thus, this region shows a degree of membership (fuzzy membership) and it is indicative of a neutral zone that can be used for discovering and learning a new concept. The order-3 Voronoi region is further decomposed and modelled in a much finer form by the ordered order-3 Voronoi diagram as shown in Figure 2(b). That is, it is further decomposed into 3! number of regions in the ordered order-3 Voronoi diagram. This ordered diagram provides richer information at the expense of complexity.

FIGURE 2 The order-3 Voronoi diagram and ordered order-3 Voronoi diagram of P (P is the same as in Figure 1): (a) ⁽³⁾(P); (b) ^〈3〉(P).

Definitions

Definition 1

Given a set P = {p ₁, p ₂,…, p _n } of exemplars forming a set  = {C ₁, C ₂,…, C _k } of concepts, the kth concept region of C _i  ∊  (denoted by ℑ^(k) C _i ) is defined by a union of all order-k Voronoi regions whose generators (member points) all belong to the same concept C _i . It is formally defined as follows:

Definition 2

Given a set P = {p ₁, p ₂,…, p _n } of exemplars forming a set  = {C ₁, C ₂,…, C _k } of concepts, the kth neutral zone of  (denoted by ℘^(k)) is defined by a union of all order-k Voronoi regions whose generators do not belong to the same concept. It is formally defined as follows:

for such that p _u  ∊ C _s , p _v  ∊ C _t where s ≠ t.

in ℑ^(k) C _i exhibits a total membership of to C _i constituting a concept kernel of C _i while in ℘^(k) shows a partial and degree of membership.

Definition 3

Given an order-k Voronoi region V(P ^(k)) in ℘^(k), the degree of membership of V(P ^(k)) to a concept C _j is defined as follows:

For any C _i and C _j  ∊ , ℑ^(k) C _i and ℑ^(k) C _j are mutually exclusive, and a union of ∪_{∀C i} ℑ^(k) C _i and ℘^(k) is collectively exhaustive. Solid thick black polylines in Figure 2(a) define concept boundaries, and a yellow shaded region representing a neutral zone separates the two concept regions.

Concept Management

Once concept regions and neutral zones are defined, concept management becomes a series of processes of manipulating concept regions and neutral zones. Concept categorization in conceptual spaces is equivalent to tessellating concepts (Gärdenfors and Williams 2001). Both ℑ^(k) C _i and ℘^(k) are able to model concept growth, and are used for concept learning, concept discovery, and concept formation. When a new instance p is given, it will fall into one of the regions in ℑ^(k) C _i and ℘^(k) since OkVD produces a tessellation. When it falls within a certain concept region, the concept region will grow. When it falls within the neutral zone, it is suggestive of a new possible concept depending on the context. Figure 3 displays order-k concept regions and neutral zones, and explains the working principle of concept management. Figure 3(a) shows order-1 concept boundaries of P = {p ₁, p ₂,…, p ₁₀} forming two concepts P ₁ = {p ₁, p ₂, p ₃, p ₇, p ₈} and P ₂ = {p ₄, p ₅, p ₆, p ₉, p ₁₀}. Concepts are of arbitrary shape and they are not necessarily connected. Figure 3(b) defines ℑ⁽²⁾ P ₁ and ℑ⁽²⁾ P ₂, and the second-order neutral zone ℘⁽²⁾ (grey-shaded). Similarly, Figure 3(c) defines the third-order concept regions and neutral zone. In this example, ℘⁽³⁾ is shaded in two different colors: one light grey neutral zone indicating a region more influenced by the concept P ₁ (2/3 from P ₁ and 1/3 from P ₂) and one dark grey neutral zone indicating a region more influenced by the concept P ₂ (1/3 from P ₁ and 2/3 from P ₂). Also, it is seen from the figure that ℑ⁽³⁾ C _i is disconnected. As k increases, the neutral zone grows while concept regions shrink. This implies that higher k values tend to define tighter concept regions defining strongly coupled concept kernels and wider neutral zones. Concept kerneling is a process of defining a subset of concept region that exhibits strong intraconcept interactions. Concept kernels represent pure concept regions. A new instance falling into a certain concept kernel strongly suggests that the new instance belongs to the concept. Concept kernels are used for concept reasoning (Gärdenfors and Williams 2001) typically with well-defined, region-based reasoning approaches such as region connection calculus (RCC) (Cohn, Bennett, Gooday, and Gotts 1997). Figure 3(d) shows a typical approach for concept kerneling within conceptual spaces using convex hulls (O'Rourke 1993). One major problem with this approach is that kernels may overlap, which becomes problematic in concept learning and categorization. This unwanted kernel overlapping is avoided in our approach. Concept regions are hardened as k grows and they are mutually exclusive in all cases. A series of figures in Figure 3 illustrates the working principle of our approach, and demonstrates our proposed framework's capabilities for indeterminate concept representation, concept kerneling, concept learning and categorization, complex concept representation, and concept discovery and formation. In addition, a series of different values of k provides a complete set of indeterminate (vague) concept boundaries and regions, which can model geospatial uncertainty. Our framework provides an interactive environment that enables an agent (a user) to choose the most suitable value k for a given task. The following subsection describes how this is achieved through a generic Delaunay triangle data structure.

FIGURE 3 Concept management with OkVD of P = {p ₁, p ₂,…, p ₁₀} forming two concepts P ₁ = {p ₁, p ₂, p ₃, p ₇, p ₈} and P ₂ = {p ₄, p ₅, p ₆, p ₉, p ₁₀}: (a) a concept tessellation defined by O1VD; (b) a concept tessellation defined by O2VD; (c) a concept tessellation defined by O3VD; and (d) concept kerneling with convex hulls.

Data Structure

Several algorithmic approaches (Aurenhammer and Schwarzkopf 1991; Chazelle and Edelsbrunner 1987; Dehne 1983; Lee 1982) have been proposed to efficiently compute higher order diagrams in the computational geometry community. Dehne (1983) proposed an O(n ⁴) time algorithm that constructs the complete ^(k). Several other attempts (Aurenhammer and Schwarzkopf 1991, Chazelle and Edelsbrunner 1987; Lee 1982; Lee and Lee 2009) have been made to improve the computational time requirement of Dehne's algorithm. These approaches simply compute higher order diagrams, but they do not provide underlying data structures that can support interactivity and many geospatial topological queries. The best-known algorithm for the order-k Voronoi diagram is O(k(n − k)log n + n log³ n) (Berg, Kreveld, Overmars, and Schwarzkopf 2000). Thus, the complete ^(k) requires O(n ³ log n + n log³ n) time.

Our data structure develops Dehne's structure (1983) and builds the entire order of Delaunay triangles. It is based on the combination of two tables: generator list and triangle lists, which is similar to the triangle-based data structure (Dehne 1983). The generator list is a table of points containing the x, y coordinate with a unique identification number. The triangle lists are tables of triangles, each with three vertices, a circumcircle center point, and a list of generator identifications lying within the circumcircle.

In the unified data structure, the triangles are assigned to the triangle table based on the number of generators that are lying within the circumcircle for this triangle. These triangles are referred to as order-k triangles, where k is the number of generators within the circumcircle of this triangle. Table 2 depicts the assignment of triangles shown in Figure 4. The triangle ▵p ₁ p ₂ p ₅ does not contain any other points in its circumcircle; thus it is an order-0 triangle. On the other hand, ▵p ₁ p ₂ p ₄ contains one point (p ₅) within its circumcircle; thus it is an order-1 triangle. In a similar way, ▵p ₁ p ₂ p ₃ contains two points (p ₄, p ₅) within its circumcircle, thus it is an order-2 triangle.

FIGURE 4 Circumcircles and data structure for the complete order-k Voronoi diagrams: (a) Order-0 triangles; (b) Order-1 triangles; (c) Order-2 triangles.

TABLE 2 Complete Order- k Delaunay Triangle Data Structure

Order-k Delaunay triangle	Triangle (▵) ID	Onpoint ▵abc	Inpoint
Order-0 Delaunay triangle	1	{p 1, p 2, p 5}	φ
Order-0 Delaunay triangle	2	{p 2, p 3, p 5}	φ
Order-0 Delaunay triangle	3	{p 3, p 4, p 5}	φ
Order-0 Delaunay triangle	4	{p 1, p 4, p 5}	φ
Order-1 Delaunay triangle	5	{p 1, p 2, p 4}	{p 5}
Order-1 Delaunay triangle	6	{p 2, p 3, p 4}	{p 5}
Order-2 Delaunay triangle	7	{p 1, p 2, p 3}	{p 4, p 5}
Order-2 Delaunay triangle	8	{p 1, p 3, p 4}	{p 2, p 5}

Derivation of the complete order-k Voronoi diagrams from the unified data structure basically follows the Dehne' rule (1983)—^(k) is derived from the combination of both order-(k − 1) and order-(k − 2) triangles. That is, ⁽¹⁾ is derived from the order-0 triangle list while ⁽²⁾ is derived from the order-0 and order-1 triangle lists. Therefore, triangle lists need to be indexed and need not to be exhaustively searched. Once the complete ^(k) is computed, ^〈k〉 is computed by ^〈k〉 = ∪^(k). This step requires O(n ³ log n) time with an indexing data structure support.

INTERDOMAIN CONCEPT MANAGEMENT

In conceptual spaces, a concept consists of at least one domain. Concepts may have multiple domains and the Manhattan metric is used for interdomain dissimilarity measure (Gärdenfors 2000; Okabe, Boots, Sugihara, and Chiu 2000). Our framework supports this higher-order domain and interdomain concept management. Figure 5 shows O1VD and O2VD of P (the same as in Figure 1) in the Manhattan metric. These diagrams model interdomain interactions and support interdomain concept management.

FIGURE 5 Interdomain tessellations and concept management (P is the same is in Figure 1): (a) O1VD of P in the Manhattan metric; (b) O2VD of P in the Manhattan metric.

GEOSPATIAL CONCEPT MANAGEMENT CASE STUDIES

Geospatial concept management is an important issue in geospatial data mining and knowledge discovery (Miller and Han 2001). This section provides two case studies of geospatial concept management with real datasets.

Case Study with Well-Separated Concepts

In this case study, real geospatial datasets from Brisbane, the capital city of Queensland, Australia are considered. We utilize raw crime and geospatial feature datasets recorded in the years 1996 and 1998 by the Queensland Police Service around 217 central urban suburbs of Brisbane as our study region. Brisbane is continuously experiencing steady population and crime growth. Building crime-related concepts in this region provides a valuable resource to city planners, policing agencies, and criminologists.

Figure 6 depicts a dataset consisting of 4 different geospatial concepts: post office ({p ₃,…, p ₇}), murder ({p ₈,…, p ₁₂}), caravan park ({p ₁₃,…, p ₁₇}) and unknown crime type ({p ₁₈, p ₁₉,…, p ₃₆, p ₃₇}). Each concept is geospatially correlated and aggregated. That is, each concept is represented by a set of regions in conceptual spaces. Locations of post offices, murder incidents, and caravan parks are recorded in the year 1996, and locations of unknown crime type (later turned out to be offenses against property) are recorded in the year 1998. In this scenario, we build the higher-order Voronoi diagrams inspired concept boundaries and use them for learning the unknown crime incidents. First, we build concept regions (boundaries) of the three known concepts: post office, murder, and caravan park. The concept regions of O1VD and O5VD are superimposed in Figure 6(b). As k becomes larger, the neutral zone widens. The neutral zone grey shaded and boundarized by thick black polylines defines ℑ⁽⁵⁾ C _i and ℘⁽⁵⁾ while thick white polylines within ℘⁽⁵⁾ defines ℘⁽¹⁾. Table 3 summarizes learning of 20 unknown objects with the complete higher-order Voronoi diagrams.

FIGURE 6 A study region with dataset I, P = {p ₃, p ₄,…, p ₃₆, p ₃₇}: (a) a study region with exemplars and unknown objects; (b) concept boundaries defined by O1VD and O5VD.

TABLE 3 Conceptualization of Dataset I with the Complete Higher-Order Voronoi Diagrams: m Denotes Murder, p Denotes Post Office, c Denotes Caravan Park, and Superscript Denotes Frequency

^(k)	Order-1	Order-2	Order-3	Order-4	Order-5	VoP
p 18	m ^(1)	m ^(2)	m ^(3)	m ^(4)	m ^(4), p ^(1)	m ^(1)
p 19	p ^(1)	m ^(1), p ^(1)	m ^(1), p ^(2)	m ^(2), p ^(2)	m ^(3), p ^(2)	m ^(1)
p 20	p ^(1)	p ^(2)	p ^(3)	p ^(4)	p ^(4), m ^(1)	p ^(1)
p 21	m ^(1)	m ^(1), p ^(1)	m ^(2), p ^(1)	m ^(2), p ^(2)	m ^(3), p ^(2)	m ^(1)
p 22	p ^(1)	p ^(2)	p ^(3)	p ^(3), m ^(1)	p ^(4), m ^(1)	p ^(1)
p 23	p ^(1)	p ^(1), m ^(1)	p ^(1), m ^(2)	p ^(2), m ^(2)	p ^(3), m ^(2)	p ^(1)
p 24	m ^(1)	p ^(1), m ^(1)	p ^(1), m ^(2)	p ^(2), m ^(2)	p ^(3), m ^(2)	p ^(1)
p 25	p ^(1)	p ^(2)	p ^(3)	p ^(4)	p ^(4), m ^(1)	p ^(1)
p 26	m ^(1)	m ^(2)	m ^(3)	m ^(3), p ^(1)	m ^(4), p ^(1)	m ^(1)
p 27	m ^(1)	m ^(2)	m ^(2), p ^(1)	m ^(3), p ^(1)	m ^(3), p ^(1), c ^(1)	m ^(1)
p 28	m ^(1)	m ^(1), c ^(1)	m ^(2), c ^(1)	m ^(3), c ^(1)	m ^(3), c ^(2)	c ^(1)
p 29	m ^(1)	m ^(2)	m ^(3)	m ^(4)	m ^(4), c ^(1)	m ^(1)
p 30	m ^(1)	m ^(1), c ^(1)	m ^(2), c ^(1)	m ^(3), c ^(1)	m ^(4), c ^(1)	m ^(1)
p 31	c ^(1)	c ^(1), m ^(1)	c ^(2), m ^(1)	c ^(3), m ^(1)	c ^(4), m ^(1)	c ^(1)
p 32	c ^(1)	c ^(1), m ^(1)	c ^(2), m ^(1)	c ^(3), m ^(1)	c ^(4), m ^(1)	c ^(1)
p 33	p ^(1)	p ^(2)	p ^(2), c ^(1)	p ^(2), c ^(2)	p ^(3), c ^(2)	p ^(1)
p 34	p ^(1)	p ^(2)	p ^(3)	p ^(3), c ^(1)	p ^(4), c ^(1)	p ^(1)
p 35	p ^(1)	p ^(1), c ^(1)	p ^(2), c ^(1)	p ^(3), c ^(1)	p ^(3), c ^(2)	p ^(1)
p 36	c ^(1)	c ^(2)	c ^(3)	c ^(3), p ^(1)	c ^(4), p ^(1)	c ^(1)
p 37	p ^(1)	p ^(2)	p ^(3)	p ^(4)	p ^(4), c ^(1)	p ^(1)

Undoubtedly, VoI and VoP (Figure 6 and Table 3) assign all unknown objects to one of existing concepts, and fail to form a new concept. Concept discovery and formation is much improved with the use of the order-2 Voronoi diagram. With the order-3, order-4, and order-5 Voronoi diagrams, more than half of unknown objects fall into the neutral zone that may trigger a new concept formation based on the majority voting (Kuncheva 2004). This trend is well depicted in Figure 7(a). The number of unknown objects misconceptualized into one of existing concepts is gradually decreasing as k grows while the number of objects falling into the neutral zone is constantly increasing. Figure 7(b) depicts the number of occurrences of each object in the neutral zone. Generally, they grow as k increases. In this particular case, more numbers of misconceptualized post office and murder occurrences are observed than the number of misconceptualized caravan park occurrences. This means that unknown crime instances conceptualized into the caravan park concept are relatively closely coupled with the caravan park exemplars.

FIGURE 7 Trends of dataset I: (a) conceptualization distribution; (b) occurrences in the neutral zone.

Case Study with Multi-Pieced Concepts

This case study illustrates complex concepts with different sizes and multi-pieced regions. The second dataset consists of three geospatial concepts recorded in the year 1996, and a set of unknown geospatial features recorded in the year 1997 in a study area of 209 suburban Gold Coast region, south of Brisbane. The dataset includes 15 national park exemplars (shown in rectangles in Figure 8(a)) mainly distributed in the southern part of the study region, 11 post office exemplars (shown in triangles in Figure 8(b)), widely distributed all over the study region, and eight college exemplars (shown in circles in Figure 8(c)) mainly distributed along the coast. A set of 25 unknown objects in the study region has been recorded in the following year (shown in question marks in Figure 8(c)). Different from dataset I, geospatial concepts in this case study are not well separated and are composed of multi-pieced regions. Figure 8(b) shows an O2VD concept tessellation of Q, while Figure 8(c) exhibits an O4VD concept tessellation of Q.

FIGURE 8 A study region with dataset II, Q(|Q| = 59): (a) a study region with exemplars and unknown objects; (b) concept boundaries defined by the 2-order Voronoi diagram; and (c) concept boundaries defined by the 4-order Voronoi diagram.

Since data are not well-separated but widely distributed, experiments are conducted up to the O4VD tessellation. Undoubtedly, Figure 9(a) shows an increasing trend in the number of new objects falling into the neutral zone as k increases. One thing to note here is that numbers of misconceptualized objects into concepts are not always decreasing. The number of unknown examples conceptualized to the national park concept remains constant and the number of unknown examples conceptualized to the college concept remains unchanged after an initial drop at the O2VD concept tessellation. This implies that unknown examples conceptualized to the college concept are tightly coupled (geospatially closely located) with the college exemplars. Figure 9(b) shows occurrences of unknown objects in the neutral zone. As k increases, there is a sudden jump in numbers of occurrences of misconceptualized post office and college instances in the neutral zone particularly from the O1VD concept tessellation to the O3VD concept tessellation. Notably, the post office concept is gaining more attention from the O1VD concept tessellation to the O2VD concept tessellation (losing 1 but gaining 3), while the college concept is gaining more attention from the O2VD concept tessellation to the O3VD concept tessellation (losing nothing but gaining 2). This example demonstrates that our proposed approach provides a robust framework for managing complex concepts.

FIGURE 9 Trends of dataset II: (a) conceptualization distribution; (b) occurrences in the neutral zone.

CONCLUSIONS

The Voronoi diagram provides a cognitively economical way of representing information about concepts (Gärdenfors 2000). VoI and VoP have been two popular approaches for representing concepts in conceptual spaces. In this article, we provide a flexible concept tessellation framework overcoming the rigidity and inflexibility of traditional approaches. It is based on the complete higher order Voronoi diagrams and robustly supports various concept management processes. We also develop a generic unified data structure that interactively supports our concept management framework. The OkVD approach is inclusive of VoI and VoP, and is offering extra functionality for various concept management. Experimental results with real geospatial datasets demonstrate robustness and superiority of our approach over traditional approaches.

As geospatial concepts become complex, scalability to higher domain conceptual spaces is of interest. Computational efficiency is of another interest as geospatial data grow at an unprecedented rate. Automatic detection of interesting patterns within conceptual spaces will help an agent effectively manage concepts. Future work is to adopt and develop data mining techniques to improve our proposed framework more scalable, efficient, and intelligent.

DECLARATION OF INTEREST

The author declares no conflict of interest.