Statistical Pattern Recognition, 3rd Edition

Statistical Pattern Recognition......Page 3
Contents......Page 9
Preface......Page 21
Notation......Page 25
1.1.1 Introduction......Page 27
1.1.2 The Basic Model......Page 28
1.2 Stages in a Pattern Recognition Problem......Page 30
1.3 Issues......Page 32
1.4 Approaches to Statistical Pattern Recognition......Page 33
1.5.1 Bayes’ Decision Rule for Minimum Error......Page 34
1.5.2 Bayes’ Decision Rule for Minimum Error – Reject Option......Page 38
1.5.3 Bayes’ Decision Rule for Minimum Risk......Page 39
1.5.5 Neyman–Pearson Decision Rule......Page 41
1.5.6 Minimax Criterion......Page 44
1.5.7 Discussion......Page 45
1.6.1 Introduction......Page 46
1.6.2 Linear Discriminant Functions......Page 47
1.6.3 Piecewise Linear Discriminant Functions......Page 49
1.6.4 Generalised Linear Discriminant Function......Page 50
1.6.5 Summary......Page 52
1.7 Multiple Regression......Page 53
1.9 Notes and References......Page 55
Exercises......Page 57
2.1 Introduction......Page 59
2.2.1 Estimative Approach......Page 60
2.3.1 Specification......Page 61
2.3.2 Derivation of the Gaussian Classifier Plug-In Estimates......Page 63
2.3.3 Example Application Study......Page 65
2.4.2 Na¨ıve Bayes......Page 66
2.4.4 Linear Discriminant Function......Page 67
2.4.5 Regularised Discriminant Analysis......Page 68
2.4.6 Example Application Study......Page 70
2.4.7 Further Developments......Page 71
2.5.1 Introduction......Page 72
2.5.2 Mixture Models for Discrimination......Page 74
2.5.3 Parameter Estimation for Normal Mixture Models......Page 75
2.5.4 Normal Mixture Model Covariance Matrix Constraints......Page 77
2.5.5 How Many Components?......Page 78
2.5.6 Maximum Likelihood Estimation via EM......Page 81
2.5.7 Example Application Study......Page 86
2.5.8 Further Developments......Page 88
2.6 Application Studies......Page 89
2.8 Recommendations......Page 92
Exercises......Page 93
3.1 Introduction......Page 96
3.1.2 Recursive Calculation......Page 98
3.2.1 Conjugate Priors......Page 99
3.2.2 Estimating the Mean of a Normal Distribution with Known Variance......Page 101
3.2.3 Estimating the Mean and the Covariance Matrix of a Multivariate Normal Distribution......Page 105
3.2.4 Unknown Prior Class Probabilities......Page 111
3.3.2 Summarisation......Page 113
3.3.4 Rejection Sampling......Page 115
3.3.5 Ratio of Uniforms......Page 116
3.3.6 Importance Sampling......Page 118
3.4.2 The Gibbs Sampler......Page 121
3.4.3 Metropolis–Hastings Algorithm......Page 129
3.4.4 Data Augmentation......Page 133
3.4.5 Reversible Jump Markov Chain Monte Carlo......Page 134
3.4.6 Slice Sampling......Page 135
3.4.7 MCMC Example – Estimation of Noisy Sinusoids......Page 137
3.4.8 Summary......Page 141
3.5.1 Labelled Training Data......Page 142
3.5.2 Unlabelled Training Data......Page 143
3.6.1 Introduction......Page 145
3.6.2 Basic Methodology......Page 147
3.6.3 Summary......Page 151
3.7.2 Description......Page 152
3.7.3 Factorised Variational Approximation......Page 155
3.7.4 Simple Example......Page 157
3.7.5 Use of the Procedure for Model Selection......Page 161
3.7.6 Further Developments and Applications......Page 162
3.8.1 Introduction......Page 163
3.8.2 ABC Rejection Sampling......Page 164
3.8.3 ABC MCMC Sampling......Page 166
3.8.4 ABC Population Monte Carlo Sampling......Page 167
3.8.5 Model Selection......Page 168
3.8.6 Summary......Page 169
3.9 Example Application Study......Page 170
3.10 Application Studies......Page 171
3.11 Summary and Discussion......Page 172
3.13 Notes and References......Page 173
Exercises......Page 174
4.1.1 Basic Properties of Density Estimators......Page 176
4.2.1 k-Nearest-Neighbour Classifier......Page 178
4.2.2 Derivation......Page 180
4.2.3 Choice of Distance Metric......Page 183
4.2.5 Linear Approximating and Eliminating Search Algorithm......Page 185
4.2.6 Branch and Bound Search Algorithms: kd-Trees......Page 189
4.2.7 Branch and Bound Search Algorithms: Ball-Trees......Page 196
4.2.8 Editing Techniques......Page 200
4.2.9 Example Application Study......Page 203
4.2.10 Further Developments......Page 204
4.2.11 Summary......Page 205
4.3 Histogram Method......Page 206
4.3.2 Independence Assumption (Naïve Bayes)......Page 207
4.3.3 Lancaster Models......Page 208
4.3.4 Maximum Weight Dependence Trees......Page 209
4.3.5 Bayesian Networks......Page 212
4.3.6 Example Application Study – Naïve Bayes Text Classification......Page 216
4.3.7 Summary......Page 219
4.4 Kernel Methods......Page 220
4.4.1 Biasedness......Page 223
4.4.2 Multivariate Extension......Page 224
4.4.3 Choice of Smoothing Parameter......Page 225
4.4.4 Choice of Kernel......Page 227
4.4.5 Example Application Study......Page 228
4.4.7 Summary......Page 229
4.5 Expansion by Basis Functions......Page 230
4.6.2 Mathematical Basis......Page 233
4.6.3 Copula Functions......Page 234
4.6.4 Estimating Copula Probability Density Functions......Page 235
4.6.5 Simple Example......Page 237
4.6.6 Summary......Page 238
4.7 Application Studies......Page 239
4.8 Summary and Discussion......Page 242
4.10 Notes and References......Page 243
Exercises......Page 244
5.1 Introduction......Page 247
5.2.1 General Ideas......Page 248
5.2.2 Perceptron Criterion......Page 249
5.2.3 Fisher’s Criterion......Page 253
5.2.4 Least Mean-Squared-Error Procedures......Page 254
5.2.6 Summary......Page 261
5.3.1 General Ideas......Page 262
5.3.2 Error-Correction Procedure......Page 263
5.3.3 Fisher’s Criterion – Linear Discriminant Analysis......Page 264
5.3.4 Least Mean-Squared-Error Procedures......Page 267
5.3.6 Example Application Study......Page 272
5.3.7 Further Developments......Page 273
5.3.8 Summary......Page 274
5.4.2 Linearly Separable Two-Class Data......Page 275
5.4.3 Linearly Nonseparable Two-Class Data......Page 279
5.4.4 Multiclass SVMs......Page 282
5.4.5 SVMs for Regression......Page 283
5.4.6 Implementation......Page 285
5.4.7 Example Application Study......Page 288
5.5.1 Two-Class Case......Page 289
5.5.2 Maximum Likelihood Estimation......Page 290
5.5.3 Multiclass Logistic Discrimination......Page 292
5.5.5 Further Developments......Page 293
5.7 Summary and Discussion......Page 294
5.8 Recommendations......Page 295
Exercises......Page 296
6.1 Introduction......Page 300
6.2.1 Introduction......Page 302
6.2.3 Specifying the Functional Form......Page 304
6.2.4 The Positions of the Centres......Page 305
6.2.5 Smoothing Parameters......Page 307
6.2.6 Calculation of the Weights......Page 308
6.2.7 Model Order Selection......Page 310
6.2.8 Simple RBF......Page 311
6.2.9 Motivation......Page 312
6.2.11 Example Application Study......Page 314
6.2.12 Further Developments......Page 315
6.2.13 Summary......Page 316
6.3.2 Binary Classification......Page 317
6.3.3 Types of Kernel......Page 318
6.3.4 Model Selection......Page 319
6.3.6 Probability Estimates......Page 320
6.3.8 Example Application Study......Page 322
6.3.9 Further Developments......Page 323
6.4.1 Introduction......Page 324
6.4.2 Specifying the MLP Structure......Page 325
6.4.3 Determining the MLP Weights......Page 326
6.4.5 Logistic Classification......Page 333
6.4.6 Example Application Study......Page 336
6.4.7 Bayesian MLP Networks......Page 337
6.4.9 Summary......Page 339
6.5 Application Studies......Page 340
6.6 Summary and Discussion......Page 342
6.7 Recommendations......Page 343
Exercises......Page 344
7.1 Introduction......Page 348
7.2.1 Introduction......Page 349
7.2.2 Decision Tree Construction......Page 352
7.2.3 Selection of the Splitting Rule......Page 353
7.2.4 Terminating the Splitting Procedure......Page 356
7.2.6 Decision Tree Pruning – Worked Example......Page 358
7.2.7 Decision Tree Construction Methods......Page 363
7.2.8 Other Issues......Page 365
7.2.9 Example Application Study......Page 366
7.2.10 Further Developments......Page 367
7.3.1 Introduction......Page 368
7.3.3 Rule Induction Using a Sequential Covering Algorithm......Page 371
7.3.4 Example Application Study......Page 376
7.4.2 Recursive Partitioning Model......Page 377
7.4.4 Further Developments......Page 381
7.5 Application Studies......Page 382
7.7 Recommendations......Page 384
Exercises......Page 385
8.1 Introduction......Page 387
8.2 Characterising a Classifier Combination Scheme......Page 388
8.2.1 Feature Space......Page 389
8.2.2 Level......Page 392
8.2.4 Form of Component Classifiers......Page 394
8.2.6 Optimisation......Page 395
8.3.1 Architectures......Page 396
8.3.2 Bayesian Approaches......Page 397
8.3.3 Neyman–Pearson Formulation......Page 399
8.3.4 Trainable Rules......Page 400
8.3.5 Fixed Rules......Page 401
8.4.1 Product Rule......Page 402
8.4.2 Sum Rule......Page 403
8.4.3 Min, Max and Median Combiners......Page 404
8.4.5 Borda Count......Page 405
8.4.6 Combiners Trained on Class Predictions......Page 406
8.4.8 Mixture of Experts......Page 408
8.4.9 Bagging......Page 411
8.4.10 Boosting......Page 413
8.4.11 Random Forests......Page 415
8.4.12 Model Averaging......Page 416
8.4.13 Summary of Methods......Page 422
8.4.14 Example Application Study......Page 424
8.5 Application Studies......Page 425
8.6 Summary and Discussion......Page 426
8.8 Notes and References......Page 427
Exercises......Page 428
9.1 Introduction......Page 430
9.2.1 Performance Measures......Page 431
9.2.2 Discriminability......Page 432
9.2.3 Reliability......Page 439
9.2.4 ROC Curves for Performance Assessment......Page 441
9.2.5 Population and Sensor Drift......Page 445
9.2.6 Example Application Study......Page 447
9.2.7 Further Developments......Page 448
9.2.8 Summary......Page 449
9.3.1 Which Technique is Best?......Page 450
9.3.2 Statistical Tests......Page 451
9.3.3 Comparing Rules When Misclassification Costs are Uncertain......Page 452
9.3.4 Example Application Study......Page 454
9.4 Application Studies......Page 455
9.7 Notes and References......Page 456
Exercises......Page 457
10.1 Introduction......Page 459
10.2.1 Introduction......Page 461
10.2.2 Characterisation of Feature Selection Approaches......Page 465
10.2.3 Evaluation Measures......Page 466
10.2.4 Search Algorithms for Feature Subset Selection......Page 475
10.2.5 Complete Search – Branch and Bound......Page 476
10.2.6 Sequential Search......Page 480
10.2.7 Random Search......Page 484
10.2.8 Markov Blanket......Page 485
10.2.9 Stability of Feature Selection......Page 486
10.2.11 Further Developments......Page 488
10.3 Linear Feature Extraction......Page 489
10.3.1 Principal Components Analysis......Page 490
10.3.2 Karhunen–Loève Transformation......Page 501
10.3.3 Example Application Study......Page 507
10.3.4 Further Developments......Page 508
10.3.5 Summary......Page 509
10.4.1 Classical Scaling......Page 510
10.4.2 Metric MDS......Page 512
10.4.3 Ordinal Scaling......Page 513
10.4.4 Algorithms......Page 516
10.4.5 MDS for Feature Extraction......Page 517
10.4.6 Example Application Study......Page 518
10.5 Application Studies......Page 519
10.7 Recommendations......Page 521
10.8 Notes and References......Page 522
Exercises......Page 523
11.1 Introduction......Page 527
11.2 Hierarchical Methods......Page 528
11.2.1 Single-Link Method......Page 529
11.2.2 Complete-Link Method......Page 532
11.2.3 Sum-of-Squares Method......Page 533
11.2.5 Properties of a Hierarchical Classification......Page 534
11.2.7 Summary......Page 535
11.3 Quick Partitions......Page 536
11.4.1 Model Description......Page 537
11.4.2 Example Application Study......Page 538
11.5 Sum-of-Squares Methods......Page 539
11.5.1 Clustering Criteria......Page 540
11.5.2 Clustering Algorithms......Page 541
11.5.3 Vector Quantisation......Page 546
11.5.5 Further Developments......Page 556
11.6.1 Elementary Graph Theory......Page 557
11.6.3 Application to Clustering......Page 560
11.6.5 Forms of Graph Laplacian......Page 561
11.6.6 Example Application Study......Page 562
11.7.1 Introduction......Page 564
11.7.2 Statistical Tests......Page 565
11.7.3 Absence of Class Structure......Page 566
11.7.4 Validity of Individual Clusters......Page 567
11.7.6 Validation of Individual Clusterings......Page 568
11.7.8 Relative Criteria......Page 569
11.7.9 Choosing the Number of Clusters......Page 571
11.8 Application Studies......Page 572
11.9 Summary and Discussion......Page 575
11.10 Recommendations......Page 577
11.11 Notes and References......Page 578
Exercises......Page 579
12.1 Introduction......Page 581
12.1.2 Properties......Page 583
12.1.3 Questions to Address......Page 585
12.1.5 Outline......Page 586
12.2.1 Graph Matrices......Page 587
12.2.3 Distance Measures......Page 588
12.2.5 Centrality Measures......Page 589
12.2.6 Random Graphs......Page 590
12.3.1 Clustering Methods......Page 591
12.3.2 Girvan–Newman Algorithm......Page 594
12.3.3 Modularity Approaches......Page 596
12.3.4 Local Modularity......Page 597
12.3.5 Clique Percolation......Page 599
12.3.6 Example Application Study......Page 600
12.4 Link Prediction......Page 601
12.4.1 Approaches to Link Prediction......Page 602
12.4.3 Further Developments......Page 604
12.6 Summary and Discussion......Page 605
Exercises......Page 606
13.1 Model Selection......Page 607
13.1.2 Cross-Validation......Page 608
13.1.4 Akaike’s Information Criterion......Page 609
13.1.5 Minimum Description Length......Page 610
13.2 Missing Data......Page 611
13.3 Outlier Detection and Robust Procedures......Page 612
13.4 Mixed Continuous and Discrete Variables......Page 613
13.5.1 Bounds on the Expected Risk......Page 614
13.5.2 The VC Dimension......Page 615
References......Page 617
Index......Page 663