Observing the environment and recognising patterns for the purpose of decision making is fundamental to human nature. This book deals with the scientific discipline that enables similar perception in machines through pattern recognition, which has application in diverse technology areas—character recognition, image processing, industrial automation, internet searches, speech recognition, medical diagnostics, target recognition, space science, remote sensing, data mining, biometric identification—to name a few. This book is an exposition of principal topics in pattern recognition using an algorithmic approach. It provides a thorough introduction to the concepts of pattern recognition and a systematic account of the major topics in pattern recognition besides reviewing the vast progress made in the field in recent times. It includes basic techniques of pattern recognition, neural networks, support vector machines and decision trees. While theoretical aspects have been given due coverage, the emphasis is more on the practical. The book is replete with examples and illustrations and includes chapter-end exercises.
Dr. V. Susheela Devi and Professor M. Narasimha Murty are from the Department of Computer Science and Automation, Indian Institute of Science, Bangalore.
1. Introduction 1.1 What is Pattern Recognition? 1.2 Data Sets for Pattern Recognition 1.3 Different Paradigms for Pattern Recognition Discussion Further Reading Exercises Bibliography 2. Representation 2.1 Data Structures for Pattern Representation 2.1.1 Patterns as Vectors 2.1.2 Patterns as Strings 2.1.3 Logical Descriptions 2.1.4 Fuzzy and Rough Pattern Sets 2.1.5 Patterns as Trees and Graphs 2.2 Representation of Clusters 2.3 Proximity Measures 2.3.1 Distance Measure 2.3.2 Weighted Distance Measure 2.3.3 Non-Metric Similarity Function 2.3.4 Edit Distance 2.3.5 Mutual Neighbourhood Distance (MND) 2.3.6 Conceptual Cohesiveness 2.3.7 Kernel Functions 2.4 Size of Patterns 2.4.1 Normalisation of Data 2.4.2 Use of Appropriate Similarity Measures 2.5 Abstractions of the Data Set 2.6 Feature Extraction 2.6.1 Fisher’s Linear Discriminant 2.6.2 Principal Component Analysis (PCA) 2.7 Feature Selection 2.7.1 Exhaustive Search 2.7.2 Branch and Bound Search 2.7.3 Selection of Best Individual Features 2.7.4 Sequential Selection 2.7.5 Sequential Floating Search 2.7.6 Max–Min approach to Feature Selection 2.7.7 Stochastic Search Techniques 2.7.8 Artificial Neural Networks 2.8 Evaluation of Classifiers 2.9 Evaluation of Clustering Discussion Further Reading Exercises Computer Exercises Bibliography 3. Nearest Neighbour Based Classifiers 3.1 Nearest Neighbour Algorithm 3.2 Variants of the NN Algorithm 3.2.1 k Nearest Neighbour (kNN) Algorithm 3.2.2 Modified k Nearest Neighbour (MkNN) Algorithm 3.2.3 Fuzzy kNN Algorithm 3.2.4 r Near Neighbours 3.3 Use of the Nearest Neighbour Algorithm for Transaction Databases 3.4 Efficient Algorithms 3.4.1 The Branch and Bound Algorithm 3.4.2 The Cube Algorithm 3.4.3 Searching for the Nearest Neighbour by Projection 3.4.4 Ordered Partitions 3.4.5 Incremental Nearest Neighbour Search 3.5 Data Reduction 3.6 Prototype Selection 3.6.1 Minimal Distance Classifier (MDC) 3.6.2 Condensation Algorithms 3.6.3 Editing Algorithms 3.6.4 Clustering methods 3.6.5 Other Methods Discussion Further Reading Exercises Computer Exercises Bibliography 4.Bayes Classifier 4.1 Bayes Theorem 4.2 Minimum error rate classifier 4.3 Estimation of Probabilities 4.4 Comparison with the NNC 4.5 Naive Bayes Classifier 4.5.1 Classification using Naive Bayes Classifier 4.5.2 The naive Bayes probabilistic model 4.5.3 Parameter estimation 4.5.4 Constructing a classifier from the probability model 4.6 Bayesian Belief Network Discussion Further Reading Exercises Computer Exercises Bibliography 5. Hidden Markov Models 5.1 Markov Models for Classification 5.2 Hidden Markov Models 5.2.1 HMM Parameters 5.2.2 Learning HMMs 5.3 Classification Using HMMs 5.3.1 Classification of Test Patterns Discussion Further Reading Exercises Computer Exercises Bibliography 6. Decision Trees 6.1 Introduction 6.2 Decision Trees for Pattern Classification 6.3 Construction of Decision Trees 6.3.1 Measures of Impurity 6.3.2 Which Attribute to Choose? 6.4 Splitting at the Nodes 6.4.1 When to Stop Splitting 6.5 Overfitting and Pruning 6.5.1 Pruning by Finding Irrelevant Attributes 6.5.2 Use of Cross-Validation 6.6 Example of Decision Tree Induction Discussion Further Reading Exercises Computer Exercises Bibliography 7. Support Vector Machines 7.1 Introduction 7.1.1 Linear Discriminant Functions 7.2 Learning the Linear Discriminant Function 7.2.1 Learning the Weight Vector 7.2.2 Multi-class Problems 7.2.3 Generality of Linear Discriminants 7.3 Neural Networks 7.3.1 Artificial Neuron 7.3.2 Feed-forward Network 7.3.3 Multi-layer Perceptron 7.4 SVM for Classification 7.4.1 Linearly Separable Case 7.4.2 Non-linearly Separable Case Discussion Further Reading Exercises Computer Exercises Bibliography 8. Combination of Classifiers 8.1 Introduction 8.2 Methods for Constructing Ensembles of Classifiers 8.2.1 Sub-sampling the Training Examples 8.2.2 Manipulating the Input Features 8.2.3 Manipulating the Output Targets 8.2.4 Injecting Randomness 8.3 Methods for Combining Classifiers 8.4 Evaluation of Classifiers 8.5 Evaluation of Clustering Discussion Further Reading Exercises Computer Exercises Bibliography 9. Clustering 9.1 Why is Clustering Important? 9.2 Hierarchical Algorithms 9.2.1 Divisive Clustering 9.2.2 Agglomerative Clustering 9.3 Partitional Clustering 9.3.1 K-Means Algorithm 9.3.2 Soft Partitioning 9.4 Clustering Large Data Sets 9.4.1 Possible Solutions 9.4.2 Incremental Clustering 9.4.3 Divide-and-Conquer Approach Discussion Further Reading Exercises Computer Exercises Bibliography 10 Summary 11. An Application: Handwritten Digit Recognition 11.1 Description of the Digit Data 11.2 Pre-processing of Data 11.3 Classification Algorithms 11.4 Selection of Representative Patterns 11.5 Results Discussion Further Reading Bibliography