Introduction to data mining pang ning tan vipin kumar pdf

Association Analysis

1. Consider the data set shown in Table 5.20 (439 page). (Chapter 5)
(a) Compute the support for itemsets {e}, {b, d}, and {b, d, e} by treating each transaction ID as a market basket.
(b) Use the results in part (a) to compute the confidence for the association rules {b, d} −→ {e} and {e} −→ {b, d}. Is confidence a symmetric measure?
(c) Use the results in part (c) to compute the confidence for the association rules {b, d} −→ {e} and {e} −→ {b, d}.

2. Consider the transactions shown in Table 6.15, with an item taxonomy given in Figure 6.15 (515 page). (Chapter 6)
(a) What are the main challenges of mining association rules with item taxonomy?
(b) Consider the approach where each transaction t is replaced by an extended transaction t_ that contains all the items in t as well as their respective ancestors. For example, the transaction t = { Chips, Cookies} will be replaced by t_ = {Chips, Cookies, Snack Food, Food}. Use this approach to derive all frequent itemsets (up to size 4) with support ≥ 70%.
(c) Consider an alternative approach where the frequent itemsets are generated one level at a time. Initially, all the frequent itemsets involving items at the highest level of the hierarchy are generated. Next, we use the frequent itemsets discovered at the higher level of the hierarchy to generate candidate itemsets involving items at the lower levels of the hierarchy. For example, we generate the candidate itemset {Chips, Diet Soda} only if {Snack Food, Soda} is frequent. Use this approach to derive all frequent itemsets (up to size 4) with support ≥ 70%.

3. Consider a data set consisting of 220 data vectors, where each vector has 32 components and each component is a 4-byte value. Suppose that vector quantization is used for compression and that 216 prototype vectors are used. How many bytes of storage does that data set take before and after compression and what is the compression ratio? (Chapter 7)
.
Grading Rubric for the Assignment #3:
Delivery: Delivered the assignments on time, and in correct format: 25 percent
Completion: Providing a thoroughly develop the document including descriptions of all questions: 25 percent
Understanding: Demonstrating a clear understanding of purpose and writing a central idea with mostly relevant facts, details, and/or explanation: 25 percent
Organization: Paper is well organized, makes good use of transition statements, and in most instances follows a logical progression including good use of symbols, spacing in output: 25 percent

INTRODUCTION TO DATA MINING

INTRODUCTION TO DATA MINING SECOND EDITION

PANG-NING TAN

Michigan State Universit

MICHAEL STEINBACH

University of Minnesota

ANUJ KARPATNE

University of Minnesota

VIPIN KUMAR

University of Minnesota

330 Hudson Street, NY NY 10013

Director, Portfolio Management: Engineering, Computer Science & Global Editions: Julian Partridge

Specialist, Higher Ed Portfolio Management: Matt Goldstein

Portfolio Management Assistant: Meghan Jacoby

Managing Content Producer: Scott Disanno

Content Producer: Carole Snyder

Web Developer: Steve Wright

Rights and Permissions Manager: Ben Ferrini

Manufacturing Buyer, Higher Ed, Lake Side Communications Inc (LSC): Maura Zaldivar-Garcia

Inventory Manager: Ann Lam

Product Marketing Manager: Yvonne Vannatta

Field Marketing Manager: Demetrius Hall

Marketing Assistant: Jon Bryant

Cover Designer: Joyce Wells, jWellsDesign

Full-Service Project Management: Chandrasekar Subramanian, SPi Global

Copyright ©2019 Pearson Education, Inc. All rights reserved. Manufactured in the United States of America. This publication is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. For information regarding permissions, request forms and the appropriate contacts within the Pearson Education Global Rights & Permissions department, please visit www.pearsonhighed.com/permissions/.

Many of the designations by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps.

Library of Congress Cataloging-in-Publication Data on File

Names: Tan, Pang-Ning, author. | Steinbach, Michael, author. | Karpatne, Anuj, author. | Kumar, Vipin, 1956- author.

Title: Introduction to Data Mining / Pang-Ning Tan, Michigan State University, Michael Steinbach, University of Minnesota, Anuj Karpatne, University of Minnesota, Vipin Kumar, University of Minnesota.

Description: Second edition. | New York, NY : Pearson Education, [2019] | Includes bibliographical references and index.

Identifiers: LCCN 2017048641 | ISBN 9780133128901 | ISBN 0133128903

Subjects: LCSH: Data mining.

Classification: LCC QA76.9.D343 T35 2019 | DDC 006.3/12–dc23 LC record available at https://lccn.loc.gov/2017048641

1 18

ISBN-10: 0133128903

ISBN-13: 9780133128901

To our families …

Preface to the Second Edition Since the first edition, roughly 12 years ago, much has changed in the field of data analysis. The volume and variety of data being collected continues to increase, as has the rate (velocity) at which it is being collected and used to make decisions. Indeed, the term, Big Data, has been used to refer to the massive and diverse data sets now available. In addition, the term data science has been coined to describe an emerging area that applies tools and techniques from various fields, such as data mining, machine learning, statistics, and many others, to extract actionable insights from data, often big data.

The growth in data has created numerous opportunities for all areas of data analysis. The most dramatic developments have been in the area of predictive modeling, across a wide range of application domains. For instance, recent advances in neural networks, known as deep learning, have shown impressive results in a number of challenging areas, such as image classification, speech recognition, as well as text categorization and understanding. While not as dramatic, other areas, e.g., clustering, association analysis, and anomaly detection have also continued to advance. This new edition is in response to those advances.

Overview As with the first edition, the second edition of the 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, predictive modeling, association analysis, cluster analysis, anomaly detection, and avoiding false discoveries. 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. As before, classification, association analysis and cluster analysis, are each covered in a pair of chapters. The introductory

chapter covers basic concepts, representative algorithms, and evaluation techniques, while the more following chapter discusses advanced concepts and algorithms. As before, our 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.

To help readers better understand the concepts that have been presented, we provide an extensive set of examples, figures, and exercises. The solutions to the original exercises, which are already circulating on the web, will be made public. The exercises are mostly unchanged from the last edition, with the exception of new exercises in the chapter on avoiding false discoveries. New exercises for the other chapters and their solutions will be available to instructors via the web. Bibliographic notes are included at the end of each chapter for readers who are interested in more advanced topics, historically important papers, and recent trends. These have also been significantly updated. The book also contains a comprehensive subject and author index.

What is New in the Second Edition? Some of the most significant improvements in the text have been in the two chapters on classification. The introductory chapter uses the decision tree classifier for illustration, but the discussion on many topics—those that apply across all classification approaches—has been greatly expanded and clarified, including topics such as overfitting, underfitting, the impact of training size, model complexity, model selection, and common pitfalls in model evaluation. Almost every section of the advanced classification chapter has been significantly updated. The material on Bayesian networks, support vector machines, and artificial neural networks has been significantly expanded. We have added a separate section on deep networks to address the current developments in this area. The discussion of evaluation, which occurs in the section on imbalanced classes, has also been updated and improved.

The changes in association analysis are more localized. We have completely reworked the section on the evaluation of association patterns (introductory chapter), as well as the sections on sequence and graph mining (advanced

chapter). Changes to cluster analysis are also localized. The introductory chapter added the K-means initialization technique and an updated the discussion of cluster evaluation. The advanced clustering chapter adds a new section on spectral graph clustering. Anomaly detection has been greatly revised and expanded. Existing approaches—statistical, nearest neighbor/density-based, and clustering based—have been retained and updated, while new approaches have been added: reconstruction-based, one- class classification, and information-theoretic. The reconstruction-based approach is illustrated using autoencoder networks that are part of the deep learning paradigm. The data chapter has been updated to include discussions of mutual information and kernel-based techniques.

The last chapter, which discusses how to avoid false discoveries and produce valid results, is completely new, and is novel among other contemporary textbooks on data mining. It supplements the discussions in the other chapters with a discussion of the statistical concepts (statistical significance, p-values, false discovery rate, permutation testing, etc.) relevant to avoiding spurious results, and then illustrates these concepts in the context of data mining techniques. This chapter addresses the increasing concern over the validity and reproducibility of results obtained from data analysis. The addition of this last chapter is a recognition of the importance of this topic and an acknowledgment that a deeper understanding of this area is needed for those analyzing data.

The data exploration chapter has been deleted, as have the appendices, from the print edition of the book, but will remain available on the web. A new appendix provides a brief discussion of scalability in the context of big data.

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, although such a background will make for easier going in

some sections. As before, the book, and more specifically, the chapters covering major data mining topics, are designed to be as self-contained as possible. Thus, the order in which topics can be covered is quite flexible. The core material is covered in chapters 2 (data), 3 (classification), 5 (association analysis), 7 (clustering), and 9 (anomaly detection). We recommend at least a cursory coverage of Chapter 10 (Avoiding False Discoveries) to instill in students some caution when interpreting the results of their data analysis. Although the introductory data chapter (2) should be covered first, the basic classification (3), association analysis (5), and clustering chapters (7), can be covered in any order. Because of the relationship of anomaly detection (9) to classification (3) and clustering (7), these chapters should precede Chapter 9. Various topics can be selected from the advanced classification, association analysis, and clustering chapters (4, 6, and 8, respectively) to fit the schedule and interests 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 Support materials available to all readers of this book are available at http://www-users.cs.umn.edu/~kumar/dmbook.

PowerPoint lecture slides

Suggestions for student projects

Data mining resources, such as algorithms and data sets

Online tutorials that give step-by-step examples for selected data mining techniques described in the book using actual data sets and data analysis software

Additional support materials, including solutions to exercises, are available only to instructors adopting this textbook for classroom use. The book’s resources will be mirrored at www.pearsonhighered.com/cs-resources.

http://www.pearsonhighered.com/cs-resources
Comments and suggestions, as well as reports of errors, can be sent to the authors through dmbook@cs.umn.edu.

Acknowledgments Many people contributed to the first and second editions of the book. We begin by acknowledging our families to whom this book is dedicated. Without their patience and support, this project would have been impossible.

We would like to thank the current and former students of our data mining groups at the University of Minnesota and Michigan State for their contributions. Eui-Hong (Sam) Han and Mahesh Joshi helped with the initial data mining classes. Some of the exercises and presentation slides that they created can be found in the book and its accompanying slides. Students in our data mining groups who provided comments on drafts of the book or who contributed in other ways include Shyam Boriah, Haibin Cheng, Varun Chandola, Eric Eilertson, Levent Ertöz, Jing Gao, Rohit Gupta, Sridhar Iyer, Jung-Eun Lee, Benjamin Mayer, Aysel Ozgur, Uygar Oztekin, Gaurav Pandey, Kashif Riaz, Jerry Scripps, Gyorgy Simon, Hui Xiong, Jieping Ye, and Pusheng Zhang. We would also like to thank the students of our data mining classes at the University of Minnesota and Michigan State University who worked with early drafts of the book and provided invaluable feedback. We specifically note the helpful suggestions of Bernardo Craemer, Arifin Ruslim, Jamshid Vayghan, and Yu Wei.

Joydeep Ghosh (University of Texas) and Sanjay Ranka (University of Florida) class tested early versions of the book. We also received many useful suggestions directly from the following UT students: Pankaj Adhikari, Rajiv Bhatia, Frederic Bosche, Arindam Chakraborty, Meghana Deodhar, Chris Everson, David Gardner, Saad Godil, Todd Hay, Clint Jones, Ajay Joshi, Joonsoo Lee, Yue Luo, Anuj Nanavati, Tyler Olsen, Sunyoung Park, Aashish Phansalkar, Geoff Prewett, Michael Ryoo, Daryl Shannon, and Mei Yang.

Ronald Kostoff (ONR) read an early version of the clustering chapter and offered numerous suggestions. George Karypis provided invaluable LATEX assistance in creating an author index. Irene Moulitsas also provided

assistance with LATEX and reviewed some of the appendices. Musetta Steinbach was very helpful in finding errors in the figures.

We would like to acknowledge our colleagues at the University of Minnesota and Michigan State who have helped create a positive environment for data mining research. They include Arindam Banerjee, Dan Boley, Joyce Chai, Anil Jain, Ravi Janardan, Rong Jin, George Karypis, Claudia Neuhauser, Haesun Park, William F. Punch, György Simon, Shashi Shekhar, and Jaideep Srivastava. The collaborators on our many data mining projects, who also have our gratitude, include Ramesh Agrawal, Maneesh Bhargava, Steve Cannon, Alok Choudhary, Imme Ebert-Uphoff, Auroop Ganguly, Piet C. de Groen, Fran Hill, Yongdae Kim, Steve Klooster, Kerry Long, Nihar Mahapatra, Rama Nemani, Nikunj Oza, Chris Potter, Lisiane Pruinelli, Nagiza Samatova, Jonathan Shapiro, Kevin Silverstein, Brian Van Ness, Bonnie Westra, Nevin Young, and Zhi-Li Zhang.

The departments of Computer Science and Engineering at the University of Minnesota and Michigan State University provided computing resources and a supportive environment for this project. ARDA, ARL, ARO, DOE, NASA, NOAA, and NSF provided research support for Pang-Ning Tan, Michael Stein-bach, Anuj Karpatne, and Vipin Kumar. In particular, Kamal Abdali, Mitra Basu, Dick Brackney, Jagdish Chandra, Joe Coughlan, Michael Coyle, Stephen Davis, Frederica Darema, Richard Hirsch, Chandrika Kamath, Tsengdar Lee, Raju Namburu, N. Radhakrishnan, James Sidoran, Sylvia Spengler, Bhavani Thuraisingham, Walt Tiernin, Maria Zemankova, Aidong Zhang, and Xiaodong Zhang have been supportive of our research in data mining and high-performance computing.

It was a pleasure working with the helpful staff at Pearson Education. In particular, we would like to thank Matt Goldstein, Kathy Smith, Carole Snyder, and Joyce Wells. We would also like to thank George Nichols, who helped with the art work and Paul Anagnostopoulos, who provided LATEX support.

We are grateful to the following Pearson reviewers: Leman Akoglu (Carnegie Mellon University), Chien-Chung Chan (University of Akron), Zhengxin Chen (University of Nebraska at Omaha), Chris Clifton (Purdue University), Joy-deep Ghosh (University of Texas, Austin), Nazli Goharian (Illinois

Institute of Technology), J. Michael Hardin (University of Alabama), Jingrui He (Arizona State University), James Hearne (Western Washington University), Hillol Kargupta (University of Maryland, Baltimore County and Agnik, LLC), Eamonn Keogh (University of California-Riverside), Bing Liu (University of Illinois at Chicago), Mariofanna Milanova (University of Arkansas at Little Rock), Srinivasan Parthasarathy (Ohio State University), Zbigniew W. Ras (University of North Carolina at Charlotte), Xintao Wu (University of North Carolina at Charlotte), and Mohammed J. Zaki (Rensselaer Polytechnic Institute).

Over the years since the first edition, we have also received numerous comments from readers and students who have pointed out typos and various other issues. We are unable to mention these individuals by name, but their input is much appreciated and has been taken into account for the second edition.

Contents 1. Preface to the Second Edition v

1. 1 Introduction 1

1. 1.1 What Is Data Mining? 4

2. 1.2 Motivating Challenges 5

3. 1.3 The Origins of Data Mining 7

4. 1.4 Data Mining Tasks 9

5. 1.5 Scope and Organization of the Book 13

6. 1.6 Bibliographic Notes 15

1. 1.7 Exercises 21

2. 2 Data 23

1. 2.1 Types of Data 26

1. 2.1.1 Attributes and Measurement 27

2. 2.1.2 Types of Data Sets 34

2. 2.2 Data Quality 42

1. 2.2.1 Measurement and Data Collection Issues 42

2. 2.2.2 Issues Related to Applications 49

3. 2.3 Data Preprocessing 50

1. 2.3.1 Aggregation 51

2. 2.3.2 Sampling 52

3. 2.3.3 Dimensionality Reduction 56

4. 2.3.4 Feature Subset Selection 58

5. 2.3.5 Feature Creation 61

6. 2.3.6 Discretization and Binarization 63

7. 2.3.7 Variable Transformation 69

4. 2.4 Measures of Similarity and Dissimilarity 71

1. 2.4.1 Basics 72

2. 2.4.2 Similarity and Dissimilarity between Simple Attributes 74

3. 2.4.3 Dissimilarities between Data Objects 76

4. 2.4.4 Similarities between Data Objects 78

5. 2.4.5 Examples of Proximity Measures 79

6. 2.4.6 Mutual Information 88

7. 2.4.7 Kernel Functions* 90

8. 2.4.8 Bregman Divergence* 94

9. 2.4.9 Issues in Proximity Calculation 96

10. 2.4.10 Selecting the Right Proximity Measure 98

5. 2.5 Bibliographic Notes 100

1. 2.6 Exercises 105

3. 3 Classification: Basic Concepts and Techniques 113

1. 3.1 Basic Concepts 114

2. 3.2 General Framework for Classification 117

3. 3.3 Decision Tree Classifier 119

1. 3.3.1 A Basic Algorithm to Build a Decision Tree 121

2. 3.3.2 Methods for Expressing Attribute Test Conditions 124

3. 3.3.3 Measures for Selecting an Attribute Test Condition 127

4. 3.3.4 Algorithm for Decision Tree Induction 136

5. 3.3.5 Example Application: Web Robot Detection 138

6. 3.3.6 Characteristics of Decision Tree Classifiers 140

4. 3.4 Model Overfitting 147

1. 3.4.1 Reasons for Model Overfitting 149

5. 3.5 Model Selection 156

1. 3.5.1 Using a Validation Set 156

2. 3.5.2 Incorporating Model Complexity 157

3. 3.5.3 Estimating Statistical Bounds 162

4. 3.5.4 Model Selection for Decision Trees 162

6. 3.6 Model Evaluation 164

1. 3.6.1 Holdout Method 165

2. 3.6.2 Cross-Validation 165

7. 3.7 Presence of Hyper-parameters 168

1. 3.7.1 Hyper-parameter Selection 168

2. 3.7.2 Nested Cross-Validation 170

8. 3.8 Pitfalls of Model Selection and Evaluation 172

1. 3.8.1 Overlap between Training and Test Sets 172

2. 3.8.2 Use of Validation Error as Generalization Error 172

9. 3.9 Model Comparison* 173

1. 3.9.1 Estimating the Confidence Interval for Accuracy 174

2. 3.9.2 Comparing the Performance of Two Models 175

10. 3.10 Bibliographic Notes 176

1. 3.11 Exercises 185

4. 4 Classification: Alternative Techniques 193

1. 4.1 Types of Classifiers 193

2. 4.2 Rule-Based Classifier 195

1. 4.2.1 How a Rule-Based Classifier Works 197

2. 4.2.2 Properties of a Rule Set 198

3. 4.2.3 Direct Methods for Rule Extraction 199

4. 4.2.4 Indirect Methods for Rule Extraction 204

5. 4.2.5 Characteristics of Rule-Based Classifiers 206

3. 4.3 Nearest Neighbor Classifiers 208

1. 4.3.1 Algorithm 209

2. 4.3.2 Characteristics of Nearest Neighbor Classifiers 210

4. 4.4 Naïve Bayes Classifier 212

1. 4.4.1 Basics of Probability Theory 213

2. 4.4.2 Naïve Bayes Assumption 218

5. 4.5 Bayesian Networks 227

1. 4.5.1 Graphical Representation 227

2. 4.5.2 Inference and Learning 233

3. 4.5.3 Characteristics of Bayesian Networks 242

6. 4.6 Logistic Regression 243

1. 4.6.1 Logistic Regression as a Generalized Linear Model 244

2. 4.6.2 Learning Model Parameters 245

3. 4.6.3 Characteristics of Logistic Regression 248

7. 4.7 Artificial Neural Network (ANN) 249

1. 4.7.1 Perceptron 250

2. 4.7.2 Multi-layer Neural Network 254

3. 4.7.3 Characteristics of ANN 261

8. 4.8 Deep Learning 262

1. 4.8.1 Using Synergistic Loss Functions 263

2. 4.8.2 Using Responsive Activation Functions 266

3. 4.8.3 Regularization 268

4. 4.8.4 Initialization of Model Parameters 271

5. 4.8.5 Characteristics of Deep Learning 275

9. 4.9 Support Vector Machine (SVM) 276

1. 4.9.1 Margin of a Separating Hyperplane 276

2. 4.9.2 Linear SVM 278

3. 4.9.3 Soft-margin SVM 284

4. 4.9.4 Nonlinear SVM 290

5. 4.9.5 Characteristics of SVM 294

10. 4.10 Ensemble Methods 296

1. 4.10.1 Rationale for Ensemble Method 297

2. 4.10.2 Methods for Constructing an Ensemble Classifier 297

3. 4.10.3 Bias-Variance Decomposition 300

4. 4.10.4 Bagging 302

5. 4.10.5 Boosting 305

6. 4.10.6 Random Forests 310

7. 4.10.7 Empirical Comparison among Ensemble Methods 312

11. 4.11 Class Imbalance Problem 313

1. 4.11.1 Building Classifiers with Class Imbalance 314

2. 4.11.2 Evaluating Performance with Class Imbalance 318

3. 4.11.3 Finding an Optimal Score Threshold 322

4. 4.11.4 Aggregate Evaluation of Performance 323

12. 4.12 Multiclass Problem 330

13. 4.13 Bibliographic Notes 333

1. 4.14 Exercises 345

5. 5 Association Analysis: Basic Concepts and Algorithms 357

1. 5.1 Preliminaries 358

2. 5.2 Frequent Itemset Generation 362

1. 5.2.1 The Apriori Principle 363

2. 5.2.2 Frequent Itemset Generation in the Apriori Algorithm 364

3. 5.2.3 Candidate Generation and Pruning 368

4. 5.2.4 Support Counting 373

5. 5.2.5 Computational Complexity 377

3. 5.3 Rule Generation 380

1. 5.3.1 Confidence-Based Pruning 380

2. 5.3.2 Rule Generation in Apriori Algorithm 381

3. 5.3.3 An Example: Congressional Voting Records 382

4. 5.4 Compact Representation of Frequent Itemsets 384

1. 5.4.1 Maximal Frequent Itemsets 384

2. 5.4.2 Closed Itemsets 386

5. 5.5 Alternative Methods for Generating Frequent Itemsets* 389

6. 5.6 FP-Growth Algorithm* 393

1. 5.6.1 FP-Tree Representation 394

2. 5.6.2 Frequent Itemset Generation in FP-Growth Algorithm 397

7. 5.7 Evaluation of Association Patterns 401

1. 5.7.1 Objective Measures of Interestingness 402

2. 5.7.2 Measures beyond Pairs of Binary Variables 414

3. 5.7.3 Simpson’s Paradox 416

8. 5.8 Effect of Skewed Support Distribution 418

9. 5.9 Bibliographic Notes 424

1. 5.10 Exercises 438

6. 6 Association Analysis: Advanced Concepts 451

1. 6.1 Handling Categorical Attributes 451

2. 6.2 Handling Continuous Attributes 454

1. 6.2.1 Discretization-Based Methods 454

2. 6.2.2 Statistics-Based Methods 458

3. 6.2.3 Non-discretization Methods 460

3. 6.3 Handling a Concept Hierarchy 462

4. 6.4 Sequential Patterns 464

1. 6.4.1 Preliminaries 465

2. 6.4.2 Sequential Pattern Discovery 468

3. 6.4.3 Timing Constraints∗ 473

4. 6.4.4 Alternative Counting Schemes∗ 477

5. 6.5 Subgraph Patterns 479

1. 6.5.1 Preliminaries 480

2. 6.5.2 Frequent Subgraph Mining 483

3. 6.5.3 Candidate Generation 487

4. 6.5.4 Candidate Pruning 493

5. 6.5.5 Support Counting 493

6. 6.6 Infrequent Patterns∗ 493

1. 6.6.1 Negative Patterns 494

2. 6.6.2 Negatively Correlated Patterns 495

3. 6.6.3 Comparisons among Infrequent Patterns, Negative Patterns, and Negatively Correlated Patterns 496

4. 6.6.4 Techniques for Mining Interesting Infrequent Patterns 498

5. 6.6.5 Techniques Based on Mining Negative Patterns 499

6. 6.6.6 Techniques Based on Support Expectation 501

7. 6.7 Bibliographic Notes 505

1. 6.8 Exercises 510

7. 7 Cluster Analysis: Basic Concepts and Algorithms 525

1. 7.1 Overview 528

1. 7.1.1 What Is Cluster Analysis? 528

2. 7.1.2 Different Types of Clusterings 529

3. 7.1.3 Different Types of Clusters 531

2. 7.2 K-means 534

1. 7.2.1 The Basic K-means Algorithm 535

2. 7.2.2 K-means: Additional Issues 544

3. 7.2.3 Bisecting K-means 547

4. 7.2.4 K-means and Different Types of Clusters 548

5. 7.2.5 Strengths and Weaknesses 549

6. 7.2.6 K-means as an Optimization Problem 549

3. 7.3 Agglomerative Hierarchical Clustering 554

1. 7.3.1 Basic Agglomerative Hierarchical Clustering Algorithm 555

2. 7.3.2 Specific Techniques 557

3. 7.3.3 The Lance-Williams Formula for Cluster Proximity 562

4. 7.3.4 Key Issues in Hierarchical Clustering 563

5. 7.3.5 Outliers 564

6. 7.3.6 Strengths and Weaknesses 565

4. 7.4 DBSCAN 565

1. 7.4.1 Traditional Density: Center-Based Approach 565

2. 7.4.2 The DBSCAN Algorithm 567

3. 7.4.3 Strengths and Weaknesses 569

5. 7.5 Cluster Evaluation 571

1. 7.5.1 Overview 571

2. 7.5.2 Unsupervised Cluster Evaluation Using Cohesion and Separation 574

3. 7.5.3 Unsupervised Cluster Evaluation Using the Proximity Matrix 582

4. 7.5.4 Unsupervised Evaluation of Hierarchical Clustering 585

5. 7.5.5 Determining the Correct Number of Clusters 587

6. 7.5.6 Clustering Tendency 588

7. 7.5.7 Supervised Measures of Cluster Validity 589

8. 7.5.8 Assessing the Significance of Cluster Validity Measures 594

9. 7.5.9 Choosing a Cluster Validity Measure 596

6. 7.6 Bibliographic Notes 597

1. 7.7 Exercises 603

8. 8 Cluster Analysis: Additional Issues and Algorithms 613

1. 8.1 Characteristics of Data, Clusters, and Clustering Algorithms 614

1. 8.1.1 Example: Comparing K-means and DBSCAN 614

2. 8.1.2 Data Characteristics 615

3. 8.1.3 Cluster Characteristics 617

4. 8.1.4 General Characteristics of Clustering Algorithms 619

2. 8.2 Prototype-Based Clustering 621

1. 8.2.1 Fuzzy Clustering 621

2. 8.2.2 Clustering Using Mixture Models 627

3. 8.2.3 Self-Organizing Maps (SOM) 637

3. 8.3 Density-Based Clustering 644

1. 8.3.1 Grid-Based Clustering 644

2. 8.3.2 Subspace Clustering 648

3. 8.3.3 DENCLUE: A Kernel-Based Scheme for Density-Based Clustering 652

4. 8.4 Graph-Based Clustering 656

1. 8.4.1 Sparsification 657

2. 8.4.2 Minimum Spanning Tree (MST) Clustering 658

3. 8.4.3 OPOSSUM: Optimal Partitioning of Sparse Similarities Using METIS 659

4. 8.4.4 Chameleon: Hierarchical Clustering with Dynamic Modeling 660

5. 8.4.5 Spectral Clustering 666

6. 8.4.6 Shared Nearest Neighbor Similarity 673

7. 8.4.7 The Jarvis-Patrick Clustering Algorithm 676

8. 8.4.8 SNN Density 678

9. 8.4.9 SNN Density-Based Clustering 679

5. 8.5 Scalable Clustering Algorithms 681

1. 8.5.1 Scalability: General Issues and Approaches 681

2. 8.5.2 BIRCH 684

3. 8.5.3 CURE 686

6. 8.6 Which Clustering Algorithm? 690

7. 8.7 Bibliographic Notes 693

1. 8.8 Exercises 699

9. 9 Anomaly Detection 703

1. 9.1 Characteristics of Anomaly Detection Problems 705

1. 9.1.1 A Definition of an Anomaly 705

2. 9.1.2 Nature of Data 706

3. 9.1.3 How Anomaly Detection is Used 707

2. 9.2 Characteristics of Anomaly Detection Methods 708

3. 9.3 Statistical Approaches 710

1. 9.3.1 Using Parametric Models 710

2. 9.3.2 Using Non-parametric Models 714

3. 9.3.3 Modeling Normal and Anomalous Classes 715

4. 9.3.4 Assessing Statistical Significance 717

5. 9.3.5 Strengths and Weaknesses 718

4. 9.4 Proximity-based Approaches 719

1. 9.4.1 Distance-based Anomaly Score 719

2. 9.4.2 Density-based Anomaly Score 720

3. 9.4.3 Relative Density-based Anomaly Score 722

4. 9.4.4 Strengths and Weaknesses 723

5. 9.5 Clustering-based Approaches 724

1. 9.5.1 Finding Anomalous Clusters 724

2. 9.5.2 Finding Anomalous Instances 725

3. 9.5.3 Strengths and Weaknesses 728

6. 9.6 Reconstruction-based Approaches 728

1. 9.6.1 Strengths and Weaknesses 731

7. 9.7 One-class Classification 732

1. 9.7.1 Use of Kernels 733

2. 9.7.2 The Origin Trick 734

3. 9.7.3 Strengths and Weaknesses 738

8. 9.8 Information Theoretic Approaches 738

1. 9.8.1 Strengths and Weaknesses 740

9. 9.9 Evaluation of Anomaly Detection 740

10. 9.10 Bibliographic Notes 742

1. 9.11 Exercises 749

10. 10 Avoiding False Discoveries 755

1. 10.1 Preliminaries: Statistical Testing 756

1. 10.1.1 Significance Testing 756

2. 10.1.2 Hypothesis Testing 761

3. 10.1.3 Multiple Hypothesis Testing 767

4. 10.1.4 Pitfalls in Statistical Testing 776

2. 10.2 Modeling Null and Alternative Distributions 778

1. 10.2.1 Generating Synthetic Data Sets 781

2. 10.2.2 Randomizing Class Labels 782

3. 10.2.3 Resampling Instances 782

4. 10.2.4 Modeling the Distribution of the Test Statistic 783

3. 10.3 Statistical Testing for Classification 783

1. 10.3.1 Evaluating Classification Performance 783

2. 10.3.2 Binary Classification as Multiple Hypothesis Testing 785

3. 10.3.3 Multiple Hypothesis Testing in Model Selection 786

4. 10.4 Statistical Testing for Association Analysis 787

1. 10.4.1 Using Statistical Models 788

2. 10.4.2 Using Randomization Methods 794

5. 10.5 Statistical Testing for Cluster Analysis 795

1. 10.5.1 Generating a Null Distribution for Internal Indices 796

2. 10.5.2 Generating a Null Distribution for External Indices 798

3. 10.5.3 Enrichment 798

6. 10.6 Statistical Testing for Anomaly Detection 800

7. 10.7 Bibliographic Notes 803

1. 10.8 Exercises 808

1. Author Index 816

2. Subject Index 829

3. Copyright Permissions 839

1 Introduction Rapid advances in data collection and storage technology, coupled with the ease with which data can be generated and disseminated, have triggered the explosive growth of data, leading to the current age of big data. Deriving actionable insights from these large data sets is increasingly important in decision making across almost all areas of society, including business and industry; science and engineering; medicine and biotechnology; and government and individuals. However, the amount of data (volume), its complexity (variety), and the rate at which it is being collected and processed (velocity) have simply become too great for humans to analyze unaided. Thus, there is a great need for automated tools for extracting useful information from the big data despite the challenges posed by its enormity and diversity.

Data mining blends traditional data analysis methods with sophisticated algorithms for processing this abundance of data. In this introductory chapter, we present an overview of data mining and outline the key topics to be covered in this book. We start with a description of some applications that require more advanced techniques for data analysis.

Business and Industry Point-of-sale data collection (bar code scanners, radio frequency identification (RFID), and smart card technology) have allowed retailers to collect up-to-the-minute data about customer purchases at the checkout counters of their stores. Retailers can utilize this information, along with other business-critical data, such as web server logs from e-commerce websites and customer service records from call centers, to help them better understand the needs of their customers and make more informed business decisions.

Data mining techniques can be used to support a wide range of business intelligence applications, such as customer profiling, targeted marketing, workflow management, store layout, fraud detection, and automated buying and selling. An example of the last application is high-speed stock trading, where decisions on buying and selling have to be made in less than a second

using data about financial transactions. Data mining can also help retailers answer important business questions, such as “Who are the most profitable customers?” “What products can be cross-sold or up-sold?” and “What is the revenue outlook of the company for next year?” These questions have inspired the development of such data mining techniques as association analysis (Chapters 5 and 6).

As the Internet continues to revolutionize the way we interact and make decisions in our everyday lives, we are generating massive amounts of data about our online experiences, e.g., web browsing, messaging, and posting on social networking websites. This has opened several opportunities for business applications that use web data. For example, in the e-commerce sector, data about our online viewing or shopping preferences can be used to provide personalized recommendations of products. Data mining also plays a prominent role in supporting several other Internet-based services, such as filtering spam messages, answering search queries, and suggesting social updates and connections. The large corpus of text, images, and videos available on the Internet has enabled a number of advancements in data mining methods, including deep learning, which is discussed in Chapter 4. These developments have led to great advances in a number of applications, such as object recognition, natural language translation, and autonomous driving.

Another domain that has undergone a rapid big data transformation is the use of mobile sensors and devices, such as smart phones and wearable computing devices. With better sensor technologies, it has become possible to collect a variety of information about our physical world using low-cost sensors embedded on everyday objects that are connected to each other, termed the Internet of Things (IOT). This deep integration of physical sensors in digital systems is beginning to generate large amounts of diverse and distributed data about our environment, which can be used for designing convenient, safe, and energy-efficient home systems, as well as for urban planning of smart cities.

Medicine, Science, and Engineering Researchers in medicine, science, and engineering are rapidly accumulating data that is key to significant new discoveries. For example, as an important step toward improving our

understanding of the Earth’s climate system, NASA has deployed a series of Earth-orbiting satellites that continuously generate global observations of the land surface, oceans, and atmosphere. However, because of the size and spatio-temporal nature of the data, traditional methods are often not suitable for analyzing these data sets. Techniques developed in data mining can aid Earth scientists in answering questions such as the following: “What is the relationship between the frequency and intensity of ecosystem disturbances such as droughts and hurricanes to global warming?” “How is land surface precipitation and temperature affected by ocean surface temperature?” and “How well can we predict the beginning and end of the growing season for a region?”

As another example, researchers in molecular biology hope to use the large amounts of genomic data to better understand the structure and function of genes. In the past, traditional methods in molecular biology allowed scientists to study only a few genes at a time in a given experiment. Recent breakthroughs in microarray technology have enabled scientists to compare the behavior of thousands of genes under various situations. Such comparisons can help determine the function of each gene, and perhaps isolate the genes responsible for certain diseases. However, the noisy, high- dimensional nature of data requires new data analysis methods. In addition to analyzing gene expression data, data mining can also be used to address other important biological challenges such as protein structure prediction, multiple sequence alignment, the modeling of biochemical pathways, and phylogenetics.

Another example is the use of data mining techniques to analyze electronic health record (EHR) data, which has become increasingly available. Not very long ago, studies of patients required manually examining the physical records of individual patients and extracting very specific pieces of information pertinent to the particular question being investigated. EHRs allow for a faster and broader exploration of such data. However, there are significant challenges since the observations on any one patient typically occur during their visits to a doctor or hospital and only a small number of details about the health of the patient are measured during any particular visit.

Currently, EHR analysis focuses on simple types of data, e.g., a patient’s

blood pressure or the diagnosis code of a disease. However, large amounts of more complex types of medical data are also being collected, such as electrocardiograms (ECGs) and neuroimages from magnetic resonance imaging (MRI) or functional Magnetic Resonance Imaging (fMRI). Although challenging to analyze, this data also provides vital information about patients. Integrating and analyzing such data, with traditional EHR and genomic data is one of the capabilities needed to enable precision medicine, which aims to provide more personalized patient care.

1.1 What Is Data Mining? Data mining is the process of automatically discovering useful information in large data repositories. Data mining techniques are deployed to scour large data sets in order to find novel and useful patterns that might otherwise remain unknown. They also provide the capability to predict the outcome of a future observation, such as the amount a customer will spend at an online or a brick-and-mortar store.

Not all information discovery tasks are considered to be data mining. Examples include queries, e.g., looking up individual records in a database or finding web pages that contain a particular set of keywords. This is because such tasks can be accomplished through simple interactions with a database management system or an information retrieval system. These systems rely on traditional computer science techniques, which include sophisticated indexing structures and query processing algorithms, for efficiently organizing and retrieving information from large data repositories. Nonetheless, data mining techniques have been used to enhance the performance of such systems by improving the quality of the search results based on their relevance to the input queries.