中国奇迹的黄昏

Introduction to Data Mining presents fundamental concepts and algorithms for those learning data mining for the first time. Each concept is explored thoroughly and supported with numerous examples. KEY TOPICS: Provides both theoretical and practical coverage of all data mining topics. Includes extensive number of integrated examples and figures. Topics covered include; predictive modeling, association analysis, clustering, anomaly detection, visualization. MARKET: Suitable for individuals seeking an introduction to data mining. The text assumes only a modest statistics or mathematics background, and no database knowledge is needed. INTRODUCTION TO DATA MINING INTRODUCTION TO DATA MINING Preface to the Second Edition Overview What is New in the Second Edition? To the Instructor Support Materials Contents 1 Introduction 1.1 What Is Data Mining? 1.2 Motivating Challenges 1.3 The Origins of Data Mining 1.4 Data Mining Tasks 1.5 Scope and Organization of the Book 1.6 Bibliographic Notes Bibliography 1.7 Exercises 2 Data 2.1 Types of Data 2.1.1 Attributes and Measurement What Is an Attribute? The Type of an Attribute The Different Types of Attributes Describing Attributes by the Number of Values Asymmetric Attributes General Comments on Levels of Measurement 2.1.2 Types of Data Sets General Characteristics of Data Sets Dimensionality Distribution Resolution Record Data Transaction or Market Basket Data The Data Matrix The Sparse Data Matrix Graph-Based Data Data with Relationships among Objects Data with Objects That Are Graphs Ordered Data Sequential Transaction Data Time Series Data Sequence Data Spatial and Spatio-Temporal Data Handling Non-Record Data 2.2 Data Quality 2.2.1 Measurement and Data Collection Issues Measurement and Data Collection Errors Noise and Artifacts Precision, Bias, and Accuracy Outliers Missing Values Eliminate Data Objects or Attributes Estimate Missing Values Ignore the Missing Value during Analysis Inconsistent Values Duplicate Data 2.2.2 Issues Related to Applications 2.3 Data Preprocessing 2.3.1 Aggregation 2.3.2 Sampling Sampling Approaches Progressive Sampling 2.3.3 Dimensionality Reduction The Curse of Dimensionality Linear Algebra Techniques for Dimensionality Reduction 2.3.4 Feature Subset Selection An Architecture for Feature Subset Selection Feature Weighting 2.3.5 Feature Creation Feature Extraction Mapping the Data to a New Space 2.3.6 Discretization and Binarization Binarization Discretization of Continuous Attributes Unsupervised Discretization Supervised Discretization Categorical Attributes with Too Many Values 2.3.7 Variable Transformation Simple Functions Normalization or Standardization 2.4 Measures of Similarity and Dissimilarity 2.4.1 Basics Definitions Transformations 2.4.2 Similarity and Dissimilarity between Simple Attributes 2.4.3 Dissimilarities between Data Objects Distances 2.4.4 Similarities between Data Objects 2.4.5 Examples of Proximity Measures Similarity Measures for Binary Data Simple Matching Coefficient Jaccard Coefficient Cosine Similarity Extended Jaccard Coefficient (Tanimoto Coefficient) Correlation Differences Among Measures For Continuous Attributes 2.4.6 Mutual Information 2.4.7 Kernel Functions* 2.4.8 Bregman Divergence* 2.4.9 Issues in Proximity Calculation Standardization and Correlation for Distance Measures Combining Similarities for Heterogeneous Attributes Using Weights 2.4.10 Selecting the Right Proximity Measure 2.5 Bibliographic Notes Bibliography 2.6 Exercises 3 Classification: Basic Concepts and Techniques 3.1 Basic Concepts 3.2 General Framework for Classification 3.3 Decision Tree Classifier 3.3.1 A Basic Algorithm to Build a Decision Tree Hunt's Algorithm Design Issues of Decision Tree Induction 3.3.2 Methods for Expressing Attribute Test Conditions 3.3.3 Measures for Selecting an Attribute Test Condition Impurity Measure for a Single Node Collective Impurity of Child Nodes Identifying the best attribute test condition Splitting of Qualitative Attributes Binary Splitting of Qualitative Attributes Binary Splitting of Quantitative Attributes Gain Ratio 3.3.4 Algorithm for Decision Tree Induction 3.3.5 Example Application: Web Robot Detection 3.3.6 Characteristics of Decision Tree Classifiers 3.4 Model Overfitting 3.4.1 Reasons for Model Overfitting Limited Training Size High Model Complexity 3.5 Model Selection 3.5.1 Using a Validation Set 3.5.2 Incorporating Model Complexity Estimating the Complexity of Decision Trees Minimum Description Length Principle 3.5.3 Estimating Statistical Bounds 3.5.4 Model Selection for Decision Trees 3.6 Model Evaluation 3.6.1 Holdout Method 3.6.2 Cross-Validation 3.7 Presence of Hyper-parameters 3.7.1 Hyper-parameter Selection 3.7.2 Nested Cross-Validation 3.8 Pitfalls of Model Selection and Evaluation 3.8.1 Overlap between Training and Test Sets 3.8.2 Use of Validation Error as Generalization Error 3.9 Model Comparison* 3.9.1 Estimating the Confidence Interval for Accuracy 3.9.2 Comparing the Performance of Two Models 3.10 Bibliographic Notes Bibliography 3.11 Exercises 4 Classification: Alternative Techniques 4.1 Types of Classifiers 4.2 Rule-Based Classifier 4.2.1 How a Rule-Based Classifier Works 4.2.2 Properties of a Rule Set 4.2.3 Direct Methods for Rule Extraction Learn-One-Rule Function Rule Pruning Building the Rule Set Instance Elimination 4.2.4 Indirect Methods for Rule Extraction 4.2.5 Characteristics of Rule-Based Classifiers 4.3 Nearest Neighbor Classifiers 4.3.1 Algorithm 4.3.2 Characteristics of Nearest Neighbor Classifiers 4.4 Naïve Bayes Classifier 4.4.1 Basics of Probability Theory Bayes Theorem Using Bayes Theorem for Classification 4.4.2 Naïve Bayes Assumption Conditional Independence How a Naïve Bayes Classifier Works Estimating Conditional Probabilities for Categorical Attributes Estimating Conditional Probabilities for Continuous Attributes Handling Zero Conditional Probabilities Characteristics of Naïve Bayes Classifiers 4.5 Bayesian Networks 4.5.1 Graphical Representation Conditional Independence Joint Probability Use of Hidden Variables 4.5.2 Inference and Learning Variable Elimination Sum-Product Algorithm for Trees Generalizations for Non-Tree Graphs Learning Model Parameters 4.5.3 Characteristics of Bayesian Networks 4.6 Logistic Regression 4.6.1 Logistic Regression as a Generalized Linear Model 4.6.2 Learning Model Parameters 4.6.3 Characteristics of Logistic Regression 4.7 Artificial Neural Network (ANN) 4.7.1 Perceptron Learning the Perceptron 4.7.2 Multi-layer Neural Network Learning Model Parameters 4.7.3 Characteristics of ANN 4.8 Deep Learning 4.8.1 Using Synergistic Loss Functions Saturation of Outputs Cross entropy loss function 4.8.2 Using Responsive Activation Functions Vanishing Gradient Problem Rectified Linear Units (ReLU) 4.8.3 Regularization Dropout 4.8.4 Initialization of Model Parameters Supervised Pretraining Unsupervised Pretraining Use of Autoencoders Hybrid Pretraining 4.8.5 Characteristics of Deep Learning 4.9 Support Vector Machine (SVM) 4.9.1 Margin of a Separating Hyperplane Rationale for Maximum Margin 4.9.2 Linear SVM Learning Model Parameters 4.9.3 Soft-margin SVM SVM as a Regularizer of Hinge Loss 4.9.4 Nonlinear SVM Attribute Transformation Learning a Nonlinear SVM Model 4.9.5 Characteristics of SVM 4.10 Ensemble Methods 4.10.1 Rationale for Ensemble Method 4.10.2 Methods for Constructing an Ensemble Classifier 4.10.3 Bias-Variance Decomposition 4.10.4 Bagging 4.10.5 Boosting AdaBoost 4.10.6 Random Forests 4.10.7 Empirical Comparison among Ensemble Methods 4.11 Class Imbalance Problem 4.11.1 Building Classifiers with Class Imbalance Oversampling and Undersampling Assigning Scores to Test Instances 4.11.2 Evaluating Performance with Class Imbalance 4.11.3 Finding an Optimal Score Threshold 4.11.4 Aggregate Evaluation of Performance ROC Curve Precision-Recall Curve 4.12 Multiclass Problem 4.13 Bibliographic Notes Bibliography 4.14 Exercises 5 Association Analysis: Basic Concepts and Algorithms 5.1 Preliminaries 5.2 Frequent Itemset Generation 5.2.1 The Apriori Principle 5.2.2 Frequent Itemset Generation in the Apriori Algorithm 5.2.3 Candidate Generation and Pruning Candidate Generation Brute-Force Method Fk−1×F1 Method Fk−1×Fk−1 Method Candidate Pruning 5.2.4 Support Counting Support Counting Using a Hash Tree* 5.2.5 Computational Complexity 5.3 Rule Generation 5.3.1 Confidence-Based Pruning 5.3.2 Rule Generation in Apriori Algorithm 5.3.3 An Example: Congressional Voting Records 5.4 Compact Representation of Frequent Itemsets 5.4.1 Maximal Frequent Itemsets 5.4.2 Closed Itemsets 5.5 Alternative Methods for Generating Frequent Itemsets* 5.6 FP-Growth Algorithm* 5.6.1 FP-Tree Representation 5.6.2 Frequent Itemset Generation in FP-Growth Algorithm 5.7 Evaluation of Association Patterns 5.7.1 Objective Measures of Interestingness Alternative Objective Interestingness Measures Consistency among Objective Measures Properties of Objective Measures Inversion Property Scaling Property Null Addition Property Asymmetric Interestingness Measures 5.7.2 Measures beyond Pairs of Binary Variables 5.7.3 Simpson's Paradox 5.8 Effect of Skewed Support Distribution 5.9 Bibliographic Notes Bibliography 5.10 Exercises 6 Association Analysis: Advanced Concepts 6.1 Handling Categorical Attributes 6.2 Handling Continuous Attributes 6.2.1 Discretization-Based Methods 6.2.2 Statistics-Based Methods Rule Generation Rule Validation 6.2.3 Non-discretization Methods 6.3 Handling a Concept Hierarchy 6.4 Sequential Patterns 6.4.1 Preliminaries Sequences Subsequences 6.4.2 Sequential Pattern Discovery 6.4.3 Timing Constraints* The maxspan Constraint The mingap and maxgap Constraints The Window Size Constraint 6.4.4 Alternative Counting Schemes* 6.5 Subgraph Patterns 6.5.1 Preliminaries Graphs Graph Isomorphism Subgraphs 6.5.2 Frequent Subgraph Mining 6.5.3 Candidate Generation 6.5.4 Candidate Pruning 6.5.5 Support Counting 6.6 Infrequent Patterns* 6.6.1 Negative Patterns 6.6.2 Negatively Correlated Patterns 6.6.3 Comparisons among Infrequent Patterns, Negative Patterns, and Negatively Correlated Patterns 6.6.4 Techniques for Mining Interesting Infrequent Patterns 6.6.5 Techniques Based on Mining Negative Patterns 6.6.6 Techniques Based on Support Expectation Support Expectation Based on Concept Hierarchy Support Expectation Based on Indirect Association 6.7 Bibliographic Notes Bibliography 6.8 Exercises 7 Cluster Analysis: Basic Concepts and Algorithms 7.1 Overview 7.1.1 What Is Cluster Analysis? 7.1.2 Different Types of Clusterings 7.1.3 Different Types of Clusters Road Map 7.2 K-means 7.2.1 The Basic K-means Algorithm Assigning Points to the Closest Centroid Centroids and Objective Functions Data in Euclidean Space Document Data The General Case Choosing Initial Centroids K-means++ Time and Space Complexity 7.2.2 K-means: Additional Issues Handling Empty Clusters Outliers Reducing the SSE with Postprocessing Updating Centroids Incrementally 7.2.3 Bisecting K-means 7.2.4 K-means and Different Types of Clusters 7.2.5 Strengths and Weaknesses 7.2.6 K-means as an Optimization Problem Derivation of K-means as an Algorithm to Minimize the SSE Derivation of K-means for SAE 7.3 Agglomerative Hierarchical Clustering 7.3.1 Basic Agglomerative Hierarchical Clustering Algorithm Defining Proximity between Clusters Time and Space Complexity 7.3.2 Specific Techniques Sample Data Single Link or MIN Complete Link or MAX or CLIQUE Group Average Ward’s Method and Centroid Methods 7.3.3 The Lance-Williams Formula for Cluster Proximity 7.3.4 Key Issues in Hierarchical Clustering Lack of a Global Objective Function Ability to Handle Different Cluster Sizes Merging Decisions Are Final 7.3.5 Outliers 7.3.6 Strengths and Weaknesses 7.4 DBSCAN 7.4.1 Traditional Density: Center-Based Approach Classification of Points According to Center-Based Density 7.4.2 The DBSCAN Algorithm Time and Space Complexity Selection of DBSCAN Parameters Clusters of Varying Density An Example 7.4.3 Strengths and Weaknesses 7.5 Cluster Evaluation 7.5.1 Overview 7.5.2 Unsupervised Cluster Evaluation Using Cohesion and Separation Graph-Based View of Cohesion and Separation Prototype-Based View of Cohesion and Separation Relationship between Prototype-Based Cohesion and Graph-Based Cohesion Relationship of the Two Approaches to Prototype-Based Separation Relationship between Cohesion and Separation Relationship between Graph- and Centroid-Based Cohesion Overall Measures of Cohesion and Separation Evaluating Individual Clusters and Objects The Silhouette Coefficient 7.5.3 Unsupervised Cluster Evaluation Using the Proximity Matrix General Comments on Unsupervised Cluster Evaluation Measures Measuring Cluster Validity via Correlation Judging a Clustering Visually by Its Similarity Matrix 7.5.4 Unsupervised Evaluation of Hierarchical Clustering 7.5.5 Determining the Correct Number of Clusters 7.5.6 Clustering Tendency 7.5.7 Supervised Measures of Cluster Validity Classification-Oriented Measures of Cluster Validity Similarity-Oriented Measures of Cluster Validity Cluster Validity for Hierarchical Clusterings 7.5.8 Assessing the Significance of Cluster Validity Measures 7.5.9 Choosing a Cluster Validity Measure 7.6 Bibliographic Notes Bibliography 7.7 Exercises 8 Cluster Analysis: Additional Issues and Algorithms 8.1 Characteristics of Data, Clusters, and Clustering Algorithms 8.1.1 Example: Comparing K-means and DBSCAN 8.1.2 Data Characteristics 8.1.3 Cluster Characteristics 8.1.4 General Characteristics of Clustering Algorithms Road Map 8.2 Prototype-Based Clustering 8.2.1 Fuzzy Clustering Fuzzy Sets Fuzzy Clusters Fuzzy c-means Computing SSE Initialization Computing Centroids Updating the Fuzzy Pseudo-partition Strengths and Limitations 8.2.2 Clustering Using Mixture Models Mixture Models Estimating Model Parameters Using Maximum Likelihood Estimating Mixture Model Parameters Using Maximum Likelihood: The EM Algorithm Advantages and Limitations of Mixture Model Clustering Using the EM Algorithm 8.2.3 Self-Organizing Maps (SOM) The SOM Algorithm Initialization Selection of an Object Assignment Update Termination Applications Strengths and Limitations 8.3 Density-Based Clustering 8.3.1 Grid-Based Clustering Defining Grid Cells The Density of Grid Cells Forming Clusters from Dense Grid Cells Strengths and Limitations 8.3.2 Subspace Clustering CLIQUE Strengths and Limitations of CLIQUE 8.3.3 DENCLUE: A Kernel-Based Scheme for Density-Based Clustering Kernel Density Estimation Implementation Issues Strengths and Limitations of DENCLUE 8.4 Graph-Based Clustering 8.4.1 Sparsification 8.4.2 Minimum Spanning Tree (MST) Clustering 8.4.3 OPOSSUM: Optimal Partitioning of Sparse Similarities Using METIS Strengths and Weaknesses 8.4.4 Chameleon: Hierarchical Clustering with Dynamic Modeling Deciding Which Clusters to Merge Chameleon Algorithm Sparsification Graph Partitioning Agglomerative Hierarchical Clustering Complexity Strengths and Limitations 8.4.5 Spectral Clustering Relationship between Spectral Clustering and Graph Partitioning Strengths and Limitations 8.4.6 Shared Nearest Neighbor Similarity Problems with Traditional Similarity in High-Dimensional Data Problems with Differences in Density SNN Similarity Computation SNN Similarity versus Direct Similarity 8.4.7 The Jarvis-Patrick Clustering Algorithm Strengths and Limitations 8.4.8 SNN Density 8.4.9 SNN Density-Based Clustering The SNN Density-based Clustering Algorithm Strengths and Limitations 8.5 Scalable Clustering Algorithms 8.5.1 Scalability: General Issues and Approaches 8.5.2 BIRCH 8.5.3 CURE Sampling in CURE Partitioning 8.6 Which Clustering Algorithm? 8.7 Bibliographic Notes Bibliography 8.8 Exercises 9 Anomaly Detection 9.1 Characteristics of Anomaly Detection Problems 9.1.1 A Definition of an Anomaly 9.1.2 Nature of Data 9.1.3 How Anomaly Detection is Used 9.2 Characteristics of Anomaly Detection Methods 9.3 Statistical Approaches 9.3.1 Using Parametric Models Using the Univariate Gaussian Distribution Using the Multivariate Gaussian Distribution 9.3.2 Using Non-parametric Models 9.3.3 Modeling Normal and Anomalous Classes 9.3.4 Assessing Statistical Significance 9.3.5 Strengths and Weaknesses 9.4 Proximity-based Approaches 9.4.1 Distance-based Anomaly Score 9.4.2 Density-based Anomaly Score 9.4.3 Relative Density-based Anomaly Score 9.4.4 Strengths and Weaknesses 9.5 Clustering-based Approaches 9.5.1 Finding Anomalous Clusters 9.5.2 Finding Anomalous Instances Assessing the Extent to Which an Object Belongs to a Cluster Impact of Outliers on the Initial Clustering The Number of Clusters to Use 9.5.3 Strengths and Weaknesses 9.6 Reconstruction-based Approaches 9.6.1 Strengths and Weaknesses 9.7 One-class Classification 9.7.1 Use of Kernels 9.7.2 The Origin Trick 9.7.3 Strengths and Weaknesses 9.8 Information Theoretic Approaches 9.8.1 Strengths and Weaknesses 9.9 Evaluation of Anomaly Detection 9.10 Bibliographic Notes Bibliography 9.11 Exercises 10 Avoiding False Discoveries 10.1 Preliminaries: Statistical Testing 10.1.1 Significance Testing Null Hypothesis Test Statistic Null Distribution Assessing Statistical Significance 10.1.2 Hypothesis Testing Critical Region Type I and Type II Errors Effect Size 10.1.3 Multiple Hypothesis Testing Family-wise Error Rate (FWER) Bonferroni Procedure False discovery rate (FDR) Benjamini-Hochberg Procedure 10.1.4 Pitfalls in Statistical Testing 10.2 Modeling Null and Alternative Distributions 10.2.1 Generating Synthetic Data Sets 10.2.2 Randomizing Class Labels 10.2.3 Resampling Instances 10.2.4 Modeling the Distribution of the Test Statistic 10.3 Statistical Testing for Classification 10.3.1 Evaluating Classification Performance 10.3.2 Binary Classification as Multiple Hypothesis Testing 10.3.3 Multiple Hypothesis Testing in Model Selection 10.4 Statistical Testing for Association Analysis 10.4.1 Using Statistical Models Using Fisher’s Exact Test Using the Chi-Squared Test 10.4.2 Using Randomization Methods 10.5 Statistical Testing for Cluster Analysis 10.5.1 Generating a Null Distribution for Internal Indices 10.5.2 Generating a Null Distribution for External Indices 10.5.3 Enrichment 10.6 Statistical Testing for Anomaly Detection 10.7 Bibliographic Notes Bibliography 10.8 Exercises Author Index Subject Index Copyright Permissions