2007 IEEE International Conference on Control and Automation Guangzhou, CHINA - May 30 to June 1, 2007

FrC7-5

Construction and Application of Bayesian Network Model for Spatial Data Mining

Jiejun Huang School of Resource and Environment Engineering Wuhan University of Technology Wuhan, China

Yanbin Yuan School of Resource and Environment Engineering Wuhan University of Technology Wuhan, China Yybjm@163.com

mining in large spatial database [2]. Beaubouef et al used a rough set foundation for expressing topological relationships and provided an extension of spatial association rule generation that will be able to use rough set-modeled spatial data [3]. Ng and Han have proposed a new clustering method called CLARANS and developed two spatial data mining algorithms that aim to discover relationships between spatial and nonspatial attributes [4]. Brimicombe has discussed a novel variable resolution approach to cluster discovery in spatial discovery, and shown that it is an effective method of guiding decisions on K where no other a priori knowledge is available [5]. Salmenkivi presented and evaluated a variety of spatial ordering methods that can transform spatial relations into a one-dimensional ordering and encoding which preserves spatial locality as much possible [6]. Zhang and Zhu have studied a parallelism of spatial data mining based on autocorrelation decision tree, and presented an individual implement of intelligent information retrieval for spatial data mining [7]. Guo and Gahegan have presented and evaluated a variety of spatial ordering methods that can transform spatial relations into a one-dimensional ordering and encoding which preserves spatial locality as much possible [8]. Recently, more and more authors have been studied on spatial data mining and knowledge discovery in spatial database [9-10]. Bayesian networks are the method for uncertainty reasoning and knowledge representation that was advanced at the end of the 20th Century. It is a probabilistic graphical model, which has been used for probabilistic reasoning in expert systems. Because that the novel method has a powerful ability for reasoning and a flexible mechanism to learning, it provides an effective way to deal with causality or uncertainty. Bayesian networks proved to have surprisingly broad applications, such as medical diagnoses [11, 12], image classification and Image understanding [13, 14], prediction and forecasting [15, 16], in particular, knowledge discovery and data mining [17-19]. In this paper, we focused on application of Bayesian network method to spatial data mining. Bayesian networks as spatial data mining have following characteristics: 1) Inference in spatial data mining is rigorous based on Bayesian probability theory. This rigor will not decrease along with inference passages of any length. 2) Inference in spatial data mining is flexible and general, meaning that there is no need to distinguish between forward reasoning or backward reasoning, unlike rule based systems or feedforward neural networks. Information in the form of evidence may come into the network from any location (variables or nodes) in the

Hjjtk2 ,21cn.com

Abstract The advent of spatial information technologies, such as GIS, GPS and Remote Sensing, have great enhanced our capabilities to collect and capture spatial data. How to discover potentially useful information and knowledge from massive amounts of spatial data is becoming a crucial project for spatial analysis and spatial decision making. Bayesian networks have a powerful ability for reasoning and semantic representation, which combined with qualitative analysis and quantitative analysis, with prior knowledge and observed data, and provides an effective way to spatial data mining. This paper focuses on construction and learning a Bayesian network model for spatial data mining. Firstly, we introduce the theory of spatial data mining and discuss the characteristics of Bayesian networks. A framework and process of spatial data mining is proposed. Then we construct a Bayesian network model for spatial data mining with the given dataset. The experimental results demonstrate the feasibility and practical of the proposed approach to spatial data mining. Finally, we draw a conclusion and show further avenues for research.

Keywords-Bayesian networks; spatial data mining; knowledge acquisition; spatial classificatio; learning

I.

INTRODUCTION

Nowadays, the capture, propagation and exploitation of information are closely related to all of us, information has become perhaps the most important factor determining the standard of living. The ability of Information management and science decision has enhanced greatly with the establishment of information system, expert system and knowledge base. At the same time, along with the rapid accumulation of data and information, how to use huge amounts of data is becoming a crucial project for businesses and governments. Data mining has been emerging as a new research field and a new technology for discovery of novel and interesting knowledge from huge database. Spatial data mining, or knowledge discovery in spatial database, is a subfield of data mining that extracts potentially useful information and knowledge from spatial database. It involves different techniques and different methods from various areas of research. Cromp & Campbell used data mining for automatically extracting content from remotely sensed images [1]. Lu et al have studied spatial data

The work presented in this paper was supported by the National Natural Science Foundation of China (40601076, 40571128) and Open Research Fund of State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing (WKL (06) 0303)

2802

1-4244-0818-0/07/$20.00 (? 2007 IEEE

network, and such incoming information will then be propagated throughout the rest of the network. 3) Spatial data mining based on Bayesian network can be controlled by artificial conditioning. This is useful in case approximate inference is required under some circumstances, or the network is too big but the connections between far-reaching subnetworks are sparse or tenuous. In section 2, we discussed how to use Bayesian networks for spatial data mining, and proposed a framework of spatial data mining based on Bayesian networks. Section 3 constructed a Bayesian network model for spatial data mining with the given dataset. Section 4 concluded with a summary and a statement of future work.

SPATIAL DATA MINING BASED ON BAYESIAN NETWORKS A. The Framework ofSpatial Data Mining Efficient tools for extracting information from spatial data sets can be of importance to organizations which own, generate and manage large spatial data sets. Therefore, spatial data mining is very useful for understanding spatial data and spatial decision making. Many scholars have been studied on spatial data mining with the new theory and algorithm as Decision tree, Rough Set, Genetic Algorithm and Support Vector Machines, and so on. How to carry out spatial data mining? The framework of spatial data mining is described as fig 1. It is the basic of collecting the spatial data. Spatial data cleaning and analyzing is the core step. After obtaining spatial knowledge, we should to explain and evaluate the results, and then apply the meaningful knowledge to the specific domain.

B. Bayesian networks for spatial data mining As for a spatial data mining method, Bayesian networks can

II.

Spatial knowledge

Spatial statistics

Spatial classification

Spatial clustering Spatial prediction

DatabJase

nowleage

DLU _

Data wao OM6696

Metat

. .........................................

Figure 1. A framework of spatial data mining.

be used for spatial knowledge representation, spatial classification, spatial clustering, and spatial prediction. We address the application domain for spatial data mining as follows. * Spatial variable Discovery. Identifying a new variable of the problem domain is like discovering a new dimension of thinking about that problem domain. As for a spatial problem, we assume that it is fully described by a finite set of random variables. Each variable is fully defined in a finite frame, i.e. set of all possible states. The set of spatial relations among variables is called the structure of the Bayesian network, which represents the qualitative knowledge about the problem domain. The conditional probabilities associated with spatial relations correspond to the quantitative aspects of the expert knowledge. If all the variables are identified, and each variable is defined with a frame, if all the spatial relations are identified and all the conditional probabilities are determined, we say that we have a complete Bayesian network which is a complete representation of the knowledge of the spatial problem. In other words, we can find the spatial variable that hidden in the domain by learning Bayesian networks. * Spatial clustering is related to spatial classification, but differs in that no groups have yet been defined. Using spatial clustering, the data mining tool discovers different groupings within the data. This can be applied to problems as diverse as finding affinity groups for spatial objects. The process of spatial clustering is somehow similar to spatial classification. Again the purpose is to divide the records of a database in similar, homogeneous groups, but this time the user does not know the classes before the analysis. The clustering algorithm will have to discover the more natural way to group the records together, and then proceed with the grouping. The best application of clustering is with spatial databases. These are databases where each record represents a point in a certain space. The clustering algorithm finds all the points belonging to the same clusters. Using Bayesian network for spatial clustering, each node is associated to a cluster, in a way that the cluster associated to a father contains all the clusters associated to his children. The structure can be created with a top-down or bottom-up strategy. The main applications of spatial clustering are in the image processing field. The spatial clustering can be used to analyze satellite images of earth surface, astronomical images or medical images. * Spatial classification is the process which finds the common properties among a set of objects in a spatial database. It recognizes spatial patterns that describe the group to which an item belongs. It does this by examining existing items that already have been classified and inferring a set of rules. The purpose of spatial classification is to assign each object of the database to a group, or class, according to a certain classification model. Firstly, we scan the records of the training set and create a description ofthe classification

2803

model. By learning the classes and their properties of the spatial data sets, so that we can construct the Bayesian network structure, that is to say, the classification model can be correctly created and can be used to classify all the remaining records of the database. The model created is tested against a new test set of the database. A classification model will always work perfectly on the training set which was used for its construction. Spatial classification is a natural task of spatial data mining, because it helps to divide the database in smaller homogeneous groups. It has many applications: image interpretation, performance prediction, selective marketing and others. Using Bayesian rule, we can compare two models using the ratio

P(w1, I x) > P(w2 I x)

P(wO1 I x) < P(w2 I x)

then xE then xE 2j E

(1)

Using Bayes chain rule, and let Pai is the set of parents of the variable Vi, so we can get the joint probability distribution:

P(V)

*

n

P(V,

Pa)

(2)

Spatial prediction is a goal-directed activity; knowledge discovery is more open ended, and searches without expectation for interesting patterns. Predictive methods search for and identify strong patterns in a given data set, so that new cases matched against these patterns can be labeled based on closeness of match to these existing data items. In predictive mining, the data model usually consists of a large sample set of cases, with each case containing a certain number of features. Formulating a predictive problem trains the system to "learn" which patterns match predefmed criteria within existing cases and which don't, and to accept or reject new cases based on these criteria. Bayesian network are capable of learning, the structure can be constructed by training the spatial data sets. And the resulting model has a clear interpretation. Bayesian networks frequently are applied to more general pattern recognition problems such as handwriting recognition and interpretation of electrocardiograms.

III.

CONSTRUCTION AND APPLICATION OF BAYESIAN

NETWORK MODELS

Variable definition. Define the relevant variables and the relationship between the variables. And the states of the variables should be defined. * Structure learning. In order to obtain the edge among the variables, we should cut the edges that did not exist. Further more, we should determine the directions of all edges based on prior knowledge and the given data set. Structure learning of Bayesian networks is the key step to perform reasoning and predicting. * Parameter estimation. It refers to define the conditional probabilities of the relationships. That is to say, this step should get a set of conditional probability distributions associated with every node. B. Application ofBayesian Network Models This application shows that we use Bayesian networks to spatial data mining in agricultural land gradation. The data set contains 2160 cases in land resource evaluation. The domain problem has 8 variables; each of them has several attributes. And one variable responds to one node in the model respectively. The variables and their implications describe as follows. 1) Soil erodibility (SE): the intensity of the soil that has been beaten by weather, rainwater or other chemicals. 2) Gradient (GR): A measure of slope (soil-surface), i.e. the rate of inclination for land topography changes. 3) Organic matter (OM): consists of plant and animal material that is in the process of decomposing. 4) Soil thickness (TI-H): it indicates the thickness of soil that available for Crop or other vegetation. 5) Irrigation efficiency (IE): It can be defined in terms of crop consumptive water use, irrigated area, harvested crop yield and total amount of water stored in the fields for the entire growing period. 6) Soil PH (PH): indicates the acidity of the soil, it can be determined by having a soil analysis carried out, and has a range approximately from 0 to 14;7) Soil texture (ST): the relative proportions of sand, silt, and clay particles in a mass of soil. 8) Land grades (LG): the quality of the agricultural land measured by the natural and economic characteristics. After defining the domain variables and data preparation, we can obtain the structure of the Bayesian network model by the three steps of construction model (showed as Fig. 2). And then we should compute the conditional probabilities of the relationships, and then integration the relative parameter into a complete Bayesian network. Eventually, a Bayesian network model for spatial data mining has been constructed.

*

A. Construction of Bayesian network models In the last few years Bayesian networks have become a popular way of modeling probabilistic relationships among a set of variables for a given domain [20-23]. Though, the construction of Bayesian networks is a hard task and the number of possible structures and the number of parameters for those structures can be huge. Learning a Bayesian network from data involves two tasks: Estimating the probabilities for the conditional probability tables (learning parameters) and deriving the structure of the network. Here we present a process of construction Bayesian networks, which includes three steps: variables definition, structure learning, and parameter estimation.

Figure 2. Bayesian network model for agricultural land gradation.

2804

We selected 200 cases to test the validity of the model. Table I showed the experiment results, the evaluation grade of 178 cases is the same as their actual grade, so the evaluation accuracy is 89.0%. Contrast of Bayesian networks and Naive Bayes for agricultural land gradation, we can conclude that the experimental results validate the practical viability of the proposed approach for spatial data mining.

TABLE I.

[3] [4] [5] [6]

CONTRAST OF BAYESIAN NETWORKS AND NAIVE BAYES FOR

AGRICULTURAL LAND GRADATION

method

Bayesian Network

Testing set

200

correct

Evaluation accuracy

89.0%

[7]

[8]

178

Naive Bayes

200

157

78.5%

IV. CONCLUSION AND FUTURE WORK Spatial data mining is a young and promising research domain. It is a potentially rich resource for spatial decision making and intelligent spatial analysis. More and more methods have been used to spatial data mining, including rough set, support vector machine, Markov Random Field, and decision tree, etc. In this paper, we focused on application of Bayesian network method to spatial data mining from a new point. Firstly, we introduce the theory of spatial data mining and discuss the characteristics of Bayesian networks. A framework and process of spatial data mining based on Bayesian networks has been proposed. Then we construct a Bayesian network model for spatial data mining with the given dataset. The experimental results demonstrate the feasibility and practical of the proposed approach to spatial data mining. Spatial data mining has been recognized as research topic only in recent years, which does present us with many theoretical challenges. That is to say, there are many research issues which need to further studied. For example, how to store the large amount of multidimensional spatial data? How to exact knowledge from spatio-temporal database? Another important issue is how to design algorithms that can handle diverse spatial data type as well as dynamic data types. As for future work, we would design and develop a spatial data mining tool based on Bayesian networks. Further more, spatial data mining should be combined with statistical analysis, spatial reasoning and GIS Agent to create spatial decision support system and intelligent spatial information system. ACKNOWLEDGEMENT The work presented in this paper was supported by the National Natural Science Foundation of P. R. China (40601076, 40571128) and Open Research Fund of State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing (WKL (06) 0303).

REFERENCES [1] R. F. Cromp, W. J. Campbell, "Data mining of multidimensional remotely sensed images," In Proceedings of the 2nd International Conference on Information and Knowledge Management, ACM, USA, pp. 471-480, November 1993. [2] W. Lu, J. Han, and B. C. Ooi, "Discovery of general Knowledge in Large Spatial Database," In Proceedings of Far East Workshop on Geographic Information Systems, Singapore, pp. 275-289, June 1993.

[9]

[10] [11] [12] [13] [14]

[15] [16] [17] [18] [19] [20]

[21] [22]

[23]

T. Beaubouef, R. Ladner, F. Petry, "Rough set spatial data modeling for data mining," International Journal of Intelligent Systems, United States, vol. 19, pp. 567-584, July 2004. R. T. Ng, J. Han, "CLARANS: A method for clustering objects for spatial data mining," IEEE Transactions on Knowledge and Data Engineering, vol. 14, pp. 1003-1016, September/October 2002. A. J. Brimicombe, "Cluster discovery in spatial data mining: A variable resolution approach," Management Information Systems, vol. 6, pp. 625-634, September 2002. M. Salmenkivi, "Efficient mining of correlation patterns in spatial point data," Lecture Notes in Computer Science, Germany, vol. 4213, pp. 359370, September 2006. S. Zhang, Z. Zhu, "Parallelism of spatial data mining based on autocorrelation decision tree," Journal of Systems Engineering and Electronics, vol.16, pp.947-956, December 2005. D. Guo, M. Gahegan, "Spatial ordering and encoding for geographic data mining and visualization," Journal of Intelligent Information Systems, vol.27, n 3, pp. 243-266, November 2006. S. Shekhar, P. R. Schrater, R. R.Vatsavai, W. Wu, S. Chawla, "Spatial contextual classification and prediction models for mining geospatial data," IEEE Transactions on Multimedia, vol. 4, n 2, pp. 174-188, June 2002. D. Malerba, M. Ceci, A. Appice, "Mining model trees from spatial data," Lecture Notes in Computer Science, Germany, vol. 3721 LNAI, pp. 169-180, October 2005. N. Green, "A Bayesian network coding scheme for annotating biomedical information presented to genetic counseling clients," Journal of Biomedical Informatics, vol. 38, n 2, pp. 130-144, April 2005. V. Labatut, J. Pastor, S. Ruff, J. F. Demonet, P. Celsis, "Cerebral modeling and dynamic Bayesian networks," Artificial Intelligence in Medicine, vol. 30, pp. 119-139, February 2004. J. Luo, A. E. Savakis, A. Singhal, "A Bayesian network-based framework for semantic image understanding," Pattern Recognition, vol. 38, n 6, pp. 919-934, June 2005. C. Solares, A. M. Sanz, "Bayesian network classifiers: An application to remote sensing image classification," WSEAS Transactions on Systems, vol. 4, pp. 343-348, April 2005. K. C. Van, A. R. Gray, "An application of Bayesian network for predicting object-oriented software maintainability," Information and Software Technology, vol. 48, pp. 59-67, January 2006. S. Sun, C. Zhang, G. Yu, "A Bayesian network approach to traffic flow forecasting," IEEE Transactions on Intelligent Transportation Systems, vol. 7, pp. 124-133, March 2006. N. J. Randon, J. Lawry, "Probabilistic and fuzzy methods for information fusion in data mining," International Journal of Intelligent Systems, vol.18, pp.609-631, June 2003. A. Porwal, E. J. Carranza, M. Hale, "Bayesian network classifiers for mineral potential mapping," Computers and Geosciences, vol.32(1), pp. 1-16, February 2006. A. Ouali, C. A Ramdane, M. 0. Krebs, "Data mining based Bayesian networks for best classification," Computational Statistics and Data Analysis, Netherlands, vol. 51, pp. 1278-1292, November 2006. C. J. Lee, K. J. Lee, "Application of Bayesian network to the probabilistic risk assessment of nuclear waste disposal," Reliability Engineering and System Safety, United Kingdom, vol. 91, pp. 515-532, May 2006. J. Huang, H. Pan, Y.Wan, "An algorithm for cooperative learning of Bayesian network structure from data," Lecture Notes in Computer Science, Germany, vol. 3168 LNCS, pp. 86-94, October 2005 L. Falzon, "Using Bayesian network analysis to support centre of gravity analysis in military planning," European Journal of Operational Research, Netherlands, vol. 170, n 2, pp. 629-643, April 2006. J. Del Sagrado, S. Moral, "Qualitative combination of Bayesian networks," International Journal of Intelligent Systems, United Kingdom, vol. 18, n 2, pp. 237-249, February 2003.

2805