This is the first comprehensive book dedicated entirely to the field of decision trees in data mining and covers all aspects of this important technique. Decision trees have become one of the most powerful and popular approaches in knowledge discovery and data mining, the science and technology of exploring large and complex bodies of data in order to discover useful patterns. The area is of great importance because it enables modeling and knowledge extraction from the abundance of data available. Both theoreticians and practitioners are continually seeking techniques to make the process more efficient, cost-effective and accurate. Decision trees, originally implemented in decision theory and statistics, are highly effective tools in other areas such as data mining, text mining, information extraction, machine learning, and pattern recognition.This book invites readers to explore the many benefits in data mining that decision trees offer: self-explanatory and easy to follow when compacted; able to handle a variety of input data: nominal, numeric and textual; able to process datasets that may have errors or missing values; high predictive performance for a relatively small computational effort; available in many data mining packages over a variety of platforms; and, useful for various tasks, such as classification, regression, clustering and feature selection.
Author(s): Lior Rokach, Oded Maimon
Series: Series in Machine Perception and Artificial Intelligence
Publisher: World Scientific Publishing Company
Year: 2008
Language: English
Pages: 244
Tags: Информатика и вычислительная техника;Искусственный интеллект;Интеллектуальный анализ данных;
Contents......Page 12
Preface......Page 8
1.1 Data Mining and Knowledge Discovery......Page 20
1.2 Taxonomy of Data Mining Methods......Page 22
1.3.1 Overview......Page 23
1.4 Classification Trees......Page 24
1.5 Characteristics of Classification Trees......Page 27
1.5.2 The hierarchical nature of decision trees......Page 28
1.6 Relation to Rule Induction......Page 30
2.0.1 Training Set......Page 32
2.0.2 Definition of the Classification Problem......Page 33
2.0.4 Probability Estimation in Decision Trees......Page 35
2.0.4.1 Laplace Correction......Page 36
2.1 Algorithmic Framework for Decision Trees......Page 37
2.2 Stopping Criteria......Page 38
3.2 Generalization Error......Page 40
3.2.1 Theoretical Estimation of Generalization Error......Page 41
3.2.2 Empirical Estimation of Generalization Error......Page 42
3.2.3 Alternatives to the Accuracy Measure......Page 43
3.2.4 The F-Measure......Page 44
3.2.5 Confusion Matrix......Page 46
3.2.6 Classifier Evaluation under Limited Resources......Page 47
3.2.6.2 Hit Rate Curve......Page 49
3.2.6.5 Pearson Correlation Coegfficient......Page 51
3.2.6.6 Area Under Curve (AUC)......Page 53
3.2.6.8 Average Qrecall......Page 54
3.2.6.9 Potential Extract Measure (PEM)......Page 55
3.2.7.1 McNemar’s Test......Page 59
3.2.7.2 A Test for the Difference of Two Proportions......Page 60
3.2.7.4 The k-fold Cross-validated Paired t Test......Page 62
3.4 Comprehensibility......Page 63
3.5 Scalability to Large Datasets......Page 64
3.7 Stability......Page 66
3.8 Interestingness Measures......Page 67
3.9 Overfitting and Underfitting......Page 68
3.10 “No Free Lunch” Theorem......Page 69
4.1.2 Impurity based Criteria......Page 72
4.1.3 Information Gain......Page 73
4.1.6 DKM Criterion......Page 74
4.1.9 Distance Measure......Page 75
4.1.11 Twoing Criterion......Page 76
4.1.14 AUC Splitting Criteria......Page 77
4.2 Handling Missing Values......Page 78
5.2.1 Overview......Page 82
5.2.2 Cost Complexity Pruning......Page 83
5.2.5 Pessimistic Pruning......Page 84
5.2.6 Error-Based Pruning (EBP)......Page 85
5.2.8 Other Pruning Methods......Page 86
5.3 Optimal Pruning......Page 87
6.1.3 CART......Page 90
6.1.4 CHAID......Page 91
6.1.7 Advantages and Disadvantages of Decision Trees......Page 92
6.1.8 Oblivious Decision Trees......Page 95
6.1.9 Decision Trees Inducers for Large Datasets......Page 97
6.1.11 Lazy Tree......Page 98
6.1.12 Option Tree......Page 99
6.2 Lookahead......Page 101
6.3 Oblique Decision Trees......Page 102
7.2 Introduction......Page 106
7.3.1.1 Majority Voting......Page 109
7.3.1.4 Bayesian Combination......Page 110
7.3.1.6 Vogging......Page 111
7.3.1.10 DEA Weighting Method......Page 112
7.3.1.12 Gating Network......Page 113
7.3.2.1 Stacking......Page 114
7.3.2.2 Arbiter Trees......Page 116
7.3.2.3 Combiner Trees......Page 118
7.3.2.4 Grading......Page 119
7.4.1.1 Model-guided Instance Selection......Page 120
7.4.2.1 Bagging......Page 124
7.4.2.2 Wagging......Page 126
7.4.2.3 Random Forest......Page 127
7.5 Ensemble Diversity......Page 128
7.5.1 Manipulating the Inducer......Page 129
7.5.1.3 Hypothesis Space Traversal......Page 130
7.5.2.1 Resampling......Page 131
7.5.2.3 Partitioning......Page 132
7.5.3 Manipulating the Target Attribute Representation......Page 133
7.5.4 Partitioning the Search Space......Page 134
7.5.4.1 Divide and Conquer......Page 135
7.5.4.2 Feature Subset-based Ensemble Methods......Page 136
7.5.5 Multi-Inducers......Page 140
7.5.6 Measuring the Diversity......Page 141
7.6.2 Pre Selection of the Ensemble Size......Page 143
7.6.4 Pruning — Post Selection of the Ensemble Size......Page 144
7.6.4.2 Post-combining Pruning......Page 145
7.8 Multistrategy Ensemble Learning......Page 146
7.10 Open Source for Decision Trees Forests......Page 147
8.2 The Motives for Incremental Learning......Page 150
8.3 The Inefficiency Challenge......Page 151
8.4 The Concept Drift Challenge......Page 152
9.2 The “Curse of Dimensionality”......Page 156
9.3 Techniques for Feature Selection......Page 159
9.3.1.3 Using One Learning Algorithm as a Filter for Another......Page 160
9.3.1.6 Simba and G-flip......Page 161
9.3.2.1 Mallows Cp......Page 162
9.3.2.3 Principal Component Analysis (PCA)......Page 163
9.3.3.1 Wrappers for Decision Tree Learners......Page 164
9.4 Feature Selection as a Means of Creating Ensembles......Page 165
9.5 Ensemble Methodology as a Means for Improving Feature Selection......Page 166
9.5.1 Independent Algorithmic Framework......Page 168
9.5.2 Combining Procedure......Page 169
9.5.2.1 Simple Weighted Voting......Page 170
9.5.2.2 Naïve Bayes Weighting using Arti.cial
Contrasts......Page 171
9.5.3.1 Multiple Feature Selectors......Page 173
9.6 Using Decision Trees for Feature Selection......Page 175
9.7 Limitation of Feature Selection Methods......Page 176
10.1 Overview......Page 178
10.2 Membership Function......Page 179
10.3 Fuzzy Classification Problems......Page 180
10.4 Fuzzy Set Operations......Page 182
10.6 Creating Fuzzy Decision Tree......Page 183
10.6.1 Fuzzifying Numeric Attributes......Page 184
10.6.2 Inducing of Fuzzy Decision Tree......Page 185
10.9 Other Fuzzy Decision Tree Inducers......Page 188
11.2 A Decision Tree Framework for Instance-Space Decomposition......Page 190
11.2.1 Stopping Rules......Page 193
11.2.3 Split Validation Examinations......Page 194
11.3.1 CPOM Outline......Page 195
11.3.2 The Grouped Gain Ratio Splitting Rule......Page 196
11.4 Induction of Decision Trees by an Evolutionary Algorithm......Page 198
12.2 Sequence Representation......Page 206
12.3 Pattern Discovery......Page 207
12.4.1 Heuristics for Pattern Selection......Page 209
12.5 Classifier Training......Page 210
12.5.2 Cascading Decision Trees......Page 211
12.6 Application of CREDT in Improving of Information Retrieval ofMedical Narrative Reports......Page 212
12.6.1.1 Text Classification......Page 214
12.6.1.3 Frameworks for Information Extraction......Page 217
12.6.1.5 Identifying Negative Context in Nondomain Specific Text (General NLP)......Page 218
12.6.1.7 Works Based on Knowledge Engineering......Page 219
12.6.2.2 Step 1: Corpus Preparation......Page 220
12.6.2.4 Step 1.2: Sentence Boundaries......Page 221
12.6.2.6 Step 2: Patterns Creation......Page 222
12.6.2.7 Step 3: Patterns Selection......Page 225
12.6.2.8 Step 4: Classi.er Training......Page 227
12.6.2.9 Cascade of Three Classifiers......Page 228
Bibliography......Page 234
Index......Page 262
