Data Mining: Concepts and Techniques Jiawei Han and Micheline Kamber Simon Fraser University Note: This manuscript is based on a forthcoming book by Jiawei Han and Micheline Kamber, c 2000 (c) Morgan Kaufmann Publishers. All rights reserved. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Preface Our capabilities of both generating and collecting data have been increasing rapidly in the last several decades. Contributing factors include the widespread use of bar codes for most commercial products, the computerization of many business, scienti c and government transactions and managements, and advances in data collection tools ranging from scanned texture and image platforms, to on-line instrumentation in manufacturing and shopping, and to satellite remote sensing systems.
In addition, popular use of the World Wide Web as a global information system has ooded us with a tremendous amount of data and information. This explosive growth in stored data has generated an urgent need for new techniques and automated tools that can intelligently assist us in transforming the vast amounts of data into useful information and knowledge. This book explores the concepts and techniques of data mining, a promising and ourishing frontier in database systems and new database applications. Data mining, also popularly referred to as knowledge discovery in databases (KDD), is the automated or convenient extraction of patterns representing knowledge implicitly stored in large databases, data warehouses, and other massive information repositories.
Data mining is a multidisciplinary eld, drawing work from areas including database technology, arti cial in- telligence, machine learning, neural networks, statistics, pattern recognition, knowledge based systems, knowledge acquisition, information retrieval, high performance computing, and data visualization. We present the material in this book from a database perspective. That is, we focus on issues relating to the feasibility, usefulness, eciency, and scalability of techniques for the discovery of patterns hidden in large databases. As a result, this book is not intended as an introduction to database systems, machine learning, or statistics, etc., although we do provide the background necessary in these areas in order to facilitate the reader's comprehension of their respective roles in data mining.
Rather, the book is a comprehensive introduction to data mining, presented with database issues in focus. It should be useful for computing science students, application developers, and business professionals, as well as researchers involved in any of the disciplines listed above. Data mining emerged during the late 1980's, has made great strides during the 1990's, and is expected to continue to ourish into the new millennium. This book presents an overall picture of the eld from a database researcher's point of view, introducing interesting data mining techniques and systems, and discussing applications and research directions.
An important motivation for writing this book was the need to build an organized framework for the study of data mining | a challenging task owing to the extensive multidisciplinary nature of this fast developing eld. We hope that this book will encourage people with di erent backgrounds and experiences to exchange their views regarding data mining so as to contribute towards the further promotion and shaping of this exciting and dynamic eld. To the teacher This book is designed to give a broad, yet in depth overview of the eld of data mining. You will nd it useful for teaching a course on data mining at an advanced undergraduate level, or the rst-year graduate level.
In addition, individual chapters may be included as material for courses on selected topics in database systems or in arti cial intelligence. We have tried to make the chapters as self-contained as possible. For a course taught at the undergraduate level, you might use chapters 1 to 8 as the core course material. Remaining class material may be selected from among the more advanced topics described in chapters 9 and 10.
For a graduate level course, you may choose to cover the entire book in one semester. Each chapter ends with a set of exercises, suitable as assigned homework. The exercises are either short questions i LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ii that test basic mastery of the material covered, or longer questions which require analytical thinking. To the student We hope that this textbook will spark your interest in the fresh, yet evolving eld of data mining.
We have attempted to present the material in a clear manner, with careful explanation of the topics covered. Each chapter ends with a summary describing the main points. We have included many gures and illustrations throughout the text in order to make the book more enjoyable and \reader-friendly". Although this book was designed as a textbook, we have tried to organize it so that it will also be useful to you as a reference book or handbook, should you later decide to pursue a career in data mining.
What do you need to know in order to read this book? You should have some knowledge of the concepts and terminology associated with database systems. However, we do try to provide enough background of the basics in database technology, so that if your memory is a bit rusty, you will not have trouble following the discussions in the book. You should have some knowledge of database querying, although knowledge of any speci c query language is not required. You should have some programming experience.
In particular, you should be able to read pseudo-code, and understand simple data structures such as multidimensional arrays. It will be helpful to have some preliminary background in statistics, machine learning, or pattern recognition. However, we will familiarize you with the basic concepts of these areas that are relevant to data mining from a database perspective. To the professional This book was designed to cover a broad range of topics in the eld of data mining.
As a result, it is a good handbook on the subject. Because each chapter is designed to be as stand-alone as possible, you can focus on the topics that most interest you. Much of the book is suited to applications programmers or information service managers like yourself who wish to learn about the key ideas of data mining on their own. The techniques and algorithms presented are of practical utility.
Rather than selecting algorithms that perform well on small \toy" databases, the algorithms described in the book are geared for the discovery of data patterns hidden in large, real databases. In Chapter 10, we brie y discuss data mining systems in commercial use, as well as promising research prototypes. Each algorithm presented in the book is illustrated in pseudo-code. The pseudo- code is similar to the C programming language, yet is designed so that it should be easy to follow by programmers unfamiliar with C or C++.
If you wish to implement any of the algorithms, you should nd the translation of our pseudo-code into the programming language of your choice to be a fairly straightforward task. Organization of the book The book is organized as follows. Chapter 1 provides an introduction to the multidisciplinary eld of data mining. It discusses the evolutionary path of database technology which led up to the need for data mining, and the importance of its application potential.
The basic architecture of data mining systems is described, and a brief introduction to the concepts of database systems and data warehouses is given. A detailed classi cation of data mining tasks is presented, based on the di erent kinds of knowledge to be mined. A classi cation of data mining systems is presented, and major challenges in the eld are discussed. Chapter 2 is an introduction to data warehouses and OLAP (On-Line Analytical Processing).
Topics include the concept of data warehouses and multidimensional databases, the construction of data cubes, the implementation of on-line analytical processing, and the relationship between data warehousing and data mining. Chapter 3 describes techniques for preprocessing the data prior to mining. Methods of data cleaning, data integration and transformation, and data reduction are discussed, including the use of concept hierarchies for dynamic and static discretization. The automatic generation of concept hierarchies is also described.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com iii Chapter 4 introduces the primitives of data mining which de ne the speci cation of a data mining task. It describes a data mining query language (DMQL), and provides examples of data mining queries. Other topics include the construction of graphical user interfaces, and the speci cation and manipulation of concept hierarchies. Chapter 5 describes techniques for concept description, including characterization and discrimination.
An attribute-oriented generalization technique is introduced, as well as its di erent implementations including a gener- alized relation technique and a multidimensional data cube technique. Several forms of knowledge presentation and visualization are illustrated. Relevance analysis is discussed. Methods for class comparison at multiple abstraction levels, and methods for the extraction of characteristic rules and discriminant rules with interestingness measurements are presented.
In addition, statistical measures for descriptive mining are discussed. Chapter 6 presents methods for mining association rules in transaction databases as well as relational databases and data warehouses. It includes a classi cation of association rules, a presentation of the basic Apriori algorithm and its variations, and techniques for mining multiple-level association rules, multidimensional association rules, quantitative association rules, and correlation rules. Strategies for nding interesting rules by constraint-based mining and the use of interestingness measures to focus the rule search are also described.
Chapter 7 describes methods for data classi cation and predictive modeling. Major methods of classi cation and prediction are explained, including decision tree induction, Bayesian classi cation, the neural network technique of backpropagation, k-nearest neighbor classi ers, case-based reasoning, genetic algorithms, rough set theory, and fuzzy set approaches. Association-based classi cation, which applies association rule mining to the problem of classi cation, is presented. Methods of regression are introduced, and issues regarding classi er accuracy are discussed.
Chapter 8 describes methods of clustering analysis. It rst introduces the concept of data clustering and then presents several major data clustering approaches, including partition-based clustering, hierarchical clustering, and model-based clustering. Methods for clustering continuous data, discrete data, and data in multidimensional data cubes are presented. The scalability of clustering algorithms is discussed in detail.
Chapter 9 discusses methods for data mining in advanced database systems. It includes data mining in object- oriented databases, spatial databases, text databases, multimedia databases, active databases, temporal databases, heterogeneous and legacy databases, and resource and knowledge discovery in the Internet information base. Finally, in Chapter 10, we summarize the concepts presented in this book and discuss applications of data mining and some challenging research issues. Errors It is likely that this book may contain typos, errors, or omissions.
If you notice any errors, have suggestions regarding additional exercises or have other constructive criticism, we would be very happy to hear from you. We welcome and appreciate your suggestions. You can send your comments to: Data Mining: Concept and Techniques Intelligent Database Systems Research Laboratory Simon Fraser University, Burnaby, British Columbia Canada V5A 1S6 Fax: (604) 291-3045 Alternatively, you can use electronic mails to submit bug reports, request a list of known errors, or make con- structive suggestions. To receive instructions, send email to with \Subject: help" in the message header.ca We regret that we cannot personally respond to all e-mails.
The errata of the book and other updated information related to the book can be found by referencing the Web address: http://db. Acknowledgements We would like to express our sincere thanks to all the members of the data mining research group who have been working with us at Simon Fraser University on data mining related research, and to all the members of the DBMiner system development team, who have been working on an exciting data mining project, , and have made DBMiner it a real success. The data mining research team currently consists of the following active members: Julia Gitline, LUAN VAN CHAT LUONG download : add luanvanchat@agmail.