Orient BlackSwan

About the BookAbout the AuthorTable of Contents

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