Combining pattern classifiers: methods and algorithms

Combined classifiers, which are central to the ubiquitous performance of pattern recognition and machine learning, are generally considered more accurate than single classifiers. In a didactic, detailed assessment, Combining Pattern Classifiers examines the basic theories and tactics of classifier combination while presenting the most recent research in the field. Among the pattern recognition tasks that this book explores are mail sorting, face recognition, signature verification, decoding brain fMRI images, identifying emotions, analyzing gene microarray data, and spotting patterns in consumer preference. This updated second edition is equipped with the latest knowledge for academics, students, and practitioners involved in pattern recognition fields"

Classifier Combination is a field of growing interest within the very large area of Pattern Classification"

Includes index

Preface xv Acknowledgements xxi 1 Fundamentals of Pattern Recognition 1 1.1 Basic Concepts: Class Feature Data Set 1 1.1.1 Classes and Class Labels 1 1.1.2 Features 2 1.1.3 Data Set 3 1.1.4 Generate Your Own Data 6 1.2 Classifier Discriminant Functions Classification Regions 9 1.3 Classification Error and Classification Accuracy 11 1.3.1 Where Does the Error Come From? Bias and Variance 11 1.3.2 Estimation of the Error 13 1.3.3 Confusion Matrices and Loss Matrices 14 1.3.4 Training and Testing Protocols 15 1.3.5 Overtraining and Peeking 17 1.4 Experimental Comparison of Classifiers 19 1.4.1 Two Trained Classifiers and a Fixed Testing Set 20 1.4.2 Two Classifier Models and a Single Data Set 22 1.4.3 Two Classifier Models and Multiple Data Sets 26 1.4.4 Multiple Classifier Models and Multiple Data Sets 27 1.5 Bayes Decision Theory 30 1.5.1 Probabilistic Framework 301.5.2 Discriminant Functions and Decision Boundaries 31 1.5.3 Bayes Error 33 1.6 Clustering and Feature Selection 35 1.6.1 Clustering 35 1.6.2 Feature Selection 37 1.7 Challenges of Real-Life Data 40 Appendix 41 1.A.1 Data Generation 41 1.A.2 Comparison of Classifiers 42 1.A.2.1 MATLAB Functions for Comparing Classifiers 42 1.A.2.2 Critical Values for Wilcoxon and Sign Test 45 1.A.3 Feature Selection 47 2 Base Classifiers 49 2.1 Linear and Quadratic Classifiers 49 2.1.1 Linear Discriminant Classifier 49 2.1.2 Nearest Mean Classifier 52 2.1.3 Quadratic Discriminant Classifier 52 2.1.4 Stability of LDC and QDC 53 2.2 Decision Tree Classifiers 55 2.2.1 Basics and Terminology 55 2.2.2 Training of Decision Tree Classifiers 57 2.2.3 Selection of the Feature for a Node 58 2.2.4 Stopping Criterion 60 2.2.5 Pruning of the Decision Tree 63 2.2.6 C4.5 and ID3 64 2.2.7 Instability of Decision Trees 64 2.2.8 Random Trees 65 2.3 The Na¨yve Bayes Classifier 66 2.4 Neural Networks 68 2.4.1 Neurons 68 2.4.2 Rosenblatt's Perceptron 70 2.4.3 Multi-Layer Perceptron 71

2.5 Support Vector Machines 73 2.5.1 Why Would It Work? 73 2.5.2 Classification Margins 74 2.5.3 Optimal Linear Boundary 76 2.5.4 Parameters and Classification Boundaries of SVM 78 2.6 The k-Nearest Neighbor Classifier (k-nn) 80 2.7 Final Remarks 82 2.7.1 Simple or Complex Models? 82 2.7.2 The Triangle Diagram 83 2.7.3 Choosing a Base Classifier for Ensembles 85 Appendix 85 2.A.1 MATLAB Code for the Fish Data 85 2.A.2 MATLAB Code for Individual Classifiers 86 2.A.2.1 Decision Tree 86 2.A.2.2 Na¨yve Bayes 89 2.A.2.3 Multi-Layer Perceptron 90 2.A.2.4 1-nn Classifier 92 3 An Overview of the Field 94 3.1 Philosophy 94 3.2 Two Examples 98 3.2.1 The Wisdom of the "Classifier Crowd" 98 3.2.2 The Power of Divide-and-Conquer 98 3.3 Structure of the Area 100 3.3.1 Terminology 100 3.3.2 A Taxonomy of Classifier Ensemble Methods 100 3.3.3 Classifier Fusion and Classifier Selection 104 3.4 Quo Vadis? 105 3.4.1 Reinventing the Wheel? 105 3.4.2 The Illusion of Progress? 106 3.4.3 A Bibliometric Snapshot 107 4 Combining Label Outputs 111 4.1 Types of Classifier Outputs 111 4.2 A Probabilistic Framework for Combining Label Outputs 112 4.3 Majority Vote 113 4.3.1 "Democracy" in Classifier Combination 113 4.3.2 Accuracy of the Majority Vote 114 4.3.3 Limits on the Majority Vote Accuracy: An Example 117 4.3.4 Patterns of Success and Failure 119 4.3.5 Optimality of the Majority Vote Combiner 124 4.4 Weighted Majority Vote 125 4.4.1 Two Examples 126 4.4.2 Optimality of the Weighted Majority Vote Combiner 127 4.5 Na¨yve-Bayes Combiner 128 4.5.1 Optimality of the Na¨yve Bayes Combiner 128 4.5.2 Implementation of the NB Combiner 130 4.6 Multinomial Methods 132 4.7 Comparison of Combination Methods for Label Outputs 135 Appendix 137 4.A.1 Matan's Proof for the Limits on the Majority Vote Accuracy 137 4.A.2 Selected MATLAB Code 139 5 Combining Continuous-Valued Outputs 143 5.1 Decision Profile 143 5.2 How Do We Get Probability Outputs? 144 5