ABSTRACT

In this paper, we applied the rough sets to the point cluster and river network selection. In order to meet the requirements of rough sets, first, we structuralize and quantify the spatial information of objects by convex hull, triangulated irregular network (TIN), Voronoi diagram, etc.; second, we manually assign decisional attributes to the information table according to conditional attributes. In doing so, the spatial information and attribute information are integrated together to evaluate the importance of points and rivers by rough sets theory. Finally, we select the point cluster and the river network in a progressive manner. The experimental results show that our method is valid and effective. In comparison with previous work, our method has the advantage to adaptively consider the spatial and attribute information at the same time without any a priori knowledge.

Keywords:Rough Sets Theory, Map Generalization, Point Cluster, River Network, Progressive Selection

1. Introduction

Point and line are the two most common objects to represent the spatial features and phenomena on the map, e.g. we use points to denote the village on small scale map, the point of interests (POIs) of the searching results in web or mobile mapping, we also employ lines to represent the road, river, as well as the region border on nearly all the maps. Generally, maps are generated to different scales for specific purposes. One of the most important techniques for scale transformation is selection, which can be used to reduce the complexity of map contents, emphasize the interesting phenomena, and delete the unimportant details while maintaining the geometrical and topological relations between objects. Acquiring geodata is much easier than it once was; especially as the attribute information becomes increasingly available. This change gives the object selection an even wider implication—we should take into account not only the spatial characteristics of the objects, but also the attribute information during the process. Currently, most of the methods for object selection merely consider the attribute information. In considering of this, we proposed a novel method of using Rough Sets to combine the spatial and the attribute information together to evaluate the importance of spatial objects for progressive selection.

Rough sets is proposed by Z. Pawlak in 1990s, which can handle the incomplete and inaccurate data without relying on any a priori knowledge. In recent years, some researchers have tried to apply rough sets to cartographic generalization. Song et al. [1] employed the attribute reduction to mine the knowledge of river network selection. Li et al. [2] -[4] proposed a method based on rough set to generalize the point cluster as well as the river network. However, there are some limitations of their method, especially for applying the rough set to the non-decisional attribute information table. Our work is different from these two, we propose a strategy to assign decisional attribute for the information table, and use the dependency of attributes in rough sets to evaluate the importance of spatial objects for progressive selection.

The remainder of the paper is organized as follows: Section 2 surveys the related work. Section 3 outlines the main idea of object selection based on rough sets theory. Section 4 presents the experiments of the point cluster and river network selection. And Section 5 discusses the future application of our method.

2. Related Work

Research of point and line object selection in map generalization has a long history ranging from the traditional paper map to the electronic map on mobile device and web. Yan and Weibel [5] employ the Voronoi diagram for the point cluster selection. In their method, they constructed an equation taking into account the thematic importance as well as the local density to evaluate selection possibility. Unfortunately, this method lacks the ability to determine the weight of these two kinds of factors. Cai and Guo [6] introduced the Kohonen net to implement the selection of point set. The method can maintain the distribution feature of pointsbut doesn’t take the attribute information into account. De Berg et al. [7] proposed a method for the simplification of dot maps. They formalized the problem—derive coarse dot map from the fine one—by employing the concept of “-approximations.” And they can then compute good approximations of the derived and source maps by a heuristic method. The approach could be applied to the map with large amount of points while only consider the geometric information. Bereuter et al. [8] [9] proposed the concept of Real-time generalization for the points on the mobile device. They use the quadtree to manage the points with its “hierarchical subdivision structure” and “progressive levels of detail”. By employing the indices of the quadtree as auxiliary data, they refined the algorithms of selection, simplification, aggregation and displacement for the points. Their method focuses mainly on the efficiency and the distribution character of the points; merely taking into account the attribute information.

There are also many approaches have been developed regarding river selection. Ai et al. [10] [11] implemented an algorithm by employing the Voronoi diagram to calculate the catchment of the hydrographic network, and use the area of the catchment as a main factor to evaluate the importance of rivers, but the experimental results is not satisfying. Buttenfield et al. [12] -[14] proposed a series methods for the generalization of National Hydrographic Dataset (NHD). Their approaches classify the hydrographic data by considering geographic factors—terrain and the climate, which include mountainous, hilly or flat, and dry or humid. Then, according to the characteristic of different types of hydrographic data, a researcher can set the processing sequence as well as the parameters of algorithms to generate coarse version of the fine hydrographic data. Hydrographic generalization results based on this method turn out to be quite effective. Sen et al. [15] [16] presented a method based on k-means clustering and Self Organizing Maps (SOM) to implement the generalization of the hydrographic data. This method enjoys the advantage that takes account of semantic information directly.

In addition to mainly focus on the geometrical information and the topological information, some researches about the generalization of river network address the thematic information. Dahinden and Sester [17] developed a method for the river network selection based on its importance. But the importance of the rivers is not determined by geometric or topologic features. It is in fact linked with “the fact and the frequency of their use”. The generalization result of this method is not stable, which highly related to the crowd sourcing information—the data in public repositories, and parameters of the assessment approach. Tinker et al. [18] also implement a hydrographic generalization based on the thematic information—the local mean annual precipitation.

Since the thematic information is acquired far more easily nowadays, we need to develop tools for the map generalization that can handle the spatial information (the geometrical, topological characteristic) and the attribute information (the thematic, semantic data) at the same time. In this paper, we propose a selection method based on the rough sets. Our method can integrate the spatial information and attribute information together to evaluate the importance of the spatial object, which is the criterion for the object selection. In addition, we carry out the selection process in a progressive manner to maintain the distribution consistency of spatial objects.

3. Objects Selection Based on Rough Sets Theory

The selection of point and line objects is based on their importance that evaluated by the spatial information and attribute information. The basic idea of employing rough sets theory to calculate the importance of geospatial objects is to find the dependency between attributes. Thus, we will introduce the concepts of rough sets theory, then, outline the method for information table construction, and propose the progressive selection algorithm.

3.1. Basic Concepts of Rough Sets

According to [19] , “the starting point of the rough sets theory is the indiscernibility relation, generated by information about objects of interest”. The indiscernibility relation is defined as an information table (also called an information system or an attribute-value table) in rough sets theory. A model of the information table can be defined as:. Where is a finite set of objects named as universe; is a finite set of attributes, where and are conditional attribute subset and decisional attribute subset; for each attribute

, is the function for designating the value for. An indiscernibility relation, where

, is. in short, is the family of all indiscernibility of. “Another important issue in data analysis is discovering dependencies between attributes”

[19] . For subsets and, if, then depends on in degree k0 k 1. POS_C(D) is the positive region of U/D with respect to C, which consists of all the elements of U that can be uniquely classified to blocks of U/D by subset C.

Take Table 1 as illustration, six entities are included. The conditional attributes and decisional attribute are and separately. According to the above mentioned definitionsU/C = {{e₁}, {e₂}, {e₃}, {e₄}, {e₅}, {e₆}}, and U/D = {{e₁, e₄, e₅}, {e₂, e₃, e₆}}. Let subset P = {c₁, c₂}, then U/P = {{e₁, e₂, e₃}, {e₄, e₆}, {e₅}}. In this case, we could conclude that the POS_C(D) = 6, and POS_P(D) = 1, which can be interpreted that all elements of U can be uniquely classified to the partition U/D by means of C, while only 1 can be classified by means of P. Then the decisional attribute d totally depends on attribute set C, and 1/6 depends on attribute set P. For each attribute, the importance of c_i for the decisional attribute D can be defined as, therefore, the importance of c₃ is 1 - 1/6 = 5/6. That means without attribute c₃, only 1/6 elements in U can be correctly classified, then the importance of attribute c₃is 5/6.

By employing the dependency of attributes, we can calculate the importance of each conditional attribute if we can construct an information table for the spatial objects which are to be selected.

3.2. Information Table Construction

Attribute information always can be easily transformed to quantitative indexes. While the spatial information sometimes cannot be obtained directly, we need use structuralization to extract it. Structuralizing spatial objects means to recognize and quantify the topological relations between objects and the spatial distribution features of objects. There are many methods for the structuralization of map objects, such as convex hull [20] , constrained TIN [21] , Voronoi diagram [22] and so on.

3.2.1. Structuralization of Point Cluster

Take the hotel distribution of a city in Figure 1(a) as example. All the data in our experiment is vector data that can be displayed at any scale. First, the nesting level of the convex hull is constructed, which is shown in Figure 1(b). This information can represent the boundary structure of points since points on border have a greater impact on general structure than the inner points. Second, the Voronoi diagram, shown as Figure 1(c), is employed to represent the affection domain of each point. The larger the area is, the more important the point tends to be. Third, the local density, shown as the gray area of Figure 1(c) and Equation (1), can be derived from the Voronoi diagram. The smaller the local density is, the more opportunities the point to be retained during selection.

. (1)

where D_i is the local density of point i, S_i is the Voronoi area of point i, m is the count of the nighbours of point i, and S_k is the Voronoi area of point i’s neighbour point k.

In addition, we take into account the relation between the road and the point, shown as Figure 1(d). It is more convenient for the travellers to stay the hotel near by the main road; then we prefer to retain the point near to the main road.By employing these methods, we can quantify the spatial information of the point cluster—represent the border and inner of points by the level of convex hull, affection domain and local density by Voronoi area, and the location by distance to the road.

3.2.2. Structuralization of River Network

The pattern of the river network is more complicated than the point cluster. In this paper, we focus on the tree-like river network, which consists of a trunk river and some tributaries. Figure 2(a) is an example of the river network which consists of 14 rivers. The blue river 1 is the main stream and others import into it.

First, the length of each river should be taken into account to evaluate the importance of the rivers. Long rivers are always regarded as the geometrical skeleton of the network. Second, we use Horton code [23] as the grade to represent the hierarchy relationship between the rivers, which shown as Figure 2(a). No rivers import into rivers with grade 1. The red rivers, with grade 2, have the rivers with grade 1 directly imported into. And the blue river with the largest grade has many rivers with grade 2 directly imported into. We couldn’t remove the river before those rivers directly import into it are removed. Third, the level of the rivers showing in Figure 2(c) is employed to denote the tree-like structure of the rivers in this paper. The level is much like the binary tree, each node has at most two child nodes, distinguished as “left” and “right”, and nodes with children are parent nodes. In the river network, for each river the left tributaries are regarded as its left node, and right tributaries are the right node. Rivers in the same node are siblings to each other. For example, in this river network, river 4, 9, 12 are siblings to each other, river 1 is the common parent of these rivers, and river 4 has the left child river 5, the right child river 6. Deletion of the river with a higher level is more likely to destroy the tree-like structure than the deletion of a river with lower level. Then we prefer to select rivers with a high level. Fourth, the catchment of the rivers [11] , showing in Figure 2(b), is employed as an index as well. We use the Voronoi diagram of the rivers, which generated by TIN, to partition the space, and regard the Voronoi area as the catchment of the river. Furthermore, the catchment of the parent river owns all its children’s catchment. This index is a synthetical index which could represent not only the hierarchy relation between rivers, but also their intervals and local density. In addition, we introduce another index—a location metric—to reflect the location of rivers related to their parents in the tree-like structure. The index is shown as Equation (2).

. (2)

where L_i is the location metric of river i, L is the length of river i’s parent, and n is the amount of river i’s sib-

lings in the tree. According to this definition, rivers that are siblings to each have the same location metric. The index is interpreted as follow: if two rivers import the same parent from the different sides, then the river with fewer siblings tends to be more important than the other river with more siblings regardless of all other indexes.

By the structuralization of river network, we can quantify the spatial information of the river network into several parameters—describe the tree-like structure by the Horton code (grade) and tree level, the catchment (or affection domain) by Voronoi area, and the location by location metric.

3.2.3. Information Table of Points and Rivers

After structuralization, we can construct the information table as Table 2 and Table 3 by adding the attribute information. In Table 2, the “Grade” and the “Number of Rooms” are attribute information of hotels. Grade represents the star-level of the hotel. This is also a synthetical index that manually generated according to the facilities, services, management, and et al. we can get this index via the internet. In addition, the number of the rooms can reflex the scale of the hotel immediately. In Table 3, we didn’t add any additional attribute information to this table. That is because the attribute information of the rivers is not easily obtainable. But we could add that kind of information to the table if it is available, such as the precipitation of the catchment.

According to rough sets, to calculate the importance of conditional attributes, a decisional attribute should be contained. In the case of spatial object selection, the decision is to decide which objects should be deleted and which should be selected. But in Table 2 and