Data Mining: Concepts and Techniques (The Morgan Kaufmann Series in Data Management Systems) 4th Edition PDF – eBook

 

EBOOK DETAILS

• Authors: by Jiawei Han, Jian Pei, Hanghang Tong (Author)
• File Size: 19 MB
• Format: PDF
• Paperback: 786 pages
• Publisher: Morgan Kaufmann; 4th edition (October 17, 2022)
• Language: English
• ISBN-10: 9780128117606
• ISBN-13: 978-0128117606

Download Data Mining: Concepts and Techniques (The Morgan Kaufmann Series in Data Management Systems) 4th Edition PDF – eBook

Contents 

Foreword . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii Foreword to second edition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxi Acknowledgments ......................................................... xxvii About the authors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxix CHAPTER 1 Introduction .................................................. 1 1.1 What is data mining? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Data mining: an essential step in knowledge discovery . ................. 2 1.3 Diversity of data types for data mining .............................. 4 1.4 Mining various kinds of knowledge ................................ 5 1.4.1 Multidimensional data summarization ........................ 6 1.4.2 Mining frequent patterns, associations, and correlations . . . ........ 6 1.4.3 Classification and regression for predictive analysis .............. 7 1.4.4 Cluster analysis ......................................... 9 1.4.5 Deep learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4.6 Outlier analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4.7 Are all mining results interesting? . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.5 Data mining: confluence of multiple disciplines . . . . . . . . . . . . . . . . . . . . . . . 12 1.5.1 Statistics and data mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.5.2 Machine learning and data mining . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.5.3 Database technology and data mining . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5.4 Data mining and data science . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5.5 Data mining and other disciplines . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.6 Data mining and applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.7 Data mining and society . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.10 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 CHAPTER 2 Data, measurements, and data preprocessing ........................ 23 2.1 Data types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.1.1 Nominal attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.1.2 Binary attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.3 Ordinal attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.4 Numeric attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.1.5 Discrete vs. continuous attributes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2 Statistics of data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.2.1 Measuring the central tendency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.2 Measuring the dispersion of data . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 vii viii Contents 2.2.3 Covariance and correlation analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2.4 Graphic displays of basic statistics of data . . . . . . . . . . . . . . . . . . . . . 38 2.3 Similarity and distance measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.3.1 Data matrix vs. dissimilarity matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.3.2 Proximity measures for nominal attributes . . . . . . . . . . . . . . . . . . . . . 44 2.3.3 Proximity measures for binary attributes . . . . . . . . . . . . . . . . . . . . . . 46 2.3.4 Dissimilarity of numeric data: Minkowski distance . . . . . . . . . . . . . . 48 2.3.5 Proximity measures for ordinal attributes . . . . . . . . . . . . . . . . . . . . . . 49 2.3.6 Dissimilarity for attributes of mixed types . . . . . . . . . . . . . . . . . . . . . 50 2.3.7 Cosine similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.3.8 Measuring similar distributions: the Kullback-Leibler divergence . . . . 53 2.3.9 Capturing hidden semantics in similarity measures . . . . . . . . . . . . . . . 55 2.4 Data quality, data cleaning, and data integration . . . . . . . . . . . . . . . . . . . . . . . 55 2.4.1 Data quality measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.4.2 Data cleaning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.4.3 Data integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.5 Data transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2.5.1 Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 2.5.2 Discretization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 2.5.3 Data compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.5.4 Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 2.6 Dimensionality reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.6.1 Principal components analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.6.2 Attribute subset selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2.6.3 Nonlinear dimensionality reduction methods . . . . . . . . . . . . . . . . . . . 74 2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 2.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 2.9 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 CHAPTER 3 Data warehousing and online analytical processing ................... 85 3.1 Data warehouse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.1.1 Data warehouse: what and why? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.1.2 Architecture of data warehouses: enterprise data warehouses and data marts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 3.1.3 Data lakes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 3.2 Data warehouse modeling: schema and measures . . . . . . . . . . . . . . . . . . . . . . 96 3.2.1 Data cube: a multidimensional data model . . . . . . . . . . . . . . . . . . . . . 97 3.2.2 Schemas for multidimensional data models: stars, snowflakes, and fact constellations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3.2.3 Concept hierarchies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 3.2.4 Measures: categorization and computation . . . . . . . . . . . . . . . . . . . . . 105 3.3 OLAP operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 3.3.1 Typical OLAP operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 3.3.2 Indexing OLAP data: bitmap index and join index . . . . . . . . . . . . . . . 108 3.3.3 Storage implementation: column-based databases . . . . . . . . . . . . . . . 111 Contents ix 3.4 Data cube computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 3.4.1 Terminology of data cube computation . . . . . . . . . . . . . . . . . . . . . . . 113 3.4.2 Data cube materialization: ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 3.4.3 OLAP server architectures: ROLAP vs. MOLAP vs. HOLAP . . . . . . 117 3.4.4 General strategies for data cube computation . . . . . . . . . . . . . . . . . . . 119 3.5 Data cube computation methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 3.5.1 Multiway array aggregation for full cube computation . . . . . . . . . . . . 121 3.5.2 BUC: computing iceberg cubes from the apex cuboid downward . . . . 125 3.5.3 Precomputing shell fragments for fast high-dimensional OLAP . . . . . 129 3.5.4 Efficient processing of OLAP queries using cuboids . . . . . . . . . . . . . . 132 3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 3.8 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 CHAPTER 4 Pattern mining: basic concepts and methods ........................ 145 4.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 4.1.1 Market basket analysis: a motivating example . . . . . . . . . . . . . . . . . . 145 4.1.2 Frequent itemsets, closed itemsets, and association rules . . . . . . . . . . 147 4.2 Frequent itemset mining methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 4.2.1 Apriori algorithm: finding frequent itemsets by confined candidate generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 4.2.2 Generating association rules from frequent itemsets . . . . . . . . . . . . . . 153 4.2.3 Improving the efficiency of Apriori . . . . . . . . . . . . . . . . . . . . . . . . . . 155 4.2.4 A pattern-growth approach for mining frequent itemsets . . . . . . . . . . 157 4.2.5 Mining frequent itemsets using the vertical data format . . . . . . . . . . . 160 4.2.6 Mining closed and max patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 4.3 Which patterns are interesting?—Pattern evaluation methods . . . . . . . . . . . . . 163 4.3.1 Strong rules are not necessarily interesting . . . . . . . . . . . . . . . . . . . . . 163 4.3.2 From association analysis to correlation analysis . . . . . . . . . . . . . . . . 164 4.3.3 A comparison of pattern evaluation measures . . . . . . . . . . . . . . . . . . . 165 4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 4.6 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 CHAPTER 5 Pattern mining: advanced methods ................................ 175 5.1 Mining various kinds of patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 5.1.1 Mining multilevel associations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 5.1.2 Mining multidimensional associations . . . . . . . . . . . . . . . . . . . . . . . . 179 5.1.3 Mining quantitative association rules . . . . . . . . . . . . . . . . . . . . . . . . . 180 5.1.4 Mining high-dimensional data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 5.1.5 Mining rare patterns and negative patterns . . . . . . . . . . . . . . . . . . . . . 185 5.2 Mining compressed or approximate patterns . . . . . . . . . . . . . . . . . . . . . . . . . . 187 5.2.1 Mining compressed patterns by pattern clustering . . . . . . . . . . . . . . . 187 5.2.2 Extracting redundancy-aware top-k patterns . . . . . . . . . . . . . . . . . . . . 189 x Contents 5.3 Constraint-based pattern mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 5.3.1 Pruning pattern space with pattern pruning constraints . . . . . . . . . . . . 193 5.3.2 Pruning data space with data pruning constraints . . . . . . . . . . . . . . . . 196 5.3.3 Mining space pruning with succinctness constraints . . . . . . . . . . . . . . 197 5.4 Mining sequential patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 5.4.1 Sequential pattern mining: concepts and primitives . . . . . . . . . . . . . . 198 5.4.2 Scalable methods for mining sequential patterns . . . . . . . . . . . . . . . . 200 5.4.3 Constraint-based mining of sequential patterns . . . . . . . . . . . . . . . . . . 210 5.5 Mining subgraph patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 5.5.1 Methods for mining frequent subgraphs . . . . . . . . . . . . . . . . . . . . . . . 212 5.5.2 Mining variant and constrained substructure patterns . . . . . . . . . . . . . 219 5.6 Pattern mining: application examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 5.6.1 Phrase mining in massive text data . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 5.6.2 Mining copy and paste bugs in software programs . . . . . . . . . . . . . . . 230 5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 5.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 5.9 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 CHAPTER 6 Classification: basic concepts and methods ......................... 239 6.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 6.1.1 What is classification? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239 6.1.2 General approach to classification . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 6.2 Decision tree induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 6.2.1 Decision tree induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244 6.2.2 Attribute selection measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 6.2.3 Tree pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 6.3 Bayes classification methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259 6.3.1 Bayes’ theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260 6.3.2 Naïve Bayesian classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 6.4 Lazy learners (or learning from your neighbors) . . . . . . . . . . . . . . . . . . . . . . . 266 6.4.1 k-nearest-neighbor classifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 6.4.2 Case-based reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 6.5 Linear classifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 6.5.1 Linear regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270 6.5.2 Perceptron: turning linear regression to classification . . . . . . . . . . . . . 272 6.5.3 Logistic regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 6.6 Model evaluation and selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 6.6.1 Metrics for evaluating classifier performance . . . . . . . . . . . . . . . . . . . 278 6.6.2 Holdout method and random subsampling . . . . . . . . . . . . . . . . . . . . . 283 6.6.3 Cross-validation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283 6.6.4 Bootstrap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284 6.6.5 Model selection using statistical tests of significance . . . . . . . . . . . . . 285 6.6.6 Comparing classifiers based on cost–benefit and ROC curves . . . . . . . 286 6.7 Techniques to improve classification accuracy . . . . . . . . . . . . . . . . . . . . . . . . 290 6.7.1 Introducing ensemble methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 Contents xi 6.7.2 Bagging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 6.7.3 Boosting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 6.7.4 Random forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 6.7.5 Improving classification accuracy of class-imbalanced data . . . . . . . . 297 6.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 6.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 6.10 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 CHAPTER 7 Classification: advanced methods ................................. 307 7.1 Feature selection and engineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 7.1.1 Filter methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 7.1.2 Wrapper methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 7.1.3 Embedded methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 7.2 Bayesian belief networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 7.2.1 Concepts and mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 7.2.2 Training Bayesian belief networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 7.3 Support vector machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 7.3.1 Linear support vector machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 7.3.2 Nonlinear support vector machines . . . . . . . . . . . . . . . . . . . . . . . . . . 324 7.4 Rule-based and pattern-based classification . . . . . . . . . . . . . . . . . . . . . . . . . . 327 7.4.1 Using IF-THEN rules for classification . . . . . . . . . . . . . . . . . . . . . . . 328 7.4.2 Rule extraction from a decision tree . . . . . . . . . . . . . . . . . . . . . . . . . . 330 7.4.3 Rule induction using a sequential covering algorithm . . . . . . . . . . . . . 331 7.4.4 Associative classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 7.4.5 Discriminative frequent pattern–based classification . . . . . . . . . . . . . . 338 7.5 Classification with weak supervision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 7.5.1 Semisupervised classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 7.5.2 Active learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 7.5.3 Transfer learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 7.5.4 Distant supervision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 7.5.5 Zero-shot learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 7.6 Classification with rich data type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 7.6.1 Stream data classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 7.6.2 Sequence classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 7.6.3 Graph data classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355 7.7 Potpourri: other related techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 7.7.1 Multiclass classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 7.7.2 Distance metric learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362 7.7.3 Interpretability of classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 7.7.4 Genetic algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 7.7.5 Reinforcement learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 7.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369 7.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 7.10 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 xii Contents CHAPTER 8 Cluster analysis: basic concepts and methods ....................... 379 8.1 Cluster analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 8.1.1 What is cluster analysis? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380 8.1.2 Requirements for cluster analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 8.1.3 Overview of basic clustering methods . . . . . . . . . . . . . . . . . . . . . . . . 383 8.2 Partitioning methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385 8.2.1 k-Means: a centroid-based technique . . . . . . . . . . . . . . . . . . . . . . . . . 386 8.2.2 Variations of k-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388 8.3 Hierarchical methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394 8.3.1 Basic concepts of hierarchical clustering . . . . . . . . . . . . . . . . . . . . . . 394 8.3.2 Agglomerative hierarchical clustering . . . . . . . . . . . . . . . . . . . . . . . . 397 8.3.3 Divisive hierarchical clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400 8.3.4 BIRCH: scalable hierarchical clustering using clustering feature trees 402 8.3.5 Probabilistic hierarchical clustering . . . . . . . . . . . . . . . . . . . . . . . . . . 404 8.4 Density-based and grid-based methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407 8.4.1 DBSCAN: density-based clustering based on connected regions with high density . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 8.4.2 DENCLUE: clustering based on density distribution functions . . . . . . 411 8.4.3 Grid-based methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414 8.5 Evaluation of clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417 8.5.1 Assessing clustering tendency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417 8.5.2 Determining the number of clusters . . . . . . . . . . . . . . . . . . . . . . . . . . 419 8.5.3 Measuring clustering quality: extrinsic methods . . . . . . . . . . . . . . . . . 420 8.5.4 Intrinsic methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424 8.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425 8.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 8.8 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429 CHAPTER 9 Cluster analysis: advanced methods ............................... 431 9.1 Probabilistic model-based clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431 9.1.1 Fuzzy clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433 9.1.2 Probabilistic model-based clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . 435 9.1.3 Expectation-maximization algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 438 9.2 Clustering high-dimensional data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441 9.2.1 Why is clustering high-dimensional data challenging? . . . . . . . . . . . . 441 9.2.2 Axis-parallel subspace approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . 445 9.2.3 Arbitrarily oriented subspace approaches . . . . . . . . . . . . . . . . . . . . . . 447 9.3 Biclustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 9.3.1 Why and where is biclustering useful? . . . . . . . . . . . . . . . . . . . . . . . . 448 9.3.2 Types of biclusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450 9.3.3 Biclustering methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452 9.3.4 Enumerating all biclusters using MaPle . . . . . . . . . . . . . . . . . . . . . . . 453 9.4 Dimensionality reduction for clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454 9.4.1 Linear dimensionality reduction methods for clustering . . . . . . . . . . . 455 9.4.2 Nonnegative matrix factorization (NMF) . . . . . . . . . . . . . . . . . . . . . . 458 Contents xiii 9.4.3 Spectral clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460 9.5 Clustering graph and network data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463 9.5.1 Applications and challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463 9.5.2 Similarity measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465 9.5.3 Graph clustering methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470 9.6 Semisupervised clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475 9.6.1 Semisupervised clustering on partially labeled data . . . . . . . . . . . . . . 475 9.6.2 Semisupervised clustering on pairwise constraints . . . . . . . . . . . . . . . 476 9.6.3 Other types of background knowledge for semisupervised clustering . 477 9.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 9.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480 9.9 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482 CHAPTER 10 Deep learning ................................................ 485 10.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 10.1.1 What is deep learning? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 10.1.2 Backpropagation algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 10.1.3 Key challenges for training deep learning models . . . . . . . . . . . . . . . . 498 10.1.4 Overview of deep learning architecture . . . . . . . . . . . . . . . . . . . . . . . 499 10.2 Improve training of deep learning models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500 10.2.1 Responsive activation functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500 10.2.2 Adaptive learning rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 10.2.3 Dropout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504 10.2.4 Pretraining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507 10.2.5 Cross-entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509 10.2.6 Autoencoder: unsupervised deep learning . . . . . . . . . . . . . . . . . . . . . 511 10.2.7 Other techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514 10.3 Convolutional neural networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517 10.3.1 Introducing convolution operation . . . . . . . . . . . . . . . . . . . . . . . . . . . 517 10.3.2 Multidimensional convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519 10.3.3 Convolutional layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523 10.4 Recurrent neural networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526 10.4.1 Basic RNN models and applications . . . . . . . . . . . . . . . . . . . . . . . . . 526 10.4.2 Gated RNNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532 10.4.3 Other techniques for addressing long-term dependence . . . . . . . . . . . 536 10.5 Graph neural networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539 10.5.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540 10.5.2 Graph convolutional networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541 10.5.3 Other types of GNNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545 10.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547 10.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548 10.8 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552 CHAPTER 11 Outlier detection .............................................. 557 11.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557 xiv Contents 11.1.1 What are outliers? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558 11.1.2 Types of outliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559 11.1.3 Challenges of outlier detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561 11.1.4 An overview of outlier detection methods . . . . . . . . . . . . . . . . . . . . . 562 11.2 Statistical approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565 11.2.1 Parametric methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565 11.2.2 Nonparametric methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 569 11.3 Proximity-based approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572 11.3.1 Distance-based outlier detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572 11.3.2 Density-based outlier detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573 11.4 Reconstruction-based approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576 11.4.1 Matrix factorization–based methods for numerical data . . . . . . . . . . . 577 11.4.2 Pattern-based compression methods for categorical data . . . . . . . . . . . 582 11.5 Clustering- vs. classification-based approaches . . . . . . . . . . . . . . . . . . . . . . . . 585 11.5.1 Clustering-based approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585 11.5.2 Classification-based approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588 11.6 Mining contextual and collective outliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590 11.6.1 Transforming contextual outlier detection to conventional outlier detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591 11.6.2 Modeling normal behavior with respect to contexts . . . . . . . . . . . . . . 591 11.6.3 Mining collective outliers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592 11.7 Outlier detection in high-dimensional data . . . . . . . . . . . . . . . . . . . . . . . . . . . 593 11.7.1 Extending conventional outlier detection . . . . . . . . . . . . . . . . . . . . . . 594 11.7.2 Finding outliers in subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 595 11.7.3 Outlier detection ensemble . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596 11.7.4 Taming high dimensionality by deep learning . . . . . . . . . . . . . . . . . . . 597 11.7.5 Modeling high-dimensional outliers . . . . . . . . . . . . . . . . . . . . . . . . . . 599 11.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600 11.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601 11.10 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 602 CHAPTER 12 Data mining trends and research frontiers ........................... 605 12.1 Mining rich data types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605 12.1.1 Mining text data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605 12.1.2 Spatial-temporal data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 610 12.1.3 Graph and networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612 12.2 Data mining applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617 12.2.1 Data mining for sentiment and opinion . . . . . . . . . . . . . . . . . . . . . . . . 617 12.2.2 Truth discovery and misinformation identification . . . . . . . . . . . . . . . 620 12.2.3 Information and disease propagation . . . . . . . . . . . . . . . . . . . . . . . . . 623 12.2.4 Productivity and team science . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626 12.3 Data mining methodologies and systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629 12.3.1 Structuring unstructured data for knowledge mining: a data-driven approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629 12.3.2 Data augmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632 Contents xv 12.3.3 From correlation to causality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635 12.3.4 Network as a context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637 12.3.5 Auto-ML: methods and systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640 12.4 Data mining, people, and society . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642 12.4.1 Privacy-preserving data mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642 12.4.2 Human-algorithm interaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646 12.4.3 Mining beyond maximizing accuracy: fairness, interpretability, and robustness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648 12.4.4 Data mining for social good . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652 APPENDIX A Mathematical background ....................................... 655 A.1 Probability and statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655 A.1.1 PDF of typical distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655 A.1.2 MLE and MAP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656 A.1.3 Significance test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657 A.1.4 Density estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658 A.1.5 Bias-variance tradeoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659 A.1.6 Cross-validation and Jackknife . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 660 A.2 Numerical optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661 A.2.1 Gradient descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661 A.2.2 Variants of gradient descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662 A.2.3 Newton’s method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664 A.2.4 Coordinate descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666 A.2.5 Quadratic programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666 A.3 Matrix and linear algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 668 A.3.1 Linear system Ax = b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 668 A.3.2 Norms of vectors and matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 669 A.3.3 Matrix decompositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 669 A.3.4 Subspace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671 A.3.5 Orthogonality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 672 A.4 Concepts and tools from signal processing . . . . . . . . . . . . . . . . . . . . . . . . . . . 673 A.4.1 Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 673 A.4.2 Kullback-Leibler divergence (KL-divergence) . . . . . . . . . . . . . . . . . . 674 A.4.3 Mutual information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675 A.4.4 Discrete Fourier transform (DFT) and fast Fourier transform (FFT) . . 676 A.5 Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 681 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735