DECOMPOSITION METHODOLOGY FOR KNOWLEDGE DISCOVERY AND DATA MINING THEORY AND APPLICATIONS

1 . Knowledge Discovery and Data Mining: Concepts and
Fundamental Aspects 1
1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Data Mining and Knowledge Discovery . . . . . . . . . . . . 1
1.3 Taxonomy of Data Mining Methods . . . . . . . . . . . . . 3
1.4 Supervised Methods . . . . . . . . . . . . . . . . . . . . . . 4
1.4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4.2 Training Set . . . . . . . . . . . . . . . . . . . . . . . 5
1.4.3 Definition of the Classification Problem . . . . . . . 6
1.4.4 Induction Algorithms . . . . . . . . . . . . . . . . . . 8
1.5 Rule Induction . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Bayesian Methods . . . . . . . . . . . . . . . . . . . . . . . 12
1.7.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.7.2 Naive Bayes . . . . . . . . . . . . . . . . . . . . . . . 12
1.7.2.1 The Basic Naive Bayes Classifier . . . . . . 12
1.7.2.2 Naive Bayes for Numeric Attributes . . . . . 14
1.7.2.4 Laplace Correction . . . . . . . . . . . . . . 15
1.7.2.5 NoMatch . . . . . . . . . . . . . . . . . . . 15
1.7.3 Other Bayesian Methods . . . . . . . . . . . . . . . . 16
1.8 Other Induction Methods . . . . . . . . . . . . . . . . . . . 16
1.8.1 Neural Networks . . . . . . . . . . . . . . . . . . . . 16
1.8.2 Genetic Algorithms . . . . . . . . . . . . . . . . . . . 18
1.7.2.3 Correction to the Probability Estimation . . 14
xi
xii Contents
1.8.3 Instancebased Learning . . . . . . . . . . . . . . . . .
1.8.4 Support Vector Machines . . . . . . . . . . . . . . .
1.9 Performance Evaluation . . . . . . . . . . . . . . . . . . . .
1.9.1 Generalization Error . . . . . . . . . . . . . . . . . .
1.9.2 Theoretical Estimation of Generalization Error . . .
1.9.2.1 VC-Framework . . . . . . . . . . . . . . . .
1.9.2.2 PAC-Framework . . . . . . . . . . . . . . . .
1.9.3 Empirical Estimation of Generalization Error . . . .
1.9.4 Bias and Variance Decomposition . . . . . . . . . . .
1.9.5 Computational Complexity . . . . . . . . . . . . . .
1.9.6 Comprehensibility . . . . . . . . . . . . . . . . . . . .
1.10 “No Free Lunch” Theorem . . . . . . . . . . . . . . . . . . .
1.11 Scalability to Large Datasets
1.12 The “Curse of Dimensionality”
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
2 . Decision Trees
2.1 Decision Trees . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Algorithmic Framework for Decision Trees . . . . . . . . . .
2.3 Univariate Splitting Criteria . . . . . . . . . . . . . . . . . .
2.3.2 Impurity Based Criteria . . . . . . . . . . . . . . . .
2.3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.3 Information Gain . . . . . . . . . . . . . . . . . . . .
2.3.4 Gini Index . . . . . . . . . . . . . . . . . . . . . . . .
2.3.5 Likelihood Ratio Chi-Squared Statistics . . . . . . .
2.3.6 DKM Criterion . . . . . . . . . . . . . . . . . . . . .
2.3.7 Normalized Impurity Based Criteria . . . . . . . . .
2.3.8 Gain Ratio . . . . . . . . . . . . . . . . . . . . . . . .
2.3.9 Distance Measure . . . . . . . . . . . . . . . . . . . .
2.3.10 Binary criteria . . . . . . . . . . . . . . . . . . . . . .
2.3.1 1 Twoing Criterion . . . . . . . . . . . . . . . . . . . .
2.3.12 Orthogonal Criterion . . . . . . . . . . . . . . . . . .
2.3.13 Kolmogorov-Smirnov Criterion . . . . . . . . . . . .
2.3.14 AUC Splitting Criteria . . . . . . . . . . . . . . . . .
2.4 Multivariate Splitting Criteria . . . . . . . . . . . . . . . . .
2.5 Stopping Criteria . . . . . . . . . . . . . . . . . . . . . . . .
2.6 Pruning Methods . . . . . . . . . . . . . . . . . . . . . . . .
2.3.15 Other Univariate Splitting Criteria . . . . . . . . . .
2.3.16 Comparison of Univariate Splitting Criteria . . . . .
2.6.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . .

Contents xiii
2.6.2 Cost-Complexity Pruning . . . . . . . . . . . . . . . 46
2.6.3 Reduced Error Pruning . . . . . . . . . . . . . . . . . 46
2.6.4 Minimum Error Pruning (MEP) . . . . . . . . . . . . 47
2.6.5 Pessimistic Pruning . . . . . . . . . . . . . . . . . . . 47
2.6.6 Error-Based Pruning (EBP) . . . . . . . . . . . . . . 48
2.6.7 Optimal Pruning . . . . . . . . . . . . . . . . . . . . 49
2.6.8 Minimum Description Length Pruning . . . . . . . . 49
2.6.9 Other Pruning Methods . . . . . . . . . . . . . . . . . 50
2.6.10 Comparison of Pruning Methods . . . . . . . . . . . 50
2.7 Other Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
2.7.1 Weighting Instances . . . . . . . . . . . . . . . . . . 50
2.7.2 Misclassification costs . . . . . . . . . . . . . . . . . 50
2.7.3 Handling Missing Values . . . . . . . . . . . . . . . . 50
2.8 Decision Trees Inducers . . . . . . . . . . . . . . . . . . . . 52
2.8.1 ID3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.8.2 C4.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.8.3 CART . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.8.4 CHAID . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.8.5 QUEST . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.8.6 Reference to Other Algorithms . . . . . . . . . . . . 54
2.8.7 Advantages and Disadvantages of Decision Trees . . 54
2.8.8 Oblivious Decision Trees . . . . . . . . . . . . . . . . 56
2.8.9 Decision Trees Inducers for Large Datasets . . . . . . 57
2.8.10 Incremental Induction . . . . . . . . . . . . . . . . . 59
3 . Clustering Methods 61
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.2 Distance Measures . . . . . . . . . . . . . . . . . . . . . . . 62
3.2.1 Minkowski: Distance Measures for Numeric
Attributes . . . . . . . . . . . . . . . . . . . . . . . . 62
3.2.2 Distance Measures for Binary Attributes . . . . . . . 63
3.2.3 Distance Measures for Nominal Attributes . . . . . . 64
3.2.4 Distance Metrics for Ordinal Attributes . . . . . . . 64
3.2.5 Distance Metrics for Mixed-Type Attributes . . . . . 64
3.3 Similarity Functions . . . . . . . . . . . . . . . . . . . . . . 65
3.3.1 Cosine Measure . . . . . . . . . . . . . . . . . . . . . 65
3.3.2 Pearson Correlation Measure . . . . . . . . . . . . . 66
3.3.3 Extended Jaccard Measure . . . . . . . . . . . . . . . 66
3.3.4 Dice Coefficient Measure . . . . . . . . . . . . . . . . 66
xiv Contents
3.4 Evaluation Criteria Measures . . . . . . . . . . . . . . . . . 66
3.4.1 Internal Quality Criteria . . . . . . . . . . . . . . . . 66
3.4.1.1 Sum of Squared Error (SSE) . . . . . . . . . 67
3.4.1.2 Other Minimum Variance Criteria . . . . . . 67
3.4.1.3 Scatter Criteria . . . . . . . . . . . . . . . . 68
3.4.1.4 Condorcet’s Criterion . . . . . . . . . . . . . . 69
3.4.1.5 The C-Criterion . . . . . . . . . . . . . . . . 70
3.4.1.6 Category Utility Metric . . . . . . . . . . . . 70
3.4.1.7 Edge Cut Metrics . . . . . . . . . . . . . . .
3.4.2 External Quality Criteria . . . . . . . . . . . . . . . 70
3.4.2.1 Mutual Information Based Measure . . . . . 71
3.4.2.2 Precision-Recall Measure . . . . . . . . . . 71
3.4.2.3 Rand Index . . . . . . . . . . . . . . . . . . 71
3.5 Clustering Methods . . . . . . . . . . . . . . . . . . . . . . . 72
3.5.1 Hierarchical Methods . . . . . . . . . . . . . . . . . . 72
3.5.2.1 Error Minimization Algorithms . . . . . . . 75
3.5.3 Density Based Methods . . . . . . . . . . . . . . . . 78
3.5.4 Model Based Clustering . . . . . . . . . . . . . . . . 80
3.5.4.1 Decision Trees . . . . . . . . . . . . . . . . . 80
3.5.4.2 Neural Networks . . . . . . . . . . . . . . . 80
3.5.5 Grid-Based Methods . . . . . . . . . . . . . . . . . . 81
3.5.6 Fuzzy Clustering . . . . . . . . . . . . . . . . . . . . 81
3.5.7 Evolutionary Approaches for Clustering . . . . . . . 81
3.5.8 Simulated Annealing for Clustering . . . . . . . . . . 84
3.5.9 Which Technique to Use? . . . . . . . . . . . . . . . 84
3.6 Clustering Large Data Sets . . . . . . . . . . . . . . . . . . 86
3.6.1 Decomposition Approach . . . . . . . . . . . . . . . . 88
3.6.2 Incremental Clustering . . . . . . . . . . . . . . . . . 88
3.6.3 Parallel Implementation . . . . . . . . . . . . . . . . 90
3.7 Determining the Number of Clusters . . . . . . . . . . . . . 90
70
3.5.2 Partitioning Methods . . . . . . . . . . . . . . . . . 75
3.5.2.2 Graph-Theoretic Clustering . . . . . . . . . 77
3.7.1 Methods Based on Intra Cluster Scatter . . . . . . . 91
3.7.2 Methods Based on Both the Inter and Intra Cluster
Scatter . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.7.3 Criteria Based on Probabilistic . . . . . . . . . . . . 94
4 . Ensemble Methods 95
4.1 Multiple Classifiers . . . . . . . . . . . . . . . . . . . . . . . 95
Contents xv
4.2 Ensemble Methodology . . . . . . . . . . . . . . . . . . . . . 96
4.3 Sequential Methodology . . . . . . . . . . . . . . . . . . . . 97
4.3.1 Model Guided Instance Selection . . . . . . . . . . . 98
4.3.1.1 Uncertainty Sampling . . . . . . . . . . . . . 99
4.3.1.2 Boosting . . . . . . . . . . . . . . . . . . . . 100
4.3.1.3 Windowing . . . . . . . . . . . . . . . . . . . 103
4.3.2 Incremental Batch Learning . . . . . . . . . . . . . . 105
4.4 Concurrent Methodology . . . . . . . . . . . . . . . . . . . . 105
4.4.0.1 Bagging . . . . . . . . . . . . . . . . . . . . 106
4.4.0.2 Cross-validated Committees . . . . . . . . . 108
4.5 Combining Classifiers . . . . . . . . . . . . . . . . . . . . . 108
4.5.1 Simple Combining Methods . . . . . . . . . . . . . . 108
4.5.1.1 Uniform Voting . . . . . . . . . . . . . . . . 108
4.5.1.2 Distribution Summation . . . . . . . . . . . 109
4.5.1.3 Bayesian Combination . . . . . . . . . . . . 109
4.5.1.4 Dempster-Shafer . . . . . . . . . . . . . . . 109
4.5.1.5 NaiveBayes . . . . . . . . . . . . . . . . . . 110
4.5.1.6 Entropy Weighting . . . . . . . . . . . . . . 110
4.5.1.7 Density Based Weighting . . . . . . . . . . 110
4.5.1.8 DEA Weighting Method . . . . . . . . . . . 111
4.5.1.9 Logarithmic Opinion Pool . . . . . . . . . . 111
4.5.1.10 Order Statistics . . . . . . . . . . . . . . . . 111
4.5.2.1 Stacking . . . . . . . . . . . . . . . . . . . . 111
4.5.2.2 Arbiter Trees . . . . . . . . . . . . . . . . . 112
4.5.2.3 Combiner Trees . . . . . . . . . . . . . . . . 115
4.5.2.4 Grading . . . . . . . . . . . . . . . . . . . . 115
4.6 Ensemble Size . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.6.1 Selecting the Ensemble Size . . . . . . . . . . . . . . 116
4.6.2 Pruning Ensembles . . . . . . . . . . . . . . . . . . . 117
4.7 Ensemble Diversity . . . . . . . . . . . . . . . . . . . . . . . 118
4.7.1 Manipulating the Inducer . . . . . . . . . . . . . . . 118
4.7.2 Manipulating the Training Set . . . . . . . . . . . . . 119
4.7.2.1 Manipulating the Tuples . . . . . . . . . . . 119
4.7.2.2 Manipulating the Input Feature Set . . . . . 119
4.7.2.3 Manipulating the Target Attribute . . . . . 121
4.7.3 Measuring the Diversity . . . . . . . . . . . . . . . . 121
4.5.2 Meta Combining Methods . . . . . . . . . . . . . . . 111
...................................................................

...................................................................
..................................................................