WIXLIB

xiiContents4.1.44.1.54.24.34.44.54.64.74.8Data Warehousing: A Multitiered Architecture 130Data Warehouse Models: Enterprise Warehouse, Data Mart,and Virtual Warehouse 1324.1.6 Extraction, Transformation, and Loading 1344.1.7 Metadata Repository 134Data Warehouse Modeling: Data Cube and OLAP 1354.2.1 Data Cube: A Multidimensional Data Model 1364.2.2 Stars, Snowflakes, and Fact Constellations: Schemasfor Multidimensional Data Models 1394.2.3 Dimensions: The Role of Concept Hierarchies 1424.2.4 Measures: Their Categorization and Computation 1444.2.5 Typical OLAP Operations 1464.2.6 A Starnet Query Model for Querying MultidimensionalDatabases 149Data Warehouse Design and Usage 1504.3.1 A Business Analysis Framework for Data Warehouse Design 1504.3.2 Data Warehouse Design Process 1514.3.3 Data Warehouse Usage for Information Processing 1534.3.4 From Online Analytical Processing to MultidimensionalData Mining 155Data Warehouse Implementation 1564.4.1 Efficient Data Cube Computation: An Overview 1564.4.2 Indexing OLAP Data: Bitmap Index and Join Index 1604.4.3 Efficient Processing of OLAP Queries 1634.4.4 OLAP Server Architectures: ROLAP versus MOLAPversus HOLAP 164Data Generalization by Attribute-Oriented Induction 1664.5.1 Attribute-Oriented Induction for Data Characterization 1674.5.2 Efficient Implementation of Attribute-Oriented Induction 1724.5.3 Attribute-Oriented Induction for Class Comparisons 175Summary 178Exercises 180Bibliographic Notes 184Chapter 5 Data Cube Technology 1875.1Data Cube Computation: Preliminary Concepts 1885.1.1 Cube Materialization: Full Cube, Iceberg Cube, Closed Cube,and Cube Shell 1885.1.2 General Strategies for Data Cube Computation 1925.2Data Cube Computation Methods 1945.2.1 Multiway Array Aggregation for Full Cube Computation 195

Contents5.2.2xiii5.5BUC: Computing Iceberg Cubes from the Apex CuboidDownward 2005.2.3 Star-Cubing: Computing Iceberg Cubes Using a DynamicStar-Tree Structure 2045.2.4 Precomputing Shell Fragments for Fast High-Dimensional OLAP 210Processing Advanced Kinds of Queries by Exploring CubeTechnology 2185.3.1 Sampling Cubes: OLAP-Based Mining on Sampling Data 2185.3.2 Ranking Cubes: Efficient Computation of Top-k Queries 225Multidimensional Data Analysis in Cube Space 2275.4.1 Prediction Cubes: Prediction Mining in Cube Space 2275.4.2 Multifeature Cubes: Complex Aggregation at MultipleGranularities 2305.4.3 Exception-Based, Discovery-Driven Cube Space Exploration 231Summary 2345.6Exercises5.7Bibliographic Notes5.35.4235240Chapter 6 Mining Frequent Patterns, Associations, and Correlations: BasicConcepts and Methods 2436.1Basic Concepts 2436.1.1 Market Basket Analysis: A Motivating Example 2446.1.2 Frequent Itemsets, Closed Itemsets, and Association Rules 2466.2Frequent Itemset Mining Methods 2486.2.1 Apriori Algorithm: Finding Frequent Itemsets by ConfinedCandidate Generation 2486.2.2 Generating Association Rules from Frequent Itemsets 2546.2.3 Improving the Efficiency of Apriori 2546.2.4 A Pattern-Growth Approach for Mining Frequent Itemsets 2576.2.5 Mining Frequent Itemsets Using Vertical Data Format 2596.2.6 Mining Closed and Max Patterns 2626.36.4Which Patterns Are Interesting?—Pattern EvaluationMethods 2646.3.1 Strong Rules Are Not Necessarily Interesting 2646.3.2 From Association Analysis to Correlation Analysis 2656.3.3 A Comparison of Pattern Evaluation Measures 267Summary 2716.5Exercises6.6Bibliographic Notes273276

xivContentsChapter 7 Advanced Pattern Mining 2797.1Pattern Mining: A Road Map 2797.2Pattern Mining in Multilevel, Multidimensional Space 2837.2.1 Mining Multilevel Associations 2837.2.2 Mining Multidimensional Associations 2877.2.3 Mining Quantitative Association Rules 2897.2.4 Mining Rare Patterns and Negative Patterns 2917.3Constraint-Based Frequent Pattern Mining 2947.3.1 Metarule-Guided Mining of Association Rules 2957.3.2 Constraint-Based Pattern Generation: Pruning Pattern Spaceand Pruning Data Space 2967.4Mining High-Dimensional Data and Colossal Patterns 3017.4.1 Mining Colossal Patterns by Pattern-Fusion 3027.5Mining Compressed or Approximate Patterns 3077.5.1 Mining Compressed Patterns by Pattern Clustering 3087.5.2 Extracting Redundancy-Aware Top-k Patterns 3107.6Pattern Exploration and Application 3137.6.1 Semantic Annotation of Frequent Patterns 3137.6.2 Applications of Pattern Mining 3177.7Summary 3197.8Exercises 3217.9Bibliographic Notes 323Chapter 8 Classification: Basic Concepts 3278.1Basic Concepts 3278.1.1 What Is Classification? 3278.1.2 General Approach to Classification 3288.2Decision Tree Induction 3308.2.1 Decision Tree Induction 3328.2.2 Attribute Selection Measures 3368.2.3 Tree Pruning 3448.2.4 Scalability and Decision Tree Induction 3478.2.5 Visual Mining for Decision Tree Induction 3488.3Bayes Classification Methods 3508.3.1 Bayes’ Theorem 3508.3.2 Naı̈ve Bayesian Classification 3518.4Rule-Based Classification 3558.4.1 Using IF-THEN Rules for Classification 3558.4.2 Rule Extraction from a Decision Tree 3578.4.3 Rule Induction Using a Sequential Covering Algorithm359

Contents8.58.68.78.88.9xvModel Evaluation and Selection 3648.5.1 Metrics for Evaluating Classifier Performance 3648.5.2 Holdout Method and Random Subsampling 3708.5.3 Cross-Validation 3708.5.4 Bootstrap 3718.5.5 Model Selection Using Statistical Tests of Significance 3728.5.6 Comparing Classifiers Based on Cost–Benefit and ROC Curves 373Techniques to Improve Classification Accuracy 3778.6.1 Introducing Ensemble Methods 3788.6.2 Bagging 3798.6.3 Boosting and AdaBoost 3808.6.4 Random Forests 3828.6.5 Improving Classification Accuracy of Class-Imbalanced Data 383Summary 385Exercises 386Bibliographic Notes 389Chapter 9 Classification: Advanced Methods 3939.1Bayesian Belief Networks 3939.1.1 Concepts and Mechanisms 3949.1.2 Training Bayesian Belief Networks 3969.2Classification by Backpropagation 3989.2.1 A Multilayer Feed-Forward Neural Network 3989.2.2 Defining a Network Topology 4009.2.3 Backpropagation 4009.2.4 Inside the Black Box: Backpropagation and Interpretability 4069.3Support Vector Machines 4089.3.1 The Case When the Data Are Linearly Separable 4089.3.2 The Case When the Data Are Linearly Inseparable 4139.4Classification Using Frequent Patterns 4159.4.1 Associative Classification 4169.4.2 Discriminative Frequent Pattern–Based Classification 4199.5Lazy Learners (or Learning from Your Neighbors) 4229.5.1 k-Nearest-Neighbor Classifiers 4239.5.2 Case-Based Reasoning 4259.6Other Classification Methods 4269.6.1 Genetic Algorithms 4269.6.2 Rough Set Approach 4279.6.3 Fuzzy Set Approaches 4289.7Additional Topics Regarding Classification 4299.7.1 Multiclass Classification 430

xviContents9.89.99.109.7.2 Semi-Supervised Classification9.7.3 Active Learning 4339.7.4 Transfer Learning 434Summary 436Exercises 438Bibliographic Notes 439432Chapter 10 Cluster Analysis: Basic Concepts and Methods 44310.1 Cluster Analysis 44410.1.1 What Is Cluster Analysis? 44410.1.2 Requirements for Cluster Analysis 44510.1.3 Overview of Basic Clustering Methods 44810.2 Partitioning Methods 45110.2.1 k-Means: A Centroid-Based Technique 45110.2.2 k-Medoids: A Representative Object-Based Technique 45410.3 Hierarchical Methods 45710.3.1 Agglomerative versus Divisive Hierarchical Clustering 45910.3.2 Distance Measures in Algorithmic Methods 46110.3.3 BIRCH: Multiphase Hierarchical Clustering Using ClusteringFeature Trees 46210.3.4 Chameleon: Multiphase Hierarchical Clustering Using DynamicModeling 46610.3.5 Probabilistic Hierarchical Clustering 46710.4 Density-Based Methods 47110.4.1 DBSCAN: Density-Based Clustering Based on ConnectedRegions with High Density 47110.4.2 OPTICS: Ordering Points to Identify the Clustering Structure 47310.4.3 DENCLUE: Clustering Based on Density Distribution Functions 47610.5 Grid-Based Methods 47910.5.1 STING: STatistical INformation Grid 47910.5.2 CLIQUE: An Apriori-like Subspace Clustering Method 48110.6 Evaluation of Clustering 48310.6.1 Assessing Clustering Tendency 48410.6.2 Determining the Number of Clusters 48610.6.3 Measuring Clustering Quality 48710.7 Summary 49010.8 Exercises 49110.9 Bibliographic Notes 494Chapter 11 Advanced Cluster Analysis 49711.1 Probabilistic Model-Based Clustering11.1.1 Fuzzy Clusters 499497

Contents11.211.311.411.511.611.711.1.2 Probabilistic Model-Based Clusters 50111.1.3 Expectation-Maximization Algorithm 505Clustering High-Dimensional Data 50811.2.1 Clustering High-Dimensional Data: Problems, Challenges,and Major Methodologies 50811.2.2 Subspace Clustering Methods 51011.2.3 Biclustering 51211.2.4 Dimensionality Reduction Methods and Spectral ClusteringClustering Graph and Network Data 52211.3.1 Applications and Challenges 52311.3.2 Similarity Measures 52511.3.3 Graph Clustering Methods 528Clustering with Constraints 53211.4.1 Categorization of Constraints 53311.4.2 Methods for Clustering with Constraints 535Summary 538Exercises 539Bibliographic Notes 540519Chapter 12 Outlier Detection 54312.1 Outliers and Outlier Analysis 54412.1.1 What Are Outliers? 54412.1.2 Types of Outliers 54512.1.3 Challenges of Outlier Detection 54812.2 Outlier Detection Methods 54912.2.1 Supervised, Semi-Supervised, and Unsupervised Methods 54912.2.2 Statistical Methods, Proximity-Based Methods, andClustering-Based Methods 55112.3 Statistical Approaches 55312.3.1 Parametric Methods 55312.3.2 Nonparametric Methods 55812.4 Proximity-Based Approaches 56012.4.1 Distance-Based Outlier Detection and a Nested LoopMethod 56112.4.2 A Grid-Based Method 56212.4.3 Density-Based Outlier Detection 56412.5 Clustering-Based Approaches 56712.6 Classification-Based Approaches 57112.7 Mining Contextual and Collective Outliers 57312.7.1 Transforming Contextual Outlier Detection to ConventionalOutlier Detection 573xvii

xviiiContents12.7.2 Modeling Normal Behavior with Respect to Contexts12.7.3 Mining Collective Outliers 57512.8 Outlier Detection in High-Dimensional Data 57612.8.1 Extending Conventional Outlier Detection 57712.8.2 Finding Outliers in Subspaces 57812.8.3 Modeling High-Dimensional Outliers 57912.9 Summary 58112.10 Exercises 58212.11 Bibliographic Notes 583574Chapter 13 Data Mining Trends and Research Frontiers 58513.1 Mining Complex Data Types 58513.1.1 Mining Sequence Data: Time-Series, Symbolic Sequences,and Biological Sequences 58613.1.2 Mining Graphs and Networks 59113.1.3 Mining Other Kinds of Data 59513.2 Other Methodologies of Data Mining 59813.2.1 Statistical Data Mining 59813.2.2 Views on Data Mining Foundations 60013.2.3 Visual and Audio Data Mining 60213.3 Data Mining Applications 60713.3.1 Data Mining for Financial Data Analysis 60713.3.2 Data Mining for Retail and Telecommunication Industries 60913.3.3 Data Mining in Science and Engineering 61113.3.4 Data Mining for Intrusion Detection and Prevention 61413.3.5 Data Mining and Recommender Systems 61513.4 Data Mining and Society 61813.4.1 Ubiquitous and Invisible Data Mining 61813.4.2 Privacy, Security, and Social Impacts of Data Mining 62013.5 Data Mining Trends 62213.6 Summary 62513.7 Exercises 62613.8 Bibliographic Notes 628BibliographyIndex673633

ForewordAnalyzing large amounts of data is a necessity. Even popular science books, like “supercrunchers,” give compelling cases where large amounts of data yield discoveries andintuitions that surprise even experts. Every enterprise benefits from collecting and analyzing its data: Hospitals can spot trends and anomalies in their patient records, searchengines can do better ranking and ad placement, and environmental and public healthagencies can spot patterns and abnormalities in their data. The list continues, withcybersecurity and computer network intrusion detection; monitoring of the energyconsumption of household appliances; pattern analysis in bioinformatics and pharmaceutical data; financial and business intelligence data; spotting trends in blogs, Twitter,and many more. Storage is inexpensive and getting even less so, as are data sensors. Thus,collecting and storing data is easier than ever before.The problem then becomes how to analyze the data. This is exactly the focus of thisThird Edition of the book. Jiawei, Micheline, and Jian give encyclopedic coverage of allthe related methods, from the classic topics of clustering and classification, to databasemethods (e.g., association rules, data cubes) to more recent and advanced topics (e.g.,SVD/PCA, wavelets, support vector machines).The exposition is extremely accessible to beginners and advanced readers alike. Thebook gives the fundamental material first and the more advanced material in follow-upchapters. It also has numerous rhetorical questions, which I found extremely helpful formaintaining focus.We have used the first two editions as textbooks in data mining courses at CarnegieMellon and plan to continue to do so with this Third Edition. The new version hassignificant additions: Notably, it has more than 100 citations to works from 2006onward, focusing on more recent material such as graphs and social networks, sensor networks, and outlier detection. This book has a new section for visualization, hasexpanded outlier detection into a whole chapter, and has separate chapters for advancedxix

xxForewordmethods—for example, pattern mining with top-k patterns and more and clusteringmethods with biclustering and graph clustering.Overall, it is an excellent book on classic and modern data mining methods, and it isideal not only for teaching but also as a reference book.Christos FaloutsosCarnegie Mellon University

Foreword to Second EditionWe are deluged by data—scientific data, medical data, demographic data, financial data,and marketing data. People have no time to look at this data. Human attention hasbecome the precious resource. So, we must find ways to automatically analyze thedata, to automatically classify it, to automatically summarize it, to automatically discover and characterize trends in it, and to automatically flag anomalies. This is oneof the most active and exciting areas of the database research community. Researchersin areas including statistics, visualization, artificial intelligence, and machine learningare contributing to this field. The breadth of the field makes it difficult to grasp theextraordinary progress over the last few decades.Six years ago, Jiawei Han’s and Micheline Kamber’s seminal textbook organized andpresented Data Mining. It heralded a golden age of innovation in the field. This revisionof their book reflects that progress; more than half of the references and historical notesare to recent work. The field has matured with many new and improved algorithms, andhas broadened to include many more datatypes: streams, sequences, graphs, time-series,geospatial, audio, images, and video. We are certainly not at the end of the golden age—indeed research and commercial interest in data mining continues to grow—but we areall fortunate to have this modern compendium.The book gives quick introductions to database and data mining concepts withparticular emphasis on data analysis. It then covers in a chapter-by-chapter tour theconcepts and techniques that underlie classification, prediction, association, and clustering. These topics are presented with examples, a tour of the best algorithms for eachproblem class, and with pragmatic rules of thumb about when to apply each technique.The Socratic presentation style is both very readable and very informative. I certainlylearned a lot from reading the first edition and got re-educated and updated in readingthe second edition.Jiawei Han and Micheline Kamber have been leading contributors to data miningresearch. This is the text they use with their students to bring them up to speed onxxi

xxiiForeword to Second Editionthe field. The field is evolving very rapidly, but this book is a quick way to learn thebasic ideas, and to understand where the field is today. I found it very informative andstimulating, and believe you will too.Jim GrayIn his memory

PrefaceThe computerization of our society has substantially enhanced our capabilities for bothgenerating and collecting data from diverse sources. A tremendous amount of data hasflooded almost every aspect of our lives. This explosive growth in stored or transientdata has generated an urgent need for new techniques and automated tools that canintelligently assist us in transforming the vast amounts of data into useful informationand knowledge. This has led to the generation of a promising and flourishing frontierin computer science called data mining, and its various applications. Data mining, alsopopularly referred to as knowledge discovery from data (KDD), is the automated or convenient extraction of patterns representing knowledge implicitly stored or captured inlarge databases, data warehouses, the Web, other massive information repositories, ordata streams.This book explores the concepts and techniques of knowledge discovery and data mining. As a multidisciplinary field, data mining draws on work from areas including statistics,machine learning, pattern recognition, database technology, information retrieval,network science, knowledge-based systems, artificial intelligence, high-performancecomputing, and data visualization. We focus on issues relating to the feasibility, usefulness, effectiveness, and scalability of techniques for the discovery of patterns hiddenin large data sets. As a result, this book is not intended as an introduction to statistics, machine learning, database systems, or other such areas, although we do providesome background knowledge to facilitate the reader’s comprehension of their respectiveroles in data mining. Rather, the book is a comprehensive introduction to data mining.It is useful for computing science students, application developers, and businessprofessionals, as well as researchers involved in any of the disciplines previously listed.Data mining emerged during the late 1980s, made great strides during the 1990s, andcontinues to flourish into the new millennium. This book presents an overall pictureof the field, introducing interesting data mining techniques and systems and discussingapplications and research directions. An important motivation for writing this book wasthe need to build an organized framework for the study of data mining—a challengingtask, owing to the extensive multidiscip

Data Preparation for Data Mining Using SAS Mamdouh Refaat Querying XML: XQuery, XPath, and SQL/ XML in Context Jim Melton, Stephen Buxton Data Mining: Concepts and Techniques, 3rd Edition Jiawei Han, Micheline Kamber, Jian Pei Database Modeling and Design: Logical Design, 5th Edition Toby