\ ( ( PANG.N I NG TAN Michigan State University MICHAEL STEINBACH University of Minnesota VI PI N KU MAR University of Minnesota and Army High Performance Computing Research Center +f.f_l crf.rfh. .W if f aqtY 6l$ t.T.R.C. i'&'ufe61ttt1/. Y \ t.\ $t,/,1' n,5 \. 7\ V '48! Boston San Francisco NewYork London Toronto Sydney Tokyo Singapore Madrid MexicoCity Munich Paris CapeTown HongKong Montreal G.R r+6,q If you purchased this book within the United States or Canada you should be aware that it has been wrongfirlly imported without the approval of the Publishel or the Author. T3 Loo 6 - {)gq* 3 AcquisitionsEditor Matt Goldstein ProjectEditor Katherine Harutunian Production Supervisor Marilyn Lloyd Production Services Paul C. Anagnostopoulos of Windfall Software Marketing Manager Michelle Brown Copyeditor Kathy Smith Proofreader IenniferMcClain Technicallllustration GeorgeNichols Cover Design Supervisor Joyce Cosentino Wells Cover Design Night & Day Design Cover Image @ 2005 Rob Casey/Brand X pictures hepress and Manufacturing Caroline Fell Printer HamiltonPrinting Access the latest information about Addison-Wesley titles from our iWorld Wide Web site: http : //www. aw-bc.com/computing Many of the designations used by manufacturers and sellers to distiriguish their products are claimed as trademarks. where those designations appear in this book, and Addison- Wesley was aware of a trademark claim, the designations have been printed in initial caps or all caps. The programs and applications presented in this book have been incl,[rded for their instructional value. They have been tested with care, but are not guatanteed for any particular purpose. The publisher does not offer any warranties or representations, nor does it accept any liabilities with respect to the programs or applications. Copyright @ 2006 by Pearson Education, Inc. For information on obtaining permission for use of material in this work, please submit a written request to Pearson Education, Inc., Rights and Contract Department, 75 Arlington Street, Suite 300, Boston, MA02II6 or fax your request to (617) g4g-j047. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or any other media embodiments now known or hereafter to become known, without the prior written permission of the publisher. printed in the united States of America. lsBN 0-321-42052-7 2 3 4 5 67 8 9 10-HAM-O8 07 06 our famili,es Preface Advances in data generation and collection are producing data sets of mas- sive size in commerce and a variety of scientific disciplines. Data warehouses store details of the sales and operations of businesses, Earth-orbiting satellites beam high-resolution images and sensor data back to Earth, and genomics ex- periments generate sequence, structural, and functional data for an increasing number of organisms. The ease with which data can now be gathered and stored has created a new attitude toward data analysis: Gather whatever data you can whenever and wherever possible. It has become an article of faith that the gathered data will have value, either for the purpose that initially motivated its collection or for purposes not yet envisioned. The field of data mining grew out of the limitations of current data anal- ysis techniques in handling the challenges posedl by these new types of data sets. Data mining does not replace other areas of data analysis, but rather takes them as the foundation for much of its work. While some areas of data mining, such as association analysis, are unique to the field, other areas, such as clustering, classification, and anomaly detection, build upon a long history of work on these topics in other fields. Indeed, the willingness of data mining researchers to draw upon existing techniques has contributed to the strength and breadth of the field, as well as to its rapid growth. Another strength of the field has been its emphasis on collaboration with researchers in other areas. The challenges of analyzing new types of data cannot be met by simply applying data analysis techniques in isolation from those who understand the data and the domain in which it resides. Often, skill in building multidisciplinary teams has been as responsible for the success of data mining projects as the creation of new and innovative algorithms. Just as, historically, many developments in statistics were driven by the needs of agriculture, industry, medicine, and business, rxrany of the developments in data mining are being driven by the needs of those same fields. This book began as a set of notes and lecture slides for a data mining course that has been offered at the University of Minnesota since Spring 1998 to upper-division undergraduate and graduate Students. Presentation slides viii Preface and exercises developed in these offerings grew with time and served as a basis for the book. A survey of clustering techniques in data mining, originally written in preparation for research in the area, served as a starting point for one of the chapters in the book. Over time, the clustering chapter was joined by chapters on data, classification, association analysis, and anomaly detection. The book in its current form has been class tested at the home institutions of the authors-the University of Minnesota and Michigan State University-as well as several other universities. A number of data mining books appeared in the meantime, but were not completely satisfactory for our students primarily graduate and undergrad- uate students in computer science, but including students from industry and a wide variety of other disciplines. Their mathematical and computer back- grounds varied considerably, but they shared a common goal: to learn about data mining as directly as possible in order to quickly apply it to problems in their own domains. Thus, texts with extensive mathematical or statistical prerequisites were unappealing to many of them, as were texts that required a substantial database background. The book that evolved in response to these students needs focuses as directly as possible on the key concepts of data min- ing by illustrating them with examples, simple descriptions of key algorithms, and exercises. Overview Specifically, this book provides a comprehensive introduction to data mining and is designed to be accessible and useful to students, instructors, researchers, and professionals. Areas covered include data preprocessing, vi- sualization, predictive modeling, association analysis, clustering, and anomaly detection. The goal is to present fundamental concepts and algorithms for each topic, thus providing the reader with the necessary background for the application of data mining to real problems. In addition, this book also pro- vides a starting point for those readers who are interested in pursuing research in data mining or related fields. The book covers five main topics: data, classification, association analysis, clustering, and anomaly detection. Except for anomaly detection, each of these areas is covered in a pair of chapters. For classification, association analysis, and clustering, the introductory chapter covers basic concepts, representative algorithms, and evaluation techniques, while the more advanced chapter dis- cusses advanced concepts and algorithms. The objective is to provide the reader with a sound understanding of the foundations of data mining, while still covering many important advanced topics. Because of this approach, the book is useful both as a learning tool and as a reference. Preface ix To help the readers better understand the concepts that have been pre- sented, we provide an extensive set of examples, figures, and exercises. Bib- Iiographic notes are included at the end of each chapter for readers who are interested in more advanced topics, historically important papers, and recent trends. The book also contains a comprehensive subject and author index. To the Instructor As a textbook, this book is suitable for a wide range of students at the advanced undergraduate or graduate level. Since students come to this subject with diverse backgrounds that may not include extensive knowledge of statistics or databases, our book requires minimal prerequisites- no database knowledge is needed and we assume only a modest background in statistics or mathematics. To this end, the book was designed to be as self-contained as possible. Necessary material from statistics, linear algebra, and machine learning is either integrated into the body of the text, or for some advanced topics, covered in the appendices. Since the chapters covering major data mining topics are self-contained, the order in which topics can be covered is quite flexible. The core material is covered in Chapters 2, 4, 6, 8, and 10. Although the introductory data chapter (2) should be covered first, the basic classification, association analy- sis, and clustering chapters (4, 6, and 8, respectively) can be covered in any order. Because of the relationship of anomaly detection (10) to classification (4) and clustering (8), these chapters should precede Chapter 10. Various topics can be selected from the advanced classification, association analysis, and clustering chapters (5, 7, and 9, respectively) to fit the schedule and in- terests of the instructor and students. We also advise that the lectures be augmented by projects or practical exercises in data mining. Although they are time consuming, such hands-on assignments greatly enhance the value of the course. Support Materials The supplements for the book are available at Addison- Wesley's Website www.aw.con/cssupport. Support materials available to all readers of this book include PowerPoint lecture slides Suggestions for student projects Data mining resources such as data mining algorithms and data sets On-line tutorials that give step-by-step examples for selected data mining techniques described in the book using actual data sets and data analysis software o o o o x Preface Additional support materials, including solutions to exercises, are available only to instructors adopting this textbook for classroom use. Please contact your school's Addison-Wesley representative for information on obtaining ac- cess to this material. Comments and suggestions, as well as reports of errors, can be sent to the authors through