Pattern Recognition

by Theodoridis, Sergios; Koutroumbas, Konstantinos

• ISBN13: 9780126858754
• ISBN10: 0126858756
• Edition: 2nd
• Format: Hardcover
• Copyright: 2003-03-01
• Publisher: Academic Pr

Summary

*Approaches pattern recognition from the designer's point of view*New edition highlights latest developments in this growing field, including independent components and support vector machines, not available elsewhere*Supplemented by computer examples selected from applications of interestPattern recognition is a scientific discipline that is becoming increasingly important in the age of automation and information handling and retrieval. This volume's unifying treatment covers the entire spectrum of pattern recognition applications, from image analysis to speech recognition and communications. This book presents cutting-edge material on neural networks, - a set of linked microprocessors that can form associations and uses pattern recognition to "learn". A direct result of more than 10 years of teaching experience, the text was developed by the authors through use in their own classrooms.

Table of Contents

Preface	xiii
Introduction	1	(12)
Is Pattern Recognition Important?	1	(2)
Features, Feature Vectors, and Classifiers	3	(3)
Supervised Versus Unsupervised Pattern Recognition	6	(2)
Outline of the Book	8	(5)
Classifiers Based On Bayes Decision Theory	13	(42)
Introduction	13	(1)
Bayes Decision Theory	13	(6)
Discriminant Functions and Decision Surfaces	19	(1)
Bayesian Classification for Normal Distributions	20	(7)
Estimation of Unknown Probability Density Functions	27	(17)
Maximum Likelihood Parameter Estimation	28	(3)
Maximum a Posteriori Probability Estimation	31	(1)
Bayesian Inference	32	(2)
Maximum Entropy Estimation	34	(1)
Mixture Models	35	(4)
Nonparametric Estimation	39	(5)
The Nearest Neighbor Rule	44	(11)
Linear Classifiers	55	(38)
Introduction	55	(1)
Linear Discriminant Functions and Decision Hyperplanes	55	(2)
The Perceptron Algorithm	57	(8)
Least Squares Methods	65	(7)
Mean Square Error Estimation	65	(3)
Stochastic Approximation and the LMS Algorithm	68	(2)
Sum of Error Squares Estimation	70	(2)
Mean Square Estimation Revisited	72	(5)
Mean Square Error Regression	72	(1)
MSE Estimates Posterior Class Probabilities	73	(3)
The Bias-Variance Dilemma	76	(1)
Support Vector Machines	77	(16)
Separable Classes	77	(5)
Nonseparable Classes	82	(11)
Nonlinear Classifiers	93	(70)
Introduction	93	(1)
The XOR Problem	93	(1)
The Two-Layer Perceptron	94	(7)
Classification Capabilities of the Two-Layer Perceptron	98	(3)
Three-Layer Perceptrons	101	(1)
Algorithms Based on Exact Classification of the Training Set	102	(2)
The Backpropagation Algorithm	104	(8)
Variations on the Backpropagation Theme	112	(3)
The Cost Function Choice	115	(3)
Choice of the Network Size	118	(6)
A Simulation Example	124	(2)
Networks With Weight Sharing	126	(1)
Generalized Linear Classifiers	127	(2)
Capacity of the l-Dimensional Space in Linear Dichotomies	129	(2)
Polynomial Classifiers	131	(2)
Radial Basis Function Networks	133	(4)
Universal Approximators	137	(2)
Support Vector Machines: The Nonlinear Case	139	(4)
Decision Trees	143	(7)
Set of Questions	146	(1)
Splitting Criterion	146	(1)
Stop-Splitting Rule	147	(1)
Class Assignment Rule	147	(3)
Discussion	150	(13)
Feature Selection	163	(44)
Introduction	163	(1)
Preprocessing	164	(1)
Outlier Removal	164	(1)
Data Normalization	165	(1)
Missing Data	165	(1)
Feature Selection Based on Statistical Hypothesis Testing	165	(8)
Hypothesis Testing Basics	166	(5)
Application of the t-Test in Feature Selection	171	(2)
The Receiver Operating Characteristics CROC Curve	173	(1)
Class Separability Measures	174	(7)
Divergence	174	(3)
Chernoff Bound and Bhattacharyya Distance	177	(2)
Scatter Matrices	179	(2)
Feature Subset Selection	181	(6)
Scalar Feature Selection	182	(1)
Feature Vector Selection	183	(4)
Optimal Feature Generation	187	(4)
Neural Networks and Feature Generation/Selection	191	(2)
A Hint on the Vapnik--Chernovenkis Learning Theory	193	(14)
Feature Generation I: Linear Transforms	207	(62)
Introduction	207	(1)
Basis Vectors and Images	208	(2)
The Karhunen--Loeve Transform	210	(5)
The Singular Value Decomposition	215	(4)
Independent Component Analysis	219	(7)
ICA Based on Second- and Fourth-Order Cumulants	221	(1)
ICA Based on Mutual Information	222	(4)
An ICA Simulation Example	226	(1)
The Discrete Fourier Transform (DFT)	226	(4)
One-Dimensional DFT	227	(2)
Two-Dimensional DFT	229	(1)
The Discrete Cosine and Sine Transforms	230	(1)
The Hadamard Transform	231	(2)
The Haar Transform	233	(2)
The Haar Expansion Revisited	235	(4)
Discrete Time Wavelet Transform (DTWT)	239	(10)
The Multiresolution Interpretation	249	(3)
Wavelet Packets	252	(1)
A Look at Two-Dimensional Generalizations	252	(3)
Applications	255	(14)
Feature Generation II	269	(52)
Introduction	269	(1)
Regional Features	270	(24)
Features for Texture Characterization	270	(9)
Local Linear Transforms for Texture Feature Extraction	279	(2)
Moments	281	(5)
Parametric Models	286	(8)
Features for Shape and Size Characterization	294	(9)
Fourier Features	295	(3)
Chain Codes	298	(3)
Moment-Based Features	301	(1)
Geometric Features	302	(1)
A Glimpse at Fractals	303	(18)
Self-Similarity and Fractal Dimension	303	(3)
Fractional Brownian Motion	306	(15)
Template Matching	321	(30)
Introduction	321	(1)
Measures Based on Optimal Path Searching Techniques	322	(15)
Bellman's Optimality Principle and Dynamic Programming	324	(1)
The Edit Distance	325	(4)
Dynamic Time Warping in Speech Recognition	329	(8)
Measures Based on Correlations	337	(6)
Deformable Template Models	343	(8)
Context-Dependent Classification	351	(34)
Introduction	351	(1)
The Bayes Classifier	351	(1)
Markov Chain Models	352	(1)
The Viterbi Algorithm	353	(3)
Channel Equalization	356	(5)
Hidden Markov Models	361	(12)
Training Markov Models via Neural Networks	373	(2)
A discussion of Markov Random Fields	375	(10)
System Evaluation	385	(12)
Introduction	385	(1)
Error Counting Approach	385	(2)
Exploiting the Finite Size of the Data Set	387	(3)
A Case Study From Medical Imaging	390	(7)
Clustering: Basic Concepts	397	(32)
Introduction	397	(7)
Applications of Cluster Analysis	400	(1)
Types of Features	401	(1)
Definitions of Clustering	402	(2)
Proximity Measures	404	(25)
Definitions	404	(3)
Proximity Measures between Two Points	407	(11)
Proximity Functions between a Point and a Set	418	(5)
Proximity Functions between Two Sets	423	(6)
Clustering Algorithms I: Sequential Algorithms	429	(20)
Introduction	429	(2)
Number of Possible Clusterings	429	(2)
Categories of Clustering Algorithms	431	(2)
Sequential Clustering Algorithms	433	(4)
Estimation of the Number of Clusters	435	(2)
A Modification of BSAS	437	(1)
A Two-Threshold Sequential Scheme	438	(3)
Refinement Stages	441	(2)
Neural Network Implementation	443	(6)
Description of the Architecture	443	(1)
Implementation of the BSAS Algorithm	444	(5)
Clustering Algorithms II: Hierarchical Algorithms	449	(40)
Introduction	449	(1)
Agglomerative Algorithms	450	(26)
Definition of Some Useful Quantities	451	(2)
Agglomerative Algorithms Based on Matrix Theory	453	(8)
Monotonicity and Crossover	461	(3)
Implementational Issues	464	(1)
Agglomerative Algorithms Based on Graph Theory	464	(10)
Ties in the Proximity Matrix	474	(2)
The Cophenetic Matrix	476	(2)
Divisive Algorithms	478	(2)
Choice of the Best Number of Clusters	480	(9)
Clustering Algorithms III: Schemes Based on Function Optimization	489	(56)
Introduction	489	(2)
Mixture Decomposition Schemes	491	(9)
Compact and Hyperellipsoidal Clusters	493	(4)
A Geometrical Interpretation	497	(3)
Fuzzy Clustering Algorithms	500	(22)
Point Representatives	505	(2)
Quadric Surfaces as Representatives	507	(10)
Hyperplane Representatives	517	(2)
Combining Quadric and Hyperplane Representatives	519	(2)
A Geometrical Interpretation	521	(1)
Convergence Aspects of the Fuzzy Clustering Algorithms	522	(1)
Alternating Cluster Estimation	522	(1)
Possibilistic Clustering	522	(7)
The Mode-Seeking Property	526	(3)
An Alternative Possibilistic Scheme	529	(1)
Hard Clustering Algorithms	529	(4)
The Isodata or k-Means or c-Means Algorithm	531	(2)
Vector Quantization	533	(12)
Clustering Algorithms IV	545	(46)
Introduction	545	(1)
Clustering Algorithms Based on Graph Theory	545	(7)
Minimum Spanning Tree Algorithms	546	(3)
Algorithms Based on Regions of Influence	549	(1)
Algorithms Based on Directed Trees	550	(2)
Competitive Learning Algorithms	552	(9)
Basic Competitive Learning Algorithm	554	(2)
Leaky Learning Algorithm	556	(1)
Conscientious Competitive Learning Algorithms	556	(2)
Competitive Learning--Like Algorithms Associated with Cost Functions	558	(1)
Self-Organizing Maps	559	(1)
Supervised Learning Vector Quantization	560	(1)
Branch and Bound Clustering Algorithms	561	(3)
Binary Morphology Clustering Algorithms (BMCAs)	564	(9)
Discretization	564	(1)
Morphological Operations	565	(3)
Determination of the Clusters in a Discrete Binary Set	568	(2)
Assignment of Feature Vectors to Clusters	570	(1)
The Algorithmic Scheme	571	(2)
Boundary Detection Algorithms	573	(3)
Valley-Seeking Clustering Algorithms	576	(2)
Clustering Via Cost Optimization (Revisited)	578	(4)
Simulated Annealing	579	(1)
Deterministic Annealing	580	(2)
Clustering Using Genetic Algorithms	582	(1)
Other Clustering Algorithms	583	(8)
Cluster Validity	591	(52)
Introduction	591	(1)
Hypothesis Testing Revisited	592	(2)
Hypothesis Testing in Cluster Validity	594	(11)
External Criteria	596	(6)
Internal Criteria	602	(3)
Relative Criteria	605	(16)
Hard Clustering	608	(6)
Fuzzy Clustering	614	(7)
Validity of Individual Clusters	621	(3)
External Criteria	621	(1)
Internal Criteria	622	(2)
Clustering Tendency	624	(19)
Tests for Spatial Randomness	628	(15)
Appendix A Hints from Probability and Statistics	643	(12)
Appendix B Linear Algebra Basics	655	(4)
Appendix C Cost Function Optimization	659	(18)
Appendix D Basic Definitions from Linear Systems Theory	677	(4)
Index	681