Geographic
Data Mining and
Knowledge Discovery
Second Edition
© 2009 by Taylor & Francis Group, LLC
Chapman & Hall/CRC
Data Mining and Knowledge Discovery Series
SERIES EDITOR
Vipin Kumar
University of Minnesota
Department of Computer Science and Engineering
Minneapolis, Minnesota, U.S.A.
AIMS AND SCOPE
This series aims to capture new developments and applications in data mining and knowledge
discovery, while summarizing the computational tools and techniques useful in data analysis. This
series encourages the integration of mathematical, statistical, and computational methods and
techniques through the publication of a broad range of textbooks, reference works, and hand-
books. The inclusion of concrete examples and applications is highly encouraged. The scope of the
series includes, but is not limited to, titles in the areas of data mining and knowledge discovery
methods and applications, modeling, algorithms, theory and foundations, data and knowledge
visualization, data mining systems and tools, and privacy and security issues.
PUBLISHED TITLES
UNDERSTANDING COMPLEX DATASETS: Data Mining with Matrix Decompositions
David Skillicorn
COMPUTATIONAL METHODS OF FEATURE SELECTION
Huan Liu and Hiroshi Motoda
CONSTRAINED CLUSTERING: Advances in Algorithms, Theory, and Applications
Sugato Basu, Ian Davidson, and Kiri L. Wagstaff
KNOWLEDGE DISCOVERY FOR COUNTERTERRORISM AND LAW ENFORCEMENT
David Skillicorn
MULTIMEDIA DATA MINING: A Systematic Introduction to Concepts and Theory
Zhongfei Zhang and Ruofei Zhang
NEXT GENERATION OF DATA MINING
Hillol Kargupta, Jiawei Han, Philip S. Yu, Rajeev Motwani, and Vipin Kumar
DATA MINING FOR DESIGN AND MARKETING
Yukio Ohsawa and Katsutoshi Yada
GEOGRAPHIC DATA MINING AND KNOWLEDGE DISCOVERY, Second Edition
Harvey J. Miller and Jiawei Han
© 2009 by Taylor & Francis Group, LLC
Chapman & Hall/CRC
Data Mining and Knowledge Discovery Series
Geographic
Data Mining and
Knowledge Discovery
Second Edition
Edited by
Harvey J. Miller
Jiawei Han
© 2009 by Taylor & Francis Group, LLC
CRC Press
Taylor & Francis Group
6000 Broken Sound Parkway NW, Suite 300
Boca Raton, FL 33487-2742
© 2009 by Taylor & Francis Group, LLC
CRC Press is an imprint of Taylor & Francis Group, an Informa business
No claim to original U.S. Government works
Printed in the United States of America on acid-free paper
10 9 8 7 6 5 4 3 2 1
International Standard Book Number-13: 978-1-4200-7397-3 (Hardcover)
This book contains information obtained from authentic and highly regarded sources. Reasonable
efforts have been made to publish reliable data and information, but the author and publisher can-
not assume responsibility for the validity of all materials or the consequences of their use. The
authors and publishers have attempted to trace the copyright holders of all material reproduced
in this publication and apologize to copyright holders if permission to publish in this form has not
been obtained. If any copyright material has not been acknowledged please write and let us know so
we may rectify in any future reprint.
Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced,
transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or
hereafter invented, including photocopying, microfilming, and recording, or in any information
storage or retrieval system, without written permission from the publishers.
For permission to photocopy or use material electronically from this work, please access www.copy-
right.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222
Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that pro-
vides licenses and registration for a variety of users. For organizations that have been granted a
photocopy license by the CCC, a separate system of payment has been arranged.
Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and
are used only for identification and explanation without intent to infringe.
Library of Congress Cataloging-in-Publication Data
Geographic data mining and knowledge discovery / editors, Harvey J. Miller and
Jiawei Han. -- 2nd ed.
p. cm.
Includes bibliographical references and index.
ISBN 978-1-4200-7397-3 (hard back : alk. paper)
1. Geodatabases. 2. Data mining. I. Miller, Harvey J. II. Han, Jiawei. III. Title.
G70.2.G4365 2009
910.285 6312--dc22 2009010969
Visit the Taylor & Francis Web site at
http://www.taylorandfrancis.com
and the CRC Press Web site at
http://www.crcpress.com
© 2009 by Taylor & Francis Group, LLC
Contents
Acknowledgments ..................................................................................................vii
About the Editors ....................................................................................................ix
List of Contributors ................................................................................................xi
Chapter 1 Geographic Data Mining and Knowledge Discovery:
An Overview ........................................................................................1
Harvey J. Miller and Jiawei Han
Chapter 2 Spatio-Temporal Data Mining Paradigms and Methodologies ..........27
John F. Roddick and Brian G. Lees
Chapter 3 Fundamentals of Spatial Data Warehousing for Geographic
Knowledge Discovery ........................................................................ 45
Yvan Bédard and Jiawei Han
Chapter 4 Analysis of Spatial Data with Map Cubes:
Highway Traffic Data .........................................................................69
Chang-Tien Lu, Arnold P. Boedihardjo, and Shashi Shekhar
Chapter 5 Data Quality Issues and Geographic Knowledge Discovery .............99
Marc Gervais, Yvan Bédard, Marie-Andree Levesque,
Eveline Bernier, and Rodolphe Devillers
Chapter 6 Spatial Classification and Prediction Models for Geospatial
Data Mining ..................................................................................... 117
Shashi Shekhar, Ranga Raju Vatsavai, and Sanjay Chawla
Chapter 7 An Overview of Clustering Methods in Geographic Data
Analysis ............................................................................................ 149
Jiawei Han, Jae-Gil Lee, and Micheline Kamber
© 2009 by Taylor & Francis Group, LLC
Chapter 8 Computing Medoids in Large Spatial Datasets................................ 189
Kyriakos Mouratidis, Dimitris Papadias, and Spiros Papadimitriou
Chapter 9 Looking for a Relationship? Try GWR ............................................227
A. Stewart Fotheringham, Martin Charlton, and Ura
ka Dema
ar
Chapter 10 Leveraging the Power of Spatial Data Mining to Enhance the
Applicability of GIS Technology ..................................................... 255
Donato Malerba, Antonietta Lanza, and Annalisa Appice
Chapter 11 Visual Exploration and Explanation in Geography
Analysis with Light .......................................................................... 291
Mark Gahegan
Chapter 12 Multivariate Spatial Clustering and Geovisualization ..................... 325
Diansheng Guo
Chapter 13 Toward Knowledge Discovery about Geographic Dynamics in
Spatiotemporal Databases ................................................................ 347
May Yuan
Chapter 14 The Role of a Multitier Ontological Framework in Reasoning
to Discover Meaningful Patterns of Sustainable Mobility............... 367
Monica Wachowicz, Jose Macedo, Chiara Renso, and
Arend Ligtenberg
Chapter 15 Periodic Pattern Discovery from Trajectories of Moving Objects ... 389
Huiping Cao, Nikos Mamoulis, and David W. Cheung
Chapter 16 Decentralized Spatial Data Mining for Geosensor Networks..........409
Patrick Laube and Matt Duckham
Chapter 17 Beyond Exploratory Visualization of Space Time Paths ................ 431
Menno-Jan Kraak and Otto Huisman
© 2009 by Taylor & Francis Group, LLC
Acknowledgments
The editors would like to thank the National Center for Geographic Information and
Analysis (NCGIA)  Project Varenius for supporting the March 1999 workshop
that resulted in the first edition of this book. A special thanks to Randi Cohen (Taylor
& Francis Group) who proposed a second edition and worked tirelessly on its behalf
with organizational skills that greatly exceed ours.
© 2009 by Taylor & Francis Group, LLC
About The Editors
Harvey J. Miller is professor of geography at the University of Utah. His research
and teaching interests include geographic information systems (GIS), spatial analysis,
and geocomputational techniques applied to understanding how transportation and
communication technologies shape lives, cities, and societies. He has contributed to
the theory and methodology underlying time geography: a perspective that focuses
on personal allocation of time among activities in space and its implications for indi-
vidual and collective spatial dynamics. He is the author (with Shih-Lung Shaw) of
Geographic Information Systems for Transportation: Principles and Applications
(Oxford University Press) and editor of Societies and Cities in the Age of Instant Access
(Springer). Professor Miller serves on the editorial boards of Geographical Analysis,
International Journal of Geographical Information Science, Journal of Regional
Science, Transportation, URISA Journal, and Journal of Transport and Land Use. He
was the North American editor of International Journal of Geographical Information
Science from 2000 to 2004. Professor Miller has also served as an officer or board
member of the North American Regional Science Council, the University Consortium
for Geographic Information Science, the Association of American Geographers,
and the Transportation Research Board (TRB). He is currently cochair of the TRB
Committee on Geographic Information Science and Applications.
Jiawei Han is professor in the department of computer science, University of Illinois
at Urbana-Champaign. He has been working on research in data mining, data ware-
housing, database systems, data mining from spatiotemporal data, multimedia data,
stream and radio frequency identification (RFID) data, social network data, and bio-
logical data, and has to his credit over 350 journal and conference publications. He
has chaired or served on over 100 program committees of international conferences
and workshops, including PC cochair of 2005 (IEEE) International Conference on
Data Mining (ICDM), American coordinator of 2006 International Conference on
Very Large Data Bases (VLDB), and senior PC member for the 2008 ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining. He is also serv-
ing as the founding editor-in-chief of ACM Transactions on Knowledge Discovery from
Data. He is an ACM Fellow and has received the 2004 ACM SIGKDD Innovations
Award and 2005 IEEE Computer Society Technical Achievement Award. His book
Data Mining: Concepts and Techniques (2nd ed., Morgan Kaufmann, 2006) has
been popularly used as a textbook worldwide.
© 2009 by Taylor & Francis Group, LLC
List of Contributors
Annalisa Appice Matt Duckham
UniversitÄ… degli Studi di Bari University of Melbourne
Bari, Italy Victoria, Australia
A. Stewart Fotheringham
Yvan Bédard
National University of Ireland
Laval University
County Kildare, Ireland
Quebec City, Canada
Mark Gahegan
Eveline Bernier
University of Auckland
Laval University
Auckland, New Zealand
Quebec City, Canada
Marc Gervais
Arnold P. Boedihardjo
Laval University
Virginia Tech
Quebec City, Canada
Blacksburg, Virginia
Diansheng Guo
University of South Carolina
Huiping Cao
Columbia, South Carolina
University of Hong Kong
Hong Kong
Otto Huisman
International Institute for
Martin Charlton
GeoInformation Science
National University of Ireland
and Earth Observation (ITC)
County Kildare, Ireland
Enschede, Netherlands
Sanjay Chawla
Micheline Kamber
University of Sydney
Burnaby, Canada
Sydney, Australia
Menno-Jan Kraak
International Institute for
David W. Cheung
GeoInformation Science
University of Hong Kong
and Earth Observation (ITC)
Hong Kong
Enschede, Netherlands
Ura
ka Dema
ar
Antonietta Lanza
National University of Ireland
UniversitÄ… degli Studi di Bari
County Kildare, Ireland
Bari, Italy
Rodolphe Devillers
Patrick Laube
Memorial University of Newfoundland
University of Melbourne
St. John s, Canada
Victoria, Australia
© 2009 by Taylor & Francis Group, LLC
Jae-Gil Lee Dimitris Papadias
University of Illinois Hong Kong University of Science
Urbana-Champaign and Technology
Urbana, Illinois Clear Water Bay, Hong Kong
Brian G. Lees
Spiros Papadimitriou
University of New South Wales
IBM T.J. Watson Research Center
Canberra, Australia
Hawthorne, New York
Marie-Andree Levesque
Chiara Renso
Laval University
KDDLAB-CNR
Quebec City, Canada
Pisa, Italy
Arend Ligtenberg
John F. Roddick
Wageningen University and Research
Flinders University
Wageningen, Netherlands
Adelaide, South Australia
Chang-Tien Lu
Shashi Shekhar
Virginia Tech
University of Minnesota
Blacksburg, Virginia
Minneapolis, Minnesota
Jose Macedo
Ranga Raju Vatsavai
Swiss Federal Institute of Technology
Oak Ridge National Laboratory
Zurich, Switzerland
Oak Ridge, Tennessee
Donato Malerba
Monica Wachowicz
UniversitÄ… degli Studi di Bari
Technical University of Madrid
Bari, Italy
Madrid, Spain
and
Nikos Mamoulis
Wageningen University and Research
University of Hong Kong
Wageningen, Netherlands
Hong Kong
Kyriakos Mouratidis May Yuan
Singapore Management University University of Oklahoma
Singapore Norman, Oklahoma
© 2009 by Taylor & Francis Group, LLC