Geographic Data Mining and Knowledge Discovery, Second Edition (Chapman & Hall/Crc Data Mining and Knowledge Discovery)

This is the definitive volume on cutting-edge exploratory analysis of massive spatial and spatiotemporal databases. Since the publication of the first edition of Geographic Data Mining and Knowledge Discovery, new techniques for geographic data warehousing (GDW), spatial data mining, and geovisualization (GVis) have been developed. In addition, there has been a rise in the use of knowledge discovery techniques due to the increasing collection and storage of data on spatiotemporal processes and mobile objects. Incorporating these novel developments, this second edition reflects the current state of the art in the field. New to the Second Edition offers: updated material on geographic knowledge discovery (GKD), GDW research, map cubes, spatial dependency, spatial clustering methods, clustering techniques for trajectory data, the INGENS 2.0 software, and GVis techniques; new chapter on data quality issues in GKD; new chapter that presents a tree-based partition querying methodology for medoid computation in large spatial databases; new chapter that discusses the use of geographically weighted regression as an exploratory technique; new chapter that gives an integrated approach to multivariate analysis and geovisualization; and, five new chapters on knowledge discovery from spatiotemporal and mobile objects databases. Geographic Data Mining and Knowledge Discovery is a promising young discipline with many challenging research problems. This book shows that this area represents an important direction in the development of a new generation of spatial analysis tools for data-rich environments. Exploring various problems and possible solutions, it will motivate researchers to develop new methods and applications in this emerging field Geographic Data Mining and Knowledge Discovery, Second Edition......Page 3 Contents......Page 5 Acknowledgments......Page 7 About The Editors......Page 8 List of Contributors......Page 9 Table of Contents......Page 0 CONTENTS......Page 11 1.1 INTRODUCTION......Page 12 1.2.1 KNOWLEDGE DISCOVERY FROM DATABASES......Page 13 1.2.2 DATA WAREHOUSING......Page 14 1.2.3 THE KDD PROCESS AND DATA MINING......Page 16 1.2.4 VISUALIZATION AND KNOWLEDGE DISCOVERY......Page 19 1.3.1.1 Geographic Information in Knowledge Discovery......Page 20 1.3.1.3 Geographic Knowledge Discovery in Geographic Research......Page 23 1.3.2 GEOGRAPHIC DATA WAREHOUSING......Page 24 1.3.3.1 Spatial Classification and Capturing Spatial Dependency......Page 25 1.3.3.2 Spatial Segmentation and Clustering......Page 26 1.3.3.5 Spatial Association......Page 27 1.3.4 GEOVISUALIZATION......Page 28 1.3.5 SPATIOTEMPORAL AND MOBILE OBJECTS DATABASES......Page 29 REFERENCES......Page 31 2.1 INTRODUCTION......Page 37 2.2.1 RULE TYPES......Page 39 2.2.2 SPATIAL VS. SPATIO-TEMPORAL DATA......Page 40 2.2.3 HANDLING SECOND-HAND DATA......Page 44 2.3 META-MINING AS A DISCOVERY PROCESS PARADIGM......Page 45 2.4.1 THE PROCESS OF SCIENTIFIC INDUCTION......Page 47 2.4.2 USING DATA MINING TO SUPPORT SCIENTIFIC INDUCTION......Page 49 ACKNOWLEDGMENTS......Page 50 REFERENCES......Page 51 3.1 INTRODUCTION......Page 55 3.2 KEY CONCEPTS AND ARCHITECTURES FOR DATA WAREHOUSES......Page 57 3.2.1 DATA WAREHOUSE......Page 58 3.2.2 MULTIDIMENSIONAL DATA STRUCTURE......Page 61 3.2.3 DATA MART......Page 63 3.2.4 ONLINE ANALYTICAL PROCESSING (OLAP)......Page 64 3.2.5 DATA MINING......Page 65 3.2.6 DATA WAREHOUSE ARCHITECTURES......Page 66 3.3 SPATIAL DATA WAREHOUSING......Page 68 3.3.1 SPATIAL DATA CUBES......Page 69 3.3.2 SPATIAL DIMENSIONS......Page 70 3.3.4 SPATIAL ETL......Page 73 3.3.5 SPATIAL OLAP OPERATORS......Page 74 3.4 DISCUSSION AND CONCLUSION......Page 75 REFERENCES......Page 76 CONTENTS......Page 79 4.1 INTRODUCTION......Page 80 4.2.1 AN EXAMPLE OF GEOGRAPHIC INFORMATION SYSTEM......Page 81 4.2.2 AGGREGATE FUNCTIONS......Page 83 4.2.3 AGGREGATION HIERARCHY......Page 85 4.2.4 THE ROLE OF AN AGGREGATION HIERARCHY......Page 88 4.3.1 DEFINITION......Page 89 4.3.2 STEPS IN GENERATING A MAP CUBE......Page 91 4.3.3 THE GRAMMAR FOR THE MAP CUBE OPERATOR......Page 92 4.4 APPLICATION OF MAP CUBE IN TRANSPORTATION DATA......Page 93 C. Highway Station Plot (SHS)......Page 94 D. Highway Station vs. Time of Day Plot (SHSTTD)......Page 96 E. Highway Stations vs. Day of Week Plot (SHSTDW)......Page 97 4.5 CASE STUDY — TRAFFIC INCIDENT ANALYSIS......Page 99 4.6 CONCLUSION AND FUTURE WORK......Page 106 REFERENCES......Page 107 5.1 INTRODUCTION......Page 108 5.2 FUNDAMENTAL CONCEPTS OF SPATIAL DATA QUALITY AND UNCERTAINTY IN A GEOGRAPHIC KNOWLEDGE DISCOVERY CONTEXT......Page 109 5.2.1 GEOSPATIAL DATA QUALITY AND UNCERTAINTY......Page 110 5.3 EXISTING APPROACHES TO PREVENT USERS FROM SPATIAL DATA MISUSES......Page 112 5.4 AN APPROACH BASED ON RISK MANAGEMENT TO PREVENT DATA MISUSES IN DATA WAREHOUSING AND GKD CONTEXTS......Page 113 5.5.1 LEGAL CRITERIA FOR SPATIAL DATACUBE PRODUCERS RELATED TO THE INTERNAL QUALITY OF DATA......Page 117 5.5.2 LEGAL CRITERIA FOR SPATIAL DATACUBE PRODUCERS RELATED TO THE EXTERNAL QUALITY OF DATA......Page 118 5.5.4 LEGAL PERTINENCE OF A RISK-MANAGEMENT APPROACH......Page 119 REFERENCES......Page 120 CONTENTS......Page 125 6.1 INTRODUCTION......Page 126 6.1.1 OUTLINE AND SCOPE OF THIS CHAPTER......Page 127 6.2.1 BIRD NESTING LOCATION PREDICTION......Page 128 6.2.3 LOCATION PREDICTION: PROBLEM FORMULATION......Page 131 6.3.1 LOGISTIC REGRESSION MODELING......Page 133 6.3.2 BAYESIAN CLASSIFICATION......Page 134 6.4.1 SPATIAL AUTOREGRESSION MODEL (SAR)......Page 136 6.4.2 MARKOV RANDOM FIELD CLASSIFIERS......Page 137 6.5.1 COMPARISON OF SAR AND MRF USING A PROBABILISTIC FRAMEWORK......Page 138 6.5.2.1 Metrics of Comparison for Classification Accuracy......Page 141 6.5.2.2 Metrics of Comparison for Spatial Accuracy......Page 142 6.5.4.1 Spatial Accuracy Results (SAR and MRF Comparision)......Page 143 6.5.5.1 Spatial Accuracy Result of Comparison SAR and MRF Models for Linearly Separable Synthetic Datasets......Page 145 6.6 SPATIAL SEMISUPERVISED CLASSIFICATION......Page 147 6.6.2 SPATIAL EXTENSION OF SEMISUPERVISED LEARNING......Page 148 6.6.3 EXPERIMENTAL RESULTS......Page 150 6.7 CONCLUSIONS AND FUTURE WORK......Page 151 REFERENCES......Page 152 CONTENTS......Page 172 7.1 INTRODUCTION......Page 173 7.2.1.2 Geographic Customer Segmentation......Page 174 7.2.1.3 Crime Hot-Spot Analysis......Page 175 7.2.1.4 Land Use Detection......Page 176 7.2.2 CATEGORIZATION OF MAJOR CLUSTERING METHODS......Page 177 7.2.3.1 Centroid-Based Technique: The k-Means Method......Page 179 7.2.3.2 Representative Object-Based Technique: The k-Medoids Method......Page 181 7.2.3.3 A Model-Based Method: Expectation-Maximization (EM)......Page 183 7.2.3.4 Partitioning Methods in Large Databases: From k-Medoids to CLARANS......Page 185 7.2.4.1 Agglomerative and Divisive Hierarchical Clustering......Page 186 7.2.4.2 BIRCH: Balanced Iterative Reducing and Clustering Using Hierarchies......Page 188 7.2.4.3 Chameleon: A Hierarchical Clustering Algorithm Using Dynamic Modeling......Page 190 7.2.5.1 DBSCAN: A Density-Based Clustering Method Based on Connected Regions with Sufficiently High Density......Page 193 7.2.5.2 OPTICS: Ordering Points to Identify the Clustering Structure......Page 195 7.2.5.3 DENCLUE: Clustering Based on Density Distribution Functions......Page 196 7.3.1 APPLICATION: TROPICAL CYCLONE TRAJECTORY ANALYSIS......Page 199 7.3.2.1 Probabilistic Method......Page 201 7.3.2.2 Density-Based Method......Page 202 7.3.3.1 Overall Procedure......Page 203 7.3.3.2 The Partitioning Phase......Page 205 7.3.3.4 Clustering Result......Page 206 7.4 SUMMARY......Page 207 REFERENCES......Page 208 8.1 INTRODUCTION......Page 211 8.2.1 R-TREES AND NEAREST NEIGHBOR SEARCH......Page 213 8.2.2 K-MEDOIDS AND RELATED PROBLEMS......Page 215 8.3 FRAMEWORK OVERVIEW AND BASIC DEFINITIONS......Page 217 8.4 k-MEDOID QUERIES......Page 219 8.5 MEDOID-AGGREGATE QUERIES......Page 223 8.6 MEDOID-OPTIMIZATION QUERIES......Page 226 8.7.1 K-MEDOID QUERIES......Page 229 8.7.2 MEDOID-AGGREGATE QUERIES......Page 237 8.7.3 MEDOID-OPTIMIZATION QUERIES......Page 240 REFERENCES......Page 247 9.1 INTRODUCTION......Page 249 9.2 LINEAR REGRESSION......Page 251 9.3 REGRESSION WITH SPATIAL DATA......Page 252 9.4.1 HOW WELL DOES THE MODEL FIT?......Page 253 9.5 GEOVISUAL ANALYTICS AND GWR......Page 255 9.6.1 THE DATA......Page 256 9.6.2 GENERAL PATTERNS IN THE DATA......Page 259 9.6.3 GLOBAL MODEL......Page 261 9.6.5 RESULTS......Page 263 9.6.6 LOCAL PARAMETER ESTIMATE MAPS......Page 264 9.6.7 VISUALIZING THE RESULTS — FURTHER INSIGHTS......Page 269 9.7 CONCLUSIONS......Page 273 REFERENCES......Page 274 CONTENTS......Page 277 10.1 INTRODUCTION......Page 278 10.2 SPATIAL DATA MINING AND GIS......Page 280 10.3 INGENS 2.0 ARCHITECTURE AND SPATIAL DATA MODEL......Page 282 10.4.1 CONCEPTUAL DESCRIPTION GENERATION......Page 286 10.4.2 CLASSIFICATION RULE DISCOVERY......Page 288 10.4.3 ASSOCIATION RULE DISCOVERY......Page 292 10.5 SDMOQL......Page 294 10.5.1 DATA SPECIFICATION......Page 295 10.5.2 THE KIND OF KNOWLEDGE TO BE MINED......Page 296 10.5.3 SPECIFICATION OF PRIMITIVE AND PATTERN DESCRIPTORS......Page 297 10.5.4 SYNTAX FOR BACKGROUND KNOWLEDGE AND CONCEPT HIERARCHY SPECIFICATION......Page 299 10.6.1 MINING CLASSIFICATION RULES......Page 300 10.6.2 ASSOCIATION RULES......Page 304 10.7 CONCLUDING REMARKS AND DIRECTIONS FOR FURTHER RESEARCH......Page 306 REFERENCES......Page 308 11.1 INTRODUCTION......Page 312 11.1.1 WHY IS THERE A NEED FOR VISUALLY LED EXPLORATION?......Page 314 11.1.3 RESEARCH TO DATE......Page 316 11.2.1 VISUALLY ENCODING DATA......Page 318 11.2.2 VISUALIZATION TECHNIQUES FOR DATA EXPLORATION......Page 321 11.3.1 DEDUCTION......Page 330 11.3.3 ABDUCTION......Page 331 11.3.4 FORMING CHAINS OF INFERENCE......Page 332 11.4 COMBINING THE TECHNIQUES WITH THE PHILOSOPHY......Page 336 11.5 CONCLUSIONS AND CHALLENGES FOR GEOVISUALIZATION......Page 338 REFERENCES......Page 341 12.1 INTRODUCTION......Page 346 12.2.1 CLUSTER ANALYSIS......Page 348 12.2.2 REGIONALIZATION......Page 349 12.2.3 GEOVISUALIZATION......Page 350 12.3.1 A THEORETICAL FRAMEWORK......Page 352 12.3.2 MULTIVARIATE CLUSTERING AND PATTERN ENCODING......Page 354 12.3.3 MULTIVARIATE VISUALIZATION AND MAPPING......Page 356 12.3.4 REGIONALIZATION WITH SPATIALLY CONSTRAINED HIERARCHICAL CLUSTERING......Page 357 12.4.2 DISCOVERING CLIMATE CHANGE PATTERNS......Page 358 12.4.3 COMPARING REGIONALIZATION AND SOM RESULTS......Page 360 12.5 CONCLUSION AND DISCUSSION......Page 362 REFERENCES......Page 363 13.1 INTRODUCTION......Page 367 13.2 SPATIOTEMPORAL CONSTRUCTS OF GEOGRAPHIC DYNAMICS: ACTIVITY, EVENT, AND PROCESS......Page 368 13.3 EXTENDING GEOGRAPHIC SPACE TO GEOGRAPHIC DYNAMICS IN A GIS ANALYSIS FRAMEWORK......Page 373 13.4 SEQUENCING CONSIDERATIONS IN ASSEMBLING SPATIOTEMPORAL CONSTRUCTS OF GEOGRAPHIC DYNAMICS......Page 375 13.5 FROM SPATIOTEMPORAL DATABASES TO KNOWLEDGE OF GEOGRAPHIC DYNAMICS......Page 378 13.6 CONCLUDING REMARKS......Page 380 REFERENCES......Page 382 CONTENTS......Page 386 14.1 INTRODUCTION......Page 387 14.2 THE ONTOLOGICAL FOUNDATION FOR A GKDD PROCESS......Page 389 14.2.1 THE GKDD ONTOLOGICAL TIERS......Page 390 14.2.2 THE FORMALIZATION OF THE DATA ONTOLOGY TIER......Page 392 14.2.2.1 The Movement-as-Trajectory Metaphor within the Data Ontology Tier......Page 393 14.3.1 CONCEPTUAL DATABASE MODELING FOR TRAJECTORY......Page 394 14.3.2 IMPLEMENTATION......Page 397 14.3.2.1 Mapping Assertions......Page 399 14.4 REASONING AND QUERYING......Page 400 14.5 CONCLUSIONS......Page 402 REFERENCES......Page 404 15.1 INTRODUCTION......Page 407 15.2 LITERATURE OF MINING TRAJECTORY DATA......Page 408 15.3.1 MOTIVATING EXAMPLE AND NAIVE METHOD......Page 409 15.3.2 MODEL......Page 411 15.3.3.1 Obtaining Frequent 1-Patterns......Page 413 15.3.3.2 A Level-Wise, Bottom-Up Approach......Page 414 15.3.3.3 A Two-Phase, Top-Down Algorithm......Page 415 15.3.3.5 Effectiveness......Page 418 15.3.4 VARIANTS......Page 420 15.3.4.1 Patterns with Validity Eras......Page 421 15.3.4.2 Shifted and Distorted Patterns......Page 422 15.4 OPEN ISSUES......Page 423 REFERENCES......Page 424 CONTENTS......Page 427 16.2.1 DISTRIBUTED AND DECENTRALIZED SPATIAL COMPUTING......Page 428 16.2.2 CENTRALIZED (GEOGRAPHIC) KNOWLEDGE DISCOVERY AND DATA MINING......Page 430 16.3 DECENTRALIZED SPATIAL DATA MINING (DSDM)......Page 431 16.3.1 PROBLEM DEFINITION......Page 432 16.3.2.1 Geosensor Networks......Page 433 16.3.2.2 Clusters......Page 435 16.3.3.3 Selective Collaboration......Page 436 16.3.3.4 Node Mobility......Page 437 16.4.1 NAIVIE CLUSTERING (NC)......Page 438 16.4.2 HAPPINESS EXTRAPOLATION CLUSTERING (HEC)......Page 439 16.4.3 HAPPINESS ABSORPTION CLUSTERING (HAC)......Page 441 16.5 EXPERIMENTS......Page 443 16.5.2 RESULTS......Page 444 16.6 DISCUSSION AND CONCLUSIONS......Page 445 ACKNOWLEDGMENTS......Page 446 REFERENCES......Page 447 17.1 INTRODUCTION......Page 449 17.2 TRADITIONAL SOLUTIONS: FRAMEWORKS, TOOLS, AND TECHNIQUES......Page 450 17.3.1 BACKGROUND......Page 452 17.3.2 STC IN GEOVISUAL ANALYTICS 1 — LINKING MOVEMENT AND ATTRIBUTE DATA......Page 453 17.3.3 STC IN GEOVISUAL ANALYTICS 2 — ANALYZING POTENTIAL MOVEMENT AND ACTIVITIES......Page 456 17.4 DISCUSSION AND CONCLUSION......Page 459 REFERENCES......Page 460