This book considers classical and current theory and practice, of supervised, unsupervised and semi-supervised pattern recognition, to build a complete background for professionals and students of engineering. The authors, leading experts in the field of pattern recognition, have provided an up-to-date, self-contained volume encapsulating this wide spectrum of information. The very latest methods are incorporated in this edition: semi-supervised learning, combining clustering algorithms, and relevance feedback.Thoroughly developed to include many more worked examples to give greater understanding of the various methods and techniques Many more diagrams included--now in two color--to provide greater insight through visual presentation Matlab code of the most common methods are given at the end of each chapter An accompanying book with Matlab code of the most common methods and algorithms in the book, together with a descriptive summary and solved examples, and including real-life data sets in imaging and audio recognition. The companion book is available separately or at a special packaged price (Book ISBN: 9780123744869. Package ISBN: 9780123744913) Latest hot topics included to further the reference value of the text including non-linear dimensionality reduction techniques, relevance feedback, semi-supervised learning, spectral clustering, combining clustering algorithms Solutions manual, powerpoint slides, and additional resources are available to faculty using the text for their course. Register at www.textbooks.elsevier.com and search on "Theodoridis" to access resources for instructor.
Author(s): Sergios Theodoridis, Konstantinos Koutroumbas
Edition: 4
Publisher: Academic Press
Year: 2008
Language: English
Pages: 967
Scope And Approach ......Page 12
Supplements To The Text ......Page 13
Acknowledgments ......Page 14
1.1 Is Pattern Recognition Important? ......Page 15
1.2 Features, Feature Vectors, And Classifiers ......Page 18
1.3 Supervised, Unsupervised, And Semi-supervised Learning ......Page 21
1.4 Matlab Programs ......Page 23
1.5 Outline Of The Book ......Page 24
2.2 Bayes Decision Theory ......Page 27
2.3 Discriminant Functions And Decision Surfaces ......Page 33
2.4.1 The Gaussian Probability Density Function ......Page 34
2.4.2 The Bayesian Classifier For Normally Distributed Classes ......Page 38
2.5.1 Maximum Likelihood Parameter Estimation ......Page 48
2.5.2 Maximum A Posteriori Probability Estimation ......Page 52
2.5.3 Bayesian Inference ......Page 53
2.5.4 Maximum Entropy Estimation ......Page 57
2.5.5 Mixture Models ......Page 58
2.5.6 Nonparametric Estimation ......Page 63
2.5.7 The Naive-bayes Classifier ......Page 73
2.6 The Nearest Neighbor Rule ......Page 75
2.7 Bayesian Networks ......Page 78
2.8 Problems ......Page 85
Matlab Programs And Exercises ......Page 93
References ......Page 100
3.2 Linear Discriminant Functions And Decision Hyperplanes ......Page 104
3.3 The Perceptron Algorithm ......Page 106
3.4.1 Mean Square Error Estimation ......Page 116
3.4.2 Stochastic Approximation And The Lms Algorithm ......Page 118
3.4.3 Sum Of Error Squares Estimation ......Page 121
3.5.1 Mean Square Error Regression ......Page 123
3.5.2 Mse Estimates Posterior Class Probabilities ......Page 125
3.5.3 The Bias–variance Dilemma ......Page 127
3.6 Logistic Discrimination ......Page 130
3.7.1 Separable Classes ......Page 132
3.7.2 Nonseparable Classes ......Page 137
3.7.3 The Multiclass Case ......Page 140
3.7.4 -svm ......Page 146
3.7.5 Support Vector Machines: A Geometric Viewpoint ......Page 149
3.7.6 Reduced Convex Hulls ......Page 151
3.8 Problems ......Page 155
Matlab Programs And Exercises ......Page 157
References ......Page 160
4.2 The Xor Problem ......Page 164
4.3 The Two-layer Perceptron ......Page 166
4.3.1 Classification Capabilities Of The Two-layer Perceptron ......Page 169
4.4 Three-layer Perceptrons ......Page 171
4.5 Algorithms Based On Exact Classification Of The Training Set ......Page 173
4.6 The Backpropagation Algorithm ......Page 175
4.7 Variations On The Backpropagation Theme ......Page 182
4.8 The Cost Function Choice ......Page 185
4.9 Choice Of The Network Size ......Page 189
4.10 A Simulation Example ......Page 194
4.11 Networks With Weight Sharing ......Page 196
4.12 Generalized Linear Classifiers ......Page 198
4.13 Capacity Of The L-dimensional Space In Linear Dichotomies ......Page 200
4.14 Polynomial Classifiers ......Page 202
4.15 Radial Basis Function Networks ......Page 203
4.16 Universal Approximators ......Page 207
4.17 Probabilistic Neural Networks ......Page 209
4.18 Support Vector Machines: The Nonlinear Case ......Page 211
4.19 Beyond The Svm Paradigm ......Page 216
4.19.1 Expansion In Kernel Functions And Model Sparsi.cation ......Page 218
4.19.2 Robust Statistics Regression ......Page 224
4.20 Decision Trees ......Page 228
4.20.2 Splitting Criterion ......Page 231
4.20.4 Class Assignment Rule ......Page 232
4.21 Combining Classifiers ......Page 235
4.21.1 Geometric Average Rule ......Page 236
4.21.2 Arithmetic Average Rule ......Page 237
4.21.3 Majority Voting Rule ......Page 238
4.21.4 A Bayesian Viewpoint ......Page 240
4.22 The Boosting Approach To Combine Classifiers ......Page 243
4.23 The Class Imbalance Problem ......Page 250
4.24 Discussion ......Page 252
4.25 Problems ......Page 253
Matlab Programs And Exercises ......Page 257
References ......Page 262
5.1 Introduction ......Page 274
5.2.1 Outlier Removal ......Page 275
5.2.3 Missing Data ......Page 276
5.3 The Peaking Phenomenon ......Page 278
5.4.1 Hypothesis Testing Basics ......Page 281
5.4.2 Application Of The T -test In Feature Selection ......Page 286
5.5 The Receiver Operating Characteristics (roc) Curve ......Page 288
5.6.1 Divergence ......Page 289
5.6.2 Chernoff Bound And Bhattacharyya Distance ......Page 291
5.6.3 Scatter Matrices ......Page 293
5.7.1 Scalar Feature Selection ......Page 296
5.7.2 Feature Vector Selection ......Page 297
5.8 Optimal Feature Generation ......Page 301
5.9 Neural Networks And Feature Generation/selection ......Page 311
5.10 A Hint On Generalization Theory ......Page 312
5.11 The Bayesian Information Criterion ......Page 322
5.12 Problems ......Page 324
Matlab Programs And Exercises ......Page 327
References ......Page 331
6.1 Introduction ......Page 336
6.2 Basis Vectors And Images ......Page 337
6.3 The Karhunen–loève Transform ......Page 339
6.4 The Singular Value Decomposition ......Page 348
6.5 Independent Component Analysis ......Page 355
6.5.1 Ica Based On Secondand Fourth-order Cumulants ......Page 357
6.5.2 Ica Based On Mutual Information ......Page 358
6.5.3 An Ica Simulation Example ......Page 361
6.6 Nonnegative Matrix Factorization ......Page 362
6.7 Nonlinear Dimensionality Reduction ......Page 363
6.7.1 Kernel PCA......Page 364
6.7.2 Graph-based Methods ......Page 366
6.8 The Discrete Fourier Transform (dft) ......Page 376
6.8.1 One-dimensional Dft ......Page 377
6.9 The Discrete Cosine And Sine Transforms ......Page 379
6.10 The Hadamard Transform ......Page 381
6.11 The Haar Transform ......Page 382
6.12 The Haar Expansion Revisited ......Page 384
6.13 Discrete Time Wavelet Transform (dtwt) ......Page 388
6.14 The Multiresolution Interpretation ......Page 397
6.15 Wavelet Packets ......Page 400
6.16 A Look At Two-dimensional Generalizations ......Page 401
6.17 Applications ......Page 403
6.18 Problems ......Page 409
Matlab Programs And Exercises ......Page 412
References ......Page 415
7.1 Introduction ......Page 423
7.2.1 Features For Texture Characterization ......Page 424
7.2.2 Local Linear Transforms For Texture Feature Extraction ......Page 433
7.2.3 Moments ......Page 435
7.2.4 Parametric Models ......Page 439
7.3 Features For Shape And Size Characterization ......Page 447
7.3.1 Fourier Features ......Page 448
7.3.2 Chain Codes ......Page 451
7.3.3 Moment-based Features ......Page 453
7.3.4 Geometric Features ......Page 454
7.4.1 Self-similarity And Fractal Dimension ......Page 456
7.4.2 Fractional Brownian Motion ......Page 458
7.5 Typical Features For Speech And Audio Classification ......Page 463
7.5.1 Short Time Processing Of Signals ......Page 464
7.5.2 Cepstrum ......Page 467
7.5.3 The Mel-cepstrum ......Page 469
7.5.4 Spectral Features ......Page 472
7.5.5 Time Domain Features ......Page 474
7.5.6 An Example ......Page 475
7.6 Problems ......Page 478
Matlab Programs And Exercises ......Page 482
References ......Page 485
8.1 Introduction ......Page 492
8.2 Measures Based On Optimal Path Searching Techniques ......Page 493
8.2.1 Bellman’s Optimality Principle And Dynamic Programming ......Page 495
8.2.2 The Edit Distance ......Page 498
8.2.3 Dynamic Time Warping In Speech Recognition ......Page 502
8.3 Measures Based On Correlations ......Page 509
8.4 Deformable Template Models ......Page 515
8.5 Content-based Information Retrieval: Relevance Feedback ......Page 519
8.6 Problems ......Page 524
Matlab Programs And Exercises ......Page 525
References ......Page 528
9.2 The Bayes Classifier ......Page 531
9.3 Markov Chain Models ......Page 532
9.4 The Viterbi Algorithm ......Page 533
9.5 Channel Equalization ......Page 537
9.6 Hidden Markov Models ......Page 542
9.7 Hmm With State Duration Modeling ......Page 555
9.8 Training Markov Models Via Neural Networks ......Page 562
9.9 A Discussion Of Markov Random Fields ......Page 564
9.10 Problems ......Page 566
Matlab Programs And Exercises ......Page 567
References ......Page 570
10.1 Introduction ......Page 576
10.2 Error-counting Approach ......Page 577
10.3 Exploiting The Finite Size Of The Data Set ......Page 578
10.4 A Case Study From Medical Imaging ......Page 582
10.5 Semi-supervised Learning ......Page 586
10.5.1 Generative Models ......Page 588
10.5.2 Graph-based Methods ......Page 591
10.5.3 Transductive Support Vector Machines ......Page 595
10.6 Problems ......Page 599
References ......Page 600
11.1 Introduction ......Page 604
11.1.1 Applications Of Cluster Analysis ......Page 607
11.1.2 Types Of Features ......Page 608
11.1.3 Definitions Of Clustering ......Page 609
11.2.1 Definitions ......Page 611
11.2.2 Proximity Measures Between Two Points ......Page 613
11.2.3 Proximity Functions Between A Point And A Set ......Page 625
11.2.4 Proximity Functions Between Two Sets ......Page 629
11.3 Problems ......Page 631
References ......Page 633
12.1.1 Number Of Possible Clusterings ......Page 635
12.2 Categories Of Clustering Algorithms ......Page 637
12.3 Sequential Clustering Algorithms ......Page 641
12.3.1 Estimation Of The Number Of Clusters ......Page 643
12.4 A Modification Of Bsas ......Page 645
12.5 A Two-threshold Sequential Scheme ......Page 646
12.6 Refinement Stages ......Page 649
12.7.1 Description Of The Architecture ......Page 651
12.7.2 Implementation Of The Bsas Algorithm ......Page 652
12.8 Problems ......Page 654
Matlab Programs And Exercises ......Page 656
References ......Page 658
13.1 Introduction ......Page 661
13.2 Agglomerative Algorithms ......Page 662
13.2.1 Definition Of Some Useful Quantities ......Page 663
13.2.2 Agglomerative Algorithms Based On Matrix Theory ......Page 666
13.2.3 Monotonicity And Crossover ......Page 672
13.2.5 Agglomerative Algorithms Based On Graph Theory ......Page 675
13.2.6 Ties In The Proximity Matrix ......Page 684
13.3 The Cophenetic Matrix ......Page 687
13.4 Divisive Algorithms ......Page 688
13.5 Hierarchical Algorithms For Large Data Sets ......Page 690
13.6 Choice Of The Best Number Of Clusters ......Page 698
13.7 Problems ......Page 701
Matlab Programs And Exercises ......Page 703
References ......Page 705
14.1 Introduction ......Page 709
14.2 Mixture Decomposition Schemes ......Page 711
14.2.1 Compact And Hyperellipsoidal Clusters ......Page 713
14.2.2 A Geometrical Interpretation ......Page 717
14.3 Fuzzy Clustering Algorithms ......Page 720
14.3.1 Point Representatives ......Page 724
14.3.2 Quadric Surfaces As Representatives ......Page 726
14.3.3 Hyperplane Representatives ......Page 736
14.3.4 Combining Quadric And Hyperplane Representatives ......Page 739
14.3.6 Convergence Aspects Of The Fuzzy Clustering Algorithms ......Page 740
14.4 Possibilistic Clustering ......Page 741
14.4.1 The Mode-seeking Property ......Page 745
14.5 Hard Clustering Algorithms ......Page 747
14.5.1 The Isodata Or K-means Or C-means Algorithm ......Page 749
14.5.2 K -medoids Algorithms ......Page 753
14.6 Vector Quantization ......Page 757
Appendix ......Page 759
14.7 Problems ......Page 760
Matlab Programs And Excercises ......Page 763
References ......Page 766
15.2 Clustering Algorithms Based On Graph Theory ......Page 772
15.2.1 Minimum Spanning Tree Algorithms ......Page 773
15.2.2 Algorithms Based On Regions Of In.uence ......Page 775
15.2.3 Algorithms Based On Directed Trees ......Page 777
15.2.4 Spectral Clustering ......Page 779
15.3 Competitive Learning Algorithms ......Page 787
15.3.1 Basic Competitive Learning Algorithm ......Page 789
15.3.2 Leaky Learning Algorithm ......Page 790
15.3.3 Conscientious Competitive Learning Algorithms ......Page 791
15.3.4 Competitive Learning–like Algorithms Associated With Cost Functions ......Page 792
15.3.5 Self-organizing Maps ......Page 793
15.3.6 Supervised Learning Vector Quantization ......Page 795
15.4 Binary Morphology Clustering Algorithms (bmcas) ......Page 796
15.4.1 Discretization ......Page 797
15.4.2 Morphological Operations ......Page 798
15.4.3 Determination Of The Clusters In A Discrete Binary Set ......Page 801
15.4.4 Assignment Of Feature Vectors To Clusters ......Page 802
15.4.5 The Algorithmic Scheme ......Page 803
15.5 Boundary Detection Algorithms ......Page 805
15.6 Valley-seeking Clustering Algorithms ......Page 808
15.7.1 Branch And Bound Clustering Algorithms ......Page 810
15.7.2 Simulated Annealing ......Page 814
15.7.3 Deterministic Annealing ......Page 815
15.7.4 Clustering Using Genetic Algorithms ......Page 817
15.8 Kernel Clustering Methods ......Page 818
15.9.1 The Dbscan Algorithm ......Page 822
15.9.2 The Dbclasd Algorithm ......Page 825
15.9.3 The Denclue Algorithm ......Page 826
15.10 Clustering Algorithms For High-dimensional Data Sets ......Page 828
15.10.1 Dimensionality Reduction Clustering Approach ......Page 829
15.10.2 Subspace Clustering Approach ......Page 831
15.11 Other Clustering Algorithms ......Page 844
15.12 Combination Of Clusterings ......Page 846
15.13 Problems ......Page 853
Matlab Programs And Exercises ......Page 856
References ......Page 859
16.1 Introduction ......Page 870
16.2 Hypothesis Testing Revisited ......Page 871
16.3 Hypothesis Testing In Cluster Validity ......Page 873
16.3.1 External Criteria ......Page 875
16.3.2 Internal Criteria ......Page 880
16.4 Relative Criteria ......Page 884
16.4.1 Hard Clustering ......Page 887
16.4.2 Fuzzy Clustering ......Page 894
16.5 Validity Of Individual Clusters ......Page 900
16.5.2 Internal Criteria ......Page 901
16.6 Clustering Tendency ......Page 903
16.6.1 Tests For Spatial Randomness ......Page 907
16.7 Problems ......Page 912
References ......Page 916
A.1 Total Probability And The Bayes Rule ......Page 921
A.5 Characteristic Functions ......Page 922
A.6 Moments And Cumulants ......Page 923
A.7 Edgeworth Expansion Of A Pdf ......Page 924
A.8 Kullback–leibler Distance ......Page 925
A.9 Multivariate Gaussian Or Normal Probability Density Function ......Page 926
A.10 Transformation Of Random Variables ......Page 927
A.12 Central Limit Theorem ......Page 929
A.13 Chi-square Distribution ......Page 930
A.15 Beta Distribution ......Page 931
References ......Page 932
B.1 Positive Definite And Symmetric Matrices ......Page 933
B.2 Correlation Matrix Diagonalization ......Page 934
C.1 Gradient Descent Algorithm ......Page 936
C.3 Conjugate-gradient Method ......Page 940
C.4 Optimization For Constrained Problems ......Page 941
References ......Page 951
D.1 Linear Time Invariant (lti) Systems ......Page 952
D.2 Transfer Function ......Page 953
D.4 Two-dimensional Generalizations ......Page 954
Index ......Page 955
