Pattern Recognition (eBook)

Cover 1
CONTENTS 6
Preface 14
Chapter 1. INTRODUCTION 16
1.1 Is Pattern Recognition Important? 16
1.2 Features, Feature Vectors, and Classifiers 18
1.3 Supervised Versus Unsupervised Pattern Recognition 21
1.4 Outline of the Book 23
Chapter 2. CLASSIFIERS BASED ON BAYES DECISION THEORY 28
2.1 Introduction 28
2.2 Bayes Decision Theory 28
2.3 Discriminant Functions and Decision Surfaces 34
2.4 Bayesian Classification for Normal Distributions 35
2.5 Estimation of Unknown Probability Density Functions 42
2.6 The Nearest Neighbor Rule 59
Chapter 3. LINEAR CLASSIFIERS 70
3.1 Introduction 70
3.2 Linear Discriminant Functions and Decision Hyperplanes 70
3.3 The Perceptron Algorithm 72
3.4 Least Squares Methods 80
3.5 Mean Square Estimation Revisited 87
3.6 Support Vector Machines 92
Chapter 4. NONLINEAR CLASSIFIERS 108
4.1 Introduction 108
4.2 The XOR Problem 108
4.3 The Two-Layer Perceptron 109
4.4 Three-Layer Perceptrons 116
4.5 Algorithms Based on Exact Classification of the Training Set 117
4.6 The Backpropagation Algorithm 119
4.7 Variations on the Backpropagation Theme 127
4.8 The Cost Function Choice 130
4.9 Choice of the Network Size 133
4.10 A Simulation Example 139
4.11 NetworksWithWeight Sharing 141
4.12 Generalized Linear Classifiers 142
4.13 Capacity of the l-Dimensional Space in Linear Dichotomies 144
4.14 Polynomial Classifiers 146
4.15 Radial Basis Function Networks 148
4.16 Universal Approximators 152
4.17 Support Vector Machines: The Nonlinear Case 154
4.18 Decision Trees 158
4.19 Discussion 165
Chapter 5. FEATURE SELECTION 178
5.1 Introduction 178
5.2 Preprocessing 179
5.3 Feature Selection Based on Statistical Hypothesis Testing 181
5.4 The Receiver Operating Characteristics CROC Curve 188
5.5 Class Separability Measures 189
5.6 Feature Subset Selection 196
5.7 Optimal Feature Generation 202
5.8 Neural Networks and Feature Generation/Selection 206
5.9 A Hint on the Vapnik–Chernovenkis Learning Theory 208
Chapter 6. FEATURE GENERATION I: LINEAR TRANSFORMS 222
6.1 Introduction 222
6.2 Basis Vectors and Images 223
6.3 The Karhunen–Loève Transform 225
6.4 The Singular Value Decomposition 230
6.5 Independent Component Analysis 234
6.6 The Discrete Fourier Transform (DFT) 241
6.7 The Discrete Cosine and Sine Transforms 245
6.8 The Hadamard Transform 246
6.9 The Haar Transform 248
6.10 The Haar Expansion Revisited 250
6.11 Discrete TimeWavelet Transform (DTWT) 254
6.12 The Multiresolution Interpretation 264
6.13 Wavelet Packets 267
6.14 A Look at Two-Dimensional Generalizations 267
6.15 Applications 270
Chapter 7. FEATURE GENERATION II 284
7.1 Introduction 284
7.2 Regional Features 285
7.3 Features for Shape and Size Characterization 309
7.4 A Glimpse at Fractals 318
Chapter 8. TEMPLATE MATCHING 336
8.1 Introduction 336
8.2 Measures Based on Optimal Path Searching Techniques 337
8.3 Measures Based on Correlations 352
8.4 Deformable Template Models 358
Chapter 8. TEMPLATE MATCHING 336
8.1 Introduction 336
8.2 Measures based on optimal path searching techniques 337
8.3 Measures based on correlations 352
8.4 Deformable template models 358
Chapter 9. CONTEXT-DEPENDENT CLASSIFICATION 366
9.1 Introduction 366
9.2 The Bayes Classifier 366
9.3 Markov Chain Models 367
9.4 The Viterbi Algorithm 368
9.5 Channel Equalization 371
9.6 Hidden Markov Models 376
9.7 Training Markov Models via Neural Networks 388
9.8 A discussion of Markov Random Fields 390
Chapter 10. SYSTEM EVALUATION 400
10.1 Introduction 400
10.2 Error Counting Approach 400
10.3 Exploiting the Finite Size of the Data Set 402
10.4 A Case Study From Medical Imaging 405
Chapter 11. CLUSTERING: BASIC CONCEPTS 412
11.1 Introduction 412
11.2 Proximity Measures 419
Chapter 12. CLUSTERING ALGORITHMS I: SEQUENTIAL ALGORITHMS 444
12.1 Introduction 444
12.2 Categories of Clustering Algorithms 446
12.3 Sequential Clustering Algorithms 448
12.4 A Modification of BSAS 452
12.5 ATwo-Threshold Sequential Scheme 453
12.6 Refinement Stages 456
12.7 Neural Network Implementation 458
Chapter 13. CLUSTERING ALGORITHMS II: HIERARCHICAL ALGORITHMS 464
13.1 Introduction 464
13.2 Agglomerative Algorithms 465
13.3 The Cophenetic Matrix 491
13.4 Divisive Algorithms 493
13.5 Choice of the Best Number of Clusters 495
Chapter 14. CLUSTERING ALGORITHMS III: SCHEMES BASED ON FUNCTION OPTIMIZATION 504
14.1 Introduction 504
14.2 Mixture Decomposition Schemes 506
14.3 Fuzzy Clustering Algorithms 515
14.4 Possibilistic Clustering 537
14.5 Hard Clustering Algorithms 544
14.6 Vector Quantization 548
Chapter 15. CLUSTERING ALGORITHMS IV 560
15.1 Introduction 560
15.2 Clustering Algorithms Based on Graph Theory 560
15.3 Competitive Learning Algorithms 567
15.4 Branch and Bound Clustering Algorithms 576
15.5 Binary Morphology Clustering Algorithms (BMCAs) 579
15.6 Boundary Detection Algorithms 588
15.7 Valley-Seeking Clustering Algorithms 591
15.8 Clustering Via Cost Optimization (Revisited) 593
15.9 Clustering Using Genetic Algorithms 597
15.10 Other Clustering Algorithms 598
Chapter 16. CLUSTER VALIDITY 606
16.1 Introduction 606
16.2 Hypothesis Testing Revisited 607
16.3 Hypothesis Testing in Cluster Validity 609
16.4 Relative Criteria 620
16.5 Validity of Individual Clusters 636
16.6 Clustering Tendency 639
Appendix A: Hints from Probability and Statistics 658
Appendix B: Linear Algebra Basics 670
Appendix C: Cost Function Optimization 674
Appendix D: Basic Definitions from Linear Systems Theory 692
Index 696